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
51using namespace std;
52using boost::filtered_graph;
53using boost::make_filtered_graph;
54using boost::make_constant_property;
55using boost::reverse_graph;
56using boost::adaptors::reverse;
57
58namespace ue2 {
59
60namespace {
61
62/** Distance value used to indicate that the vertex can't be reached. */
63static 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 */
70static constexpr int DIST_INFINITY = INT_MAX - 1;
71
72//
73// Filters
74//
75
76template <class GraphT>
77struct 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
95private:
96 const vector<bool> *bad = nullptr;
97 const GraphT *g = nullptr;
98};
99
100template <class GraphT>
101struct 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
122private:
123 const GraphT *g = nullptr;
124};
125
126} // namespace
127
128template<class Graph>
129static
130vector<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
170template <class GraphT>
171static
172void 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 */
241static
242depth 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
252static
253DepthMinMax 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
262template<class Graph, class Output>
263static
264void 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
281vector<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
305vector<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
338vector<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
379vector<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