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
81using namespace std;
82using boost::adaptors::map_values;
83
84namespace 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
93static
94bool 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
106static
107void 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 */
120static
121void 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
171void 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.
210static
211size_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
229bool RoseBuildImpl::isPseudoStar(const RoseEdge &e) const {
230 return !g[e].minBound && isPseudoStarOrFirstOnly(e);
231}
232
233bool 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
270bool 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
279static
280size_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
291static
292RoseRoleHistory 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
370static
371void 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
379bool 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. */
452static
453bool 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
485static
486bool 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
557static
558void 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
587static
588bool 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
644static
645bool 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. */
718static
719void 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
769bool RoseBuildImpl::isDelayed(u32 id) const {
770 return literal_info.at(id).undelayed_id != id;
771}
772
773bool 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
783bool 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
793bool 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
803void 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. */
860static
861map<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
872namespace {
873struct infix_info {
874 set<RoseVertex> preds;
875 set<RoseVertex> succs;
876};
877}
878
879static
880map<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
910static
911map<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
921static
922u32 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
930static
931bool 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
1001static
1002void 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
1062static
1063void 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
1083static
1084bool 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
1116static
1117bool 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 */
1141static
1142void 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
1196static
1197void optimiseRoseTops(RoseBuildImpl &build) {
1198 reduceTopTriggerLoad(build);
1199 /* prune unused tops ? */
1200 findTopTriggerCancels(build);
1201}
1202
1203static
1204void 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
1271static
1272void 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
1292static
1293void 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
1330static
1331void 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. */
1368static const size_t MAX_1BYTE_SMALL_BLOCK_LITERALS = 20;
1369
1370static
1371void 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
1403static
1404void 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
1428static
1429bool 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
1458static
1459bool extractSEPLiterals(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
1517static
1518bool extractSEPLiterals(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
1544static
1545void 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
1621static
1622bool 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 */
1638static
1639bool 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
1666static
1667bool 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
1682bytecode_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