1 | /* |
2 | * Copyright (c) 2015-2016, 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 | #include "rose_build_width.h" |
30 | |
31 | #include "nfagraph/ng_holder.h" |
32 | #include "nfagraph/ng_dump.h" |
33 | #include "nfagraph/ng_width.h" |
34 | #include "rose_build_impl.h" |
35 | #include "ue2common.h" |
36 | #include "util/graph.h" |
37 | #include "util/graph_range.h" |
38 | |
39 | #include <algorithm> |
40 | |
41 | using namespace std; |
42 | |
43 | namespace ue2 { |
44 | |
45 | static |
46 | bool is_end_anchored(const RoseGraph &g, RoseVertex v) { |
47 | for (auto w : adjacent_vertices_range(v, g)) { |
48 | if (g[w].eod_accept) { |
49 | return true; |
50 | } |
51 | } |
52 | |
53 | return false; |
54 | } |
55 | |
56 | u32 findMinWidth(const RoseBuildImpl &tbi, enum rose_literal_table table) { |
57 | if (table != ROSE_FLOATING && table != ROSE_ANCHORED && |
58 | table != ROSE_EOD_ANCHORED) { |
59 | /* handle other tables if ever required */ |
60 | assert(0); |
61 | return 0; |
62 | } |
63 | |
64 | const RoseGraph &g = tbi.g; |
65 | |
66 | vector<RoseVertex> table_verts; |
67 | |
68 | for (auto v : vertices_range(g)) { |
69 | if (tbi.hasLiteralInTable(v, table)) { |
70 | table_verts.push_back(v); |
71 | } |
72 | } |
73 | |
74 | set<RoseVertex> reachable; |
75 | find_reachable(g, table_verts, &reachable); |
76 | |
77 | u32 minWidth = ROSE_BOUND_INF; |
78 | for (auto v : reachable) { |
79 | if (g[v].eod_accept) { |
80 | DEBUG_PRINTF("skipping %zu - not a real vertex\n" , g[v].index); |
81 | continue; |
82 | } |
83 | |
84 | const u32 w = g[v].min_offset; |
85 | |
86 | if (!g[v].reports.empty()) { |
87 | DEBUG_PRINTF("%zu can fire report at offset %u\n" , g[v].index, w); |
88 | minWidth = min(minWidth, w); |
89 | } |
90 | |
91 | if (is_end_anchored(g, v)) { |
92 | DEBUG_PRINTF("%zu can fire eod report at offset %u\n" , g[v].index, |
93 | w); |
94 | minWidth = min(minWidth, w); |
95 | } |
96 | |
97 | if (g[v].suffix) { |
98 | depth suffix_width = findMinWidth(g[v].suffix, g[v].suffix.top); |
99 | assert(suffix_width.is_reachable()); |
100 | DEBUG_PRINTF("%zu has suffix with top %u (width %s), can fire " |
101 | "report at %u\n" , |
102 | g[v].index, g[v].suffix.top, suffix_width.str().c_str(), |
103 | w + suffix_width); |
104 | minWidth = min(minWidth, w + suffix_width); |
105 | } |
106 | } |
107 | |
108 | /* TODO: take into account the chain relationship between the mpv and other |
109 | * engines */ |
110 | DEBUG_PRINTF("min width %u\n" , minWidth); |
111 | return minWidth; |
112 | } |
113 | |
114 | u32 findMaxBAWidth(const RoseBuildImpl &tbi) { |
115 | const RoseGraph &g = tbi.g; |
116 | if (!isLeafNode(tbi.root, g)) { |
117 | DEBUG_PRINTF("floating literal -> no max width\n" ); |
118 | return ROSE_BOUND_INF; |
119 | } |
120 | |
121 | u64a maxWidth = 0; |
122 | |
123 | for (const auto &outfix : tbi.outfixes) { |
124 | maxWidth = max(maxWidth, (u64a)outfix.maxBAWidth); |
125 | if (maxWidth >= ROSE_BOUND_INF) { |
126 | DEBUG_PRINTF("outfix with no max ba width\n" ); |
127 | return ROSE_BOUND_INF; |
128 | } |
129 | } |
130 | |
131 | // Everyone's anchored, so the max width can be taken from the max |
132 | // max_offset on our vertices (so long as all accepts are EOD). |
133 | for (auto v : vertices_range(g)) { |
134 | if (!g[v].reports.empty() && !g[v].eod_accept) { |
135 | DEBUG_PRINTF("accept not at eod\n" ); |
136 | return ROSE_BOUND_INF; |
137 | } |
138 | |
139 | if (g[v].reports.empty() && !g[v].suffix) { |
140 | continue; |
141 | } |
142 | |
143 | assert(g[v].eod_accept || g[v].suffix); |
144 | |
145 | u64a w = g[v].max_offset; |
146 | |
147 | if (g[v].suffix) { |
148 | if (has_non_eod_accepts(g[v].suffix)) { |
149 | return ROSE_BOUND_INF; |
150 | } |
151 | depth suffix_width = findMaxWidth(g[v].suffix, g[v].suffix.top); |
152 | DEBUG_PRINTF("suffix max width for top %u is %s\n" , g[v].suffix.top, |
153 | suffix_width.str().c_str()); |
154 | assert(suffix_width.is_reachable()); |
155 | if (!suffix_width.is_finite()) { |
156 | DEBUG_PRINTF("suffix too wide\n" ); |
157 | return ROSE_BOUND_INF; |
158 | } |
159 | |
160 | w += suffix_width; |
161 | } |
162 | |
163 | maxWidth = max(maxWidth, w); |
164 | if (maxWidth >= ROSE_BOUND_INF) { |
165 | DEBUG_PRINTF("too wide\n" ); |
166 | return ROSE_BOUND_INF; |
167 | } |
168 | } |
169 | |
170 | DEBUG_PRINTF("max ba width %llu\n" , maxWidth); |
171 | assert(maxWidth < ROSE_BOUND_INF); |
172 | return maxWidth; |
173 | } |
174 | |
175 | u32 findMaxBAWidth(const RoseBuildImpl &tbi, enum rose_literal_table table) { |
176 | const RoseGraph &g = tbi.g; |
177 | if (!isLeafNode(tbi.root, g) && table == ROSE_FLOATING) { |
178 | DEBUG_PRINTF("floating literal -> no max width\n" ); |
179 | return ROSE_BOUND_INF; |
180 | } |
181 | |
182 | if (table != ROSE_FLOATING && table != ROSE_ANCHORED) { |
183 | /* handle other tables if ever required */ |
184 | assert(0); |
185 | return ROSE_BOUND_INF; |
186 | } |
187 | |
188 | DEBUG_PRINTF("looking for a max ba width for %s\n" , |
189 | table == ROSE_FLOATING ? "floating" : "anchored" ); |
190 | |
191 | vector<RoseVertex> table_verts; |
192 | |
193 | for (auto v : vertices_range(g)) { |
194 | if ((table == ROSE_FLOATING && tbi.isFloating(v)) |
195 | || (table == ROSE_ANCHORED && tbi.isAnchored(v))) { |
196 | table_verts.push_back(v); |
197 | } |
198 | } |
199 | |
200 | set<RoseVertex> reachable; |
201 | find_reachable(g, table_verts, &reachable); |
202 | |
203 | u64a maxWidth = 0; |
204 | // Everyone's anchored, so the max width can be taken from the max |
205 | // max_offset on our vertices (so long as all accepts are ACCEPT_EOD). |
206 | for (auto v : reachable) { |
207 | DEBUG_PRINTF("inspecting vert %zu\n" , g[v].index); |
208 | |
209 | if (g[v].eod_accept) { |
210 | DEBUG_PRINTF("skipping %zu - not a real vertex\n" , g[v].index); |
211 | continue; |
212 | } |
213 | |
214 | if (!g[v].reports.empty()) { |
215 | DEBUG_PRINTF("accept not at eod\n" ); |
216 | return ROSE_BOUND_INF; |
217 | } |
218 | |
219 | u64a w = g[v].max_offset; |
220 | |
221 | u64a follow_max = tbi.calcSuccMaxBound(v); /* may have a long bound to |
222 | accept_eod node */ |
223 | |
224 | if (g[v].suffix) { |
225 | if (has_non_eod_accepts(g[v].suffix)) { |
226 | DEBUG_PRINTF("has accept\n" ); |
227 | return ROSE_BOUND_INF; |
228 | } |
229 | depth suffix_width = findMaxWidth(g[v].suffix); |
230 | DEBUG_PRINTF("suffix max width %s\n" , suffix_width.str().c_str()); |
231 | assert(suffix_width.is_reachable()); |
232 | if (!suffix_width.is_finite()) { |
233 | DEBUG_PRINTF("suffix too wide\n" ); |
234 | return ROSE_BOUND_INF; |
235 | } |
236 | follow_max = max(follow_max, (u64a)suffix_width); |
237 | } |
238 | |
239 | w += follow_max; |
240 | |
241 | DEBUG_PRINTF("w %llu\n" , w); |
242 | |
243 | maxWidth = max(maxWidth, w); |
244 | if (maxWidth >= ROSE_BOUND_INF) { |
245 | DEBUG_PRINTF("too wide\n" ); |
246 | return ROSE_BOUND_INF; |
247 | } |
248 | } |
249 | |
250 | DEBUG_PRINTF("max ba width %llu\n" , maxWidth); |
251 | assert(maxWidth < ROSE_BOUND_INF); |
252 | return maxWidth; |
253 | } |
254 | |
255 | } // namespace ue2 |
256 | |