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 | /** \file |
30 | * \brief Miscellaneous optimisations. |
31 | * |
32 | * We sometimes see patterns of the form: |
33 | * |
34 | * /^.*<[^<]*foobaz/s |
35 | * |
36 | * This is bad for Rose as the escapes from the cyclic state are the same as |
37 | * the trigger. However, we can transform this into: |
38 | * |
39 | * /^.*<.*foobaz/s |
40 | * |
41 | * ... as the first dot star can eat all but the last '<'. |
42 | * |
43 | * Slightly more formally: |
44 | * |
45 | * Given a cyclic state v with character reachability v_cr and proper preds |
46 | * {p1 .. pn} with character reachability {p1_cr .. pn_cr}. |
47 | * |
48 | * let v_cr' = union(intersection(p1_cr .. pn_cr), v_cr) |
49 | * |
50 | * v_cr can be replaced with v_cr' without changing the behaviour of the system |
51 | * if: |
52 | * |
53 | * for any given proper pred pi: if pi is set in the nfa then after consuming |
54 | * any symbol in v_cr', pi will still be set in the nfa and every successor of |
55 | * v is a successor of pi. |
56 | * |
57 | * The easiest way for this condition to be satisfied is for each proper pred |
58 | * pi to have all its preds all have an edge to a pred of pi with a character |
59 | * reachability containing v_cr'. There are, however, other ways to establish |
60 | * the condition holds. |
61 | * |
62 | * Note: a similar transformation can be applied in reverse, details left as an |
63 | * exercise for the interested reader. */ |
64 | #include "ng_misc_opt.h" |
65 | |
66 | #include "ng_holder.h" |
67 | #include "ng_prune.h" |
68 | #include "ng_util.h" |
69 | #include "util/charreach.h" |
70 | #include "util/container.h" |
71 | #include "util/graph_range.h" |
72 | #include "util/graph_small_color_map.h" |
73 | #include "util/flat_containers.h" |
74 | #include "ue2common.h" |
75 | |
76 | #include <boost/dynamic_bitset.hpp> |
77 | #include <boost/graph/depth_first_search.hpp> |
78 | #include <boost/graph/filtered_graph.hpp> |
79 | |
80 | #include <map> |
81 | #include <set> |
82 | #include <vector> |
83 | |
84 | using namespace std; |
85 | using boost::make_filtered_graph; |
86 | |
87 | namespace ue2 { |
88 | |
89 | static |
90 | void findCandidates(NGHolder &g, const vector<NFAVertex> &ordering, |
91 | vector<NFAVertex> *cand) { |
92 | for (auto it = ordering.rbegin(), ite = ordering.rend(); it != ite; ++it) { |
93 | NFAVertex v = *it; |
94 | |
95 | if (is_special(v, g) |
96 | || !hasSelfLoop(v, g) |
97 | || g[v].char_reach.all()) { |
98 | continue; |
99 | } |
100 | |
101 | // For `v' to be a candidate, its predecessors must all have the same |
102 | // successor set as `v'. |
103 | |
104 | auto succ_v = succs(v, g); |
105 | flat_set<NFAVertex> succ_u; |
106 | |
107 | for (auto u : inv_adjacent_vertices_range(v, g)) { |
108 | succ_u.clear(); |
109 | succ(g, u, &succ_u); |
110 | if (succ_v != succ_u) { |
111 | goto next_cand; |
112 | } |
113 | } |
114 | DEBUG_PRINTF("vertex %zu is a candidate\n" , g[v].index); |
115 | cand->push_back(v); |
116 | next_cand:; |
117 | } |
118 | } |
119 | |
120 | static |
121 | void findCandidates_rev(NGHolder &g, const vector<NFAVertex> &ordering, |
122 | vector<NFAVertex> *cand) { |
123 | for (auto it = ordering.begin(), ite = ordering.end(); it != ite; ++it) { |
124 | NFAVertex v = *it; |
125 | |
126 | if (is_special(v, g) |
127 | || !hasSelfLoop(v, g) |
128 | || g[v].char_reach.all()) { |
129 | continue; |
130 | } |
131 | |
132 | // For `v' to be a candidate, its predecessors must all have the same |
133 | // successor set as `v'. |
134 | |
135 | auto pred_v = preds(v, g); |
136 | flat_set<NFAVertex> pred_u; |
137 | |
138 | for (auto u : adjacent_vertices_range(v, g)) { |
139 | pred_u.clear(); |
140 | pred(g, u, &pred_u); |
141 | if (pred_v != pred_u) { |
142 | goto next_cand; |
143 | } |
144 | } |
145 | DEBUG_PRINTF("vertex %zu is a candidate\n" , g[v].index); |
146 | cand->push_back(v); |
147 | next_cand:; |
148 | } |
149 | } |
150 | |
151 | /** Find the intersection of the reachability of the predecessors of \p v. */ |
152 | static |
153 | void predCRIntersection(const NGHolder &g, NFAVertex v, CharReach &add) { |
154 | add.setall(); |
155 | for (auto u : inv_adjacent_vertices_range(v, g)) { |
156 | if (u != v) { |
157 | add &= g[u].char_reach; |
158 | } |
159 | } |
160 | } |
161 | |
162 | /** Find the intersection of the reachability of the successors of \p v. */ |
163 | static |
164 | void succCRIntersection(const NGHolder &g, NFAVertex v, CharReach &add) { |
165 | add.setall(); |
166 | for (auto u : adjacent_vertices_range(v, g)) { |
167 | if (u != v) { |
168 | add &= g[u].char_reach; |
169 | } |
170 | } |
171 | } |
172 | |
173 | /** The sustain set is used to show that once vertex p is on it stays on given |
174 | * the alphabet new_cr. Every vertex pp in the sustain set has the following |
175 | * properties: |
176 | * -# an edge to p |
177 | * -# enough edges to vertices in the sustain set to ensure that a vertex in |
178 | * the sustain set will be on after consuming a character. */ |
179 | static |
180 | set<NFAVertex> findSustainSet(const NGHolder &g, NFAVertex p, |
181 | bool ignore_starts, const CharReach &new_cr) { |
182 | auto cand = preds<set<NFAVertex>>(p, g); |
183 | if (ignore_starts) { |
184 | cand.erase(g.startDs); |
185 | } |
186 | /* remove elements from cand until the sustain set property holds */ |
187 | bool changed; |
188 | do { |
189 | DEBUG_PRINTF("|cand| %zu\n" , cand.size()); |
190 | changed = false; |
191 | set<NFAVertex>::const_iterator it = cand.begin(); |
192 | while (it != cand.end()) { |
193 | NFAVertex u = *it; |
194 | ++it; |
195 | CharReach sus_cr; |
196 | for (auto v : adjacent_vertices_range(u, g)) { |
197 | if (contains(cand, v)) { |
198 | sus_cr |= g[v].char_reach; |
199 | } |
200 | } |
201 | |
202 | if (!new_cr.isSubsetOf(sus_cr)) { |
203 | cand.erase(u); |
204 | changed = true; |
205 | } |
206 | } |
207 | } while (changed); |
208 | |
209 | /* Note: it may be possible to find a (larger) sustain set for a smaller |
210 | * new_cr */ |
211 | return cand; |
212 | } |
213 | |
214 | /** Finds the reverse version of the sustain set.. whatever that means. */ |
215 | static |
216 | set<NFAVertex> findSustainSet_rev(const NGHolder &g, NFAVertex p, |
217 | const CharReach &new_cr) { |
218 | auto cand = succs<set<NFAVertex>>(p, g); |
219 | /* remove elements from cand until the sustain set property holds */ |
220 | bool changed; |
221 | do { |
222 | changed = false; |
223 | set<NFAVertex>::const_iterator it = cand.begin(); |
224 | while (it != cand.end()) { |
225 | NFAVertex u = *it; |
226 | ++it; |
227 | CharReach sus_cr; |
228 | for (auto v : inv_adjacent_vertices_range(u, g)) { |
229 | if (contains(cand, v)) { |
230 | sus_cr |= g[v].char_reach; |
231 | } |
232 | } |
233 | |
234 | if (!new_cr.isSubsetOf(sus_cr)) { |
235 | cand.erase(u); |
236 | changed = true; |
237 | } |
238 | } |
239 | } while (changed); |
240 | |
241 | /* Note: it may be possible to find a (larger) sustain set for a smaller |
242 | * new_cr */ |
243 | return cand; |
244 | } |
245 | |
246 | static |
247 | bool enlargeCyclicVertex(NGHolder &g, som_type som, NFAVertex v) { |
248 | DEBUG_PRINTF("considering vertex %zu\n" , g[v].index); |
249 | const CharReach &v_cr = g[v].char_reach; |
250 | |
251 | CharReach add; |
252 | predCRIntersection(g, v, add); |
253 | |
254 | add |= v_cr; |
255 | |
256 | if (add == v_cr) { |
257 | DEBUG_PRINTF("no benefit\n" ); |
258 | return false; |
259 | } |
260 | |
261 | DEBUG_PRINTF("cr of width %zu up for grabs\n" , add.count() - v_cr.count()); |
262 | |
263 | for (auto p : inv_adjacent_vertices_range(v, g)) { |
264 | if (p == v) { |
265 | continue; |
266 | } |
267 | DEBUG_PRINTF("looking at pred %zu\n" , g[p].index); |
268 | |
269 | bool ignore_sds = som; /* if we are tracking som, entries into a state |
270 | from sds are significant. */ |
271 | |
272 | set<NFAVertex> sustain = findSustainSet(g, p, ignore_sds, add); |
273 | DEBUG_PRINTF("sustain set is %zu\n" , sustain.size()); |
274 | if (sustain.empty()) { |
275 | DEBUG_PRINTF("yawn\n" ); |
276 | } |
277 | |
278 | for (auto pp : inv_adjacent_vertices_range(p, g)) { |
279 | /* we need to ensure that whenever pp sets p, that a member of the |
280 | sustain set is set. Note: p's cr may be not be a subset of |
281 | new_cr */ |
282 | CharReach sustain_cr; |
283 | for (auto pv : adjacent_vertices_range(pp, g)) { |
284 | if (contains(sustain, pv)) { |
285 | sustain_cr |= g[pv].char_reach; |
286 | } |
287 | } |
288 | if (!g[p].char_reach.isSubsetOf(sustain_cr)) { |
289 | DEBUG_PRINTF("unable to establish that preds are forced on\n" ); |
290 | return false; |
291 | } |
292 | } |
293 | } |
294 | |
295 | /* the cr can be increased */ |
296 | g[v].char_reach = add; |
297 | DEBUG_PRINTF("vertex %zu was widened\n" , g[v].index); |
298 | return true; |
299 | } |
300 | |
301 | static |
302 | bool enlargeCyclicVertex_rev(NGHolder &g, NFAVertex v) { |
303 | DEBUG_PRINTF("considering vertex %zu\n" , g[v].index); |
304 | const CharReach &v_cr = g[v].char_reach; |
305 | |
306 | CharReach add; |
307 | succCRIntersection(g, v, add); |
308 | |
309 | add |= v_cr; |
310 | |
311 | if (add == v_cr) { |
312 | DEBUG_PRINTF("no benefit\n" ); |
313 | return false; |
314 | } |
315 | |
316 | DEBUG_PRINTF("cr of width %zu up for grabs\n" , add.count() - v_cr.count()); |
317 | |
318 | for (auto p : adjacent_vertices_range(v, g)) { |
319 | if (p == v) { |
320 | continue; |
321 | } |
322 | DEBUG_PRINTF("looking at succ %zu\n" , g[p].index); |
323 | |
324 | set<NFAVertex> sustain = findSustainSet_rev(g, p, add); |
325 | DEBUG_PRINTF("sustain set is %zu\n" , sustain.size()); |
326 | if (sustain.empty()) { |
327 | DEBUG_PRINTF("yawn\n" ); |
328 | } |
329 | |
330 | for (auto pp : adjacent_vertices_range(p, g)) { |
331 | /* we need to ensure something - see fwd ver */ |
332 | CharReach sustain_cr; |
333 | for (auto pv : inv_adjacent_vertices_range(pp, g)) { |
334 | if (contains(sustain, pv)) { |
335 | sustain_cr |= g[pv].char_reach; |
336 | } |
337 | } |
338 | if (!g[p].char_reach.isSubsetOf(sustain_cr)) { |
339 | DEBUG_PRINTF("unable to establish that succs are thingy\n" ); |
340 | return false; |
341 | } |
342 | } |
343 | } |
344 | |
345 | /* the cr can be increased */ |
346 | g[v].char_reach = add; |
347 | DEBUG_PRINTF("vertex %zu was widened\n" , g[v].index); |
348 | return true; |
349 | } |
350 | |
351 | static |
352 | bool enlargeCyclicCR(NGHolder &g, som_type som, |
353 | const vector<NFAVertex> &ordering) { |
354 | DEBUG_PRINTF("hello\n" ); |
355 | |
356 | vector<NFAVertex> candidates; |
357 | findCandidates(g, ordering, &candidates); |
358 | |
359 | bool rv = false; |
360 | for (auto v : candidates) { |
361 | rv |= enlargeCyclicVertex(g, som, v); |
362 | } |
363 | |
364 | return rv; |
365 | } |
366 | |
367 | static |
368 | bool enlargeCyclicCR_rev(NGHolder &g, const vector<NFAVertex> &ordering) { |
369 | DEBUG_PRINTF("olleh\n" ); |
370 | |
371 | vector<NFAVertex> candidates; |
372 | findCandidates_rev(g, ordering, &candidates); |
373 | |
374 | bool rv = false; |
375 | for (auto v : candidates) { |
376 | rv |= enlargeCyclicVertex_rev(g, v); |
377 | } |
378 | |
379 | return rv; |
380 | } |
381 | |
382 | bool improveGraph(NGHolder &g, som_type som) { |
383 | /* use a topo ordering so that we can get chains of cyclic states |
384 | * done in one sweep */ |
385 | |
386 | const vector<NFAVertex> ordering = getTopoOrdering(g); |
387 | |
388 | return enlargeCyclicCR(g, som, ordering) |
389 | | enlargeCyclicCR_rev(g, ordering); |
390 | } |
391 | |
392 | /** finds a smaller reachability for a state by the reverse transformation of |
393 | * enlargeCyclicCR. */ |
394 | CharReach reduced_cr(NFAVertex v, const NGHolder &g, |
395 | const map<NFAVertex, BoundedRepeatSummary> &br_cyclic) { |
396 | DEBUG_PRINTF("find minimal cr for %zu\n" , g[v].index); |
397 | CharReach v_cr = g[v].char_reach; |
398 | if (proper_in_degree(v, g) != 1) { |
399 | return v_cr; |
400 | } |
401 | |
402 | NFAVertex pred = getSoleSourceVertex(g, v); |
403 | assert(pred); |
404 | |
405 | /* require pred to be fed by one vertex OR (start + startDS) */ |
406 | NFAVertex predpred; |
407 | size_t idp = in_degree(pred, g); |
408 | if (hasSelfLoop(pred, g)) { |
409 | return v_cr; /* not cliche */ |
410 | } else if (idp == 1) { |
411 | predpred = getSoleSourceVertex(g, pred); |
412 | } else if (idp == 2 |
413 | && edge(g.start, pred, g).second |
414 | && edge(g.startDs, pred, g).second) { |
415 | predpred = g.startDs; |
416 | } else { |
417 | return v_cr; /* not cliche */ |
418 | } |
419 | |
420 | assert(predpred); |
421 | |
422 | /* require predpred to be cyclic and its cr to be a superset of |
423 | pred and v */ |
424 | if (!hasSelfLoop(predpred, g)) { |
425 | return v_cr; /* not cliche */ |
426 | } |
427 | |
428 | if (contains(br_cyclic, predpred) |
429 | && !br_cyclic.at(predpred).unbounded()) { |
430 | return v_cr; /* fake cyclic */ |
431 | } |
432 | |
433 | const CharReach &p_cr = g[pred].char_reach; |
434 | const CharReach &pp_cr = g[predpred].char_reach; |
435 | if (!v_cr.isSubsetOf(pp_cr) || !p_cr.isSubsetOf(pp_cr)) { |
436 | return v_cr; /* not cliche */ |
437 | } |
438 | |
439 | DEBUG_PRINTF("confirming [x]* prop\n" ); |
440 | /* we require all of v succs to be succ of p */ |
441 | set<NFAVertex> v_succ; |
442 | insert(&v_succ, adjacent_vertices(v, g)); |
443 | set<NFAVertex> p_succ; |
444 | insert(&p_succ, adjacent_vertices(pred, g)); |
445 | |
446 | if (!is_subset_of(v_succ, p_succ)) { |
447 | DEBUG_PRINTF("fail\n" ); |
448 | return v_cr; /* not cliche */ |
449 | } |
450 | |
451 | if (contains(v_succ, g.accept) || contains(v_succ, g.acceptEod)) { |
452 | /* need to check that reports of v are a subset of p's */ |
453 | if (!is_subset_of(g[v].reports, |
454 | g[pred].reports)) { |
455 | DEBUG_PRINTF("fail - reports not subset\n" ); |
456 | return v_cr; /* not cliche */ |
457 | } |
458 | } |
459 | |
460 | DEBUG_PRINTF("woot success\n" ); |
461 | v_cr &= ~p_cr; |
462 | return v_cr; |
463 | } |
464 | |
465 | vector<CharReach> reduced_cr(const NGHolder &g, |
466 | const map<NFAVertex, BoundedRepeatSummary> &br_cyclic) { |
467 | assert(hasCorrectlyNumberedVertices(g)); |
468 | vector<CharReach> refined_cr(num_vertices(g), CharReach()); |
469 | |
470 | for (auto v : vertices_range(g)) { |
471 | u32 v_idx = g[v].index; |
472 | refined_cr[v_idx] = reduced_cr(v, g, br_cyclic); |
473 | } |
474 | |
475 | return refined_cr; |
476 | } |
477 | |
478 | static |
479 | bool anyOutSpecial(NFAVertex v, const NGHolder &g) { |
480 | for (auto w : adjacent_vertices_range(v, g)) { |
481 | if (is_special(w, g) && w != v) { |
482 | return true; |
483 | } |
484 | } |
485 | return false; |
486 | } |
487 | |
488 | bool mergeCyclicDotStars(NGHolder &g) { |
489 | set<NFAVertex> verticesToRemove; |
490 | set<NFAEdge> edgesToRemove; |
491 | |
492 | // avoid graphs where startDs is not a free spirit |
493 | if (out_degree(g.startDs, g) > 1) { |
494 | return false; |
495 | } |
496 | |
497 | // check if any of the connected vertices are dots |
498 | for (auto v : adjacent_vertices_range(g.start, g)) { |
499 | if (is_special(v, g)) { |
500 | continue; |
501 | } |
502 | const CharReach &cr = g[v].char_reach; |
503 | |
504 | // if this is a cyclic dot |
505 | if (cr.all() && edge(v, v, g).second) { |
506 | // prevent insane graphs |
507 | if (anyOutSpecial(v, g)) { |
508 | continue; |
509 | } |
510 | // we don't know if we're going to remove this vertex yet |
511 | vector<NFAEdge> deadEdges; |
512 | |
513 | // check if all adjacent vertices have edges from start |
514 | for (const auto &e : out_edges_range(v, g)) { |
515 | NFAVertex t = target(e, g); |
516 | // skip self |
517 | if (t == v) { |
518 | continue; |
519 | } |
520 | // skip vertices that don't have edges from start |
521 | if (!edge(g.start, t, g).second) { |
522 | continue; |
523 | } |
524 | // add an edge from startDs to this vertex |
525 | add_edge_if_not_present(g.startDs, t, g); |
526 | |
527 | // mark this edge for removal |
528 | deadEdges.push_back(e); |
529 | } |
530 | // if the number of edges to be removed equals out degree, vertex |
531 | // needs to be removed; else, only remove the edges |
532 | if (deadEdges.size() == proper_out_degree(v, g)) { |
533 | verticesToRemove.insert(v); |
534 | } else { |
535 | edgesToRemove.insert(deadEdges.begin(), deadEdges.end()); |
536 | } |
537 | } |
538 | } |
539 | |
540 | if (verticesToRemove.empty() && edgesToRemove.empty()) { |
541 | return false; |
542 | } |
543 | |
544 | DEBUG_PRINTF("removing %zu edges and %zu vertices\n" , edgesToRemove.size(), |
545 | verticesToRemove.size()); |
546 | remove_edges(edgesToRemove, g); |
547 | remove_vertices(verticesToRemove, g); |
548 | /* some predecessors to the cyclic vertices may no longer be useful (no out |
549 | * edges), so we can remove them */ |
550 | pruneUseless(g); |
551 | return true; |
552 | } |
553 | |
554 | struct PrunePathsInfo { |
555 | explicit PrunePathsInfo(const NGHolder &g) |
556 | : color_map(make_small_color_map(g)), bad(num_vertices(g)) {} |
557 | |
558 | void clear() { |
559 | no_explore.clear(); |
560 | color_map.fill(small_color::white); |
561 | bad.reset(); |
562 | } |
563 | |
564 | flat_set<NFAEdge> no_explore; |
565 | using color_map_type = decltype(make_small_color_map(NGHolder())); |
566 | color_map_type color_map; |
567 | boost::dynamic_bitset<> bad; |
568 | }; |
569 | |
570 | /** |
571 | * Finds the set of vertices that cannot be on if v is not on, setting their |
572 | * indices in bitset PrunePathsInfo::bad. |
573 | */ |
574 | static |
575 | void findDependentVertices(const NGHolder &g, PrunePathsInfo &info, |
576 | NFAVertex v) { |
577 | /* We need to exclude any vertex that may be reached on a path which is |
578 | * incompatible with the vertex v being on. */ |
579 | |
580 | /* A vertex u is bad if: |
581 | * 1) its reach may be incompatible with v (not a subset) |
582 | * 2) it if there is an edge from a bad vertex b and there is either not an |
583 | * edge v->u or not an edge b->v. |
584 | * Note: 2) means v is never bad as it has a selfloop |
585 | * |
586 | * Can do this with a DFS from all the initial bad states with a conditional |
587 | * check down edges. Alternately can just filter these edges out of the |
588 | * graph first. |
589 | */ |
590 | for (NFAVertex t : adjacent_vertices_range(v, g)) { |
591 | for (NFAEdge e : in_edges_range(t, g)) { |
592 | NFAVertex s = source(e, g); |
593 | if (edge(s, v, g).second) { |
594 | info.no_explore.insert(e); |
595 | } |
596 | } |
597 | } |
598 | |
599 | auto filtered_g = |
600 | make_filtered_graph(g, make_bad_edge_filter(&info.no_explore)); |
601 | |
602 | // We use a bitset to track bad vertices, rather than filling a (potentially |
603 | // very large) set structure. |
604 | auto recorder = make_vertex_index_bitset_recorder(info.bad); |
605 | |
606 | for (NFAVertex b : vertices_range(g)) { |
607 | if (b != g.start && g[b].char_reach.isSubsetOf(g[v].char_reach)) { |
608 | continue; |
609 | } |
610 | boost::depth_first_visit(filtered_g, b, recorder, info.color_map); |
611 | } |
612 | } |
613 | |
614 | static |
615 | bool willBeEnabledConcurrently(NFAVertex main_cyclic, NFAVertex v, |
616 | const NGHolder &g) { |
617 | return is_subset_of(preds(main_cyclic, g), preds(v, g)); |
618 | } |
619 | |
620 | static |
621 | bool sometimesEnabledConcurrently(NFAVertex main_cyclic, NFAVertex v, |
622 | const NGHolder &g) { |
623 | return has_intersection(preds(main_cyclic, g), preds(v, g)); |
624 | } |
625 | |
626 | static |
627 | bool pruneUsingSuccessors(NGHolder &g, PrunePathsInfo &info, NFAVertex u, |
628 | som_type som) { |
629 | if (som && (is_virtual_start(u, g) || u == g.startDs)) { |
630 | return false; |
631 | } |
632 | |
633 | bool changed = false; |
634 | DEBUG_PRINTF("using cyclic %zu as base\n" , g[u].index); |
635 | info.clear(); |
636 | findDependentVertices(g, info, u); |
637 | vector<NFAVertex> u_succs; |
638 | for (NFAVertex v : adjacent_vertices_range(u, g)) { |
639 | if (som && is_virtual_start(v, g)) { |
640 | /* as v is virtual start, its som has been reset so can not override |
641 | * existing in progress matches. */ |
642 | continue; |
643 | } |
644 | u_succs.push_back(v); |
645 | } |
646 | |
647 | stable_sort(u_succs.begin(), u_succs.end(), |
648 | [&](NFAVertex a, NFAVertex b) { |
649 | return g[a].char_reach.count() > g[b].char_reach.count(); |
650 | }); |
651 | |
652 | flat_set<NFAEdge> dead; |
653 | |
654 | for (NFAVertex v : u_succs) { |
655 | DEBUG_PRINTF(" using %zu as killer\n" , g[v].index); |
656 | /* Need to distinguish between vertices that are switched on after the |
657 | * cyclic vs vertices that are switched on concurrently with the cyclic |
658 | * if (subject to a suitable reach) */ |
659 | bool v_peer_of_cyclic = willBeEnabledConcurrently(u, v, g); |
660 | for (NFAVertex s : adjacent_vertices_range(v, g)) { |
661 | DEBUG_PRINTF(" looking at preds of %zu\n" , g[s].index); |
662 | for (NFAEdge e : in_edges_range(s, g)) { |
663 | NFAVertex p = source(e, g); |
664 | if (info.bad.test(g[p].index) || p == v || p == u |
665 | || p == g.accept) { |
666 | DEBUG_PRINTF("%zu not a cand\n" , g[p].index); |
667 | continue; |
668 | } |
669 | if (is_any_accept(s, g) && g[p].reports != g[v].reports) { |
670 | DEBUG_PRINTF("%zu bad reports\n" , g[p].index); |
671 | continue; |
672 | } |
673 | /* the out-edges of a vertex that may be enabled on the same |
674 | * byte as the cyclic can only be killed by the out-edges of a |
675 | * peer vertex which will be enabled with the cyclic (a non-peer |
676 | * may not be switched on until another byte is processed). */ |
677 | if (!v_peer_of_cyclic |
678 | && sometimesEnabledConcurrently(u, p, g)) { |
679 | DEBUG_PRINTF("%zu can only be squashed by a proper peer\n" , |
680 | g[p].index); |
681 | continue; |
682 | } |
683 | |
684 | if (g[p].char_reach.isSubsetOf(g[v].char_reach)) { |
685 | dead.insert(e); |
686 | changed = true; |
687 | DEBUG_PRINTF("removing edge %zu->%zu\n" , g[p].index, |
688 | g[s].index); |
689 | } else if (is_subset_of(succs(p, g), succs(u, g))) { |
690 | if (is_match_vertex(p, g) |
691 | && !is_subset_of(g[p].reports, g[v].reports)) { |
692 | continue; |
693 | } |
694 | DEBUG_PRINTF("updating reach on %zu\n" , g[p].index); |
695 | changed |= (g[p].char_reach & g[v].char_reach).any(); |
696 | g[p].char_reach &= ~g[v].char_reach; |
697 | } |
698 | |
699 | } |
700 | } |
701 | remove_edges(dead, g); |
702 | dead.clear(); |
703 | } |
704 | |
705 | DEBUG_PRINTF("changed %d\n" , (int)changed); |
706 | return changed; |
707 | } |
708 | |
709 | bool prunePathsRedundantWithSuccessorOfCyclics(NGHolder &g, som_type som) { |
710 | /* TODO: the reverse form of this is also possible */ |
711 | bool changed = false; |
712 | PrunePathsInfo info(g); |
713 | |
714 | for (NFAVertex v : vertices_range(g)) { |
715 | if (hasSelfLoop(v, g) && g[v].char_reach.all()) { |
716 | changed |= pruneUsingSuccessors(g, info, v, som); |
717 | } |
718 | } |
719 | |
720 | if (changed) { |
721 | pruneUseless(g); |
722 | clearReports(g); |
723 | } |
724 | |
725 | return changed; |
726 | } |
727 | |
728 | } // namespace ue2 |
729 | |