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 Functions for finding the min/max width of the input required to |
31 | * match a pattern. |
32 | */ |
33 | #include "ng_width.h" |
34 | |
35 | #include "ng_holder.h" |
36 | #include "ng_util.h" |
37 | #include "ue2common.h" |
38 | #include "util/depth.h" |
39 | #include "util/graph.h" |
40 | #include "util/graph_small_color_map.h" |
41 | |
42 | #include <deque> |
43 | #include <vector> |
44 | |
45 | #include <boost/graph/breadth_first_search.hpp> |
46 | #include <boost/graph/dag_shortest_paths.hpp> |
47 | #include <boost/graph/filtered_graph.hpp> |
48 | |
49 | using namespace std; |
50 | |
51 | namespace ue2 { |
52 | |
53 | namespace { |
54 | |
55 | /** |
56 | * Filter out special edges, or in the top-specific variant, start edges that |
57 | * don't have the right top set. |
58 | */ |
59 | struct SpecialEdgeFilter { |
60 | SpecialEdgeFilter() {} |
61 | explicit SpecialEdgeFilter(const NGHolder &h_in) : h(&h_in) {} |
62 | SpecialEdgeFilter(const NGHolder &h_in, u32 top_in) |
63 | : h(&h_in), single_top(true), top(top_in) {} |
64 | |
65 | bool operator()(const NFAEdge &e) const { |
66 | NFAVertex u = source(e, *h); |
67 | NFAVertex v = target(e, *h); |
68 | if ((is_any_start(u, *h) && is_any_start(v, *h)) || |
69 | (is_any_accept(u, *h) && is_any_accept(v, *h))) { |
70 | return false; |
71 | } |
72 | if (single_top) { |
73 | if (u == h->start && !contains((*h)[e].tops, top)) { |
74 | return false; |
75 | } |
76 | if (u == h->startDs) { |
77 | return false; |
78 | } |
79 | } |
80 | return true; |
81 | |
82 | } |
83 | private: |
84 | const NGHolder *h = nullptr; |
85 | bool single_top = false; |
86 | u32 top = 0; |
87 | }; |
88 | |
89 | } // namespace |
90 | |
91 | static |
92 | depth findMinWidth(const NGHolder &h, const SpecialEdgeFilter &filter, |
93 | NFAVertex src) { |
94 | if (isLeafNode(src, h)) { |
95 | return depth::unreachable(); |
96 | } |
97 | |
98 | boost::filtered_graph<NGHolder, SpecialEdgeFilter> g(h, filter); |
99 | |
100 | assert(hasCorrectlyNumberedVertices(h)); |
101 | const size_t num = num_vertices(h); |
102 | vector<depth> distance(num, depth::unreachable()); |
103 | distance.at(g[src].index) = depth(0); |
104 | |
105 | auto index_map = get(&NFAGraphVertexProps::index, g); |
106 | |
107 | // Since we are interested in the single-source shortest paths on a graph |
108 | // with the same weight on every edge, using BFS will be faster than |
109 | // Dijkstra here. |
110 | breadth_first_search(g, src, |
111 | visitor(make_bfs_visitor(record_distances( |
112 | make_iterator_property_map(distance.begin(), index_map), |
113 | boost::on_tree_edge())))); |
114 | |
115 | DEBUG_PRINTF("d[accept]=%s, d[acceptEod]=%s\n" , |
116 | distance.at(NODE_ACCEPT).str().c_str(), |
117 | distance.at(NODE_ACCEPT_EOD).str().c_str()); |
118 | |
119 | depth d = min(distance.at(NODE_ACCEPT), distance.at(NODE_ACCEPT_EOD)); |
120 | |
121 | if (d.is_unreachable()) { |
122 | return d; |
123 | } |
124 | |
125 | assert(d.is_finite()); |
126 | assert(d > depth(0)); |
127 | return d - depth(1); |
128 | } |
129 | |
130 | static |
131 | depth findMaxWidth(const NGHolder &h, const SpecialEdgeFilter &filter, |
132 | NFAVertex src) { |
133 | if (isLeafNode(src, h)) { |
134 | return depth::unreachable(); |
135 | } |
136 | |
137 | if (hasReachableCycle(h, src)) { |
138 | // There's a cycle reachable from this src, so we have inf width. |
139 | return depth::infinity(); |
140 | } |
141 | |
142 | boost::filtered_graph<NGHolder, SpecialEdgeFilter> g(h, filter); |
143 | |
144 | assert(hasCorrectlyNumberedVertices(h)); |
145 | const size_t num = num_vertices(h); |
146 | vector<int> distance(num); |
147 | auto colors = make_small_color_map(h); |
148 | |
149 | auto index_map = get(&NFAGraphVertexProps::index, g); |
150 | |
151 | // DAG shortest paths with negative edge weights. |
152 | dag_shortest_paths(g, src, |
153 | distance_map(make_iterator_property_map(distance.begin(), index_map)) |
154 | .weight_map(boost::make_constant_property<NFAEdge>(-1)) |
155 | .color_map(colors)); |
156 | |
157 | depth acceptDepth, acceptEodDepth; |
158 | if (get(colors, h.accept) == small_color::white) { |
159 | acceptDepth = depth::unreachable(); |
160 | } else { |
161 | acceptDepth = depth(-1 * distance.at(NODE_ACCEPT)); |
162 | } |
163 | if (get(colors, h.acceptEod) == small_color::white) { |
164 | acceptEodDepth = depth::unreachable(); |
165 | } else { |
166 | acceptEodDepth = depth(-1 * distance.at(NODE_ACCEPT_EOD)); |
167 | } |
168 | |
169 | depth d; |
170 | if (acceptDepth.is_unreachable()) { |
171 | d = acceptEodDepth; |
172 | } else if (acceptEodDepth.is_unreachable()) { |
173 | d = acceptDepth; |
174 | } else { |
175 | d = max(acceptDepth, acceptEodDepth); |
176 | } |
177 | |
178 | if (d.is_unreachable()) { |
179 | assert(findMinWidth(h, filter, src).is_unreachable()); |
180 | return d; |
181 | } |
182 | |
183 | // Invert sign and subtract one for start transition. |
184 | assert(d.is_finite() && d > depth(0)); |
185 | return d - depth(1); |
186 | } |
187 | |
188 | static |
189 | depth findMinWidth(const NGHolder &h, const SpecialEdgeFilter &filter) { |
190 | depth startDepth = findMinWidth(h, filter, h.start); |
191 | depth dotstarDepth = findMinWidth(h, filter, h.startDs); |
192 | DEBUG_PRINTF("startDepth=%s, dotstarDepth=%s\n" , startDepth.str().c_str(), |
193 | dotstarDepth.str().c_str()); |
194 | if (startDepth.is_unreachable()) { |
195 | assert(dotstarDepth.is_finite()); |
196 | return dotstarDepth; |
197 | } else if (dotstarDepth.is_unreachable()) { |
198 | assert(startDepth.is_finite()); |
199 | return startDepth; |
200 | } else { |
201 | assert(min(startDepth, dotstarDepth).is_finite()); |
202 | return min(startDepth, dotstarDepth); |
203 | } |
204 | } |
205 | |
206 | depth findMinWidth(const NGHolder &h) { |
207 | return findMinWidth(h, SpecialEdgeFilter(h)); |
208 | } |
209 | |
210 | depth findMinWidth(const NGHolder &h, u32 top) { |
211 | return findMinWidth(h, SpecialEdgeFilter(h, top)); |
212 | } |
213 | |
214 | static |
215 | depth findMaxWidth(const NGHolder &h, const SpecialEdgeFilter &filter) { |
216 | depth startDepth = findMaxWidth(h, filter, h.start); |
217 | depth dotstarDepth = findMaxWidth(h, filter, h.startDs); |
218 | DEBUG_PRINTF("startDepth=%s, dotstarDepth=%s\n" , startDepth.str().c_str(), |
219 | dotstarDepth.str().c_str()); |
220 | if (startDepth.is_unreachable()) { |
221 | return dotstarDepth; |
222 | } else if (dotstarDepth.is_unreachable()) { |
223 | return startDepth; |
224 | } else { |
225 | return max(startDepth, dotstarDepth); |
226 | } |
227 | } |
228 | |
229 | depth findMaxWidth(const NGHolder &h) { |
230 | return findMaxWidth(h, SpecialEdgeFilter(h)); |
231 | } |
232 | |
233 | depth findMaxWidth(const NGHolder &h, u32 top) { |
234 | return findMaxWidth(h, SpecialEdgeFilter(h, top)); |
235 | } |
236 | |
237 | } // namespace ue2 |
238 | |