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
41using namespace std;
42
43namespace ue2 {
44
45static
46bool 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
56u32 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
114u32 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
175u32 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