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
84using namespace std;
85using boost::make_filtered_graph;
86
87namespace ue2 {
88
89static
90void 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
120static
121void 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. */
152static
153void 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. */
163static
164void 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. */
179static
180set<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. */
215static
216set<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
246static
247bool 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
301static
302bool 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
351static
352bool 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
367static
368bool 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
382bool 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. */
394CharReach 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
465vector<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
478static
479bool 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
488bool 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
554struct 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 */
574static
575void 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
614static
615bool willBeEnabledConcurrently(NFAVertex main_cyclic, NFAVertex v,
616 const NGHolder &g) {
617 return is_subset_of(preds(main_cyclic, g), preds(v, g));
618}
619
620static
621bool sometimesEnabledConcurrently(NFAVertex main_cyclic, NFAVertex v,
622 const NGHolder &g) {
623 return has_intersection(preds(main_cyclic, g), preds(v, g));
624}
625
626static
627bool 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
709bool 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