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 NFA graph vertex depth calculations. |
32 | */ |
33 | #include "ng_depth.h" |
34 | #include "ng_util.h" |
35 | #include "ue2common.h" |
36 | #include "util/graph_range.h" |
37 | #include "util/graph_small_color_map.h" |
38 | |
39 | #include <deque> |
40 | #include <vector> |
41 | |
42 | #include <boost/graph/breadth_first_search.hpp> |
43 | #include <boost/graph/dag_shortest_paths.hpp> |
44 | #include <boost/graph/depth_first_search.hpp> |
45 | #include <boost/graph/filtered_graph.hpp> |
46 | #include <boost/graph/property_maps/constant_property_map.hpp> |
47 | #include <boost/graph/reverse_graph.hpp> |
48 | #include <boost/graph/topological_sort.hpp> |
49 | #include <boost/range/adaptor/reversed.hpp> |
50 | |
51 | using namespace std; |
52 | using boost::filtered_graph; |
53 | using boost::make_filtered_graph; |
54 | using boost::make_constant_property; |
55 | using boost::reverse_graph; |
56 | using boost::adaptors::reverse; |
57 | |
58 | namespace ue2 { |
59 | |
60 | namespace { |
61 | |
62 | /** Distance value used to indicate that the vertex can't be reached. */ |
63 | static constexpr int DIST_UNREACHABLE = INT_MAX; |
64 | |
65 | /** |
66 | * Distance value used to indicate that the distance to a vertex is infinite |
67 | * (for example, it's the max distance and there's a cycle in the path) or so |
68 | * large that we should consider it effectively infinite. |
69 | */ |
70 | static constexpr int DIST_INFINITY = INT_MAX - 1; |
71 | |
72 | // |
73 | // Filters |
74 | // |
75 | |
76 | template <class GraphT> |
77 | struct NodeFilter { |
78 | typedef typename GraphT::edge_descriptor EdgeT; |
79 | NodeFilter() {} // BGL filters must be default-constructible. |
80 | NodeFilter(const vector<bool> *bad_in, const GraphT *g_in) |
81 | : bad(bad_in), g(g_in) { } |
82 | bool operator()(const EdgeT &e) const { |
83 | assert(g && bad); |
84 | |
85 | u32 src_idx = (*g)[source(e, *g)].index; |
86 | u32 tar_idx = (*g)[target(e, *g)].index; |
87 | |
88 | if (tar_idx == NODE_START_DOTSTAR) { |
89 | return false; |
90 | } |
91 | |
92 | return !(*bad)[src_idx] && !(*bad)[tar_idx]; |
93 | } |
94 | |
95 | private: |
96 | const vector<bool> *bad = nullptr; |
97 | const GraphT *g = nullptr; |
98 | }; |
99 | |
100 | template <class GraphT> |
101 | struct StartFilter { |
102 | typedef typename GraphT::edge_descriptor EdgeT; |
103 | StartFilter() {} // BGL filters must be default-constructible. |
104 | explicit StartFilter(const GraphT *g_in) : g(g_in) { } |
105 | bool operator()(const EdgeT &e) const { |
106 | assert(g); |
107 | |
108 | u32 src_idx = (*g)[source(e, *g)].index; |
109 | u32 tar_idx = (*g)[target(e, *g)].index; |
110 | |
111 | // Remove our stylised edges from anchored start to startDs. |
112 | if (src_idx == NODE_START && tar_idx == NODE_START_DOTSTAR) { |
113 | return false; |
114 | } |
115 | // Also remove the equivalent in the reversed direction. |
116 | if (src_idx == NODE_ACCEPT_EOD && tar_idx == NODE_ACCEPT) { |
117 | return false; |
118 | } |
119 | return true; |
120 | } |
121 | |
122 | private: |
123 | const GraphT *g = nullptr; |
124 | }; |
125 | |
126 | } // namespace |
127 | |
128 | template<class Graph> |
129 | static |
130 | vector<bool> findLoopReachable(const Graph &g, |
131 | const typename Graph::vertex_descriptor src) { |
132 | vector<bool> deadNodes(num_vertices(g)); |
133 | |
134 | using Edge = typename Graph::edge_descriptor; |
135 | using Vertex = typename Graph::vertex_descriptor; |
136 | using EdgeSet = set<Edge>; |
137 | |
138 | EdgeSet deadEdges; |
139 | BackEdges<EdgeSet> be(deadEdges); |
140 | |
141 | auto colors = make_small_color_map(g); |
142 | |
143 | depth_first_search(g, be, colors, src); |
144 | auto af = make_bad_edge_filter(&deadEdges); |
145 | auto acyclic_g = make_filtered_graph(g, af); |
146 | |
147 | vector<Vertex> topoOrder; /* actually reverse topological order */ |
148 | topoOrder.reserve(deadNodes.size()); |
149 | topological_sort(acyclic_g, back_inserter(topoOrder), color_map(colors)); |
150 | |
151 | for (const auto &e : deadEdges) { |
152 | size_t srcIdx = g[source(e, g)].index; |
153 | if (srcIdx != NODE_START_DOTSTAR) { |
154 | deadNodes[srcIdx] = true; |
155 | } |
156 | } |
157 | |
158 | for (auto v : reverse(topoOrder)) { |
159 | for (const auto &e : in_edges_range(v, g)) { |
160 | if (deadNodes[g[source(e, g)].index]) { |
161 | deadNodes[g[v].index] = true; |
162 | break; |
163 | } |
164 | } |
165 | } |
166 | |
167 | return deadNodes; |
168 | } |
169 | |
170 | template <class GraphT> |
171 | static |
172 | void calcDepthFromSource(const GraphT &g, |
173 | typename GraphT::vertex_descriptor srcVertex, |
174 | const vector<bool> &deadNodes, vector<int> &dMin, |
175 | vector<int> &dMax) { |
176 | typedef typename GraphT::edge_descriptor EdgeT; |
177 | |
178 | const size_t numVerts = num_vertices(g); |
179 | |
180 | NodeFilter<GraphT> nf(&deadNodes, &g); |
181 | StartFilter<GraphT> sf(&g); |
182 | |
183 | /* minimum distance needs to run on a graph with .*start unreachable |
184 | * from start */ |
185 | typedef filtered_graph<GraphT, StartFilter<GraphT> > StartFilteredGraph; |
186 | const StartFilteredGraph mindist_g(g, sf); |
187 | |
188 | /* maximum distance needs to run on a graph without cycles & nodes |
189 | * reachable from cycles */ |
190 | typedef filtered_graph<GraphT, NodeFilter<GraphT> > NodeFilteredGraph; |
191 | const NodeFilteredGraph maxdist_g(g, nf); |
192 | |
193 | // Record distance of each vertex from source using one of the following |
194 | // algorithms. |
195 | |
196 | /* note: filtered graphs have same num_{vertices,edges} as base */ |
197 | |
198 | dMin.assign(numVerts, DIST_UNREACHABLE); |
199 | dMax.assign(numVerts, DIST_UNREACHABLE); |
200 | dMin[mindist_g[srcVertex].index] = 0; |
201 | |
202 | using boost::make_iterator_property_map; |
203 | |
204 | auto min_index_map = get(vertex_index, mindist_g); |
205 | |
206 | breadth_first_search(mindist_g, srcVertex, |
207 | visitor(make_bfs_visitor(record_distances( |
208 | make_iterator_property_map(dMin.begin(), |
209 | min_index_map), |
210 | boost::on_tree_edge()))) |
211 | .color_map(make_small_color_map(mindist_g))); |
212 | |
213 | auto max_index_map = get(vertex_index, maxdist_g); |
214 | |
215 | dag_shortest_paths(maxdist_g, srcVertex, |
216 | distance_map(make_iterator_property_map(dMax.begin(), |
217 | max_index_map)) |
218 | .weight_map(make_constant_property<EdgeT>(-1)) |
219 | .color_map(make_small_color_map(maxdist_g))); |
220 | |
221 | for (size_t i = 0; i < numVerts; i++) { |
222 | if (dMin[i] > DIST_UNREACHABLE) { |
223 | dMin[i] = DIST_UNREACHABLE; |
224 | } |
225 | DEBUG_PRINTF("%zu: dm %d %d\n" , i, dMin[i], dMax[i]); |
226 | if (dMax[i] >= DIST_UNREACHABLE && dMin[i] < DIST_UNREACHABLE) { |
227 | dMax[i] = -DIST_INFINITY; /* max depths currently negative */ |
228 | DEBUG_PRINTF("bumping max to %d\n" , dMax[i]); |
229 | } else if (dMax[i] >= DIST_UNREACHABLE |
230 | || dMax[i] < -DIST_UNREACHABLE) { |
231 | dMax[i] = -DIST_UNREACHABLE; |
232 | DEBUG_PRINTF("bumping max to %d\n" , dMax[i]); |
233 | } |
234 | } |
235 | } |
236 | |
237 | /** |
238 | * \brief Convert the integer distance we use in our shortest path calculations |
239 | * to a \ref depth value. |
240 | */ |
241 | static |
242 | depth depthFromDistance(int val) { |
243 | assert(val >= 0); |
244 | if (val >= DIST_UNREACHABLE) { |
245 | return depth::unreachable(); |
246 | } else if (val == DIST_INFINITY) { |
247 | return depth::infinity(); |
248 | } |
249 | return depth((u32)val); |
250 | } |
251 | |
252 | static |
253 | DepthMinMax getDepths(u32 idx, const vector<int> &dMin, |
254 | const vector<int> &dMax) { |
255 | DepthMinMax d(depthFromDistance(dMin[idx]), |
256 | depthFromDistance(-1 * dMax[idx])); |
257 | DEBUG_PRINTF("idx=%u, depths=%s\n" , idx, d.str().c_str()); |
258 | assert(d.min <= d.max); |
259 | return d; |
260 | } |
261 | |
262 | template<class Graph, class Output> |
263 | static |
264 | void calcAndStoreDepth(const Graph &g, |
265 | const typename Graph::vertex_descriptor src, |
266 | const vector<bool> &deadNodes, |
267 | vector<int> &dMin /* util */, |
268 | vector<int> &dMax /* util */, |
269 | vector<Output> &depths, |
270 | DepthMinMax Output::*store) { |
271 | calcDepthFromSource(g, src, deadNodes, dMin, dMax); |
272 | |
273 | for (auto v : vertices_range(g)) { |
274 | u32 idx = g[v].index; |
275 | assert(idx < depths.size()); |
276 | Output &d = depths.at(idx); |
277 | d.*store = getDepths(idx, dMin, dMax); |
278 | } |
279 | } |
280 | |
281 | vector<NFAVertexDepth> calcDepths(const NGHolder &g) { |
282 | assert(hasCorrectlyNumberedVertices(g)); |
283 | const size_t numVertices = num_vertices(g); |
284 | |
285 | vector<NFAVertexDepth> depths(numVertices); |
286 | vector<int> dMin; |
287 | vector<int> dMax; |
288 | |
289 | /* |
290 | * create a filtered graph for max depth calculations: all nodes/edges |
291 | * reachable from a loop need to be removed |
292 | */ |
293 | auto deadNodes = findLoopReachable(g, g.start); |
294 | |
295 | DEBUG_PRINTF("doing start\n" ); |
296 | calcAndStoreDepth(g, g.start, deadNodes, dMin, dMax, depths, |
297 | &NFAVertexDepth::fromStart); |
298 | DEBUG_PRINTF("doing startds\n" ); |
299 | calcAndStoreDepth(g, g.startDs, deadNodes, dMin, dMax, depths, |
300 | &NFAVertexDepth::fromStartDotStar); |
301 | |
302 | return depths; |
303 | } |
304 | |
305 | vector<NFAVertexRevDepth> calcRevDepths(const NGHolder &g) { |
306 | assert(hasCorrectlyNumberedVertices(g)); |
307 | const size_t numVertices = num_vertices(g); |
308 | |
309 | vector<NFAVertexRevDepth> depths(numVertices); |
310 | vector<int> dMin; |
311 | vector<int> dMax; |
312 | |
313 | /* reverse the graph before walking it */ |
314 | typedef reverse_graph<NGHolder, const NGHolder &> RevNFAGraph; |
315 | const RevNFAGraph rg(g); |
316 | |
317 | assert(num_vertices(g) == num_vertices(rg)); |
318 | |
319 | /* |
320 | * create a filtered graph for max depth calculations: all nodes/edges |
321 | * reachable from a loop need to be removed |
322 | */ |
323 | auto deadNodes = findLoopReachable(rg, g.acceptEod); |
324 | |
325 | DEBUG_PRINTF("doing accept\n" ); |
326 | calcAndStoreDepth<RevNFAGraph, NFAVertexRevDepth>( |
327 | rg, g.accept, deadNodes, dMin, dMax, depths, |
328 | &NFAVertexRevDepth::toAccept); |
329 | DEBUG_PRINTF("doing accepteod\n" ); |
330 | deadNodes[NODE_ACCEPT] = true; // Hide accept->acceptEod edge. |
331 | calcAndStoreDepth<RevNFAGraph, NFAVertexRevDepth>( |
332 | rg, g.acceptEod, deadNodes, dMin, dMax, depths, |
333 | &NFAVertexRevDepth::toAcceptEod); |
334 | |
335 | return depths; |
336 | } |
337 | |
338 | vector<NFAVertexBidiDepth> calcBidiDepths(const NGHolder &g) { |
339 | assert(hasCorrectlyNumberedVertices(g)); |
340 | const size_t numVertices = num_vertices(g); |
341 | |
342 | vector<NFAVertexBidiDepth> depths(numVertices); |
343 | vector<int> dMin; |
344 | vector<int> dMax; |
345 | |
346 | /* |
347 | * create a filtered graph for max depth calculations: all nodes/edges |
348 | * reachable from a loop need to be removed |
349 | */ |
350 | auto deadNodes = findLoopReachable(g, g.start); |
351 | |
352 | DEBUG_PRINTF("doing start\n" ); |
353 | calcAndStoreDepth<NGHolder, NFAVertexBidiDepth>( |
354 | g, g.start, deadNodes, dMin, dMax, depths, |
355 | &NFAVertexBidiDepth::fromStart); |
356 | DEBUG_PRINTF("doing startds\n" ); |
357 | calcAndStoreDepth<NGHolder, NFAVertexBidiDepth>( |
358 | g, g.startDs, deadNodes, dMin, dMax, depths, |
359 | &NFAVertexBidiDepth::fromStartDotStar); |
360 | |
361 | /* Now go backwards */ |
362 | typedef reverse_graph<NGHolder, const NGHolder &> RevNFAGraph; |
363 | const RevNFAGraph rg(g); |
364 | deadNodes = findLoopReachable(rg, g.acceptEod); |
365 | |
366 | DEBUG_PRINTF("doing accept\n" ); |
367 | calcAndStoreDepth<RevNFAGraph, NFAVertexBidiDepth>( |
368 | rg, g.accept, deadNodes, dMin, dMax, depths, |
369 | &NFAVertexBidiDepth::toAccept); |
370 | DEBUG_PRINTF("doing accepteod\n" ); |
371 | deadNodes[NODE_ACCEPT] = true; // Hide accept->acceptEod edge. |
372 | calcAndStoreDepth<RevNFAGraph, NFAVertexBidiDepth>( |
373 | rg, g.acceptEod, deadNodes, dMin, dMax, depths, |
374 | &NFAVertexBidiDepth::toAcceptEod); |
375 | |
376 | return depths; |
377 | } |
378 | |
379 | vector<DepthMinMax> calcDepthsFrom(const NGHolder &g, const NFAVertex src) { |
380 | assert(hasCorrectlyNumberedVertices(g)); |
381 | const size_t numVertices = num_vertices(g); |
382 | |
383 | auto deadNodes = findLoopReachable(g, g.start); |
384 | |
385 | vector<int> dMin, dMax; |
386 | calcDepthFromSource(g, src, deadNodes, dMin, dMax); |
387 | |
388 | vector<DepthMinMax> depths(numVertices); |
389 | |
390 | for (auto v : vertices_range(g)) { |
391 | auto idx = g[v].index; |
392 | depths.at(idx) = getDepths(idx, dMin, dMax); |
393 | } |
394 | |
395 | return depths; |
396 | } |
397 | |
398 | } // namespace ue2 |
399 | |