intermediate changes

ref:cde9a383711a11544ce7e107a78147fb96cc4029

1 files changed, 2547 insertions, 0 deletions

diff --git a/contrib/libs/hyperscan/src/nfagraph/ng_repeat.cpp b/contrib/libs/hyperscan/src/nfagraph/ng_repeat.cpp
new file mode 100644
index 0000000000..1f63ad3c6f
--- /dev/null
+++ b/contrib/libs/hyperscan/src/nfagraph/ng_repeat.cpp
@@ -0,0 +1,2547 @@
+/*
+ * Copyright (c) 2015-2018, 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 Bounded repeat analysis.
+ */
+#include "ng_repeat.h"
+
+#include "grey.h"
+#include "ng_depth.h"
+#include "ng_holder.h"
+#include "ng_limex_accel.h"
+#include "ng_prune.h"
+#include "ng_reports.h"
+#include "ng_som_util.h"
+#include "ng_util.h"
+#include "nfa/accel.h"
+#include "nfa/limex_limits.h"
+#include "nfa/repeat_internal.h"
+#include "nfa/repeatcompile.h"
+#include "util/container.h"
+#include "util/dump_charclass.h"
+#include "util/graph_range.h"
+#include "util/graph_small_color_map.h"
+#include "util/graph_undirected.h"
+#include "util/report_manager.h"
+#include "util/unordered.h"
+
+#include <algorithm>
+#include <map>
+#include <queue>
+#include <unordered_map>
+#include <unordered_set>
+
+#include <boost/graph/connected_components.hpp>
+#include <boost/graph/depth_first_search.hpp>
+#include <boost/graph/filtered_graph.hpp>
+#include <boost/graph/reverse_graph.hpp>
+#include <boost/graph/topological_sort.hpp>
+#include <boost/icl/interval_set.hpp>
+
+using namespace std;
+using boost::depth_first_search;
+using boost::depth_first_visit;
+using boost::make_assoc_property_map;
+
+namespace ue2 {
+
+namespace {
+
+/**
+ * \brief Filter that retains only edges between vertices with the same
+ * reachability. Special vertices are dropped.
+ */
+template<class Graph>
+struct ReachFilter {
+    ReachFilter() = default;
+    explicit ReachFilter(const Graph *g_in) : g(g_in) {}
+
+    // Convenience typedefs.
+    using Traits = typename boost::graph_traits<Graph>;
+    using VertexDescriptor = typename Traits::vertex_descriptor;
+    using EdgeDescriptor = typename Traits::edge_descriptor;
+
+    bool operator()(const VertexDescriptor &v) const {
+        assert(g);
+        // Disallow special vertices, as otherwise we will try to remove them
+        // later.
+        return !is_special(v, *g);
+    }
+
+    bool operator()(const EdgeDescriptor &e) const {
+        assert(g);
+        // Vertices must have the same reach.
+        auto u = source(e, *g), v = target(e, *g);
+        const CharReach &cr_u = (*g)[u].char_reach;
+        const CharReach &cr_v = (*g)[v].char_reach;
+        return cr_u == cr_v;
+    }
+
+    const Graph *g = nullptr;
+};
+
+using RepeatGraph = boost::filtered_graph<NGHolder, ReachFilter<NGHolder>,
+                                          ReachFilter<NGHolder>>;
+
+struct ReachSubgraph {
+    vector<NFAVertex> vertices;
+    depth repeatMin{0};
+    depth repeatMax{0};
+    u32 minPeriod = 1;
+    bool is_reset = false;
+    enum RepeatType historyType = REPEAT_RING;
+    bool bad = false; // if true, ignore this case
+};
+
+} // namespace
+
+static
+void findInitDepths(const NGHolder &g,
+                    unordered_map<NFAVertex, NFAVertexDepth> &depths) {
+    auto d = calcDepths(g);
+
+    for (auto v : vertices_range(g)) {
+        size_t idx = g[v].index;
+        assert(idx < d.size());
+        depths.emplace(v, d[idx]);
+    }
+}
+
+static
+vector<NFAVertex> buildTopoOrder(const RepeatGraph &g) {
+    /* Note: RepeatGraph is a filtered version of NGHolder and still has
+     * NFAVertex as its vertex descriptor */
+
+    typedef unordered_set<NFAEdge> EdgeSet;
+    EdgeSet deadEdges;
+
+    // We don't have indices spanning [0,N] on our filtered graph, so we
+    // provide a colour map.
+    unordered_map<NFAVertex, boost::default_color_type> colours;
+
+    depth_first_search(g, visitor(BackEdges<EdgeSet>(deadEdges)).
+                          color_map(make_assoc_property_map(colours)));
+    auto acyclic_g = make_filtered_graph(g, make_bad_edge_filter(&deadEdges));
+
+    vector<NFAVertex> topoOrder;
+    topological_sort(acyclic_g, back_inserter(topoOrder),
+                     color_map(make_assoc_property_map(colours)));
+
+    reverse(topoOrder.begin(), topoOrder.end());
+
+    return topoOrder;
+}
+
+static
+void proper_pred(const NGHolder &g, NFAVertex v,
+                 unordered_set<NFAVertex> &p) {
+    pred(g, v, &p);
+    p.erase(v); // self-loops
+}
+
+static
+void proper_succ(const NGHolder &g, NFAVertex v,
+                 unordered_set<NFAVertex> &s) {
+    succ(g, v, &s);
+    s.erase(v); // self-loops
+}
+
+static
+bool roguePredecessor(const NGHolder &g, NFAVertex v,
+                      const unordered_set<NFAVertex> &involved,
+                      const unordered_set<NFAVertex> &pred) {
+    u32 seen = 0;
+
+    for (auto u : inv_adjacent_vertices_range(v, g)) {
+        if (contains(involved, u)) {
+            continue;
+        }
+        if (!contains(pred, u)) {
+            DEBUG_PRINTF("%zu is a rogue pred\n", g[u].index);
+            return true;
+        }
+
+        seen++;
+    }
+
+    // We must have edges from either (a) none of our external predecessors, or
+    // (b) all of our external predecessors.
+    if (!seen) {
+        return false;
+    }
+    return pred.size() != seen;
+}
+
+static
+bool rogueSuccessor(const NGHolder &g, NFAVertex v,
+                    const unordered_set<NFAVertex> &involved,
+                    const unordered_set<NFAVertex> &succ) {
+    u32 seen = 0;
+    for (auto w : adjacent_vertices_range(v, g)) {
+        if (contains(involved, w)) {
+            continue;
+        }
+
+        if (!contains(succ, w)) {
+            DEBUG_PRINTF("%zu is a rogue succ\n", g[w].index);
+            return true;
+        }
+
+        seen++;
+    }
+
+    // We must have edges to either (a) none of our external successors, or
+    // (b) all of our external successors.
+    if (!seen) {
+        return false;
+    }
+    return succ.size() != seen;
+}
+
+static
+bool hasDifferentTops(const NGHolder &g, const vector<NFAVertex> &verts) {
+    /* TODO: check that we need this now that we allow multiple tops */
+    const flat_set<u32> *tops = nullptr;
+
+    for (auto v : verts) {
+        for (const auto &e : in_edges_range(v, g)) {
+            NFAVertex u = source(e, g);
+            if (u != g.start && u != g.startDs) {
+                continue; // Only edges from starts have valid top properties.
+            }
+            DEBUG_PRINTF("edge (%zu,%zu) with %zu tops\n", g[u].index,
+                         g[v].index, g[e].tops.size());
+            if (!tops) {
+                tops = &g[e].tops;
+            } else if (g[e].tops != *tops) {
+                return true; // More than one set of tops.
+            }
+        }
+    }
+
+    return false;
+}
+
+static
+bool vertexIsBad(const NGHolder &g, NFAVertex v,
+                 const unordered_set<NFAVertex> &involved,
+                 const unordered_set<NFAVertex> &tail,
+                 const unordered_set<NFAVertex> &pred,
+                 const unordered_set<NFAVertex> &succ,
+                 const flat_set<ReportID> &reports) {
+    DEBUG_PRINTF("check vertex %zu\n", g[v].index);
+
+    // We must drop any vertex that is the target of a back-edge within
+    // our subgraph. The tail set contains all vertices that are after v in a
+    // topo ordering.
+    for (auto u : inv_adjacent_vertices_range(v, g)) {
+        if (contains(tail, u)) {
+            DEBUG_PRINTF("back-edge (%zu,%zu) in subgraph found\n",
+                         g[u].index, g[v].index);
+            return true;
+        }
+    }
+
+    // If this vertex has an entry from outside our subgraph, it must have
+    // edges from *all* the vertices in pred and no other external entries.
+    // Similarly for exits.
+    if (roguePredecessor(g, v, involved, pred)) {
+        DEBUG_PRINTF("preds for %zu not well-formed\n", g[v].index);
+        return true;
+    }
+
+    if (rogueSuccessor(g, v, involved, succ)) {
+        DEBUG_PRINTF("succs for %zu not well-formed\n", g[v].index);
+        return true;
+    }
+
+    // All reporting vertices should have the same reports.
+    if (is_match_vertex(v, g) && reports != g[v].reports) {
+        DEBUG_PRINTF("report mismatch to %zu\n", g[v].index);
+        return true;
+    }
+
+    return false;
+}
+
+static
+void splitSubgraph(const NGHolder &g, const deque<NFAVertex> &verts,
+                   const u32 minNumVertices, queue<ReachSubgraph> &q) {
+    DEBUG_PRINTF("entry\n");
+
+    // We construct a copy of the graph using just the vertices we want, rather
+    // than using a filtered_graph -- this way is faster.
+    NGHolder verts_g;
+    unordered_map<NFAVertex, NFAVertex> verts_map; // in g -> in verts_g
+    fillHolder(&verts_g, g, verts, &verts_map);
+
+    const auto ug = make_undirected_graph(verts_g);
+
+    unordered_map<NFAVertex, u32> repeatMap;
+
+    size_t num = connected_components(ug, make_assoc_property_map(repeatMap));
+    DEBUG_PRINTF("found %zu connected repeat components\n", num);
+    assert(num > 0);
+
+    vector<ReachSubgraph> rs(num);
+
+    for (auto v : verts) {
+        assert(!is_special(v, g));
+        auto vu = verts_map.at(v);
+        auto rit = repeatMap.find(vu);
+        if (rit == repeatMap.end()) {
+            continue; /* not part of a repeat */
+        }
+        u32 comp_id = rit->second;
+        assert(comp_id < num);
+        rs[comp_id].vertices.push_back(v);
+    }
+
+    for (const auto &rsi : rs) {
+        if (rsi.vertices.empty()) {
+            // Empty elements can happen when connected_components finds a
+            // subgraph consisting entirely of specials (which aren't added to
+            // ReachSubgraph in the loop above). There's nothing we can do with
+            // these, so we skip them.
+            continue;
+        }
+        DEBUG_PRINTF("repeat with %zu vertices\n", rsi.vertices.size());
+        if (rsi.vertices.size() >= minNumVertices) {
+            DEBUG_PRINTF("enqueuing\n");
+            q.push(rsi);
+        }
+    }
+}
+
+static
+void findFirstReports(const NGHolder &g, const ReachSubgraph &rsi,
+                      flat_set<ReportID> &reports) {
+    for (auto v : rsi.vertices) {
+        if (is_match_vertex(v, g)) {
+            reports = g[v].reports;
+            return;
+        }
+    }
+}
+
+static
+void checkReachSubgraphs(const NGHolder &g, vector<ReachSubgraph> &rs,
+                         const u32 minNumVertices) {
+    if (rs.empty()) {
+        return;
+    }
+
+    DEBUG_PRINTF("%zu subgraphs\n", rs.size());
+
+    vector<ReachSubgraph> rs_out;
+
+    queue<ReachSubgraph> q;
+    for (const auto &rsi : rs) {
+        if (rsi.vertices.size() < minNumVertices) {
+            continue;
+        }
+        q.push(rsi);
+    }
+
+    while (!q.empty()) {
+        const ReachSubgraph &rsi = q.front();
+
+        if (rsi.vertices.size() < minNumVertices) {
+            q.pop(); // Too small for consideration as a repeat.
+            continue;
+        }
+
+        DEBUG_PRINTF("subgraph with %zu vertices\n", rsi.vertices.size());
+
+        // Check that all the edges from outside have the same tops. TODO: we
+        // don't have to throw the whole subgraph out, we could do this check
+        // on a per vertex basis.
+        if (hasDifferentTops(g, rsi.vertices)) {
+            DEBUG_PRINTF("different tops!\n");
+            q.pop();
+            continue;
+        }
+
+        unordered_set<NFAVertex> involved(rsi.vertices.begin(),
+                                          rsi.vertices.end());
+        unordered_set<NFAVertex> tail(involved); // to look for back-edges.
+        unordered_set<NFAVertex> pred, succ;
+        proper_pred(g, rsi.vertices.front(), pred);
+        proper_succ(g, rsi.vertices.back(), succ);
+
+        flat_set<ReportID> reports;
+        findFirstReports(g, rsi, reports);
+
+        bool recalc = false;
+        deque<NFAVertex> verts;
+
+        for (auto v : rsi.vertices) {
+            tail.erase(v); // now contains all vertices _after_ this one.
+
+            if (vertexIsBad(g, v, involved, tail, pred, succ, reports)) {
+                recalc = true;
+                continue;
+            }
+
+            verts.push_back(v);
+        }
+
+        if (recalc) {
+            if (verts.size() < minNumVertices) {
+                DEBUG_PRINTF("subgraph got too small\n");
+                q.pop();
+                continue;
+            }
+            splitSubgraph(g, verts, minNumVertices, q);
+        } else {
+            DEBUG_PRINTF("subgraph is ok\n");
+            rs_out.push_back(rsi);
+        }
+        q.pop();
+    }
+
+    rs.swap(rs_out);
+}
+
+namespace {
+class DistanceSet {
+private:
+    // We use boost::icl to do the heavy lifting.
+    typedef boost::icl::closed_interval<u32> ClosedInterval;
+    typedef boost::icl::interval_set<u32, std::less, ClosedInterval>
+        IntervalSet;
+    IntervalSet distances;
+public:
+    // Add a distance.
+    void insert(u32 d) {
+        distances.insert(d);
+    }
+
+    void add(const DistanceSet &a) {
+        distances += a.distances; // union operation
+    }
+
+    // Increment all the distances by one and add.
+    void add_incremented(const DistanceSet &a) {
+        for (const auto &d : a.distances) {
+            u32 lo = lower(d) + 1;
+            u32 hi = upper(d) + 1;
+            distances.insert(boost::icl::construct<ClosedInterval>(lo, hi));
+        }
+    }
+
+#ifdef DEBUG
+    void dump() const {
+        if (distances.empty()) {
+            printf("<empty>");
+            return;
+        }
+
+        for (const auto &d : distances) {
+            printf("[%u,%u] ", lower(d), upper(d));
+        }
+    }
+#endif
+
+    // True if this distance set is a single contiguous interval.
+    bool is_contiguous() const {
+        IntervalSet::const_iterator it = distances.begin();
+        if (it == distances.end()) {
+            return false;
+        }
+        ++it;
+        return (it == distances.end());
+    }
+
+    pair<u32, u32> get_range() const {
+        assert(is_contiguous());
+        return make_pair(lower(distances), upper(distances));
+    }
+};
+}
+
+/**
+ * Returns false if the given bounds are too large to be implemented with our
+ * runtime engines that handle bounded repeats.
+ */
+static
+bool tooLargeToImplement(const depth &repeatMin, const depth &repeatMax) {
+    if (!repeatMin.is_finite()) {
+        DEBUG_PRINTF("non-finite min bound %s\n", repeatMin.str().c_str());
+        assert(0); // this is a surprise!
+        return true;
+    }
+
+    if ((u32)repeatMin >= REPEAT_INF) {
+        DEBUG_PRINTF("min bound %s too large\n", repeatMin.str().c_str());
+        return true;
+    }
+
+    if (repeatMax.is_finite() && (u32)repeatMax >= REPEAT_INF) {
+        DEBUG_PRINTF("finite max bound %s too large\n", repeatMax.str().c_str());
+        return true;
+    }
+
+    return false;
+}
+
+/** Returns false if the graph is not a supported bounded repeat. */
+static
+bool processSubgraph(const NGHolder &g, ReachSubgraph &rsi,
+                     u32 minNumVertices) {
+    DEBUG_PRINTF("reach subgraph has %zu vertices\n", rsi.vertices.size());
+
+    if (rsi.vertices.size() < minNumVertices) {
+        DEBUG_PRINTF("too small, min is %u\n", minNumVertices);
+        return false;
+    }
+
+    NFAVertex first = rsi.vertices.front();
+    NFAVertex last = rsi.vertices.back();
+
+    typedef unordered_map<NFAVertex, DistanceSet> DistanceMap;
+    DistanceMap dist;
+
+    // Initial distance sets.
+    for (auto u : inv_adjacent_vertices_range(first, g)) {
+        if (u == first) {
+            continue; // no self-loops
+        }
+        DEBUG_PRINTF("pred vertex %zu\n", g[u].index);
+        dist[u].insert(0);
+    }
+
+    for (auto v : rsi.vertices) {
+        for (auto u : inv_adjacent_vertices_range(v, g)) {
+            if (u == v) {
+                continue; // no self-loops
+            }
+
+            auto di = dist.find(u);
+            if (di == dist.end()) {
+                assert(0);
+                return false;
+            }
+
+            dist[v].add_incremented(di->second);
+        }
+    }
+
+    // Remove pred distances from our map.
+    for (auto u : inv_adjacent_vertices_range(first, g)) {
+        if (u == first) {
+            continue; // no self-loops
+        }
+        dist.erase(u);
+    }
+
+    // Calculate final union of distances.
+    DistanceSet final_d;
+    for (auto v : adjacent_vertices_range(last, g)) {
+        if (v == last) {
+            continue; // no self-loops
+        }
+        for (auto u : inv_adjacent_vertices_range(v, g)) {
+            if (u == v) {
+                continue; // no self-loops
+            }
+            auto di = dist.find(u);
+            if (di == dist.end()) {
+                continue;
+            }
+            final_d.add(di->second);
+        }
+    }
+
+#ifdef DEBUG
+    DEBUG_PRINTF("final_d dists: ");
+    final_d.dump();
+    printf("\n");
+#endif
+
+    if (!final_d.is_contiguous()) {
+        // not handled right now
+        DEBUG_PRINTF("not contiguous!\n");
+        return false;
+    }
+
+    pair<u32, u32> range = final_d.get_range();
+    if (range.first > depth::max_value() || range.second > depth::max_value()) {
+        DEBUG_PRINTF("repeat (%u,%u) not representable with depths\n",
+                     range.first, range.second);
+        return false;
+    }
+    rsi.repeatMin = depth(range.first);
+    rsi.repeatMax = depth(range.second);
+
+    // If we've got a self-loop anywhere, we've got inf max.
+    if (anySelfLoop(g, rsi.vertices.begin(), rsi.vertices.end())) {
+        DEBUG_PRINTF("repeat contains self-loop, setting max to INF\n");
+        rsi.repeatMax = depth::infinity();
+    }
+
+    // If our pattern contains a bounded repeat that we wouldn't be able to
+    // implement as runtime, then we have no strategy that leads to
+    // implementation -- it's not like falling back to a DFA or other
+    // non-repeat engine is going to succeed.
+    if (tooLargeToImplement(rsi.repeatMin, rsi.repeatMax)) {
+        throw CompileError("Pattern too large.");
+    }
+
+    return true;
+}
+
+static
+bool allPredsInSubgraph(NFAVertex v, const NGHolder &g,
+                        const unordered_set<NFAVertex> &involved) {
+    for (auto u : inv_adjacent_vertices_range(v, g)) {
+        if (!contains(involved, u)) {
+            return false;
+        }
+    }
+    return true;
+}
+
+static
+void buildTugTrigger(NGHolder &g, NFAVertex cyclic, NFAVertex v,
+                     const unordered_set<NFAVertex> &involved,
+                     unordered_map<NFAVertex, NFAVertexDepth> &depths,
+                     vector<NFAVertex> &tugs) {
+    if (allPredsInSubgraph(v, g, involved)) {
+        // We can transform this vertex into a tug trigger in-place.
+        DEBUG_PRINTF("all preds in subgraph, vertex %zu becomes tug\n",
+                     g[v].index);
+        add_edge(cyclic, v, g);
+        tugs.push_back(v);
+        return;
+    }
+
+    // Some predecessors of v are not in the subgraph, so we need to clone v
+    // and split up its in-edges.
+    NFAVertex t = clone_vertex(g, v);
+    depths[t] = depths[v];
+
+    DEBUG_PRINTF("there are other paths, cloned tug %zu from vertex %zu\n",
+                  g[t].index, g[v].index);
+
+    tugs.push_back(t);
+    add_edge(cyclic, t, g);
+
+    // New vertex gets all of v's successors, including v itself if it's
+    // cyclic.
+    clone_out_edges(g, v, t);
+}
+
+static
+NFAVertex createCyclic(NGHolder &g, ReachSubgraph &rsi) {
+    NFAVertex last = rsi.vertices.back();
+    NFAVertex cyclic = clone_vertex(g, last);
+    add_edge(cyclic, cyclic, g);
+
+    DEBUG_PRINTF("created cyclic vertex %zu\n", g[cyclic].index);
+    return cyclic;
+}
+
+static
+NFAVertex createPos(NGHolder &g, ReachSubgraph &rsi) {
+    NFAVertex pos = add_vertex(g);
+    NFAVertex first = rsi.vertices.front();
+
+    g[pos].char_reach = g[first].char_reach;
+
+    DEBUG_PRINTF("created pos vertex %zu\n", g[pos].index);
+    return pos;
+}
+
+// 2 if v is directly connected to an accept, or 1 if one hop away,
+// or 0 otherwise.
+static
+u32 isCloseToAccept(const NGHolder &g, NFAVertex v) {
+    if (is_any_accept(v, g)) {
+        return 2;
+    }
+
+    for (auto w : adjacent_vertices_range(v, g)) {
+        if (is_any_accept(w, g)) {
+            return 1;
+        }
+    }
+
+    return 0;
+}
+
+static
+u32 unpeelAmount(const NGHolder &g, const ReachSubgraph &rsi) {
+    const NFAVertex last = rsi.vertices.back();
+    u32 rv = 0;
+
+    for (auto v : adjacent_vertices_range(last, g)) {
+        rv = max(rv, isCloseToAccept(g, v));
+    }
+
+    return rv;
+}
+
+static
+void unpeelNearEnd(NGHolder &g, ReachSubgraph &rsi,
+                   unordered_map<NFAVertex, NFAVertexDepth> &depths,
+                   vector<NFAVertex> *succs) {
+    u32 unpeel = unpeelAmount(g, rsi);
+    DEBUG_PRINTF("unpeeling %u vertices\n", unpeel);
+
+    while (unpeel) {
+        NFAVertex last = rsi.vertices.back();
+        NFAVertex first = rsi.vertices.front();
+
+        NFAVertex d = clone_vertex(g, last);
+        depths[d] = depths[last];
+        DEBUG_PRINTF("created vertex %zu\n", g[d].index);
+
+        for (auto v : *succs) {
+            add_edge(d, v, g);
+        }
+
+        if (rsi.repeatMin > depth(1)) {
+            rsi.repeatMin -= 1;
+        } else {
+            /* Skip edge for the cyclic state; note that we must clone their
+             * edge properties as they may include tops. */
+            for (const auto &e : in_edges_range(first, g)) {
+                add_edge(source(e, g), d, g[e], g);
+            }
+        }
+
+        succs->clear();
+        succs->push_back(d);
+
+        rsi.repeatMax -= 1;
+
+        assert(rsi.repeatMin > depth(0));
+        assert(rsi.repeatMax > depth(0));
+
+        unpeel--;
+    }
+}
+
+/** Fetch the set of successor vertices of this subgraph. */
+static
+void getSuccessors(const NGHolder &g, const ReachSubgraph &rsi,
+                   vector<NFAVertex> *succs) {
+    assert(!rsi.vertices.empty());
+    // Successors come from successors of last vertex.
+    NFAVertex last = rsi.vertices.back();
+
+    for (auto v : adjacent_vertices_range(last, g)) {
+        if (v == last) { /* ignore self loop */
+            continue;
+        }
+        succs->push_back(v);
+    }
+}
+
+/** Disconnect the given subgraph from its predecessors and successors in the
+ * NFA graph and replace it with a cyclic state. */
+static
+void replaceSubgraphWithSpecial(NGHolder &g, ReachSubgraph &rsi,
+                               vector<BoundedRepeatData> *repeats,
+                               unordered_map<NFAVertex, NFAVertexDepth> &depths,
+                               unordered_set<NFAVertex> &created) {
+    assert(!rsi.bad);
+    /* As we may need to unpeel 2 vertices, we need the width to be more than 2.
+     * This should only happen if the graph did not have redundancy pass
+     * performed on as vertex count checks would be prevent us reaching here.
+     */
+    if (rsi.repeatMax <= depth(2)) {
+        return;
+    }
+    assert(rsi.repeatMin > depth(0));
+    assert(rsi.repeatMax >= rsi.repeatMin);
+    assert(rsi.repeatMax > depth(2));
+
+    DEBUG_PRINTF("entry\n");
+
+    const unordered_set<NFAVertex> involved(rsi.vertices.begin(),
+                                                 rsi.vertices.end());
+    vector<NFAVertex> succs;
+    getSuccessors(g, rsi, &succs);
+
+    unpeelNearEnd(g, rsi, depths, &succs);
+
+    // Create our replacement cyclic state with the same reachability and
+    // report info as the last vertex in our topo-ordered list.
+    NFAVertex cyclic = createCyclic(g, rsi);
+    created.insert(cyclic);
+
+    // One more special vertex is necessary: the positive trigger (same
+    // reach as cyclic).
+    NFAVertex pos_trigger = createPos(g, rsi);
+    created.insert(pos_trigger);
+    add_edge(pos_trigger, cyclic, g);
+
+    // Update depths for our new vertices.
+    NFAVertex first = rsi.vertices.front(), last = rsi.vertices.back();
+    depths[pos_trigger] = depths[first];
+    depths[cyclic].fromStart =
+        unionDepthMinMax(depths[first].fromStart, depths[last].fromStart);
+    depths[cyclic].fromStartDotStar = unionDepthMinMax(
+        depths[first].fromStartDotStar, depths[last].fromStartDotStar);
+
+    // Wire predecessors to positive trigger.
+    for (const auto &e : in_edges_range(first, g)) {
+        add_edge(source(e, g), pos_trigger, g[e], g);
+    }
+
+    // Wire cyclic state to tug trigger states built from successors.
+    vector<NFAVertex> tugs;
+    for (auto v : succs) {
+        buildTugTrigger(g, cyclic, v, involved, depths, tugs);
+    }
+    created.insert(tugs.begin(), tugs.end());
+    assert(!tugs.empty());
+
+    // Wire pos trigger to tugs if min repeat is one -- this deals with cases
+    // where we can get a pos and tug trigger on the same byte.
+    if (rsi.repeatMin == depth(1)) {
+        for (auto v : tugs) {
+            add_edge(pos_trigger, v, g);
+        }
+    }
+
+    // Remove the vertices/edges in the subgraph.
+    remove_vertices(rsi.vertices, g, false);
+    erase_all(&depths, rsi.vertices);
+
+    repeats->push_back(BoundedRepeatData(rsi.historyType, rsi.repeatMin,
+                                         rsi.repeatMax, rsi.minPeriod, cyclic,
+                                         pos_trigger, tugs));
+}
+
+/** Variant for Rose-specific graphs that terminate in a sole accept, so we can
+ * use a "lazy tug". See UE-1636. */
+static
+void replaceSubgraphWithLazySpecial(NGHolder &g, ReachSubgraph &rsi,
+                          vector<BoundedRepeatData> *repeats,
+                          unordered_map<NFAVertex, NFAVertexDepth> &depths,
+                          unordered_set<NFAVertex> &created) {
+    assert(!rsi.bad);
+    assert(rsi.repeatMin);
+    assert(rsi.repeatMax >= rsi.repeatMin);
+
+    DEBUG_PRINTF("entry\n");
+
+    const unordered_set<NFAVertex> involved(rsi.vertices.begin(),
+                                            rsi.vertices.end());
+    vector<NFAVertex> succs;
+    getSuccessors(g, rsi, &succs);
+
+    // Create our replacement cyclic state with the same reachability and
+    // report info as the last vertex in our topo-ordered list.
+    NFAVertex cyclic = createCyclic(g, rsi);
+    created.insert(cyclic);
+
+    // One more special vertex is necessary: the positive trigger (same
+    // reach as cyclic).
+    NFAVertex pos_trigger = createPos(g, rsi);
+    created.insert(pos_trigger);
+    add_edge(pos_trigger, cyclic, g);
+
+    // Update depths for our new vertices.
+    NFAVertex first = rsi.vertices.front(), last = rsi.vertices.back();
+    depths[pos_trigger] = depths[first];
+    depths[cyclic].fromStart =
+        unionDepthMinMax(depths[first].fromStart, depths[last].fromStart);
+    depths[cyclic].fromStartDotStar = unionDepthMinMax(
+        depths[first].fromStartDotStar, depths[last].fromStartDotStar);
+
+    // Wire predecessors to positive trigger.
+    for (const auto &e : in_edges_range(first, g)) {
+        add_edge(source(e, g), pos_trigger, g[e], g);
+    }
+
+    // In the rose case, our tug is our cyclic, and it's wired to our
+    // successors (which should be just the accept).
+    vector<NFAVertex> tugs;
+    assert(succs.size() == 1);
+    for (auto v : succs) {
+        add_edge(cyclic, v, g);
+    }
+
+    // Wire pos trigger to accept if min repeat is one -- this deals with cases
+    // where we can get a pos and tug trigger on the same byte.
+    if (rsi.repeatMin == depth(1)) {
+        for (auto v : succs) {
+            add_edge(pos_trigger, v, g);
+            g[pos_trigger].reports = g[cyclic].reports;
+        }
+    }
+
+    // Remove the vertices/edges in the subgraph.
+    remove_vertices(rsi.vertices, g, false);
+    erase_all(&depths, rsi.vertices);
+
+    repeats->push_back(BoundedRepeatData(rsi.historyType, rsi.repeatMin,
+                                         rsi.repeatMax, rsi.minPeriod, cyclic,
+                                         pos_trigger, tugs));
+}
+
+static
+bool isCompBigEnough(const RepeatGraph &rg, const u32 minRepeat) {
+    // filtered_graph doesn't filter the num_vertices call.
+    size_t n = 0;
+    RepeatGraph::vertex_iterator vi, ve;
+    for (tie(vi, ve) = vertices(rg); vi != ve; ++vi) {
+        if (++n >= minRepeat) {
+            return true;
+        }
+    }
+    return false;
+}
+
+// Marks the subgraph as bad if it can't be handled.
+static
+void reprocessSubgraph(const NGHolder &h, const Grey &grey,
+                       ReachSubgraph &rsi) {
+    vector<ReachSubgraph> rs(1, rsi);
+    checkReachSubgraphs(h, rs, grey.minExtBoundedRepeatSize);
+    if (rs.size() != 1) {
+        DEBUG_PRINTF("subgraph split into %zu\n", rs.size());
+        rsi.bad = true;
+        return;
+    }
+
+    rsi = rs.back(); // Potentially modified.
+
+    if (processSubgraph(h, rsi, grey.minExtBoundedRepeatSize)) {
+        DEBUG_PRINTF("reprocessed subgraph is {%s,%s} repeat\n",
+                     rsi.repeatMin.str().c_str(), rsi.repeatMax.str().c_str());
+    } else {
+        DEBUG_PRINTF("reprocessed subgraph is bad\n");
+        rsi.bad = true;
+    }
+}
+
+/** Remove vertices from the beginning and end of the vertex set that are
+ * involved in other repeats as a result of earlier repeat transformations. */
+static
+bool peelSubgraph(const NGHolder &g, const Grey &grey, ReachSubgraph &rsi,
+                  const unordered_set<NFAVertex> &created) {
+    assert(!rsi.bad);
+
+    if (created.empty()) {
+        return true;
+    }
+
+    if (rsi.vertices.empty()) {
+        return false;
+    }
+
+    // Peel involved vertices from the front.
+    vector<NFAVertex>::iterator zap = rsi.vertices.end();
+    for (auto it = rsi.vertices.begin(), ite = rsi.vertices.end(); it != ite;
+         ++it) {
+        if (!contains(created, *it)) {
+            zap = it;
+            break;
+        } else {
+            DEBUG_PRINTF("%zu is involved in another repeat\n", g[*it].index);
+        }
+    }
+    DEBUG_PRINTF("peeling %zu vertices from front\n",
+                 distance(rsi.vertices.begin(), zap));
+    rsi.vertices.erase(rsi.vertices.begin(), zap);
+
+    // Peel involved vertices and vertices with edges to involved vertices from
+    // the back; otherwise we may try to transform a POS into a TUG.
+    zap = rsi.vertices.begin();
+    for (auto it = rsi.vertices.rbegin(), ite = rsi.vertices.rend(); it != ite;
+         ++it) {
+        if (!contains(created, *it) &&
+            !contains_any_of(created, adjacent_vertices(*it, g))) {
+            zap = it.base(); // Note: erases everything after it.
+            break;
+        } else {
+            DEBUG_PRINTF("%zu is involved in another repeat\n", g[*it].index);
+        }
+    }
+    DEBUG_PRINTF("peeling %zu vertices from back\n",
+                 distance(zap, rsi.vertices.end()));
+    rsi.vertices.erase(zap, rsi.vertices.end());
+
+    // If vertices in the middle are involved in other repeats, it's a definite
+    // no-no.
+    for (auto v : rsi.vertices) {
+        if (contains(created, v)) {
+            DEBUG_PRINTF("vertex %zu is in another repeat\n", g[v].index);
+            return false;
+        }
+    }
+
+    reprocessSubgraph(g, grey, rsi);
+    return !rsi.bad;
+}
+
+/** For performance reasons, it's nice not to have an exceptional state right
+ * next to a startDs state: that way we can do double-byte accel, whereas
+ * otherwise the NEG trigger would limit us to single. This might be a good
+ * idea to extend to cyclic states, too. */
+static
+void peelStartDotStar(const NGHolder &g,
+                      const unordered_map<NFAVertex, NFAVertexDepth> &depths,
+                      const Grey &grey, ReachSubgraph &rsi) {
+    if (rsi.vertices.size() < 1) {
+        return;
+    }
+
+    NFAVertex first = rsi.vertices.front();
+    if (depths.at(first).fromStartDotStar.min == depth(1)) {
+        DEBUG_PRINTF("peeling start front vertex %zu\n", g[first].index);
+        rsi.vertices.erase(rsi.vertices.begin());
+        reprocessSubgraph(g, grey, rsi);
+    }
+}
+
+static
+void buildReachSubgraphs(const NGHolder &g, vector<ReachSubgraph> &rs,
+                         const u32 minNumVertices) {
+    const ReachFilter<NGHolder> fil(&g);
+    const RepeatGraph rg(g, fil, fil);
+
+    if (!isCompBigEnough(rg, minNumVertices)) {
+        DEBUG_PRINTF("component not big enough, bailing\n");
+        return;
+    }
+
+    const auto ug = make_undirected_graph(rg);
+
+    unordered_map<NFAVertex, u32> repeatMap;
+
+    unsigned int num;
+    num = connected_components(ug, make_assoc_property_map(repeatMap));
+    DEBUG_PRINTF("found %u connected repeat components\n", num);
+
+    // Now, we build a set of topo-ordered ReachSubgraphs.
+    vector<NFAVertex> topoOrder = buildTopoOrder(rg);
+
+    rs.resize(num);
+
+    for (auto v : topoOrder) {
+        auto rit = repeatMap.find(v);
+        if (rit == repeatMap.end()) {
+            continue; /* not part of a repeat */
+        }
+        u32 comp_id = rit->second;
+        assert(comp_id < num);
+        rs[comp_id].vertices.push_back(v);
+    }
+
+#ifdef DEBUG
+    for (size_t i = 0; i < rs.size(); i++) {
+        DEBUG_PRINTF("rs %zu has %zu vertices.\n", i, rs[i].vertices.size());
+    }
+#endif
+}
+
+static
+bool hasSkipEdges(const NGHolder &g, const ReachSubgraph &rsi) {
+    assert(!rsi.vertices.empty());
+
+    const NFAVertex first = rsi.vertices.front();
+    const NFAVertex last = rsi.vertices.back();
+
+    // All of the preds of first must have edges to all the successors of last.
+    for (auto u : inv_adjacent_vertices_range(first, g)) {
+        for (auto v : adjacent_vertices_range(last, g)) {
+            if (!edge(u, v, g).second) {
+                return false;
+            }
+        }
+    }
+
+    return true;
+}
+
+/* depth info is valid as calculated at entry */
+static
+bool entered_at_fixed_offset(NFAVertex v, const NGHolder &g,
+            const unordered_map<NFAVertex, NFAVertexDepth> &depths,
+            const unordered_set<NFAVertex> &reached_by_fixed_tops) {
+    DEBUG_PRINTF("|reached_by_fixed_tops| %zu\n",
+                  reached_by_fixed_tops.size());
+    if (is_triggered(g) && !contains(reached_by_fixed_tops, v)) {
+        /* can't do this for infix/suffixes unless we know trigger literals
+         * can only occur at one offset */
+        DEBUG_PRINTF("bad top(s) for %zu\n", g[v].index);
+        return false;
+    }
+
+    if (depths.at(v).fromStartDotStar.min.is_reachable()) {
+        DEBUG_PRINTF("reachable from startDs\n");
+        return false;
+    }
+
+    /* look at preds as v may be cyclic */
+    const depth &first = depths.at(v).fromStart.min;
+    assert(first.is_reachable());
+    if (!first.is_finite()) {
+        DEBUG_PRINTF("first not finite\n");
+        return false;
+    }
+    DEBUG_PRINTF("first is at least %s from start\n", first.str().c_str());
+
+    for (auto u : inv_adjacent_vertices_range(v, g)) {
+        const depth &u_max_depth = depths.at(u).fromStart.max;
+        DEBUG_PRINTF("pred %zu max depth %s from start\n", g[u].index,
+                     u_max_depth.str().c_str());
+        if (u_max_depth != first - depth(1)) {
+            return false;
+        }
+    }
+
+    return true;
+}
+
+static
+NFAVertex buildTriggerStates(NGHolder &g, const vector<CharReach> &trigger,
+                             u32 top) {
+    NFAVertex u = g.start;
+    for (const auto &cr : trigger) {
+        NFAVertex v = add_vertex(g);
+        g[v].char_reach = cr;
+        add_edge(u, v, g);
+        if (u == g.start) {
+            g[edge(u, v, g)].tops.insert(top);
+        }
+        u = v;
+    }
+
+    DEBUG_PRINTF("trigger len=%zu has sink %zu\n", trigger.size(), g[u].index);
+    return u;
+}
+
+/**
+ * For triggered graphs, replace the "top" edges from start with the triggers
+ * they represent, for the purposes of determining sole entry.
+ */
+static
+void addTriggers(NGHolder &g,
+                 const map<u32, vector<vector<CharReach>>> &triggers) {
+    if (!is_triggered(g)) {
+        assert(triggers.empty());
+        return;
+    }
+
+    vector<NFAEdge> dead;
+    map<u32, vector<NFAVertex>> starts_by_top;
+
+    for (const auto &e : out_edges_range(g.start, g)) {
+        const NFAVertex &v = target(e, g);
+        if (v == g.startDs) {
+            continue;
+        }
+
+        const auto &tops = g[e].tops;
+
+        // The caller may not have given us complete trigger information. If we
+        // don't have any triggers for a particular top, we should just leave
+        // it alone.
+        for (u32 top : tops) {
+            if (!contains(triggers, top)) {
+                DEBUG_PRINTF("no triggers for top %u\n", top);
+                goto next_edge;
+            }
+
+            starts_by_top[top].push_back(v);
+        }
+        dead.push_back(e);
+    next_edge:;
+    }
+
+    remove_edges(dead, g);
+
+    for (const auto &m : starts_by_top) {
+        const auto &top = m.first;
+        const auto &starts = m.second;
+
+        assert(contains(triggers, top));
+        const auto &top_triggers = triggers.at(top);
+
+        for (const auto &trigger : top_triggers) {
+            NFAVertex u = buildTriggerStates(g, trigger, top);
+            for (const auto &v : starts) {
+                add_edge_if_not_present(u, v, g);
+            }
+        }
+    }
+}
+
+static
+CharReach predReach(const NGHolder &g, NFAVertex v) {
+    CharReach cr;
+    for (auto u : inv_adjacent_vertices_range(v, g)) {
+        cr |= g[u].char_reach;
+    }
+    return cr;
+}
+
+/**
+ * Filter the given vertex map (which maps from vertices in another graph to
+ * vertices in subg) so that it only contains vertices that actually exist in
+ * subg.
+ */
+static
+void filterMap(const NGHolder &subg,
+               unordered_map<NFAVertex, NFAVertex> &vmap) {
+    NGHolder::vertex_iterator vi, ve;
+    tie(vi, ve) = vertices(subg);
+    const unordered_set<NFAVertex> remaining_verts(vi, ve);
+
+    unordered_map<NFAVertex, NFAVertex> fmap; // filtered map
+
+    for (const auto &m : vmap) {
+        if (contains(remaining_verts, m.second)) {
+            fmap.insert(m);
+        }
+    }
+
+    vmap.swap(fmap);
+}
+
+/** Construct a graph for sole entry analysis that only considers paths through
+ * the bounded repeat. */
+static
+void buildRepeatGraph(NGHolder &rg,
+                      unordered_map<NFAVertex, NFAVertex> &rg_map,
+                      const NGHolder &g, const ReachSubgraph &rsi,
+                      const map<u32, vector<vector<CharReach>>> &triggers) {
+    cloneHolder(rg, g, &rg_map);
+    assert(rg.kind == g.kind);
+
+    clear_in_edges(rg.accept, rg);
+    clear_in_edges(rg.acceptEod, rg);
+    add_edge(rg.accept, rg.acceptEod, rg);
+
+    // Find the set of vertices in rg involved in the repeat.
+    unordered_set<NFAVertex> rg_involved;
+    for (const auto &v : rsi.vertices) {
+        assert(contains(rg_map, v));
+        rg_involved.insert(rg_map.at(v));
+    }
+
+    // Remove all out-edges from repeat vertices that aren't to other repeat
+    // vertices, then connect terminal repeat vertices to accept.
+    for (const auto &v : rsi.vertices) {
+        NFAVertex rv = rg_map.at(v);
+        remove_out_edge_if(rv, [&](const NFAEdge &e) {
+            return !contains(rg_involved, target(e, rg));
+        }, rg);
+        if (!has_successor(rv, rg)) { // no interior out-edges
+            add_edge(rv, rg.accept, rg);
+        }
+    }
+
+    pruneUseless(rg);
+
+    if (is_triggered(rg)) {
+        // Add vertices for all our triggers
+        addTriggers(rg, triggers);
+        renumber_vertices(rg);
+
+        // We don't know anything about how often this graph is triggered, so we
+        // make the start vertex cyclic for the purposes of this analysis ONLY.
+        add_edge(rg.start, rg.start, rg);
+    }
+
+    filterMap(rg, rg_map);
+
+    // All of our repeat vertices should have vertices in rg.
+    assert(all_of(begin(rsi.vertices), end(rsi.vertices),
+                  [&](const NFAVertex &v) { return contains(rg_map, v); }));
+}
+
+/**
+ * Construct an input DAG which accepts on all entries to the repeat.
+ */
+static
+void buildInputGraph(NGHolder &lhs,
+                     unordered_map<NFAVertex, NFAVertex> &lhs_map,
+                     const NGHolder &g, const NFAVertex first,
+                     const map<u32, vector<vector<CharReach>>> &triggers) {
+    DEBUG_PRINTF("building lhs with first=%zu\n", g[first].index);
+    cloneHolder(lhs, g, &lhs_map);
+    assert(g.kind == lhs.kind);
+    addTriggers(lhs, triggers);
+    renumber_vertices(lhs);
+
+    // Replace each back-edge (u,v) with an edge (startDs,v), which will
+    // generate entries at at least the rate of the loop created by that
+    // back-edge.
+    set<NFAEdge> dead;
+    BackEdges<set<NFAEdge> > backEdgeVisitor(dead);
+    depth_first_search(lhs, visitor(backEdgeVisitor).root_vertex(lhs.start));
+    for (const auto &e : dead) {
+        const NFAVertex u = source(e, lhs), v = target(e, lhs);
+        if (u == v) {
+            continue; // Self-loops are OK.
+        }
+
+        DEBUG_PRINTF("replacing back-edge (%zu,%zu) with edge (startDs,%zu)\n",
+                     lhs[u].index, lhs[v].index, lhs[v].index);
+
+        add_edge_if_not_present(lhs.startDs, v, lhs);
+        remove_edge(e, lhs);
+    }
+
+    clear_in_edges(lhs.accept, lhs);
+    clear_in_edges(lhs.acceptEod, lhs);
+    add_edge(lhs.accept, lhs.acceptEod, lhs);
+
+    // Wire the predecessors of the first repeat vertex to accept, then prune.
+    NFAVertex lhs_first = lhs_map.at(first);
+    for (auto u : inv_adjacent_vertices_range(lhs_first, lhs)) {
+        add_edge_if_not_present(u, lhs.accept, lhs);
+    }
+
+    pruneUseless(lhs);
+    filterMap(lhs, lhs_map);
+}
+
+/**
+ * Maximum number of vertices in the input DAG to actually allow sole entry
+ * calculation (as very large cases make sentClearsTail take a long, long time
+ * to complete.)
+ */
+static const size_t MAX_SOLE_ENTRY_VERTICES = 10000;
+
+/** True if (1) fixed offset or (2) reentries to this subgraph must involve a
+ * character which escapes the repeat, meaning that we only need to store a
+ * single offset at runtime. See UE-1361. */
+static
+bool hasSoleEntry(const NGHolder &g, const ReachSubgraph &rsi,
+                  const unordered_map<NFAVertex, NFAVertexDepth> &depths,
+                  const unordered_set<NFAVertex> &reached_by_fixed_tops,
+                  const map<u32, vector<vector<CharReach>>> &triggers) {
+    DEBUG_PRINTF("checking repeat {%s,%s}\n", rsi.repeatMin.str().c_str(),
+                 rsi.repeatMax.str().c_str());
+    NFAVertex first = rsi.vertices.front();
+    const CharReach &repeatReach = g[first].char_reach;
+
+    /* trivial case first is at a fixed depth */
+    if (entered_at_fixed_offset(first, g, depths, reached_by_fixed_tops)) {
+        DEBUG_PRINTF("fixed depth\n");
+        return true;
+    }
+
+    DEBUG_PRINTF("repeat reach is %s\n", describeClass(repeatReach).c_str());
+
+    // Nothing can escape a dot repeat.
+    if (repeatReach.all()) {
+        DEBUG_PRINTF("dot repeat cannot be escaped\n");
+        return false;
+    }
+
+    // Another easy case: if the union of the reach of all entries to the
+    // repeat will always escape the repeat, we have sole entry.
+    if (predReach(g, first).isSubsetOf(~repeatReach)) {
+        DEBUG_PRINTF("pred reach %s, which is subset of repeat escape\n",
+                     describeClass(predReach(g, first)).c_str());
+        return true;
+    }
+
+    NGHolder rg;
+    unordered_map<NFAVertex, NFAVertex> rg_map;
+    buildRepeatGraph(rg, rg_map, g, rsi, triggers);
+    assert(rg.kind == g.kind);
+
+    NGHolder lhs;
+    unordered_map<NFAVertex, NFAVertex> lhs_map;
+    buildInputGraph(lhs, lhs_map, g, first, triggers);
+    assert(lhs.kind == g.kind);
+
+    if (num_vertices(lhs) > MAX_SOLE_ENTRY_VERTICES) {
+        DEBUG_PRINTF("too many vertices (%zu) for sole entry test.\n",
+                     num_vertices(lhs));
+        return false;
+    }
+
+    // Split the repeat graph into two regions: vertices in the LHS input DAG
+    // are in one region, vertices in the bounded repeat are in another.
+    const u32 lhs_region = 1;
+    const u32 repeat_region = 2;
+    unordered_map<NFAVertex, u32> region_map;
+
+    for (const auto &v : rsi.vertices) {
+        assert(!is_special(v, g)); // no specials in repeats
+        assert(contains(rg_map, v));
+        DEBUG_PRINTF("rg vertex %zu in repeat\n", rg[rg_map.at(v)].index);
+        region_map.emplace(rg_map.at(v), repeat_region);
+    }
+
+    for (const auto &v : vertices_range(rg)) {
+        if (!contains(region_map, v)) {
+            DEBUG_PRINTF("rg vertex %zu in lhs (trigger)\n", rg[v].index);
+            region_map.emplace(v, lhs_region);
+        }
+    }
+
+    u32 bad_region = 0;
+    if (sentClearsTail(rg, region_map, lhs, lhs_region, &bad_region)) {
+        DEBUG_PRINTF("input dag clears repeat: sole entry\n");
+        return true;
+    }
+
+    DEBUG_PRINTF("not sole entry\n");
+    return false;
+}
+
+namespace {
+
+template<class Graph>
+struct StrawWalker {
+    StrawWalker(const NGHolder &h_in, const Graph &g_in,
+                const vector<BoundedRepeatData> &all_repeats)
+        : h(h_in), g(g_in), repeats(all_repeats) {}
+
+    /** True if v is a cyclic that belongs to a bounded repeat (one without an
+     * inf max bound). */
+    bool isBoundedRepeatCyclic(NFAVertex v) const {
+        for (const auto &r : repeats) {
+            if (r.repeatMax.is_finite() && r.cyclic == v) {
+                return true;
+            }
+        }
+        return false;
+    }
+
+    NFAVertex step(NFAVertex v) const {
+        typename Graph::adjacency_iterator ai, ae;
+        tie(ai, ae) = adjacent_vertices(v, g);
+        assert(ai != ae);
+        NFAVertex next = *ai;
+        if (next == v) { // Ignore self loop.
+            ++ai;
+            if (ai == ae) {
+                return NGHolder::null_vertex();
+            }
+            next = *ai;
+        }
+        ++ai;
+        if (ai != ae && *ai == v) { // Ignore self loop
+            ++ai;
+        }
+        if (ai != ae) {
+            DEBUG_PRINTF("more than one succ\n");
+            set<NFAVertex> succs;
+            insert(&succs, adjacent_vertices(v, g));
+            succs.erase(v);
+            for (tie(ai, ae) = adjacent_vertices(v, g); ai != ae; ++ai) {
+                next = *ai;
+                DEBUG_PRINTF("checking %zu\n", g[next].index);
+                if (next == v) {
+                    continue;
+                }
+                set<NFAVertex> lsuccs;
+                insert(&lsuccs, adjacent_vertices(next, g));
+
+                if (lsuccs != succs) {
+                    continue;
+                }
+
+                // Ensure that if v is in connected to accept, the reports
+                // on `next` much match.
+                if (is_match_vertex(v, h) && g[v].reports != g[next].reports) {
+                    DEBUG_PRINTF("report mismatch\n");
+                    continue;
+                }
+
+                return next;
+            }
+            DEBUG_PRINTF("bailing\n");
+            return NGHolder::null_vertex();
+        }
+        return next;
+    }
+
+    NFAVertex walk(NFAVertex v, vector<NFAVertex> &straw) const {
+        DEBUG_PRINTF("walk from %zu\n", g[v].index);
+        unordered_set<NFAVertex> visited;
+        straw.clear();
+
+        while (!is_special(v, g)) {
+            DEBUG_PRINTF("checking %zu\n", g[v].index);
+            NFAVertex next = step(v);
+            if (next == NGHolder::null_vertex()) {
+                break;
+            }
+            if (!visited.insert(next).second) {
+                DEBUG_PRINTF("already visited %zu, bailing\n", g[next].index);
+                break; /* don't want to get stuck in any complicated loops */
+            }
+
+            const CharReach &reach_v = g[v].char_reach;
+            const CharReach &reach_next = g[next].char_reach;
+            if (!reach_v.isSubsetOf(reach_next)) {
+                DEBUG_PRINTF("%zu's reach is not a superset of %zu's\n",
+                             g[next].index, g[v].index);
+                break;
+            }
+
+            // If this is cyclic with the right reach, we're done. Note that
+            // startDs fulfils this requirement.
+            if (hasSelfLoop(next, g) && !isBoundedRepeatCyclic(next)) {
+                DEBUG_PRINTF("found cyclic %zu\n", g[next].index);
+                return next;
+            }
+
+            v = next;
+            straw.push_back(v);
+        }
+
+        straw.clear();
+        return NGHolder::null_vertex();
+    }
+
+private:
+    const NGHolder &h; // underlying graph
+    const Graph &g;
+    const vector<BoundedRepeatData> &repeats;
+};
+
+} // namespace
+
+static
+NFAVertex walkStrawToCyclicRev(const NGHolder &g, NFAVertex v,
+                               const vector<BoundedRepeatData> &all_repeats,
+                               vector<NFAVertex> &straw) {
+    typedef boost::reverse_graph<NGHolder, const NGHolder &> RevGraph;
+    const RevGraph revg(g);
+
+    auto cyclic = StrawWalker<RevGraph>(g, revg, all_repeats).walk(v, straw);
+    reverse(begin(straw), end(straw)); // path comes from cyclic
+    return cyclic;
+}
+
+static
+NFAVertex walkStrawToCyclicFwd(const NGHolder &g, NFAVertex v,
+                               const vector<BoundedRepeatData> &all_repeats,
+                               vector<NFAVertex> &straw) {
+    return StrawWalker<NGHolder>(g, g, all_repeats).walk(v, straw);
+}
+
+/** True if entries to this subgraph must pass through a cyclic state with
+ * reachability that is a superset of the reach of the repeat, and
+ * reachabilities along this path "nest" into the reaches of their
+ * predecessors.
+ *
+ * This is what is called a 'straw' in the region code. */
+static
+bool hasCyclicSupersetEntryPath(const NGHolder &g, const ReachSubgraph &rsi,
+                                const vector<BoundedRepeatData> &all_repeats) {
+    // Cope with peeling by following a chain of single vertices backwards
+    // until we encounter our cyclic, all of which must have superset reach.
+    vector<NFAVertex> straw;
+    return walkStrawToCyclicRev(g, rsi.vertices.front(), all_repeats, straw) !=
+           NGHolder::null_vertex();
+}
+
+static
+bool hasCyclicSupersetExitPath(const NGHolder &g, const ReachSubgraph &rsi,
+                               const vector<BoundedRepeatData> &all_repeats) {
+    vector<NFAVertex> straw;
+    return walkStrawToCyclicFwd(g, rsi.vertices.back(), all_repeats, straw) !=
+           NGHolder::null_vertex();
+}
+
+static
+bool leadsOnlyToAccept(const NGHolder &g, const ReachSubgraph &rsi) {
+    const NFAVertex u = rsi.vertices.back();
+    for (auto v : adjacent_vertices_range(u, g)) {
+        if (v != g.accept) {
+            return false;
+        }
+    }
+    assert(out_degree(u, g));
+    return true;
+}
+
+static
+bool allSimpleHighlander(const ReportManager &rm,
+                         const flat_set<ReportID> &reports) {
+    assert(!reports.empty());
+    for (auto report : reports) {
+        if (!isSimpleExhaustible(rm.getReport(report))) {
+            return false;
+        }
+    }
+
+    return true;
+}
+
+// Finds a single, fairly unrefined trigger for the repeat by walking backwards
+// and collecting the unioned reach at each step.
+static
+vector<CharReach> getUnionedTrigger(const NGHolder &g, const NFAVertex v) {
+    const size_t MAX_TRIGGER_STEPS = 32;
+
+    vector<CharReach> trigger;
+
+    flat_set<NFAVertex> curr, next;
+    insert(&curr, inv_adjacent_vertices(v, g));
+
+    if (contains(curr, g.start)) {
+        DEBUG_PRINTF("start in repeat's immediate preds\n");
+        trigger.push_back(CharReach::dot()); // Trigger could be anything!
+        return trigger;
+    }
+
+    for (size_t num_steps = 0; num_steps < MAX_TRIGGER_STEPS; num_steps++) {
+        next.clear();
+        trigger.push_back(CharReach());
+        CharReach &cr = trigger.back();
+
+        for (auto v_c : curr) {
+            cr |= g[v_c].char_reach;
+            insert(&next, inv_adjacent_vertices(v_c, g));
+        }
+
+        DEBUG_PRINTF("cr[%zu]=%s\n", num_steps, describeClass(cr).c_str());
+
+        if (next.empty() || contains(next, g.start)) {
+            break;
+        }
+
+        curr.swap(next);
+    }
+
+    reverse(trigger.begin(), trigger.end());
+    return trigger;
+}
+
+static
+vector<vector<CharReach>> getRepeatTriggers(const NGHolder &g,
+                                            const NFAVertex sink) {
+    const size_t MAX_TRIGGER_STEPS = 32;
+    const size_t UNIONED_FALLBACK_THRESHOLD = 100;
+
+    using Path = deque<NFAVertex>;
+
+    vector<vector<CharReach>> triggers;
+
+    deque<Path> q; // work queue
+    deque<Path> done; // finished paths
+
+    size_t max_len = MAX_TRIGGER_STEPS;
+
+    // Find a set of paths leading to vertex v by depth first search.
+
+    for (auto u : inv_adjacent_vertices_range(sink, g)) {
+        if (is_any_start(u, g)) {
+            triggers.push_back({}); // empty
+            return triggers;
+        }
+        q.push_back(Path(1, u));
+    }
+
+    while (!q.empty()) {
+        Path &path = q.front();
+        NFAVertex v = path.back();
+
+        if (path.size() >= max_len) {
+            max_len = min(max_len, path.size());
+            done.push_back(path);
+            goto next_path;
+        }
+
+        for (auto u : inv_adjacent_vertices_range(v, g)) {
+            if (is_any_start(u, g)) {
+                // Found an accept. There's no point expanding this path any
+                // further, we're done.
+                max_len = min(max_len, path.size());
+                done.push_back(path);
+                goto next_path;
+            }
+
+            if (path.size() + 1 >= max_len) {
+                done.push_back(path);
+                done.back().push_back(u);
+            } else {
+                q.push_back(path); // copy
+                q.back().push_back(u);
+            }
+        }
+
+    next_path:
+        q.pop_front();
+
+        // If our queue or our finished trigger list gets too large, fall back
+        // to generating a single trigger with union reach.
+        if (q.size() + done.size() > UNIONED_FALLBACK_THRESHOLD) {
+            DEBUG_PRINTF("search too large, fall back to union trigger\n");
+            triggers.clear();
+            triggers.push_back(getUnionedTrigger(g, sink));
+            return triggers;
+        }
+    }
+
+    assert(!done.empty());
+
+    // Convert our path list into a set of unique triggers.
+    ue2_unordered_set<vector<CharReach>> unique_triggers;
+    for (const auto &path : done) {
+        vector<CharReach> reach_path;
+        for (auto jt = path.rbegin(), jte = path.rend(); jt != jte; ++jt) {
+            reach_path.push_back(g[*jt].char_reach);
+        }
+        unique_triggers.insert(reach_path);
+    }
+
+    insert(&triggers, triggers.end(), unique_triggers);
+    sort(triggers.begin(), triggers.end());
+    DEBUG_PRINTF("built %zu unique triggers, max_len=%zu\n", triggers.size(),
+                 max_len);
+    return triggers;
+}
+
+static
+void findMinPeriod(const NGHolder &g,
+                   const map<u32, vector<vector<CharReach>>> &triggers,
+                   ReachSubgraph &rsi) {
+    const auto v = rsi.vertices.front();
+    const CharReach &cr = g[v].char_reach;
+
+    vector<vector<CharReach>> repeat_triggers;
+
+    if (is_triggered(g)) {
+        // Construct a temporary copy of the graph that also contains its
+        // triggers, potentially lengthening the repeat's triggers.
+        NGHolder tg;
+        unordered_map<NFAVertex, NFAVertex> tg_map;
+        cloneHolder(tg, g, &tg_map);
+        addTriggers(tg, triggers);
+        assert(contains(tg_map, v));
+        repeat_triggers = getRepeatTriggers(tg, tg_map.at(v));
+    } else {
+        // Not triggered, no need to mutate the graph.
+        repeat_triggers = getRepeatTriggers(g, v);
+    }
+
+    rsi.minPeriod = minPeriod(repeat_triggers, cr, &rsi.is_reset);
+    DEBUG_PRINTF("%zu triggers, minPeriod=%u, is_reset=%d\n",
+                 repeat_triggers.size(), rsi.minPeriod, (int)rsi.is_reset);
+}
+
+static
+void
+selectHistoryScheme(const NGHolder &g, const ReportManager *rm,
+                    ReachSubgraph &rsi,
+                    const unordered_map<NFAVertex, NFAVertexDepth> &depths,
+                    const unordered_set<NFAVertex> &reached_by_fixed_tops,
+                    const map<u32, vector<vector<CharReach>>> &triggers,
+                    const vector<BoundedRepeatData> &all_repeats,
+                    const bool simple_model_selection) {
+    // {N,} cases use the FIRST history mechanism.
+    if (rsi.repeatMax.is_infinite()) {
+        DEBUG_PRINTF("selected FIRST history\n");
+        rsi.historyType = REPEAT_FIRST;
+        return;
+    }
+
+    /* If we have a repeat which only raises a highlander, only the first match
+     * matters */
+    if (rm && leadsOnlyToAccept(g, rsi)
+        && allSimpleHighlander(*rm, g[rsi.vertices.back()].reports)) {
+        DEBUG_PRINTF("selected FIRST history (as highlander)\n");
+        rsi.historyType = REPEAT_FIRST;
+        rsi.repeatMax = depth::infinity(); /* for consistency */
+        return;
+    }
+
+    // {N,M} cases can use the FIRST mechanism if they follow a cyclic which
+    // includes their reachability via a "straw" path. (see UE-1589)
+    if (hasCyclicSupersetEntryPath(g, rsi, all_repeats)) {
+        DEBUG_PRINTF("selected FIRST history due to cyclic pred with "
+                     "superset of reach\n");
+        rsi.historyType = REPEAT_FIRST;
+        rsi.repeatMax = depth::infinity(); /* will continue to pump out matches */
+        return;
+    }
+
+    // Similarly, {N,M} cases can use the FIRST mechanism if they precede a
+    // cyclic which includes their reachability via a "straw" path.
+    if (hasCyclicSupersetExitPath(g, rsi, all_repeats)) {
+        DEBUG_PRINTF("selected FIRST history due to cyclic succ with "
+                     "superset of reach\n");
+        rsi.historyType = REPEAT_FIRST;
+        rsi.repeatMax = depth::infinity(); /* will continue to pump out matches */
+        return;
+    }
+
+    // Could have skip edges and therefore be a {0,N} repeat.
+    if (rsi.repeatMin == depth(1) && hasSkipEdges(g, rsi)) {
+        DEBUG_PRINTF("selected LAST history\n");
+        rsi.historyType = REPEAT_LAST;
+        return;
+    }
+
+    // Fill minPeriod, is_reset flags
+    findMinPeriod(g, triggers, rsi);
+
+    // If we can't re-enter this cyclic state, we have a reset case.
+    // This check can be very expensive, so we don't do it if we've been asked
+    // for simple model selection.
+    if (!simple_model_selection && !rsi.is_reset &&
+        hasSoleEntry(g, rsi, depths, reached_by_fixed_tops, triggers)) {
+        DEBUG_PRINTF("repeat is sole entry -> reset\n");
+        rsi.is_reset = true;
+    }
+
+    // We can lean on the common selection code for the remainder of our repeat
+    // models.
+    rsi.historyType = chooseRepeatType(rsi.repeatMin, rsi.repeatMax,
+                                       rsi.minPeriod, rsi.is_reset);
+}
+
+static
+void buildFeeder(NGHolder &g, const BoundedRepeatData &rd,
+                 unordered_set<NFAVertex> &created,
+                 const vector<NFAVertex> &straw) {
+    if (!g[rd.cyclic].char_reach.all()) {
+        // Create another cyclic feeder state with flipped reach.  It has an
+        // edge from the repeat's cyclic state and pos_trigger, an edge to the
+        // straw, and edges from every vertex along the straw.
+        NFAVertex feeder = clone_vertex(g, rd.cyclic);
+        created.insert(feeder);
+        g[feeder].char_reach.flip();
+        add_edge(feeder, feeder, g);
+        add_edge(rd.pos_trigger, feeder, g);
+        add_edge(rd.cyclic, feeder, g);
+        add_edge(feeder, straw.front(), g);
+
+        // An edge from every vertex in the straw.
+        for (auto v : straw) {
+            add_edge(v, feeder, g);
+        }
+
+        // An edge to the feeder from the first vertex in the straw and all of
+        // its predecessors (other than the feeder itself, we've already
+        // created that edge!)
+        for (auto u : inv_adjacent_vertices_range(straw.front(), g)) {
+            if (u == feeder) {
+                continue;
+            }
+            add_edge(u, feeder, g);
+        }
+
+        DEBUG_PRINTF("added feeder %zu\n", g[feeder].index);
+    } else {
+        // No neg trigger means feeder is empty, and unnecessary.
+        assert(g[rd.pos_trigger].char_reach.all());
+    }
+}
+
+/**
+ * If we have a leading first repeat, we can split startDs so that it is not
+ * cyclic so that the repeat is only triggered once, rather than every byte. If we
+ * perform this transform we must create another cyclic state to retrigger the
+ * repeat after we see an escape for the repeat.
+ *
+ * We do not use the anchored start state to allow us to restart the NFA at a deep
+ * offset.
+ */
+static
+bool improveLeadingRepeat(NGHolder &g, BoundedRepeatData &rd,
+                          unordered_set<NFAVertex> &created,
+                          const vector<BoundedRepeatData> &all_repeats) {
+    assert(edge(g.startDs, g.startDs, g).second);
+
+    // UE-1617: can rewire FIRST history cases that are preceded by
+    // startDs.
+    if (rd.type != REPEAT_FIRST) {
+        return false;
+    }
+
+    const CharReach &cyc_cr = g[rd.cyclic].char_reach;
+
+    // This transformation is only worth doing if this would allow us to
+    // accelerate the cyclic state (UE-2055).
+    if ((~cyc_cr).count() > ACCEL_MAX_STOP_CHAR) {
+        DEBUG_PRINTF("we wouldn't be able to accel this case\n");
+        return false;
+    }
+
+    vector<NFAVertex> straw;
+    NFAVertex pred =
+        walkStrawToCyclicRev(g, rd.pos_trigger, all_repeats, straw);
+    if (pred != g.startDs) {
+        DEBUG_PRINTF("straw walk doesn't lead to startDs\n");
+        return false;
+    }
+
+    // This transformation is only safe if the straw path from startDs that
+    // we've discovered can *only* lead to this repeat, since we're going to
+    // remove the self-loop on startDs.
+    if (proper_out_degree(g.startDs, g) > 1) {
+        DEBUG_PRINTF("startDs has other successors\n");
+        return false;
+    }
+    for (const auto &v : straw) {
+        if (proper_out_degree(v, g) != 1) {
+            DEBUG_PRINTF("branch between startDs and repeat, from vertex %zu\n",
+                         g[v].index);
+            return false;
+        }
+    }
+
+    if (g[rd.pos_trigger].char_reach.count() < ACCEL_MAX_STOP_CHAR) {
+        DEBUG_PRINTF("entry is narrow, could be accelerable\n");
+        return false;
+    }
+
+    assert(!straw.empty());
+
+    /* If there is overlap between the feeder and the first vertex in the straw
+     * fun things happen. TODO: handle fun things happening (requires more
+     * edges and more vertices). */
+    if (!g[straw.front()].char_reach.isSubsetOf(cyc_cr)) {
+        DEBUG_PRINTF("straw has `interesting' reach\n");
+        return false;
+    }
+
+    DEBUG_PRINTF("repeat can be improved by removing startDs loop!\n");
+
+    // Remove the self-loop on startDs! What a blast!
+    remove_edge(g.startDs, g.startDs, g);
+
+    // Wire up feeder state to straw.
+    buildFeeder(g, rd, created, straw);
+
+    return true;
+}
+
+static
+vector<NFAVertex> makeOwnStraw(NGHolder &g, BoundedRepeatData &rd,
+                               const vector<NFAVertex> &straw) {
+    // Straw runs from startDs to our pos trigger.
+    assert(!straw.empty());
+    assert(edge(g.startDs, straw.front(), g).second);
+    assert(edge(straw.back(), rd.pos_trigger, g).second);
+
+    vector<NFAVertex> own_straw;
+    for (const auto &v : straw) {
+        NFAVertex v2 = clone_vertex(g, v);
+        if (hasSelfLoop(v, g)) {
+            add_edge(v2, v2, g);
+        }
+        if (!own_straw.empty()) {
+            add_edge(own_straw.back(), v2, g);
+        }
+        own_straw.push_back(v2);
+    }
+
+    // Wire our straw to start, not startDs.
+    add_edge(g.start, own_straw.front(), g);
+
+    // Swap over to using our own straw to get to the POS trigger.
+    remove_edge(straw.back(), rd.pos_trigger, g);
+    add_edge(own_straw.back(), rd.pos_trigger, g);
+
+    return own_straw;
+}
+
+/**
+ * Specialized version of improveLeadingRepeat for outfixes, in which we can
+ * rewire the straw to start instead of removing the startDs self-loop.
+ */
+static
+bool improveLeadingRepeatOutfix(NGHolder &g, BoundedRepeatData &rd,
+                                unordered_set<NFAVertex> &created,
+                                const vector<BoundedRepeatData> &all_repeats) {
+    assert(g.kind == NFA_OUTFIX);
+
+    // UE-1617: can rewire FIRST history cases that are preceded by
+    // startDs.
+    if (rd.type != REPEAT_FIRST) {
+        return false;
+    }
+
+    const CharReach &cyc_cr = g[rd.cyclic].char_reach;
+
+    // This transformation is only worth doing if this would allow us to
+    // accelerate the cyclic state (UE-2055).
+    if ((~cyc_cr).count() > ACCEL_MAX_STOP_CHAR) {
+        DEBUG_PRINTF("we wouldn't be able to accel this case\n");
+        return false;
+    }
+
+    vector<NFAVertex> straw;
+    NFAVertex pred =
+        walkStrawToCyclicRev(g, rd.pos_trigger, all_repeats, straw);
+    if (pred != g.startDs) {
+        DEBUG_PRINTF("straw walk doesn't lead to startDs\n");
+        return false;
+    }
+
+    if (g[rd.pos_trigger].char_reach.count() < ACCEL_MAX_STOP_CHAR) {
+        DEBUG_PRINTF("entry is narrow, could be accelerable\n");
+        return false;
+    }
+
+    assert(!straw.empty());
+
+    /* If there is overlap between the feeder and the first vertex in the straw
+     * fun things happen. TODO: handle fun things happening (requires more
+     * edges and more vertices). */
+    if (!g[straw.front()].char_reach.isSubsetOf(cyc_cr)) {
+        DEBUG_PRINTF("straw has `interesting' reach\n");
+        return false;
+    }
+
+    DEBUG_PRINTF("repeat can be improved by rebuilding its entry\n");
+
+    const auto own_straw = makeOwnStraw(g, rd, straw);
+    insert(&created, own_straw);
+
+    // Wire up feeder state to our new straw.
+    buildFeeder(g, rd, created, own_straw);
+
+    // We may no longer need the original straw.
+    pruneUseless(g);
+
+    return true;
+}
+
+/** Returns true if doing the bounded repeat transformation on this case
+ * results in a smaller NFA model. */
+static
+bool givesBetterModel(const NGHolder &g, const vector<ReachSubgraph> &rs) {
+    static const u32 MAX_FAST_STATES = 128; // bigger NFAs are fat and slow.
+
+    // We use vertex count as an upper bound for the number of states.
+    u32 curr_states = num_vertices(g) - 2; // accepts don't have states
+
+    if (curr_states <= MAX_FAST_STATES) {
+        return false;
+    }
+    if (curr_states > NFA_MAX_STATES) {
+        return true;
+    }
+
+    u32 expected_states = curr_states;
+    for (const auto &rsi : rs) {
+        /* may be off as unpeeling not done yet */
+        expected_states += 2; /* cyclic and pos */
+        expected_states -= rsi.vertices.size();
+    }
+
+    return ROUNDUP_N(curr_states, 128) != ROUNDUP_N(expected_states, 128);
+}
+
+/** True if this repeat terminates with a vertex that leads only to accept. */
+static
+bool endsInAccept(const NGHolder &g, const ReachSubgraph &rsi) {
+    NFAVertex last = rsi.vertices.back();
+    return getSoleDestVertex(g, last) == g.accept;
+}
+
+static
+bool endsInAcceptEod(const NGHolder &g, const ReachSubgraph &rsi) {
+    NFAVertex last = rsi.vertices.back();
+    return getSoleDestVertex(g, last) == g.acceptEod;
+}
+
+namespace {
+class pfti_visitor : public boost::default_dfs_visitor {
+public:
+    pfti_visitor(unordered_map<NFAVertex, depth> &top_depths_in,
+                 const depth &our_depth_in)
+        : top_depths(top_depths_in), our_depth(our_depth_in) {}
+
+    void discover_vertex(NFAVertex v, UNUSED const NGHolder &g) {
+        DEBUG_PRINTF("discovered %zu (depth %s)\n", g[v].index,
+                     our_depth.str().c_str());
+
+        auto it = top_depths.find(v);
+        if (it != top_depths.end() && it->second != our_depth) {
+            // already seen at a different depth, remove from consideration.
+            it->second = depth::infinity();
+        } else {
+            top_depths[v] = our_depth;
+        }
+    }
+    unordered_map<NFAVertex, depth> &top_depths;
+    const depth &our_depth;
+};
+} // namespace
+
+static
+void populateFixedTopInfo(const map<u32, u32> &fixed_depth_tops,
+                          const NGHolder &g,
+                          unordered_set<NFAVertex> *reached_by_fixed_tops) {
+    if (fixed_depth_tops.empty()) {
+        return; /* we will never find anything */
+    }
+
+    assert(!proper_out_degree(g.startDs, g));
+    unordered_map<NFAVertex, depth> top_depths;
+    auto colours = make_small_color_map(g);
+
+    for (const auto &e : out_edges_range(g.start, g)) {
+        NFAVertex v = target(e, g);
+        if (v == g.startDs) {
+            continue;
+        }
+
+        depth td = depth::infinity();
+        for (u32 top : g[e].tops) {
+            if (!contains(fixed_depth_tops, top)) {
+                td = depth::infinity();
+                break;
+            }
+            depth td_t(fixed_depth_tops.at(top));
+            if (td == td_t) {
+                continue;
+            } else if (td == depth::infinity()) {
+                td = td_t;
+            } else {
+                td = depth::infinity();
+                break;
+            }
+        }
+
+        DEBUG_PRINTF("scanning from %zu depth=%s\n", g[v].index,
+                     td.str().c_str());
+        /* for each vertex reachable from v update its map to reflect that it is
+         * reachable from a top of depth td. */
+
+        depth_first_visit(g, v, pfti_visitor(top_depths, td), colours);
+    }
+
+    for (const auto &v_depth : top_depths) {
+        const NFAVertex v = v_depth.first;
+        const depth &d = v_depth.second;
+        if (d.is_finite()) {
+            DEBUG_PRINTF("%zu reached by fixed tops at depth %s\n",
+                         g[v].index, d.str().c_str());
+            reached_by_fixed_tops->insert(v);
+        }
+    }
+}
+
+#ifndef NDEBUG
+/** Assertion use only. Returns true if the given bounded repeats share any
+ * vertices, which we don't allow. */
+static
+bool hasOverlappingRepeats(UNUSED const NGHolder &g,
+                           const vector<BoundedRepeatData> &repeats) {
+    unordered_set<NFAVertex> involved;
+
+    for (const auto &br : repeats) {
+        if (contains(involved, br.cyclic)) {
+            DEBUG_PRINTF("already seen cyclic %zu\n", g[br.cyclic].index);
+            return true;
+        }
+        if (contains(involved, br.pos_trigger)) {
+            DEBUG_PRINTF("already seen pos %zu\n", g[br.pos_trigger].index);
+            return true;
+        }
+        for (auto v : br.tug_triggers) {
+            if (contains(involved, v)) {
+                DEBUG_PRINTF("already seen tug %zu\n", g[v].index);
+                return true;
+            }
+        }
+
+        involved.insert(br.cyclic);
+        involved.insert(br.pos_trigger);
+        involved.insert(br.tug_triggers.begin(), br.tug_triggers.end());
+    }
+
+    return false;
+}
+
+#endif // NDEBUG
+
+/**
+ * Identifies so-called "nasty" repeats, in which the reachability of both the
+ * repeat itself and its tugs are wide, which means that executing the NFA will
+ * likely be bogged down in exception processing.
+ */
+static
+bool repeatIsNasty(const NGHolder &g, const ReachSubgraph &rsi,
+                   const unordered_map<NFAVertex, NFAVertexDepth> &depths) {
+    if (num_vertices(g) > NFA_MAX_STATES) {
+        // We may have no choice but to implement this repeat to get the graph
+        // down to a tractable number of vertices.
+        return false;
+    }
+
+    if (!generates_callbacks(g) && endsInAccept(g, rsi)) {
+        DEBUG_PRINTF("would generate a lazy tug, repeat is OK\n");
+        return false;
+    }
+
+    const NFAVertex first = rsi.vertices.front();
+    DEBUG_PRINTF("min depth from startds = %s\n",
+                 depths.at(first).fromStartDotStar.min.str().c_str());
+    if (depths.at(first).fromStartDotStar.min > depth(2)) {
+        return false;
+    }
+
+    NFAVertex last = rsi.vertices.back();
+    const CharReach &cyclicreach = g[last].char_reach;
+    CharReach tugreach;
+    for (auto v : adjacent_vertices_range(last, g)) {
+        if (v == last || is_special(v, g)) {
+            continue;
+        }
+        tugreach |= g[v].char_reach;
+    }
+    // Deal with unpeeled cases.
+    if (tugreach.none()) {
+        tugreach = cyclicreach;
+    }
+    DEBUG_PRINTF("tugreach.count=%zu, cyclicreach.count=%zu\n",
+                 tugreach.count(), cyclicreach.count());
+    return (tugreach.count() > 200) && (cyclicreach.count() > 200);
+}
+
+void analyseRepeats(NGHolder &g, const ReportManager *rm,
+                    const map<u32, u32> &fixed_depth_tops,
+                    const map<u32, vector<vector<CharReach>>> &triggers,
+                    vector<BoundedRepeatData> *repeats, bool streaming,
+                    bool simple_model_selection, const Grey &grey,
+                    bool *reformed_start_ds) {
+    if (!grey.allowExtendedNFA || !grey.allowLimExNFA) {
+        return;
+    }
+
+    // Quick sanity test.
+    assert(allMatchStatesHaveReports(g));
+
+#ifndef NDEBUG
+    // So we can assert that the number of tops hasn't changed at the end of
+    // this analysis.
+    const flat_set<u32> allTops = getTops(g);
+#endif
+
+    // Later on, we're (a little bit) dependent on depth information for
+    // unpeeling and so forth. Note that these depths MUST be maintained when
+    // new vertices are added.
+    unordered_map<NFAVertex, NFAVertexDepth> depths;
+    findInitDepths(g, depths);
+
+    // Construct our list of subgraphs with the same reach using BGL magic.
+    vector<ReachSubgraph> rs;
+    buildReachSubgraphs(g, rs, grey.minExtBoundedRepeatSize);
+
+    // Validate and split subgraphs.
+    checkReachSubgraphs(g, rs, grey.minExtBoundedRepeatSize);
+
+    // Identify which subgraphs represent bounded repeats in forms ("cliches")
+    // that we accept, and mark the others as bad.
+    for (auto &rsi: rs) {
+        if (!processSubgraph(g, rsi, grey.minExtBoundedRepeatSize)) {
+            rsi.bad = true;
+            continue;
+        }
+
+        DEBUG_PRINTF("rsi min %s=max=%s\n", rsi.repeatMin.str().c_str(),
+                     rsi.repeatMax.str().c_str());
+
+        // Identify repeats with wide cyclic and tug reach which will produce
+        // low-performance implementations and avoid doing them.
+        if (repeatIsNasty(g, rsi, depths)) {
+            DEBUG_PRINTF("marking nasty repeat as bad\n");
+            rsi.bad = true;
+        }
+    }
+
+    // Remove bad cases, then sort remaining subgraphs in descending size
+    // order.
+    rs.erase(remove_if(rs.begin(), rs.end(),
+                       [](const ReachSubgraph &r) { return r.bad; }),
+                       rs.end());
+    stable_sort(rs.begin(), rs.end(),
+                [](const ReachSubgraph &a, const ReachSubgraph &b) {
+                    return a.vertices.size() > b.vertices.size();
+                });
+
+    if (!streaming && !givesBetterModel(g, rs)) {
+        /* in block mode, there is no state space so we are only looking for
+         * performance wins */
+        DEBUG_PRINTF("repeat would not reduce NFA model size, skipping\n");
+        return;
+    }
+
+    if (rs.empty()) {
+        /* no good repeats */
+        return;
+    }
+
+    // Store a copy of the original, unmodified graph in case we need to revert
+    // back: in particular, due to tug cloning it is possible to build a graph
+    // that was bigger than the original. See UE-2370.  FIXME: smarter analysis
+    // could make this unnecessary?
+    const unique_ptr<const NGHolder> orig_g(cloneHolder(g));
+
+    unordered_set<NFAVertex> reached_by_fixed_tops;
+    if (is_triggered(g)) {
+        populateFixedTopInfo(fixed_depth_tops, g, &reached_by_fixed_tops);
+    }
+
+    // Go to town on the remaining acceptable subgraphs.
+    unordered_set<NFAVertex> created;
+    for (auto &rsi : rs) {
+        DEBUG_PRINTF("subgraph (beginning vertex %zu) is a {%s,%s} repeat\n",
+                     g[rsi.vertices.front()].index,
+                     rsi.repeatMin.str().c_str(), rsi.repeatMax.str().c_str());
+
+        if (!peelSubgraph(g, grey, rsi, created)) {
+            DEBUG_PRINTF("peel failed, skipping\n");
+            continue;
+        }
+
+        // Attempt to peel a vertex if we're up against startDs, for
+        // performance reasons.
+        peelStartDotStar(g, depths, grey, rsi);
+
+        // Our peeling passes may have killed off this repeat.
+        if (rsi.bad) {
+            continue;
+        }
+
+        selectHistoryScheme(g, rm, rsi, depths, reached_by_fixed_tops, triggers,
+                            *repeats, simple_model_selection);
+
+        if (!generates_callbacks(g) && endsInAccept(g, rsi)) {
+            DEBUG_PRINTF("accepty-rosy graph\n");
+            replaceSubgraphWithLazySpecial(g, rsi, repeats, depths, created);
+        } else if (endsInAcceptEod(g, rsi)) {
+            DEBUG_PRINTF("accepty-rosy graph\n");
+            replaceSubgraphWithLazySpecial(g, rsi, repeats, depths, created);
+        } else {
+            replaceSubgraphWithSpecial(g, rsi, repeats, depths, created);
+        }
+
+        // Some of our analyses require correctly numbered vertices, so we
+        // renumber after changes.
+        renumber_vertices(g);
+    }
+
+    bool modified_start_ds = false;
+
+    // We may be able to make improvements to the graph for performance
+    // reasons. Note that this may do 'orrible things like remove the startDs
+    // cycle, this should only happen quite late in the graph lifecycle.
+    if (repeats->size() == 1) {
+        if (g.kind == NFA_OUTFIX) {
+            improveLeadingRepeatOutfix(g, repeats->back(), created, *repeats);
+            // (Does not modify startDs, so we don't need to set
+            // reformed_start_ds for this case.)
+        } else {
+            modified_start_ds =
+                improveLeadingRepeat(g, repeats->back(), created, *repeats);
+        }
+    }
+
+    if (reformed_start_ds) {
+        *reformed_start_ds = modified_start_ds;
+    }
+
+    if (!repeats->empty()) {
+        if (num_vertices(g) > NFA_MAX_STATES) {
+            // We've managed to build an unimplementable NFA. Swap back to the
+            // original.
+            DEBUG_PRINTF("NFA has %zu vertices; swapping back to the "
+                         "original graph\n", num_vertices(g));
+            clear_graph(g);
+            assert(orig_g);
+            cloneHolder(g, *orig_g);
+            repeats->clear();
+        }
+
+        // Sanity test: we don't want any repeats that share special vertices
+        // as our construction code later can't cope with it.
+        assert(!hasOverlappingRepeats(g, *repeats));
+
+        // We have modified the graph, so we need to ensure that our edges
+        // and vertices are correctly numbered.
+        renumber_vertices(g);
+        renumber_edges(g);
+        // Remove stray report IDs.
+        clearReports(g);
+    }
+
+    // Quick sanity tests.
+    assert(allMatchStatesHaveReports(g));
+    assert(!is_triggered(g) || getTops(g) == allTops);
+}
+
+/**
+ * \brief True if the non-special vertices in the given graph all have the same
+ * character reachability.
+ */
+static
+bool allOneReach(const NGHolder &g) {
+    const CharReach *cr = nullptr;
+    for (const auto &v : vertices_range(g)) {
+        if (is_special(v, g)) {
+            continue;
+        }
+        if (!cr) {
+            cr = &g[v].char_reach;
+        } else {
+            if (*cr != g[v].char_reach) {
+                return false;
+            }
+        }
+    }
+    return true;
+}
+
+bool isPureRepeat(const NGHolder &g, PureRepeat &repeat) {
+    assert(allMatchStatesHaveReports(g));
+
+    DEBUG_PRINTF("entry\n");
+
+    // Must be start anchored.
+    assert(edge(g.startDs, g.startDs, g).second);
+    if (out_degree(g.startDs, g) > 1) {
+        DEBUG_PRINTF("Unanchored\n");
+        return false;
+    }
+
+    // Must not be EOD-anchored.
+    assert(edge(g.accept, g.acceptEod, g).second);
+    if (in_degree(g.acceptEod, g) > 1) {
+        DEBUG_PRINTF("EOD anchored\n");
+        return false;
+    }
+
+    // Must have precisely one top.
+    if (is_triggered(g) && !onlyOneTop(g)) {
+        DEBUG_PRINTF("Too many tops\n");
+        return false;
+    }
+
+    if (!allOneReach(g)) {
+        DEBUG_PRINTF("vertices with different reach\n");
+        return false;
+    }
+
+    // We allow this code to report true for any repeat, even for '.*' or '.+'
+    // cases.
+    const u32 minNumVertices = 1;
+
+    vector<ReachSubgraph> rs;
+    buildReachSubgraphs(g, rs, minNumVertices);
+    checkReachSubgraphs(g, rs, minNumVertices);
+    if (rs.size() != 1) {
+        DEBUG_PRINTF("too many subgraphs\n");
+        return false;
+    }
+
+    ReachSubgraph &rsi = *rs.begin();
+    if (!processSubgraph(g, rsi, minNumVertices)) {
+        DEBUG_PRINTF("not a supported repeat\n");
+        return false;
+    }
+
+    if (rsi.vertices.size() + N_SPECIALS != num_vertices(g)) {
+        DEBUG_PRINTF("repeat doesn't span graph\n");
+        return false;
+    }
+
+    assert(!rsi.bad);
+    assert(rsi.vertices.size() >= minNumVertices);
+
+    const NFAVertex v = rsi.vertices.back();
+
+    repeat.reach = g[v].char_reach;
+    repeat.bounds.min = rsi.repeatMin;
+    repeat.bounds.max = rsi.repeatMax;
+    insert(&repeat.reports, g[v].reports);
+
+    if (isVacuous(g)) {
+        // This graph might be a {0,N} or {0,} repeat. For this to be true, we
+        // must have found a {1,N} or {1,} repeat and the start vertex must
+        // have the same report set as the vertices in the repeat.
+        if (repeat.bounds.min == depth(1) &&
+            g[g.start].reports == g[v].reports) {
+            repeat.bounds.min = depth(0);
+            DEBUG_PRINTF("graph is %s repeat\n", repeat.bounds.str().c_str());
+        } else {
+            DEBUG_PRINTF("not a supported repeat\n");
+            return false;
+        }
+    }
+
+    assert(all_reports(g) == set<ReportID>(begin(g[v].reports),
+                                           end(g[v].reports)));
+    return true;
+}
+
+void findRepeats(const NGHolder &h, u32 minRepeatVertices,
+                 vector<GraphRepeatInfo> *repeats_out) {
+    // Construct our list of subgraphs with the same reach using BGL magic.
+    vector<ReachSubgraph> rs;
+    buildReachSubgraphs(h, rs, minRepeatVertices);
+    checkReachSubgraphs(h, rs, minRepeatVertices);
+
+    for (auto &rsi : rs) {
+        if (!processSubgraph(h, rsi, minRepeatVertices)) {
+            continue;
+        }
+
+        DEBUG_PRINTF("rsi min=%s max=%s\n", rsi.repeatMin.str().c_str(),
+                     rsi.repeatMax.str().c_str());
+
+        depth repeatMax = rsi.repeatMax;
+
+        vector<BoundedRepeatData> all_repeats; /* we don't mutate the graph in
+                                                * this path */
+        if (hasCyclicSupersetEntryPath(h, rsi, all_repeats)) {
+            DEBUG_PRINTF("selected FIRST history due to cyclic pred with "
+                         "superset of reach\n");
+            repeatMax = depth::infinity(); /* will continue to pump out matches */
+        }
+        if (hasCyclicSupersetExitPath(h, rsi, all_repeats)) {
+            DEBUG_PRINTF("selected FIRST history due to cyclic succ with "
+                         "superset of reach\n");
+            repeatMax = depth::infinity(); /* will continue to pump out matches */
+        }
+
+        repeats_out->push_back(GraphRepeatInfo());
+        GraphRepeatInfo &ri = repeats_out->back();
+        ri.vertices.swap(rsi.vertices);
+        ri.repeatMin = rsi.repeatMin;
+        ri.repeatMax = repeatMax;
+    }
+}
+
+} // namespace ue2