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

/* 
 * Copyright (c) 2015-2017, Intel Corporation 
 * 
 * Redistribution and use in source and binary forms, with or without 
 * modification, are permitted provided that the following conditions are met: 
 * 
 *  * Redistributions of source code must retain the above copyright notice, 
 *    this list of conditions and the following disclaimer. 
 *  * Redistributions in binary form must reproduce the above copyright 
 *    notice, this list of conditions and the following disclaimer in the 
 *    documentation and/or other materials provided with the distribution. 
 *  * Neither the name of Intel Corporation nor the names of its contributors 
 *    may be used to endorse or promote products derived from this software 
 *    without specific prior written permission. 
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
 * POSSIBILITY OF SUCH DAMAGE. 
 */ 
 
/** \file 
 * \brief Graph fuzzer for approximate matching 
 */ 
 
#include "ng_fuzzy.h" 
 
#include "ng.h" 
#include "ng_depth.h" 
#include "ng_util.h" 
 
#include <map> 
#include <vector> 
using namespace std; 
 
namespace ue2 { 
 
// returns all successors up to a given depth in a vector of sets, indexed by 
// zero-based depth from source vertex 
static 
vector<flat_set<NFAVertex>> gatherSuccessorsByDepth(const NGHolder &g, 
                                                    NFAVertex src, u32 depth) { 
    vector<flat_set<NFAVertex>> result(depth); 
    flat_set<NFAVertex> cur, next; 
 
    assert(depth > 0); 
 
    // populate current set of successors 
    for (auto v : adjacent_vertices_range(src, g)) { 
        // ignore self-loops 
        if (src == v) { 
            continue; 
        } 
        DEBUG_PRINTF("Node %zu depth 1\n", g[v].index); 
        cur.insert(v); 
    } 
    result[0] = cur; 
 
    for (unsigned d = 1; d < depth; d++) { 
        // collect all successors for all current level vertices 
        for (auto v : cur) { 
            // don't go past special nodes 
            if (is_special(v, g)) { 
                continue; 
            } 
 
            for (auto succ : adjacent_vertices_range(v, g)) { 
                // ignore self-loops 
                if (v == succ) { 
                    continue; 
                } 
                DEBUG_PRINTF("Node %zu depth %u\n", g[succ].index, d + 1); 
                next.insert(succ); 
            } 
        } 
        result[d] = next; 
        next.swap(cur); 
        next.clear(); 
    } 
 
    return result; 
} 
 
// returns all predecessors up to a given depth in a vector of sets, indexed by 
// zero-based depth from source vertex 
static 
vector<flat_set<NFAVertex>> gatherPredecessorsByDepth(const NGHolder &g, 
                                                      NFAVertex src, 
                                                      u32 depth) { 
    vector<flat_set<NFAVertex>> result(depth); 
    flat_set<NFAVertex> cur, next; 
 
    assert(depth > 0); 
 
    // populate current set of successors 
    for (auto v : inv_adjacent_vertices_range(src, g)) { 
        // ignore self-loops 
        if (src == v) { 
            continue; 
        } 
        DEBUG_PRINTF("Node %zu depth 1\n", g[v].index); 
        cur.insert(v); 
    } 
    result[0] = cur; 
 
    for (unsigned d = 1; d < depth; d++) { 
        // collect all successors for all current level vertices 
        for (auto v : cur) { 
            for (auto pred : inv_adjacent_vertices_range(v, g)) { 
                // ignore self-loops 
                if (v == pred) { 
                    continue; 
                } 
                DEBUG_PRINTF("Node %zu depth %u\n", g[pred].index, d + 1); 
                next.insert(pred); 
            } 
        } 
        result[d] = next; 
        next.swap(cur); 
        next.clear(); 
    } 
 
    return result; 
} 
 
/* 
 * This struct produces a fuzzed graph; that is, a graph that is able to match 
 * the original pattern, as well as input data within a certain edit distance. 
 * Construct the struct, then call fuzz_graph() to transform the graph. 
 * 
 * Terminology used: 
 * - Shadow vertices: vertices mirroring the original graph at various edit 
 * distances 
 * - Shadow graph level: edit distance of a particular shadow graph 
 * - Helpers: dot vertices assigned to shadow vertices, used for insert/replace 
 */ 
struct ShadowGraph { 
    NGHolder &g; 
    u32 edit_distance; 
    bool hamming; 
    map<pair<NFAVertex, u32>, NFAVertex> shadow_map; 
    map<pair<NFAVertex, u32>, NFAVertex> helper_map; 
    map<NFAVertex, NFAVertex> clones; 
    // edge creation is deferred 
    vector<pair<NFAVertex, NFAVertex>> edges_to_be_added; 
    flat_set<NFAVertex> orig; 
 
    ShadowGraph(NGHolder &g_in, u32 ed_in, bool hamm_in) 
        : g(g_in), edit_distance(ed_in), hamming(hamm_in) {} 
 
    void fuzz_graph() { 
        if (edit_distance == 0) { 
            return; 
        } 
 
        DEBUG_PRINTF("edit distance = %u hamming = %s\n", edit_distance, 
                     hamming ? "true" : "false"); 
 
        // step 1: prepare the vertices, helpers and shadows according to 
        // the original graph 
        prepare_graph(); 
 
        // step 2: add shadow and helper nodes 
        build_shadow_graph(); 
 
        // step 3: set up reports for newly created vertices (and make clones 
        // if necessary) 
        if (!hamming) { 
            create_reports(); 
        } 
 
        // step 4: wire up shadow graph and helpers for insert/replace/remove 
        connect_shadow_graph(); 
 
        // step 5: commit all the edge wirings 
        DEBUG_PRINTF("Committing edge wirings\n"); 
        for (const auto &p : edges_to_be_added) { 
            add_edge_if_not_present(p.first, p.second, g); 
        } 
 
        DEBUG_PRINTF("Done!\n"); 
    } 
 
private: 
    const NFAVertex& get_clone(const NFAVertex &v) { 
        return contains(clones, v) ? 
                    clones[v] : v; 
    } 
 
    void connect_to_clones(const NFAVertex &u, const NFAVertex &v) { 
        const NFAVertex &clone_u = get_clone(u); 
        const NFAVertex &clone_v = get_clone(v); 
 
        edges_to_be_added.emplace_back(u, v); 
        DEBUG_PRINTF("Adding edge: %zu -> %zu\n", g[u].index, g[v].index); 
 
        // do not connect clones to accepts, we do it during cloning 
        if (is_any_accept(clone_v, g)) { 
            return; 
        } 
        edges_to_be_added.emplace_back(clone_u, clone_v); 
        DEBUG_PRINTF("Adding edge: %zu -> %zu\n", g[clone_u].index, 
                     g[clone_v].index); 
    } 
 
    void prepare_graph() { 
        DEBUG_PRINTF("Building shadow graphs\n"); 
 
        for (auto v : vertices_range(g)) { 
            // all level 0 vertices are their own helpers and their own shadows 
            helper_map[make_pair(v, 0)] = v; 
            shadow_map[make_pair(v, 0)] = v; 
 
            // find special nodes 
            if (is_any_accept(v, g)) { 
                DEBUG_PRINTF("Node %zu is a special node\n", g[v].index); 
                for (unsigned edit = 1; edit <= edit_distance; edit++) { 
                    // all accepts are their own shadows and helpers at all 
                    // levels 
                    shadow_map[make_pair(v, edit)] = v; 
                    helper_map[make_pair(v, edit)] = v; 
                } 
                continue; 
            } 
            DEBUG_PRINTF("Node %zu is to be shadowed\n", g[v].index); 
            orig.insert(v); 
        } 
    } 
 
    void build_shadow_graph() { 
        for (auto v : orig) { 
            DEBUG_PRINTF("Adding shadow/helper nodes for node %zu\n", 
                         g[v].index); 
            for (unsigned dist = 1; dist <= edit_distance; dist++) { 
                auto shadow_v = v; 
 
                // start and startDs cannot have shadows but do have helpers 
                if (!is_any_start(v, g)) { 
                    shadow_v = clone_vertex(g, v); 
                    DEBUG_PRINTF("New shadow node ID: %zu (level %u)\n", 
                                 g[shadow_v].index, dist); 
                } 
                shadow_map[make_pair(v, dist)] = shadow_v; 
 
                // if there's nowhere to go from this vertex, no helper needed 
                if (proper_out_degree(v, g) < 1) { 
                    DEBUG_PRINTF("No helper for node ID: %zu (level %u)\n", 
                                 g[shadow_v].index, dist); 
                    helper_map[make_pair(v, dist)] = shadow_v; 
                    continue; 
                } 
 
                // start and startDs only have helpers for insert, so not Hamming 
                if (hamming && is_any_start(v, g)) { 
                    DEBUG_PRINTF("No helper for node ID: %zu (level %u)\n", 
                                 g[shadow_v].index, dist); 
                    helper_map[make_pair(v, dist)] = shadow_v; 
                    continue; 
                } 
 
                auto helper_v = clone_vertex(g, v); 
                DEBUG_PRINTF("New helper node ID: %zu (level %u)\n", 
                             g[helper_v].index, dist); 
 
                // this is a helper, so make it a dot 
                g[helper_v].char_reach = CharReach::dot(); 
                // do not copy virtual start's assert flags 
                if (is_virtual_start(v, g)) { 
                    DEBUG_PRINTF("Helper node ID is virtual start: %zu (level %u)\n", 
                             g[helper_v].index, dist); 
                    g[helper_v].assert_flags = 0; 
                } 
                helper_map[make_pair(v, dist)] = helper_v; 
            } 
        } 
    } 
 
    // wire up successors according to the original graph, wire helpers 
    // to shadow successors (insert/replace) 
    void connect_succs(NFAVertex v, u32 dist) { 
        DEBUG_PRINTF("Wiring up successors for node %zu shadow level %u\n", 
                     g[v].index, dist); 
        const auto &cur_shadow_v = shadow_map[make_pair(v, dist)]; 
        const auto &cur_shadow_helper = helper_map[make_pair(v, dist)]; 
 
        // multiple insert 
        if (!hamming && dist > 1) { 
            const auto &prev_level_helper = helper_map[make_pair(v, dist - 1)]; 
            connect_to_clones(prev_level_helper, cur_shadow_helper); 
        } 
 
        for (auto orig_dst : adjacent_vertices_range(v, g)) { 
            const auto &shadow_dst = shadow_map[make_pair(orig_dst, dist)]; 
 
            connect_to_clones(cur_shadow_v, shadow_dst); 
 
            // ignore startDs for insert/replace 
            if (orig_dst == g.startDs) { 
                continue; 
            } 
 
            connect_to_clones(cur_shadow_helper, shadow_dst); 
        } 
    } 
 
    // wire up predecessors according to the original graph, wire 
    // predecessors to helpers (replace), wire predecessor helpers to 
    // helpers (multiple replace) 
    void connect_preds(NFAVertex v, u32 dist) { 
        DEBUG_PRINTF("Wiring up predecessors for node %zu shadow level %u\n", 
                     g[v].index, dist); 
        const auto &cur_shadow_v = shadow_map[make_pair(v, dist)]; 
        const auto &cur_shadow_helper = helper_map[make_pair(v, dist)]; 
 
        auto orig_src_vertices = inv_adjacent_vertices_range(v, g); 
        for (auto orig_src : orig_src_vertices) { 
            // ignore edges from start to startDs 
            if (v == g.startDs && orig_src == g.start) { 
                continue; 
            } 
            // ignore self-loops for replace 
            if (orig_src != v) { 
                // do not wire a replace node for start vertices if we 
                // have a virtual start 
                if (is_virtual_start(v, g) && is_any_start(orig_src, g)) { 
                    continue; 
                } 
 
                if (dist) { 
                    const auto &prev_level_src = 
                        shadow_map[make_pair(orig_src, dist - 1)]; 
                    const auto &prev_level_helper = 
                        helper_map[make_pair(orig_src, dist - 1)]; 
 
                    connect_to_clones(prev_level_src, cur_shadow_helper); 
                    connect_to_clones(prev_level_helper, cur_shadow_helper); 
                } 
            } 
            // wire predecessor according to original graph 
            const auto &shadow_src = shadow_map[make_pair(orig_src, dist)]; 
 
            connect_to_clones(shadow_src, cur_shadow_v); 
        } 
    } 
 
    // wire up previous level helper to current shadow (insert) 
    void connect_helpers(NFAVertex v, u32 dist) { 
        DEBUG_PRINTF("Wiring up helpers for node %zu shadow level %u\n", 
                     g[v].index, dist); 
        const auto &cur_shadow_helper = helper_map[make_pair(v, dist)]; 
        auto prev_level_v = shadow_map[make_pair(v, dist - 1)]; 
 
        connect_to_clones(prev_level_v, cur_shadow_helper); 
    } 
 
    /* 
     * wiring edges for removal is a special case. 
     * 
     * when wiring edges for removal, as well as wiring up immediate 
     * predecessors to immediate successors, we also need to wire up more 
     * distant successors to their respective shadow graph levels. 
     * 
     * for example, consider graph start->a->b->c->d->accept. 
     * 
     * at edit distance 1, we need remove edges start->b, a->c, b->d, and 
     * c->accept, all going from original graph (level 0) to shadow graph 
     * level 1. 
     * 
     * at edit distance 2, we also need edges start->c, a->d and b->accept, 
     * all going from level 0 to shadow graph level 2. 
     * 
     * this is propagated to all shadow levels; that is, given edit 
     * distance 3, we will have edges from shadow levels 0->1, 0->2, 
     * 0->3, 1->2, 1->3, and 2->3. 
     * 
     * therefore, we wire them in steps: first wire with step 1 (0->1, 1->2, 
     * 2->3) at depth 1, then wire with step 2 (0->2, 1->3) at depth 2, etc. 
     * 
     * we also have to wire helpers to their removal successors, to 
     * accommodate for a replace followed by a remove, on all shadow levels. 
     * 
     * and finally, we also have to wire source shadows into removal 
     * successor helpers on a level above, to accommodate for a remove 
     * followed by a replace. 
     */ 
    void connect_removals(NFAVertex v) { 
        DEBUG_PRINTF("Wiring up remove edges for node %zu\n", g[v].index); 
 
        // vertices returned by this function don't include self-loops 
        auto dst_vertices_by_depth = 
            gatherSuccessorsByDepth(g, v, edit_distance); 
        auto orig_src_vertices = inv_adjacent_vertices_range(v, g); 
        for (auto orig_src : orig_src_vertices) { 
            // ignore self-loops 
            if (orig_src == v) { 
                continue; 
            } 
            for (unsigned step = 1; step <= edit_distance; step++) { 
                for (unsigned dist = step; dist <= edit_distance; dist++) { 
                    auto &dst_vertices = dst_vertices_by_depth[step - 1]; 
                    for (auto &orig_dst : dst_vertices) { 
                        const auto &shadow_src = 
                            shadow_map[make_pair(orig_src, dist - step)]; 
                        const auto &shadow_helper = 
                            helper_map[make_pair(orig_src, dist - step)]; 
                        const auto &shadow_dst = 
                                shadow_map[make_pair(orig_dst, dist)]; 
 
                        // removal 
                        connect_to_clones(shadow_src, shadow_dst); 
 
                        // removal from helper vertex 
                        connect_to_clones(shadow_helper, shadow_dst); 
 
                        // removal into helper, requires additional edit 
                        if ((dist + 1) <= edit_distance) { 
                            const auto &next_level_helper = 
                                    helper_map[make_pair(orig_dst, dist + 1)]; 
 
                            connect_to_clones(shadow_src, next_level_helper); 
                        } 
                    } 
                } 
            } 
        } 
    } 
 
    void connect_shadow_graph() { 
        DEBUG_PRINTF("Wiring up the graph\n"); 
 
        for (auto v : orig) { 
 
            DEBUG_PRINTF("Wiring up edges for node %zu\n", g[v].index); 
 
            for (unsigned dist = 0; dist <= edit_distance; dist++) { 
 
                // handle insert/replace 
                connect_succs(v, dist); 
 
                // handle replace/multiple insert 
                connect_preds(v, dist); 
 
                // handle helpers 
                if (!hamming && dist > 0) { 
                    connect_helpers(v, dist); 
                } 
            } 
 
            // handle removals 
            if (!hamming) { 
                connect_removals(v); 
            } 
        } 
    } 
 
    void connect_to_targets(NFAVertex src, const flat_set<NFAVertex> &targets) { 
        for (auto dst : targets) { 
            DEBUG_PRINTF("Adding edge: %zu -> %zu\n", g[src].index, 
                         g[dst].index); 
            edges_to_be_added.emplace_back(src, dst); 
        } 
    } 
 
    // create a clone of the vertex, but overwrite its report set 
    void create_clone(NFAVertex v, const flat_set<ReportID> &reports, 
                      unsigned max_edit_distance, 
                      const flat_set<NFAVertex> &targets) { 
        // some vertices may have the same reports, but different successors; 
        // therefore, we may need to connect them multiple times, but still only 
        // clone once 
        bool needs_cloning = !contains(clones, v); 
 
        DEBUG_PRINTF("Cloning node %zu\n", g[v].index); 
        // go through all shadows and helpers, including 
        // original vertex 
        for (unsigned d = 0; d < max_edit_distance; d++) { 
            auto shadow_v = shadow_map[make_pair(v, d)]; 
            auto helper_v = helper_map[make_pair(v, d)]; 
 
            NFAVertex new_shadow_v, new_helper_v; 
 
            // make sure we don't clone the same vertex twice 
            if (needs_cloning) { 
                new_shadow_v = clone_vertex(g, shadow_v); 
                DEBUG_PRINTF("New shadow node ID: %zu (level %u)\n", 
                             g[new_shadow_v].index, d); 
                clones[shadow_v] = new_shadow_v; 
            } else { 
                new_shadow_v = clones[shadow_v]; 
            } 
            g[new_shadow_v].reports = reports; 
 
            connect_to_targets(new_shadow_v, targets); 
 
            if (shadow_v == helper_v) { 
                continue; 
            } 
            if (needs_cloning) { 
                new_helper_v = clone_vertex(g, helper_v); 
                DEBUG_PRINTF("New helper node ID: %zu (level %u)\n", 
                             g[new_helper_v].index, d); 
                clones[helper_v] = new_helper_v; 
            } else { 
                new_helper_v = clones[helper_v]; 
            } 
            g[new_helper_v].reports = reports; 
 
            connect_to_targets(new_helper_v, targets); 
        } 
    } 
 
    void write_reports(NFAVertex v, const flat_set<ReportID> &reports, 
                       unsigned max_edit_distance, 
                       const flat_set<NFAVertex> &targets) { 
        // we're overwriting reports, but we're not losing any 
        // information as we already cached all the different report 
        // sets, so vertices having different reports will be cloned and set up 
        // with the correct report set 
 
        // go through all shadows and helpers, including original 
        // vertex 
        for (unsigned d = 0; d < max_edit_distance; d++) { 
            auto shadow_v = shadow_map[make_pair(v, d)]; 
            auto helper_v = helper_map[make_pair(v, d)]; 
            DEBUG_PRINTF("Setting up reports for shadow node: %zu " 
                         "(level %u)\n", 
                         g[shadow_v].index, d); 
            DEBUG_PRINTF("Setting up reports for helper node: %zu " 
                         "(level %u)\n", 
                         g[helper_v].index, d); 
            g[shadow_v].reports = reports; 
            g[helper_v].reports = reports; 
 
            connect_to_targets(shadow_v, targets); 
            connect_to_targets(helper_v, targets); 
        } 
    } 
 
    /* 
     * we may have multiple report sets per graph. that means, whenever we 
     * construct additional paths through the graph (alternations, removals), we 
     * have to account for the fact that some vertices are predecessors to 
     * vertices with different report sets. 
     * 
     * whenever that happens, we have to clone the paths for both report sets, 
     * and set up these new vertices with their respective report sets as well. 
     * 
     * in order to do that, we first have to get all the predecessors for accept 
     * and acceptEod vertices. then, go through them one by one, and take note 
     * of the report lists. the first report set we find, wins, the rest we 
     * clone. 
     * 
     * we also have to do this in two passes, because there may be vertices that 
     * are predecessors to vertices with different report sets, so to avoid 
     * overwriting reports we will be caching reports info instead. 
     */ 
    void create_reports() { 
        map<flat_set<ReportID>, flat_set<NFAVertex>> reports_to_vertices; 
        flat_set<NFAVertex> accepts{g.accept, g.acceptEod}; 
 
        // gather reports info from all vertices connected to accept 
        for (auto accept : accepts) { 
            for (auto src : inv_adjacent_vertices_range(accept, g)) { 
                // skip special vertices 
                if (is_special(src, g)) { 
                    continue; 
                } 
                reports_to_vertices[g[src].reports].insert(src); 
            } 
        } 
 
        // we expect to see at most two report sets 
        assert(reports_to_vertices.size() > 0 && 
               reports_to_vertices.size() <= 2); 
 
        // set up all reports 
        bool clone = false; 
        for (auto &pair : reports_to_vertices) { 
            const auto &reports = pair.first; 
            const auto &vertices = pair.second; 
 
            for (auto src : vertices) { 
                // get all predecessors up to edit distance 
                auto src_vertices_by_depth = 
                        gatherPredecessorsByDepth(g, src, edit_distance); 
 
                // find which accepts source vertex connects to 
                flat_set<NFAVertex> targets; 
                for (const auto &accept : accepts) { 
                    NFAEdge e = edge(src, accept, g); 
                    if (e) { 
                        targets.insert(accept); 
                    } 
                } 
                assert(targets.size()); 
 
                for (unsigned d = 0; d < src_vertices_by_depth.size(); d++) { 
                    const auto &preds = src_vertices_by_depth[d]; 
                    for (auto v : preds) { 
                        // only clone a node if it already contains reports 
                        if (clone && !g[v].reports.empty()) { 
                            create_clone(v, reports, edit_distance - d, 
                                         targets); 
                        } else { 
                            write_reports(v, reports, edit_distance - d, 
                                          targets); 
                        } 
                    } 
                } 
            } 
            // clone vertices only if it's not our first report set 
            clone = true; 
        } 
    } 
}; 
 
// check if we will edit our way into a vacuous pattern 
static 
bool will_turn_vacuous(const NGHolder &g, u32 edit_distance) { 
    auto depths = calcRevDepths(g); 
 
    depth min_depth = depth::infinity(); 
    auto idx = g[g.start].index; 
 
    // check distance from start to accept/acceptEod 
    if (depths[idx].toAccept.min.is_finite()) { 
        min_depth = min(depths[idx].toAccept.min, min_depth); 
    } 
    if (depths[idx].toAcceptEod.min.is_finite()) { 
        min_depth = min(depths[idx].toAcceptEod.min, min_depth); 
    } 
 
    idx = g[g.startDs].index; 
 
    // check distance from startDs to accept/acceptEod 
    if (depths[idx].toAccept.min.is_finite()) { 
        min_depth = min(depths[idx].toAccept.min, min_depth); 
    } 
    if (depths[idx].toAcceptEod.min.is_finite()) { 
        min_depth = min(depths[idx].toAcceptEod.min, min_depth); 
    } 
 
    assert(min_depth.is_finite()); 
 
    // now, check if we can edit our way into a vacuous pattern 
    if (min_depth <= (u64a) edit_distance + 1) { 
        DEBUG_PRINTF("Pattern will turn vacuous if approximately matched\n"); 
        return true; 
    } 
    return false; 
} 
 
void validate_fuzzy_compile(const NGHolder &g, u32 edit_distance, bool hamming, 
                            bool utf8, const Grey &grey) { 
    if (edit_distance == 0) { 
        return; 
    } 
    if (!grey.allowApproximateMatching) { 
        throw CompileError("Approximate matching is disabled."); 
    } 
    if (edit_distance > grey.maxEditDistance) { 
        throw CompileError("Edit distance is too big."); 
    } 
    if (utf8) { 
        throw CompileError("UTF-8 is disallowed for approximate matching."); 
    } 
    // graph isn't fuzzable if there are edge assertions anywhere in the graph 
    for (auto e : edges_range(g)) { 
        if (g[e].assert_flags) { 
            throw CompileError("Zero-width assertions are disallowed for " 
                               "approximate matching."); 
        } 
    } 
    if (!hamming && will_turn_vacuous(g, edit_distance)) { 
        throw CompileError("Approximate matching patterns that reduce to " 
                           "vacuous patterns are disallowed."); 
    } 
} 
 
void make_fuzzy(NGHolder &g, u32 edit_distance, bool hamming, 
                const Grey &grey) { 
    if (edit_distance == 0) { 
        return; 
    } 
 
    assert(grey.allowApproximateMatching); 
    assert(grey.maxEditDistance >= edit_distance); 
 
    ShadowGraph sg(g, edit_distance, hamming); 
    sg.fuzz_graph(); 
 
    // For safety, enforce limit on actual vertex count. 
    if (num_vertices(g) > grey.limitApproxMatchingVertices) { 
        DEBUG_PRINTF("built %zu vertices > limit of %u\n", num_vertices(g), 
                     grey.limitApproxMatchingVertices); 
        throw ResourceLimitError(); 
    } 
} 
 
} // namespace ue2