1/*
2 * Copyright (c) 2015-2018, 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 "catchup.h"
30#include "counting_miracle.h"
31#include "infix.h"
32#include "match.h"
33#include "miracle.h"
34#include "program_runtime.h"
35#include "rose.h"
36#include "rose_internal.h"
37#include "stream_long_lit.h"
38#include "hwlm/hwlm.h"
39#include "nfa/mcclellan.h"
40#include "nfa/nfa_api.h"
41#include "nfa/nfa_api_queue.h"
42#include "nfa/nfa_internal.h"
43#include "util/fatbit.h"
44
45static rose_inline
46void runAnchoredTableStream(const struct RoseEngine *t, const void *atable,
47 size_t alen, u64a offset,
48 struct hs_scratch *scratch) {
49 char *state_base = scratch->core_info.state + t->stateOffsets.anchorState;
50 const struct anchored_matcher_info *curr = atable;
51
52 do {
53 DEBUG_PRINTF("--anchored nfa (+%u) no %u so %u\n",
54 curr->anchoredMinDistance, curr->next_offset,
55 curr->state_offset);
56 const struct NFA *nfa
57 = (const struct NFA *)((const char *)curr + sizeof(*curr));
58 assert(ISALIGNED_CL(nfa));
59 assert(isMcClellanType(nfa->type));
60
61 char *state = state_base + curr->state_offset;
62
63 char start = 0;
64 size_t adj = 0;
65
66 if (offset <= curr->anchoredMinDistance) {
67 adj = curr->anchoredMinDistance - offset;
68 if (adj >= alen) {
69 goto next_nfa;
70 }
71
72 start = 1;
73 } else {
74 // (No state decompress necessary.)
75 if (nfa->type == MCCLELLAN_NFA_8) {
76 if (!*(u8 *)state) {
77 goto next_nfa;
78 }
79 } else {
80 if (!unaligned_load_u16(state)) {
81 goto next_nfa;
82 }
83 }
84 }
85
86 if (nfa->type == MCCLELLAN_NFA_8) {
87 nfaExecMcClellan8_SimpStream(nfa, state, scratch->core_info.buf,
88 start, adj, alen, roseAnchoredCallback,
89 scratch);
90 } else {
91 nfaExecMcClellan16_SimpStream(nfa, state, scratch->core_info.buf,
92 start, adj, alen,
93 roseAnchoredCallback, scratch);
94 }
95
96 next_nfa:
97 if (!curr->next_offset) {
98 break;
99 }
100
101 curr = (const void *)((const char *)curr + curr->next_offset);
102 } while (1);
103}
104
105
106static really_inline
107void saveStreamState(const struct NFA *nfa, struct mq *q, s64a loc) {
108 DEBUG_PRINTF("offset=%llu, length=%zu, hlength=%zu, loc=%lld\n",
109 q->offset, q->length, q->hlength, loc);
110 nfaQueueCompressState(nfa, q, loc);
111}
112
113static really_inline
114u8 getByteBefore(const struct core_info *ci, s64a sp) {
115 if (sp > 0) { // in main buffer
116 assert(sp <= (s64a)ci->len);
117 return ci->buf[sp - 1];
118 }
119 // in history buffer
120 assert(-sp < (s64a)ci->hlen);
121 return ci->hbuf[ci->hlen + sp - 1];
122}
123
124/** \brief Return value for \ref roseScanForMiracles. */
125enum MiracleAction {
126 MIRACLE_DEAD, //!< kill off this engine
127 MIRACLE_SAVED, //!< engine has been caught up and state saved
128 MIRACLE_CONTINUE //!< continue running and catch up engine
129};
130
131static really_inline
132enum MiracleAction roseScanForMiracles(const struct RoseEngine *t, char *state,
133 struct hs_scratch *scratch, u32 qi,
134 const struct LeftNfaInfo *left,
135 const struct NFA *nfa) {
136 struct core_info *ci = &scratch->core_info;
137 const u32 qCount = t->queueCount;
138 struct mq *q = scratch->queues + qi;
139
140 const char q_active = fatbit_isset(scratch->aqa, qCount, qi);
141 DEBUG_PRINTF("q_active=%d\n", q_active);
142
143 const s64a begin_loc = q_active ? q_cur_loc(q) : 0;
144 const s64a end_loc = ci->len;
145
146 s64a miracle_loc;
147 if (roseMiracleOccurs(t, left, ci, begin_loc, end_loc, &miracle_loc)) {
148 goto found_miracle;
149 }
150
151 if (roseCountingMiracleOccurs(t, left, ci, begin_loc, end_loc,
152 &miracle_loc)) {
153 goto found_miracle;
154 }
155
156 DEBUG_PRINTF("no miracle\n");
157 return MIRACLE_CONTINUE;
158
159found_miracle:
160 DEBUG_PRINTF("miracle at %lld\n", miracle_loc);
161
162 if (left->infix) {
163 if (!q_active) {
164 DEBUG_PRINTF("killing infix\n");
165 return MIRACLE_DEAD;
166 }
167
168 DEBUG_PRINTF("skip q forward, %lld to %lld\n", begin_loc, miracle_loc);
169 q_skip_forward_to(q, miracle_loc);
170 if (q_last_type(q) == MQE_START) {
171 DEBUG_PRINTF("miracle caused infix to die\n");
172 return MIRACLE_DEAD;
173 }
174
175 DEBUG_PRINTF("re-init infix state\n");
176 assert(q->items[q->cur].type == MQE_START);
177 q->items[q->cur].location = miracle_loc;
178 nfaQueueInitState(q->nfa, q);
179 } else {
180 if (miracle_loc > end_loc - t->historyRequired) {
181 char *streamState = state + getNfaInfoByQueue(t, qi)->stateOffset;
182 u64a offset = ci->buf_offset + miracle_loc;
183 u8 key = offset ? getByteBefore(ci, miracle_loc) : 0;
184 DEBUG_PRINTF("init state, key=0x%02x, offset=%llu\n", key, offset);
185 if (!nfaInitCompressedState(nfa, offset, streamState, key)) {
186 return MIRACLE_DEAD;
187 }
188 storeRoseDelay(t, state, left, (s64a)ci->len - miracle_loc);
189 return MIRACLE_SAVED;
190 }
191
192 DEBUG_PRINTF("re-init prefix (skip %lld->%lld)\n", begin_loc,
193 miracle_loc);
194 if (!q_active) {
195 fatbit_set(scratch->aqa, qCount, qi);
196 initRoseQueue(t, qi, left, scratch);
197 }
198 q->cur = q->end = 0;
199 pushQueueAt(q, 0, MQE_START, miracle_loc);
200 pushQueueAt(q, 1, MQE_TOP, miracle_loc);
201 nfaQueueInitState(q->nfa, q);
202 }
203
204 return MIRACLE_CONTINUE;
205}
206
207
208static really_inline
209char roseCatchUpLeftfix(const struct RoseEngine *t, char *state,
210 struct hs_scratch *scratch, u32 qi,
211 const struct LeftNfaInfo *left) {
212 assert(!left->transient); // active roses only
213
214 struct core_info *ci = &scratch->core_info;
215 const u32 qCount = t->queueCount;
216 struct mq *q = scratch->queues + qi;
217 const struct NFA *nfa = getNfaByQueue(t, qi);
218
219 if (nfaSupportsZombie(nfa)
220 && ci->buf_offset /* prefix can be alive with no q */
221 && !fatbit_isset(scratch->aqa, qCount, qi)
222 && isZombie(t, state, left)) {
223 DEBUG_PRINTF("yawn - zombie\n");
224 return 1;
225 }
226
227 if (left->stopTable) {
228 enum MiracleAction mrv =
229 roseScanForMiracles(t, state, scratch, qi, left, nfa);
230 switch (mrv) {
231 case MIRACLE_DEAD:
232 return 0;
233 case MIRACLE_SAVED:
234 return 1;
235 default:
236 assert(mrv == MIRACLE_CONTINUE);
237 break;
238 }
239 }
240
241 if (!fatbit_set(scratch->aqa, qCount, qi)) {
242 initRoseQueue(t, qi, left, scratch);
243
244 s32 sp;
245 if (ci->buf_offset) {
246 sp = -(s32)loadRoseDelay(t, state, left);
247 } else {
248 sp = 0;
249 }
250
251 DEBUG_PRINTF("ci->len=%zu, sp=%d, historyRequired=%u\n", ci->len, sp,
252 t->historyRequired);
253
254 if ( ci->len - sp + 1 < t->historyRequired) {
255 // we'll end up safely in the history region.
256 DEBUG_PRINTF("safely in history, skipping\n");
257 storeRoseDelay(t, state, left, (s64a)ci->len - sp);
258 return 1;
259 }
260
261 pushQueueAt(q, 0, MQE_START, sp);
262 if (left->infix || ci->buf_offset + sp > 0) {
263 loadStreamState(nfa, q, sp);
264 } else {
265 pushQueueAt(q, 1, MQE_TOP, sp);
266 nfaQueueInitState(nfa, q);
267 }
268 } else {
269 DEBUG_PRINTF("queue already active\n");
270 if (q->end - q->cur == 1 && q_cur_type(q) == MQE_START) {
271 DEBUG_PRINTF("empty queue, start loc=%lld\n", q_cur_loc(q));
272 s64a last_loc = q_cur_loc(q);
273 if (ci->len - last_loc + 1 < t->historyRequired) {
274 // we'll end up safely in the history region.
275 DEBUG_PRINTF("safely in history, saving state and skipping\n");
276 saveStreamState(nfa, q, last_loc);
277 storeRoseDelay(t, state, left, (s64a)ci->len - last_loc);
278 return 1;
279 }
280 }
281 }
282
283 // Determine whether the byte before last_loc will be in the history
284 // buffer on the next stream write.
285 s64a last_loc = q_last_loc(q);
286 s64a leftovers = ci->len - last_loc;
287 if (leftovers + 1 >= t->historyRequired) {
288 u32 catchup_offset = left->maxLag ? left->maxLag - 1 : 0;
289 last_loc = (s64a)ci->len - catchup_offset;
290 }
291
292 if (left->infix) {
293 if (infixTooOld(q, last_loc)) {
294 DEBUG_PRINTF("infix died of old age\n");
295 return 0;
296 }
297 reduceInfixQueue(q, last_loc, left->maxQueueLen, q->nfa->maxWidth);
298 }
299
300 DEBUG_PRINTF("end scan at %lld\n", last_loc);
301 pushQueueNoMerge(q, MQE_END, last_loc);
302
303#ifdef DEBUG
304 debugQueue(q);
305#endif
306
307 char rv = nfaQueueExecRose(nfa, q, MO_INVALID_IDX);
308 if (!rv) { /* nfa is dead */
309 DEBUG_PRINTF("died catching up to stream boundary\n");
310 return 0;
311 } else {
312 DEBUG_PRINTF("alive, saving stream state\n");
313 if (nfaSupportsZombie(nfa) &&
314 nfaGetZombieStatus(nfa, q, last_loc) == NFA_ZOMBIE_ALWAYS_YES) {
315 DEBUG_PRINTF("not so fast - zombie\n");
316 setAsZombie(t, state, left);
317 } else {
318 saveStreamState(nfa, q, last_loc);
319 storeRoseDelay(t, state, left, (s64a)ci->len - last_loc);
320 }
321 }
322
323 return 1;
324}
325
326static rose_inline
327void roseCatchUpLeftfixes(const struct RoseEngine *t, char *state,
328 struct hs_scratch *scratch) {
329 if (!t->activeLeftIterOffset) {
330 // No sparse iter, no non-transient roses.
331 return;
332 }
333
334 // As per UE-1629, we catch up leftfix engines to:
335 // * current position (last location in the queue, or last location we
336 // executed to if the queue is empty) if that position (and the byte
337 // before so we can decompress the stream state) will be in the history
338 // buffer on the next stream write; OR
339 // * (stream_boundary - max_delay) other
340
341 u8 *ara = getActiveLeftArray(t, state); /* indexed by offsets into
342 * left_table */
343 const u32 arCount = t->activeLeftCount;
344 const struct LeftNfaInfo *left_table = getLeftTable(t);
345 const struct mmbit_sparse_iter *it = getActiveLeftIter(t);
346
347 struct mmbit_sparse_state si_state[MAX_SPARSE_ITER_STATES];
348
349 u32 idx = 0;
350 u32 ri = mmbit_sparse_iter_begin(ara, arCount, &idx, it, si_state);
351 for (; ri != MMB_INVALID;
352 ri = mmbit_sparse_iter_next(ara, arCount, ri, &idx, it, si_state)) {
353 const struct LeftNfaInfo *left = left_table + ri;
354 u32 qi = ri + t->leftfixBeginQueue;
355 DEBUG_PRINTF("leftfix %u of %u, maxLag=%u, infix=%d\n", ri, arCount,
356 left->maxLag, (int)left->infix);
357 if (!roseCatchUpLeftfix(t, state, scratch, qi, left)) {
358 DEBUG_PRINTF("removing rose %u from active list\n", ri);
359 DEBUG_PRINTF("groups old=%016llx mask=%016llx\n",
360 scratch->tctxt.groups, left->squash_mask);
361 scratch->tctxt.groups &= left->squash_mask;
362 mmbit_unset(ara, arCount, ri);
363 }
364 }
365}
366
367// Saves out stream state for all our active suffix NFAs.
368static rose_inline
369void roseSaveNfaStreamState(const struct RoseEngine *t, char *state,
370 struct hs_scratch *scratch) {
371 struct mq *queues = scratch->queues;
372 u8 *aa = getActiveLeafArray(t, state);
373 u32 aaCount = t->activeArrayCount;
374
375 if (scratch->tctxt.mpv_inactive) {
376 DEBUG_PRINTF("mpv is dead as a doornail\n");
377 /* mpv if it exists is queue 0 */
378 mmbit_unset(aa, aaCount, 0);
379 }
380
381 for (u32 qi = mmbit_iterate(aa, aaCount, MMB_INVALID); qi != MMB_INVALID;
382 qi = mmbit_iterate(aa, aaCount, qi)) {
383 DEBUG_PRINTF("saving stream state for qi=%u\n", qi);
384
385 struct mq *q = queues + qi;
386
387 // If it's active, it should have an active queue (as we should have
388 // done some work!)
389 assert(fatbit_isset(scratch->aqa, t->queueCount, qi));
390
391 const struct NFA *nfa = getNfaByQueue(t, qi);
392 saveStreamState(nfa, q, q_cur_loc(q));
393 }
394}
395
396static rose_inline
397void ensureStreamNeatAndTidy(const struct RoseEngine *t, char *state,
398 struct hs_scratch *scratch, size_t length,
399 u64a offset) {
400 struct RoseContext *tctxt = &scratch->tctxt;
401
402 if (roseCatchUpTo(t, scratch, length + scratch->core_info.buf_offset) ==
403 HWLM_TERMINATE_MATCHING) {
404 return; /* dead; no need to clean up state. */
405 }
406 roseSaveNfaStreamState(t, state, scratch);
407 roseCatchUpLeftfixes(t, state, scratch);
408 roseFlushLastByteHistory(t, scratch, offset + length);
409 tctxt->lastEndOffset = offset + length;
410 storeGroups(t, state, tctxt->groups);
411 storeLongLiteralState(t, state, scratch);
412}
413
414static really_inline
415void do_rebuild(const struct RoseEngine *t, struct hs_scratch *scratch) {
416 assert(t->drmatcherOffset);
417 assert(!can_stop_matching(scratch));
418
419 const struct HWLM *hwlm = getByOffset(t, t->drmatcherOffset);
420 size_t len = MIN(scratch->core_info.hlen, t->delayRebuildLength);
421 const u8 *buf = scratch->core_info.hbuf + scratch->core_info.hlen - len;
422 DEBUG_PRINTF("BEGIN FLOATING REBUILD over %zu bytes\n", len);
423
424 scratch->core_info.status &= ~STATUS_DELAY_DIRTY;
425
426 hwlmExec(hwlm, buf, len, 0, roseDelayRebuildCallback, scratch,
427 scratch->tctxt.groups);
428 assert(!can_stop_matching(scratch));
429}
430
431static rose_inline
432void runEagerPrefixesStream(const struct RoseEngine *t,
433 struct hs_scratch *scratch) {
434 if (!t->eagerIterOffset
435 || scratch->core_info.buf_offset >= EAGER_STOP_OFFSET) {
436 return;
437 }
438
439 char *state = scratch->core_info.state;
440 u8 *ara = getActiveLeftArray(t, state); /* indexed by offsets into
441 * left_table */
442 const u32 arCount = t->activeLeftCount;
443 const u32 qCount = t->queueCount;
444 const struct LeftNfaInfo *left_table = getLeftTable(t);
445 const struct mmbit_sparse_iter *it = getByOffset(t, t->eagerIterOffset);
446
447 struct mmbit_sparse_state si_state[MAX_SPARSE_ITER_STATES];
448
449 u32 idx = 0;
450 u32 ri = mmbit_sparse_iter_begin(ara, arCount, &idx, it, si_state);
451 for (; ri != MMB_INVALID;
452 ri = mmbit_sparse_iter_next(ara, arCount, ri, &idx, it, si_state)) {
453 const struct LeftNfaInfo *left = left_table + ri;
454 u32 qi = ri + t->leftfixBeginQueue;
455 DEBUG_PRINTF("leftfix %u of %u, maxLag=%u\n", ri, arCount, left->maxLag);
456
457 assert(!fatbit_isset(scratch->aqa, qCount, qi));
458 assert(left->eager);
459 assert(!left->infix);
460
461 struct mq *q = scratch->queues + qi;
462 const struct NFA *nfa = getNfaByQueue(t, qi);
463 s64a loc = MIN(scratch->core_info.len,
464 EAGER_STOP_OFFSET - scratch->core_info.buf_offset);
465
466 fatbit_set(scratch->aqa, qCount, qi);
467 initRoseQueue(t, qi, left, scratch);
468
469 if (scratch->core_info.buf_offset) {
470 s64a sp = left->transient ? -(s64a)scratch->core_info.hlen
471 : -(s64a)loadRoseDelay(t, state, left);
472 pushQueueAt(q, 0, MQE_START, sp);
473 if (scratch->core_info.buf_offset + sp > 0) {
474 loadStreamState(nfa, q, sp);
475 /* if the leftfix fix is currently in a match state, we cannot
476 * advance it. */
477 if (nfaInAnyAcceptState(nfa, q)) {
478 continue;
479 }
480 pushQueueAt(q, 1, MQE_END, loc);
481 } else {
482 pushQueueAt(q, 1, MQE_TOP, sp);
483 pushQueueAt(q, 2, MQE_END, loc);
484 nfaQueueInitState(q->nfa, q);
485 }
486 } else {
487 pushQueueAt(q, 0, MQE_START, 0);
488 pushQueueAt(q, 1, MQE_TOP, 0);
489 pushQueueAt(q, 2, MQE_END, loc);
490 nfaQueueInitState(nfa, q);
491 }
492
493 char alive = nfaQueueExecToMatch(q->nfa, q, loc);
494
495 if (!alive) {
496 DEBUG_PRINTF("queue %u dead, squashing\n", qi);
497 mmbit_unset(ara, arCount, ri);
498 fatbit_unset(scratch->aqa, qCount, qi);
499 scratch->tctxt.groups &= left->squash_mask;
500 } else if (q->cur == q->end) {
501 assert(alive != MO_MATCHES_PENDING);
502 /* unlike in block mode we cannot squash groups if there is no match
503 * in this block as we need the groups on for later stream writes */
504 /* TODO: investigate possibility of a method to suppress groups for
505 * a single stream block. */
506 DEBUG_PRINTF("queue %u finished, nfa lives\n", qi);
507 q->cur = q->end = 0;
508 pushQueueAt(q, 0, MQE_START, loc);
509 } else {
510 assert(alive == MO_MATCHES_PENDING);
511 DEBUG_PRINTF("queue %u unfinished, nfa lives\n", qi);
512 q->end--; /* remove end item */
513 }
514 }
515}
516
517static really_inline
518int can_never_match(const struct RoseEngine *t, char *state,
519 struct hs_scratch *scratch, size_t length, u64a offset) {
520 struct RoseContext *tctxt = &scratch->tctxt;
521
522 if (tctxt->groups) {
523 DEBUG_PRINTF("still has active groups\n");
524 return 0;
525 }
526
527 if (offset + length <= t->anchoredDistance) { /* not < as may have eod */
528 DEBUG_PRINTF("still in anchored region\n");
529 return 0;
530 }
531
532 if (t->lastByteHistoryIterOffset) { /* last byte history is hard */
533 DEBUG_PRINTF("last byte history\n");
534 return 0;
535 }
536
537 if (mmbit_any(getActiveLeafArray(t, state), t->activeArrayCount)) {
538 DEBUG_PRINTF("active leaf\n");
539 return 0;
540 }
541
542 return 1;
543}
544
545void roseStreamExec(const struct RoseEngine *t, struct hs_scratch *scratch) {
546 DEBUG_PRINTF("OH HAI [%llu, %llu)\n", scratch->core_info.buf_offset,
547 scratch->core_info.buf_offset + (u64a)scratch->core_info.len);
548 assert(t);
549 assert(scratch->core_info.hbuf);
550 assert(scratch->core_info.buf);
551
552 // We should not have been called if we've already been told to terminate
553 // matching.
554 assert(!told_to_stop_matching(scratch));
555
556 assert(mmbit_sparse_iter_state_size(t->rolesWithStateCount)
557 < MAX_SPARSE_ITER_STATES);
558
559 size_t length = scratch->core_info.len;
560 u64a offset = scratch->core_info.buf_offset;
561
562 // We may have a maximum width (for engines constructed entirely
563 // of bi-anchored patterns). If this write would result in us progressing
564 // beyond this point, we cannot possibly match.
565 if (t->maxBiAnchoredWidth != ROSE_BOUND_INF
566 && offset + length > t->maxBiAnchoredWidth) {
567 DEBUG_PRINTF("bailing, write would progress beyond maxBAWidth\n");
568 return;
569 }
570
571 char *state = scratch->core_info.state;
572
573 struct RoseContext *tctxt = &scratch->tctxt;
574 tctxt->mpv_inactive = 0;
575 tctxt->groups = loadGroups(t, state);
576 tctxt->lit_offset_adjust = offset + 1; // index after last byte
577 tctxt->delayLastEndOffset = offset;
578 tctxt->lastEndOffset = offset;
579 tctxt->filledDelayedSlots = 0;
580 tctxt->lastMatchOffset = 0;
581 tctxt->lastCombMatchOffset = offset;
582 tctxt->minMatchOffset = offset;
583 tctxt->minNonMpvMatchOffset = offset;
584 tctxt->next_mpv_offset = 0;
585
586 DEBUG_PRINTF("BEGIN: history len=%zu, buffer len=%zu groups=%016llx\n",
587 scratch->core_info.hlen, scratch->core_info.len, tctxt->groups);
588
589 fatbit_clear(scratch->aqa);
590 scratch->al_log_sum = 0;
591 scratch->catchup_pq.qm_size = 0;
592
593 if (t->outfixBeginQueue != t->outfixEndQueue) {
594 streamInitSufPQ(t, state, scratch);
595 }
596
597 runEagerPrefixesStream(t, scratch);
598
599 u32 alen = t->anchoredDistance > offset ?
600 MIN(length + offset, t->anchoredDistance) - offset : 0;
601
602 const struct anchored_matcher_info *atable = getALiteralMatcher(t);
603 if (atable && alen) {
604 DEBUG_PRINTF("BEGIN ANCHORED %zu/%u\n", scratch->core_info.hlen, alen);
605 runAnchoredTableStream(t, atable, alen, offset, scratch);
606
607 if (can_stop_matching(scratch)) {
608 goto exit;
609 }
610 }
611
612 const struct HWLM *ftable = getFLiteralMatcher(t);
613 if (ftable) {
614 // Load in long literal table state and set up "fake history" buffers
615 // (ll_buf, etc, used by the CHECK_LONG_LIT instruction). Note that this
616 // must be done here in order to ensure that it happens before any path
617 // that leads to storeLongLiteralState(), which relies on these buffers.
618 loadLongLiteralState(t, state, scratch);
619
620 if (t->noFloatingRoots && !roseHasInFlightMatches(t, state, scratch)) {
621 DEBUG_PRINTF("skip FLOATING: no inflight matches\n");
622 goto flush_delay_and_exit;
623 }
624
625 size_t flen = length;
626 if (t->floatingDistance != ROSE_BOUND_INF) {
627 flen = t->floatingDistance > offset ?
628 MIN(t->floatingDistance, length + offset) - offset : 0;
629 }
630
631 size_t hlength = scratch->core_info.hlen;
632
633 char rebuild = hlength &&
634 (scratch->core_info.status & STATUS_DELAY_DIRTY) &&
635 (t->maxFloatingDelayedMatch == ROSE_BOUND_INF ||
636 offset < t->maxFloatingDelayedMatch);
637 DEBUG_PRINTF("**rebuild %hhd status %hhu mfdm %u, offset %llu\n",
638 rebuild, scratch->core_info.status,
639 t->maxFloatingDelayedMatch, offset);
640
641 if (rebuild) { /* rebuild floating delayed match stuff */
642 do_rebuild(t, scratch);
643 }
644
645 if (!flen) {
646 goto flush_delay_and_exit;
647 }
648
649 if (flen + offset <= t->floatingMinDistance) {
650 DEBUG_PRINTF("skip FLOATING: before floating min\n");
651 goto flush_delay_and_exit;
652 }
653
654 size_t start = 0;
655 if (offset < t->floatingMinDistance) {
656 // This scan crosses the floating min distance, so we can use that
657 // to set HWLM's "start" offset.
658 start = t->floatingMinDistance - offset;
659 }
660 DEBUG_PRINTF("start=%zu\n", start);
661
662 DEBUG_PRINTF("BEGIN FLOATING (over %zu/%zu)\n", flen, length);
663 hwlmExecStreaming(ftable, flen, start, roseFloatingCallback, scratch,
664 tctxt->groups & t->floating_group_mask);
665 }
666
667flush_delay_and_exit:
668 DEBUG_PRINTF("flushing floating\n");
669 if (cleanUpDelayed(t, scratch, length, offset) == HWLM_TERMINATE_MATCHING) {
670 return;
671 }
672
673exit:
674 DEBUG_PRINTF("CLEAN UP TIME\n");
675 if (!can_stop_matching(scratch)) {
676 ensureStreamNeatAndTidy(t, state, scratch, length, offset);
677 }
678
679 if (!told_to_stop_matching(scratch)
680 && can_never_match(t, state, scratch, length, offset)) {
681 DEBUG_PRINTF("PATTERN SET IS EXHAUSTED\n");
682 scratch->core_info.status = STATUS_EXHAUSTED;
683 return;
684 }
685
686 DEBUG_PRINTF("DONE STREAMING SCAN, status = %u\n",
687 scratch->core_info.status);
688 return;
689}
690
691static rose_inline
692void roseStreamInitEod(const struct RoseEngine *t, u64a offset,
693 struct hs_scratch *scratch) {
694 struct RoseContext *tctxt = &scratch->tctxt;
695 /* TODO: diff groups for eod */
696 tctxt->groups = loadGroups(t, scratch->core_info.state);
697 tctxt->lit_offset_adjust = scratch->core_info.buf_offset
698 - scratch->core_info.hlen
699 + 1; // index after last byte
700 tctxt->delayLastEndOffset = offset;
701 tctxt->lastEndOffset = offset;
702 tctxt->filledDelayedSlots = 0;
703 tctxt->lastMatchOffset = 0;
704 tctxt->lastCombMatchOffset = offset; /* DO NOT set 0 here! */
705 tctxt->minMatchOffset = offset;
706 tctxt->minNonMpvMatchOffset = offset;
707 tctxt->next_mpv_offset = offset;
708
709 scratch->catchup_pq.qm_size = 0;
710 scratch->al_log_sum = 0; /* clear the anchored logs */
711
712 fatbit_clear(scratch->aqa);
713}
714
715void roseStreamEodExec(const struct RoseEngine *t, u64a offset,
716 struct hs_scratch *scratch) {
717 assert(scratch);
718 assert(t->requiresEodCheck);
719 DEBUG_PRINTF("ci buf %p/%zu his %p/%zu\n", scratch->core_info.buf,
720 scratch->core_info.len, scratch->core_info.hbuf,
721 scratch->core_info.hlen);
722
723 // We should not have been called if we've already been told to terminate
724 // matching.
725 assert(!told_to_stop_matching(scratch));
726
727 if (t->maxBiAnchoredWidth != ROSE_BOUND_INF
728 && offset > t->maxBiAnchoredWidth) {
729 DEBUG_PRINTF("bailing, we are beyond max width\n");
730 /* also some of the history/state may be stale */
731 return;
732 }
733
734 if (!t->eodProgramOffset) {
735 DEBUG_PRINTF("no eod program\n");
736 return;
737 }
738
739 roseStreamInitEod(t, offset, scratch);
740
741 DEBUG_PRINTF("running eod program at %u\n", t->eodProgramOffset);
742
743 // There should be no pending delayed literals.
744 assert(!scratch->tctxt.filledDelayedSlots);
745
746 const u64a som = 0;
747 const u8 flags = ROSE_PROG_FLAG_SKIP_MPV_CATCHUP;
748
749 // Note: we ignore the result, as this is the last thing to ever happen on
750 // a scan.
751 roseRunProgram(t, scratch, t->eodProgramOffset, som, offset, flags);
752}
753