1/*
2 * Copyright (c) 2015-2017, Intel Corporation
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are met:
6 *
7 * * Redistributions of source code must retain the above copyright notice,
8 * this list of conditions and the following disclaimer.
9 * * Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 * * Neither the name of Intel Corporation nor the names of its contributors
13 * may be used to endorse or promote products derived from this software
14 * without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
17 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
18 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
19 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
20 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
21 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
22 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
23 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
24 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
25 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
26 * POSSIBILITY OF SUCH DAMAGE.
27 */
28
29/**
30 * \file
31 * \brief Prefilter Reductions.
32 *
33 * This file contains routines for reducing the size of an NFA graph that we
34 * know will be used as a prefilter.
35 *
36 * The approach used is to consider the graph as a chain of region subgraphs,
37 * and to reduce the size of the graph by replacing regions with constructs
38 * that can be implemented in fewer states.
39 *
40 * Right now, the approach used is to replace a region with a bounded repeat of
41 * vertices (with bounds derived from the min/max width of the region
42 * subgraph). These vertices are given the union of the region's character
43 * reachability.
44 *
45 * For regions with bounded max width, this strategy is quite dependent on the
46 * LimEx NFA's bounded repeat functionality.
47 */
48#include "ng_prefilter.h"
49
50#include "ng_holder.h"
51#include "ng_region.h"
52#include "ng_util.h"
53#include "ng_width.h"
54#include "ue2common.h"
55#include "util/compile_context.h"
56#include "util/container.h"
57#include "util/dump_charclass.h"
58#include "util/graph_range.h"
59
60#include <queue>
61#include <unordered_map>
62#include <unordered_set>
63
64#include <boost/range/adaptor/map.hpp>
65
66using namespace std;
67using boost::adaptors::map_values;
68
69namespace ue2 {
70
71/** Keep attempting to reduce the size of the graph until the number of
72 * vertices falls below this value. */
73static const size_t MAX_COMPONENT_VERTICES = 128;
74
75/** Only replace a region with at least this many vertices. */
76static const size_t MIN_REPLACE_VERTICES = 2;
77
78/** Estimate of how many vertices are required to represent a bounded repeat in
79 * the implementation NFA. */
80static const size_t BOUNDED_REPEAT_COUNT = 4;
81
82/** Scoring penalty for boundary regions. */
83static const size_t PENALTY_BOUNDARY = 32;
84
85/** Regions with max bounds greater than this value will have their max bound
86 * replaced with inf. */
87static const size_t MAX_REPLACE_BOUND = 10000;
88
89namespace {
90
91/** Information describing a region. */
92struct RegionInfo {
93 explicit RegionInfo(u32 id_in) : id(id_in) {}
94 u32 id; //!< region id
95 deque<NFAVertex> vertices; //!< vertices in the region
96 CharReach reach; //!< union of region reach
97 depth minWidth{0}; //!< min width of region subgraph
98 depth maxWidth{depth::infinity()}; //!< max width of region subgraph
99 bool atBoundary = false; //!< region is next to an accept
100
101 // Bigger score is better.
102 size_t score() const {
103 // TODO: charreach should be a signal?
104 size_t numVertices = vertices.size();
105 if (atBoundary) {
106 return numVertices - min(PENALTY_BOUNDARY, numVertices);
107 } else {
108 return numVertices;
109 }
110 }
111};
112
113/** Comparator used to order regions for consideration in a priority queue. */
114struct RegionInfoQueueComp {
115 bool operator()(const RegionInfo &r1, const RegionInfo &r2) const {
116 size_t score1 = r1.score(), score2 = r2.score();
117 if (score1 != score2) {
118 return score1 < score2;
119 }
120 if (r1.reach.count() != r2.reach.count()) {
121 return r1.reach.count() < r2.reach.count();
122 }
123 return r1.id < r2.id;
124 }
125};
126
127} // namespace
128
129static
130void findWidths(const NGHolder &g,
131 const unordered_map<NFAVertex, u32> &region_map,
132 RegionInfo &ri) {
133 NGHolder rg;
134 unordered_map<NFAVertex, NFAVertex> mapping;
135 fillHolder(&rg, g, ri.vertices, &mapping);
136
137 // Wire our entries to start and our exits to accept.
138 for (auto v : ri.vertices) {
139 NFAVertex v_new = mapping[v];
140 assert(v_new != NGHolder::null_vertex());
141
142 if (isRegionEntry(g, v, region_map) &&
143 !edge(rg.start, v_new, rg).second) {
144 add_edge(rg.start, v_new, rg);
145 }
146 if (isRegionExit(g, v, region_map) &&
147 !edge(v_new, rg.accept, rg).second) {
148 add_edge(v_new, rg.accept, rg);
149 }
150 }
151
152 ri.minWidth = findMinWidth(rg);
153 ri.maxWidth = findMaxWidth(rg);
154}
155
156// acc can be either h.accept or h.acceptEod.
157static
158void markBoundaryRegions(const NGHolder &h,
159 const unordered_map<NFAVertex, u32> &region_map,
160 map<u32, RegionInfo> &regions, NFAVertex acc) {
161 for (auto v : inv_adjacent_vertices_range(acc, h)) {
162 if (is_special(v, h)) {
163 continue;
164 }
165 u32 id = region_map.at(v);
166
167 auto ri = regions.find(id);
168 if (ri == regions.end()) {
169 continue; // Not tracking this region as it's too small.
170 }
171
172 ri->second.atBoundary = true;
173 }
174}
175
176static
177map<u32, RegionInfo> findRegionInfo(const NGHolder &h,
178 const unordered_map<NFAVertex, u32> &region_map) {
179 map<u32, RegionInfo> regions;
180 for (auto v : vertices_range(h)) {
181 if (is_special(v, h)) {
182 continue;
183 }
184 u32 id = region_map.at(v);
185 RegionInfo &ri = regions.emplace(id, RegionInfo(id)).first->second;
186 ri.vertices.push_back(v);
187 ri.reach |= h[v].char_reach;
188 }
189
190 // There's no point tracking more information about regions that we won't
191 // consider replacing, so we remove them from the region map.
192 for (auto it = regions.begin(); it != regions.end();) {
193 if (it->second.vertices.size() < MIN_REPLACE_VERTICES) {
194 regions.erase(it++);
195 } else {
196 ++it;
197 }
198 }
199
200 DEBUG_PRINTF("%zu regions\n", regions.size());
201
202 markBoundaryRegions(h, region_map, regions, h.accept);
203 markBoundaryRegions(h, region_map, regions, h.acceptEod);
204
205 // Determine min/max widths.
206 for (RegionInfo &ri : regions | map_values) {
207 findWidths(h, region_map, ri);
208 DEBUG_PRINTF("region %u %shas widths [%s,%s]\n", ri.id,
209 ri.atBoundary ? "(boundary) " : "",
210 ri.minWidth.str().c_str(), ri.maxWidth.str().c_str());
211 }
212
213 return regions;
214}
215
216static
217void copyInEdges(NGHolder &g, NFAVertex from, NFAVertex to) {
218 for (const auto &e : in_edges_range(from, g)) {
219 NFAVertex u = source(e, g);
220 add_edge_if_not_present(u, to, g[e], g);
221 }
222}
223
224static
225void copyOutEdges(NGHolder &g, NFAVertex from, NFAVertex to) {
226 for (const auto &e : out_edges_range(from, g)) {
227 NFAVertex t = target(e, g);
228 add_edge_if_not_present(to, t, g[e], g);
229
230 if (is_any_accept(t, g)) {
231 const auto &reports = g[from].reports;
232 g[to].reports.insert(reports.begin(), reports.end());
233 }
234 }
235}
236
237static
238void removeInteriorEdges(NGHolder &g, const RegionInfo &ri) {
239 // Set of vertices in region, for quick lookups.
240 const unordered_set<NFAVertex> rverts(ri.vertices.begin(),
241 ri.vertices.end());
242
243 auto is_interior_in_edge = [&](const NFAEdge &e) {
244 return contains(rverts, source(e, g));
245 };
246
247 for (auto v : ri.vertices) {
248 remove_in_edge_if(v, is_interior_in_edge, g);
249 }
250}
251
252static
253void replaceRegion(NGHolder &g, const RegionInfo &ri,
254 size_t *verticesAdded, size_t *verticesRemoved) {
255 // TODO: more complex replacements.
256 assert(ri.vertices.size() >= MIN_REPLACE_VERTICES);
257 assert(ri.minWidth.is_finite());
258
259 depth minWidth = ri.minWidth;
260 depth maxWidth = ri.maxWidth;
261
262 if (maxWidth > depth(MAX_REPLACE_BOUND)) {
263 DEBUG_PRINTF("using inf instead of large bound %s\n",
264 maxWidth.str().c_str());
265 maxWidth = depth::infinity();
266 }
267
268 size_t replacementSize;
269 if (minWidth == maxWidth || maxWidth.is_infinite()) {
270 replacementSize = minWidth; // {N} or {N,}
271 } else {
272 replacementSize = maxWidth; // {N,M} case
273 }
274
275 DEBUG_PRINTF("orig size %zu, replace size %zu\n", ri.vertices.size(),
276 replacementSize);
277
278 vector<NFAVertex> verts;
279 verts.reserve(replacementSize);
280 for (size_t i = 0; i < replacementSize; i++) {
281 NFAVertex v = add_vertex(g);
282 g[v].char_reach = ri.reach;
283 if (i > 0) {
284 add_edge(verts.back(), v, g);
285 }
286 verts.push_back(v);
287 }
288
289 if (maxWidth.is_infinite()) {
290 add_edge(verts.back(), verts.back(), g);
291 }
292
293 removeInteriorEdges(g, ri);
294
295 for (size_t i = 0; i < replacementSize; i++) {
296 NFAVertex v_new = verts[i];
297
298 for (auto v_old : ri.vertices) {
299 if (i == 0) {
300 copyInEdges(g, v_old, v_new);
301 }
302 if (i + 1 >= ri.minWidth) {
303 copyOutEdges(g, v_old, v_new);
304 }
305 }
306 }
307
308 remove_vertices(ri.vertices, g, false);
309
310 *verticesAdded = verts.size();
311 *verticesRemoved = ri.vertices.size();
312}
313
314namespace {
315struct SourceHasEdgeToAccept {
316 explicit SourceHasEdgeToAccept(const NGHolder &g_in) : g(g_in) {}
317 bool operator()(const NFAEdge &e) const {
318 return edge(source(e, g), g.accept, g).second;
319 }
320 const NGHolder &g;
321};
322}
323
324static
325void reduceRegions(NGHolder &h) {
326 map<u32, RegionInfo> regions = findRegionInfo(h, assignRegions(h));
327
328 RegionInfoQueueComp cmp;
329 priority_queue<RegionInfo, deque<RegionInfo>, RegionInfoQueueComp> pq(cmp);
330
331 size_t numVertices = 0;
332 for (const RegionInfo &ri : regions | map_values) {
333 numVertices += ri.vertices.size();
334 pq.push(ri);
335 }
336
337 while (numVertices > MAX_COMPONENT_VERTICES && !pq.empty()) {
338 const RegionInfo &ri = pq.top();
339 DEBUG_PRINTF("region %u: vertices=%zu reach=%s score=%zu, "
340 "widths=[%s,%s]\n",
341 ri.id, ri.vertices.size(), describeClass(ri.reach).c_str(),
342 ri.score(), ri.minWidth.str().c_str(),
343 ri.maxWidth.str().c_str());
344
345 size_t verticesAdded = 0;
346 size_t verticesRemoved = 0;
347 replaceRegion(h, ri, &verticesAdded, &verticesRemoved);
348 DEBUG_PRINTF("%zu vertices removed, %zu vertices added\n",
349 verticesRemoved, verticesAdded);
350
351 // We are trusting that implementation NFAs will be able to use the
352 // LimEx bounded repeat code here.
353 numVertices -= verticesRemoved;
354 numVertices += BOUNDED_REPEAT_COUNT;
355
356 DEBUG_PRINTF("numVertices is now %zu\n", numVertices);
357 pq.pop();
358 }
359
360 // We may have vertices that have edges to both accept and acceptEod: in
361 // this case, we can optimize for performance by removing the acceptEod
362 // edges.
363 remove_in_edge_if(h.acceptEod, SourceHasEdgeToAccept(h), h);
364}
365
366void prefilterReductions(NGHolder &h, const CompileContext &cc) {
367 if (!cc.grey.prefilterReductions) {
368 return;
369 }
370
371 if (num_vertices(h) <= MAX_COMPONENT_VERTICES) {
372 DEBUG_PRINTF("graph is already small enough (%zu vertices)\n",
373 num_vertices(h));
374 return;
375 }
376
377 DEBUG_PRINTF("before: graph with %zu vertices, %zu edges\n",
378 num_vertices(h), num_edges(h));
379
380 renumber_vertices(h);
381 renumber_edges(h);
382
383 reduceRegions(h);
384
385 renumber_vertices(h);
386 renumber_edges(h);
387
388 DEBUG_PRINTF("after: graph with %zu vertices, %zu edges\n",
389 num_vertices(h), num_edges(h));
390
391}
392
393} // namespace ue2
394