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
49using namespace std;
50
51namespace ue2 {
52
53namespace {
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 */
59struct 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 }
83private:
84 const NGHolder *h = nullptr;
85 bool single_top = false;
86 u32 top = 0;
87};
88
89} // namespace
90
91static
92depth 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
130static
131depth 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
188static
189depth 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
206depth findMinWidth(const NGHolder &h) {
207 return findMinWidth(h, SpecialEdgeFilter(h));
208}
209
210depth findMinWidth(const NGHolder &h, u32 top) {
211 return findMinWidth(h, SpecialEdgeFilter(h, top));
212}
213
214static
215depth 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
229depth findMaxWidth(const NGHolder &h) {
230 return findMaxWidth(h, SpecialEdgeFilter(h));
231}
232
233depth findMaxWidth(const NGHolder &h, u32 top) {
234 return findMaxWidth(h, SpecialEdgeFilter(h, top));
235}
236
237} // namespace ue2
238