diff options
author | Ivan Blinkov <ivan@blinkov.ru> | 2022-02-10 16:47:11 +0300 |
---|---|---|
committer | Daniil Cherednik <dcherednik@yandex-team.ru> | 2022-02-10 16:47:11 +0300 |
commit | 5b283123c882433dafbaf6b338adeea16c1a0ea0 (patch) | |
tree | 339adc63bce23800021202ae4a8328a843dc447a /contrib/libs/hyperscan/src/nfagraph/ng_som.cpp | |
parent | 1aeb9a455974457866f78722ad98114bafc84e8a (diff) | |
download | ydb-5b283123c882433dafbaf6b338adeea16c1a0ea0.tar.gz |
Restoring authorship annotation for Ivan Blinkov <ivan@blinkov.ru>. Commit 2 of 2.
Diffstat (limited to 'contrib/libs/hyperscan/src/nfagraph/ng_som.cpp')
-rw-r--r-- | contrib/libs/hyperscan/src/nfagraph/ng_som.cpp | 356 |
1 files changed, 178 insertions, 178 deletions
diff --git a/contrib/libs/hyperscan/src/nfagraph/ng_som.cpp b/contrib/libs/hyperscan/src/nfagraph/ng_som.cpp index 90942def3e..d23ac408b0 100644 --- a/contrib/libs/hyperscan/src/nfagraph/ng_som.cpp +++ b/contrib/libs/hyperscan/src/nfagraph/ng_som.cpp @@ -1,5 +1,5 @@ /* - * Copyright (c) 2015-2017, Intel Corporation + * 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: @@ -26,13 +26,13 @@ * POSSIBILITY OF SUCH DAMAGE. */ -/** - * \file +/** + * \file * \brief SOM ("Start of Match") analysis. */ - -#include "ng_som.h" - + +#include "ng_som.h" + #include "ng.h" #include "ng_dump.h" #include "ng_equivalence.h" @@ -48,11 +48,11 @@ #include "ng_som_util.h" #include "ng_split.h" #include "ng_util.h" -#include "ng_violet.h" +#include "ng_violet.h" #include "ng_width.h" #include "grey.h" #include "ue2common.h" -#include "compiler/compiler.h" +#include "compiler/compiler.h" #include "nfa/goughcompile.h" #include "nfa/nfa_internal.h" // for MO_INVALID_IDX #include "parser/position.h" @@ -69,8 +69,8 @@ #include <algorithm> #include <map> -#include <unordered_map> -#include <unordered_set> +#include <unordered_map> +#include <unordered_set> #include <vector> using namespace std; @@ -105,7 +105,7 @@ struct som_plan { static bool regionCanEstablishSom(const NGHolder &g, - const unordered_map<NFAVertex, u32> ®ions, + const unordered_map<NFAVertex, u32> ®ions, const u32 region, const vector<NFAVertex> &r_exits, const vector<DepthMinMax> &depths) { if (region == regions.at(g.accept) || @@ -116,7 +116,7 @@ bool regionCanEstablishSom(const NGHolder &g, DEBUG_PRINTF("region %u\n", region); for (UNUSED auto v : r_exits) { - DEBUG_PRINTF(" exit %zu\n", g[v].index); + DEBUG_PRINTF(" exit %zu\n", g[v].index); } /* simple if each region exit is at fixed distance from SOM. Note SOM does @@ -125,12 +125,12 @@ bool regionCanEstablishSom(const NGHolder &g, assert(regions.at(v) == region); const DepthMinMax &d = depths.at(g[v].index); if (d.min != d.max) { - DEBUG_PRINTF("failing %zu as %s != %s\n", g[v].index, + DEBUG_PRINTF("failing %zu as %s != %s\n", g[v].index, d.min.str().c_str(), d.max.str().c_str()); return false; } } - DEBUG_PRINTF("region %u/%zu is good\n", regions.at(r_exits[0]), + DEBUG_PRINTF("region %u/%zu is good\n", regions.at(r_exits[0]), g[r_exits[0]].index); return true; @@ -151,7 +151,7 @@ struct region_info { static void buildRegionMapping(const NGHolder &g, - const unordered_map<NFAVertex, u32> ®ions, + const unordered_map<NFAVertex, u32> ®ions, map<u32, region_info> &info, bool include_region_0 = false) { for (auto v : vertices_range(g)) { @@ -184,7 +184,7 @@ void buildRegionMapping(const NGHolder &g, set<NFAEdge> be; BackEdges<set<NFAEdge> > backEdgeVisitor(be); - boost::depth_first_search(g, visitor(backEdgeVisitor).root_vertex(g.start)); + boost::depth_first_search(g, visitor(backEdgeVisitor).root_vertex(g.start)); for (const auto &e : be) { NFAVertex u = source(e, g); @@ -211,17 +211,17 @@ void buildRegionMapping(const NGHolder &g, r_i.optional ? " (optional)" : ""); DEBUG_PRINTF(" enters:"); for (u32 i = 0; i < r_i.enters.size(); i++) { - printf(" %zu", g[r_i.enters[i]].index); + printf(" %zu", g[r_i.enters[i]].index); } printf("\n"); DEBUG_PRINTF(" exits:"); for (u32 i = 0; i < r_i.exits.size(); i++) { - printf(" %zu", g[r_i.exits[i]].index); + printf(" %zu", g[r_i.exits[i]].index); } printf("\n"); DEBUG_PRINTF(" all:"); for (u32 i = 0; i < r_i.full.size(); i++) { - printf(" %zu", g[r_i.full[i]].index); + printf(" %zu", g[r_i.full[i]].index); } printf("\n"); } @@ -230,7 +230,7 @@ void buildRegionMapping(const NGHolder &g, static bool validateXSL(const NGHolder &g, - const unordered_map<NFAVertex, u32> ®ions, + const unordered_map<NFAVertex, u32> ®ions, const u32 region, const CharReach &escapes, u32 *bad_region) { /* need to check that the escapes escape all of the graph past region */ u32 first_bad_region = ~0U; @@ -238,7 +238,7 @@ bool validateXSL(const NGHolder &g, u32 v_region = regions.at(v); if (!is_special(v, g) && v_region > region && (escapes & g[v].char_reach).any()) { - DEBUG_PRINTF("problem with escapes for %zu\n", g[v].index); + DEBUG_PRINTF("problem with escapes for %zu\n", g[v].index); first_bad_region = MIN(first_bad_region, v_region); } } @@ -253,7 +253,7 @@ bool validateXSL(const NGHolder &g, static bool validateEXSL(const NGHolder &g, - const unordered_map<NFAVertex, u32> ®ions, + const unordered_map<NFAVertex, u32> ®ions, const u32 region, const CharReach &escapes, const NGHolder &prefix, u32 *bad_region) { /* EXSL: To be a valid EXSL with escapes e, we require that all states @@ -267,7 +267,7 @@ bool validateEXSL(const NGHolder &g, const vector<CharReach> escapes_vec(1, escapes); const vector<CharReach> notescapes_vec(1, ~escapes); - flat_set<NFAVertex> states; + flat_set<NFAVertex> states; /* turn on all states past the prefix */ DEBUG_PRINTF("region %u is cutover\n", region); for (auto v : vertices_range(g)) { @@ -280,7 +280,7 @@ bool validateEXSL(const NGHolder &g, states = execute_graph(g, escapes_vec, states); /* flood with any number of not escapes */ - flat_set<NFAVertex> prev_states; + flat_set<NFAVertex> prev_states; while (prev_states != states) { prev_states = states; states = execute_graph(g, notescapes_vec, states); @@ -290,7 +290,7 @@ bool validateEXSL(const NGHolder &g, /* find input starts to use for when we are running the prefix through as * when the escape character arrives we may be in matching the prefix * already */ - flat_set<NFAVertex> prefix_start_states; + flat_set<NFAVertex> prefix_start_states; for (auto v : vertices_range(prefix)) { if (v != prefix.accept && v != prefix.acceptEod /* and as we have already made it past the prefix once */ @@ -355,7 +355,7 @@ bool isPossibleLock(const NGHolder &g, static unique_ptr<NGHolder> -makePrefix(const NGHolder &g, const unordered_map<NFAVertex, u32> ®ions, +makePrefix(const NGHolder &g, const unordered_map<NFAVertex, u32> ®ions, const region_info &curr, const region_info &next, bool renumber = true) { const vector<NFAVertex> &curr_exits = curr.exits; @@ -370,12 +370,12 @@ makePrefix(const NGHolder &g, const unordered_map<NFAVertex, u32> ®ions, deque<NFAVertex> lhs_verts; insert(&lhs_verts, lhs_verts.end(), vertices(g)); - unordered_map<NFAVertex, NFAVertex> lhs_map; // g -> prefix + unordered_map<NFAVertex, NFAVertex> lhs_map; // g -> prefix fillHolder(&prefix, g, lhs_verts, &lhs_map); prefix.kind = NFA_OUTFIX; // We need a reverse mapping to track regions. - unordered_map<NFAVertex, NFAVertex> rev_map; // prefix -> g + unordered_map<NFAVertex, NFAVertex> rev_map; // prefix -> g for (const auto &e : lhs_map) { rev_map.emplace(e.second, e.first); } @@ -385,7 +385,7 @@ makePrefix(const NGHolder &g, const unordered_map<NFAVertex, u32> ®ions, add_edge(prefix.accept, prefix.acceptEod, prefix); assert(!next_enters.empty()); - assert(next_enters.front() != NGHolder::null_vertex()); + assert(next_enters.front() != NGHolder::null_vertex()); u32 dead_region = regions.at(next_enters.front()); DEBUG_PRINTF("curr_region %u, dead_region %u\n", regions.at(curr_exits.front()), dead_region); @@ -404,7 +404,7 @@ makePrefix(const NGHolder &g, const unordered_map<NFAVertex, u32> ®ions, vector<NFAVertex> to_clear; assert(contains(lhs_map, curr_exits.front())); NFAVertex p_u = lhs_map[curr_exits.front()]; - DEBUG_PRINTF("p_u: %zu\n", prefix[p_u].index); + DEBUG_PRINTF("p_u: %zu\n", prefix[p_u].index); for (auto p_v : adjacent_vertices_range(p_u, prefix)) { auto v = rev_map.at(p_v); if (p_v == prefix.accept || regions.at(v) < dead_region) { @@ -414,7 +414,7 @@ makePrefix(const NGHolder &g, const unordered_map<NFAVertex, u32> ®ions, } for (auto v : to_clear) { - DEBUG_PRINTF("clearing in_edges on %zu\n", prefix[v].index); + DEBUG_PRINTF("clearing in_edges on %zu\n", prefix[v].index); clear_in_edges(v, prefix); } @@ -446,9 +446,9 @@ void replaceTempSomSlot(ReportManager &rm, NGHolder &g, u32 real_slot) { } static -void setPrefixReports(ReportManager &rm, NGHolder &g, ReportType ir_type, - u32 som_loc, const vector<DepthMinMax> &depths, - bool prefix_by_rev) { +void setPrefixReports(ReportManager &rm, NGHolder &g, ReportType ir_type, + u32 som_loc, const vector<DepthMinMax> &depths, + bool prefix_by_rev) { Report ir = makeCallback(0U, 0); ir.type = ir_type; ir.onmatch = som_loc; @@ -472,7 +472,7 @@ void setPrefixReports(ReportManager &rm, NGHolder &g, ReportType ir_type, } static -void updatePrefixReports(ReportManager &rm, NGHolder &g, ReportType ir_type) { +void updatePrefixReports(ReportManager &rm, NGHolder &g, ReportType ir_type) { /* update the som action on the prefix report */ for (auto v : inv_adjacent_vertices_range(g.accept, g)) { auto &reports = g[v].reports; @@ -543,7 +543,7 @@ void setMidfixReports(ReportManager &rm, const som_plan &item, static bool finalRegion(const NGHolder &g, - const unordered_map<NFAVertex, u32> ®ions, + const unordered_map<NFAVertex, u32> ®ions, NFAVertex v) { u32 region = regions.at(v); for (auto w : adjacent_vertices_range(v, g)) { @@ -557,8 +557,8 @@ bool finalRegion(const NGHolder &g, static void replaceExternalReportsWithSomRep(ReportManager &rm, NGHolder &g, - NFAVertex v, ReportType ir_type, - u64a param) { + NFAVertex v, ReportType ir_type, + u64a param) { assert(!g[v].reports.empty()); flat_set<ReportID> r_new; @@ -577,7 +577,7 @@ void replaceExternalReportsWithSomRep(ReportManager &rm, NGHolder &g, ir.somDistance = param; ReportID rep = rm.getInternalId(ir); - DEBUG_PRINTF("vertex %zu, replacing report %u with %u (type %u)\n", + DEBUG_PRINTF("vertex %zu, replacing report %u with %u (type %u)\n", g[v].index, report_id, rep, ir_type); r_new.insert(rep); } @@ -691,7 +691,7 @@ void fillHolderForLockCheck(NGHolder *out, const NGHolder &g, map<u32, region_info>::const_iterator picked) { /* NOTE: This is appropriate for firstMatchIsFirst */ DEBUG_PRINTF("prepping for lock check\n"); - + NGHolder &midfix = *out; map<NFAVertex, NFAVertex> v_map; @@ -699,18 +699,18 @@ void fillHolderForLockCheck(NGHolder *out, const NGHolder &g, v_map[g.startDs] = midfix.startDs; /* include the lock region */ - assert(picked != info.end()); - auto graph_last = next(picked); + assert(picked != info.end()); + auto graph_last = next(picked); + + assert(!graph_last->second.dag); + assert(graph_last->second.full.size() == 1); - assert(!graph_last->second.dag); - assert(graph_last->second.full.size() == 1); - - for (auto jt = graph_last; ; --jt) { + for (auto jt = graph_last; ; --jt) { DEBUG_PRINTF("adding r %u to midfix\n", jt->first); /* add all vertices in region, create mapping */ for (auto v : jt->second.full) { - DEBUG_PRINTF("adding v %zu to midfix\n", g[v].index); + DEBUG_PRINTF("adding v %zu to midfix\n", g[v].index); if (contains(v_map, v)) { continue; } @@ -742,38 +742,38 @@ void fillHolderForLockCheck(NGHolder *out, const NGHolder &g, } } - if (jt == info.begin()) { - break; - } - } - - /* add edges from startds to the enters of all the initial optional - * regions and the first mandatory region. */ - for (auto jt = info.begin(); ; ++jt) { + if (jt == info.begin()) { + break; + } + } + + /* add edges from startds to the enters of all the initial optional + * regions and the first mandatory region. */ + for (auto jt = info.begin(); ; ++jt) { for (auto enter : jt->second.enters) { assert(contains(v_map, enter)); NFAVertex v = v_map[enter]; add_edge_if_not_present(midfix.startDs, v, midfix); } - if (!jt->second.optional) { + if (!jt->second.optional) { + break; + } + + if (jt == graph_last) { + /* all regions are optional - add a direct edge to accept */ + add_edge_if_not_present(midfix.startDs, midfix.accept, midfix); break; } - - if (jt == graph_last) { - /* all regions are optional - add a direct edge to accept */ - add_edge_if_not_present(midfix.startDs, midfix.accept, midfix); - break; - } } assert(in_degree(midfix.accept, midfix)); - renumber_vertices(midfix); + renumber_vertices(midfix); } static void fillRoughMidfix(NGHolder *out, const NGHolder &g, - const unordered_map<NFAVertex, u32> ®ions, + const unordered_map<NFAVertex, u32> ®ions, const map<u32, region_info> &info, map<u32, region_info>::const_iterator picked) { /* as we are not the first prefix, we are probably not acyclic. We need to @@ -795,7 +795,7 @@ void fillRoughMidfix(NGHolder *out, const NGHolder &g, /* add all vertices in region, create mapping */ for (auto v : jt->second.full) { - DEBUG_PRINTF("adding v %zu to midfix\n", g[v].index); + DEBUG_PRINTF("adding v %zu to midfix\n", g[v].index); NFAVertex vnew = add_vertex(g[v], midfix); v_map[v] = vnew; } @@ -835,7 +835,7 @@ void fillRoughMidfix(NGHolder *out, const NGHolder &g, do { for (auto v : jt->second.exits) { - DEBUG_PRINTF("adding v %zu to midfix\n", g[v].index); + DEBUG_PRINTF("adding v %zu to midfix\n", g[v].index); NFAVertex vnew = add_vertex(g[v], midfix); v_map[v] = vnew; @@ -943,7 +943,7 @@ bool isMandRegionBetween(map<u32, region_info>::const_iterator a, // (woot!); updates picked, plan and bad_region. static bool advancePlan(const NGHolder &g, - const unordered_map<NFAVertex, u32> ®ions, + const unordered_map<NFAVertex, u32> ®ions, const NGHolder &prefix, bool stuck, map<u32, region_info>::const_iterator &picked, const map<u32, region_info>::const_iterator furthest, @@ -1022,7 +1022,7 @@ bool addPlan(vector<som_plan> &plan, u32 parent) { // Fetches all preds of {accept, acceptEod} for this graph. static void addReporterVertices(const NGHolder &g, vector<NFAVertex> &reporters) { - set<NFAVertex> tmp; + set<NFAVertex> tmp; insert(&tmp, inv_adjacent_vertices(g.accept, g)); insert(&tmp, inv_adjacent_vertices(g.acceptEod, g)); tmp.erase(g.accept); @@ -1030,7 +1030,7 @@ void addReporterVertices(const NGHolder &g, vector<NFAVertex> &reporters) { #ifdef DEBUG DEBUG_PRINTF("add reporters:"); for (UNUSED auto v : tmp) { - printf(" %zu", g[v].index); + printf(" %zu", g[v].index); } printf("\n"); #endif @@ -1044,7 +1044,7 @@ void addReporterVertices(const region_info &r, const NGHolder &g, vector<NFAVertex> &reporters) { for (auto v : r.exits) { if (edge(v, g.accept, g).second || edge(v, g.acceptEod, g).second) { - DEBUG_PRINTF("add reporter %zu\n", g[v].index); + DEBUG_PRINTF("add reporter %zu\n", g[v].index); reporters.push_back(v); } } @@ -1053,12 +1053,12 @@ void addReporterVertices(const region_info &r, const NGHolder &g, // Fetches the mappings of all preds of {accept, acceptEod} in this region. static void addMappedReporterVertices(const region_info &r, const NGHolder &g, - const unordered_map<NFAVertex, NFAVertex> &mapping, + const unordered_map<NFAVertex, NFAVertex> &mapping, vector<NFAVertex> &reporters) { for (auto v : r.exits) { if (edge(v, g.accept, g).second || edge(v, g.acceptEod, g).second) { - DEBUG_PRINTF("adding v=%zu\n", g[v].index); - auto it = mapping.find(v); + DEBUG_PRINTF("adding v=%zu\n", g[v].index); + auto it = mapping.find(v); assert(it != mapping.end()); reporters.push_back(it->second); } @@ -1069,9 +1069,9 @@ void addMappedReporterVertices(const region_info &r, const NGHolder &g, // from earlier regions. static void cloneGraphWithOneEntry(NGHolder &out, const NGHolder &g, - const unordered_map<NFAVertex, u32> ®ions, + const unordered_map<NFAVertex, u32> ®ions, NFAVertex entry, const vector<NFAVertex> &enters, - unordered_map<NFAVertex, NFAVertex> &orig_to_copy) { + unordered_map<NFAVertex, NFAVertex> &orig_to_copy) { orig_to_copy.clear(); cloneHolder(out, g, &orig_to_copy); @@ -1096,7 +1096,7 @@ void cloneGraphWithOneEntry(NGHolder &out, const NGHolder &g, } static -void expandGraph(NGHolder &g, unordered_map<NFAVertex, u32> ®ions, +void expandGraph(NGHolder &g, unordered_map<NFAVertex, u32> ®ions, vector<NFAVertex> &enters) { assert(!enters.empty()); const u32 split_region = regions.at(enters.front()); @@ -1113,7 +1113,7 @@ void expandGraph(NGHolder &g, unordered_map<NFAVertex, u32> ®ions, } for (auto enter : enters) { - DEBUG_PRINTF("processing enter %zu\n", g[enter].index); + DEBUG_PRINTF("processing enter %zu\n", g[enter].index); map<NFAVertex, NFAVertex> orig_to_copy; // Make a copy of all of the tail vertices, storing region info along @@ -1163,7 +1163,7 @@ void expandGraph(NGHolder &g, unordered_map<NFAVertex, u32> ®ions, [&](const NFAEdge &e) { NFAVertex u = source(e, g); return regions.at(u) < split_region; - }, g); + }, g); } new_enters.push_back(orig_to_copy[enter]); @@ -1179,11 +1179,11 @@ void expandGraph(NGHolder &g, unordered_map<NFAVertex, u32> ®ions, static bool doTreePlanningIntl(NGHolder &g, - const unordered_map<NFAVertex, u32> ®ions, + const unordered_map<NFAVertex, u32> ®ions, const map<u32, region_info> &info, map<u32, region_info>::const_iterator picked, u32 bad_region, u32 parent_plan, - const unordered_map<NFAVertex, NFAVertex> ©_to_orig, + const unordered_map<NFAVertex, NFAVertex> ©_to_orig, vector<som_plan> &plan, const Grey &grey) { assert(picked != info.end()); @@ -1335,14 +1335,14 @@ bool doTreePlanning(NGHolder &g, dumpHolder(g, g_regions, 14, "som_expandedtree", grey); for (auto v : enters) { - DEBUG_PRINTF("enter %zu\n", g[v].index); + DEBUG_PRINTF("enter %zu\n", g[v].index); // For this entry vertex, construct a version of the graph without the // other entries in this region (g_path), and calculate its depths and // regions. NGHolder g_path; - unordered_map<NFAVertex, NFAVertex> orig_to_copy; + unordered_map<NFAVertex, NFAVertex> orig_to_copy; cloneGraphWithOneEntry(g_path, g, g_regions, v, enters, orig_to_copy); auto regions = assignRegions(g_path); dumpHolder(g_path, regions, 14, "som_treepath", grey); @@ -1376,7 +1376,7 @@ bool doTreePlanning(NGHolder &g, } // Construct reverse mapping from vertices in g_path to g. - unordered_map<NFAVertex, NFAVertex> copy_to_orig; + unordered_map<NFAVertex, NFAVertex> copy_to_orig; for (const auto &m : orig_to_copy) { copy_to_orig.insert(make_pair(m.second, m.first)); } @@ -1399,7 +1399,7 @@ enum dsp_behaviour { static bool doSomPlanning(NGHolder &g, bool stuck_in, - const unordered_map<NFAVertex, u32> ®ions, + const unordered_map<NFAVertex, u32> ®ions, const map<u32, region_info> &info, map<u32, region_info>::const_iterator picked, vector<som_plan> &plan, @@ -1570,12 +1570,12 @@ void dumpSomPlan(UNUSED const NGHolder &g, UNUSED const som_plan &p, p.is_reset, p.parent); printf(" reporters:"); for (auto v : p.reporters) { - printf(" %zu", g[v].index); + printf(" %zu", g[v].index); } printf("\n"); printf(" reporters_in:"); for (auto v : p.reporters_in) { - printf(" %zu", g[v].index); + printf(" %zu", g[v].index); } printf("\n"); #endif @@ -1589,9 +1589,9 @@ void dumpSomPlan(UNUSED const NGHolder &g, UNUSED const som_plan &p, * implement the full pattern. */ static -void implementSomPlan(NG &ng, const ExpressionInfo &expr, u32 comp_id, - NGHolder &g, vector<som_plan> &plan, - const u32 first_som_slot) { +void implementSomPlan(NG &ng, const ExpressionInfo &expr, u32 comp_id, + NGHolder &g, vector<som_plan> &plan, + const u32 first_som_slot) { ReportManager &rm = ng.rm; SomSlotManager &ssm = ng.ssm; @@ -1604,14 +1604,14 @@ void implementSomPlan(NG &ng, const ExpressionInfo &expr, u32 comp_id, // Root plan, which already has a SOM slot assigned (first_som_slot). dumpSomPlan(g, plan.front(), 0); - dumpSomSubComponent(*plan.front().prefix, "04_som", expr.index, comp_id, 0, - ng.cc.grey); + dumpSomSubComponent(*plan.front().prefix, "04_som", expr.index, comp_id, 0, + ng.cc.grey); assert(plan.front().prefix); if (plan.front().escapes.any() && !plan.front().is_reset) { /* setup escaper for first som location */ if (!createEscaper(ng, *plan.front().prefix, plan.front().escapes, first_som_slot)) { - throw CompileError(expr.index, "Pattern is too large."); + throw CompileError(expr.index, "Pattern is too large."); } } @@ -1623,7 +1623,7 @@ void implementSomPlan(NG &ng, const ExpressionInfo &expr, u32 comp_id, for (++it; it != plan.end(); ++it) { const u32 plan_num = it - plan.begin(); dumpSomPlan(g, *it, plan_num); - dumpSomSubComponent(*it->prefix, "04_som", expr.index, comp_id, + dumpSomSubComponent(*it->prefix, "04_som", expr.index, comp_id, plan_num, ng.cc.grey); assert(it->parent < plan_num); @@ -1634,7 +1634,7 @@ void implementSomPlan(NG &ng, const ExpressionInfo &expr, u32 comp_id, assert(!it->no_implement); if (!buildMidfix(ng, *it, som_slot_in, som_slot_out)) { - throw CompileError(expr.index, "Pattern is too large."); + throw CompileError(expr.index, "Pattern is too large."); } updateReportToUseRecordedSom(rm, g, it->reporters_in, som_slot_in); updateReportToUseRecordedSom(rm, g, it->reporters, som_slot_out); @@ -1642,10 +1642,10 @@ void implementSomPlan(NG &ng, const ExpressionInfo &expr, u32 comp_id, /* create prefix to set the som_loc */ if (!plan.front().no_implement) { - renumber_vertices(*plan.front().prefix); + renumber_vertices(*plan.front().prefix); assert(plan.front().prefix->kind == NFA_OUTFIX); if (!ng.addHolder(*plan.front().prefix)) { - throw CompileError(expr.index, "Pattern is too large."); + throw CompileError(expr.index, "Pattern is too large."); } } } @@ -1733,17 +1733,17 @@ void clearProperInEdges(NGHolder &g, const NFAVertex sink) { namespace { struct SomRevNfa { - SomRevNfa(NFAVertex s, ReportID r, bytecode_ptr<NFA> n) + SomRevNfa(NFAVertex s, ReportID r, bytecode_ptr<NFA> n) : sink(s), report(r), nfa(move(n)) {} NFAVertex sink; ReportID report; - bytecode_ptr<NFA> nfa; + bytecode_ptr<NFA> nfa; }; } static -bytecode_ptr<NFA> makeBareSomRevNfa(const NGHolder &g, - const CompileContext &cc) { +bytecode_ptr<NFA> makeBareSomRevNfa(const NGHolder &g, + const CompileContext &cc) { // Create a reversed anchored version of this NFA which fires a zero report // ID on accept. NGHolder g_rev; @@ -1752,14 +1752,14 @@ bytecode_ptr<NFA> makeBareSomRevNfa(const NGHolder &g, setZeroReports(g_rev); // Prep for actual construction. - renumber_vertices(g_rev); + renumber_vertices(g_rev); g_rev.kind = NFA_REV_PREFIX; reduceGraphEquivalences(g_rev, cc); removeRedundancy(g_rev, SOM_NONE); DEBUG_PRINTF("building a rev NFA with %zu vertices\n", num_vertices(g_rev)); - auto nfa = constructReversedNFA(g_rev, cc); + auto nfa = constructReversedNFA(g_rev, cc); if (!nfa) { return nfa; } @@ -1792,9 +1792,9 @@ bool makeSomRevNfa(vector<SomRevNfa> &som_nfas, const NGHolder &g, return true; } - renumber_vertices(g2); // for findMinWidth, findMaxWidth. + renumber_vertices(g2); // for findMinWidth, findMaxWidth. - auto nfa = makeBareSomRevNfa(g2, cc); + auto nfa = makeBareSomRevNfa(g2, cc); if (!nfa) { DEBUG_PRINTF("couldn't build rev nfa\n"); return false; @@ -1856,7 +1856,7 @@ bool doSomRevNfa(NG &ng, NGHolder &g, const CompileContext &cc) { } static -u32 doSomRevNfaPrefix(NG &ng, const ExpressionInfo &expr, NGHolder &g, +u32 doSomRevNfaPrefix(NG &ng, const ExpressionInfo &expr, NGHolder &g, const CompileContext &cc) { depth maxWidth = findMaxWidth(g); @@ -1865,7 +1865,7 @@ u32 doSomRevNfaPrefix(NG &ng, const ExpressionInfo &expr, NGHolder &g, auto nfa = makeBareSomRevNfa(g, cc); if (!nfa) { - throw CompileError(expr.index, "Pattern is too large."); + throw CompileError(expr.index, "Pattern is too large."); } if (ng.cc.streaming) { @@ -1939,7 +1939,7 @@ map<u32, region_info>::const_iterator findLaterLiteral(const NGHolder &g, static bool attemptToBuildChainAfterSombe(SomSlotManager &ssm, NGHolder &g, - const unordered_map<NFAVertex, u32> ®ions, + const unordered_map<NFAVertex, u32> ®ions, const map<u32, region_info> &info, map<u32, region_info>::const_iterator picked, const Grey &grey, @@ -2013,7 +2013,7 @@ void setReportOnHaigPrefix(RoseBuild &rose, NGHolder &h) { static bool tryHaig(RoseBuild &rose, NGHolder &g, - const unordered_map<NFAVertex, u32> ®ions, + const unordered_map<NFAVertex, u32> ®ions, som_type som, u32 somPrecision, map<u32, region_info>::const_iterator picked, shared_ptr<raw_som_dfa> *haig, shared_ptr<NGHolder> *haig_prefix, @@ -2059,9 +2059,9 @@ void roseAddHaigLiteral(RoseBuild &tb, const shared_ptr<NGHolder> &prefix, } static -sombe_rv doHaigLitSom(NG &ng, NGHolder &g, const ExpressionInfo &expr, - u32 comp_id, som_type som, - const unordered_map<NFAVertex, u32> ®ions, +sombe_rv doHaigLitSom(NG &ng, NGHolder &g, const ExpressionInfo &expr, + u32 comp_id, som_type som, + const unordered_map<NFAVertex, u32> ®ions, const map<u32, region_info> &info, map<u32, region_info>::const_iterator lower_bound) { DEBUG_PRINTF("entry\n"); @@ -2070,18 +2070,18 @@ sombe_rv doHaigLitSom(NG &ng, NGHolder &g, const ExpressionInfo &expr, ReportManager &rm = ng.rm; SomSlotManager &ssm = ng.ssm; - if (!cc.grey.allowHaigLit) { + if (!cc.grey.allowHaigLit) { return SOMBE_FAIL; } const u32 numSomLocsBefore = ssm.numSomSlots(); /* for rollback */ u32 som_loc = ssm.getPrivateSomSlot(); - if (!checkViolet(rm, g, false, cc) && !isImplementableNFA(g, &rm, cc)) { + if (!checkViolet(rm, g, false, cc) && !isImplementableNFA(g, &rm, cc)) { // This is an optimisation: if we can't build a Haig from a portion of // the graph, then we won't be able to manage it as an outfix either // when we fall back. - throw CompileError(expr.index, "Pattern is too large."); + throw CompileError(expr.index, "Pattern is too large."); } while (1) { @@ -2156,7 +2156,7 @@ sombe_rv doHaigLitSom(NG &ng, NGHolder &g, const ExpressionInfo &expr, goto next_try; } - implementSomPlan(ng, expr, comp_id, g, plan, som_loc); + implementSomPlan(ng, expr, comp_id, g, plan, som_loc); Report ir = makeCallback(0U, 0); assert(!plan.empty()); @@ -2227,7 +2227,7 @@ bool leadingLiterals(const NGHolder &g, set<ue2_literal> *lits, for (const auto &m : curr) { const NFAVertex u = m.first; const vector<ue2_literal> &base = m.second; - DEBUG_PRINTF("expanding from %zu\n", g[u].index); + DEBUG_PRINTF("expanding from %zu\n", g[u].index); for (auto v : adjacent_vertices_range(u, g)) { if (v == g.startDs) { continue; @@ -2240,7 +2240,7 @@ bool leadingLiterals(const NGHolder &g, set<ue2_literal> *lits, DEBUG_PRINTF("match\n"); goto skip_to_next_terminal; } - if (g[v].char_reach.count() > 2 * MAX_LEADING_LITERALS) { + if (g[v].char_reach.count() > 2 * MAX_LEADING_LITERALS) { DEBUG_PRINTF("wide\n"); goto skip_to_next_terminal; } @@ -2256,8 +2256,8 @@ bool leadingLiterals(const NGHolder &g, set<ue2_literal> *lits, CharReach cr = g[v].char_reach; vector<ue2_literal> &out = next[v]; - DEBUG_PRINTF("expanding to %zu (|| = %zu)\n", g[v].index, - cr.count()); + DEBUG_PRINTF("expanding to %zu (|| = %zu)\n", g[v].index, + cr.count()); for (size_t c = cr.find_first(); c != CharReach::npos; c = cr.find_next(c)) { bool nocase = ourisalpha(c) && cr.test(mytoupper(c)) @@ -2333,7 +2333,7 @@ bool splitOffLeadingLiterals(const NGHolder &g, set<ue2_literal> *lit_out, set<NFAVertex> adj_term1; insert(&adj_term1, adjacent_vertices(*terms.begin(), g)); for (auto v : terms) { - DEBUG_PRINTF("term %zu\n", g[v].index); + DEBUG_PRINTF("term %zu\n", g[v].index); set<NFAVertex> temp; insert(&temp, adjacent_vertices(v, g)); if (temp != adj_term1) { @@ -2342,7 +2342,7 @@ bool splitOffLeadingLiterals(const NGHolder &g, set<ue2_literal> *lit_out, } } - unordered_map<NFAVertex, NFAVertex> rhs_map; + unordered_map<NFAVertex, NFAVertex> rhs_map; vector<NFAVertex> pivots; insert(&pivots, pivots.end(), adj_term1); splitRHS(g, pivots, rhs, &rhs_map); @@ -2353,14 +2353,14 @@ bool splitOffLeadingLiterals(const NGHolder &g, set<ue2_literal> *lit_out, static void findBestLiteral(const NGHolder &g, - const unordered_map<NFAVertex, u32> ®ions, + const unordered_map<NFAVertex, u32> ®ions, ue2_literal *lit_out, NFAVertex *v, const CompileContext &cc) { map<u32, region_info> info; buildRegionMapping(g, regions, info, false); ue2_literal best; - NFAVertex best_v = NGHolder::null_vertex(); + NFAVertex best_v = NGHolder::null_vertex(); map<u32, region_info>::const_iterator lit = info.begin(); while (1) { @@ -2393,10 +2393,10 @@ void findBestLiteral(const NGHolder &g, static bool splitOffBestLiteral(const NGHolder &g, - const unordered_map<NFAVertex, u32> ®ions, + const unordered_map<NFAVertex, u32> ®ions, ue2_literal *lit_out, NGHolder *lhs, NGHolder *rhs, const CompileContext &cc) { - NFAVertex v = NGHolder::null_vertex(); + NFAVertex v = NGHolder::null_vertex(); findBestLiteral(g, regions, lit_out, &v, cc); if (lit_out->empty()) { @@ -2405,43 +2405,43 @@ bool splitOffBestLiteral(const NGHolder &g, DEBUG_PRINTF("literal is '%s'\n", dumpString(*lit_out).c_str()); - unordered_map<NFAVertex, NFAVertex> lhs_map; - unordered_map<NFAVertex, NFAVertex> rhs_map; + unordered_map<NFAVertex, NFAVertex> lhs_map; + unordered_map<NFAVertex, NFAVertex> rhs_map; splitGraph(g, v, lhs, &lhs_map, rhs, &rhs_map); - DEBUG_PRINTF("v = %zu\n", g[v].index); + DEBUG_PRINTF("v = %zu\n", g[v].index); return true; } -/** - * Replace the given graph's EXTERNAL_CALLBACK reports with - * EXTERNAL_CALLBACK_SOM_PASS reports. - */ -void makeReportsSomPass(ReportManager &rm, NGHolder &g) { - for (const auto &v : vertices_range(g)) { - const auto &reports = g[v].reports; - if (reports.empty()) { - continue; - } - - flat_set<ReportID> new_reports; - for (const ReportID &id : reports) { - const Report &report = rm.getReport(id); - if (report.type != EXTERNAL_CALLBACK) { - new_reports.insert(id); - continue; - } - Report report2 = report; - report2.type = EXTERNAL_CALLBACK_SOM_PASS; - new_reports.insert(rm.getInternalId(report2)); - } - - g[v].reports = new_reports; - } -} - +/** + * Replace the given graph's EXTERNAL_CALLBACK reports with + * EXTERNAL_CALLBACK_SOM_PASS reports. + */ +void makeReportsSomPass(ReportManager &rm, NGHolder &g) { + for (const auto &v : vertices_range(g)) { + const auto &reports = g[v].reports; + if (reports.empty()) { + continue; + } + + flat_set<ReportID> new_reports; + for (const ReportID &id : reports) { + const Report &report = rm.getReport(id); + if (report.type != EXTERNAL_CALLBACK) { + new_reports.insert(id); + continue; + } + Report report2 = report; + report2.type = EXTERNAL_CALLBACK_SOM_PASS; + new_reports.insert(rm.getInternalId(report2)); + } + + g[v].reports = new_reports; + } +} + static bool doLitHaigSom(NG &ng, NGHolder &g, som_type som) { ue2_literal lit; @@ -2464,8 +2464,8 @@ bool doLitHaigSom(NG &ng, NGHolder &g, som_type som) { assert(lit.length() <= MAX_MASK2_WIDTH || !mixed_sensitivity(lit)); - makeReportsSomPass(ng.rm, *rhs); - + makeReportsSomPass(ng.rm, *rhs); + dumpHolder(*rhs, 91, "lithaig_rhs", ng.cc.grey); vector<vector<CharReach> > triggers; @@ -2497,7 +2497,7 @@ bool doLitHaigSom(NG &ng, NGHolder &g, som_type som) { static bool doHaigLitHaigSom(NG &ng, NGHolder &g, - const unordered_map<NFAVertex, u32> ®ions, + const unordered_map<NFAVertex, u32> ®ions, som_type som) { if (!ng.cc.grey.allowLitHaig) { return false; @@ -2528,8 +2528,8 @@ bool doHaigLitHaigSom(NG &ng, NGHolder &g, return false; /* TODO: handle */ } - makeReportsSomPass(ng.rm, *rhs); - + makeReportsSomPass(ng.rm, *rhs); + dumpHolder(*lhs, 92, "haiglithaig_lhs", ng.cc.grey); dumpHolder(*rhs, 93, "haiglithaig_rhs", ng.cc.grey); @@ -2541,7 +2541,7 @@ bool doHaigLitHaigSom(NG &ng, NGHolder &g, RoseInVertex v = add_vertex(RoseInVertexProps::makeLiteral(lit), ig); bool lhs_all_vac = true; - NGHolder::adjacency_iterator ai, ae; + NGHolder::adjacency_iterator ai, ae; for (tie(ai, ae) = adjacent_vertices(lhs->startDs, *lhs); ai != ae && lhs_all_vac; ++ai) { if (!is_special(*ai, *lhs)) { @@ -2630,7 +2630,7 @@ bool doHaigLitHaigSom(NG &ng, NGHolder &g, } } else { DEBUG_PRINTF("has start->accept edge\n"); - if (in_degree(g.acceptEod, g) > 1) { + if (in_degree(g.acceptEod, g) > 1) { DEBUG_PRINTF("also has a path to EOD\n"); return false; } @@ -2665,8 +2665,8 @@ bool doMultiLitHaigSom(NG &ng, NGHolder &g, som_type som) { return false; } - makeReportsSomPass(ng.rm, *rhs); - + makeReportsSomPass(ng.rm, *rhs); + dumpHolder(*rhs, 91, "lithaig_rhs", ng.cc.grey); vector<vector<CharReach>> triggers; @@ -2731,7 +2731,7 @@ bool trySombe(NG &ng, NGHolder &g, som_type som) { static map<u32, region_info>::const_iterator pickInitialSomCut(const NGHolder &g, - const unordered_map<NFAVertex, u32> ®ions, + const unordered_map<NFAVertex, u32> ®ions, const map<u32, region_info> &info, const vector<DepthMinMax> &depths) { map<u32, region_info>::const_iterator picked = info.end(); @@ -2756,7 +2756,7 @@ map<u32, region_info>::const_iterator pickInitialSomCut(const NGHolder &g, static map<u32, region_info>::const_iterator tryForLaterRevNfaCut(const NGHolder &g, - const unordered_map<NFAVertex, u32> ®ions, + const unordered_map<NFAVertex, u32> ®ions, const map<u32, region_info> &info, const vector<DepthMinMax> &depths, const map<u32, region_info>::const_iterator &orig, @@ -2831,7 +2831,7 @@ map<u32, region_info>::const_iterator tryForLaterRevNfaCut(const NGHolder &g, reverseHolder(*prefix, g_rev); anchorStarts(g_rev); - renumber_vertices(g_rev); + renumber_vertices(g_rev); g_rev.kind = NFA_REV_PREFIX; reduceGraphEquivalences(g_rev, cc); removeRedundancy(g_rev, SOM_NONE); @@ -2848,7 +2848,7 @@ map<u32, region_info>::const_iterator tryForLaterRevNfaCut(const NGHolder &g, static unique_ptr<NGHolder> makePrefixForChain(NGHolder &g, - const unordered_map<NFAVertex, u32> ®ions, + const unordered_map<NFAVertex, u32> ®ions, const map<u32, region_info> &info, const map<u32, region_info>::const_iterator &picked, vector<DepthMinMax> *depths, bool prefix_by_rev, @@ -2875,13 +2875,13 @@ unique_ptr<NGHolder> makePrefixForChain(NGHolder &g, } depths->clear(); /* renumbering invalidates depths */ - renumber_vertices(*prefix); + renumber_vertices(*prefix); DEBUG_PRINTF("done\n"); return prefix; } -sombe_rv doSom(NG &ng, NGHolder &g, const ExpressionInfo &expr, u32 comp_id, +sombe_rv doSom(NG &ng, NGHolder &g, const ExpressionInfo &expr, u32 comp_id, som_type som) { assert(som); DEBUG_PRINTF("som hello\n"); @@ -2891,7 +2891,7 @@ sombe_rv doSom(NG &ng, NGHolder &g, const ExpressionInfo &expr, u32 comp_id, // Special case: if g is completely anchored or begins with a dot-star, we // know that we have an absolute SOM of zero all the time. - if (!proper_out_degree(g.startDs, g) || beginsWithDotStar(g)) { + if (!proper_out_degree(g.startDs, g) || beginsWithDotStar(g)) { makeSomAbsReports(rm, g, g.accept); makeSomAbsReports(rm, g, g.acceptEod); return SOMBE_HANDLED_INTERNAL; @@ -3005,10 +3005,10 @@ sombe_rv doSom(NG &ng, NGHolder &g, const ExpressionInfo &expr, u32 comp_id, /* create prefix to set the som_loc */ updatePrefixReports(rm, *prefix, INTERNAL_SOM_LOC_SET_IF_UNSET); if (prefix_by_rev) { - u32 rev_comp_id = doSomRevNfaPrefix(ng, expr, *prefix, cc); + u32 rev_comp_id = doSomRevNfaPrefix(ng, expr, *prefix, cc); updatePrefixReportsRevNFA(rm, *prefix, rev_comp_id); } - renumber_vertices(*prefix); + renumber_vertices(*prefix); if (!ng.addHolder(*prefix)) { DEBUG_PRINTF("failed to add holder\n"); clear_graph(g); @@ -3088,18 +3088,18 @@ sombe_rv doSom(NG &ng, NGHolder &g, const ExpressionInfo &expr, u32 comp_id, updatePrefixReports(rm, *prefix, INTERNAL_SOM_LOC_SET); } if (prefix_by_rev && !plan.front().no_implement) { - u32 rev_comp_id = doSomRevNfaPrefix(ng, expr, *prefix, cc); + u32 rev_comp_id = doSomRevNfaPrefix(ng, expr, *prefix, cc); updatePrefixReportsRevNFA(rm, *prefix, rev_comp_id); } - implementSomPlan(ng, expr, comp_id, g, plan, som_loc); + implementSomPlan(ng, expr, comp_id, g, plan, som_loc); DEBUG_PRINTF("success\n"); return SOMBE_HANDLED_INTERNAL; } -sombe_rv doSomWithHaig(NG &ng, NGHolder &g, const ExpressionInfo &expr, - u32 comp_id, som_type som) { +sombe_rv doSomWithHaig(NG &ng, NGHolder &g, const ExpressionInfo &expr, + u32 comp_id, som_type som) { assert(som); DEBUG_PRINTF("som+haig hello\n"); @@ -3136,7 +3136,7 @@ sombe_rv doSomWithHaig(NG &ng, NGHolder &g, const ExpressionInfo &expr, buildRegionMapping(g, regions, info, true); sombe_rv rv = - doHaigLitSom(ng, g, expr, comp_id, som, regions, info, info.begin()); + doHaigLitSom(ng, g, expr, comp_id, som, regions, info, info.begin()); if (rv == SOMBE_FAIL) { clear_graph(g); cloneHolder(g, g_pristine); |