intermediate changes

ref:cde9a383711a11544ce7e107a78147fb96cc4029

1 files changed, 1035 insertions, 0 deletions

diff --git a/contrib/libs/hyperscan/src/nfagraph/ng_extparam.cpp b/contrib/libs/hyperscan/src/nfagraph/ng_extparam.cpp
new file mode 100644
index 0000000000..6eb23113f3
--- /dev/null
+++ b/contrib/libs/hyperscan/src/nfagraph/ng_extparam.cpp
@@ -0,0 +1,1035 @@
+/*
+ * 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 Propagate extended parameters to vertex reports and reduce graph if
+ * possible.
+ *
+ * This code handles the propagation of the extension parameters specified by
+ * the user with the \ref hs_expr_ext structure into the reports on the graph's
+ * vertices.
+ *
+ * There are also some analyses that prune edges that cannot contribute to a
+ * match given these constraints, or transform the graph in order to make a
+ * constraint implicit.
+ */
+
+#include "ng_extparam.h"
+
+#include "ng.h"
+#include "ng_depth.h"
+#include "ng_dump.h"
+#include "ng_prune.h"
+#include "ng_reports.h"
+#include "ng_som_util.h"
+#include "ng_width.h"
+#include "ng_util.h"
+#include "ue2common.h"
+#include "compiler/compiler.h"
+#include "parser/position.h"
+#include "util/compile_context.h"
+#include "util/compile_error.h"
+#include "util/container.h"
+#include "util/graph.h"
+#include "util/graph_range.h"
+
+#include <sstream>
+#include <string>
+
+using namespace std;
+
+namespace ue2 {
+
+static const u32 MAX_MAXOFFSET_TO_ANCHOR = 2000;
+static const u32 MAX_MINLENGTH_TO_CONVERT = 2000;
+
+/** True if all the given reports have the same extparam bounds. */
+template<typename Container>
+bool hasSameBounds(const Container &reports, const ReportManager &rm) {
+    assert(!reports.empty());
+
+    const auto &first = rm.getReport(*reports.begin());
+    for (auto id : reports) {
+        const auto &report = rm.getReport(id);
+        if (report.minOffset != first.minOffset ||
+            report.maxOffset != first.maxOffset ||
+            report.minLength != first.minLength) {
+            return false;
+        }
+    }
+
+    return true;
+}
+
+/**
+ * \brief Find the (min, max) offset adjustment for the reports on a given
+ * vertex.
+ */
+static
+pair<s32,s32> getMinMaxOffsetAdjust(const ReportManager &rm,
+                                    const NGHolder &g, NFAVertex v) {
+    s32 minAdj = 0, maxAdj = 0;
+    const auto &reports = g[v].reports;
+    for (auto ri = reports.begin(), re = reports.end(); ri != re; ++ri) {
+        const Report &ir = rm.getReport(*ri);
+        if (ri == reports.begin()) {
+            minAdj = ir.offsetAdjust;
+            maxAdj = ir.offsetAdjust;
+        } else {
+            minAdj = min(minAdj, ir.offsetAdjust);
+            maxAdj = max(maxAdj, ir.offsetAdjust);
+        }
+    }
+
+    return make_pair(minAdj, maxAdj);
+}
+
+/** \brief Find the (min, max) length of any match for the given holder. */
+static
+DepthMinMax findMatchLengths(const ReportManager &rm, const NGHolder &g) {
+    DepthMinMax match_depths;
+
+    vector<DepthMinMax> depths = getDistancesFromSOM(g);
+
+    pair<s32, s32> adj;
+
+    for (auto v : inv_adjacent_vertices_range(g.accept, g)) {
+        u32 idx = g[v].index;
+        DepthMinMax d = depths[idx]; // copy
+        adj = getMinMaxOffsetAdjust(rm, g, v);
+        DEBUG_PRINTF("vertex %u: depths=%s, adj=[%d,%d]\n", idx,
+                     d.str().c_str(), adj.first, adj.second);
+        d.min += adj.first;
+        d.max += adj.second;
+        match_depths = unionDepthMinMax(match_depths, d);
+    }
+
+    for (auto v : inv_adjacent_vertices_range(g.acceptEod, g)) {
+        if (v == g.accept) {
+            continue;
+        }
+        u32 idx = g[v].index;
+        DepthMinMax d = depths[idx]; // copy
+        adj = getMinMaxOffsetAdjust(rm, g, v);
+        DEBUG_PRINTF("vertex %u: depths=%s, adj=[%d,%d]\n", idx,
+                     d.str().c_str(), adj.first, adj.second);
+        d.min += adj.first;
+        d.max += adj.second;
+        match_depths = unionDepthMinMax(match_depths, d);
+    }
+
+    DEBUG_PRINTF("match_depths=%s\n", match_depths.str().c_str());
+
+    assert(match_depths.min.is_reachable());
+    assert(match_depths.max.is_reachable());
+    return match_depths;
+}
+
+template<typename Function>
+void replaceReports(NGHolder &g, NFAVertex accept, flat_set<NFAVertex> &seen,
+                    Function func) {
+    for (auto v : inv_adjacent_vertices_range(accept, g)) {
+        if (v == g.accept) {
+            // Don't operate on accept: the accept->acceptEod edge is stylised.
+            assert(accept == g.acceptEod);
+            assert(g[v].reports.empty());
+            continue;
+        }
+
+        if (!seen.insert(v).second) {
+            continue; // We have already processed v.
+        }
+
+        auto &reports = g[v].reports;
+        if (reports.empty()) {
+            continue;
+        }
+        decltype(g[v].reports) new_reports;
+        for (auto id : g[v].reports) {
+            new_reports.insert(func(v, id));
+        }
+        reports = std::move(new_reports);
+    }
+}
+
+/**
+ * Generic function for replacing all the reports in the graph.
+ *
+ * Pass this a function that takes a vertex and a ReportID returns another
+ * ReportID (or the same one) to replace it with.
+ */
+template<typename Function>
+void replaceReports(NGHolder &g, Function func) {
+    flat_set<NFAVertex> seen;
+    replaceReports(g, g.accept, seen, func);
+    replaceReports(g, g.acceptEod, seen, func);
+}
+
+/** \brief Replace the graph's reports with new reports that specify bounds. */
+static
+void updateReportBounds(ReportManager &rm, NGHolder &g,
+                        const ExpressionInfo &expr) {
+    DEBUG_PRINTF("updating report bounds\n");
+    replaceReports(g, [&](NFAVertex, ReportID id) {
+        Report report = rm.getReport(id); // make a copy
+        assert(!report.hasBounds());
+
+        // Note that we need to cope with offset adjustment here.
+
+        report.minOffset = expr.min_offset - report.offsetAdjust;
+        if (expr.max_offset == MAX_OFFSET) {
+            report.maxOffset = MAX_OFFSET;
+        } else {
+            report.maxOffset = expr.max_offset - report.offsetAdjust;
+        }
+        assert(report.maxOffset >= report.minOffset);
+
+        report.minLength = expr.min_length;
+        if (expr.min_length && !expr.som) {
+            report.quashSom = true;
+        }
+
+        DEBUG_PRINTF("id %u -> min_offset=%llu, max_offset=%llu, "
+                     "min_length=%llu\n", id, report.minOffset,
+                     report.maxOffset, report.minLength);
+
+        return rm.getInternalId(report);
+    });
+}
+
+static
+bool hasVirtualStarts(const NGHolder &g) {
+    for (auto v : adjacent_vertices_range(g.start, g)) {
+        if (g[v].assert_flags & POS_FLAG_VIRTUAL_START) {
+            return true;
+        }
+    }
+    return false;
+}
+
+/** Set the min_length param for all reports to zero.  */
+static
+void clearMinLengthParam(NGHolder &g, ReportManager &rm) {
+    DEBUG_PRINTF("clearing min length\n");
+    replaceReports(g, [&rm](NFAVertex, ReportID id) {
+        const auto &report = rm.getReport(id);
+        if (report.minLength) {
+            Report new_report = report;
+            new_report.minLength = 0;
+            return rm.getInternalId(new_report);
+        }
+        return id;
+    });
+}
+
+/**
+ * Set the min_offset param to zero and the max_offset param to MAX_OFFSET for
+ * all reports.
+ */
+static
+void clearOffsetParams(NGHolder &g, ReportManager &rm) {
+    DEBUG_PRINTF("clearing min and max offset\n");
+    replaceReports(g, [&rm](NFAVertex, ReportID id) {
+        const auto &report = rm.getReport(id);
+        if (report.minLength) {
+            Report new_report = report;
+            new_report.minOffset = 0;
+            new_report.maxOffset = MAX_OFFSET;
+            return rm.getInternalId(new_report);
+        }
+        return id;
+    });
+}
+
+/**
+ * If the pattern is unanchored, has a max_offset and has not asked for SOM, we
+ * can use that knowledge to anchor it which will limit its lifespan. Note that
+ * we can't use this transformation if there's a min_length, as it's currently
+ * handled using "sly SOM".
+ *
+ * Note that it is possible to handle graphs that have a combination of
+ * anchored and unanchored paths, but it's too tricky for the moment.
+ */
+static
+bool anchorPatternWithBoundedRepeat(NGHolder &g, ReportManager &rm) {
+    if (!isFloating(g)) {
+        return false;
+    }
+
+    const auto &reports = all_reports(g);
+    if (reports.empty()) {
+        return false;
+    }
+
+    if (any_of_in(reports, [&](ReportID id) {
+            const auto &report = rm.getReport(id);
+            return report.maxOffset == MAX_OFFSET || report.minLength ||
+                   report.offsetAdjust;
+        })) {
+        return false;
+    }
+
+    if (!hasSameBounds(reports, rm)) {
+        DEBUG_PRINTF("mixed report bounds\n");
+        return false;
+    }
+
+    const depth minWidth = findMinWidth(g);
+    const depth maxWidth = findMaxWidth(g);
+
+    assert(minWidth <= maxWidth);
+    assert(maxWidth.is_reachable());
+
+    const auto &first_report = rm.getReport(*reports.begin());
+    const auto min_offset = first_report.minOffset;
+    const auto max_offset = first_report.maxOffset;
+    assert(max_offset < MAX_OFFSET);
+
+    DEBUG_PRINTF("widths=[%s,%s], min/max offsets=[%llu,%llu]\n",
+                 minWidth.str().c_str(), maxWidth.str().c_str(),
+                 min_offset, max_offset);
+
+    if (max_offset > MAX_MAXOFFSET_TO_ANCHOR) {
+        return false;
+    }
+
+    if (max_offset < minWidth) {
+        assert(0);
+        return false;
+    }
+
+    // If the pattern has virtual starts, we probably don't want to touch it.
+    if (hasVirtualStarts(g)) {
+        DEBUG_PRINTF("virtual starts, bailing\n");
+        return false;
+    }
+
+    // Similarly, bail if the pattern is vacuous. TODO: this could be done, we
+    // would just need to be a little careful with reports.
+    if (isVacuous(g)) {
+        DEBUG_PRINTF("vacuous, bailing\n");
+        return false;
+    }
+
+    u32 min_bound, max_bound;
+    if (maxWidth.is_infinite()) {
+        min_bound = 0;
+        max_bound = max_offset - minWidth;
+    } else {
+        min_bound = min_offset > maxWidth ? min_offset - maxWidth : 0;
+        max_bound = max_offset - minWidth;
+    }
+
+    DEBUG_PRINTF("prepending ^.{%u,%u}\n", min_bound, max_bound);
+
+    vector<NFAVertex> initials;
+    for (auto v : adjacent_vertices_range(g.startDs, g)) {
+        if (v == g.startDs) {
+            continue;
+        }
+        initials.push_back(v);
+    }
+    if (initials.empty()) {
+        DEBUG_PRINTF("no initial vertices\n");
+        return false;
+    }
+
+    // Wire up 'min_offset' mandatory dots from anchored start.
+    NFAVertex u = g.start;
+    for (u32 i = 0; i < min_bound; i++) {
+        NFAVertex v = add_vertex(g);
+        g[v].char_reach.setall();
+        add_edge(u, v, g);
+        u = v;
+    }
+
+    NFAVertex head = u;
+
+    // Wire up optional dots for (max_offset - min_offset).
+    for (u32 i = 0; i < max_bound - min_bound; i++) {
+        NFAVertex v = add_vertex(g);
+        g[v].char_reach.setall();
+        if (head != u) {
+            add_edge(head, v, g);
+        }
+        add_edge(u, v, g);
+        u = v;
+    }
+
+    // Remove edges from starts and wire both head and u to our initials.
+    for (auto v : initials) {
+        remove_edge(g.startDs, v, g);
+        remove_edge(g.start, v, g);
+
+        if (head != u) {
+            add_edge(head, v, g);
+        }
+        add_edge(u, v, g);
+    }
+
+    renumber_vertices(g);
+    renumber_edges(g);
+
+    if (minWidth == maxWidth) {
+        // For a fixed width pattern, we can retire the offsets as
+        // they are implicit in the graph now.
+        clearOffsetParams(g, rm);
+    }
+
+    clearReports(g);
+    return true;
+}
+
+static
+NFAVertex findSingleCyclic(const NGHolder &g) {
+    NFAVertex v = NGHolder::null_vertex();
+    for (const auto &e : edges_range(g)) {
+        if (source(e, g) == target(e, g)) {
+            if (source(e, g) == g.startDs) {
+                continue;
+            }
+            if (v != NGHolder::null_vertex()) {
+                // More than one cyclic vertex.
+                return NGHolder::null_vertex();
+            }
+            v = source(e, g);
+        }
+    }
+
+    if (v != NGHolder::null_vertex()) {
+        DEBUG_PRINTF("cyclic is %zu\n", g[v].index);
+        assert(!is_special(v, g));
+    }
+    return v;
+}
+
+static
+bool hasOffsetAdjust(const ReportManager &rm, NGHolder &g,
+                     int *adjust) {
+    const auto &reports = all_reports(g);
+    if (reports.empty()) {
+        assert(0);
+        return false;
+    }
+
+    int offsetAdjust = rm.getReport(*reports.begin()).offsetAdjust;
+    for (auto report : reports) {
+        const Report &ir = rm.getReport(report);
+        if (ir.offsetAdjust != offsetAdjust) {
+            DEBUG_PRINTF("different adjusts!\n");
+            return false;
+        }
+    }
+
+    *adjust = offsetAdjust;
+    return true;
+}
+
+/**
+ * If the pattern has a min_length and is of "ratchet" form with one unbounded
+ * repeat, that repeat can become a bounded repeat.
+ *
+ *     /foo.*bar/{min_length=100} --> /foo.{94,}bar/
+ */
+static
+bool transformMinLengthToRepeat(NGHolder &g, ReportManager &rm) {
+    const auto &reports = all_reports(g);
+
+    if (reports.empty()) {
+        return false;
+    }
+
+    if (!hasSameBounds(reports, rm)) {
+        DEBUG_PRINTF("mixed report bounds\n");
+        return false;
+    }
+
+    const auto &min_length = rm.getReport(*reports.begin()).minLength;
+    if (!min_length || min_length > MAX_MINLENGTH_TO_CONVERT) {
+        return false;
+    }
+
+    // If the pattern has virtual starts, we probably don't want to touch it.
+    if (hasVirtualStarts(g)) {
+        DEBUG_PRINTF("virtual starts, bailing\n");
+        return false;
+    }
+
+    // The graph must contain a single cyclic vertex (other than startDs), and
+    // that vertex can have one pred and one successor.
+    NFAVertex cyclic = findSingleCyclic(g);
+    if (cyclic == NGHolder::null_vertex()) {
+        return false;
+    }
+
+    NGHolder::adjacency_iterator ai, ae;
+    tie(ai, ae) = adjacent_vertices(g.start, g);
+    if (*ai == g.startDs) {
+        ++ai;
+    }
+    NFAVertex v = *ai;
+    if (++ai != ae) {
+        DEBUG_PRINTF("more than one initial vertex\n");
+        return false;
+    }
+
+    u32 width = 0;
+
+    // Walk from the start vertex to the cyclic state and ensure we have a
+    // chain of vertices.
+    while (v != cyclic) {
+        DEBUG_PRINTF("vertex %zu\n", g[v].index);
+        width++;
+        auto succ = succs(v, g);
+        if (contains(succ, cyclic)) {
+            if (succ.size() == 1) {
+                v = cyclic;
+            } else if (succ.size() == 2) {
+                // Cyclic and jump edge.
+                succ.erase(cyclic);
+                NFAVertex v2 = *succ.begin();
+                if (!edge(cyclic, v2, g).second) {
+                    DEBUG_PRINTF("bad form\n");
+                    return false;
+                }
+                v = cyclic;
+            } else {
+                DEBUG_PRINTF("bad form\n");
+                return false;
+            }
+        } else {
+            if (succ.size() != 1) {
+                DEBUG_PRINTF("bad form\n");
+                return false;
+            }
+            v = *succ.begin();
+        }
+    }
+
+    // Check the cyclic state is A-OK.
+    v = getSoleDestVertex(g, cyclic);
+    if (v == NGHolder::null_vertex()) {
+        DEBUG_PRINTF("cyclic has more than one successor\n");
+        return false;
+    }
+
+    // Walk from the cyclic state to an accept and ensure we have a chain of
+    // vertices.
+    while (!is_any_accept(v, g)) {
+        DEBUG_PRINTF("vertex %zu\n", g[v].index);
+        width++;
+        auto succ = succs(v, g);
+        if (succ.size() != 1) {
+            DEBUG_PRINTF("bad form\n");
+            return false;
+        }
+        v = *succ.begin();
+    }
+
+    int offsetAdjust = 0;
+    if (!hasOffsetAdjust(rm, g, &offsetAdjust)) {
+        return false;
+    }
+    DEBUG_PRINTF("adjusting width by %d\n", offsetAdjust);
+    width += offsetAdjust;
+
+    DEBUG_PRINTF("width=%u, vertex %zu is cyclic\n", width,
+                  g[cyclic].index);
+
+    if (width >= min_length) {
+        DEBUG_PRINTF("min_length=%llu is guaranteed, as width=%u\n",
+                      min_length, width);
+        clearMinLengthParam(g, rm);
+        return true;
+    }
+
+    vector<NFAVertex> preds;
+    vector<NFAEdge> dead;
+    for (auto u : inv_adjacent_vertices_range(cyclic, g)) {
+        DEBUG_PRINTF("pred %zu\n", g[u].index);
+        if (u == cyclic) {
+            continue;
+        }
+        preds.push_back(u);
+
+        // We want to delete the out-edges of each predecessor, but need to
+        // make sure we don't delete the startDs self loop.
+        for (const auto &e : out_edges_range(u, g)) {
+            if (target(e, g) != g.startDs) {
+                dead.push_back(e);
+            }
+        }
+    }
+
+    remove_edges(dead, g);
+
+    assert(!preds.empty());
+
+    const CharReach &cr = g[cyclic].char_reach;
+
+    for (u32 i = 0; i < min_length - width - 1; ++i) {
+        v = add_vertex(g);
+        g[v].char_reach = cr;
+
+        for (auto u : preds) {
+            add_edge(u, v, g);
+        }
+        preds.clear();
+        preds.push_back(v);
+    }
+    assert(!preds.empty());
+    for (auto u : preds) {
+        add_edge(u, cyclic, g);
+    }
+
+    renumber_vertices(g);
+    renumber_edges(g);
+    clearMinLengthParam(g, rm);
+    clearReports(g);
+    return true;
+}
+
+static
+bool hasExtParams(const ExpressionInfo &expr) {
+    if (expr.min_length != 0) {
+        return true;
+    }
+    if (expr.min_offset != 0) {
+        return true;
+    }
+    if (expr.max_offset != MAX_OFFSET) {
+        return true;
+    }
+    return false;
+}
+
+static
+const depth& maxDistToAccept(const NFAVertexBidiDepth &d) {
+    if (d.toAccept.max.is_unreachable()) {
+        return d.toAcceptEod.max;
+    } else if (d.toAcceptEod.max.is_unreachable()) {
+        return d.toAccept.max;
+    }
+    return max(d.toAccept.max, d.toAcceptEod.max);
+}
+
+static
+const depth& minDistFromStart(const NFAVertexBidiDepth &d) {
+    return min(d.fromStartDotStar.min, d.fromStart.min);
+}
+
+static
+const depth& minDistToAccept(const NFAVertexBidiDepth &d) {
+    return min(d.toAccept.min, d.toAcceptEod.min);
+}
+
+static
+bool isEdgePrunable(const NGHolder &g, const Report &report,
+                    const vector<NFAVertexBidiDepth> &depths,
+                    const NFAEdge &e) {
+    const NFAVertex u = source(e, g);
+    const NFAVertex v = target(e, g);
+
+    DEBUG_PRINTF("edge (%zu,%zu)\n", g[u].index, g[v].index);
+
+    // Leave our special-to-special edges alone.
+    if (is_special(u, g) && is_special(v, g)) {
+        DEBUG_PRINTF("ignoring special-to-special\n");
+        return false;
+    }
+
+    // We must be careful around start: we don't want to remove (start, v) if
+    // (startDs, v) exists as well, since later code will assume the presence
+    // of both edges, but other cases are OK.
+    if (u == g.start && edge(g.startDs, v, g).second) {
+        DEBUG_PRINTF("ignoring unanchored start edge\n");
+        return false;
+    }
+
+    u32 u_idx = g[u].index;
+    u32 v_idx = g[v].index;
+    assert(u_idx < depths.size() && v_idx < depths.size());
+
+    const NFAVertexBidiDepth &du = depths.at(u_idx);
+    const NFAVertexBidiDepth &dv = depths.at(v_idx);
+
+    if (report.minOffset) {
+        depth max_offset = maxDistFromStartOfData(du) + maxDistToAccept(dv);
+        if (max_offset.is_finite() && max_offset < report.minOffset) {
+            DEBUG_PRINTF("max_offset=%s too small\n", max_offset.str().c_str());
+            return true;
+        }
+    }
+
+    if (report.maxOffset != MAX_OFFSET) {
+        depth min_offset = minDistFromStart(du) + minDistToAccept(dv);
+        assert(min_offset.is_finite());
+
+        if (min_offset > report.maxOffset) {
+            DEBUG_PRINTF("min_offset=%s too large\n", min_offset.str().c_str());
+            return true;
+        }
+    }
+
+    if (report.minLength && is_any_accept(v, g)) {
+        // Simple take on min_length. If we're an edge to accept and our max
+        // dist from start is too small, we can be pruned.
+        const depth &width = maxDistFromInit(du);
+        if (width.is_finite() && width < report.minLength) {
+            DEBUG_PRINTF("max width %s from start too small for min_length\n",
+                         width.str().c_str());
+            return true;
+        }
+    }
+
+    return false;
+}
+
+static
+void pruneExtUnreachable(NGHolder &g, const ReportManager &rm) {
+    const auto &reports = all_reports(g);
+    if (reports.empty()) {
+        return;
+    }
+
+    if (!hasSameBounds(reports, rm)) {
+        DEBUG_PRINTF("report bounds vary\n");
+        return;
+    }
+
+    const auto &report = rm.getReport(*reports.begin());
+
+    auto depths = calcBidiDepths(g);
+
+    vector<NFAEdge> dead;
+
+    for (const auto &e : edges_range(g)) {
+        if (isEdgePrunable(g, report, depths, e)) {
+            DEBUG_PRINTF("pruning\n");
+            dead.push_back(e);
+        }
+    }
+
+    if (dead.empty()) {
+        return;
+    }
+
+    remove_edges(dead, g);
+    pruneUseless(g);
+    clearReports(g);
+}
+
+/**
+ * Remove vacuous edges in graphs where the min_offset or min_length
+ * constraints dictate that they can never produce a match.
+ */
+static
+void pruneVacuousEdges(NGHolder &g, const ReportManager &rm) {
+    vector<NFAEdge> dead;
+
+    auto has_min_offset = [&](NFAVertex v) {
+        assert(!g[v].reports.empty()); // must be reporter
+        return all_of_in(g[v].reports, [&](ReportID id) {
+            return rm.getReport(id).minOffset > 0;
+        });
+    };
+
+    auto has_min_length = [&](NFAVertex v) {
+        assert(!g[v].reports.empty()); // must be reporter
+        return all_of_in(g[v].reports, [&](ReportID id) {
+            return rm.getReport(id).minLength > 0;
+        });
+    };
+
+    for (const auto &e : edges_range(g)) {
+        const NFAVertex u = source(e, g);
+        const NFAVertex v = target(e, g);
+
+        // Special case: Crudely remove vacuous edges from start in graphs with
+        // a min_offset.
+        if (u == g.start && is_any_accept(v, g) && has_min_offset(u)) {
+            DEBUG_PRINTF("vacuous edge in graph with min_offset!\n");
+            dead.push_back(e);
+            continue;
+        }
+
+        // If a min_length is set, vacuous edges can be removed.
+        if (is_any_start(u, g) && is_any_accept(v, g) && has_min_length(u)) {
+            DEBUG_PRINTF("vacuous edge in graph with min_length!\n");
+            dead.push_back(e);
+            continue;
+        }
+    }
+
+    if (dead.empty()) {
+        return;
+    }
+
+    DEBUG_PRINTF("removing %zu vacuous edges\n", dead.size());
+    remove_edges(dead, g);
+    pruneUseless(g);
+    clearReports(g);
+}
+
+static
+void pruneUnmatchable(NGHolder &g, const vector<DepthMinMax> &depths,
+                      const ReportManager &rm, NFAVertex accept) {
+    vector<NFAEdge> dead;
+
+    for (const auto &e : in_edges_range(accept, g)) {
+        NFAVertex v = source(e, g);
+        if (v == g.accept) {
+            assert(accept == g.acceptEod); // stylised edge
+            continue;
+        }
+
+        if (!hasSameBounds(g[v].reports, rm)) {
+            continue;
+        }
+        const auto &report = rm.getReport(*g[v].reports.begin());
+
+        u32 idx = g[v].index;
+        DepthMinMax d = depths[idx]; // copy
+        pair<s32, s32> adj = getMinMaxOffsetAdjust(rm, g, v);
+        DEBUG_PRINTF("vertex %u: depths=%s, adj=[%d,%d]\n", idx,
+                     d.str().c_str(), adj.first, adj.second);
+        d.min += adj.first;
+        d.max += adj.second;
+
+        if (d.max.is_finite() && d.max < report.minLength) {
+            DEBUG_PRINTF("prune, max match length %s < min_length=%llu\n",
+                         d.max.str().c_str(), report.minLength);
+            dead.push_back(e);
+            continue;
+        }
+
+        if (report.maxOffset != MAX_OFFSET && d.min > report.maxOffset) {
+            DEBUG_PRINTF("prune, min match length %s > max_offset=%llu\n",
+                         d.min.str().c_str(), report.maxOffset);
+            dead.push_back(e);
+            continue;
+        }
+    }
+
+    remove_edges(dead, g);
+}
+
+/**
+ * Remove edges to accepts that can never produce a match long enough to
+ * satisfy our min_length and max_offset constraints.
+ */
+static
+void pruneUnmatchable(NGHolder &g, const ReportManager &rm) {
+    if (!any_of_in(all_reports(g), [&](ReportID id) {
+            return rm.getReport(id).minLength > 0;
+        })) {
+        return;
+    }
+
+    vector<DepthMinMax> depths = getDistancesFromSOM(g);
+
+    pruneUnmatchable(g, depths, rm, g.accept);
+    pruneUnmatchable(g, depths, rm, g.acceptEod);
+
+    pruneUseless(g);
+    clearReports(g);
+}
+
+static
+bool hasOffsetAdjustments(const ReportManager &rm, const NGHolder &g) {
+    return any_of_in(all_reports(g), [&rm](ReportID id) {
+        return rm.getReport(id).offsetAdjust != 0;
+    });
+}
+
+void propagateExtendedParams(NGHolder &g, ExpressionInfo &expr,
+                             ReportManager &rm) {
+    if (!hasExtParams(expr)) {
+        return;
+    }
+
+    depth minWidth = findMinWidth(g);
+    depth maxWidth = findMaxWidth(g);
+    bool is_anchored = !has_proper_successor(g.startDs, g)
+                     && out_degree(g.start, g);
+
+    DepthMinMax match_depths = findMatchLengths(rm, g);
+    DEBUG_PRINTF("match depths %s\n", match_depths.str().c_str());
+
+    if (is_anchored && maxWidth.is_finite() && expr.min_offset > maxWidth) {
+        ostringstream oss;
+        oss << "Expression is anchored and cannot satisfy min_offset="
+            << expr.min_offset << " as it can only produce matches of length "
+            << maxWidth << " bytes at most.";
+        throw CompileError(expr.index, oss.str());
+    }
+
+    if (minWidth > expr.max_offset) {
+        ostringstream oss;
+        oss << "Expression has max_offset=" << expr.max_offset
+            << " but requires " << minWidth << " bytes to match.";
+        throw CompileError(expr.index, oss.str());
+    }
+
+    if (maxWidth.is_finite() && match_depths.max < expr.min_length) {
+        ostringstream oss;
+        oss << "Expression has min_length=" << expr.min_length << " but can "
+            "only produce matches of length " << match_depths.max <<
+            " bytes at most.";
+        throw CompileError(expr.index, oss.str());
+    }
+
+    if (expr.min_length && expr.min_length <= match_depths.min) {
+        DEBUG_PRINTF("min_length=%llu constraint is unnecessary\n",
+                     expr.min_length);
+        expr.min_length = 0;
+    }
+
+    if (!hasExtParams(expr)) {
+        return;
+    }
+
+    updateReportBounds(rm, g, expr);
+}
+
+/**
+ * If the pattern is completely anchored and has a min_length set, this can
+ * be converted to a min_offset.
+ */
+static
+void replaceMinLengthWithOffset(NGHolder &g, ReportManager &rm) {
+    if (has_proper_successor(g.startDs, g)) {
+        return; // not wholly anchored
+    }
+
+    replaceReports(g, [&rm](NFAVertex, ReportID id) {
+        const auto &report = rm.getReport(id);
+        if (report.minLength) {
+            Report new_report = report;
+            u64a min_len_offset = report.minLength - report.offsetAdjust;
+            new_report.minOffset = max(report.minOffset, min_len_offset);
+            new_report.minLength = 0;
+            return rm.getInternalId(new_report);
+        }
+        return id;
+    });
+}
+
+/**
+ * Clear offset bounds on reports that are not needed because they're satisfied
+ * by vertex depth.
+ */
+static
+void removeUnneededOffsetBounds(NGHolder &g, ReportManager &rm) {
+    auto depths = calcDepths(g);
+
+    replaceReports(g, [&](NFAVertex v, ReportID id) {
+        const auto &d = depths.at(g[v].index);
+        const depth &min_depth = min(d.fromStartDotStar.min, d.fromStart.min);
+        const depth &max_depth = maxDistFromStartOfData(d);
+
+        DEBUG_PRINTF("vertex %zu has min_depth=%s, max_depth=%s\n", g[v].index,
+                     min_depth.str().c_str(), max_depth.str().c_str());
+
+        Report report = rm.getReport(id); // copy
+        bool modified = false;
+        if (report.minOffset && !report.offsetAdjust &&
+            report.minOffset <= min_depth) {
+            report.minOffset = 0;
+            modified = true;
+        }
+        if (report.maxOffset != MAX_OFFSET && max_depth.is_finite() &&
+            report.maxOffset >= max_depth) {
+            report.maxOffset = MAX_OFFSET;
+            modified = true;
+        }
+        if (modified) {
+            DEBUG_PRINTF("vertex %zu, changed bounds to [%llu,%llu]\n",
+                         g[v].index, report.minOffset, report.maxOffset);
+            return rm.getInternalId(report);
+        }
+
+        return id;
+    });
+}
+
+void reduceExtendedParams(NGHolder &g, ReportManager &rm, som_type som) {
+    if (!any_of_in(all_reports(g),
+                   [&](ReportID id) { return rm.getReport(id).hasBounds(); })) {
+        DEBUG_PRINTF("no extparam bounds\n");
+        return;
+    }
+
+    DEBUG_PRINTF("graph has extparam bounds\n");
+
+    pruneVacuousEdges(g, rm);
+    if (can_never_match(g)) {
+        return;
+    }
+
+    pruneUnmatchable(g, rm);
+    if (can_never_match(g)) {
+        return;
+    }
+
+    if (!hasOffsetAdjustments(rm, g)) {
+        pruneExtUnreachable(g, rm);
+        if (can_never_match(g)) {
+            return;
+        }
+    }
+
+    replaceMinLengthWithOffset(g, rm);
+    if (can_never_match(g)) {
+        return;
+    }
+
+    // If the pattern has a min_length and is of "ratchet" form with one
+    // unbounded repeat, that repeat can become a bounded repeat.
+    // e.g. /foo.*bar/{min_length=100} --> /foo.{94,}bar/
+    transformMinLengthToRepeat(g, rm);
+    if (can_never_match(g)) {
+        return;
+    }
+
+    // If the pattern is unanchored, has a max_offset and has not asked for
+    // SOM, we can use that knowledge to anchor it which will limit its
+    // lifespan. Note that we can't use this transformation if there's a
+    // min_length, as it's currently handled using "sly SOM".
+    if (som == SOM_NONE) {
+        anchorPatternWithBoundedRepeat(g, rm);
+        if (can_never_match(g)) {
+            return;
+        }
+    }
+
+    removeUnneededOffsetBounds(g, rm);
+}
+
+} // namespace ue2