1/*
2 * Copyright (c) 2015-2019, 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 "ue2common.h"
32#include "grey.h"
33#include "hs_compile.h" // for HS_MODE_*
34#include "rose_build_add_internal.h"
35#include "rose_build_anchored.h"
36#include "rose_build_dump.h"
37#include "rose_build_engine_blob.h"
38#include "rose_build_exclusive.h"
39#include "rose_build_groups.h"
40#include "rose_build_infix.h"
41#include "rose_build_long_lit.h"
42#include "rose_build_lookaround.h"
43#include "rose_build_matchers.h"
44#include "rose_build_misc.h"
45#include "rose_build_program.h"
46#include "rose_build_resources.h"
47#include "rose_build_scatter.h"
48#include "rose_build_util.h"
49#include "rose_build_width.h"
50#include "rose_internal.h"
51#include "rose_program.h"
52#include "hwlm/hwlm.h" /* engine types */
53#include "hwlm/hwlm_build.h"
54#include "hwlm/hwlm_literal.h"
55#include "nfa/castlecompile.h"
56#include "nfa/goughcompile.h"
57#include "nfa/mcclellancompile.h"
58#include "nfa/mcclellancompile_util.h"
59#include "nfa/mcsheng_compile.h"
60#include "nfa/nfa_api_queue.h"
61#include "nfa/nfa_build_util.h"
62#include "nfa/nfa_internal.h"
63#include "nfa/shengcompile.h"
64#include "nfa/shufticompile.h"
65#include "nfa/tamaramacompile.h"
66#include "nfa/tamarama_internal.h"
67#include "nfagraph/ng_execute.h"
68#include "nfagraph/ng_holder.h"
69#include "nfagraph/ng_lbr.h"
70#include "nfagraph/ng_limex.h"
71#include "nfagraph/ng_mcclellan.h"
72#include "nfagraph/ng_repeat.h"
73#include "nfagraph/ng_reports.h"
74#include "nfagraph/ng_revacc.h"
75#include "nfagraph/ng_stop.h"
76#include "nfagraph/ng_util.h"
77#include "nfagraph/ng_width.h"
78#include "smallwrite/smallwrite_build.h"
79#include "som/slot_manager.h"
80#include "util/bitutils.h"
81#include "util/boundary_reports.h"
82#include "util/charreach.h"
83#include "util/charreach_util.h"
84#include "util/compile_context.h"
85#include "util/compile_error.h"
86#include "util/container.h"
87#include "util/fatbit_build.h"
88#include "util/graph_range.h"
89#include "util/insertion_ordered.h"
90#include "util/make_unique.h"
91#include "util/multibit_build.h"
92#include "util/noncopyable.h"
93#include "util/order_check.h"
94#include "util/popcount.h"
95#include "util/queue_index_factory.h"
96#include "util/report_manager.h"
97#include "util/ue2string.h"
98#include "util/verify_types.h"
99
100#include <algorithm>
101#include <array>
102#include <map>
103#include <queue>
104#include <set>
105#include <sstream>
106#include <string>
107#include <vector>
108#include <utility>
109
110#include <boost/range/adaptor/map.hpp>
111
112using namespace std;
113using boost::adaptors::map_values;
114using boost::adaptors::map_keys;
115
116namespace ue2 {
117
118/* The rose bytecode construction is a giant cesspit.
119 *
120 * One issue is that bits and pieces are constructed piecemeal and these
121 * sections are used by later in the construction process. Until the very end of
122 * the construction there is no useful invariant holding for the bytecode. This
123 * makes reordering / understanding the construction process awkward as there
124 * are hidden dependencies everywhere. We should start by shifting towards
125 * a model where the bytecode is only written to during the construction so that
126 * the dependencies can be understood by us mere mortals.
127 *
128 * I am sure the construction process is also bad from a number of other
129 * standpoints as well but the can come later.
130 *
131 * Actually, one other annoying issues the plague of member functions on the
132 * impl which tightly couples the internals of this file to all the other rose
133 * build files. Need more egregiously awesome free functions.
134 */
135
136namespace /* anon */ {
137
138struct build_context : noncopyable {
139 /** \brief information about engines to the left of a vertex */
140 map<RoseVertex, left_build_info> leftfix_info;
141
142 /** \brief mapping from suffix to queue index. */
143 map<suffix_id, u32> suffixes;
144
145 /** \brief engine info by queue. */
146 map<u32, engine_info> engine_info_by_queue;
147
148 /** \brief Simple cache of programs written to engine blob, used for
149 * deduplication. */
150 unordered_map<RoseProgram, u32, RoseProgramHash,
151 RoseProgramEquivalence> program_cache;
152
153 /** \brief State indices, for those roles that have them.
154 * Each vertex present has a unique state index in the range
155 * [0, roleStateIndices.size()). */
156 unordered_map<RoseVertex, u32> roleStateIndices;
157
158 /** \brief Mapping from queue index to bytecode offset for built engines
159 * that have already been pushed into the engine_blob. */
160 unordered_map<u32, u32> engineOffsets;
161
162 /** \brief List of long literals (ones with CHECK_LONG_LIT instructions)
163 * that need hash table support. */
164 vector<ue2_case_string> longLiterals;
165
166 /** \brief Contents of the Rose bytecode immediately following the
167 * RoseEngine. */
168 RoseEngineBlob engine_blob;
169
170 /** \brief True if this Rose engine has an MPV engine. */
171 bool needs_mpv_catchup = false;
172
173 /** \brief Resources in use (tracked as programs are added). */
174 RoseResources resources;
175};
176
177/** \brief subengine info including built engine and
178* corresponding triggering rose vertices */
179struct ExclusiveSubengine {
180 bytecode_ptr<NFA> nfa;
181 vector<RoseVertex> vertices;
182};
183
184/** \brief exclusive info to build tamarama */
185struct ExclusiveInfo : noncopyable {
186 // subengine info
187 vector<ExclusiveSubengine> subengines;
188 // all the report in tamarama
189 set<ReportID> reports;
190 // assigned queue id
191 u32 queue;
192};
193
194}
195
196static
197void add_nfa_to_blob(build_context &bc, NFA &nfa) {
198 u32 qi = nfa.queueIndex;
199 u32 nfa_offset = bc.engine_blob.add(nfa, nfa.length);
200 DEBUG_PRINTF("added nfa qi=%u, type=%u, length=%u at offset=%u\n", qi,
201 nfa.type, nfa.length, nfa_offset);
202
203 assert(!contains(bc.engineOffsets, qi));
204 bc.engineOffsets.emplace(qi, nfa_offset);
205}
206
207static
208u32 countRosePrefixes(const vector<LeftNfaInfo> &roses) {
209 u32 num = 0;
210 for (const auto &r : roses) {
211 if (!r.infix) {
212 num++;
213 }
214 }
215 return num;
216}
217
218/**
219 * \brief True if this Rose engine needs to run a catch up whenever a literal
220 * report is generated.
221 *
222 * Catch up is necessary if there are output-exposed engines (suffixes,
223 * outfixes).
224 */
225static
226bool needsCatchup(const RoseBuildImpl &build) {
227 /* Note: we could be more selective about when we need to generate catch up
228 * instructions rather than just a boolean yes/no - for instance, if we know
229 * that a role can only match before the point that an outfix/suffix could
230 * match, we do not strictly need a catchup instruction.
231 *
232 * However, this would add a certain amount of complexity to the
233 * catchup logic and would likely have limited applicability - how many
234 * reporting roles have a fixed max offset and how much time is spent on
235 * catchup for these cases?
236 */
237
238 if (!build.outfixes.empty()) {
239 /* TODO: check that they have non-eod reports */
240 DEBUG_PRINTF("has outfixes\n");
241 return true;
242 }
243
244 const RoseGraph &g = build.g;
245
246 for (auto v : vertices_range(g)) {
247 if (g[v].suffix) {
248 /* TODO: check that they have non-eod reports */
249 DEBUG_PRINTF("vertex %zu has suffix\n", g[v].index);
250 return true;
251 }
252 }
253
254 DEBUG_PRINTF("no need for catch-up on report\n");
255 return false;
256}
257
258static
259bool isPureFloating(const RoseResources &resources, const CompileContext &cc) {
260 if (!resources.has_floating) {
261 DEBUG_PRINTF("no floating table\n");
262 return false;
263 }
264
265 if (resources.has_outfixes || resources.has_suffixes ||
266 resources.has_leftfixes) {
267 DEBUG_PRINTF("has engines\n");
268 return false;
269 }
270
271 if (resources.has_anchored) {
272 DEBUG_PRINTF("has anchored matcher\n");
273 return false;
274 }
275
276 if (resources.has_eod) {
277 DEBUG_PRINTF("has eod work to do\n");
278 return false;
279 }
280
281 if (resources.has_states) {
282 DEBUG_PRINTF("has states\n");
283 return false;
284 }
285
286 if (resources.has_lit_delay) {
287 DEBUG_PRINTF("has delayed literals\n");
288 return false;
289 }
290
291 if (cc.streaming && resources.has_lit_check) {
292 DEBUG_PRINTF("has long literals in streaming mode, which needs long "
293 "literal table support\n");
294 return false;
295 }
296
297 if (resources.checks_groups) {
298 DEBUG_PRINTF("has group checks\n");
299 return false;
300 }
301
302 DEBUG_PRINTF("pure floating literals\n");
303 return true;
304}
305
306static
307bool isSingleOutfix(const RoseBuildImpl &tbi) {
308 for (auto v : vertices_range(tbi.g)) {
309 if (tbi.isAnyStart(v)) {
310 continue;
311 }
312 if (tbi.hasLiteralInTable(v, ROSE_ANCHORED_SMALL_BLOCK)) {
313 continue;
314 }
315 DEBUG_PRINTF("has role\n");
316 return false;
317 }
318
319 if (tbi.ssm.numSomSlots()) {
320 return false;
321 }
322
323 if (!tbi.boundary.report_at_eod.empty()) {
324 return false; /* streaming runtime makes liberal use of broken flag */
325 }
326
327 return tbi.outfixes.size() == 1;
328}
329
330static
331u8 pickRuntimeImpl(const RoseBuildImpl &build, const RoseResources &resources,
332 UNUSED u32 outfixEndQueue) {
333 DEBUG_PRINTF("has_outfixes=%d\n", resources.has_outfixes);
334 DEBUG_PRINTF("has_suffixes=%d\n", resources.has_suffixes);
335 DEBUG_PRINTF("has_leftfixes=%d\n", resources.has_leftfixes);
336 DEBUG_PRINTF("has_literals=%d\n", resources.has_literals);
337 DEBUG_PRINTF("has_states=%d\n", resources.has_states);
338 DEBUG_PRINTF("checks_groups=%d\n", resources.checks_groups);
339 DEBUG_PRINTF("has_lit_delay=%d\n", resources.has_lit_delay);
340 DEBUG_PRINTF("has_lit_check=%d\n", resources.has_lit_check);
341 DEBUG_PRINTF("has_anchored=%d\n", resources.has_anchored);
342 DEBUG_PRINTF("has_floating=%d\n", resources.has_floating);
343 DEBUG_PRINTF("has_eod=%d\n", resources.has_eod);
344
345 if (isPureFloating(resources, build.cc)) {
346 return ROSE_RUNTIME_PURE_LITERAL;
347 }
348
349 if (isSingleOutfix(build)) {
350 return ROSE_RUNTIME_SINGLE_OUTFIX;
351 }
352
353 return ROSE_RUNTIME_FULL_ROSE;
354}
355
356/**
357 * \brief True if this Rose engine needs to run MPV catch up in front of
358 * non-MPV reports.
359 */
360static
361bool needsMpvCatchup(const RoseBuildImpl &build) {
362 const auto &outfixes = build.outfixes;
363 bool has_mpv =
364 any_of(begin(outfixes), end(outfixes), [](const OutfixInfo &outfix) {
365 return outfix.is_nonempty_mpv();
366 });
367
368 if (!has_mpv) {
369 DEBUG_PRINTF("no mpv\n");
370 return false;
371 }
372
373 if (isSingleOutfix(build)) {
374 DEBUG_PRINTF("single outfix\n");
375 return false;
376 }
377
378 return true;
379}
380
381static
382void fillStateOffsets(const RoseBuildImpl &build, u32 rolesWithStateCount,
383 u32 anchorStateSize, u32 activeArrayCount,
384 u32 activeLeftCount, u32 laggedRoseCount,
385 u32 longLitStreamStateRequired, u32 historyRequired,
386 RoseStateOffsets *so) {
387 u32 curr_offset = 0;
388
389 // First, runtime status (stores per-stream state, like whether we need a
390 // delay rebuild or have been told to halt matching.)
391 curr_offset += sizeof(u8);
392
393 // Role state storage.
394 curr_offset += mmbit_size(rolesWithStateCount);
395
396 so->activeLeafArray = curr_offset; /* TODO: limit size of array */
397 curr_offset += mmbit_size(activeArrayCount);
398 so->activeLeafArray_size = mmbit_size(activeArrayCount);
399
400 so->activeLeftArray = curr_offset; /* TODO: limit size of array */
401 curr_offset += mmbit_size(activeLeftCount);
402 so->activeLeftArray_size = mmbit_size(activeLeftCount);
403
404 so->longLitState = curr_offset;
405 curr_offset += longLitStreamStateRequired;
406 so->longLitState_size = longLitStreamStateRequired;
407
408 // ONE WHOLE BYTE for each active leftfix with lag.
409 so->leftfixLagTable = curr_offset;
410 curr_offset += laggedRoseCount;
411
412 so->anchorState = curr_offset;
413 curr_offset += anchorStateSize;
414
415 so->groups = curr_offset;
416 so->groups_size = (build.group_end + 7) / 8;
417 assert(so->groups_size <= sizeof(u64a));
418 curr_offset += so->groups_size;
419
420 // The history consists of the bytes in the history only. YAY
421 so->history = curr_offset;
422 curr_offset += historyRequired;
423
424 // Exhaustion multibit.
425 so->exhausted = curr_offset;
426 curr_offset += mmbit_size(build.rm.numEkeys());
427 so->exhausted_size = mmbit_size(build.rm.numEkeys());
428
429 // Logical multibit.
430 so->logicalVec = curr_offset;
431 so->logicalVec_size = mmbit_size(build.rm.numLogicalKeys() +
432 build.rm.numLogicalOps());
433 curr_offset += so->logicalVec_size;
434
435 // Combination multibit.
436 so->combVec = curr_offset;
437 so->combVec_size = mmbit_size(build.rm.numCkeys());
438 curr_offset += so->combVec_size;
439
440 // SOM locations and valid/writeable multibit structures.
441 if (build.ssm.numSomSlots()) {
442 const u32 somWidth = build.ssm.somPrecision();
443 if (somWidth) { // somWidth is zero in block mode.
444 curr_offset = ROUNDUP_N(curr_offset, somWidth);
445 so->somLocation = curr_offset;
446 curr_offset += build.ssm.numSomSlots() * somWidth;
447 } else {
448 so->somLocation = 0;
449 }
450 so->somValid = curr_offset;
451 curr_offset += mmbit_size(build.ssm.numSomSlots());
452 so->somWritable = curr_offset;
453 curr_offset += mmbit_size(build.ssm.numSomSlots());
454 so->somMultibit_size = mmbit_size(build.ssm.numSomSlots());
455 } else {
456 // No SOM handling, avoid growing the stream state any further.
457 so->somLocation = 0;
458 so->somValid = 0;
459 so->somWritable = 0;
460 }
461
462 // note: state space for mask nfas is allocated later
463 so->nfaStateBegin = curr_offset;
464 so->end = curr_offset;
465}
466
467// Get the mask of initial vertices due to root and anchored_root.
468rose_group RoseBuildImpl::getInitialGroups() const {
469 rose_group groups = getSuccGroups(root)
470 | getSuccGroups(anchored_root)
471 | boundary_group_mask;
472
473 DEBUG_PRINTF("initial groups = %016llx\n", groups);
474 return groups;
475}
476
477static
478bool nfaStuckOn(const NGHolder &g) {
479 assert(!proper_out_degree(g.startDs, g));
480 set<NFAVertex> succ;
481 insert(&succ, adjacent_vertices(g.start, g));
482 succ.erase(g.startDs);
483
484 set<NFAVertex> asucc;
485 set<u32> tops;
486 set<u32> done_tops;
487
488 for (const auto &e : out_edges_range(g.start, g)) {
489 insert(&tops, g[e].tops);
490 if (!g[target(e, g)].char_reach.all()) {
491 continue;
492 }
493
494 asucc.clear();
495 insert(&asucc, adjacent_vertices(target(e, g), g));
496
497 if (asucc == succ) {
498 insert(&done_tops, g[e].tops);
499 }
500 }
501
502 return tops == done_tops;
503}
504
505namespace {
506struct PredTopPair {
507 PredTopPair(RoseVertex v, u32 t) : pred(v), top(t) {}
508 bool operator<(const PredTopPair &b) const {
509 const PredTopPair &a = *this;
510 ORDER_CHECK(pred);
511 ORDER_CHECK(top);
512 return false;
513 }
514 RoseVertex pred;
515 u32 top;
516};
517}
518
519static
520void findFixedDepthTops(const RoseGraph &g, const set<PredTopPair> &triggers,
521 map<u32, u32> *fixed_depth_tops) {
522 DEBUG_PRINTF("|trig| %zu\n", triggers.size());
523 /* find all pred roles for this holder, group by top */
524 /* if all pred roles for a given top have the same min and max offset, we
525 * add the top to the fixed_depth_top map */
526 map<u32, set<RoseVertex> > pred_by_top;
527 for (const auto &ptp : triggers) {
528 u32 top = ptp.top;
529 RoseVertex u = ptp.pred;
530 pred_by_top[top].insert(u);
531 }
532
533 for (const auto &e : pred_by_top) {
534 u32 top = e.first;
535 const set<RoseVertex> &preds = e.second;
536 if (!g[*preds.begin()].fixedOffset()) {
537 continue;
538 }
539 u32 depth = g[*preds.begin()].min_offset;
540 for (RoseVertex u : preds) {
541 if (g[u].min_offset != depth || g[u].max_offset != depth) {
542 goto next_top;
543 }
544 }
545 DEBUG_PRINTF("%u at depth %u\n", top, depth);
546 (*fixed_depth_tops)[top] = depth;
547 next_top:;
548 }
549}
550
551/**
552 * \brief Heuristic for picking between a DFA or NFA implementation of an
553 * engine.
554 */
555static
556bytecode_ptr<NFA> pickImpl(bytecode_ptr<NFA> dfa_impl,
557 bytecode_ptr<NFA> nfa_impl) {
558 assert(nfa_impl);
559 assert(dfa_impl);
560 assert(isDfaType(dfa_impl->type));
561
562 // If our NFA is an LBR, it always wins.
563 if (isLbrType(nfa_impl->type)) {
564 return nfa_impl;
565 }
566
567 // if our DFA is an accelerated Sheng, it always wins.
568 if (isShengType(dfa_impl->type) && has_accel(*dfa_impl)) {
569 return dfa_impl;
570 }
571
572 bool d_accel = has_accel(*dfa_impl);
573 bool n_accel = has_accel(*nfa_impl);
574 bool d_big = isBigDfaType(dfa_impl->type);
575 bool n_vsmall = nfa_impl->nPositions <= 32;
576 bool n_br = has_bounded_repeats(*nfa_impl);
577 DEBUG_PRINTF("da %d na %d db %d nvs %d nbr %d\n", (int)d_accel,
578 (int)n_accel, (int)d_big, (int)n_vsmall, (int)n_br);
579 if (d_big) {
580 if (!n_vsmall) {
581 if (d_accel || !n_accel) {
582 return dfa_impl;
583 } else {
584 return nfa_impl;
585 }
586 } else {
587 if (n_accel) {
588 return nfa_impl;
589 } else {
590 return dfa_impl;
591 }
592 }
593 } else {
594 /* favour a McClellan 8, unless the nfa looks really good and the dfa
595 * looks like trouble */
596 if (!d_accel && n_vsmall && n_accel && !n_br) {
597 return nfa_impl;
598 } else {
599 return dfa_impl;
600 }
601 }
602}
603
604/**
605 * \brief Builds an LBR if there's one repeat in the given CastleProto,
606 * otherwise a Castle.
607 */
608static
609bytecode_ptr<NFA>
610buildRepeatEngine(const CastleProto &proto,
611 const map<u32, vector<vector<CharReach>>> &triggers,
612 const CompileContext &cc, const ReportManager &rm) {
613 // If we only have one repeat, the LBR should always be the best possible
614 // implementation.
615 if (proto.repeats.size() == 1 && cc.grey.allowLbr) {
616 return constructLBR(proto, triggers.at(0), cc, rm);
617 }
618
619 auto castle_nfa = buildCastle(proto, triggers, cc, rm);
620 assert(castle_nfa); // Should always be constructible.
621 return castle_nfa;
622}
623
624static
625bytecode_ptr<NFA> getDfa(raw_dfa &rdfa, bool is_transient,
626 const CompileContext &cc, const ReportManager &rm) {
627 // Unleash the Sheng!!
628 auto dfa = shengCompile(rdfa, cc, rm, false);
629 if (!dfa && !is_transient) {
630 // Sheng wasn't successful, so unleash McClellan!
631 /* We don't try the hybrid for transient prefixes due to the extra
632 * bytecode and that they are usually run on small blocks */
633 dfa = mcshengCompile(rdfa, cc, rm);
634 }
635 if (!dfa) {
636 // Sheng wasn't successful, so unleash McClellan!
637 dfa = mcclellanCompile(rdfa, cc, rm, false);
638 }
639 return dfa;
640}
641
642/* builds suffix nfas */
643static
644bytecode_ptr<NFA>
645buildSuffix(const ReportManager &rm, const SomSlotManager &ssm,
646 const map<u32, u32> &fixed_depth_tops,
647 const map<u32, vector<vector<CharReach>>> &triggers,
648 suffix_id suff, const CompileContext &cc) {
649 if (suff.castle()) {
650 auto n = buildRepeatEngine(*suff.castle(), triggers, cc, rm);
651 assert(n);
652 return n;
653 }
654
655 if (suff.haig()) {
656 auto n = goughCompile(*suff.haig(), ssm.somPrecision(), cc, rm);
657 assert(n);
658 return n;
659 }
660
661 if (suff.dfa()) {
662 auto d = getDfa(*suff.dfa(), false, cc, rm);
663 assert(d);
664 return d;
665 }
666
667 assert(suff.graph());
668 NGHolder &holder = *suff.graph();
669 assert(holder.kind == NFA_SUFFIX);
670 const bool oneTop = onlyOneTop(holder);
671 bool compress_state = cc.streaming;
672
673 // Take a shot at the LBR engine.
674 if (oneTop) {
675 auto lbr = constructLBR(holder, triggers.at(0), cc, rm);
676 if (lbr) {
677 return lbr;
678 }
679 }
680
681 auto n = constructNFA(holder, &rm, fixed_depth_tops, triggers,
682 compress_state, cc);
683 assert(n);
684
685 if (oneTop && cc.grey.roseMcClellanSuffix) {
686 if (cc.grey.roseMcClellanSuffix == 2 || n->nPositions > 128 ||
687 !has_bounded_repeats_other_than_firsts(*n)) {
688 auto rdfa = buildMcClellan(holder, &rm, false, triggers.at(0),
689 cc.grey);
690 if (rdfa) {
691 auto d = getDfa(*rdfa, false, cc, rm);
692 assert(d);
693 if (cc.grey.roseMcClellanSuffix != 2) {
694 n = pickImpl(move(d), move(n));
695 } else {
696 n = move(d);
697 }
698
699 assert(n);
700 if (isMcClellanType(n->type)) {
701 // DFA chosen. We may be able to set some more properties
702 // in the NFA structure here.
703 u64a maxOffset = findMaxOffset(holder, rm);
704 if (maxOffset != MAX_OFFSET && maxOffset < 0xffffffffull) {
705 n->maxOffset = (u32)maxOffset;
706 DEBUG_PRINTF("dfa max offset %llu\n", maxOffset);
707 } else {
708 n->maxOffset = 0; // inf
709 }
710 }
711 }
712 }
713 }
714 return n;
715}
716
717static
718void findInfixTriggers(const RoseBuildImpl &build,
719 map<left_id, set<PredTopPair> > *infixTriggers) {
720 const RoseGraph &g = build.g;
721 for (auto v : vertices_range(g)) {
722 if (!g[v].left) {
723 continue;
724 }
725
726 set<PredTopPair> &triggers = (*infixTriggers)[left_id(g[v].left)];
727
728 for (const auto &e : in_edges_range(v, g)) {
729 RoseVertex u = source(e, g);
730 if (build.isAnyStart(u)) {
731 continue;
732 }
733 triggers.insert(PredTopPair(u, g[e].rose_top));
734 }
735 }
736}
737
738static
739vector<CharReach> as_cr_seq(const rose_literal_id &lit) {
740 vector<CharReach> rv = as_cr_seq(lit.s);
741 for (u32 i = 0; i < lit.delay; i++) {
742 rv.push_back(CharReach::dot());
743 }
744
745 /* TODO: take into account cmp/msk */
746 return rv;
747}
748
749/**
750 * \brief Returns a map of trigger literals as sequences of CharReach, grouped
751 * by top index.
752 */
753static
754void findTriggerSequences(const RoseBuildImpl &tbi,
755 const set<PredTopPair> &triggers,
756 map<u32, vector<vector<CharReach> > > *trigger_lits) {
757 map<u32, set<u32> > lit_ids_by_top;
758 for (const PredTopPair &t : triggers) {
759 insert(&lit_ids_by_top[t.top], tbi.g[t.pred].literals);
760 }
761
762 for (const auto &e : lit_ids_by_top) {
763 const u32 top = e.first;
764 const set<u32> &lit_ids = e.second;
765
766 for (u32 id : lit_ids) {
767 const rose_literal_id &lit = tbi.literals.at(id);
768 (*trigger_lits)[top].push_back(as_cr_seq(lit));
769 }
770 }
771}
772
773static
774bytecode_ptr<NFA> makeLeftNfa(const RoseBuildImpl &tbi, left_id &left,
775 const bool is_prefix, const bool is_transient,
776 const map<left_id, set<PredTopPair>> &infixTriggers,
777 const CompileContext &cc) {
778 const ReportManager &rm = tbi.rm;
779
780 bytecode_ptr<NFA> n;
781
782 // Should compress state if this rose is non-transient and we're in
783 // streaming mode.
784 const bool compress_state = !is_transient;
785
786 assert(is_prefix || !left.graph() || left.graph()->kind == NFA_INFIX);
787 assert(!is_prefix || !left.graph() || left.graph()->kind == NFA_PREFIX
788 || left.graph()->kind == NFA_EAGER_PREFIX);
789
790 // Holder should be implementable as an NFA at the very least.
791 if (!left.dfa() && left.graph()) {
792 assert(isImplementableNFA(*left.graph(), nullptr, cc));
793 }
794
795 map<u32, u32> fixed_depth_tops;
796 if (!is_prefix /* infix */) {
797 const set<PredTopPair> &triggers = infixTriggers.at(left);
798 findFixedDepthTops(tbi.g, triggers, &fixed_depth_tops);
799 }
800
801 if (left.castle()) {
802 assert(!is_prefix);
803 map<u32, vector<vector<CharReach> > > triggers;
804 findTriggerSequences(tbi, infixTriggers.at(left), &triggers);
805 n = buildRepeatEngine(*left.castle(), triggers, cc, rm);
806 assert(n);
807 return n; // Castles/LBRs are always best!
808 }
809
810 if (left.dfa()) {
811 n = getDfa(*left.dfa(), is_transient, cc, rm);
812 } else if (left.graph() && cc.grey.roseMcClellanPrefix == 2 && is_prefix &&
813 !is_transient) {
814 auto rdfa = buildMcClellan(*left.graph(), nullptr, cc.grey);
815 if (rdfa) {
816 n = getDfa(*rdfa, is_transient, cc, rm);
817 assert(n);
818 }
819 }
820
821 // We can attempt to build LBRs for infixes.
822 if (!n && !is_prefix && left.graph() && onlyOneTop(*left.graph())) {
823 map<u32, vector<vector<CharReach> > > triggers;
824 findTriggerSequences(tbi, infixTriggers.at(left), &triggers);
825 assert(triggers.size() == 1); // single top
826 n = constructLBR(*left.graph(), triggers.begin()->second, cc, rm);
827 }
828
829 if (!n && left.graph()) {
830 map<u32, vector<vector<CharReach>>> triggers;
831 if (left.graph()->kind == NFA_INFIX) {
832 findTriggerSequences(tbi, infixTriggers.at(left), &triggers);
833 }
834 n = constructNFA(*left.graph(), nullptr, fixed_depth_tops, triggers,
835 compress_state, cc);
836 }
837
838 if (cc.grey.roseMcClellanPrefix == 1 && is_prefix && !left.dfa()
839 && left.graph()
840 && (!n || !has_bounded_repeats_other_than_firsts(*n) || !is_fast(*n))) {
841 auto rdfa = buildMcClellan(*left.graph(), nullptr, cc.grey);
842 if (rdfa) {
843 auto d = getDfa(*rdfa, is_transient, cc, rm);
844 assert(d);
845 n = pickImpl(move(d), move(n));
846 }
847 }
848
849 return n;
850}
851
852static
853void setLeftNfaProperties(NFA &n, const left_id &left) {
854 depth min_width = findMinWidth(left);
855 DEBUG_PRINTF("min_width=%s\n", min_width.str().c_str());
856 u32 min_width_value = min_width.is_finite() ? (u32)min_width : 0;
857 n.minWidth = min_width_value;
858
859 depth max_width = findMaxWidth(left);
860 DEBUG_PRINTF("max_width=%s\n", max_width.str().c_str());
861 u32 max_width_value = max_width.is_finite() ? (u32)max_width : 0;
862 n.maxWidth = max_width_value;
863
864 // FIXME: NFA::maxOffset in Rose can't be found from reports as they don't
865 // map to internal_report structures; it would have to come from the Rose
866 // graph.
867}
868
869static
870void appendTailToHolder(NGHolder &h, const flat_set<ReportID> &reports,
871 const vector<NFAVertex> &starts,
872 const vector<CharReach> &tail) {
873 assert(!tail.empty());
874 NFAVertex curr = add_vertex(h);
875 for (NFAVertex v : starts) {
876 assert(!edge(v, h.acceptEod, h).second);
877 assert(h[v].reports == reports);
878 h[v].reports.clear();
879 remove_edge(v, h.accept, h);
880 add_edge(v, curr, h);
881 }
882 auto it = tail.begin();
883 h[curr].char_reach = *it;
884 ++it;
885 while (it != tail.end()) {
886 NFAVertex old = curr;
887 curr = add_vertex(h);
888 add_edge(old, curr, h);
889 assert(!it->none());
890 h[curr].char_reach = *it;
891 ++it;
892 }
893
894 h[curr].reports = reports;
895 add_edge(curr, h.accept, h);
896}
897
898static
899void appendTailToHolder(NGHolder &h, const vector<CharReach> &tail) {
900 assert(in_degree(h.acceptEod, h) == 1);
901 assert(!tail.empty());
902
903 map<flat_set<ReportID>, vector<NFAVertex> > reporters;
904 for (auto v : inv_adjacent_vertices_range(h.accept, h)) {
905 reporters[h[v].reports].push_back(v);
906 }
907
908 for (const auto &e : reporters) {
909 appendTailToHolder(h, e.first, e.second, tail);
910 }
911
912 renumber_edges(h);
913}
914
915static
916u32 decreaseLag(const RoseBuildImpl &build, NGHolder &h,
917 const vector<RoseVertex> &succs) {
918 const RoseGraph &rg = build.g;
919 static const size_t MAX_RESTORE_LEN = 5;
920
921 vector<CharReach> restored(MAX_RESTORE_LEN);
922 for (RoseVertex v : succs) {
923 u32 lag = rg[v].left.lag;
924 for (u32 lit_id : rg[v].literals) {
925 u32 delay = build.literals.at(lit_id).delay;
926 const ue2_literal &literal = build.literals.at(lit_id).s;
927 assert(lag <= literal.length() + delay);
928 size_t base = literal.length() + delay - lag;
929 if (base >= literal.length()) {
930 return 0;
931 }
932 size_t len = literal.length() - base;
933 len = MIN(len, restored.size());
934 restored.resize(len);
935 auto lit_it = literal.begin() + base;
936 for (u32 i = 0; i < len; i++) {
937 assert(lit_it != literal.end());
938 restored[i] |= *lit_it;
939 ++lit_it;
940 }
941 }
942 }
943
944 assert(!restored.empty());
945
946 appendTailToHolder(h, restored);
947
948 return restored.size();
949}
950
951#define EAGER_DIE_BEFORE_LIMIT 10
952
953struct eager_info {
954 shared_ptr<NGHolder> new_graph;
955 u32 lag_adjust = 0;
956};
957
958static
959bool checkSuitableForEager(bool is_prefix, const left_id &left,
960 const RoseBuildImpl &build,
961 const vector<RoseVertex> &succs,
962 rose_group squash_mask, rose_group initial_groups,
963 eager_info &ei, const CompileContext &cc) {
964 DEBUG_PRINTF("checking prefix --> %016llx...\n", squash_mask);
965
966 const RoseGraph &rg = build.g;
967
968 if (!is_prefix) {
969 DEBUG_PRINTF("not prefix\n");
970 return false; /* only prefixes (for now...) */
971 }
972
973 if ((initial_groups & squash_mask) == initial_groups) {
974 DEBUG_PRINTF("no squash -- useless\n");
975 return false;
976 }
977
978 for (RoseVertex s : succs) {
979 if (build.isInETable(s)
980 || contains(rg[s].literals, build.eod_event_literal_id)) {
981 return false; /* Ignore EOD related prefixes */
982 }
983 }
984
985 if (left.dfa()) {
986 const raw_dfa &dfa = *left.dfa();
987 if (dfa.start_floating != DEAD_STATE) {
988 return false; /* not purely anchored */
989 }
990 if (!dfa.states[dfa.start_anchored].reports.empty()) {
991 return false; /* vacuous (todo: handle?) */
992 }
993
994 if (!can_die_early(dfa, EAGER_DIE_BEFORE_LIMIT)) {
995 return false;
996 }
997 ei.new_graph = rg[succs[0]].left.graph;
998 } else if (left.graph()) {
999 const NGHolder &g = *left.graph();
1000 if (proper_out_degree(g.startDs, g)) {
1001 return false; /* not purely anchored */
1002 }
1003
1004 ei.new_graph = cloneHolder(*left.graph());
1005 auto gg = ei.new_graph;
1006 gg->kind = NFA_EAGER_PREFIX;
1007
1008 ei.lag_adjust = decreaseLag(build, *gg, succs);
1009
1010 if (is_match_vertex(gg->start, *gg)) {
1011 return false; /* should not still be vacuous as lag decreased */
1012 }
1013
1014 if (!can_die_early(*gg, EAGER_DIE_BEFORE_LIMIT)) {
1015 DEBUG_PRINTF("not eager as stuck alive\n");
1016 return false;
1017 }
1018
1019 /* We need to ensure that adding in the literals does not cause us to no
1020 * longer be able to build an nfa. */
1021 bool ok = isImplementableNFA(*gg, nullptr, cc);
1022 if (!ok) {
1023 return false;
1024 }
1025 } else {
1026 DEBUG_PRINTF("unable to determine if good for eager running\n");
1027 return false;
1028 }
1029
1030 DEBUG_PRINTF("eager prefix\n");
1031 return true;
1032}
1033
1034static
1035left_id updateLeftfixWithEager(RoseGraph &g, const eager_info &ei,
1036 const vector<RoseVertex> &succs) {
1037 u32 lag_adjust = ei.lag_adjust;
1038 auto gg = ei.new_graph;
1039 for (RoseVertex v : succs) {
1040 g[v].left.graph = gg;
1041 assert(g[v].left.lag >= lag_adjust);
1042 g[v].left.lag -= lag_adjust;
1043 DEBUG_PRINTF("added %u literal chars back, new lag %u\n", lag_adjust,
1044 g[v].left.lag);
1045 }
1046 left_id leftfix = g[succs[0]].left;
1047
1048 if (leftfix.graph()) {
1049 assert(leftfix.graph()->kind == NFA_PREFIX
1050 || leftfix.graph()->kind == NFA_EAGER_PREFIX);
1051 leftfix.graph()->kind = NFA_EAGER_PREFIX;
1052 }
1053 if (leftfix.dfa()) {
1054 assert(leftfix.dfa()->kind == NFA_PREFIX);
1055 leftfix.dfa()->kind = NFA_EAGER_PREFIX;
1056 }
1057
1058 return leftfix;
1059}
1060
1061static
1062void enforceEngineSizeLimit(const NFA *n, const Grey &grey) {
1063 const size_t nfa_size = n->length;
1064 // Global limit.
1065 if (nfa_size > grey.limitEngineSize) {
1066 throw ResourceLimitError();
1067 }
1068
1069 // Type-specific limit checks follow.
1070
1071 if (isDfaType(n->type)) {
1072 if (nfa_size > grey.limitDFASize) {
1073 throw ResourceLimitError();
1074 }
1075 } else if (isNfaType(n->type)) {
1076 if (nfa_size > grey.limitNFASize) {
1077 throw ResourceLimitError();
1078 }
1079 } else if (isLbrType(n->type)) {
1080 if (nfa_size > grey.limitLBRSize) {
1081 throw ResourceLimitError();
1082 }
1083 }
1084}
1085
1086static
1087bool buildLeftfix(RoseBuildImpl &build, build_context &bc, bool prefix, u32 qi,
1088 const map<left_id, set<PredTopPair> > &infixTriggers,
1089 set<u32> *no_retrigger_queues, set<u32> *eager_queues,
1090 const map<left_id, eager_info> &eager,
1091 const vector<RoseVertex> &succs, left_id leftfix) {
1092 RoseGraph &g = build.g;
1093 const CompileContext &cc = build.cc;
1094 const ReportManager &rm = build.rm;
1095
1096 bool is_transient = contains(build.transient, leftfix);
1097 rose_group squash_mask = build.rose_squash_masks.at(leftfix);
1098
1099 DEBUG_PRINTF("making %sleftfix\n", is_transient ? "transient " : "");
1100
1101 if (contains(eager, leftfix)) {
1102 eager_queues->insert(qi);
1103 leftfix = updateLeftfixWithEager(g, eager.at(leftfix), succs);
1104 }
1105
1106 bytecode_ptr<NFA> nfa;
1107 // Need to build NFA, which is either predestined to be a Haig (in SOM mode)
1108 // or could be all manner of things.
1109 if (leftfix.haig()) {
1110 nfa = goughCompile(*leftfix.haig(), build.ssm.somPrecision(), cc, rm);
1111 } else {
1112 nfa = makeLeftNfa(build, leftfix, prefix, is_transient, infixTriggers,
1113 cc);
1114 }
1115
1116 if (!nfa) {
1117 assert(!"failed to build leftfix");
1118 return false;
1119 }
1120
1121 setLeftNfaProperties(*nfa, leftfix);
1122
1123 nfa->queueIndex = qi;
1124 enforceEngineSizeLimit(nfa.get(), cc.grey);
1125 bc.engine_info_by_queue.emplace(nfa->queueIndex,
1126 engine_info(nfa.get(), is_transient));
1127
1128 if (!prefix && !leftfix.haig() && leftfix.graph()
1129 && nfaStuckOn(*leftfix.graph())) {
1130 DEBUG_PRINTF("%u sticks on\n", qi);
1131 no_retrigger_queues->insert(qi);
1132 }
1133
1134 DEBUG_PRINTF("built leftfix, qi=%u\n", qi);
1135 add_nfa_to_blob(bc, *nfa);
1136
1137 // Leftfixes can have stop alphabets.
1138 vector<u8> stop(N_CHARS, 0);
1139 /* haigs track som information - need more care */
1140 som_type som = leftfix.haig() ? SOM_LEFT : SOM_NONE;
1141 if (leftfix.graph()) {
1142 stop = findLeftOffsetStopAlphabet(*leftfix.graph(), som);
1143 } else if (leftfix.castle()) {
1144 stop = findLeftOffsetStopAlphabet(*leftfix.castle(), som);
1145 }
1146
1147 // Infix NFAs can have bounds on their queue lengths.
1148 u32 max_queuelen = UINT32_MAX;
1149 if (!prefix) {
1150 set<ue2_literal> lits;
1151 for (RoseVertex v : succs) {
1152 for (auto u : inv_adjacent_vertices_range(v, g)) {
1153 for (u32 lit_id : g[u].literals) {
1154 lits.insert(build.literals.at(lit_id).s);
1155 }
1156 }
1157 }
1158 DEBUG_PRINTF("%zu literals\n", lits.size());
1159 max_queuelen = findMaxInfixMatches(leftfix, lits);
1160 if (max_queuelen < UINT32_MAX) {
1161 max_queuelen++;
1162 }
1163 }
1164
1165 u32 max_width;
1166 if (is_transient) {
1167 depth d = findMaxWidth(leftfix);
1168 assert(d.is_finite());
1169 max_width = d;
1170 } else {
1171 max_width = 0;
1172 }
1173
1174 u8 cm_count = 0;
1175 CharReach cm_cr;
1176 if (cc.grey.allowCountingMiracles) {
1177 findCountingMiracleInfo(leftfix, stop, &cm_count, &cm_cr);
1178 }
1179
1180 for (RoseVertex v : succs) {
1181 bc.leftfix_info.emplace(v, left_build_info(qi, g[v].left.lag, max_width,
1182 squash_mask, stop,
1183 max_queuelen, cm_count,
1184 cm_cr));
1185 }
1186
1187 return true;
1188}
1189
1190static
1191unique_ptr<TamaInfo> constructTamaInfo(const RoseGraph &g,
1192 const vector<ExclusiveSubengine> &subengines,
1193 const bool is_suffix) {
1194 unique_ptr<TamaInfo> tamaInfo = ue2::make_unique<TamaInfo>();
1195 for (const auto &sub : subengines) {
1196 const auto &rose_vertices = sub.vertices;
1197 NFA *nfa = sub.nfa.get();
1198 set<u32> tops;
1199 for (const auto &v : rose_vertices) {
1200 if (is_suffix) {
1201 tops.insert(g[v].suffix.top);
1202 } else {
1203 for (const auto &e : in_edges_range(v, g)) {
1204 tops.insert(g[e].rose_top);
1205 }
1206 }
1207 }
1208 tamaInfo->add(nfa, tops);
1209 }
1210
1211 return tamaInfo;
1212}
1213
1214static
1215void updateTops(const RoseGraph &g, const TamaInfo &tamaInfo,
1216 TamaProto &tamaProto,
1217 const vector<ExclusiveSubengine> &subengines,
1218 const map<pair<const NFA *, u32>, u32> &out_top_remap,
1219 const bool is_suffix) {
1220 u32 i = 0;
1221 for (const auto &n : tamaInfo.subengines) {
1222 for (const auto &v : subengines[i].vertices) {
1223 if (is_suffix) {
1224 tamaProto.add(n, g[v].index, g[v].suffix.top, out_top_remap);
1225 } else {
1226 for (const auto &e : in_edges_range(v, g)) {
1227 tamaProto.add(n, g[v].index, g[e].rose_top, out_top_remap);
1228 }
1229 }
1230 }
1231 i++;
1232 }
1233}
1234
1235static
1236shared_ptr<TamaProto> constructContainerEngine(const RoseGraph &g,
1237 build_context &bc,
1238 const ExclusiveInfo &info,
1239 const u32 queue,
1240 const bool is_suffix,
1241 const Grey &grey) {
1242 const auto &subengines = info.subengines;
1243 auto tamaInfo = constructTamaInfo(g, subengines, is_suffix);
1244
1245 map<pair<const NFA *, u32>, u32> out_top_remap;
1246 auto n = buildTamarama(*tamaInfo, queue, out_top_remap);
1247 enforceEngineSizeLimit(n.get(), grey);
1248 bc.engine_info_by_queue.emplace(n->queueIndex, engine_info(n.get(), false));
1249 add_nfa_to_blob(bc, *n);
1250
1251 DEBUG_PRINTF("queue id:%u\n", queue);
1252 shared_ptr<TamaProto> tamaProto = make_shared<TamaProto>();
1253 tamaProto->reports = info.reports;
1254 updateTops(g, *tamaInfo, *tamaProto, subengines, out_top_remap, is_suffix);
1255 return tamaProto;
1256}
1257
1258static
1259void buildInfixContainer(RoseGraph &g, build_context &bc,
1260 const vector<ExclusiveInfo> &exclusive_info,
1261 const Grey &grey) {
1262 // Build tamarama engine
1263 for (const auto &info : exclusive_info) {
1264 const u32 queue = info.queue;
1265 const auto &subengines = info.subengines;
1266 auto tamaProto =
1267 constructContainerEngine(g, bc, info, queue, false, grey);
1268
1269 for (const auto &sub : subengines) {
1270 const auto &verts = sub.vertices;
1271 for (const auto &v : verts) {
1272 DEBUG_PRINTF("vert id:%zu\n", g[v].index);
1273 g[v].left.tamarama = tamaProto;
1274 }
1275 }
1276 }
1277}
1278
1279static
1280void buildSuffixContainer(RoseGraph &g, build_context &bc,
1281 const vector<ExclusiveInfo> &exclusive_info,
1282 const Grey &grey) {
1283 // Build tamarama engine
1284 for (const auto &info : exclusive_info) {
1285 const u32 queue = info.queue;
1286 const auto &subengines = info.subengines;
1287 auto tamaProto = constructContainerEngine(g, bc, info, queue, true,
1288 grey);
1289 for (const auto &sub : subengines) {
1290 const auto &verts = sub.vertices;
1291 for (const auto &v : verts) {
1292 DEBUG_PRINTF("vert id:%zu\n", g[v].index);
1293 g[v].suffix.tamarama = tamaProto;
1294 }
1295 const auto &v = verts[0];
1296 suffix_id newSuffix(g[v].suffix);
1297 bc.suffixes.emplace(newSuffix, queue);
1298 }
1299 }
1300}
1301
1302static
1303void updateExclusiveInfixProperties(const RoseBuildImpl &build,
1304 const vector<ExclusiveInfo> &exclusive_info,
1305 map<RoseVertex, left_build_info> &leftfix_info,
1306 set<u32> *no_retrigger_queues) {
1307 const RoseGraph &g = build.g;
1308 for (const auto &info : exclusive_info) {
1309 // Set leftfix optimisations, disabled for tamarama subengines
1310 rose_group squash_mask = ~rose_group{0};
1311 // Leftfixes can have stop alphabets.
1312 vector<u8> stop(N_CHARS, 0);
1313 // Infix NFAs can have bounds on their queue lengths.
1314 u32 max_queuelen = 0;
1315 u32 max_width = 0;
1316 u8 cm_count = 0;
1317 CharReach cm_cr;
1318
1319 const auto &qi = info.queue;
1320 const auto &subengines = info.subengines;
1321 bool no_retrigger = true;
1322 for (const auto &sub : subengines) {
1323 const auto &verts = sub.vertices;
1324 const auto &v_first = verts[0];
1325 left_id leftfix(g[v_first].left);
1326 if (leftfix.haig() || !leftfix.graph() ||
1327 !nfaStuckOn(*leftfix.graph())) {
1328 no_retrigger = false;
1329 }
1330
1331 for (const auto &v : verts) {
1332 set<ue2_literal> lits;
1333 for (auto u : inv_adjacent_vertices_range(v, build.g)) {
1334 for (u32 lit_id : build.g[u].literals) {
1335 lits.insert(build.literals.at(lit_id).s);
1336 }
1337 }
1338 DEBUG_PRINTF("%zu literals\n", lits.size());
1339
1340 u32 queuelen = findMaxInfixMatches(leftfix, lits);
1341 if (queuelen < UINT32_MAX) {
1342 queuelen++;
1343 }
1344 max_queuelen = max(max_queuelen, queuelen);
1345 }
1346 }
1347
1348 if (no_retrigger) {
1349 no_retrigger_queues->insert(qi);
1350 }
1351
1352 for (const auto &sub : subengines) {
1353 const auto &verts = sub.vertices;
1354 for (const auto &v : verts) {
1355 u32 lag = g[v].left.lag;
1356 leftfix_info.emplace(v, left_build_info(qi, lag, max_width,
1357 squash_mask, stop,
1358 max_queuelen, cm_count,
1359 cm_cr));
1360 }
1361 }
1362 }
1363}
1364
1365static
1366void updateExclusiveSuffixProperties(const RoseBuildImpl &build,
1367 const vector<ExclusiveInfo> &exclusive_info,
1368 set<u32> *no_retrigger_queues) {
1369 const RoseGraph &g = build.g;
1370 for (auto &info : exclusive_info) {
1371 const auto &qi = info.queue;
1372 const auto &subengines = info.subengines;
1373 bool no_retrigger = true;
1374 for (const auto &sub : subengines) {
1375 const auto &v_first = sub.vertices[0];
1376 suffix_id suffix(g[v_first].suffix);
1377 if (!suffix.graph() || !nfaStuckOn(*suffix.graph())) {
1378 no_retrigger = false;
1379 break;
1380 }
1381 }
1382
1383 if (no_retrigger) {
1384 no_retrigger_queues->insert(qi);
1385 }
1386 }
1387}
1388
1389static
1390void buildExclusiveInfixes(RoseBuildImpl &build, build_context &bc,
1391 QueueIndexFactory &qif,
1392 const map<left_id, set<PredTopPair>> &infixTriggers,
1393 const map<u32, vector<RoseVertex>> &vertex_map,
1394 const vector<vector<u32>> &groups,
1395 set<u32> *no_retrigger_queues) {
1396 RoseGraph &g = build.g;
1397 const CompileContext &cc = build.cc;
1398
1399 vector<ExclusiveInfo> exclusive_info;
1400 for (const auto &gp : groups) {
1401 ExclusiveInfo info;
1402 for (const auto &id : gp) {
1403 const auto &verts = vertex_map.at(id);
1404 left_id leftfix(g[verts[0]].left);
1405
1406 bool is_transient = false;
1407 auto n = makeLeftNfa(build, leftfix, false, is_transient,
1408 infixTriggers, cc);
1409 assert(n);
1410
1411 setLeftNfaProperties(*n, leftfix);
1412
1413 ExclusiveSubengine engine;
1414 engine.nfa = move(n);
1415 engine.vertices = verts;
1416 info.subengines.push_back(move(engine));
1417 }
1418 info.queue = qif.get_queue();
1419 exclusive_info.push_back(move(info));
1420 }
1421 updateExclusiveInfixProperties(build, exclusive_info, bc.leftfix_info,
1422 no_retrigger_queues);
1423 buildInfixContainer(g, bc, exclusive_info, build.cc.grey);
1424}
1425
1426static
1427void findExclusiveInfixes(RoseBuildImpl &build, build_context &bc,
1428 QueueIndexFactory &qif,
1429 const map<left_id, set<PredTopPair>> &infixTriggers,
1430 set<u32> *no_retrigger_queues) {
1431 const RoseGraph &g = build.g;
1432
1433 set<RoleInfo<left_id>> roleInfoSet;
1434 map<u32, vector<RoseVertex>> vertex_map;
1435
1436 u32 role_id = 0;
1437 map<left_id, u32> leftfixes;
1438 for (auto v : vertices_range(g)) {
1439 if (!g[v].left || build.isRootSuccessor(v)) {
1440 continue;
1441 }
1442
1443 left_id leftfix(g[v].left);
1444
1445 // Sanity check: our NFA should contain each of the tops mentioned on
1446 // our in-edges.
1447 assert(roseHasTops(build, v));
1448
1449 if (contains(leftfixes, leftfix)) {
1450 // NFA already built.
1451 u32 id = leftfixes[leftfix];
1452 if (contains(vertex_map, id)) {
1453 vertex_map[id].push_back(v);
1454 }
1455 DEBUG_PRINTF("sharing leftfix, id=%u\n", id);
1456 continue;
1457 }
1458
1459 if (leftfix.haig()) {
1460 continue;
1461 }
1462
1463 if (leftfix.graph() || leftfix.castle()) {
1464 leftfixes.emplace(leftfix, role_id);
1465 vertex_map[role_id].push_back(v);
1466
1467 map<u32, vector<vector<CharReach>>> triggers;
1468 findTriggerSequences(build, infixTriggers.at(leftfix), &triggers);
1469 RoleInfo<left_id> info(leftfix, role_id);
1470 if (setTriggerLiteralsInfix(info, triggers)) {
1471 roleInfoSet.insert(info);
1472 }
1473 role_id++;
1474 }
1475 }
1476
1477 if (leftfixes.size() > 1) {
1478 DEBUG_PRINTF("leftfix size:%zu\n", leftfixes.size());
1479 vector<vector<u32>> groups;
1480 exclusiveAnalysisInfix(build, vertex_map, roleInfoSet, groups);
1481 buildExclusiveInfixes(build, bc, qif, infixTriggers, vertex_map,
1482 groups, no_retrigger_queues);
1483 }
1484}
1485
1486static
1487bool buildLeftfixes(RoseBuildImpl &tbi, build_context &bc,
1488 QueueIndexFactory &qif, set<u32> *no_retrigger_queues,
1489 set<u32> *eager_queues, bool do_prefix) {
1490 RoseGraph &g = tbi.g;
1491 const CompileContext &cc = tbi.cc;
1492
1493 map<left_id, set<PredTopPair>> infixTriggers;
1494 findInfixTriggers(tbi, &infixTriggers);
1495
1496 insertion_ordered_map<left_id, vector<RoseVertex>> succs;
1497
1498 if (cc.grey.allowTamarama && cc.streaming && !do_prefix) {
1499 findExclusiveInfixes(tbi, bc, qif, infixTriggers, no_retrigger_queues);
1500 }
1501
1502 for (auto v : vertices_range(g)) {
1503 if (!g[v].left || g[v].left.tamarama) {
1504 continue;
1505 }
1506
1507 assert(tbi.isNonRootSuccessor(v) != tbi.isRootSuccessor(v));
1508 bool is_prefix = tbi.isRootSuccessor(v);
1509
1510 if (do_prefix != is_prefix) {
1511 /* we require prefixes and then infixes */
1512 continue;
1513 }
1514
1515 left_id leftfix(g[v].left);
1516
1517 // Sanity check: our NFA should contain each of the tops mentioned on
1518 // our in-edges.
1519 assert(roseHasTops(tbi, v));
1520
1521 bool is_transient = contains(tbi.transient, leftfix);
1522
1523 // Transient leftfixes can sometimes be implemented solely with
1524 // lookarounds, in which case we don't need to build an engine.
1525 // TODO: Handle SOM-tracking cases as well.
1526 if (cc.grey.roseLookaroundMasks && is_transient &&
1527 !g[v].left.tracksSom()) {
1528 vector<vector<LookEntry>> lookaround;
1529 if (makeLeftfixLookaround(tbi, v, lookaround)) {
1530 DEBUG_PRINTF("implementing as lookaround!\n");
1531 bc.leftfix_info.emplace(v, left_build_info(lookaround));
1532 continue;
1533 }
1534 }
1535
1536 succs[leftfix].push_back(v);
1537 }
1538
1539 rose_group initial_groups = tbi.getInitialGroups();
1540 rose_group combined_eager_squashed_mask = ~0ULL;
1541
1542 map<left_id, eager_info> eager;
1543
1544 for (const auto &m : succs) {
1545 const left_id &leftfix = m.first;
1546 const auto &left_succs = m.second;
1547
1548 rose_group squash_mask = tbi.rose_squash_masks.at(leftfix);
1549 eager_info ei;
1550
1551 if (checkSuitableForEager(do_prefix, leftfix, tbi, left_succs,
1552 squash_mask, initial_groups, ei, cc)) {
1553 eager[leftfix] = ei;
1554 combined_eager_squashed_mask &= squash_mask;
1555 DEBUG_PRINTF("combo %016llx...\n", combined_eager_squashed_mask);
1556 }
1557 }
1558
1559 if (do_prefix && combined_eager_squashed_mask & initial_groups) {
1560 DEBUG_PRINTF("eager groups won't squash everyone - be lazy\n");
1561 eager_queues->clear();
1562 eager.clear();
1563 }
1564
1565 for (const auto &m : succs) {
1566 const left_id &leftfix = m.first;
1567 const auto &left_succs = m.second;
1568 buildLeftfix(tbi, bc, do_prefix, qif.get_queue(), infixTriggers,
1569 no_retrigger_queues, eager_queues, eager, left_succs,
1570 leftfix);
1571 }
1572
1573 return true;
1574}
1575
1576static
1577void findSuffixTriggers(const RoseBuildImpl &tbi,
1578 map<suffix_id, set<PredTopPair> > *suffixTriggers) {
1579 const RoseGraph &g = tbi.g;
1580 for (auto v : vertices_range(g)) {
1581 if (!g[v].suffix) {
1582 continue;
1583 }
1584 PredTopPair ptp(v, g[v].suffix.top);
1585 (*suffixTriggers)[g[v].suffix].insert(ptp);
1586 }
1587}
1588
1589static
1590bool hasNonSmallBlockOutfix(const vector<OutfixInfo> &outfixes) {
1591 for (const auto &out : outfixes) {
1592 if (!out.in_sbmatcher) {
1593 return true;
1594 }
1595 }
1596 return false;
1597}
1598
1599namespace {
1600class OutfixBuilder : public boost::static_visitor<bytecode_ptr<NFA>> {
1601public:
1602 explicit OutfixBuilder(const RoseBuildImpl &build_in) : build(build_in) {}
1603
1604 bytecode_ptr<NFA> operator()(boost::blank&) const {
1605 return nullptr;
1606 };
1607
1608 bytecode_ptr<NFA> operator()(unique_ptr<raw_dfa> &rdfa) const {
1609 // Unleash the mighty DFA!
1610 return getDfa(*rdfa, false, build.cc, build.rm);
1611 }
1612
1613 bytecode_ptr<NFA> operator()(unique_ptr<raw_som_dfa> &haig) const {
1614 // Unleash the Goughfish!
1615 return goughCompile(*haig, build.ssm.somPrecision(), build.cc,
1616 build.rm);
1617 }
1618
1619 bytecode_ptr<NFA> operator()(unique_ptr<NGHolder> &holder) const {
1620 const CompileContext &cc = build.cc;
1621 const ReportManager &rm = build.rm;
1622
1623 NGHolder &h = *holder;
1624 assert(h.kind == NFA_OUTFIX);
1625
1626 // Build NFA.
1627 const map<u32, u32> fixed_depth_tops; /* no tops */
1628 const map<u32, vector<vector<CharReach>>> triggers; /* no tops */
1629 bool compress_state = cc.streaming;
1630 auto n = constructNFA(h, &rm, fixed_depth_tops, triggers,
1631 compress_state, cc);
1632
1633 // Try for a DFA upgrade.
1634 if (n && cc.grey.roseMcClellanOutfix &&
1635 !has_bounded_repeats_other_than_firsts(*n)) {
1636 auto rdfa = buildMcClellan(h, &rm, cc.grey);
1637 if (rdfa) {
1638 auto d = getDfa(*rdfa, false, cc, rm);
1639 if (d) {
1640 n = pickImpl(move(d), move(n));
1641 }
1642 }
1643 }
1644
1645 return n;
1646 }
1647
1648 bytecode_ptr<NFA> operator()(UNUSED MpvProto &mpv) const {
1649 // MPV construction handled separately.
1650 assert(mpv.puffettes.empty());
1651 return nullptr;
1652 }
1653
1654private:
1655 const RoseBuildImpl &build;
1656};
1657}
1658
1659static
1660bytecode_ptr<NFA> buildOutfix(const RoseBuildImpl &build, OutfixInfo &outfix) {
1661 assert(!outfix.is_dead()); // should not be marked dead.
1662
1663 auto n = boost::apply_visitor(OutfixBuilder(build), outfix.proto);
1664 if (n && build.cc.grey.reverseAccelerate) {
1665 buildReverseAcceleration(n.get(), outfix.rev_info, outfix.minWidth);
1666 }
1667
1668 return n;
1669}
1670
1671static
1672void prepMpv(RoseBuildImpl &tbi, build_context &bc, size_t *historyRequired,
1673 bool *mpv_as_outfix) {
1674 assert(bc.engineOffsets.empty()); // MPV should be first
1675 *mpv_as_outfix = false;
1676 OutfixInfo *mpv_outfix = nullptr;
1677
1678 /* assume outfixes are just above chain tails in queue indices */
1679 for (auto &out : tbi.outfixes) {
1680 if (out.is_nonempty_mpv()) {
1681 assert(!mpv_outfix);
1682 mpv_outfix = &out;
1683 } else {
1684 assert(!out.mpv());
1685 }
1686 }
1687
1688 if (!mpv_outfix) {
1689 return;
1690 }
1691
1692 auto *mpv = mpv_outfix->mpv();
1693 auto nfa = mpvCompile(mpv->puffettes, mpv->triggered_puffettes, tbi.rm);
1694 assert(nfa);
1695 if (!nfa) {
1696 throw CompileError("Unable to generate bytecode.");
1697 }
1698
1699 if (tbi.cc.grey.reverseAccelerate) {
1700 buildReverseAcceleration(nfa.get(), mpv_outfix->rev_info,
1701 mpv_outfix->minWidth);
1702 }
1703
1704 u32 qi = mpv_outfix->get_queue(tbi.qif);
1705 nfa->queueIndex = qi;
1706 enforceEngineSizeLimit(nfa.get(), tbi.cc.grey);
1707 bc.engine_info_by_queue.emplace(nfa->queueIndex,
1708 engine_info(nfa.get(), false));
1709
1710 DEBUG_PRINTF("built mpv\n");
1711
1712 if (!*historyRequired && requires_decompress_key(*nfa)) {
1713 *historyRequired = 1;
1714 }
1715
1716 add_nfa_to_blob(bc, *nfa);
1717 *mpv_as_outfix = !mpv->puffettes.empty();
1718}
1719
1720static
1721void setOutfixProperties(NFA &n, const OutfixInfo &outfix) {
1722 depth min_width = outfix.minWidth;
1723 DEBUG_PRINTF("min_width=%s\n", min_width.str().c_str());
1724 u32 min_width_value = min_width.is_finite() ? (u32)min_width : 0;
1725 n.minWidth = min_width_value;
1726
1727 depth max_width = outfix.maxWidth;
1728 DEBUG_PRINTF("max_width=%s\n", max_width.str().c_str());
1729 u32 max_width_value = max_width.is_finite() ? (u32)max_width : 0;
1730 n.maxWidth = max_width_value;
1731
1732 DEBUG_PRINTF("max_offset=%llu\n", outfix.maxOffset);
1733 u32 max_offset_value = outfix.maxOffset < ~0U ? (u32)outfix.maxOffset : 0;
1734 n.maxOffset = max_offset_value;
1735
1736 DEBUG_PRINTF("maxBAWidth=%u\n", outfix.maxBAWidth);
1737 if (outfix.maxBAWidth != ROSE_BOUND_INF && outfix.maxBAWidth < 256) {
1738 n.maxBiAnchoredWidth = verify_u8(outfix.maxBAWidth);
1739 }
1740}
1741
1742static
1743bool prepOutfixes(RoseBuildImpl &tbi, build_context &bc,
1744 size_t *historyRequired) {
1745 if (tbi.cc.grey.onlyOneOutfix && tbi.outfixes.size() > 1) {
1746 DEBUG_PRINTF("we have %zu outfixes, but Grey::onlyOneOutfix is set\n",
1747 tbi.outfixes.size());
1748 throw ResourceLimitError();
1749 }
1750
1751 assert(tbi.qif.allocated_count() == bc.engineOffsets.size());
1752
1753 for (auto &out : tbi.outfixes) {
1754 if (out.mpv()) {
1755 continue; /* already done */
1756 }
1757 DEBUG_PRINTF("building outfix %zd\n", &out - &tbi.outfixes[0]);
1758 auto n = buildOutfix(tbi, out);
1759 if (!n) {
1760 assert(0);
1761 return false;
1762 }
1763
1764 setOutfixProperties(*n, out);
1765
1766 n->queueIndex = out.get_queue(tbi.qif);
1767 enforceEngineSizeLimit(n.get(), tbi.cc.grey);
1768 bc.engine_info_by_queue.emplace(n->queueIndex,
1769 engine_info(n.get(), false));
1770
1771 if (!*historyRequired && requires_decompress_key(*n)) {
1772 *historyRequired = 1;
1773 }
1774
1775 add_nfa_to_blob(bc, *n);
1776 }
1777
1778 return true;
1779}
1780
1781static
1782void assignSuffixQueues(RoseBuildImpl &build, map<suffix_id, u32> &suffixes) {
1783 const RoseGraph &g = build.g;
1784
1785 for (auto v : vertices_range(g)) {
1786 if (!g[v].suffix) {
1787 continue;
1788 }
1789
1790 const suffix_id s(g[v].suffix);
1791
1792 DEBUG_PRINTF("vertex %zu triggers suffix %p\n", g[v].index, s.graph());
1793
1794 // We may have already built this NFA.
1795 if (contains(suffixes, s)) {
1796 continue;
1797 }
1798
1799 u32 queue = build.qif.get_queue();
1800 DEBUG_PRINTF("assigning %p to queue %u\n", s.graph(), queue);
1801 suffixes.emplace(s, queue);
1802 }
1803}
1804
1805static
1806void setSuffixProperties(NFA &n, const suffix_id &suff,
1807 const ReportManager &rm) {
1808 depth min_width = findMinWidth(suff);
1809 DEBUG_PRINTF("min_width=%s\n", min_width.str().c_str());
1810 u32 min_width_value = min_width.is_finite() ? (u32)min_width : 0;
1811 n.minWidth = min_width_value;
1812
1813 depth max_width = findMaxWidth(suff);
1814 DEBUG_PRINTF("max_width=%s\n", max_width.str().c_str());
1815 u32 max_width_value = max_width.is_finite() ? (u32)max_width : 0;
1816 n.maxWidth = max_width_value;
1817
1818 u64a max_offset = findMaxOffset(all_reports(suff), rm);
1819 DEBUG_PRINTF("max_offset=%llu\n", max_offset);
1820 u32 max_offset_value = max_offset < ~0U ? (u32)max_offset : 0;
1821 n.maxOffset = max_offset_value;
1822}
1823
1824static
1825void buildExclusiveSuffixes(RoseBuildImpl &build, build_context &bc,
1826 QueueIndexFactory &qif,
1827 map<suffix_id, set<PredTopPair>> &suffixTriggers,
1828 const map<u32, vector<RoseVertex>> &vertex_map,
1829 const vector<vector<u32>> &groups,
1830 set<u32> *no_retrigger_queues) {
1831 RoseGraph &g = build.g;
1832
1833 vector<ExclusiveInfo> exclusive_info;
1834 for (const auto &gp : groups) {
1835 ExclusiveInfo info;
1836 for (const auto &id : gp) {
1837 const auto &verts = vertex_map.at(id);
1838 suffix_id s(g[verts[0]].suffix);
1839
1840 const set<PredTopPair> &s_triggers = suffixTriggers.at(s);
1841
1842 map<u32, u32> fixed_depth_tops;
1843 findFixedDepthTops(g, s_triggers, &fixed_depth_tops);
1844
1845 map<u32, vector<vector<CharReach>>> triggers;
1846 findTriggerSequences(build, s_triggers, &triggers);
1847
1848 auto n = buildSuffix(build.rm, build.ssm, fixed_depth_tops,
1849 triggers, s, build.cc);
1850 assert(n);
1851
1852 setSuffixProperties(*n, s, build.rm);
1853
1854 ExclusiveSubengine engine;
1855 engine.nfa = move(n);
1856 engine.vertices = verts;
1857 info.subengines.push_back(move(engine));
1858
1859 const auto &reports = all_reports(s);
1860 info.reports.insert(reports.begin(), reports.end());
1861 }
1862 info.queue = qif.get_queue();
1863 exclusive_info.push_back(move(info));
1864 }
1865 updateExclusiveSuffixProperties(build, exclusive_info,
1866 no_retrigger_queues);
1867 buildSuffixContainer(g, bc, exclusive_info, build.cc.grey);
1868}
1869
1870static
1871void findExclusiveSuffixes(RoseBuildImpl &tbi, build_context &bc,
1872 QueueIndexFactory &qif,
1873 map<suffix_id, set<PredTopPair>> &suffixTriggers,
1874 set<u32> *no_retrigger_queues) {
1875 const RoseGraph &g = tbi.g;
1876
1877 map<suffix_id, u32> suffixes;
1878 set<RoleInfo<suffix_id>> roleInfoSet;
1879 map<u32, vector<RoseVertex>> vertex_map;
1880 u32 role_id = 0;
1881 for (auto v : vertices_range(g)) {
1882 if (!g[v].suffix) {
1883 continue;
1884 }
1885
1886 const suffix_id s(g[v].suffix);
1887
1888 DEBUG_PRINTF("vertex %zu triggers suffix %p\n", g[v].index, s.graph());
1889
1890 // We may have already built this NFA.
1891 if (contains(suffixes, s)) {
1892 u32 id = suffixes[s];
1893 if (!tbi.isInETable(v)) {
1894 vertex_map[id].push_back(v);
1895 }
1896 continue;
1897 }
1898
1899 if (s.haig()) {
1900 continue;
1901 }
1902
1903 // Currently disable eod suffixes for exclusive analysis
1904 if (!tbi.isInETable(v) && (s.graph() || s.castle())) {
1905 DEBUG_PRINTF("assigning %p to id %u\n", s.graph(), role_id);
1906 suffixes.emplace(s, role_id);
1907
1908 vertex_map[role_id].push_back(v);
1909 const set<PredTopPair> &s_triggers = suffixTriggers.at(s);
1910 map<u32, vector<vector<CharReach>>> triggers;
1911 findTriggerSequences(tbi, s_triggers, &triggers);
1912
1913 RoleInfo<suffix_id> info(s, role_id);
1914 if (setTriggerLiteralsSuffix(info, triggers)) {
1915 roleInfoSet.insert(info);
1916 }
1917 role_id++;
1918 }
1919 }
1920
1921 if (suffixes.size() > 1) {
1922 DEBUG_PRINTF("suffix size:%zu\n", suffixes.size());
1923 vector<vector<u32>> groups;
1924 exclusiveAnalysisSuffix(tbi, vertex_map, roleInfoSet, groups);
1925 buildExclusiveSuffixes(tbi, bc, qif, suffixTriggers, vertex_map,
1926 groups, no_retrigger_queues);
1927 }
1928}
1929
1930static
1931bool buildSuffixes(const RoseBuildImpl &tbi, build_context &bc,
1932 set<u32> *no_retrigger_queues,
1933 const map<suffix_id, set<PredTopPair>> &suffixTriggers) {
1934 // To ensure compile determinism, build suffix engines in order of their
1935 // (unique) queue indices, so that we call add_nfa_to_blob in the same
1936 // order.
1937 vector<pair<u32, suffix_id>> ordered;
1938 for (const auto &e : bc.suffixes) {
1939 ordered.emplace_back(e.second, e.first);
1940 }
1941 sort(begin(ordered), end(ordered));
1942
1943 for (const auto &e : ordered) {
1944 const u32 queue = e.first;
1945 const suffix_id &s = e.second;
1946
1947 if (s.tamarama()) {
1948 continue;
1949 }
1950
1951 const set<PredTopPair> &s_triggers = suffixTriggers.at(s);
1952
1953 map<u32, u32> fixed_depth_tops;
1954 findFixedDepthTops(tbi.g, s_triggers, &fixed_depth_tops);
1955
1956 map<u32, vector<vector<CharReach>>> triggers;
1957 findTriggerSequences(tbi, s_triggers, &triggers);
1958
1959 auto n = buildSuffix(tbi.rm, tbi.ssm, fixed_depth_tops, triggers,
1960 s, tbi.cc);
1961 if (!n) {
1962 return false;
1963 }
1964
1965 setSuffixProperties(*n, s, tbi.rm);
1966
1967 n->queueIndex = queue;
1968 enforceEngineSizeLimit(n.get(), tbi.cc.grey);
1969 bc.engine_info_by_queue.emplace(n->queueIndex,
1970 engine_info(n.get(), false));
1971
1972 if (s.graph() && nfaStuckOn(*s.graph())) { /* todo: have corresponding
1973 * haig analysis */
1974 assert(!s.haig());
1975 DEBUG_PRINTF("%u sticks on\n", queue);
1976 no_retrigger_queues->insert(queue);
1977 }
1978
1979 add_nfa_to_blob(bc, *n);
1980 }
1981
1982 return true;
1983}
1984
1985static
1986void buildCountingMiracles(build_context &bc) {
1987 map<pair<CharReach, u8>, u32> pre_built;
1988
1989 for (left_build_info &lbi : bc.leftfix_info | map_values) {
1990 if (!lbi.countingMiracleCount) {
1991 continue;
1992 }
1993
1994 const CharReach &cr = lbi.countingMiracleReach;
1995 assert(!cr.all() && !cr.none());
1996
1997 auto key = make_pair(cr, lbi.countingMiracleCount);
1998 if (contains(pre_built, key)) {
1999 lbi.countingMiracleOffset = pre_built[key];
2000 continue;
2001 }
2002
2003 RoseCountingMiracle rcm;
2004 memset(&rcm, 0, sizeof(rcm));
2005
2006 if (cr.count() == 1) {
2007 rcm.c = cr.find_first();
2008 } else {
2009 rcm.shufti = 1;
2010 int rv = shuftiBuildMasks(cr, (u8 *)&rcm.lo, (u8 *)&rcm.hi);
2011 if (rv == -1) {
2012 DEBUG_PRINTF("failed to build shufti\n");
2013 lbi.countingMiracleCount = 0; /* remove counting miracle */
2014 continue;
2015 }
2016
2017 rcm.poison = (~cr).find_first();
2018 }
2019
2020 rcm.count = lbi.countingMiracleCount;
2021
2022 lbi.countingMiracleOffset = bc.engine_blob.add(rcm);
2023 pre_built[key] = lbi.countingMiracleOffset;
2024 DEBUG_PRINTF("built cm for count of %u @ %u\n", rcm.count,
2025 lbi.countingMiracleOffset);
2026 }
2027}
2028
2029/* Note: buildNfas may reduce the lag for vertices that have prefixes */
2030static
2031bool buildNfas(RoseBuildImpl &tbi, build_context &bc, QueueIndexFactory &qif,
2032 set<u32> *no_retrigger_queues, set<u32> *eager_queues,
2033 u32 *leftfixBeginQueue) {
2034 map<suffix_id, set<PredTopPair>> suffixTriggers;
2035 findSuffixTriggers(tbi, &suffixTriggers);
2036
2037 if (tbi.cc.grey.allowTamarama && tbi.cc.streaming) {
2038 findExclusiveSuffixes(tbi, bc, qif, suffixTriggers,
2039 no_retrigger_queues);
2040 }
2041
2042 assignSuffixQueues(tbi, bc.suffixes);
2043
2044 if (!buildSuffixes(tbi, bc, no_retrigger_queues, suffixTriggers)) {
2045 return false;
2046 }
2047 suffixTriggers.clear();
2048
2049 *leftfixBeginQueue = qif.allocated_count();
2050
2051 if (!buildLeftfixes(tbi, bc, qif, no_retrigger_queues, eager_queues,
2052 true)) {
2053 return false;
2054 }
2055
2056 if (!buildLeftfixes(tbi, bc, qif, no_retrigger_queues, eager_queues,
2057 false)) {
2058 return false;
2059 }
2060
2061 return true;
2062}
2063
2064static
2065void allocateStateSpace(const engine_info &eng_info, NfaInfo &nfa_info,
2066 RoseStateOffsets *so, u32 *scratchStateSize,
2067 u32 *transientStateSize) {
2068 u32 state_offset;
2069 if (eng_info.transient) {
2070 // Transient engines do not use stream state, but must have room in
2071 // transient state (stored in scratch).
2072 state_offset = *transientStateSize;
2073 *transientStateSize += eng_info.stream_size;
2074 } else {
2075 // Pack NFA stream state on to the end of the Rose stream state.
2076 state_offset = so->end;
2077 so->end += eng_info.stream_size;
2078 }
2079
2080 nfa_info.stateOffset = state_offset;
2081
2082 // Uncompressed state in scratch must be aligned.
2083 *scratchStateSize = ROUNDUP_N(*scratchStateSize, eng_info.scratch_align);
2084 nfa_info.fullStateOffset = *scratchStateSize;
2085 *scratchStateSize += eng_info.scratch_size;
2086}
2087
2088static
2089void updateNfaState(const build_context &bc, vector<NfaInfo> &nfa_infos,
2090 RoseStateOffsets *so, u32 *scratchStateSize,
2091 u32 *transientStateSize) {
2092 if (nfa_infos.empty()) {
2093 return;
2094 }
2095
2096 *transientStateSize = 0;
2097 *scratchStateSize = 0;
2098
2099 for (u32 qi = 0; qi < nfa_infos.size(); qi++) {
2100 NfaInfo &nfa_info = nfa_infos[qi];
2101 const auto &eng_info = bc.engine_info_by_queue.at(qi);
2102 allocateStateSpace(eng_info, nfa_info, so, scratchStateSize,
2103 transientStateSize);
2104 }
2105}
2106
2107/* does not include history requirements for outfixes or literal matchers */
2108u32 RoseBuildImpl::calcHistoryRequired() const {
2109 u32 m = cc.grey.minHistoryAvailable;
2110
2111 for (auto v : vertices_range(g)) {
2112 if (g[v].suffix) {
2113 m = MAX(m, 2); // so that history req is at least 1, for state
2114 // compression.
2115 /* TODO: check if suffix uses state compression */
2116 }
2117
2118 if (g[v].left) {
2119 const u32 lag = g[v].left.lag;
2120 const left_id leftfix(g[v].left);
2121 if (contains(transient, leftfix)) {
2122 u32 mv = lag + findMaxWidth(leftfix);
2123
2124 // If this vertex has an event literal, we need to add one to
2125 // cope with it.
2126 if (hasLiteralInTable(v, ROSE_EVENT)) {
2127 mv++;
2128 }
2129
2130 m = MAX(m, mv);
2131 } else {
2132 /* rose will be caught up from (lag - 1), also need an extra
2133 * byte behind that to find the decompression key */
2134 m = MAX(m, lag + 1);
2135 m = MAX(m, 2); // so that history req is at least 1, for state
2136 // compression.
2137 }
2138 }
2139 }
2140
2141 // Delayed literals contribute to history requirement as well.
2142 for (u32 id = 0; id < literals.size(); id++) {
2143 const auto &lit = literals.at(id);
2144 if (lit.delay) {
2145 // If the literal is delayed _and_ has a mask that is longer than
2146 // the literal, we need enough history to match the whole mask as
2147 // well when rebuilding delayed matches.
2148 size_t len = std::max(lit.elength(), lit.msk.size() + lit.delay);
2149 ENSURE_AT_LEAST(&m, verify_u32(len));
2150 }
2151
2152 /* Benefit checks require data is available. */
2153 if (literal_info.at(id).requires_benefits) {
2154 ENSURE_AT_LEAST(&m,
2155 MIN(verify_u32(lit.elength()), MAX_MASK2_WIDTH));
2156 }
2157 }
2158
2159 m = MAX(m, max_rose_anchored_floating_overlap);
2160
2161 DEBUG_PRINTF("m=%u, ematcher_region_size=%u\n", m, ematcher_region_size);
2162
2163 if (ematcher_region_size >= m) {
2164 return ematcher_region_size;
2165 }
2166
2167 return m ? m - 1 : 0;
2168}
2169
2170static
2171u32 buildLastByteIter(const RoseGraph &g, build_context &bc) {
2172 vector<u32> lb_roles;
2173
2174 for (auto v : vertices_range(g)) {
2175 if (!hasLastByteHistorySucc(g, v)) {
2176 continue;
2177 }
2178 // Eager EOD reporters won't have state indices.
2179 auto it = bc.roleStateIndices.find(v);
2180 if (it != end(bc.roleStateIndices)) {
2181 lb_roles.push_back(it->second);
2182 DEBUG_PRINTF("last byte %u\n", it->second);
2183 }
2184 }
2185
2186 if (lb_roles.empty()) {
2187 return 0; /* invalid offset */
2188 }
2189
2190 auto iter = mmbBuildSparseIterator(lb_roles, bc.roleStateIndices.size());
2191 return bc.engine_blob.add_iterator(iter);
2192}
2193
2194static
2195u32 findMinFloatingLiteralMatch(const RoseBuildImpl &build,
2196 const vector<raw_dfa> &anchored_dfas) {
2197 if (anchored_dfas.size() > 1) {
2198 DEBUG_PRINTF("multiple anchored dfas\n");
2199 /* We must regard matches from other anchored tables as unordered, as
2200 * we do for floating matches. */
2201 return 1;
2202 }
2203
2204 const RoseGraph &g = build.g;
2205 u32 minWidth = ROSE_BOUND_INF;
2206 for (auto v : vertices_range(g)) {
2207 if (build.isAnchored(v) || build.isVirtualVertex(v)) {
2208 DEBUG_PRINTF("skipping %zu anchored or root\n", g[v].index);
2209 continue;
2210 }
2211
2212 u32 w = g[v].min_offset;
2213 DEBUG_PRINTF("%zu m_o = %u\n", g[v].index, w);
2214
2215 if (w < minWidth) {
2216 minWidth = w;
2217 }
2218 }
2219
2220 return minWidth;
2221}
2222
2223static
2224vector<u32> buildSuffixEkeyLists(const RoseBuildImpl &build, build_context &bc,
2225 const QueueIndexFactory &qif) {
2226 vector<u32> out(qif.allocated_count());
2227
2228 map<u32, vector<u32>> qi_to_ekeys; /* for determinism */
2229
2230 for (const auto &e : bc.suffixes) {
2231 const suffix_id &s = e.first;
2232 u32 qi = e.second;
2233 set<u32> ekeys = reportsToEkeys(all_reports(s), build.rm);
2234
2235 if (!ekeys.empty()) {
2236 qi_to_ekeys[qi] = {ekeys.begin(), ekeys.end()};
2237 }
2238 }
2239
2240 /* for each outfix also build elists */
2241 for (const auto &outfix : build.outfixes) {
2242 u32 qi = outfix.get_queue();
2243 set<u32> ekeys = reportsToEkeys(all_reports(outfix), build.rm);
2244
2245 if (!ekeys.empty()) {
2246 qi_to_ekeys[qi] = {ekeys.begin(), ekeys.end()};
2247 }
2248 }
2249
2250 for (auto &e : qi_to_ekeys) {
2251 u32 qi = e.first;
2252 auto &ekeys = e.second;
2253 assert(!ekeys.empty());
2254 ekeys.push_back(INVALID_EKEY); /* terminator */
2255 out[qi] = bc.engine_blob.add_range(ekeys);
2256 }
2257
2258 return out;
2259}
2260
2261/** Returns sparse iter offset in engine blob. */
2262static
2263u32 buildEodNfaIterator(build_context &bc, const u32 activeQueueCount) {
2264 vector<u32> keys;
2265 for (u32 qi = 0; qi < activeQueueCount; ++qi) {
2266 const auto &eng_info = bc.engine_info_by_queue.at(qi);
2267 if (eng_info.accepts_eod) {
2268 DEBUG_PRINTF("nfa qi=%u accepts eod\n", qi);
2269 keys.push_back(qi);
2270 }
2271 }
2272
2273 if (keys.empty()) {
2274 return 0;
2275 }
2276
2277 DEBUG_PRINTF("building iter for %zu nfas\n", keys.size());
2278
2279 auto iter = mmbBuildSparseIterator(keys, activeQueueCount);
2280 return bc.engine_blob.add_iterator(iter);
2281}
2282
2283static
2284bool hasMpvTrigger(const set<u32> &reports, const ReportManager &rm) {
2285 for (u32 r : reports) {
2286 if (rm.getReport(r).type == INTERNAL_ROSE_CHAIN) {
2287 return true;
2288 }
2289 }
2290
2291 return false;
2292}
2293
2294static
2295bool anyEndfixMpvTriggers(const RoseBuildImpl &build) {
2296 const RoseGraph &g = build.g;
2297 unordered_set<suffix_id> done;
2298
2299 /* suffixes */
2300 for (auto v : vertices_range(g)) {
2301 if (!g[v].suffix) {
2302 continue;
2303 }
2304 if (contains(done, g[v].suffix)) {
2305 continue; /* already done */
2306 }
2307 done.insert(g[v].suffix);
2308
2309 if (hasMpvTrigger(all_reports(g[v].suffix), build.rm)) {
2310 return true;
2311 }
2312 }
2313
2314 /* outfixes */
2315 for (const auto &out : build.outfixes) {
2316 if (hasMpvTrigger(all_reports(out), build.rm)) {
2317 return true;
2318 }
2319 }
2320
2321 return false;
2322}
2323
2324struct DerivedBoundaryReports {
2325 explicit DerivedBoundaryReports(const BoundaryReports &boundary) {
2326 insert(&report_at_0_eod_full, boundary.report_at_0_eod);
2327 insert(&report_at_0_eod_full, boundary.report_at_eod);
2328 insert(&report_at_0_eod_full, boundary.report_at_0);
2329 }
2330 set<ReportID> report_at_0_eod_full;
2331};
2332
2333static
2334void addSomRevNfas(build_context &bc, RoseEngine &proto,
2335 const SomSlotManager &ssm) {
2336 const auto &nfas = ssm.getRevNfas();
2337 vector<u32> nfa_offsets;
2338 nfa_offsets.reserve(nfas.size());
2339 for (const auto &nfa : nfas) {
2340 assert(nfa);
2341 u32 offset = bc.engine_blob.add(*nfa, nfa->length);
2342 DEBUG_PRINTF("wrote SOM rev NFA %zu (len %u) to offset %u\n",
2343 nfa_offsets.size(), nfa->length, offset);
2344 nfa_offsets.push_back(offset);
2345 /* note: som rev nfas don't need a queue assigned as only run in block
2346 * mode reverse */
2347 }
2348
2349 proto.somRevCount = verify_u32(nfas.size());
2350 proto.somRevOffsetOffset = bc.engine_blob.add_range(nfa_offsets);
2351}
2352
2353static
2354void recordResources(RoseResources &resources, const RoseBuildImpl &build,
2355 const vector<raw_dfa> &anchored_dfas,
2356 const vector<LitFragment> &fragments) {
2357 if (!build.outfixes.empty()) {
2358 resources.has_outfixes = true;
2359 }
2360
2361 resources.has_literals = !fragments.empty();
2362
2363 const auto &g = build.g;
2364 for (const auto &v : vertices_range(g)) {
2365 if (g[v].eod_accept) {
2366 resources.has_eod = true;
2367 break;
2368 }
2369 if (g[v].suffix && has_eod_accepts(g[v].suffix)) {
2370 resources.has_eod = true;
2371 break;
2372 }
2373 }
2374
2375 resources.has_anchored = !anchored_dfas.empty();
2376 resources.has_anchored_multiple = anchored_dfas.size() > 1;
2377 for (const auto &rdfa : anchored_dfas) {
2378 if (rdfa.states.size() > 256) {
2379 resources.has_anchored_large = true;
2380 }
2381 }
2382
2383}
2384
2385static
2386u32 writeProgram(build_context &bc, RoseProgram &&program) {
2387 if (program.empty()) {
2388 DEBUG_PRINTF("no program\n");
2389 return 0;
2390 }
2391
2392 applyFinalSpecialisation(program);
2393
2394 auto it = bc.program_cache.find(program);
2395 if (it != end(bc.program_cache)) {
2396 DEBUG_PRINTF("reusing cached program at %u\n", it->second);
2397 return it->second;
2398 }
2399
2400 recordResources(bc.resources, program);
2401 recordLongLiterals(bc.longLiterals, program);
2402
2403 auto prog_bytecode = writeProgram(bc.engine_blob, program);
2404 u32 offset = bc.engine_blob.add(prog_bytecode);
2405 DEBUG_PRINTF("prog len %zu written at offset %u\n", prog_bytecode.size(),
2406 offset);
2407 bc.program_cache.emplace(move(program), offset);
2408 return offset;
2409}
2410
2411static
2412u32 writeActiveLeftIter(RoseEngineBlob &engine_blob,
2413 const vector<LeftNfaInfo> &leftInfoTable) {
2414 vector<u32> keys;
2415 for (size_t i = 0; i < leftInfoTable.size(); i++) {
2416 if (!leftInfoTable[i].transient) {
2417 DEBUG_PRINTF("leftfix %zu is active\n", i);
2418 keys.push_back(verify_u32(i));
2419 }
2420 }
2421
2422 DEBUG_PRINTF("%zu active leftfixes\n", keys.size());
2423
2424 if (keys.empty()) {
2425 return 0;
2426 }
2427
2428 auto iter = mmbBuildSparseIterator(keys, verify_u32(leftInfoTable.size()));
2429 return engine_blob.add_iterator(iter);
2430}
2431
2432static
2433bool hasEodAnchors(const RoseBuildImpl &build, const build_context &bc,
2434 u32 outfixEndQueue) {
2435 for (u32 i = 0; i < outfixEndQueue; i++) {
2436 const auto &eng_info = bc.engine_info_by_queue.at(i);
2437 if (eng_info.accepts_eod) {
2438 DEBUG_PRINTF("outfix has eod\n");
2439 return true;
2440 }
2441 }
2442
2443 if (build.eod_event_literal_id != MO_INVALID_IDX) {
2444 DEBUG_PRINTF("eod is an event to be celebrated\n");
2445 return true;
2446 }
2447
2448 const RoseGraph &g = build.g;
2449 for (auto v : vertices_range(g)) {
2450 if (g[v].eod_accept) {
2451 DEBUG_PRINTF("literally report eod\n");
2452 return true;
2453 }
2454 if (g[v].suffix && has_eod_accepts(g[v].suffix)) {
2455 DEBUG_PRINTF("eod suffix\n");
2456 return true;
2457 }
2458 }
2459 DEBUG_PRINTF("yawn\n");
2460 return false;
2461}
2462
2463static
2464void writeDkeyInfo(const ReportManager &rm, RoseEngineBlob &engine_blob,
2465 RoseEngine &proto) {
2466 const auto inv_dkeys = rm.getDkeyToReportTable();
2467 proto.invDkeyOffset = engine_blob.add_range(inv_dkeys);
2468 proto.dkeyCount = rm.numDkeys();
2469 proto.dkeyLogSize = fatbit_size(proto.dkeyCount);
2470}
2471
2472static
2473void writeLeftInfo(RoseEngineBlob &engine_blob, RoseEngine &proto,
2474 const vector<LeftNfaInfo> &leftInfoTable) {
2475 proto.leftOffset = engine_blob.add_range(leftInfoTable);
2476 proto.activeLeftIterOffset
2477 = writeActiveLeftIter(engine_blob, leftInfoTable);
2478 proto.roseCount = verify_u32(leftInfoTable.size());
2479 proto.activeLeftCount = verify_u32(leftInfoTable.size());
2480 proto.rosePrefixCount = countRosePrefixes(leftInfoTable);
2481}
2482
2483static
2484void writeLogicalInfo(const ReportManager &rm, RoseEngineBlob &engine_blob,
2485 RoseEngine &proto) {
2486 const auto &tree = rm.getLogicalTree();
2487 proto.logicalTreeOffset = engine_blob.add_range(tree);
2488 const auto &combMap = rm.getCombInfoMap();
2489 proto.combInfoMapOffset = engine_blob.add_range(combMap);
2490 proto.lkeyCount = rm.numLogicalKeys();
2491 proto.lopCount = rm.numLogicalOps();
2492 proto.ckeyCount = rm.numCkeys();
2493}
2494
2495static
2496void writeNfaInfo(const RoseBuildImpl &build, build_context &bc,
2497 RoseEngine &proto, const set<u32> &no_retrigger_queues) {
2498 const u32 queue_count = build.qif.allocated_count();
2499 if (!queue_count) {
2500 return;
2501 }
2502
2503 auto ekey_lists = buildSuffixEkeyLists(build, bc, build.qif);
2504
2505 vector<NfaInfo> infos(queue_count);
2506 memset(infos.data(), 0, sizeof(NfaInfo) * queue_count);
2507
2508 for (u32 qi = 0; qi < queue_count; qi++) {
2509 NfaInfo &info = infos[qi];
2510 info.nfaOffset = bc.engineOffsets.at(qi);
2511 assert(qi < ekey_lists.size());
2512 info.ekeyListOffset = ekey_lists.at(qi);
2513 info.no_retrigger = contains(no_retrigger_queues, qi) ? 1 : 0;
2514 }
2515
2516 // Mark outfixes that are in the small block matcher.
2517 for (const auto &out : build.outfixes) {
2518 const u32 qi = out.get_queue();
2519 assert(qi < infos.size());
2520 infos.at(qi).in_sbmatcher = out.in_sbmatcher;
2521 }
2522
2523 // Mark suffixes triggered by EOD table literals.
2524 const RoseGraph &g = build.g;
2525 for (auto v : vertices_range(g)) {
2526 if (!g[v].suffix) {
2527 continue;
2528 }
2529 u32 qi = bc.suffixes.at(g[v].suffix);
2530 assert(qi < infos.size());
2531 if (build.isInETable(v)) {
2532 infos.at(qi).eod = 1;
2533 }
2534 }
2535
2536 // Update state offsets to do with NFAs in proto and in the NfaInfo
2537 // structures.
2538 updateNfaState(bc, infos, &proto.stateOffsets, &proto.scratchStateSize,
2539 &proto.tStateSize);
2540
2541 proto.nfaInfoOffset = bc.engine_blob.add_range(infos);
2542}
2543
2544static
2545bool hasBoundaryReports(const BoundaryReports &boundary) {
2546 if (!boundary.report_at_0.empty()) {
2547 DEBUG_PRINTF("has boundary reports at 0\n");
2548 return true;
2549 }
2550 if (!boundary.report_at_0_eod.empty()) {
2551 DEBUG_PRINTF("has boundary reports at 0 eod\n");
2552 return true;
2553 }
2554 if (!boundary.report_at_eod.empty()) {
2555 DEBUG_PRINTF("has boundary reports at eod\n");
2556 return true;
2557 }
2558 DEBUG_PRINTF("no boundary reports\n");
2559 return false;
2560}
2561
2562static
2563void makeBoundaryPrograms(const RoseBuildImpl &build, build_context &bc,
2564 const BoundaryReports &boundary,
2565 const DerivedBoundaryReports &dboundary,
2566 RoseBoundaryReports &out) {
2567 DEBUG_PRINTF("report ^: %zu\n", boundary.report_at_0.size());
2568 DEBUG_PRINTF("report $: %zu\n", boundary.report_at_eod.size());
2569 DEBUG_PRINTF("report ^$: %zu\n", dboundary.report_at_0_eod_full.size());
2570
2571 auto eod_prog = makeBoundaryProgram(build, boundary.report_at_eod);
2572 out.reportEodOffset = writeProgram(bc, move(eod_prog));
2573
2574 auto zero_prog = makeBoundaryProgram(build, boundary.report_at_0);
2575 out.reportZeroOffset = writeProgram(bc, move(zero_prog));
2576
2577 auto zeod_prog = makeBoundaryProgram(build, dboundary.report_at_0_eod_full);
2578 out.reportZeroEodOffset = writeProgram(bc, move(zeod_prog));
2579}
2580
2581static
2582unordered_map<RoseVertex, u32> assignStateIndices(const RoseBuildImpl &build) {
2583 const auto &g = build.g;
2584
2585 u32 state = 0;
2586 unordered_map<RoseVertex, u32> roleStateIndices;
2587 for (auto v : vertices_range(g)) {
2588 // Virtual vertices (starts, EOD accept vertices) never need state
2589 // indices.
2590 if (build.isVirtualVertex(v)) {
2591 continue;
2592 }
2593
2594 // We only need a state index if we have successors that are not
2595 // eagerly-reported EOD vertices.
2596 bool needs_state_index = false;
2597 for (const auto &e : out_edges_range(v, g)) {
2598 if (!canEagerlyReportAtEod(build, e)) {
2599 needs_state_index = true;
2600 break;
2601 }
2602 }
2603
2604 if (!needs_state_index) {
2605 continue;
2606 }
2607
2608 /* TODO: also don't need a state index if all edges are nfa based */
2609 roleStateIndices.emplace(v, state++);
2610 }
2611
2612 DEBUG_PRINTF("assigned %u states (from %zu vertices)\n", state,
2613 num_vertices(g));
2614
2615 return roleStateIndices;
2616}
2617
2618static
2619bool hasUsefulStops(const left_build_info &build) {
2620 for (u32 i = 0; i < N_CHARS; i++) {
2621 if (build.stopAlphabet[i]) {
2622 return true;
2623 }
2624 }
2625 return false;
2626}
2627
2628static
2629void buildLeftInfoTable(const RoseBuildImpl &tbi, build_context &bc,
2630 const set<u32> &eager_queues, u32 leftfixBeginQueue,
2631 u32 leftfixCount, vector<LeftNfaInfo> &leftTable,
2632 u32 *laggedRoseCount, size_t *history) {
2633 const RoseGraph &g = tbi.g;
2634 const CompileContext &cc = tbi.cc;
2635
2636 unordered_set<u32> done_core;
2637
2638 leftTable.resize(leftfixCount);
2639
2640 u32 lagIndex = 0;
2641
2642 for (RoseVertex v : vertices_range(g)) {
2643 if (!g[v].left) {
2644 continue;
2645 }
2646 assert(contains(bc.leftfix_info, v));
2647 const left_build_info &lbi = bc.leftfix_info.at(v);
2648 if (lbi.has_lookaround) {
2649 continue;
2650 }
2651
2652 assert(lbi.queue >= leftfixBeginQueue);
2653 u32 left_index = lbi.queue - leftfixBeginQueue;
2654 assert(left_index < leftfixCount);
2655
2656 /* seedy hack to make miracles more effective.
2657 *
2658 * TODO: make miracle seeking not depend on history length and have
2659 * runt scans */
2660 if (hasUsefulStops(lbi)) {
2661 ENSURE_AT_LEAST(history,
2662 (size_t)MIN(cc.grey.maxHistoryAvailable,
2663 g[v].left.lag + 1
2664 + cc.grey.miracleHistoryBonus));
2665 }
2666
2667 LeftNfaInfo &left = leftTable[left_index];
2668 if (!contains(done_core, left_index)) {
2669 done_core.insert(left_index);
2670 memset(&left, 0, sizeof(left));
2671 left.squash_mask = ~0ULL;
2672
2673 DEBUG_PRINTF("populating info for %u\n", left_index);
2674
2675 left.maxQueueLen = lbi.max_queuelen;
2676
2677 if (hasUsefulStops(lbi)) {
2678 assert(lbi.stopAlphabet.size() == N_CHARS);
2679 left.stopTable = bc.engine_blob.add_range(lbi.stopAlphabet);
2680 }
2681
2682 assert(lbi.countingMiracleOffset || !lbi.countingMiracleCount);
2683 left.countingMiracleOffset = lbi.countingMiracleOffset;
2684
2685 DEBUG_PRINTF("mw = %u\n", lbi.transient);
2686 left.transient = verify_u8(lbi.transient);
2687 left.infix = tbi.isNonRootSuccessor(v);
2688 left.eager = contains(eager_queues, lbi.queue);
2689
2690 // A rose has a lagIndex if it's non-transient and we are
2691 // streaming.
2692 if (!lbi.transient && cc.streaming) {
2693 assert(lagIndex < ROSE_OFFSET_INVALID);
2694 left.lagIndex = lagIndex++;
2695 } else {
2696 left.lagIndex = ROSE_OFFSET_INVALID;
2697 }
2698 }
2699
2700 DEBUG_PRINTF("rose %u is %s\n", left_index,
2701 left.infix ? "infix" : "prefix");
2702
2703 // Update squash mask.
2704 left.squash_mask &= lbi.squash_mask;
2705
2706 // Update the max delay.
2707 ENSURE_AT_LEAST(&left.maxLag, lbi.lag);
2708
2709 if (contains(g[v].literals, tbi.eod_event_literal_id)) {
2710 left.eod_check = 1;
2711 }
2712 }
2713
2714 DEBUG_PRINTF("built %u roses with lag indices\n", lagIndex);
2715 *laggedRoseCount = lagIndex;
2716}
2717
2718static
2719RoseProgram makeLiteralProgram(const RoseBuildImpl &build, build_context &bc,
2720 ProgramBuild &prog_build, u32 lit_id,
2721 const vector<vector<RoseEdge>> &lit_edge_map,
2722 bool is_anchored_replay_program) {
2723 DEBUG_PRINTF("lit_id=%u\n", lit_id);
2724 assert(lit_id < lit_edge_map.size());
2725
2726 return makeLiteralProgram(build, bc.leftfix_info, bc.suffixes,
2727 bc.engine_info_by_queue, bc.roleStateIndices,
2728 prog_build, lit_id, lit_edge_map.at(lit_id),
2729 is_anchored_replay_program);
2730}
2731
2732static
2733RoseProgram makeFragmentProgram(const RoseBuildImpl &build, build_context &bc,
2734 ProgramBuild &prog_build,
2735 const vector<u32> &lit_ids,
2736 const vector<vector<RoseEdge>> &lit_edge_map) {
2737 assert(!lit_ids.empty());
2738
2739 vector<RoseProgram> blocks;
2740 for (const auto &lit_id : lit_ids) {
2741 auto prog = makeLiteralProgram(build, bc, prog_build, lit_id,
2742 lit_edge_map, false);
2743 blocks.push_back(move(prog));
2744 }
2745
2746 return assembleProgramBlocks(move(blocks));
2747}
2748
2749/**
2750 * \brief Returns a map from literal ID to a list of edges leading into
2751 * vertices with that literal ID.
2752 */
2753static
2754vector<vector<RoseEdge>> findEdgesByLiteral(const RoseBuildImpl &build) {
2755 vector<vector<RoseEdge>> lit_edge_map(build.literals.size());
2756
2757 const auto &g = build.g;
2758 for (const auto &v : vertices_range(g)) {
2759 for (const auto &lit_id : g[v].literals) {
2760 assert(lit_id < lit_edge_map.size());
2761 auto &edge_list = lit_edge_map.at(lit_id);
2762 insert(&edge_list, edge_list.end(), in_edges(v, g));
2763 }
2764 }
2765
2766 // Sort edges in each edge list by (source, target) indices. This gives us
2767 // less surprising ordering in program generation for a literal with many
2768 // edges.
2769 for (auto &edge_list : lit_edge_map) {
2770 sort(begin(edge_list), end(edge_list), [&g](const RoseEdge &a,
2771 const RoseEdge &b) {
2772 return tie(g[source(a, g)].index, g[target(a, g)].index) <
2773 tie(g[source(b, g)].index, g[target(b, g)].index);
2774 });
2775 }
2776
2777 return lit_edge_map;
2778}
2779
2780static
2781bool isUsedLiteral(const RoseBuildImpl &build, u32 lit_id) {
2782 assert(lit_id < build.literal_info.size());
2783 const auto &info = build.literal_info[lit_id];
2784 if (!info.vertices.empty()) {
2785 return true;
2786 }
2787
2788 for (const u32 &delayed_id : info.delayed_ids) {
2789 assert(delayed_id < build.literal_info.size());
2790 const rose_literal_info &delayed_info = build.literal_info[delayed_id];
2791 if (!delayed_info.vertices.empty()) {
2792 return true;
2793 }
2794 }
2795
2796 DEBUG_PRINTF("literal %u has no refs\n", lit_id);
2797 return false;
2798}
2799
2800static
2801rose_literal_id getFragment(rose_literal_id lit) {
2802 if (lit.s.length() > ROSE_SHORT_LITERAL_LEN_MAX) {
2803 // Trim to last ROSE_SHORT_LITERAL_LEN_MAX bytes.
2804 lit.s.erase(0, lit.s.length() - ROSE_SHORT_LITERAL_LEN_MAX);
2805 }
2806 DEBUG_PRINTF("fragment: %s\n", dumpString(lit.s).c_str());
2807 return lit;
2808}
2809
2810static
2811vector<LitFragment> groupByFragment(const RoseBuildImpl &build) {
2812 vector<LitFragment> fragments;
2813 u32 frag_id = 0;
2814
2815 struct FragmentInfo {
2816 vector<u32> lit_ids;
2817 rose_group groups = 0;
2818 };
2819
2820 map<rose_literal_id, FragmentInfo> frag_info;
2821
2822 for (u32 lit_id = 0; lit_id < build.literals.size(); lit_id++) {
2823 const auto &lit = build.literals.at(lit_id);
2824 const auto &info = build.literal_info.at(lit_id);
2825
2826 if (!isUsedLiteral(build, lit_id)) {
2827 DEBUG_PRINTF("lit %u is unused\n", lit_id);
2828 continue;
2829 }
2830
2831 if (lit.table == ROSE_EVENT) {
2832 DEBUG_PRINTF("lit %u is an event\n", lit_id);
2833 continue;
2834 }
2835
2836 auto groups = info.group_mask;
2837
2838 if (lit.s.length() < ROSE_SHORT_LITERAL_LEN_MAX) {
2839 fragments.emplace_back(frag_id, lit.s, groups, lit_id);
2840 frag_id++;
2841 continue;
2842 }
2843
2844 DEBUG_PRINTF("fragment candidate: lit_id=%u %s\n", lit_id,
2845 dumpString(lit.s).c_str());
2846
2847 /** 0:/xxabcdefgh/ */
2848 /** 1:/yyabcdefgh/ */
2849 /** 2:/yyabcdefgh.+/ */
2850 // Above 3 patterns should firstly convert into RoseLiteralMap with
2851 // 2 elements ("xxabcdefgh" and "yyabcdefgh"), then convert into
2852 // LitFragment with 1 element ("abcdefgh"). Special care should be
2853 // taken to handle the 'pure' flag during the conversion.
2854
2855 rose_literal_id lit_frag = getFragment(lit);
2856 auto it = frag_info.find(lit_frag);
2857 if (it != frag_info.end()) {
2858 if (!lit_frag.s.get_pure() && it->first.s.get_pure()) {
2859 struct FragmentInfo f_info = it->second;
2860 f_info.lit_ids.push_back(lit_id);
2861 f_info.groups |= groups;
2862 frag_info.erase(it->first);
2863 frag_info.emplace(lit_frag, f_info);
2864 } else {
2865 it->second.lit_ids.push_back(lit_id);
2866 it->second.groups |= groups;
2867 }
2868 } else {
2869 struct FragmentInfo f_info;
2870 f_info.lit_ids.push_back(lit_id);
2871 f_info.groups |= groups;
2872 frag_info.emplace(lit_frag, f_info);
2873 }
2874 }
2875
2876 for (auto &m : frag_info) {
2877 auto &lit = m.first;
2878 auto &fi = m.second;
2879 DEBUG_PRINTF("frag %s -> ids: %s\n", dumpString(m.first.s).c_str(),
2880 as_string_list(fi.lit_ids).c_str());
2881 fragments.emplace_back(frag_id, lit.s, fi.groups, move(fi.lit_ids));
2882 frag_id++;
2883 assert(frag_id == fragments.size());
2884 }
2885
2886 return fragments;
2887}
2888
2889static
2890void buildIncludedIdMap(unordered_map<u32, pair<u32, u8>> &includedIdMap,
2891 const LitProto *litProto) {
2892 if (!litProto) {
2893 return;
2894 }
2895 const auto &proto = *litProto->hwlmProto;
2896 for (const auto &lit : proto.lits) {
2897 if (contains(includedIdMap, lit.id)) {
2898 const auto &included_id = includedIdMap[lit.id].first;
2899 const auto &squash = includedIdMap[lit.id].second;
2900 // The squash behavior should be the same for the same literal
2901 // in different literal matchers.
2902 if (lit.included_id != included_id ||
2903 lit.squash != squash) {
2904 includedIdMap[lit.id] = make_pair(INVALID_LIT_ID, 0);
2905 DEBUG_PRINTF("find different included info for the"
2906 " same literal\n");
2907 }
2908 } else if (lit.included_id != INVALID_LIT_ID) {
2909 includedIdMap[lit.id] = make_pair(lit.included_id, lit.squash);
2910 } else {
2911 includedIdMap[lit.id] = make_pair(INVALID_LIT_ID, 0);
2912 }
2913 }
2914}
2915
2916static
2917void findInclusionGroups(vector<LitFragment> &fragments,
2918 LitProto *fproto, LitProto *drproto,
2919 LitProto *eproto, LitProto *sbproto) {
2920 unordered_map<u32, pair<u32, u8>> includedIdMap;
2921 unordered_map<u32, pair<u32, u8>> includedDelayIdMap;
2922 buildIncludedIdMap(includedIdMap, fproto);
2923 buildIncludedIdMap(includedDelayIdMap, drproto);
2924 buildIncludedIdMap(includedIdMap, eproto);
2925 buildIncludedIdMap(includedIdMap, sbproto);
2926
2927 size_t fragNum = fragments.size();
2928 vector<u32> candidates;
2929 for (size_t j = 0; j < fragNum; j++) {
2930 DEBUG_PRINTF("frag id %lu\n", j);
2931 u32 id = j;
2932 if (contains(includedIdMap, id) ||
2933 contains(includedDelayIdMap, id)) {
2934 candidates.push_back(j);
2935 DEBUG_PRINTF("find candidate\n");
2936 }
2937 }
2938
2939 for (const auto &c : candidates) {
2940 auto &frag = fragments[c];
2941 u32 id = c;
2942 if (contains(includedIdMap, id) &&
2943 includedIdMap[id].first != INVALID_LIT_ID) {
2944 const auto &childId = includedIdMap[id];
2945 frag.included_frag_id = childId.first;
2946 frag.squash = childId.second;
2947 DEBUG_PRINTF("frag id %u child frag id %u\n", c,
2948 frag.included_frag_id);
2949 }
2950
2951 if (contains(includedDelayIdMap, id) &&
2952 includedDelayIdMap[id].first != INVALID_LIT_ID) {
2953 const auto &childId = includedDelayIdMap[id];
2954 frag.included_delay_frag_id = childId.first;
2955 frag.delay_squash = childId.second;
2956
2957 DEBUG_PRINTF("delay frag id %u child frag id %u\n", c,
2958 frag.included_delay_frag_id);
2959 }
2960 }
2961}
2962
2963static
2964void buildFragmentPrograms(const RoseBuildImpl &build,
2965 vector<LitFragment> &fragments,
2966 build_context &bc, ProgramBuild &prog_build,
2967 const vector<vector<RoseEdge>> &lit_edge_map) {
2968 // Sort fragments based on literal length and case info to build
2969 // included literal programs before their parent programs.
2970 vector<LitFragment> ordered_fragments(fragments);
2971 stable_sort(begin(ordered_fragments), end(ordered_fragments),
2972 [](const LitFragment &a, const LitFragment &b) {
2973 auto len1 = a.s.length();
2974 auto caseful1 = !a.s.any_nocase();
2975 auto len2 = b.s.length();
2976 auto caseful2 = !b.s.any_nocase();
2977 return tie(len1, caseful1) < tie(len2, caseful2);
2978 });
2979
2980 for (auto &frag : ordered_fragments) {
2981 auto &pfrag = fragments[frag.fragment_id];
2982 DEBUG_PRINTF("frag_id=%u, lit_ids=[%s]\n", pfrag.fragment_id,
2983 as_string_list(pfrag.lit_ids).c_str());
2984
2985 auto lit_prog = makeFragmentProgram(build, bc, prog_build,
2986 pfrag.lit_ids, lit_edge_map);
2987 if (pfrag.included_frag_id != INVALID_FRAG_ID &&
2988 !lit_prog.empty()) {
2989 auto &cfrag = fragments[pfrag.included_frag_id];
2990 assert(pfrag.s.length() >= cfrag.s.length() &&
2991 !pfrag.s.any_nocase() >= !cfrag.s.any_nocase());
2992 u32 child_offset = cfrag.lit_program_offset;
2993 DEBUG_PRINTF("child %u offset %u\n", cfrag.fragment_id,
2994 child_offset);
2995 addIncludedJumpProgram(lit_prog, child_offset, pfrag.squash);
2996 }
2997 pfrag.lit_program_offset = writeProgram(bc, move(lit_prog));
2998
2999 // We only do delayed rebuild in streaming mode.
3000 if (!build.cc.streaming) {
3001 continue;
3002 }
3003
3004 auto rebuild_prog = makeDelayRebuildProgram(build, prog_build,
3005 pfrag.lit_ids);
3006 if (pfrag.included_delay_frag_id != INVALID_FRAG_ID &&
3007 !rebuild_prog.empty()) {
3008 auto &cfrag = fragments[pfrag.included_delay_frag_id];
3009 assert(pfrag.s.length() >= cfrag.s.length() &&
3010 !pfrag.s.any_nocase() >= !cfrag.s.any_nocase());
3011 u32 child_offset = cfrag.delay_program_offset;
3012 DEBUG_PRINTF("child %u offset %u\n", cfrag.fragment_id,
3013 child_offset);
3014 addIncludedJumpProgram(rebuild_prog, child_offset,
3015 pfrag.delay_squash);
3016 }
3017 pfrag.delay_program_offset = writeProgram(bc, move(rebuild_prog));
3018 }
3019}
3020
3021static
3022void updateLitProtoProgramOffset(vector<LitFragment> &fragments,
3023 LitProto &litProto, bool delay) {
3024 auto &proto = *litProto.hwlmProto;
3025 for (auto &lit : proto.lits) {
3026 auto fragId = lit.id;
3027 auto &frag = fragments[fragId];
3028 if (delay) {
3029 DEBUG_PRINTF("delay_program_offset:%u\n",
3030 frag.delay_program_offset);
3031 lit.id = frag.delay_program_offset;
3032 } else {
3033 DEBUG_PRINTF("lit_program_offset:%u\n",
3034 frag.lit_program_offset);
3035 lit.id = frag.lit_program_offset;
3036 }
3037 }
3038}
3039
3040static
3041void updateLitProgramOffset(vector<LitFragment> &fragments,
3042 LitProto *fproto, LitProto *drproto,
3043 LitProto *eproto, LitProto *sbproto) {
3044 if (fproto) {
3045 updateLitProtoProgramOffset(fragments, *fproto, false);
3046 }
3047
3048 if (drproto) {
3049 updateLitProtoProgramOffset(fragments, *drproto, true);
3050 }
3051
3052 if (eproto) {
3053 updateLitProtoProgramOffset(fragments, *eproto, false);
3054 }
3055
3056 if (sbproto) {
3057 updateLitProtoProgramOffset(fragments, *sbproto, false);
3058 }
3059}
3060
3061/**
3062 * \brief Build the interpreter programs for each literal.
3063 */
3064static
3065void buildLiteralPrograms(const RoseBuildImpl &build,
3066 vector<LitFragment> &fragments, build_context &bc,
3067 ProgramBuild &prog_build, LitProto *fproto,
3068 LitProto *drproto, LitProto *eproto,
3069 LitProto *sbproto) {
3070 DEBUG_PRINTF("%zu fragments\n", fragments.size());
3071 auto lit_edge_map = findEdgesByLiteral(build);
3072
3073 findInclusionGroups(fragments, fproto, drproto, eproto, sbproto);
3074
3075 buildFragmentPrograms(build, fragments, bc, prog_build, lit_edge_map);
3076
3077 // update literal program offsets for literal matcher prototypes
3078 updateLitProgramOffset(fragments, fproto, drproto, eproto, sbproto);
3079}
3080
3081/**
3082 * \brief Write delay replay programs to the bytecode.
3083 *
3084 * Returns the offset of the beginning of the program array, and the number of
3085 * programs.
3086 */
3087static
3088pair<u32, u32> writeDelayPrograms(const RoseBuildImpl &build,
3089 const vector<LitFragment> &fragments,
3090 build_context &bc,
3091 ProgramBuild &prog_build) {
3092 auto lit_edge_map = findEdgesByLiteral(build);
3093
3094 vector<u32> programs; // program offsets indexed by (delayed) lit id
3095 unordered_map<u32, u32> cache; // program offsets we have already seen
3096
3097 for (const auto &frag : fragments) {
3098 for (const u32 lit_id : frag.lit_ids) {
3099 const auto &info = build.literal_info.at(lit_id);
3100
3101 for (const auto &delayed_lit_id : info.delayed_ids) {
3102 DEBUG_PRINTF("lit id %u delay id %u\n", lit_id, delayed_lit_id);
3103 auto prog = makeLiteralProgram(build, bc, prog_build,
3104 delayed_lit_id, lit_edge_map,
3105 false);
3106 u32 offset = writeProgram(bc, move(prog));
3107
3108 u32 delay_id;
3109 auto it = cache.find(offset);
3110 if (it != end(cache)) {
3111 delay_id = it->second;
3112 DEBUG_PRINTF("reusing delay_id %u for offset %u\n",
3113 delay_id, offset);
3114 } else {
3115 delay_id = verify_u32(programs.size());
3116 programs.push_back(offset);
3117 cache.emplace(offset, delay_id);
3118 DEBUG_PRINTF("assigned new delay_id %u for offset %u\n",
3119 delay_id, offset);
3120 }
3121 prog_build.delay_programs.emplace(delayed_lit_id, delay_id);
3122 }
3123 }
3124 }
3125
3126 DEBUG_PRINTF("%zu delay programs\n", programs.size());
3127 return {bc.engine_blob.add_range(programs), verify_u32(programs.size())};
3128}
3129
3130/**
3131 * \brief Write anchored replay programs to the bytecode.
3132 *
3133 * Returns the offset of the beginning of the program array, and the number of
3134 * programs.
3135 */
3136static
3137pair<u32, u32> writeAnchoredPrograms(const RoseBuildImpl &build,
3138 const vector<LitFragment> &fragments,
3139 build_context &bc,
3140 ProgramBuild &prog_build) {
3141 auto lit_edge_map = findEdgesByLiteral(build);
3142
3143 vector<u32> programs; // program offsets indexed by anchored id
3144 unordered_map<u32, u32> cache; // program offsets we have already seen
3145
3146 for (const auto &frag : fragments) {
3147 for (const u32 lit_id : frag.lit_ids) {
3148 const auto &lit = build.literals.at(lit_id);
3149
3150 if (lit.table != ROSE_ANCHORED) {
3151 continue;
3152 }
3153
3154 // If this anchored literal can never match past
3155 // floatingMinLiteralMatchOffset, we will never have to record it.
3156 if (findMaxOffset(build, lit_id)
3157 <= prog_build.floatingMinLiteralMatchOffset) {
3158 DEBUG_PRINTF("can never match after "
3159 "floatingMinLiteralMatchOffset=%u\n",
3160 prog_build.floatingMinLiteralMatchOffset);
3161 continue;
3162 }
3163
3164 auto prog = makeLiteralProgram(build, bc, prog_build, lit_id,
3165 lit_edge_map, true);
3166 u32 offset = writeProgram(bc, move(prog));
3167 DEBUG_PRINTF("lit_id=%u -> anch prog at %u\n", lit_id, offset);
3168
3169 u32 anch_id;
3170 auto it = cache.find(offset);
3171 if (it != end(cache)) {
3172 anch_id = it->second;
3173 DEBUG_PRINTF("reusing anch_id %u for offset %u\n", anch_id,
3174 offset);
3175 } else {
3176 anch_id = verify_u32(programs.size());
3177 programs.push_back(offset);
3178 cache.emplace(offset, anch_id);
3179 DEBUG_PRINTF("assigned new anch_id %u for offset %u\n", anch_id,
3180 offset);
3181 }
3182 prog_build.anchored_programs.emplace(lit_id, anch_id);
3183 }
3184 }
3185
3186 DEBUG_PRINTF("%zu anchored programs\n", programs.size());
3187 return {bc.engine_blob.add_range(programs), verify_u32(programs.size())};
3188}
3189
3190/**
3191 * \brief Returns all reports used by output-exposed engines, for which we need
3192 * to generate programs.
3193 */
3194static
3195set<ReportID> findEngineReports(const RoseBuildImpl &build) {
3196 set<ReportID> reports;
3197
3198 // The small write engine uses these engine report programs.
3199 insert(&reports, build.smwr.all_reports());
3200
3201 for (const auto &outfix : build.outfixes) {
3202 insert(&reports, all_reports(outfix));
3203 }
3204
3205 const auto &g = build.g;
3206 for (auto v : vertices_range(g)) {
3207 if (g[v].suffix) {
3208 insert(&reports, all_reports(g[v].suffix));
3209 }
3210 }
3211
3212 DEBUG_PRINTF("%zu engine reports (of %zu)\n", reports.size(),
3213 build.rm.numReports());
3214 return reports;
3215}
3216
3217static
3218pair<u32, u32> buildReportPrograms(const RoseBuildImpl &build,
3219 build_context &bc) {
3220 const auto reports = findEngineReports(build);
3221 vector<u32> programs;
3222 programs.reserve(reports.size());
3223
3224 for (ReportID id : reports) {
3225 auto program = makeReportProgram(build, bc.needs_mpv_catchup, id);
3226 u32 offset = writeProgram(bc, move(program));
3227 programs.push_back(offset);
3228 build.rm.setProgramOffset(id, offset);
3229 DEBUG_PRINTF("program for report %u @ %u (%zu instructions)\n", id,
3230 programs.back(), program.size());
3231 }
3232
3233 u32 offset = bc.engine_blob.add_range(programs);
3234 u32 count = verify_u32(programs.size());
3235 return {offset, count};
3236}
3237
3238static
3239bool hasEodAnchoredSuffix(const RoseBuildImpl &build) {
3240 const RoseGraph &g = build.g;
3241 for (auto v : vertices_range(g)) {
3242 if (g[v].suffix && build.isInETable(v)) {
3243 DEBUG_PRINTF("vertex %zu is in eod table and has a suffix\n",
3244 g[v].index);
3245 return true;
3246 }
3247 }
3248 return false;
3249}
3250
3251static
3252bool hasEodMatcher(const RoseBuildImpl &build) {
3253 const RoseGraph &g = build.g;
3254 for (auto v : vertices_range(g)) {
3255 if (build.isInETable(v)) {
3256 DEBUG_PRINTF("vertex %zu is in eod table\n", g[v].index);
3257 return true;
3258 }
3259 }
3260 return false;
3261}
3262
3263static
3264void addEodAnchorProgram(const RoseBuildImpl &build, const build_context &bc,
3265 ProgramBuild &prog_build, bool in_etable,
3266 RoseProgram &program) {
3267 const RoseGraph &g = build.g;
3268
3269 // Predecessor state id -> program block.
3270 map<u32, RoseProgram> pred_blocks;
3271
3272 for (auto v : vertices_range(g)) {
3273 if (!g[v].eod_accept) {
3274 continue;
3275 }
3276
3277 DEBUG_PRINTF("vertex %zu (with %zu preds) fires on EOD\n", g[v].index,
3278 in_degree(v, g));
3279
3280 vector<RoseEdge> edge_list;
3281 for (const auto &e : in_edges_range(v, g)) {
3282 RoseVertex u = source(e, g);
3283 if (build.isInETable(u) != in_etable) {
3284 DEBUG_PRINTF("pred %zu %s in etable\n", g[u].index,
3285 in_etable ? "is not" : "is");
3286 continue;
3287 }
3288 if (canEagerlyReportAtEod(build, e)) {
3289 DEBUG_PRINTF("already done report for vertex %zu\n",
3290 g[u].index);
3291 continue;
3292 }
3293 edge_list.push_back(e);
3294 }
3295
3296 const bool multiple_preds = edge_list.size() > 1;
3297 for (const auto &e : edge_list) {
3298 RoseVertex u = source(e, g);
3299 assert(contains(bc.roleStateIndices, u));
3300 u32 pred_state = bc.roleStateIndices.at(u);
3301 pred_blocks[pred_state].add_block(
3302 makeEodAnchorProgram(build, prog_build, e, multiple_preds));
3303 }
3304 }
3305
3306 addPredBlocks(pred_blocks, bc.roleStateIndices.size(), program);
3307}
3308
3309static
3310void addEodEventProgram(const RoseBuildImpl &build, build_context &bc,
3311 ProgramBuild &prog_build, RoseProgram &program) {
3312 if (build.eod_event_literal_id == MO_INVALID_IDX) {
3313 return;
3314 }
3315
3316 const RoseGraph &g = build.g;
3317 const auto &lit_info = build.literal_info.at(build.eod_event_literal_id);
3318 assert(lit_info.delayed_ids.empty());
3319 assert(!lit_info.squash_group);
3320 assert(!lit_info.requires_benefits);
3321
3322 // Collect all edges leading into EOD event literal vertices.
3323 vector<RoseEdge> edge_list;
3324 for (const auto &v : lit_info.vertices) {
3325 for (const auto &e : in_edges_range(v, g)) {
3326 edge_list.push_back(e);
3327 }
3328 }
3329
3330 // Sort edge list for determinism, prettiness.
3331 sort(begin(edge_list), end(edge_list),
3332 [&g](const RoseEdge &a, const RoseEdge &b) {
3333 return tie(g[source(a, g)].index, g[target(a, g)].index) <
3334 tie(g[source(b, g)].index, g[target(b, g)].index);
3335 });
3336
3337 auto block = makeLiteralProgram(build, bc.leftfix_info, bc.suffixes,
3338 bc.engine_info_by_queue,
3339 bc.roleStateIndices, prog_build,
3340 build.eod_event_literal_id, edge_list,
3341 false);
3342 program.add_block(move(block));
3343}
3344
3345static
3346RoseProgram makeEodProgram(const RoseBuildImpl &build, build_context &bc,
3347 ProgramBuild &prog_build, u32 eodNfaIterOffset) {
3348 RoseProgram program;
3349
3350 addEodEventProgram(build, bc, prog_build, program);
3351 addEnginesEodProgram(eodNfaIterOffset, program);
3352 addEodAnchorProgram(build, bc, prog_build, false, program);
3353 if (hasEodMatcher(build)) {
3354 addMatcherEodProgram(program);
3355 }
3356 addEodAnchorProgram(build, bc, prog_build, true, program);
3357 if (hasEodAnchoredSuffix(build)) {
3358 addSuffixesEodProgram(program);
3359 }
3360
3361 return program;
3362}
3363
3364static
3365RoseProgram makeFlushCombProgram(const RoseEngine &t) {
3366 RoseProgram program;
3367 if (t.ckeyCount) {
3368 addFlushCombinationProgram(program);
3369 }
3370 return program;
3371}
3372
3373static
3374u32 history_required(const rose_literal_id &key) {
3375 if (key.msk.size() < key.s.length()) {
3376 return key.elength() - 1;
3377 } else {
3378 return key.msk.size() + key.delay - 1;
3379 }
3380}
3381
3382static
3383void fillMatcherDistances(const RoseBuildImpl &build, RoseEngine *engine) {
3384 const RoseGraph &g = build.g;
3385
3386 engine->floatingDistance = 0;
3387 engine->floatingMinDistance = ROSE_BOUND_INF;
3388 engine->anchoredDistance = 0;
3389 engine->maxFloatingDelayedMatch = 0;
3390 u32 delayRebuildLength = 0;
3391 engine->smallBlockDistance = 0;
3392
3393 for (auto v : vertices_range(g)) {
3394 if (g[v].literals.empty()) {
3395 continue;
3396 }
3397
3398 assert(g[v].min_offset < ROSE_BOUND_INF); // cannot == ROSE_BOUND_INF
3399 assert(g[v].min_offset <= g[v].max_offset);
3400
3401 for (u32 lit_id : g[v].literals) {
3402 const rose_literal_id &key = build.literals.at(lit_id);
3403 u32 max_d = g[v].max_offset;
3404 u32 min_d = g[v].min_offset;
3405
3406 DEBUG_PRINTF("checking %u: elen %zu min/max %u/%u\n", lit_id,
3407 key.elength_including_mask(), min_d, max_d);
3408
3409 if (build.literal_info[lit_id].undelayed_id != lit_id) {
3410 /* this is a delayed match; need to update delay properties */
3411 /* TODO: can delayed literals ever be in another table ? */
3412 if (key.table == ROSE_FLOATING) {
3413 ENSURE_AT_LEAST(&engine->maxFloatingDelayedMatch, max_d);
3414 ENSURE_AT_LEAST(&delayRebuildLength, history_required(key));
3415 }
3416 }
3417
3418 /* for the FloatingDistances we need the true max depth of the
3419 string */
3420 if (max_d != ROSE_BOUND_INF && key.table != ROSE_ANCHORED) {
3421 assert(max_d >= key.delay);
3422 max_d -= key.delay;
3423 }
3424
3425 switch (key.table) {
3426 case ROSE_FLOATING:
3427 ENSURE_AT_LEAST(&engine->floatingDistance, max_d);
3428 if (min_d >= key.elength_including_mask()) {
3429 LIMIT_TO_AT_MOST(&engine->floatingMinDistance,
3430 min_d - (u32)key.elength_including_mask());
3431 } else {
3432 /* overlapped literals from rose + anchored table can
3433 * cause us to underflow due to sloppiness in
3434 * estimates */
3435 engine->floatingMinDistance = 0;
3436 }
3437 break;
3438 case ROSE_ANCHORED_SMALL_BLOCK:
3439 ENSURE_AT_LEAST(&engine->smallBlockDistance, max_d);
3440 break;
3441 case ROSE_ANCHORED:
3442 ENSURE_AT_LEAST(&engine->anchoredDistance, max_d);
3443 break;
3444 case ROSE_EOD_ANCHORED:
3445 // EOD anchored literals are in another table, so they
3446 // don't contribute to these calculations.
3447 break;
3448 case ROSE_EVENT:
3449 break; // Not a real literal.
3450 }
3451 }
3452 }
3453
3454 // Floating literals go in the small block table too.
3455 ENSURE_AT_LEAST(&engine->smallBlockDistance, engine->floatingDistance);
3456
3457 // Clipped by its very nature.
3458 LIMIT_TO_AT_MOST(&engine->smallBlockDistance, 32U);
3459
3460 engine->delayRebuildLength = delayRebuildLength;
3461
3462 DEBUG_PRINTF("anchoredDistance = %u\n", engine->anchoredDistance);
3463 DEBUG_PRINTF("floatingDistance = %u\n", engine->floatingDistance);
3464 DEBUG_PRINTF("smallBlockDistance = %u\n", engine->smallBlockDistance);
3465 assert(engine->anchoredDistance <= build.cc.grey.maxAnchoredRegion);
3466
3467 /* anchored->floating squash literals may lower floating min distance */
3468 /* TODO: find actual value */
3469 if (!engine->anchoredDistance) {
3470 return;
3471 }
3472}
3473
3474static
3475u32 writeEagerQueueIter(const set<u32> &eager, u32 leftfixBeginQueue,
3476 u32 queue_count, RoseEngineBlob &engine_blob) {
3477 if (eager.empty()) {
3478 return 0;
3479 }
3480
3481 vector<u32> vec;
3482 for (u32 q : eager) {
3483 assert(q >= leftfixBeginQueue);
3484 vec.push_back(q - leftfixBeginQueue);
3485 }
3486
3487 auto iter = mmbBuildSparseIterator(vec, queue_count - leftfixBeginQueue);
3488 return engine_blob.add_iterator(iter);
3489}
3490
3491static
3492bytecode_ptr<RoseEngine> addSmallWriteEngine(const RoseBuildImpl &build,
3493 const RoseResources &res,
3494 bytecode_ptr<RoseEngine> rose) {
3495 assert(rose);
3496
3497 if (roseIsPureLiteral(rose.get())) {
3498 DEBUG_PRINTF("pure literal case, not adding smwr\n");
3499 return rose;
3500 }
3501
3502 u32 qual = roseQuality(res, rose.get());
3503 auto smwr_engine = build.smwr.build(qual);
3504 if (!smwr_engine) {
3505 DEBUG_PRINTF("no smwr built\n");
3506 return rose;
3507 }
3508
3509 const size_t mainSize = rose.size();
3510 const size_t smallWriteSize = smwr_engine.size();
3511 DEBUG_PRINTF("adding smwr engine, size=%zu\n", smallWriteSize);
3512
3513 const size_t smwrOffset = ROUNDUP_CL(mainSize);
3514 const size_t newSize = smwrOffset + smallWriteSize;
3515
3516 auto rose2 = make_zeroed_bytecode_ptr<RoseEngine>(newSize, 64);
3517 char *ptr = (char *)rose2.get();
3518 memcpy(ptr, rose.get(), mainSize);
3519 memcpy(ptr + smwrOffset, smwr_engine.get(), smallWriteSize);
3520
3521 rose2->smallWriteOffset = verify_u32(smwrOffset);
3522 rose2->size = verify_u32(newSize);
3523
3524 return rose2;
3525}
3526
3527/**
3528 * \brief Returns the pair (number of literals, max length) for all real
3529 * literals in the floating table that are in-use.
3530 */
3531static
3532pair<size_t, size_t> floatingCountAndMaxLen(const RoseBuildImpl &build) {
3533 size_t num = 0;
3534 size_t max_len = 0;
3535
3536 for (u32 id = 0; id < build.literals.size(); id++) {
3537 const rose_literal_id &lit = build.literals.at(id);
3538
3539 if (lit.table != ROSE_FLOATING) {
3540 continue;
3541 }
3542 if (lit.delay) {
3543 // Skip delayed literals, so that we only count the undelayed
3544 // version that ends up in the HWLM table.
3545 continue;
3546 }
3547 if (!isUsedLiteral(build, id)) {
3548 continue;
3549 }
3550
3551 num++;
3552 max_len = max(max_len, lit.s.length());
3553 }
3554 DEBUG_PRINTF("%zu floating literals with max_len=%zu\n", num, max_len);
3555 return {num, max_len};
3556}
3557
3558size_t calcLongLitThreshold(const RoseBuildImpl &build,
3559 const size_t historyRequired) {
3560 const auto &cc = build.cc;
3561
3562 // In block mode, we don't have history, so we don't need long literal
3563 // support and can just use "medium-length" literal confirm. TODO: we could
3564 // specialize further and have a block mode literal confirm instruction.
3565 if (!cc.streaming) {
3566 return SIZE_MAX;
3567 }
3568
3569 size_t longLitLengthThreshold = ROSE_LONG_LITERAL_THRESHOLD_MIN;
3570
3571 // Expand to size of history we've already allocated. Note that we need N-1
3572 // bytes of history to match a literal of length N.
3573 longLitLengthThreshold = max(longLitLengthThreshold, historyRequired + 1);
3574
3575 // If we only have one literal, allow for a larger value in order to avoid
3576 // building a long literal table for a trivial Noodle case that we could
3577 // fit in history.
3578 const auto num_len = floatingCountAndMaxLen(build);
3579 if (num_len.first == 1) {
3580 if (num_len.second > longLitLengthThreshold) {
3581 DEBUG_PRINTF("expanding for single literal of length %zu\n",
3582 num_len.second);
3583 longLitLengthThreshold = num_len.second;
3584 }
3585 }
3586
3587 // Clamp to max history available.
3588 longLitLengthThreshold =
3589 min(longLitLengthThreshold, size_t{cc.grey.maxHistoryAvailable} + 1);
3590
3591 return longLitLengthThreshold;
3592}
3593
3594static
3595map<left_id, u32> makeLeftQueueMap(const RoseGraph &g,
3596 const map<RoseVertex, left_build_info> &leftfix_info) {
3597 map<left_id, u32> lqm;
3598 for (const auto &e : leftfix_info) {
3599 if (e.second.has_lookaround) {
3600 continue;
3601 }
3602 DEBUG_PRINTF("%zu: using queue %u\n", g[e.first].index, e.second.queue);
3603 assert(e.second.queue != INVALID_QUEUE);
3604 left_id left(g[e.first].left);
3605 assert(!contains(lqm, left) || lqm[left] == e.second.queue);
3606 lqm[left] = e.second.queue;
3607 }
3608
3609 return lqm;
3610}
3611
3612bytecode_ptr<RoseEngine> RoseBuildImpl::buildFinalEngine(u32 minWidth) {
3613 // We keep all our offsets, counts etc. in a prototype RoseEngine which we
3614 // will copy into the real one once it is allocated: we can't do this
3615 // until we know how big it will be.
3616 RoseEngine proto;
3617 memset(&proto, 0, sizeof(proto));
3618
3619 // Set scanning mode.
3620 if (!cc.streaming) {
3621 proto.mode = HS_MODE_BLOCK;
3622 } else if (cc.vectored) {
3623 proto.mode = HS_MODE_VECTORED;
3624 } else {
3625 proto.mode = HS_MODE_STREAM;
3626 }
3627
3628 DerivedBoundaryReports dboundary(boundary);
3629
3630 size_t historyRequired = calcHistoryRequired(); // Updated by HWLM.
3631 size_t longLitLengthThreshold = calcLongLitThreshold(*this,
3632 historyRequired);
3633 DEBUG_PRINTF("longLitLengthThreshold=%zu\n", longLitLengthThreshold);
3634
3635 vector<LitFragment> fragments = groupByFragment(*this);
3636
3637 auto anchored_dfas = buildAnchoredDfas(*this, fragments);
3638
3639 build_context bc;
3640 u32 floatingMinLiteralMatchOffset
3641 = findMinFloatingLiteralMatch(*this, anchored_dfas);
3642 recordResources(bc.resources, *this, anchored_dfas, fragments);
3643 bc.needs_mpv_catchup = needsMpvCatchup(*this);
3644
3645 makeBoundaryPrograms(*this, bc, boundary, dboundary, proto.boundary);
3646
3647 tie(proto.reportProgramOffset, proto.reportProgramCount) =
3648 buildReportPrograms(*this, bc);
3649
3650 // Build NFAs
3651 bool mpv_as_outfix;
3652 prepMpv(*this, bc, &historyRequired, &mpv_as_outfix);
3653 proto.outfixBeginQueue = qif.allocated_count();
3654 if (!prepOutfixes(*this, bc, &historyRequired)) {
3655 return nullptr;
3656 }
3657 proto.outfixEndQueue = qif.allocated_count();
3658 proto.leftfixBeginQueue = proto.outfixEndQueue;
3659
3660 set<u32> no_retrigger_queues;
3661 set<u32> eager_queues;
3662
3663 /* Note: buildNfas may reduce the lag for vertices that have prefixes */
3664 if (!buildNfas(*this, bc, qif, &no_retrigger_queues, &eager_queues,
3665 &proto.leftfixBeginQueue)) {
3666 return nullptr;
3667 }
3668 u32 eodNfaIterOffset = buildEodNfaIterator(bc, proto.leftfixBeginQueue);
3669 buildCountingMiracles(bc);
3670
3671 u32 queue_count = qif.allocated_count(); /* excludes anchored matcher q;
3672 * som rev nfas */
3673 if (queue_count > cc.grey.limitRoseEngineCount) {
3674 throw ResourceLimitError();
3675 }
3676
3677 // Enforce role table resource limit.
3678 if (num_vertices(g) > cc.grey.limitRoseRoleCount) {
3679 throw ResourceLimitError();
3680 }
3681
3682 bc.roleStateIndices = assignStateIndices(*this);
3683
3684 u32 laggedRoseCount = 0;
3685 vector<LeftNfaInfo> leftInfoTable;
3686 buildLeftInfoTable(*this, bc, eager_queues, proto.leftfixBeginQueue,
3687 queue_count - proto.leftfixBeginQueue, leftInfoTable,
3688 &laggedRoseCount, &historyRequired);
3689
3690 // Information only needed for program construction.
3691 ProgramBuild prog_build(floatingMinLiteralMatchOffset,
3692 longLitLengthThreshold, needsCatchup(*this));
3693 prog_build.vertex_group_map = getVertexGroupMap(*this);
3694 prog_build.squashable_groups = getSquashableGroups(*this);
3695
3696 tie(proto.anchoredProgramOffset, proto.anchored_count) =
3697 writeAnchoredPrograms(*this, fragments, bc, prog_build);
3698
3699 tie(proto.delayProgramOffset, proto.delay_count) =
3700 writeDelayPrograms(*this, fragments, bc, prog_build);
3701
3702 // Build floating HWLM matcher prototype.
3703 rose_group fgroups = 0;
3704 auto fproto = buildFloatingMatcherProto(*this, fragments,
3705 longLitLengthThreshold,
3706 &fgroups, &historyRequired);
3707
3708 // Build delay rebuild HWLM matcher prototype.
3709 auto drproto = buildDelayRebuildMatcherProto(*this, fragments,
3710 longLitLengthThreshold);
3711
3712 // Build EOD-anchored HWLM matcher prototype.
3713 auto eproto = buildEodAnchoredMatcherProto(*this, fragments);
3714
3715 // Build small-block HWLM matcher prototype.
3716 auto sbproto = buildSmallBlockMatcherProto(*this, fragments);
3717
3718 buildLiteralPrograms(*this, fragments, bc, prog_build, fproto.get(),
3719 drproto.get(), eproto.get(), sbproto.get());
3720
3721 auto eod_prog = makeEodProgram(*this, bc, prog_build, eodNfaIterOffset);
3722 proto.eodProgramOffset = writeProgram(bc, move(eod_prog));
3723
3724 size_t longLitStreamStateRequired = 0;
3725 proto.longLitTableOffset
3726 = buildLongLiteralTable(*this, bc.engine_blob, bc.longLiterals,
3727 longLitLengthThreshold, &historyRequired,
3728 &longLitStreamStateRequired);
3729
3730 proto.lastByteHistoryIterOffset = buildLastByteIter(g, bc);
3731 proto.eagerIterOffset = writeEagerQueueIter(
3732 eager_queues, proto.leftfixBeginQueue, queue_count, bc.engine_blob);
3733
3734 addSomRevNfas(bc, proto, ssm);
3735
3736 writeDkeyInfo(rm, bc.engine_blob, proto);
3737 writeLeftInfo(bc.engine_blob, proto, leftInfoTable);
3738 writeLogicalInfo(rm, bc.engine_blob, proto);
3739
3740 auto flushComb_prog = makeFlushCombProgram(proto);
3741 proto.flushCombProgramOffset = writeProgram(bc, move(flushComb_prog));
3742
3743 // Build anchored matcher.
3744 auto atable = buildAnchoredMatcher(*this, fragments, anchored_dfas);
3745 if (atable) {
3746 proto.amatcherOffset = bc.engine_blob.add(atable);
3747 }
3748
3749 // Build floating HWLM matcher.
3750 auto ftable = buildHWLMMatcher(*this, fproto.get());
3751 if (ftable) {
3752 proto.fmatcherOffset = bc.engine_blob.add(ftable);
3753 bc.resources.has_floating = true;
3754 }
3755
3756 // Build delay rebuild HWLM matcher.
3757 auto drtable = buildHWLMMatcher(*this, drproto.get());
3758 if (drtable) {
3759 proto.drmatcherOffset = bc.engine_blob.add(drtable);
3760 }
3761
3762 // Build EOD-anchored HWLM matcher.
3763 auto etable = buildHWLMMatcher(*this, eproto.get());
3764 if (etable) {
3765 proto.ematcherOffset = bc.engine_blob.add(etable);
3766 }
3767
3768 // Build small-block HWLM matcher.
3769 auto sbtable = buildHWLMMatcher(*this, sbproto.get());
3770 if (sbtable) {
3771 proto.sbmatcherOffset = bc.engine_blob.add(sbtable);
3772 }
3773
3774 proto.activeArrayCount = proto.leftfixBeginQueue;
3775
3776 proto.anchorStateSize = atable ? anchoredStateSize(*atable) : 0;
3777
3778 DEBUG_PRINTF("rose history required %zu\n", historyRequired);
3779 assert(!cc.streaming || historyRequired <= cc.grey.maxHistoryAvailable);
3780
3781 // Some SOM schemes (reverse NFAs, for example) may require more history.
3782 historyRequired = max(historyRequired, (size_t)ssm.somHistoryRequired());
3783
3784 assert(!cc.streaming || historyRequired <=
3785 max(cc.grey.maxHistoryAvailable, cc.grey.somMaxRevNfaLength));
3786
3787 fillStateOffsets(*this, bc.roleStateIndices.size(), proto.anchorStateSize,
3788 proto.activeArrayCount, proto.activeLeftCount,
3789 laggedRoseCount, longLitStreamStateRequired,
3790 historyRequired, &proto.stateOffsets);
3791
3792 // Write in NfaInfo structures. This will also update state size
3793 // information in proto.
3794 writeNfaInfo(*this, bc, proto, no_retrigger_queues);
3795
3796 scatter_plan_raw state_scatter = buildStateScatterPlan(
3797 sizeof(u8), bc.roleStateIndices.size(), proto.activeLeftCount,
3798 proto.rosePrefixCount, proto.stateOffsets, cc.streaming,
3799 proto.activeArrayCount, proto.outfixBeginQueue, proto.outfixEndQueue);
3800
3801 u32 currOffset; /* relative to base of RoseEngine */
3802 if (!bc.engine_blob.empty()) {
3803 currOffset = bc.engine_blob.base_offset + bc.engine_blob.size();
3804 } else {
3805 currOffset = sizeof(RoseEngine);
3806 }
3807
3808 currOffset = ROUNDUP_CL(currOffset);
3809 DEBUG_PRINTF("currOffset %u\n", currOffset);
3810
3811 currOffset = ROUNDUP_N(currOffset, alignof(scatter_unit_u64a));
3812 u32 state_scatter_aux_offset = currOffset;
3813 currOffset += aux_size(state_scatter);
3814
3815 proto.historyRequired = verify_u32(historyRequired);
3816 proto.ekeyCount = rm.numEkeys();
3817
3818 proto.somHorizon = ssm.somPrecision();
3819 proto.somLocationCount = ssm.numSomSlots();
3820 proto.somLocationFatbitSize = fatbit_size(proto.somLocationCount);
3821
3822 proto.runtimeImpl = pickRuntimeImpl(*this, bc.resources,
3823 proto.outfixEndQueue);
3824 proto.mpvTriggeredByLeaf = anyEndfixMpvTriggers(*this);
3825
3826 proto.queueCount = queue_count;
3827 proto.activeQueueArraySize = fatbit_size(queue_count);
3828 proto.handledKeyCount = prog_build.handledKeys.size();
3829 proto.handledKeyFatbitSize = fatbit_size(proto.handledKeyCount);
3830
3831 proto.rolesWithStateCount = bc.roleStateIndices.size();
3832
3833 proto.initMpvNfa = mpv_as_outfix ? 0 : MO_INVALID_IDX;
3834 proto.stateSize = mmbit_size(bc.roleStateIndices.size());
3835
3836 proto.delay_fatbit_size = fatbit_size(proto.delay_count);
3837 proto.anchored_fatbit_size = fatbit_size(proto.anchored_count);
3838
3839 // The Small Write matcher is (conditionally) added to the RoseEngine in
3840 // another pass by the caller. Set to zero (meaning no SMWR engine) for
3841 // now.
3842 proto.smallWriteOffset = 0;
3843
3844 proto.amatcherMinWidth = findMinWidth(*this, ROSE_ANCHORED);
3845 proto.fmatcherMinWidth = findMinWidth(*this, ROSE_FLOATING);
3846 proto.eodmatcherMinWidth = findMinWidth(*this, ROSE_EOD_ANCHORED);
3847 proto.amatcherMaxBiAnchoredWidth = findMaxBAWidth(*this, ROSE_ANCHORED);
3848 proto.fmatcherMaxBiAnchoredWidth = findMaxBAWidth(*this, ROSE_FLOATING);
3849 proto.minWidth = hasBoundaryReports(boundary) ? 0 : minWidth;
3850 proto.minWidthExcludingBoundaries = minWidth;
3851 proto.floatingMinLiteralMatchOffset = floatingMinLiteralMatchOffset;
3852
3853 proto.maxBiAnchoredWidth = findMaxBAWidth(*this);
3854 proto.noFloatingRoots = hasNoFloatingRoots();
3855 proto.requiresEodCheck = hasEodAnchors(*this, bc, proto.outfixEndQueue);
3856 proto.hasOutfixesInSmallBlock = hasNonSmallBlockOutfix(outfixes);
3857 proto.canExhaust = rm.patternSetCanExhaust();
3858 proto.hasSom = hasSom;
3859
3860 /* populate anchoredDistance, floatingDistance, floatingMinDistance, etc */
3861 fillMatcherDistances(*this, &proto);
3862
3863 proto.initialGroups = getInitialGroups();
3864 proto.floating_group_mask = fgroups;
3865 proto.totalNumLiterals = verify_u32(literal_info.size());
3866 proto.asize = verify_u32(atable.size());
3867 proto.ematcherRegionSize = ematcher_region_size;
3868
3869 proto.size = currOffset;
3870
3871 // Time to allocate the real RoseEngine structure, at cacheline alignment.
3872 auto engine = make_zeroed_bytecode_ptr<RoseEngine>(currOffset, 64);
3873 assert(engine); // will have thrown bad_alloc otherwise.
3874
3875 // Copy in our prototype engine data.
3876 memcpy(engine.get(), &proto, sizeof(proto));
3877
3878 write_out(&engine->state_init, (char *)engine.get(), state_scatter,
3879 state_scatter_aux_offset);
3880
3881 // Copy in the engine blob.
3882 bc.engine_blob.write_bytes(engine.get());
3883
3884 // Add a small write engine if appropriate.
3885 engine = addSmallWriteEngine(*this, bc.resources, move(engine));
3886
3887 DEBUG_PRINTF("rose done %p\n", engine.get());
3888
3889 dumpRose(*this, fragments, makeLeftQueueMap(g, bc.leftfix_info),
3890 bc.suffixes, engine.get());
3891
3892 return engine;
3893}
3894
3895} // namespace ue2
3896