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 | #include "rose_build_impl.h" |
30 | |
31 | #include "grey.h" |
32 | #include "hs_internal.h" |
33 | #include "rose_build_anchored.h" |
34 | #include "rose_build_castle.h" |
35 | #include "rose_build_convert.h" |
36 | #include "rose_build_dump.h" |
37 | #include "rose_build_groups.h" |
38 | #include "rose_build_matchers.h" |
39 | #include "rose_build_merge.h" |
40 | #include "rose_build_role_aliasing.h" |
41 | #include "rose_build_util.h" |
42 | #include "ue2common.h" |
43 | #include "hwlm/hwlm_literal.h" |
44 | #include "nfa/nfa_internal.h" |
45 | #include "nfa/rdfa.h" |
46 | #include "nfagraph/ng_holder.h" |
47 | #include "nfagraph/ng_execute.h" |
48 | #include "nfagraph/ng_is_equal.h" |
49 | #include "nfagraph/ng_limex.h" |
50 | #include "nfagraph/ng_mcclellan.h" |
51 | #include "nfagraph/ng_prune.h" |
52 | #include "nfagraph/ng_repeat.h" |
53 | #include "nfagraph/ng_reports.h" |
54 | #include "nfagraph/ng_stop.h" |
55 | #include "nfagraph/ng_util.h" |
56 | #include "nfagraph/ng_width.h" |
57 | #include "util/bitutils.h" |
58 | #include "util/charreach.h" |
59 | #include "util/charreach_util.h" |
60 | #include "util/compare.h" |
61 | #include "util/compile_context.h" |
62 | #include "util/container.h" |
63 | #include "util/dump_charclass.h" |
64 | #include "util/flat_containers.h" |
65 | #include "util/graph_range.h" |
66 | #include "util/order_check.h" |
67 | #include "util/report_manager.h" |
68 | #include "util/ue2string.h" |
69 | #include "util/verify_types.h" |
70 | |
71 | #include <algorithm> |
72 | #include <functional> |
73 | #include <map> |
74 | #include <set> |
75 | #include <string> |
76 | #include <vector> |
77 | #include <utility> |
78 | |
79 | #include <boost/range/adaptor/map.hpp> |
80 | |
81 | using namespace std; |
82 | using boost::adaptors::map_values; |
83 | |
84 | namespace ue2 { |
85 | |
86 | #define ANCHORED_REHOME_MIN_FLOATING 800 |
87 | #define ANCHORED_REHOME_MIN_FLOATING_SHORT 50 |
88 | #define ANCHORED_REHOME_ALLOW_SHORT 20 |
89 | #define ANCHORED_REHOME_DEEP 25 |
90 | #define ANCHORED_REHOME_SHORT_LEN 3 |
91 | |
92 | #define MAX_EXPLOSION_NC 3 |
93 | static |
94 | bool limited_explosion(const ue2_literal &s) { |
95 | u32 nc_count = 0; |
96 | |
97 | for (const auto &e : s) { |
98 | if (e.nocase) { |
99 | nc_count++; |
100 | } |
101 | } |
102 | |
103 | return nc_count <= MAX_EXPLOSION_NC; |
104 | } |
105 | |
106 | static |
107 | void removeLiteralFromGraph(RoseBuildImpl &build, u32 id) { |
108 | assert(id < build.literal_info.size()); |
109 | auto &info = build.literal_info.at(id); |
110 | for (const auto &v : info.vertices) { |
111 | build.g[v].literals.erase(id); |
112 | } |
113 | info.vertices.clear(); |
114 | } |
115 | |
116 | /** |
117 | * \brief Replace the given mixed-case literal with the set of its caseless |
118 | * variants. |
119 | */ |
120 | static |
121 | void explodeLiteral(RoseBuildImpl &build, u32 id) { |
122 | const auto &lit = build.literals.at(id); |
123 | auto &info = build.literal_info[id]; |
124 | |
125 | assert(!info.group_mask); // not set yet |
126 | assert(info.undelayed_id == id); // we do not explode delayed literals |
127 | |
128 | for (auto it = caseIterateBegin(lit.s); it != caseIterateEnd(); ++it) { |
129 | ue2_literal new_str(*it, false); |
130 | |
131 | if (!maskIsConsistent(new_str.get_string(), false, lit.msk, lit.cmp)) { |
132 | DEBUG_PRINTF("msk/cmp for literal can't match, skipping\n" ); |
133 | continue; |
134 | } |
135 | |
136 | u32 new_id = |
137 | build.getLiteralId(new_str, lit.msk, lit.cmp, lit.delay, lit.table); |
138 | |
139 | DEBUG_PRINTF("adding exploded lit %u: '%s'\n" , new_id, |
140 | dumpString(new_str).c_str()); |
141 | |
142 | const auto &new_lit = build.literals.at(new_id); |
143 | auto &new_info = build.literal_info.at(new_id); |
144 | insert(&new_info.vertices, info.vertices); |
145 | for (const auto &v : info.vertices) { |
146 | build.g[v].literals.insert(new_id); |
147 | } |
148 | |
149 | build.literal_info[new_id].undelayed_id = new_id; |
150 | if (!info.delayed_ids.empty()) { |
151 | flat_set<u32> &del_ids = new_info.delayed_ids; |
152 | for (u32 delay_id : info.delayed_ids) { |
153 | const auto &dlit = build.literals.at(delay_id); |
154 | u32 new_delay_id = |
155 | build.getLiteralId(new_lit.s, new_lit.msk, new_lit.cmp, |
156 | dlit.delay, dlit.table); |
157 | del_ids.insert(new_delay_id); |
158 | build.literal_info[new_delay_id].undelayed_id = new_id; |
159 | } |
160 | } |
161 | } |
162 | |
163 | // Remove the old literal and any old delay variants. |
164 | removeLiteralFromGraph(build, id); |
165 | for (u32 delay_id : info.delayed_ids) { |
166 | removeLiteralFromGraph(build, delay_id); |
167 | } |
168 | info.delayed_ids.clear(); |
169 | } |
170 | |
171 | void RoseBuildImpl::handleMixedSensitivity(void) { |
172 | vector<u32> explode; |
173 | for (u32 id = 0; id < literals.size(); id++) { |
174 | const rose_literal_id &lit = literals.at(id); |
175 | |
176 | if (lit.delay) { |
177 | continue; /* delay id's are virtual-ish */ |
178 | } |
179 | |
180 | if (lit.table == ROSE_ANCHORED || lit.table == ROSE_EVENT) { |
181 | continue; /* wrong table */ |
182 | } |
183 | |
184 | if (!mixed_sensitivity(lit.s)) { |
185 | continue; |
186 | } |
187 | |
188 | // We don't want to explode long literals, as they require confirmation |
189 | // with a CHECK_LONG_LIT instruction and need unique final_ids. |
190 | // TODO: we could allow explosion for literals where the prefixes |
191 | // covered by CHECK_LONG_LIT are identical. |
192 | |
193 | if (lit.s.length() <= ROSE_LONG_LITERAL_THRESHOLD_MIN && |
194 | limited_explosion(lit.s) && literal_info[id].delayed_ids.empty()) { |
195 | DEBUG_PRINTF("need to explode existing string '%s'\n" , |
196 | dumpString(lit.s).c_str()); |
197 | explode.push_back(id); |
198 | } else { |
199 | literal_info[id].requires_benefits = true; |
200 | } |
201 | } |
202 | |
203 | for (u32 id : explode) { |
204 | explodeLiteral(*this, id); |
205 | } |
206 | } |
207 | |
208 | // Returns the length of the longest prefix of s that is (a) also a suffix of s |
209 | // and (b) not s itself. |
210 | static |
211 | size_t maxPeriod(const ue2_literal &s) { |
212 | /* overly conservative if only part of the string is nocase */ |
213 | if (s.empty()) { |
214 | return 0; |
215 | } |
216 | |
217 | const size_t len = s.length(); |
218 | const char *begin = s.c_str(), *end = begin + len; |
219 | size_t i; |
220 | for (i = len - 1; i != 0; i--) { |
221 | if (!cmp(begin, end - i, i, s.any_nocase())) { |
222 | break; |
223 | } |
224 | } |
225 | |
226 | return i; |
227 | } |
228 | |
229 | bool RoseBuildImpl::isPseudoStar(const RoseEdge &e) const { |
230 | return !g[e].minBound && isPseudoStarOrFirstOnly(e); |
231 | } |
232 | |
233 | bool RoseBuildImpl::isPseudoStarOrFirstOnly(const RoseEdge &e) const { |
234 | RoseVertex u = source(e, g); |
235 | RoseVertex v = target(e, g); |
236 | |
237 | if (g[e].maxBound != ROSE_BOUND_INF) { |
238 | return false; |
239 | } |
240 | |
241 | if (isAnyStart(u)) { |
242 | return true; |
243 | } |
244 | |
245 | if (isAnchored(u)) { |
246 | /* anchored table runs out of order */ |
247 | return false; |
248 | } |
249 | |
250 | if (hasDelayedLiteral(u)) { |
251 | return false; |
252 | } |
253 | |
254 | if (g[v].left) { |
255 | return false; |
256 | } |
257 | |
258 | if (g[v].eod_accept) { |
259 | return true; |
260 | } |
261 | |
262 | assert(!g[v].literals.empty()); |
263 | if (maxLiteralOverlap(u, v)) { |
264 | return false; |
265 | } |
266 | |
267 | return true; |
268 | } |
269 | |
270 | bool RoseBuildImpl::hasOnlyPseudoStarInEdges(RoseVertex v) const { |
271 | for (const auto &e : in_edges_range(v, g)) { |
272 | if (!isPseudoStar(e)) { |
273 | return false; |
274 | } |
275 | } |
276 | return true; |
277 | } |
278 | |
279 | static |
280 | size_t trailerDueToSelf(const rose_literal_id &lit) { |
281 | size_t trailer = lit.s.length() - maxPeriod(lit.s); |
282 | if (trailer > 255) { |
283 | return 255; |
284 | } |
285 | if (!trailer) { |
286 | return 1; |
287 | } |
288 | return trailer; |
289 | } |
290 | |
291 | static |
292 | RoseRoleHistory findHistoryScheme(const RoseBuildImpl &tbi, const RoseEdge &e) { |
293 | const RoseGraph &g = tbi.g; |
294 | const RoseVertex u = source(e, g); /* pred role */ |
295 | const RoseVertex v = target(e, g); /* current role */ |
296 | |
297 | DEBUG_PRINTF("find history for [%zu,%zu]\n" , g[u].index, g[v].index); |
298 | DEBUG_PRINTF("u has min_offset=%u, max_offset=%u\n" , g[u].min_offset, |
299 | g[u].max_offset); |
300 | |
301 | if (g[v].left) { |
302 | if (!tbi.isAnyStart(u)) { |
303 | /* infix nfa will track history, treat as pseudo .*. Note: rose lits |
304 | * may overlap so rose history track would be wrong anyway */ |
305 | DEBUG_PRINTF("skipping history as prefix\n" ); |
306 | return ROSE_ROLE_HISTORY_NONE; |
307 | } |
308 | if (g[e].minBound || g[e].maxBound != ROSE_BOUND_INF) { |
309 | DEBUG_PRINTF("rose prefix with external bounds\n" ); |
310 | return ROSE_ROLE_HISTORY_ANCH; |
311 | } else { |
312 | return ROSE_ROLE_HISTORY_NONE; |
313 | } |
314 | } |
315 | |
316 | // Handle EOD cases. |
317 | if (g[v].eod_accept) { |
318 | const u32 minBound = g[e].minBound, maxBound = g[e].maxBound; |
319 | DEBUG_PRINTF("EOD edge with bounds [%u,%u]\n" , minBound, maxBound); |
320 | |
321 | // Trivial case: we don't need history for {0,inf} bounds |
322 | if (minBound == 0 && maxBound == ROSE_BOUND_INF) { |
323 | return ROSE_ROLE_HISTORY_NONE; |
324 | } |
325 | |
326 | // Event literals store no history. |
327 | if (tbi.hasLiteralInTable(u, ROSE_EVENT)) { |
328 | return ROSE_ROLE_HISTORY_NONE; |
329 | } |
330 | |
331 | // Trivial case: fixed offset from anchor |
332 | if (g[u].fixedOffset()) { |
333 | return ROSE_ROLE_HISTORY_ANCH; |
334 | } |
335 | |
336 | // If the bounds are {0,0}, this role can only match precisely at EOD. |
337 | if (minBound == 0 && maxBound == 0) { |
338 | /* last byte history will squash the state byte so cannot have other |
339 | * succ */ |
340 | assert(out_degree(u, g) == 1); |
341 | return ROSE_ROLE_HISTORY_LAST_BYTE; |
342 | } |
343 | |
344 | // XXX: No other history schemes should be possible any longer. |
345 | assert(0); |
346 | } |
347 | |
348 | // Non-EOD cases. |
349 | |
350 | DEBUG_PRINTF("examining edge [%zu,%zu] with bounds {%u,%u}\n" , |
351 | g[u].index, g[v].index, g[e].minBound, g[e].maxBound); |
352 | |
353 | if (tbi.isAnchored(v)) { |
354 | // Matches for literals in the anchored table will always arrive at the |
355 | // right offsets, so there's no need for history-based confirmation. |
356 | DEBUG_PRINTF("v in anchored table, no need for history\n" ); |
357 | assert(u == tbi.anchored_root); |
358 | return ROSE_ROLE_HISTORY_NONE; |
359 | } |
360 | |
361 | if (g[u].fixedOffset() && |
362 | (g[e].minBound || g[e].maxBound != ROSE_BOUND_INF)) { |
363 | DEBUG_PRINTF("fixed offset -> anch\n" ); |
364 | return ROSE_ROLE_HISTORY_ANCH; |
365 | } |
366 | |
367 | return ROSE_ROLE_HISTORY_NONE; |
368 | } |
369 | |
370 | static |
371 | void assignHistories(RoseBuildImpl &tbi) { |
372 | for (const auto &e : edges_range(tbi.g)) { |
373 | if (tbi.g[e].history == ROSE_ROLE_HISTORY_INVALID) { |
374 | tbi.g[e].history = findHistoryScheme(tbi, e); |
375 | } |
376 | } |
377 | } |
378 | |
379 | bool RoseBuildImpl::isDirectReport(u32 id) const { |
380 | assert(id < literal_info.size()); |
381 | |
382 | // Literal info properties. |
383 | const rose_literal_info &info = literal_info[id]; |
384 | if (info.vertices.empty()) { |
385 | return false; |
386 | } |
387 | |
388 | if (!info.delayed_ids.empty() /* dr's don't set groups */ |
389 | || info.requires_benefits) { /* dr's don't require confirm */ |
390 | return false; |
391 | } |
392 | |
393 | if (isDelayed(id)) { /* can't handle delayed dr atm as we require delay |
394 | * ids to be dense */ |
395 | return false; |
396 | } |
397 | |
398 | // Role properties. |
399 | |
400 | // Note that a literal can have multiple roles and still be a direct |
401 | // report; it'll become a multi-direct report ("MDR") that fires each |
402 | // role's reports from a list. |
403 | |
404 | for (auto v : info.vertices) { |
405 | assert(contains(g[v].literals, id)); |
406 | |
407 | if (g[v].reports.empty() || |
408 | g[v].eod_accept || // no accept EOD |
409 | !g[v].isBoring() || |
410 | !isLeafNode(v, g) || // Must have no out-edges |
411 | in_degree(v, g) != 1) { // Role must have exactly one in-edge |
412 | return false; |
413 | } |
414 | |
415 | // Use the program to handle cases that aren't external reports. |
416 | for (const ReportID &rid : g[v].reports) { |
417 | if (!isExternalReport(rm.getReport(rid))) { |
418 | return false; |
419 | } |
420 | } |
421 | |
422 | if (literals.at(id).table == ROSE_ANCHORED) { |
423 | /* in-edges are irrelevant for anchored region. */ |
424 | continue; |
425 | } |
426 | |
427 | /* The in-edge must be an (0, inf) edge from root. */ |
428 | assert(in_degree(v, g) != 0); |
429 | RoseEdge e = *(in_edges(v, g).first); |
430 | if (source(e, g) != root || g[e].minBound != 0 || |
431 | g[e].maxBound != ROSE_BOUND_INF) { |
432 | return false; |
433 | } |
434 | |
435 | // Note: we allow ekeys; they will result in unused roles being built as |
436 | // direct reporting will be used when actually matching in Rose. |
437 | /* TODO: prevent roles being created */ |
438 | } |
439 | |
440 | DEBUG_PRINTF("literal %u ('%s') is a %s report\n" , id, |
441 | dumpString(literals.at(id).s).c_str(), |
442 | info.vertices.size() > 1 ? "multi-direct" : "direct" ); |
443 | return true; |
444 | } |
445 | |
446 | |
447 | /* If we have prefixes that can squash all the floating roots, we can have a |
448 | * somewhat-conditional floating table. As we can't yet look at squash_masks, we |
449 | * have to make some guess as to if we are in this case but the win for not |
450 | * running a floating table over a large portion of the stream is significantly |
451 | * larger than avoiding running an eod table over the last N bytes. */ |
452 | static |
453 | bool checkFloatingKillableByPrefixes(const RoseBuildImpl &tbi) { |
454 | for (auto v : vertices_range(tbi.g)) { |
455 | if (!tbi.isRootSuccessor(v)) { |
456 | continue; |
457 | } |
458 | |
459 | if (!tbi.isFloating(v)) { |
460 | continue; |
461 | } |
462 | |
463 | if (!tbi.g[v].left) { |
464 | DEBUG_PRINTF("unguarded floating root\n" ); |
465 | return false; |
466 | } |
467 | |
468 | if (tbi.g[v].left.graph) { |
469 | const NGHolder &h = *tbi.g[v].left.graph; |
470 | if (proper_out_degree(h.startDs, h)) { |
471 | DEBUG_PRINTF("floating nfa prefix, won't die\n" ); |
472 | return false; |
473 | } |
474 | } else if (tbi.g[v].left.dfa) { |
475 | if (tbi.g[v].left.dfa->start_floating != DEAD_STATE) { |
476 | DEBUG_PRINTF("floating dfa prefix, won't die\n" ); |
477 | return false; |
478 | } |
479 | } |
480 | } |
481 | |
482 | return true; |
483 | } |
484 | |
485 | static |
486 | bool checkEodStealFloating(const RoseBuildImpl &build, |
487 | const vector<u32> &eodLiteralsForFloating, |
488 | u32 numFloatingLiterals, |
489 | size_t shortestFloatingLen) { |
490 | if (eodLiteralsForFloating.empty()) { |
491 | DEBUG_PRINTF("no eod literals\n" ); |
492 | return true; |
493 | } |
494 | |
495 | if (!numFloatingLiterals) { |
496 | DEBUG_PRINTF("no floating table\n" ); |
497 | return false; |
498 | } |
499 | |
500 | if (build.hasNoFloatingRoots()) { |
501 | DEBUG_PRINTF("skipping as floating table is conditional\n" ); |
502 | /* TODO: investigate putting stuff in atable */ |
503 | return false; |
504 | } |
505 | |
506 | if (checkFloatingKillableByPrefixes(build)) { |
507 | DEBUG_PRINTF("skipping as prefixes may make ftable conditional\n" ); |
508 | return false; |
509 | } |
510 | |
511 | // Collect a set of all floating literals. |
512 | unordered_set<ue2_literal> floating_lits; |
513 | for (auto &lit : build.literals) { |
514 | if (lit.table == ROSE_FLOATING) { |
515 | floating_lits.insert(lit.s); |
516 | } |
517 | } |
518 | |
519 | DEBUG_PRINTF("%zu are eod literals, %u floating; floating len=%zu\n" , |
520 | eodLiteralsForFloating.size(), numFloatingLiterals, |
521 | shortestFloatingLen); |
522 | u32 new_floating_lits = 0; |
523 | |
524 | for (u32 eod_id : eodLiteralsForFloating) { |
525 | const rose_literal_id &lit = build.literals.at(eod_id); |
526 | DEBUG_PRINTF("checking '%s'\n" , dumpString(lit.s).c_str()); |
527 | |
528 | if (contains(floating_lits, lit.s)) { |
529 | DEBUG_PRINTF("skip; there is already a floating version\n" ); |
530 | continue; |
531 | } |
532 | |
533 | // Don't want to make the shortest floating literal shorter/worse. |
534 | if (trailerDueToSelf(lit) < 4 || lit.s.length() < shortestFloatingLen) { |
535 | DEBUG_PRINTF("len=%zu, selfOverlap=%zu\n" , lit.s.length(), |
536 | trailerDueToSelf(lit)); |
537 | DEBUG_PRINTF("would shorten, bailing\n" ); |
538 | return false; |
539 | } |
540 | |
541 | new_floating_lits++; |
542 | } |
543 | DEBUG_PRINTF("..would require %u new floating literals\n" , |
544 | new_floating_lits); |
545 | |
546 | // Magic number thresholds: we only want to get rid of our EOD table if it |
547 | // would make no real difference to the FDR. |
548 | if (numFloatingLiterals / 8 < new_floating_lits |
549 | && (new_floating_lits > 3 || numFloatingLiterals <= 2)) { |
550 | DEBUG_PRINTF("leaving eod table alone.\n" ); |
551 | return false; |
552 | } |
553 | |
554 | return true; |
555 | } |
556 | |
557 | static |
558 | void promoteEodToFloating(RoseBuildImpl &tbi, const vector<u32> &eodLiterals) { |
559 | DEBUG_PRINTF("promoting %zu eod literals to floating table\n" , |
560 | eodLiterals.size()); |
561 | |
562 | for (u32 eod_id : eodLiterals) { |
563 | const rose_literal_id &lit = tbi.literals.at(eod_id); |
564 | DEBUG_PRINTF("eod_id=%u, lit=%s\n" , eod_id, dumpString(lit.s).c_str()); |
565 | u32 floating_id = tbi.getLiteralId(lit.s, lit.msk, lit.cmp, lit.delay, |
566 | ROSE_FLOATING); |
567 | DEBUG_PRINTF("floating_id=%u, lit=%s\n" , floating_id, |
568 | dumpString(tbi.literals.at(floating_id).s).c_str()); |
569 | auto &float_verts = tbi.literal_info[floating_id].vertices; |
570 | auto &eod_verts = tbi.literal_info[eod_id].vertices; |
571 | |
572 | insert(&float_verts, eod_verts); |
573 | eod_verts.clear(); |
574 | |
575 | DEBUG_PRINTF("eod_lit=%u -> float_lit=%u\n" , eod_id, floating_id); |
576 | |
577 | for (auto v : float_verts) { |
578 | tbi.g[v].literals.erase(eod_id); |
579 | tbi.g[v].literals.insert(floating_id); |
580 | } |
581 | |
582 | tbi.literal_info[floating_id].requires_benefits |
583 | = tbi.literal_info[eod_id].requires_benefits; |
584 | } |
585 | } |
586 | |
587 | static |
588 | bool promoteEodToAnchored(RoseBuildImpl &tbi, const vector<u32> &eodLiterals) { |
589 | DEBUG_PRINTF("promoting eod literals to anchored table\n" ); |
590 | bool rv = true; |
591 | |
592 | for (u32 eod_id : eodLiterals) { |
593 | const rose_literal_id &lit = tbi.literals.at(eod_id); |
594 | |
595 | NGHolder h; |
596 | add_edge(h.start, h.accept, h); |
597 | appendLiteral(h, lit.s); /* we only accept cases which are anchored |
598 | * hard up against start */ |
599 | |
600 | u32 a_id = tbi.getNewLiteralId(); |
601 | u32 remap_id = 0; |
602 | DEBUG_PRINTF(" trying to add dfa stuff\n" ); |
603 | int anch_ok = addToAnchoredMatcher(tbi, h, a_id, &remap_id); |
604 | |
605 | if (anch_ok == ANCHORED_FAIL) { |
606 | DEBUG_PRINTF("failed to promote to anchored need to keep etable\n" ); |
607 | rv = false; |
608 | continue; |
609 | } else if (anch_ok == ANCHORED_REMAP) { |
610 | DEBUG_PRINTF("remapped\n" ); |
611 | a_id = remap_id; |
612 | } else { |
613 | assert(anch_ok == ANCHORED_SUCCESS); |
614 | } |
615 | |
616 | // Store the literal itself in a side structure so that we can use it |
617 | // for overlap calculations later. This may be obsolete when the old |
618 | // Rose construction path (and its history selection code) goes away. |
619 | tbi.anchoredLitSuffix.insert(make_pair(a_id, lit)); |
620 | |
621 | auto &a_verts = tbi.literal_info[a_id].vertices; |
622 | auto &eod_verts = tbi.literal_info[eod_id].vertices; |
623 | |
624 | for (auto v : eod_verts) { |
625 | for (const auto &e : in_edges_range(v, tbi.g)) { |
626 | assert(tbi.g[e].maxBound != ROSE_BOUND_INF); |
627 | tbi.g[e].minBound += lit.s.length(); |
628 | tbi.g[e].maxBound += lit.s.length(); |
629 | } |
630 | } |
631 | |
632 | insert(&a_verts, eod_verts); |
633 | eod_verts.clear(); |
634 | |
635 | for (auto v : a_verts) { |
636 | tbi.g[v].literals.erase(eod_id); |
637 | tbi.g[v].literals.insert(a_id); |
638 | } |
639 | } |
640 | |
641 | return rv; |
642 | } |
643 | |
644 | static |
645 | bool suitableForAnchored(const RoseBuildImpl &tbi, const rose_literal_id &l_id, |
646 | const rose_literal_info &lit) { |
647 | const RoseGraph &g = tbi.g; |
648 | |
649 | bool seen = false; |
650 | u32 min_offset = 0; |
651 | u32 max_offset = 0; |
652 | |
653 | if (!lit.delayed_ids.empty() || l_id.delay) { |
654 | DEBUG_PRINTF("delay\n" ); |
655 | return false; |
656 | } |
657 | |
658 | if (!l_id.msk.empty()) { |
659 | DEBUG_PRINTF("msk\n" ); |
660 | return false; |
661 | } |
662 | |
663 | for (auto v : lit.vertices) { |
664 | if (!seen) { |
665 | min_offset = g[v].min_offset; |
666 | max_offset = g[v].max_offset; |
667 | seen = true; |
668 | |
669 | if (max_offset > tbi.cc.grey.maxAnchoredRegion) { |
670 | DEBUG_PRINTF("too deep %u\n" , max_offset); |
671 | return false; |
672 | } |
673 | } |
674 | |
675 | if (max_offset != g[v].max_offset || min_offset != g[v].min_offset) { |
676 | DEBUG_PRINTF(":(\n" ); |
677 | return false; |
678 | } |
679 | |
680 | if (!g[v].isBoring()) { |
681 | DEBUG_PRINTF(":(\n" ); |
682 | return false; |
683 | } |
684 | |
685 | if (g[v].literals.size() != 1) { |
686 | DEBUG_PRINTF("shared\n" ); |
687 | return false; |
688 | } |
689 | |
690 | if (tbi.isNonRootSuccessor(v)) { |
691 | DEBUG_PRINTF("non root\n" ); |
692 | return false; |
693 | } |
694 | |
695 | if (max_offset != l_id.s.length() || min_offset != l_id.s.length()) { |
696 | DEBUG_PRINTF("|%zu| (%u,%u):(\n" , l_id.s.length(), min_offset, |
697 | max_offset); |
698 | /* TODO: handle cases with small bounds */ |
699 | return false; |
700 | } |
701 | |
702 | for (auto w : adjacent_vertices_range(v, g)) { |
703 | if (!g[w].eod_accept) { |
704 | DEBUG_PRINTF("non eod accept literal\n" ); |
705 | return false; |
706 | } |
707 | } |
708 | } |
709 | return true; |
710 | } |
711 | |
712 | // If we've got a small number of long, innocuous EOD literals and a large |
713 | // floating table, we consider promoting those EOD literals to the floating |
714 | // table to avoid having to run both. See UE-2069, consider deleting this and |
715 | // replacing with an elegant reverse DFA. |
716 | /* We do not want to do this if we would otherwise avoid running the floating |
717 | * table altogether. */ |
718 | static |
719 | void stealEodVertices(RoseBuildImpl &tbi) { |
720 | u32 numFloatingLiterals = 0; |
721 | u32 numAnchoredLiterals = 0; |
722 | size_t shortestFloatingLen = SIZE_MAX; |
723 | vector<u32> eodLiteralsForFloating; |
724 | vector<u32> eodLiteralsForAnchored; |
725 | DEBUG_PRINTF("hi\n" ); |
726 | |
727 | for (u32 i = 0; i < tbi.literal_info.size(); i++) { |
728 | const auto &info = tbi.literal_info[i]; |
729 | if (info.vertices.empty()) { |
730 | continue; // skip unused literals |
731 | } |
732 | |
733 | const rose_literal_id &lit = tbi.literals.at(i); |
734 | |
735 | if (lit.table == ROSE_EOD_ANCHORED) { |
736 | if (suitableForAnchored(tbi, lit, info)) { |
737 | eodLiteralsForAnchored.push_back(i); |
738 | } else { |
739 | eodLiteralsForFloating.push_back(i); |
740 | } |
741 | } else if (lit.table == ROSE_FLOATING) { |
742 | numFloatingLiterals++; |
743 | shortestFloatingLen = min(shortestFloatingLen, lit.s.length()); |
744 | } else if (lit.table == ROSE_ANCHORED) { |
745 | numAnchoredLiterals++; |
746 | } |
747 | } |
748 | |
749 | /* given a choice of having either an eod table or an anchored table, we |
750 | * always favour having an anchored table */ |
751 | |
752 | if (!checkEodStealFloating(tbi, eodLiteralsForFloating, numFloatingLiterals, |
753 | shortestFloatingLen)) { |
754 | DEBUG_PRINTF("removing etable weakens ftable\n" ); |
755 | return; |
756 | } |
757 | |
758 | promoteEodToFloating(tbi, eodLiteralsForFloating); |
759 | |
760 | if (!promoteEodToAnchored(tbi, eodLiteralsForAnchored)) { |
761 | DEBUG_PRINTF("still need ematcher\n" ); |
762 | return; |
763 | } |
764 | |
765 | // We're no longer using the EOD matcher. |
766 | tbi.ematcher_region_size = 0; |
767 | } |
768 | |
769 | bool RoseBuildImpl::isDelayed(u32 id) const { |
770 | return literal_info.at(id).undelayed_id != id; |
771 | } |
772 | |
773 | bool RoseBuildImpl::hasDelayedLiteral(RoseVertex v) const { |
774 | for (u32 lit_id : g[v].literals) { |
775 | if (literals.at(lit_id).delay) { |
776 | return true; |
777 | } |
778 | } |
779 | |
780 | return false; |
781 | } |
782 | |
783 | bool RoseBuildImpl::hasDelayPred(RoseVertex v) const { |
784 | for (auto u : inv_adjacent_vertices_range(v, g)) { |
785 | if (hasDelayedLiteral(u)) { |
786 | return true; |
787 | } |
788 | } |
789 | |
790 | return false; |
791 | } |
792 | |
793 | bool RoseBuildImpl::hasAnchoredTablePred(RoseVertex v) const { |
794 | for (auto u : inv_adjacent_vertices_range(v, g)) { |
795 | if (isAnchored(u)) { |
796 | return true; |
797 | } |
798 | } |
799 | |
800 | return false; |
801 | } |
802 | |
803 | void RoseBuildImpl::findTransientLeftfixes(void) { |
804 | for (auto v : vertices_range(g)) { |
805 | if (!g[v].left) { |
806 | continue; |
807 | } |
808 | |
809 | /* infixes can never (or at least not yet) be transient */ |
810 | if (isNonRootSuccessor(v)) { |
811 | continue; |
812 | } |
813 | |
814 | const left_id &left(g[v].left); |
815 | |
816 | if (::ue2::isAnchored(left) && !isInETable(v)) { |
817 | /* etable prefixes currently MUST be transient as we do not know |
818 | * where we can safely catch them up to (yet). */ |
819 | DEBUG_PRINTF("anchored roses in rocky soil are not fleeting\n" ); |
820 | continue; |
821 | } |
822 | |
823 | const depth max_width = findMaxWidth(left); |
824 | if (!max_width.is_finite()) { |
825 | DEBUG_PRINTF("inf max width\n" ); |
826 | continue; |
827 | } |
828 | |
829 | if (cc.streaming) { |
830 | /* STREAMING: transient prefixes must be able to run using history |
831 | * rather than storing state. */ |
832 | u32 his = g[v].left.lag + max_width; |
833 | |
834 | // If this vertex has an event literal, we need to add one to cope |
835 | // with it. |
836 | if (hasLiteralInTable(v, ROSE_EVENT)) { |
837 | his++; |
838 | } |
839 | |
840 | /* +1 as trigger must appear in main buffer and no byte is needed to |
841 | * decompress the state */ |
842 | if (his <= cc.grey.maxHistoryAvailable + 1) { |
843 | transient.insert(left); |
844 | DEBUG_PRINTF("a transient leftfix spotted his=%u\n" , his); |
845 | } |
846 | } else { |
847 | /* BLOCK: transientness is less important and more fuzzy, ideally |
848 | * it should be quick to calculate the state. No need to worry about |
849 | * history (and hence lag). */ |
850 | if (max_width < depth(ROSE_BLOCK_TRANSIENT_MAX_WIDTH)) { |
851 | transient.insert(left); |
852 | DEBUG_PRINTF("a transient block leftfix spotted [%u]\n" , |
853 | (u32)max_width); |
854 | } |
855 | } |
856 | } |
857 | } |
858 | |
859 | /** Find all the different roses and their associated literals. */ |
860 | static |
861 | map<left_id, vector<RoseVertex>> findLeftSucc(const RoseBuildImpl &build) { |
862 | map<left_id, vector<RoseVertex>> leftfixes; |
863 | for (auto v : vertices_range(build.g)) { |
864 | if (build.g[v].left) { |
865 | const LeftEngInfo &lei = build.g[v].left; |
866 | leftfixes[lei].push_back(v); |
867 | } |
868 | } |
869 | return leftfixes; |
870 | } |
871 | |
872 | namespace { |
873 | struct infix_info { |
874 | set<RoseVertex> preds; |
875 | set<RoseVertex> succs; |
876 | }; |
877 | } |
878 | |
879 | static |
880 | map<NGHolder *, infix_info> findInfixGraphInfo(const RoseBuildImpl &build) { |
881 | map<NGHolder *, infix_info> rv; |
882 | |
883 | for (auto v : vertices_range(build.g)) { |
884 | if (!build.g[v].left) { |
885 | continue; |
886 | } |
887 | |
888 | if (build.isRootSuccessor(v)) { |
889 | DEBUG_PRINTF("a prefix is never an infix\n" ); |
890 | continue; |
891 | } |
892 | |
893 | /* ensure only proper nfas */ |
894 | const LeftEngInfo &lei = build.g[v].left; |
895 | if (!lei.graph) { |
896 | continue; |
897 | } |
898 | if (lei.haig || lei.dfa) { |
899 | continue; |
900 | } |
901 | assert(!lei.castle); |
902 | infix_info &info = rv[lei.graph.get()]; |
903 | insert(&info.preds, inv_adjacent_vertices_range(v, build.g)); |
904 | info.succs.insert(v); |
905 | } |
906 | |
907 | return rv; |
908 | } |
909 | |
910 | static |
911 | map<u32, flat_set<NFAEdge>> getTopInfo(const NGHolder &h) { |
912 | map<u32, flat_set<NFAEdge>> rv; |
913 | for (NFAEdge e : out_edges_range(h.start, h)) { |
914 | for (u32 t : h[e].tops) { |
915 | rv[t].insert(e); |
916 | } |
917 | } |
918 | return rv; |
919 | } |
920 | |
921 | static |
922 | u32 findUnusedTop(const map<u32, flat_set<NFAEdge>> &tops) { |
923 | u32 i = 0; |
924 | while (contains(tops, i)) { |
925 | i++; |
926 | } |
927 | return i; |
928 | } |
929 | |
930 | static |
931 | bool reduceTopTriggerLoad(RoseBuildImpl &build, NGHolder &h, RoseVertex u) { |
932 | RoseGraph &g = build.g; |
933 | |
934 | set<u32> tops; /* tops triggered by u */ |
935 | for (RoseEdge e : out_edges_range(u, g)) { |
936 | RoseVertex v = target(e, g); |
937 | if (g[v].left.graph.get() != &h) { |
938 | continue; |
939 | } |
940 | tops.insert(g[e].rose_top); |
941 | } |
942 | |
943 | assert(!tops.empty()); |
944 | if (tops.size() <= 1) { |
945 | return false; |
946 | } |
947 | DEBUG_PRINTF("%zu triggers %zu tops for %p\n" , build.g[u].index, |
948 | tops.size(), &h); |
949 | |
950 | auto h_top_info = getTopInfo(h); |
951 | flat_set<NFAEdge> edges_to_trigger; |
952 | for (u32 t : tops) { |
953 | insert(&edges_to_trigger, h_top_info[t]); |
954 | } |
955 | |
956 | u32 new_top = ~0U; |
957 | /* check if there is already a top with the right the successor set */ |
958 | for (const auto &elem : h_top_info) { |
959 | if (elem.second == edges_to_trigger) { |
960 | new_top = elem.first; |
961 | break; |
962 | } |
963 | } |
964 | |
965 | /* if no existing suitable top, add a new top for us */ |
966 | if (new_top == ~0U) { |
967 | new_top = findUnusedTop(h_top_info); |
968 | |
969 | /* add top to edges out of start */ |
970 | for (NFAEdge e : out_edges_range(h.start, h)) { |
971 | if (has_intersection(tops, h[e].tops)) { |
972 | h[e].tops.insert(new_top); |
973 | } |
974 | } |
975 | |
976 | /* check still implementable if we add a new top */ |
977 | if (!isImplementableNFA(h, nullptr, build.cc)) { |
978 | DEBUG_PRINTF("unable to add new top\n" ); |
979 | for (NFAEdge e : out_edges_range(h.start, h)) { |
980 | h[e].tops.erase(new_top); |
981 | } |
982 | /* we should be back to the original graph */ |
983 | assert(isImplementableNFA(h, nullptr, build.cc)); |
984 | return false; |
985 | } |
986 | } |
987 | |
988 | DEBUG_PRINTF("using new merged top %u\n" , new_top); |
989 | assert(new_top != ~0U); |
990 | for (RoseEdge e: out_edges_range(u, g)) { |
991 | RoseVertex v = target(e, g); |
992 | if (g[v].left.graph.get() != &h) { |
993 | continue; |
994 | } |
995 | g[e].rose_top = new_top; |
996 | } |
997 | |
998 | return true; |
999 | } |
1000 | |
1001 | static |
1002 | void packInfixTops(NGHolder &h, RoseGraph &g, |
1003 | const set<RoseVertex> &verts) { |
1004 | if (!is_triggered(h)) { |
1005 | DEBUG_PRINTF("not triggered, no tops\n" ); |
1006 | return; |
1007 | } |
1008 | assert(isCorrectlyTopped(h)); |
1009 | DEBUG_PRINTF("pruning unused tops\n" ); |
1010 | flat_set<u32> used_tops; |
1011 | for (auto v : verts) { |
1012 | assert(g[v].left.graph.get() == &h); |
1013 | |
1014 | for (const auto &e : in_edges_range(v, g)) { |
1015 | u32 top = g[e].rose_top; |
1016 | used_tops.insert(top); |
1017 | } |
1018 | } |
1019 | |
1020 | map<u32, u32> top_mapping; |
1021 | for (u32 t : used_tops) { |
1022 | u32 new_top = top_mapping.size(); |
1023 | top_mapping[t] = new_top; |
1024 | } |
1025 | |
1026 | for (auto v : verts) { |
1027 | assert(g[v].left.graph.get() == &h); |
1028 | |
1029 | for (const auto &e : in_edges_range(v, g)) { |
1030 | g[e].rose_top = top_mapping.at(g[e].rose_top); |
1031 | } |
1032 | } |
1033 | |
1034 | vector<NFAEdge> dead; |
1035 | for (const auto &e : out_edges_range(h.start, h)) { |
1036 | NFAVertex v = target(e, h); |
1037 | if (v == h.startDs) { |
1038 | continue; // stylised edge, leave it alone. |
1039 | } |
1040 | flat_set<u32> updated_tops; |
1041 | for (u32 t : h[e].tops) { |
1042 | if (contains(top_mapping, t)) { |
1043 | updated_tops.insert(top_mapping.at(t)); |
1044 | } |
1045 | } |
1046 | h[e].tops = std::move(updated_tops); |
1047 | if (h[e].tops.empty()) { |
1048 | DEBUG_PRINTF("edge (start,%zu) has only unused tops\n" , h[v].index); |
1049 | dead.push_back(e); |
1050 | } |
1051 | } |
1052 | |
1053 | if (dead.empty()) { |
1054 | return; |
1055 | } |
1056 | |
1057 | remove_edges(dead, h); |
1058 | pruneUseless(h); |
1059 | clearReports(h); // As we may have removed vacuous edges. |
1060 | } |
1061 | |
1062 | static |
1063 | void reduceTopTriggerLoad(RoseBuildImpl &build) { |
1064 | auto infixes = findInfixGraphInfo(build); |
1065 | |
1066 | for (auto &p : infixes) { |
1067 | if (onlyOneTop(*p.first)) { |
1068 | continue; |
1069 | } |
1070 | |
1071 | bool changed = false; |
1072 | for (RoseVertex v : p.second.preds) { |
1073 | changed |= reduceTopTriggerLoad(build, *p.first, v); |
1074 | } |
1075 | |
1076 | if (changed) { |
1077 | packInfixTops(*p.first, build.g, p.second.succs); |
1078 | reduceImplementableGraph(*p.first, SOM_NONE, nullptr, build.cc); |
1079 | } |
1080 | } |
1081 | } |
1082 | |
1083 | static |
1084 | bool triggerKillsRoseGraph(const RoseBuildImpl &build, const left_id &left, |
1085 | const set<ue2_literal> &all_lits, |
1086 | const RoseEdge &e) { |
1087 | assert(left.graph()); |
1088 | const NGHolder &h = *left.graph(); |
1089 | |
1090 | flat_set<NFAVertex> all_states; |
1091 | insert(&all_states, vertices(h)); |
1092 | assert(out_degree(h.startDs, h) == 1); /* triggered don't use sds */ |
1093 | DEBUG_PRINTF("removing sds\n" ); |
1094 | all_states.erase(h.startDs); |
1095 | |
1096 | flat_set<NFAVertex> states; |
1097 | |
1098 | /* check each pred literal to see if they all kill previous graph |
1099 | * state */ |
1100 | for (u32 lit_id : build.g[source(e, build.g)].literals) { |
1101 | const rose_literal_id &pred_lit = build.literals.at(lit_id); |
1102 | const ue2_literal s = findNonOverlappingTail(all_lits, pred_lit.s); |
1103 | |
1104 | DEBUG_PRINTF("running graph %zu\n" , states.size()); |
1105 | states = execute_graph(h, s, all_states, true); |
1106 | DEBUG_PRINTF("ran, %zu states on\n" , states.size()); |
1107 | |
1108 | if (!states.empty()) { |
1109 | return false; |
1110 | } |
1111 | } |
1112 | |
1113 | return true; |
1114 | } |
1115 | |
1116 | static |
1117 | bool triggerKillsRose(const RoseBuildImpl &build, const left_id &left, |
1118 | const set<ue2_literal> &all_lits, const RoseEdge &e) { |
1119 | if (left.haig()) { |
1120 | /* TODO: To allow this for som-based engines we would also need to |
1121 | * ensure as well that no other triggers can occur at the same location |
1122 | * with a different som. */ |
1123 | return false; |
1124 | } |
1125 | |
1126 | if (left.graph()) { |
1127 | return triggerKillsRoseGraph(build, left, all_lits, e); |
1128 | } |
1129 | |
1130 | if (left.castle()) { |
1131 | return triggerKillsRoseCastle(build, left, all_lits, e); |
1132 | } |
1133 | |
1134 | return false; |
1135 | } |
1136 | |
1137 | /* Sometimes the arrival of a top for a rose infix can ensure that the nfa would |
1138 | * be dead at that time. In the case of multiple trigger literals, we can only |
1139 | * base our decision on that portion of literal after any overlapping literals. |
1140 | */ |
1141 | static |
1142 | void findTopTriggerCancels(RoseBuildImpl &build) { |
1143 | auto left_succ = findLeftSucc(build); /* leftfixes -> succ verts */ |
1144 | |
1145 | for (const auto &r : left_succ) { |
1146 | const left_id &left = r.first; |
1147 | const vector<RoseVertex> &succs = r.second; |
1148 | |
1149 | assert(!succs.empty()); |
1150 | if (build.isRootSuccessor(*succs.begin())) { |
1151 | /* a prefix is never an infix */ |
1152 | continue; |
1153 | } |
1154 | |
1155 | set<u32> tops_seen; |
1156 | set<RoseEdge> rose_edges; |
1157 | set<u32> pred_lit_ids; |
1158 | |
1159 | for (auto v : succs) { |
1160 | for (const auto &e : in_edges_range(v, build.g)) { |
1161 | RoseVertex u = source(e, build.g); |
1162 | tops_seen.insert(build.g[e].rose_top); |
1163 | insert(&pred_lit_ids, build.g[u].literals); |
1164 | rose_edges.insert(e); |
1165 | } |
1166 | } |
1167 | |
1168 | set<ue2_literal> all_lits; |
1169 | |
1170 | if (tops_seen.size() > 1) { |
1171 | goto next_rose; /* slightly tricky to deal with overlap case */ |
1172 | } |
1173 | |
1174 | for (u32 lit_id : pred_lit_ids) { |
1175 | const rose_literal_id &p_lit = build.literals.at(lit_id); |
1176 | if (p_lit.delay || p_lit.table == ROSE_ANCHORED) { |
1177 | goto next_rose; |
1178 | } |
1179 | all_lits.insert(p_lit.s); |
1180 | DEBUG_PRINTF("trigger: '%s'\n" , dumpString(p_lit.s).c_str()); |
1181 | } |
1182 | |
1183 | DEBUG_PRINTF("rose has %zu trigger literals, %zu edges\n" , |
1184 | all_lits.size(), rose_edges.size()); |
1185 | |
1186 | for (const auto &e : rose_edges) { |
1187 | if (triggerKillsRose(build, left, all_lits, e)) { |
1188 | DEBUG_PRINTF("top will override previous rose state\n" ); |
1189 | build.g[e].rose_cancel_prev_top = true; |
1190 | } |
1191 | } |
1192 | next_rose:; |
1193 | } |
1194 | } |
1195 | |
1196 | static |
1197 | void optimiseRoseTops(RoseBuildImpl &build) { |
1198 | reduceTopTriggerLoad(build); |
1199 | /* prune unused tops ? */ |
1200 | findTopTriggerCancels(build); |
1201 | } |
1202 | |
1203 | static |
1204 | void buildRoseSquashMasks(RoseBuildImpl &tbi) { |
1205 | /* Rose nfa squash masks are applied to the groups when the nfa can no |
1206 | * longer match */ |
1207 | |
1208 | map<left_id, vector<RoseVertex>> roses = |
1209 | findLeftSucc(tbi); /* rose -> succ verts */ |
1210 | |
1211 | /* a rose nfa can squash a group if all literals in that group are a |
1212 | * successor of the nfa and all the literals */ |
1213 | for (const auto &e : roses) { |
1214 | const left_id &left = e.first; |
1215 | const vector<RoseVertex> &succs = e.second; |
1216 | |
1217 | set<u32> lit_ids; |
1218 | bool anchored_pred = false; |
1219 | for (auto v : succs) { |
1220 | lit_ids.insert(tbi.g[v].literals.begin(), tbi.g[v].literals.end()); |
1221 | for (auto u : inv_adjacent_vertices_range(v, tbi.g)) { |
1222 | anchored_pred |= tbi.isAnchored(u); |
1223 | } |
1224 | } |
1225 | |
1226 | /* Due to the anchored table not being able to set groups again, |
1227 | * we cannot use a rose nfa for group squashing if it is being triggered |
1228 | * from the anchored table and can match more than once. */ |
1229 | |
1230 | if (anchored_pred) { /* infix with pred in anchored table */ |
1231 | u32 min_off = ~0U; |
1232 | u32 max_off = 0U; |
1233 | for (auto v : succs) { |
1234 | for (auto u : inv_adjacent_vertices_range(v, tbi.g)) { |
1235 | min_off = min(min_off, tbi.g[u].min_offset); |
1236 | max_off = max(max_off, tbi.g[u].max_offset); |
1237 | } |
1238 | } |
1239 | if (min_off != max_off) { |
1240 | /* leave all groups alone */ |
1241 | tbi.rose_squash_masks[left] = ~0ULL; |
1242 | continue; |
1243 | } |
1244 | } |
1245 | |
1246 | rose_group unsquashable = tbi.boundary_group_mask; |
1247 | |
1248 | for (u32 lit_id : lit_ids) { |
1249 | const rose_literal_info &info = tbi.literal_info[lit_id]; |
1250 | if (!info.delayed_ids.empty() |
1251 | || !all_of_in(info.vertices, |
1252 | [&](RoseVertex v) { |
1253 | return left == tbi.g[v].left; })) { |
1254 | DEBUG_PRINTF("group %llu is unsquashable\n" , info.group_mask); |
1255 | unsquashable |= info.group_mask; |
1256 | } |
1257 | } |
1258 | |
1259 | rose_group squash_mask = ~0ULL; /* leave all groups alone */ |
1260 | |
1261 | for (u32 i = 0; i < ROSE_GROUPS_MAX; i++) { |
1262 | if (is_subset_of(tbi.group_to_literal[i], lit_ids)) { |
1263 | squash_mask &= ~(1ULL << i); |
1264 | } |
1265 | } |
1266 | squash_mask |= unsquashable; |
1267 | tbi.rose_squash_masks[left] = squash_mask; |
1268 | } |
1269 | } |
1270 | |
1271 | static |
1272 | void countFloatingLiterals(const RoseBuildImpl &tbi, u32 *total_count, |
1273 | u32 *short_count) { |
1274 | *total_count = 0; |
1275 | *short_count = 0; |
1276 | for (const rose_literal_id &lit : tbi.literals) { |
1277 | if (lit.delay) { |
1278 | continue; /* delay id's are virtual-ish */ |
1279 | } |
1280 | |
1281 | if (lit.table != ROSE_FLOATING) { |
1282 | continue; /* wrong table */ |
1283 | } |
1284 | |
1285 | ++*total_count; |
1286 | if (lit.s.length() <= ANCHORED_REHOME_SHORT_LEN) { |
1287 | ++*short_count; |
1288 | } |
1289 | } |
1290 | } |
1291 | |
1292 | static |
1293 | void rehomeAnchoredLiteral(RoseBuildImpl &tbi, const simple_anchored_info &sai, |
1294 | const set<u32> &lit_ids) { |
1295 | /* TODO: verify that vertices only have a single literal at the moment */ |
1296 | |
1297 | DEBUG_PRINTF("rehoming ^.{%u,%u}%s\n" , sai.min_bound, sai.max_bound, |
1298 | dumpString(sai.literal).c_str()); |
1299 | |
1300 | /* Get a floating literal corresponding to the anchored literal */ |
1301 | u32 new_literal_id = tbi.getLiteralId(sai.literal, 0, ROSE_FLOATING); |
1302 | rose_literal_info &new_lit_info = tbi.literal_info[new_literal_id]; |
1303 | DEBUG_PRINTF("floating literal id -> %u\n" , new_literal_id); |
1304 | |
1305 | for (u32 lit_id : lit_ids) { |
1306 | rose_literal_info &old_lit_info = tbi.literal_info[lit_id]; |
1307 | assert(old_lit_info.delayed_ids.empty()); |
1308 | |
1309 | for (auto v : old_lit_info.vertices) { |
1310 | /* Transfer vertex over to new literal id */ |
1311 | assert(tbi.g[v].literals.size() == 1); |
1312 | tbi.g[v].literals.clear(); |
1313 | tbi.g[v].literals.insert(new_literal_id); |
1314 | new_lit_info.vertices.insert(v); |
1315 | |
1316 | /* ensure bounds on the vertex's in-edge are correct */ |
1317 | assert(in_degree(v, tbi.g) == 1); |
1318 | const RoseEdge &e = *in_edges(v, tbi.g).first; |
1319 | assert(tbi.g[e].minBound == sai.min_bound + sai.literal.length()); |
1320 | assert(tbi.g[e].maxBound == sai.max_bound + sai.literal.length()); |
1321 | tbi.g[e].minBound = sai.min_bound; |
1322 | tbi.g[e].maxBound = sai.max_bound; |
1323 | } |
1324 | |
1325 | /* mark the old literal as empty */ |
1326 | old_lit_info.vertices.clear(); |
1327 | } |
1328 | } |
1329 | |
1330 | static |
1331 | void rehomeAnchoredLiterals(RoseBuildImpl &tbi) { |
1332 | /* if we have many literals in the floating table, we want to push |
1333 | * literals which are anchored but deep into the floating table as they |
1334 | * are unlikely to reduce the performance of the floating table. */ |
1335 | u32 total_count; |
1336 | u32 short_count; |
1337 | countFloatingLiterals(tbi, &total_count, &short_count); |
1338 | |
1339 | DEBUG_PRINTF("considering rehoming options\n" ); |
1340 | |
1341 | if (total_count < ANCHORED_REHOME_MIN_FLOATING |
1342 | && short_count < ANCHORED_REHOME_MIN_FLOATING_SHORT) { |
1343 | DEBUG_PRINTF("not a heavy case %u %u\n" , total_count, short_count); |
1344 | return; |
1345 | } |
1346 | |
1347 | u32 min_rehome_len = ANCHORED_REHOME_SHORT_LEN + 1; |
1348 | if (short_count >= ANCHORED_REHOME_ALLOW_SHORT) { |
1349 | min_rehome_len--; |
1350 | } |
1351 | |
1352 | for (map<simple_anchored_info, set<u32> >::iterator it |
1353 | = tbi.anchored_simple.begin(); |
1354 | it != tbi.anchored_simple.end();) { |
1355 | if (it->first.max_bound < ANCHORED_REHOME_DEEP |
1356 | || it->first.literal.length() < min_rehome_len) { |
1357 | ++it; |
1358 | continue; |
1359 | } |
1360 | |
1361 | rehomeAnchoredLiteral(tbi, it->first, it->second); |
1362 | tbi.anchored_simple.erase(it++); |
1363 | } |
1364 | } |
1365 | |
1366 | /** \brief Maximum number of single-byte literals to add to the small block |
1367 | * table. */ |
1368 | static const size_t MAX_1BYTE_SMALL_BLOCK_LITERALS = 20; |
1369 | |
1370 | static |
1371 | void addSmallBlockLiteral(RoseBuildImpl &tbi, const simple_anchored_info &sai, |
1372 | const set<u32> &lit_ids) { |
1373 | DEBUG_PRINTF("anchored ^.{%u,%u}%s\n" , sai.min_bound, sai.max_bound, |
1374 | dumpString(sai.literal).c_str()); |
1375 | |
1376 | u32 lit_id = tbi.getLiteralId(sai.literal, 0, ROSE_ANCHORED_SMALL_BLOCK); |
1377 | rose_literal_info &lit_info = tbi.literal_info[lit_id]; |
1378 | DEBUG_PRINTF("anchored small block literal id -> %u\n" , lit_id); |
1379 | |
1380 | RoseGraph &g = tbi.g; |
1381 | const RoseVertex anchored_root = tbi.anchored_root; |
1382 | |
1383 | for (u32 old_id : lit_ids) { |
1384 | assert(old_id < tbi.literal_info.size()); |
1385 | const rose_literal_info &li = tbi.literal_info[old_id]; |
1386 | |
1387 | for (auto lit_v : li.vertices) { |
1388 | // Clone vertex with the new literal ID. |
1389 | RoseVertex v = add_vertex(g[lit_v], g); |
1390 | g[v].literals.clear(); |
1391 | g[v].literals.insert(lit_id); |
1392 | g[v].min_offset = sai.min_bound + sai.literal.length(); |
1393 | g[v].max_offset = sai.max_bound + sai.literal.length(); |
1394 | lit_info.vertices.insert(v); |
1395 | |
1396 | RoseEdge e = add_edge(anchored_root, v, g); |
1397 | g[e].minBound = sai.min_bound; |
1398 | g[e].maxBound = sai.max_bound; |
1399 | } |
1400 | } |
1401 | } |
1402 | |
1403 | static |
1404 | void addSmallBlockLiteral(RoseBuildImpl &tbi, const ue2_literal &lit, |
1405 | const flat_set<ReportID> &reports) { |
1406 | DEBUG_PRINTF("lit %s, reports: %s\n" , dumpString(lit).c_str(), |
1407 | as_string_list(reports).c_str()); |
1408 | assert(!reports.empty()); |
1409 | |
1410 | u32 lit_id = tbi.getLiteralId(lit, 0, ROSE_ANCHORED_SMALL_BLOCK); |
1411 | assert(lit_id < tbi.literal_info.size()); |
1412 | rose_literal_info &lit_info = tbi.literal_info[lit_id]; |
1413 | |
1414 | RoseGraph &g = tbi.g; |
1415 | |
1416 | RoseVertex v = add_vertex(g); |
1417 | g[v].literals.insert(lit_id); |
1418 | g[v].reports = reports; |
1419 | |
1420 | RoseEdge e = add_edge(tbi.root, v, g); |
1421 | g[e].minBound = 0; |
1422 | g[e].maxBound = ROSE_BOUND_INF; |
1423 | g[v].min_offset = 1; |
1424 | g[v].max_offset = ROSE_BOUND_INF; |
1425 | lit_info.vertices.insert(v); |
1426 | } |
1427 | |
1428 | static |
1429 | bool stateIsSEPLiteral(const dstate_id_t &s, const symbol_t &sym, |
1430 | const raw_dfa &rdfa) { |
1431 | const dstate &ds = rdfa.states[s]; |
1432 | if (!ds.reports_eod.empty() || ds.reports.empty()) { |
1433 | DEBUG_PRINTF("badly formed reports\n" ); |
1434 | return false; |
1435 | } |
1436 | |
1437 | DEBUG_PRINTF("examine state %u reached by sym %u\n" , s, sym); |
1438 | |
1439 | for (symbol_t i = 0; i < rdfa.getImplAlphaSize(); i++) { |
1440 | const auto &s_next = ds.next[i]; |
1441 | DEBUG_PRINTF("state %u -> %u on sym %u\n" , s, s_next, i); |
1442 | if (s_next == DEAD_STATE) { |
1443 | continue; // dead, probably pruned |
1444 | } else if (s_next == s && i == sym) { |
1445 | continue; // self loop on same symbol |
1446 | } else if (s_next == rdfa.start_floating) { |
1447 | continue; // return to floating start |
1448 | } |
1449 | |
1450 | // We don't handle any other transitions. |
1451 | DEBUG_PRINTF("not single-byte\n" ); |
1452 | return false; |
1453 | } |
1454 | |
1455 | return true; |
1456 | } |
1457 | |
1458 | static |
1459 | bool (const raw_dfa &rdfa, |
1460 | map<ue2_literal, flat_set<ReportID>> &lits_out) { |
1461 | if (rdfa.start_floating == DEAD_STATE) { |
1462 | DEBUG_PRINTF("not floating?\n" ); |
1463 | return false; |
1464 | } |
1465 | if (rdfa.start_anchored != rdfa.start_floating) { |
1466 | DEBUG_PRINTF("not all floating?\n" ); |
1467 | return false; |
1468 | } |
1469 | |
1470 | map<flat_set<ReportID>, vector<u32>> lits; // reports -> symbols |
1471 | |
1472 | const dstate &start = rdfa.states[rdfa.start_floating]; |
1473 | |
1474 | const symbol_t alpha_size = rdfa.getImplAlphaSize(); |
1475 | for (symbol_t i = 0; i < alpha_size; i++) { |
1476 | auto next = start.next[i]; |
1477 | if (next == DEAD_STATE || next == rdfa.start_floating) { |
1478 | continue; |
1479 | } |
1480 | |
1481 | if (!stateIsSEPLiteral(next, i, rdfa)) { |
1482 | return false; |
1483 | } |
1484 | lits[rdfa.states[next].reports].push_back(i); |
1485 | } |
1486 | |
1487 | // Map from symbols back to character reachability. |
1488 | vector<CharReach> reach(alpha_size); |
1489 | for (u32 i = 0; i < N_CHARS; i++) { |
1490 | assert(rdfa.alpha_remap[i] < alpha_size); |
1491 | reach[rdfa.alpha_remap[i]].set(i); |
1492 | } |
1493 | |
1494 | for (const auto &m : lits) { |
1495 | const auto &reports = m.first; |
1496 | const auto &symbols = m.second; |
1497 | |
1498 | CharReach cr; |
1499 | for (const auto &sym : symbols) { |
1500 | cr |= reach[sym]; |
1501 | } |
1502 | |
1503 | for (size_t i = cr.find_first(); i != cr.npos; i = cr.find_next(i)) { |
1504 | if (myisupper(i) && cr.test(mytolower(i))) { |
1505 | // ignore upper half of a nocase pair |
1506 | continue; |
1507 | } |
1508 | |
1509 | bool nocase = myislower(i) && cr.test(mytoupper(i)); |
1510 | insert(&lits_out[ue2_literal((char)i, nocase)], reports); |
1511 | } |
1512 | } |
1513 | |
1514 | return true; |
1515 | } |
1516 | |
1517 | static |
1518 | bool (const OutfixInfo &outfix, const ReportManager &rm, |
1519 | map<ue2_literal, flat_set<ReportID>> &lits_out) { |
1520 | if (outfix.minWidth != depth(1) || outfix.maxWidth != depth(1)) { |
1521 | DEBUG_PRINTF("outfix must be fixed width of one\n" ); |
1522 | return false; |
1523 | } |
1524 | |
1525 | for (const auto &report_id : all_reports(outfix)) { |
1526 | const auto &report = rm.getReport(report_id); |
1527 | if (!isSimpleExhaustible(report)) { |
1528 | DEBUG_PRINTF("report id %u not simple exhaustible\n" , report_id); |
1529 | return false; |
1530 | } |
1531 | } |
1532 | |
1533 | // SEP cases should always become DFAs, so that's the only extract code we |
1534 | // have implemented here. |
1535 | |
1536 | if (outfix.rdfa()) { |
1537 | return extractSEPLiterals(*outfix.rdfa(), lits_out); |
1538 | } |
1539 | |
1540 | DEBUG_PRINTF("cannot extract literals from outfix type\n" ); |
1541 | return false; |
1542 | } |
1543 | |
1544 | static |
1545 | void addAnchoredSmallBlockLiterals(RoseBuildImpl &tbi) { |
1546 | if (tbi.cc.streaming) { |
1547 | DEBUG_PRINTF("not block mode\n" ); |
1548 | return; |
1549 | } |
1550 | if (!tbi.anchored_nfas.empty()) { |
1551 | DEBUG_PRINTF("anchored table is not purely literal\n" ); |
1552 | return; |
1553 | } |
1554 | |
1555 | // At the moment, we only use the small-block matcher if all our anchored |
1556 | // literals are direct reports (i.e. leaf nodes in the Rose graph). |
1557 | for (const set<u32> &lits : tbi.anchored_simple | map_values) { |
1558 | for (u32 lit_id : lits) { |
1559 | if (!tbi.isDirectReport(lit_id)) { |
1560 | DEBUG_PRINTF("not all anchored lits are direct reports\n" ); |
1561 | return; |
1562 | } |
1563 | } |
1564 | } |
1565 | |
1566 | vector<pair<simple_anchored_info, set<u32> > > anchored_lits; |
1567 | vector<OutfixInfo *> sep_outfixes; |
1568 | size_t oneByteLiterals = 0; |
1569 | |
1570 | for (const auto &e : tbi.anchored_simple) { |
1571 | const simple_anchored_info &sai = e.first; |
1572 | const set<u32> &lit_ids = e.second; |
1573 | |
1574 | if (sai.literal.length() + sai.min_bound > ROSE_SMALL_BLOCK_LEN) { |
1575 | DEBUG_PRINTF("skipping literal '%s' with min bound %u that cannot " |
1576 | "match inside small block width\n" , |
1577 | dumpString(sai.literal).c_str(), sai.min_bound); |
1578 | } |
1579 | |
1580 | anchored_lits.push_back(make_pair(sai, lit_ids)); |
1581 | if (sai.literal.length() == 1) { |
1582 | oneByteLiterals++; |
1583 | } |
1584 | } |
1585 | |
1586 | // Capture SEP outfixes as well, adding them as literals to the small block |
1587 | // table. |
1588 | map<ue2_literal, flat_set<ReportID>> sep_literals; |
1589 | for (OutfixInfo &oi : tbi.outfixes) { |
1590 | if (extractSEPLiterals(oi, tbi.rm, sep_literals)) { |
1591 | sep_outfixes.push_back(&oi); |
1592 | } |
1593 | } |
1594 | |
1595 | oneByteLiterals += sep_literals.size(); |
1596 | DEBUG_PRINTF("%zu one-byte literals\n" , oneByteLiterals); |
1597 | if (oneByteLiterals > MAX_1BYTE_SMALL_BLOCK_LITERALS) { |
1598 | DEBUG_PRINTF("too many one-byte literals, not building small block " |
1599 | "table!\n" ); |
1600 | return; |
1601 | } |
1602 | |
1603 | for (const auto &e : tbi.anchored_simple) { |
1604 | const simple_anchored_info &sai = e.first; |
1605 | const set<u32> &lit_ids = e.second; |
1606 | |
1607 | addSmallBlockLiteral(tbi, sai, lit_ids); |
1608 | } |
1609 | |
1610 | for (const auto &m : sep_literals) { |
1611 | addSmallBlockLiteral(tbi, m.first, m.second); |
1612 | } |
1613 | |
1614 | for (OutfixInfo *oi : sep_outfixes) { |
1615 | assert(oi); |
1616 | oi->in_sbmatcher = true; |
1617 | } |
1618 | } |
1619 | |
1620 | #ifndef NDEBUG |
1621 | static |
1622 | bool historiesAreValid(const RoseGraph &g) { |
1623 | for (const auto &e : edges_range(g)) { |
1624 | if (g[e].history == ROSE_ROLE_HISTORY_INVALID) { |
1625 | DEBUG_PRINTF("edge [%zu,%zu] has invalid history\n" , |
1626 | g[source(e, g)].index, g[target(e, g)].index); |
1627 | return false; |
1628 | } |
1629 | } |
1630 | |
1631 | return true; |
1632 | } |
1633 | |
1634 | /** |
1635 | * Assertion: Returns true if we have a reference hanging around to a vertex |
1636 | * that no longer exists in the graph. |
1637 | */ |
1638 | static |
1639 | bool danglingVertexRef(RoseBuildImpl &tbi) { |
1640 | RoseGraph::vertex_iterator vi, ve; |
1641 | tie(vi, ve) = vertices(tbi.g); |
1642 | const unordered_set<RoseVertex> valid_vertices(vi, ve); |
1643 | |
1644 | if (!contains(valid_vertices, tbi.anchored_root)) { |
1645 | DEBUG_PRINTF("anchored root vertex %zu not in graph\n" , |
1646 | tbi.g[tbi.anchored_root].index); |
1647 | return true; |
1648 | } |
1649 | |
1650 | for (const auto &e : tbi.ghost) { |
1651 | if (!contains(valid_vertices, e.first)) { |
1652 | DEBUG_PRINTF("ghost key vertex %zu not in graph\n" , |
1653 | tbi.g[e.first].index); |
1654 | return true; |
1655 | } |
1656 | if (!contains(valid_vertices, e.second)) { |
1657 | DEBUG_PRINTF("ghost value vertex %zu not in graph\n" , |
1658 | tbi.g[e.second].index); |
1659 | return true; |
1660 | } |
1661 | } |
1662 | |
1663 | return false; |
1664 | } |
1665 | |
1666 | static |
1667 | bool roleOffsetsAreValid(const RoseGraph &g) { |
1668 | for (auto v : vertices_range(g)) { |
1669 | if (g[v].min_offset >= ROSE_BOUND_INF) { |
1670 | DEBUG_PRINTF("invalid min_offset for role %zu\n" , g[v].index); |
1671 | return false; |
1672 | } |
1673 | if (g[v].min_offset > g[v].max_offset) { |
1674 | DEBUG_PRINTF("min_offset > max_offset for %zu\n" , g[v].index); |
1675 | return false; |
1676 | } |
1677 | } |
1678 | return true; |
1679 | } |
1680 | #endif // NDEBUG |
1681 | |
1682 | bytecode_ptr<RoseEngine> RoseBuildImpl::buildRose(u32 minWidth) { |
1683 | dumpRoseGraph(*this, "rose_early.dot" ); |
1684 | |
1685 | // Early check for Rose implementability. |
1686 | assert(canImplementGraphs(*this)); |
1687 | |
1688 | // Sanity check vertex role offsets. |
1689 | assert(roleOffsetsAreValid(g)); |
1690 | |
1691 | convertPrefixToBounds(*this); |
1692 | |
1693 | // Turn flood-prone suffixes into suffix NFAs. |
1694 | convertFloodProneSuffixes(*this); |
1695 | |
1696 | // Turn repeats into Castle prototypes. |
1697 | makeCastles(*this); |
1698 | |
1699 | rehomeAnchoredLiterals(*this); |
1700 | |
1701 | // If we've got a very small number of EOD-anchored literals, consider |
1702 | // moving them into the floating table so that we only have one literal |
1703 | // matcher to run. Note that this needs to happen before |
1704 | // addAnchoredSmallBlockLiterals as it may create anchored literals. |
1705 | assert(roleOffsetsAreValid(g)); |
1706 | stealEodVertices(*this); |
1707 | |
1708 | addAnchoredSmallBlockLiterals(*this); |
1709 | |
1710 | // Merge duplicate leaf nodes |
1711 | dedupeSuffixes(*this); |
1712 | if (cc.grey.roseGraphReduction) { |
1713 | mergeDupeLeaves(*this); |
1714 | uncalcLeaves(*this); |
1715 | } |
1716 | |
1717 | assert(roleOffsetsAreValid(g)); |
1718 | handleMixedSensitivity(); |
1719 | |
1720 | assignHistories(*this); |
1721 | |
1722 | convertAnchPrefixToBounds(*this); |
1723 | |
1724 | // Do some final graph reduction. |
1725 | dedupeLeftfixes(*this); |
1726 | aliasRoles(*this, false); // Don't merge leftfixes. |
1727 | dedupeLeftfixes(*this); |
1728 | uncalcLeaves(*this); |
1729 | |
1730 | /* note the leftfixes which do not need to keep state across stream |
1731 | boundaries */ |
1732 | findTransientLeftfixes(); |
1733 | |
1734 | dedupeLeftfixesVariableLag(*this); |
1735 | mergeLeftfixesVariableLag(*this); |
1736 | mergeSmallLeftfixes(*this); |
1737 | mergeCastleLeftfixes(*this); |
1738 | |
1739 | // Do a rose-merging aliasing pass. |
1740 | aliasRoles(*this, true); |
1741 | |
1742 | // Merging of suffixes _below_ role aliasing, as otherwise we'd have to |
1743 | // teach role aliasing about suffix tops. |
1744 | mergeCastleSuffixes(*this); |
1745 | mergePuffixes(*this); |
1746 | mergeAcyclicSuffixes(*this); |
1747 | mergeSmallSuffixes(*this); |
1748 | |
1749 | // Convert Castles that would be better off as NFAs back to NGHolder |
1750 | // infixes/suffixes. |
1751 | if (unmakeCastles(*this)) { |
1752 | // We may be able to save some stream state by merging the newly |
1753 | // "unmade" Castles. |
1754 | mergeSmallSuffixes(*this); |
1755 | mergeSmallLeftfixes(*this); |
1756 | } |
1757 | |
1758 | assert(!hasOrphanedTops(*this)); |
1759 | |
1760 | // Do a rose-merging aliasing pass. |
1761 | aliasRoles(*this, true); |
1762 | assert(!hasOrphanedTops(*this)); |
1763 | |
1764 | // Run a merge pass over the outfixes as well. |
1765 | mergeOutfixes(*this); |
1766 | |
1767 | assert(!danglingVertexRef(*this)); |
1768 | assert(!hasOrphanedTops(*this)); |
1769 | |
1770 | findMoreLiteralMasks(*this); |
1771 | |
1772 | assignGroupsToLiterals(*this); |
1773 | assignGroupsToRoles(*this); |
1774 | findGroupSquashers(*this); |
1775 | |
1776 | /* final prep work */ |
1777 | remapCastleTops(*this); |
1778 | optimiseRoseTops(*this); |
1779 | buildRoseSquashMasks(*this); |
1780 | |
1781 | rm.assignDkeys(this); |
1782 | |
1783 | /* transfer mpv outfix to main queue */ |
1784 | if (mpv_outfix) { |
1785 | outfixes.push_back(move(*mpv_outfix)); |
1786 | mpv_outfix = nullptr; |
1787 | } |
1788 | |
1789 | assert(canImplementGraphs(*this)); |
1790 | assert(!hasOrphanedTops(*this)); |
1791 | assert(roleOffsetsAreValid(g)); |
1792 | assert(historiesAreValid(g)); |
1793 | |
1794 | dumpRoseGraph(*this, "rose_pre_norm.dot" ); |
1795 | |
1796 | return buildFinalEngine(minWidth); |
1797 | } |
1798 | |
1799 | } // namespace ue2 |
1800 | |