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 | |
112 | using namespace std; |
113 | using boost::adaptors::map_values; |
114 | using boost::adaptors::map_keys; |
115 | |
116 | namespace 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 | |
136 | namespace /* anon */ { |
137 | |
138 | struct 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 */ |
179 | struct ExclusiveSubengine { |
180 | bytecode_ptr<NFA> nfa; |
181 | vector<RoseVertex> vertices; |
182 | }; |
183 | |
184 | /** \brief exclusive info to build tamarama */ |
185 | struct 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 | |
196 | static |
197 | void 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 | |
207 | static |
208 | u32 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 | */ |
225 | static |
226 | bool 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 | |
258 | static |
259 | bool 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 | |
306 | static |
307 | bool 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 | |
330 | static |
331 | u8 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 | */ |
360 | static |
361 | bool 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 | |
381 | static |
382 | void 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. |
468 | rose_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 | |
477 | static |
478 | bool 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 | |
505 | namespace { |
506 | struct 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 | |
519 | static |
520 | void 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 | */ |
555 | static |
556 | bytecode_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 | */ |
608 | static |
609 | bytecode_ptr<NFA> |
610 | buildRepeatEngine(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 | |
624 | static |
625 | bytecode_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 */ |
643 | static |
644 | bytecode_ptr<NFA> |
645 | buildSuffix(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 | |
717 | static |
718 | void 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 | |
738 | static |
739 | vector<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 | */ |
753 | static |
754 | void 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 | |
773 | static |
774 | bytecode_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 | |
852 | static |
853 | void 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 | |
869 | static |
870 | void 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 | |
898 | static |
899 | void 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 | |
915 | static |
916 | u32 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 | |
953 | struct eager_info { |
954 | shared_ptr<NGHolder> new_graph; |
955 | u32 lag_adjust = 0; |
956 | }; |
957 | |
958 | static |
959 | bool 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 | |
1034 | static |
1035 | left_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 | |
1061 | static |
1062 | void 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 | |
1086 | static |
1087 | bool 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 | |
1190 | static |
1191 | unique_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 | |
1214 | static |
1215 | void 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 | |
1235 | static |
1236 | shared_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 | |
1258 | static |
1259 | void 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 | |
1279 | static |
1280 | void 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 | |
1302 | static |
1303 | void 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 | |
1365 | static |
1366 | void 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 | |
1389 | static |
1390 | void 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 | |
1426 | static |
1427 | void 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 | |
1486 | static |
1487 | bool 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 | |
1576 | static |
1577 | void 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 | |
1589 | static |
1590 | bool 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 | |
1599 | namespace { |
1600 | class OutfixBuilder : public boost::static_visitor<bytecode_ptr<NFA>> { |
1601 | public: |
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 | |
1654 | private: |
1655 | const RoseBuildImpl &build; |
1656 | }; |
1657 | } |
1658 | |
1659 | static |
1660 | bytecode_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 | |
1671 | static |
1672 | void 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 | |
1720 | static |
1721 | void 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 | |
1742 | static |
1743 | bool 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 | |
1781 | static |
1782 | void 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 | |
1805 | static |
1806 | void 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 | |
1824 | static |
1825 | void 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 | |
1870 | static |
1871 | void 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 | |
1930 | static |
1931 | bool 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 | |
1985 | static |
1986 | void 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 */ |
2030 | static |
2031 | bool 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 | |
2064 | static |
2065 | void 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 | |
2088 | static |
2089 | void 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 */ |
2108 | u32 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 | |
2170 | static |
2171 | u32 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 | |
2194 | static |
2195 | u32 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 | |
2223 | static |
2224 | vector<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. */ |
2262 | static |
2263 | u32 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 | |
2283 | static |
2284 | bool 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 | |
2294 | static |
2295 | bool 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 | |
2324 | struct 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 | |
2333 | static |
2334 | void 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 | |
2353 | static |
2354 | void 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 | |
2385 | static |
2386 | u32 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 | |
2411 | static |
2412 | u32 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 | |
2432 | static |
2433 | bool 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 | |
2463 | static |
2464 | void 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 | |
2472 | static |
2473 | void 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 | |
2483 | static |
2484 | void 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 | |
2495 | static |
2496 | void 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 | |
2544 | static |
2545 | bool 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 | |
2562 | static |
2563 | void 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 | |
2581 | static |
2582 | unordered_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 | |
2618 | static |
2619 | bool 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 | |
2628 | static |
2629 | void 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 | |
2718 | static |
2719 | RoseProgram 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 | |
2732 | static |
2733 | RoseProgram 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 | */ |
2753 | static |
2754 | vector<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 | |
2780 | static |
2781 | bool 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 | |
2800 | static |
2801 | rose_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 | |
2810 | static |
2811 | vector<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 | |
2889 | static |
2890 | void 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 | |
2916 | static |
2917 | void 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 | |
2963 | static |
2964 | void 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 | |
3021 | static |
3022 | void 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 | |
3040 | static |
3041 | void 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 | */ |
3064 | static |
3065 | void 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 | */ |
3087 | static |
3088 | pair<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 | */ |
3136 | static |
3137 | pair<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 | */ |
3194 | static |
3195 | set<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 | |
3217 | static |
3218 | pair<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 | |
3238 | static |
3239 | bool 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 | |
3251 | static |
3252 | bool 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 | |
3263 | static |
3264 | void 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 | |
3309 | static |
3310 | void 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 | |
3345 | static |
3346 | RoseProgram 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 | |
3364 | static |
3365 | RoseProgram makeFlushCombProgram(const RoseEngine &t) { |
3366 | RoseProgram program; |
3367 | if (t.ckeyCount) { |
3368 | addFlushCombinationProgram(program); |
3369 | } |
3370 | return program; |
3371 | } |
3372 | |
3373 | static |
3374 | u32 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 | |
3382 | static |
3383 | void 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 | |
3474 | static |
3475 | u32 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 | |
3491 | static |
3492 | bytecode_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 | */ |
3531 | static |
3532 | pair<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 | |
3558 | size_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 | |
3594 | static |
3595 | map<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 | |
3612 | bytecode_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 | |