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 | |
66 | using namespace std; |
67 | using boost::adaptors::map_values; |
68 | |
69 | namespace ue2 { |
70 | |
71 | /** Keep attempting to reduce the size of the graph until the number of |
72 | * vertices falls below this value. */ |
73 | static const size_t MAX_COMPONENT_VERTICES = 128; |
74 | |
75 | /** Only replace a region with at least this many vertices. */ |
76 | static 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. */ |
80 | static const size_t BOUNDED_REPEAT_COUNT = 4; |
81 | |
82 | /** Scoring penalty for boundary regions. */ |
83 | static 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. */ |
87 | static const size_t MAX_REPLACE_BOUND = 10000; |
88 | |
89 | namespace { |
90 | |
91 | /** Information describing a region. */ |
92 | struct 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. */ |
114 | struct 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 | |
129 | static |
130 | void findWidths(const NGHolder &g, |
131 | const unordered_map<NFAVertex, u32> ®ion_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. |
157 | static |
158 | void markBoundaryRegions(const NGHolder &h, |
159 | const unordered_map<NFAVertex, u32> ®ion_map, |
160 | map<u32, RegionInfo> ®ions, 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 | |
176 | static |
177 | map<u32, RegionInfo> findRegionInfo(const NGHolder &h, |
178 | const unordered_map<NFAVertex, u32> ®ion_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 | |
216 | static |
217 | void 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 | |
224 | static |
225 | void 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 | |
237 | static |
238 | void 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 | |
252 | static |
253 | void 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 | |
314 | namespace { |
315 | struct 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 | |
324 | static |
325 | void 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 | |
366 | void 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 | |