1/*
2 * Copyright (c) 2016-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/**
30 * \file
31 * \brief Rose build: code for constructing literal tables.
32 */
33
34#include "rose_build_matchers.h"
35
36#include "rose_build_dump.h"
37#include "rose_build_impl.h"
38#include "rose_build_lit_accel.h"
39#include "rose_build_width.h"
40#include "hwlm/hwlm_build.h"
41#include "hwlm/hwlm_internal.h"
42#include "hwlm/hwlm_literal.h"
43#include "nfa/castlecompile.h"
44#include "nfa/nfa_api_queue.h"
45#include "util/charreach_util.h"
46#include "util/compile_context.h"
47#include "util/compile_error.h"
48#include "util/dump_charclass.h"
49#include "util/make_unique.h"
50#include "util/report.h"
51#include "util/report_manager.h"
52#include "util/verify_types.h"
53#include "ue2common.h"
54
55#include <iomanip>
56#include <sstream>
57
58#include <boost/range/adaptor/map.hpp>
59#include <boost/range/adaptor/reversed.hpp>
60
61using namespace std;
62using boost::adaptors::map_values;
63
64namespace ue2 {
65
66static const size_t MAX_ACCEL_STRING_LEN = 16;
67
68#if defined(DEBUG) || defined(DUMP_SUPPORT)
69static UNUSED
70string dumpMask(const vector<u8> &v) {
71 ostringstream oss;
72 for (u8 e : v) {
73 oss << setfill('0') << setw(2) << hex << (unsigned int)e;
74 }
75 return oss.str();
76}
77#endif
78
79static
80bool maskFromLeftGraph(const LeftEngInfo &left, vector<u8> &msk,
81 vector<u8> &cmp) {
82 const u32 lag = left.lag;
83 const ReportID report = left.leftfix_report;
84
85 DEBUG_PRINTF("leftfix with lag %u, report %u\n", lag, report);
86
87 assert(left.graph);
88 const NGHolder &h = *left.graph;
89 assert(in_degree(h.acceptEod, h) == 1); // no eod reports
90
91 // Start with the set of reporter vertices for this leftfix.
92 set<NFAVertex> curr;
93 for (auto u : inv_adjacent_vertices_range(h.accept, h)) {
94 if (contains(h[u].reports, report)) {
95 curr.insert(u);
96 }
97 }
98 assert(!curr.empty());
99
100 size_t i = HWLM_MASKLEN - lag - 1;
101 do {
102 if (curr.empty() || contains(curr, h.start)
103 || contains(curr, h.startDs)) {
104 DEBUG_PRINTF("end of the road\n");
105 break;
106 }
107
108 set<NFAVertex> next;
109 CharReach cr;
110 for (NFAVertex v : curr) {
111 const auto &v_cr = h[v].char_reach;
112 DEBUG_PRINTF("vertex %zu, reach %s\n", h[v].index,
113 describeClass(v_cr).c_str());
114 cr |= v_cr;
115 insert(&next, inv_adjacent_vertices(v, h));
116 }
117 make_and_cmp_mask(cr, &msk.at(i), &cmp.at(i));
118 DEBUG_PRINTF("%zu: reach=%s, msk=%u, cmp=%u\n", i,
119 describeClass(cr).c_str(), msk[i], cmp[i]);
120 curr.swap(next);
121 } while (i-- > 0);
122
123 return true;
124}
125
126static
127bool maskFromLeftCastle(const LeftEngInfo &left, vector<u8> &msk,
128 vector<u8> &cmp) {
129 const u32 lag = left.lag;
130 const ReportID report = left.leftfix_report;
131
132 DEBUG_PRINTF("leftfix with lag %u, report %u\n", lag, report);
133
134 assert(left.castle);
135 const CastleProto &c = *left.castle;
136
137 depth min_width(depth::infinity());
138 for (const PureRepeat &repeat : c.repeats | map_values) {
139 if (contains(repeat.reports, report)) {
140 min_width = min(min_width, repeat.bounds.min);
141 }
142 }
143
144 DEBUG_PRINTF("castle min width for this report is %s\n",
145 min_width.str().c_str());
146
147 if (!min_width.is_finite() || min_width == depth(0)) {
148 DEBUG_PRINTF("bad min width\n");
149 return false;
150 }
151
152 u32 len = min_width;
153 u32 end = HWLM_MASKLEN - lag;
154 for (u32 i = end; i > end - min(end, len); i--) {
155 make_and_cmp_mask(c.reach(), &msk.at(i - 1), &cmp.at(i - 1));
156 }
157
158 return true;
159}
160
161static
162bool maskFromLeft(const LeftEngInfo &left, vector<u8> &msk, vector<u8> &cmp) {
163 if (left.lag >= HWLM_MASKLEN) {
164 DEBUG_PRINTF("too much lag\n");
165 return false;
166 }
167
168 if (left.graph) {
169 return maskFromLeftGraph(left, msk, cmp);
170 } else if (left.castle) {
171 return maskFromLeftCastle(left, msk, cmp);
172 }
173
174 return false;
175}
176
177static
178bool maskFromPreds(const RoseBuildImpl &build, const rose_literal_id &id,
179 const RoseVertex v, vector<u8> &msk, vector<u8> &cmp) {
180 const RoseGraph &g = build.g;
181
182 // For right now, wuss out and only handle cases with one pred.
183 if (in_degree(v, g) != 1) {
184 return false;
185 }
186
187 // Root successors have no literal before them.
188 if (build.isRootSuccessor(v)) {
189 return false;
190 }
191
192 // If we have a single predecessor with a short bound, we may be able to
193 // fill out a mask with the trailing bytes of the previous literal. This
194 // allows us to improve literals like the 'bar' in 'fo.bar'.
195
196 RoseEdge e = *(in_edges(v, g).first);
197 u32 bound = g[e].maxBound;
198 if (bound != g[e].minBound || bound >= HWLM_MASKLEN) {
199 return false;
200 }
201
202 bound += id.s.length();
203 if (bound >= HWLM_MASKLEN) {
204 return false;
205 }
206
207 DEBUG_PRINTF("bound %u\n", bound);
208
209 RoseVertex u = source(e, g);
210 if (g[u].literals.size() != 1) {
211 DEBUG_PRINTF("u has %zu literals\n", g[u].literals.size());
212 return false;
213 }
214
215 u32 u_lit_id = *(g[u].literals.begin());
216 const rose_literal_id &u_id = build.literals.at(u_lit_id);
217 DEBUG_PRINTF("u has lit: %s\n", escapeString(u_id.s).c_str());
218
219 // Number of characters to take from the back of u's literal.
220 size_t u_len = u_id.s.length();
221 size_t u_sublen = min(u_len, (size_t)HWLM_MASKLEN - bound);
222
223 size_t i = HWLM_MASKLEN - (bound + u_sublen);
224
225 ue2_literal::const_iterator it, ite;
226 for (it = u_id.s.begin() + (u_len - u_sublen), ite = u_id.s.end();
227 it != ite; ++it) {
228 make_and_cmp_mask(*it, &msk.at(i), &cmp.at(i));
229 ++i;
230 }
231
232 return true;
233}
234
235static
236bool addSurroundingMask(const RoseBuildImpl &build, const rose_literal_id &id,
237 const RoseVertex v, vector<u8> &msk, vector<u8> &cmp) {
238 // Start with zero masks.
239 msk.assign(HWLM_MASKLEN, 0);
240 cmp.assign(HWLM_MASKLEN, 0);
241
242 const LeftEngInfo &left = build.g[v].left;
243 if (left && left.lag < HWLM_MASKLEN) {
244 if (maskFromLeft(left, msk, cmp)) {
245 DEBUG_PRINTF("mask from a leftfix!\n");
246 return true;
247 }
248 }
249
250 if (id.s.length() < HWLM_MASKLEN) {
251 if (maskFromPreds(build, id, v, msk, cmp)) {
252 DEBUG_PRINTF("mask from preds!\n");
253 return true;
254 }
255 }
256
257 return false;
258}
259
260static
261bool hamsterMaskCombine(vector<u8> &msk, vector<u8> &cmp,
262 const vector<u8> &v_msk, const vector<u8> &v_cmp) {
263 assert(msk.size() == HWLM_MASKLEN && cmp.size() == HWLM_MASKLEN);
264 assert(v_msk.size() == HWLM_MASKLEN && v_cmp.size() == HWLM_MASKLEN);
265
266 u8 all_masks = 0;
267
268 for (size_t i = 0; i < HWLM_MASKLEN; i++) {
269 u8 filter = ~(cmp[i] ^ v_cmp[i]);
270 msk[i] &= v_msk[i];
271 msk[i] &= filter;
272 cmp[i] &= filter;
273
274 all_masks |= msk[i];
275 }
276
277 // Return false if we have no bits on in any mask elements.
278 return all_masks != 0;
279}
280
281static
282bool addSurroundingMask(const RoseBuildImpl &build, const rose_literal_id &id,
283 const rose_literal_info &info, vector<u8> &msk,
284 vector<u8> &cmp) {
285 if (!build.cc.grey.roseHamsterMasks) {
286 return false;
287 }
288
289 if (!info.delayed_ids.empty()) {
290 // Not safe to add masks to delayed literals at this late stage.
291 return false;
292 }
293
294 msk.assign(HWLM_MASKLEN, 0);
295 cmp.assign(HWLM_MASKLEN, 0);
296
297 size_t num = 0;
298 vector<u8> v_msk, v_cmp;
299
300 for (RoseVertex v : info.vertices) {
301 if (!addSurroundingMask(build, id, v, v_msk, v_cmp)) {
302 DEBUG_PRINTF("no mask\n");
303 return false;
304 }
305
306 if (!num++) {
307 // First (or only) vertex, this becomes the mask/cmp pair.
308 msk = v_msk;
309 cmp = v_cmp;
310 } else {
311 // Multiple vertices with potentially different masks. We combine
312 // them into an 'advisory' mask.
313 if (!hamsterMaskCombine(msk, cmp, v_msk, v_cmp)) {
314 DEBUG_PRINTF("mask went to zero\n");
315 return false;
316 }
317 }
318 }
319
320 normaliseLiteralMask(id.s, msk, cmp);
321
322 if (msk.empty()) {
323 DEBUG_PRINTF("no mask\n");
324 return false;
325 }
326
327 DEBUG_PRINTF("msk=%s, cmp=%s\n", dumpMask(msk).c_str(),
328 dumpMask(cmp).c_str());
329 return true;
330}
331
332void findMoreLiteralMasks(RoseBuildImpl &build) {
333 if (!build.cc.grey.roseHamsterMasks) {
334 return;
335 }
336
337 vector<u32> candidates;
338 for (u32 id = 0; id < build.literals.size(); id++) {
339 const auto &lit = build.literals.at(id);
340
341 if (lit.delay || build.isDelayed(id)) {
342 continue;
343 }
344
345 // Literal masks are only allowed for literals that will end up in an
346 // HWLM table.
347 switch (lit.table) {
348 case ROSE_FLOATING:
349 case ROSE_EOD_ANCHORED:
350 case ROSE_ANCHORED_SMALL_BLOCK:
351 break;
352 default:
353 continue;
354 }
355
356 candidates.push_back(id);
357 }
358
359 for (const u32 &id : candidates) {
360 const auto &lit = build.literals.at(id);
361 auto &lit_info = build.literal_info.at(id);
362
363 vector<u8> msk, cmp;
364 if (!addSurroundingMask(build, lit, lit_info, msk, cmp)) {
365 continue;
366 }
367 DEBUG_PRINTF("found surrounding mask for lit_id=%u (%s)\n", id,
368 dumpString(lit.s).c_str());
369 u32 new_id = build.getLiteralId(lit.s, msk, cmp, lit.delay, lit.table);
370 if (new_id == id) {
371 continue;
372 }
373 DEBUG_PRINTF("replacing with new lit_id=%u\n", new_id);
374
375 // Note that our new literal may already exist and have vertices, etc.
376 // We assume that this transform is happening prior to group assignment.
377 assert(lit_info.group_mask == 0);
378 auto &new_info = build.literal_info.at(new_id);
379
380 // Move the vertices across.
381 new_info.vertices.insert(begin(lit_info.vertices),
382 end(lit_info.vertices));
383 for (auto v : lit_info.vertices) {
384 build.g[v].literals.erase(id);
385 build.g[v].literals.insert(new_id);
386 }
387 lit_info.vertices.clear();
388
389 // Preserve other properties.
390 new_info.requires_benefits = lit_info.requires_benefits;
391 }
392}
393
394// The mask already associated with the literal and any mask due to
395// mixed-case is mandatory.
396static
397void addLiteralMask(const rose_literal_id &id, vector<u8> &msk,
398 vector<u8> &cmp) {
399 const size_t suffix_len = min(id.s.length(), size_t{HWLM_MASKLEN});
400 bool mixed_suffix = mixed_sensitivity_in(id.s.end() - suffix_len,
401 id.s.end());
402
403 if (id.msk.empty() && !mixed_suffix) {
404 return;
405 }
406
407 while (msk.size() < HWLM_MASKLEN) {
408 msk.insert(msk.begin(), 0);
409 cmp.insert(cmp.begin(), 0);
410 }
411
412 if (!id.msk.empty()) {
413 assert(id.msk.size() <= HWLM_MASKLEN);
414 assert(id.msk.size() == id.cmp.size());
415 for (size_t i = 0; i < id.msk.size(); i++) {
416 size_t mand_offset = msk.size() - i - 1;
417 size_t lit_offset = id.msk.size() - i - 1;
418 msk[mand_offset] = id.msk[lit_offset];
419 cmp[mand_offset] = id.cmp[lit_offset];
420 }
421 }
422
423 if (mixed_suffix) {
424 auto it = id.s.rbegin();
425 for (size_t i = 0; i < suffix_len; ++i, ++it) {
426 const auto &c = *it;
427 if (!c.nocase) {
428 size_t offset = HWLM_MASKLEN - i - 1;
429 DEBUG_PRINTF("offset %zu must match 0x%02x exactly\n", offset,
430 c.c);
431 make_and_cmp_mask(c, &msk[offset], &cmp[offset]);
432 }
433 }
434 }
435
436 normaliseLiteralMask(id.s, msk, cmp);
437}
438
439static
440bool isDirectHighlander(const RoseBuildImpl &build, const u32 id,
441 const rose_literal_info &info) {
442 if (!build.isDirectReport(id)) {
443 return false;
444 }
445
446 auto is_simple_exhaustible = [&build](ReportID rid) {
447 const Report &report = build.rm.getReport(rid);
448 return isSimpleExhaustible(report);
449 };
450
451 assert(!info.vertices.empty());
452 for (const auto &v : info.vertices) {
453 const auto &reports = build.g[v].reports;
454 assert(!reports.empty());
455 if (!all_of(begin(reports), end(reports),
456 is_simple_exhaustible)) {
457 return false;
458 }
459 }
460 return true;
461}
462
463// Called by isNoRunsLiteral below.
464static
465bool isNoRunsVertex(const RoseBuildImpl &build, RoseVertex u) {
466 const RoseGraph &g = build.g;
467 if (!g[u].isBoring()) {
468 DEBUG_PRINTF("u=%zu is not boring\n", g[u].index);
469 return false;
470 }
471
472 if (!g[u].reports.empty()) {
473 DEBUG_PRINTF("u=%zu has accept\n", g[u].index);
474 return false;
475 }
476
477 /* TODO: handle non-root roles as well. It can't be that difficult... */
478
479 if (in_degree(u, g) != 1) {
480 DEBUG_PRINTF("u=%zu is not a root role\n", g[u].index);
481 return false;
482 }
483
484 RoseEdge e = edge(build.root, u, g);
485
486 if (!e) {
487 DEBUG_PRINTF("u=%zu is not a root role\n", g[u].index);
488 return false;
489 }
490
491 if (g[e].minBound != 0 || g[e].maxBound != ROSE_BOUND_INF) {
492 DEBUG_PRINTF("u=%zu has bounds from root\n", g[u].index);
493 return false;
494 }
495
496 for (const auto &oe : out_edges_range(u, g)) {
497 RoseVertex v = target(oe, g);
498 if (g[oe].maxBound != ROSE_BOUND_INF) {
499 DEBUG_PRINTF("edge (%zu,%zu) has max bound\n", g[u].index,
500 g[v].index);
501 return false;
502 }
503 if (g[v].left) {
504 DEBUG_PRINTF("v=%zu has rose prefix\n", g[v].index);
505 return false;
506 }
507 }
508 return true;
509}
510
511static
512bool isNoRunsLiteral(const RoseBuildImpl &build, const u32 id,
513 const rose_literal_info &info, const size_t max_len) {
514 DEBUG_PRINTF("lit id %u\n", id);
515
516 if (info.requires_benefits) {
517 DEBUG_PRINTF("requires benefits\n"); // which would need confirm
518 return false;
519 }
520
521 size_t len = build.literals.at(id).s.length();
522 if (len > max_len) {
523 DEBUG_PRINTF("long literal, requires confirm\n");
524 return false;
525 }
526
527 if (len > ROSE_SHORT_LITERAL_LEN_MAX) {
528 DEBUG_PRINTF("medium-length literal, requires confirm\n");
529 return false;
530 }
531
532 if (isDirectHighlander(build, id, info)) {
533 DEBUG_PRINTF("highlander direct report\n");
534 return true;
535 }
536
537 // Undelayed vertices.
538 for (RoseVertex v : info.vertices) {
539 if (!isNoRunsVertex(build, v)) {
540 return false;
541 }
542 }
543
544 // Delayed vertices.
545 for (u32 d : info.delayed_ids) {
546 assert(d < build.literal_info.size());
547 const rose_literal_info &delayed_info = build.literal_info.at(d);
548 assert(delayed_info.undelayed_id == id);
549 for (RoseVertex v : delayed_info.vertices) {
550 if (!isNoRunsVertex(build, v)) {
551 return false;
552 }
553 }
554 }
555
556 DEBUG_PRINTF("is no-runs literal\n");
557 return true;
558}
559
560static
561bool isNoRunsFragment(const RoseBuildImpl &build, const LitFragment &f,
562 const size_t max_len) {
563 // For the fragment to be marked "no runs", every literal it fires must
564 // need no further confirmation work.
565 return all_of_in(f.lit_ids, [&](u32 lit_id) {
566 const auto &info = build.literal_info.at(lit_id);
567 return isNoRunsLiteral(build, lit_id, info, max_len);
568 });
569}
570
571static
572const raw_puff &getChainedPuff(const RoseBuildImpl &build,
573 const Report &report) {
574 DEBUG_PRINTF("chained report, event %u\n", report.onmatch);
575
576 // MPV has already been moved to the outfixes vector.
577 assert(!build.mpv_outfix);
578
579 auto mpv_outfix_it = find_if(
580 begin(build.outfixes), end(build.outfixes),
581 [](const OutfixInfo &outfix) { return outfix.is_nonempty_mpv(); });
582 assert(mpv_outfix_it != end(build.outfixes));
583 const auto *mpv = mpv_outfix_it->mpv();
584
585 u32 puff_index = report.onmatch - MQE_TOP_FIRST;
586 assert(puff_index < mpv->triggered_puffettes.size());
587 return mpv->triggered_puffettes.at(puff_index);
588}
589
590/**
591 * \brief Returns a conservative estimate of the minimum offset at which the
592 * given literal can lead to a report.
593 *
594 * TODO: This could be made more precise by calculating a "distance to accept"
595 * for every vertex in the graph; right now we're only accurate for leaf nodes.
596 */
597static
598u64a literalMinReportOffset(const RoseBuildImpl &build,
599 const rose_literal_id &lit,
600 const rose_literal_info &info) {
601 const auto &g = build.g;
602
603 const u32 lit_len = verify_u32(lit.elength());
604
605 u64a lit_min_offset = UINT64_MAX;
606
607 for (const auto &v : info.vertices) {
608 DEBUG_PRINTF("vertex %zu min_offset=%u\n", g[v].index, g[v].min_offset);
609
610 u64a vert_offset = g[v].min_offset;
611
612 if (vert_offset >= lit_min_offset) {
613 continue;
614 }
615
616 u64a min_offset = UINT64_MAX;
617
618 for (const auto &id : g[v].reports) {
619 const Report &report = build.rm.getReport(id);
620 DEBUG_PRINTF("report id %u, min offset=%llu\n", id,
621 report.minOffset);
622 if (report.type == INTERNAL_ROSE_CHAIN) {
623 // This vertex triggers an MPV, which will fire reports after
624 // repeating for a while.
625 assert(report.minOffset == 0); // Should not have bounds.
626 const auto &puff = getChainedPuff(build, report);
627 DEBUG_PRINTF("chained puff repeats=%u\n", puff.repeats);
628 const Report &puff_report = build.rm.getReport(puff.report);
629 DEBUG_PRINTF("puff report %u, min offset=%llu\n", puff.report,
630 puff_report.minOffset);
631 min_offset = min(min_offset, max(vert_offset + puff.repeats,
632 puff_report.minOffset));
633 } else {
634 DEBUG_PRINTF("report min offset=%llu\n", report.minOffset);
635 min_offset = min(min_offset, max(vert_offset,
636 report.minOffset));
637 }
638 }
639
640 if (g[v].suffix) {
641 depth suffix_width = findMinWidth(g[v].suffix, g[v].suffix.top);
642 assert(suffix_width.is_reachable());
643 DEBUG_PRINTF("suffix with width %s\n", suffix_width.str().c_str());
644 min_offset = min(min_offset, vert_offset + suffix_width);
645 }
646
647 if (!isLeafNode(v, g) || min_offset == UINT64_MAX) {
648 min_offset = vert_offset;
649 }
650
651 lit_min_offset = min(lit_min_offset, min_offset);
652 }
653
654 // If this literal in the undelayed literal corresponding to some delayed
655 // literals, we must take their minimum offsets into account.
656 for (const u32 &delayed_id : info.delayed_ids) {
657 const auto &delayed_lit = build.literals.at(delayed_id);
658 const auto &delayed_info = build.literal_info.at(delayed_id);
659 u64a delayed_min_offset = literalMinReportOffset(build, delayed_lit,
660 delayed_info);
661 DEBUG_PRINTF("delayed_id=%u, min_offset = %llu\n", delayed_id,
662 delayed_min_offset);
663 lit_min_offset = min(lit_min_offset, delayed_min_offset);
664 }
665
666 // If we share a vertex with a shorter literal, our min offset might dip
667 // below the length of this one.
668 lit_min_offset = max(lit_min_offset, u64a{lit_len});
669
670 return lit_min_offset;
671}
672
673template<class Container>
674void trim_to_suffix(Container &c, size_t len) {
675 if (c.size() <= len) {
676 return;
677 }
678
679 size_t suffix_len = c.size() - len;
680 c.erase(c.begin(), c.begin() + suffix_len);
681}
682
683namespace {
684
685/** \brief Prototype for literal matcher construction. */
686struct MatcherProto {
687 /** \brief Literal fragments used to construct the literal matcher. */
688 vector<hwlmLiteral> lits;
689
690 /** \brief Longer literals used for acceleration analysis. */
691 vector<AccelString> accel_lits;
692
693 /** \brief The history required by the literal matcher. */
694 size_t history_required = 0;
695
696 /** \brief Insert the contents of another MatcherProto. */
697 void insert(const MatcherProto &a);
698};
699}
700
701static
702void addFragmentLiteral(const RoseBuildImpl &build, MatcherProto &mp,
703 const LitFragment &f, u32 id, size_t max_len) {
704 const rose_literal_id &lit = build.literals.at(id);
705
706 DEBUG_PRINTF("lit='%s' (len %zu)\n", dumpString(lit.s).c_str(),
707 lit.s.length());
708
709 vector<u8> msk = lit.msk; // copy
710 vector<u8> cmp = lit.cmp; // copy
711
712 bool noruns = isNoRunsFragment(build, f, max_len);
713 DEBUG_PRINTF("fragment is %s\n", noruns ? "noruns" : "not noruns");
714
715 auto lit_final = lit.s; // copy
716
717 if (lit_final.length() > ROSE_SHORT_LITERAL_LEN_MAX) {
718 DEBUG_PRINTF("truncating to tail of length %zu\n",
719 size_t{ROSE_SHORT_LITERAL_LEN_MAX});
720 lit_final.erase(0, lit_final.length() - ROSE_SHORT_LITERAL_LEN_MAX);
721 // We shouldn't have set a threshold below 8 chars.
722 assert(msk.size() <= ROSE_SHORT_LITERAL_LEN_MAX);
723 assert(!noruns);
724 }
725
726 addLiteralMask(lit, msk, cmp);
727
728 const auto &s_final = lit_final.get_string();
729 bool nocase = lit_final.any_nocase();
730 bool pure = f.s.get_pure();
731
732 DEBUG_PRINTF("id=%u, s='%s', nocase=%d, noruns=%d, msk=%s, cmp=%s\n",
733 f.fragment_id, escapeString(s_final).c_str(), (int)nocase,
734 noruns, dumpMask(msk).c_str(), dumpMask(cmp).c_str());
735
736 if (!maskIsConsistent(s_final, nocase, msk, cmp)) {
737 DEBUG_PRINTF("msk/cmp for literal can't match, skipping\n");
738 return;
739 }
740
741 const auto &groups = f.groups;
742
743 mp.lits.emplace_back(move(s_final), nocase, noruns, f.fragment_id,
744 groups, msk, cmp, pure);
745}
746
747static
748void addAccelLiteral(MatcherProto &mp, const rose_literal_id &lit,
749 const rose_literal_info &info, size_t max_len) {
750 const auto &s = lit.s; // copy
751
752 DEBUG_PRINTF("lit='%s' (len %zu)\n", dumpString(s).c_str(), s.length());
753
754 vector<u8> msk = lit.msk; // copy
755 vector<u8> cmp = lit.cmp; // copy
756 addLiteralMask(lit, msk, cmp);
757
758 if (!maskIsConsistent(s.get_string(), s.any_nocase(), msk, cmp)) {
759 DEBUG_PRINTF("msk/cmp for literal can't match, skipping\n");
760 return;
761 }
762
763 // Literals used for acceleration must be limited to max_len, as that's all
764 // we can see in history.
765 string s_final = lit.s.get_string();
766 trim_to_suffix(s_final, max_len);
767 trim_to_suffix(msk, max_len);
768 trim_to_suffix(cmp, max_len);
769
770 mp.accel_lits.emplace_back(s_final, lit.s.any_nocase(), msk, cmp,
771 info.group_mask);
772}
773
774/**
775 * \brief Build up a vector of literals (and associated other data) for the
776 * given table.
777 *
778 * If max_offset is specified (and not ROSE_BOUND_INF), then literals that can
779 * only lead to a pattern match after max_offset may be excluded.
780 */
781static
782MatcherProto makeMatcherProto(const RoseBuildImpl &build,
783 const vector<LitFragment> &fragments,
784 rose_literal_table table, bool delay_rebuild,
785 size_t max_len, u32 max_offset = ROSE_BOUND_INF) {
786 MatcherProto mp;
787
788 if (delay_rebuild) {
789 assert(table == ROSE_FLOATING);
790 assert(build.cc.streaming);
791 }
792
793 vector<u32> used_lit_ids;
794
795 for (const auto &f : fragments) {
796 assert(!f.lit_ids.empty());
797
798 // All literals that share a fragment are in the same table.
799 if (build.literals.at(f.lit_ids.front()).table != table) {
800 continue; // next fragment.
801 }
802
803 DEBUG_PRINTF("fragment %u, %zu lit_ids\n", f.fragment_id,
804 f.lit_ids.size());
805
806 used_lit_ids.clear();
807 for (u32 id : f.lit_ids) {
808 const rose_literal_id &lit = build.literals.at(id);
809 assert(id < build.literal_info.size());
810 const auto &info = build.literal_info.at(id);
811 if (lit.delay) {
812 continue; /* delay id's are virtual-ish */
813 }
814
815 // When building the delay rebuild table, we only want to include
816 // literals that have delayed variants.
817 if (delay_rebuild && info.delayed_ids.empty()) {
818 DEBUG_PRINTF("not needed for delay rebuild\n");
819 continue;
820 }
821
822 if (max_offset != ROSE_BOUND_INF) {
823 u64a min_report = literalMinReportOffset(build, lit, info);
824 if (min_report > max_offset) {
825 DEBUG_PRINTF("min report offset=%llu exceeds "
826 "max_offset=%u\n", min_report, max_offset);
827 continue;
828 }
829 }
830
831 used_lit_ids.push_back(id);
832 }
833
834 if (used_lit_ids.empty()) {
835 continue; // next fragment.
836 }
837
838 // Build our fragment (for the HWLM matcher) from the first literal.
839 addFragmentLiteral(build, mp, f, used_lit_ids.front(), max_len);
840
841 for (u32 id : used_lit_ids) {
842 const rose_literal_id &lit = build.literals.at(id);
843 assert(id < build.literal_info.size());
844 const auto &info = build.literal_info.at(id);
845
846 // All literals contribute accel information.
847 addAccelLiteral(mp, lit, info, max_len);
848
849 // All literals contribute to history requirement in streaming mode.
850 if (build.cc.streaming) {
851 size_t lit_hist_len =
852 max(lit.msk.size(), min(lit.s.length(), max_len));
853 lit_hist_len = lit_hist_len ? lit_hist_len - 1 : 0;
854 DEBUG_PRINTF("lit requires %zu bytes of history\n",
855 lit_hist_len);
856 assert(lit_hist_len <= build.cc.grey.maxHistoryAvailable);
857 mp.history_required = max(mp.history_required, lit_hist_len);
858 }
859 }
860 }
861
862 sort_and_unique(mp.lits);
863 sort_and_unique(mp.accel_lits);
864
865 return mp;
866}
867
868void MatcherProto::insert(const MatcherProto &a) {
869 ::ue2::insert(&lits, lits.end(), a.lits);
870 ::ue2::insert(&accel_lits, accel_lits.end(), a.accel_lits);
871 sort_and_unique(lits);
872 sort_and_unique(accel_lits);
873 history_required = max(history_required, a.history_required);
874}
875
876static
877void buildAccel(const RoseBuildImpl &build,
878 const vector<AccelString> &accel_lits, HWLM &hwlm) {
879 if (!build.cc.grey.hamsterAccelForward) {
880 return;
881 }
882
883 if (hwlm.type == HWLM_ENGINE_NOOD) {
884 return;
885 }
886
887 buildForwardAccel(&hwlm, accel_lits, build.getInitialGroups());
888}
889
890bytecode_ptr<HWLM>
891buildHWLMMatcher(const RoseBuildImpl &build, LitProto *litProto) {
892 if (!litProto) {
893 return nullptr;
894 }
895 auto hwlm = hwlmBuild(*litProto->hwlmProto, build.cc,
896 build.getInitialGroups());
897 if (!hwlm) {
898 throw CompileError("Unable to generate bytecode.");
899 }
900
901 buildAccel(build, litProto->accel_lits, *hwlm);
902
903 DEBUG_PRINTF("built eod-anchored literal table size %zu bytes\n",
904 hwlm.size());
905 return hwlm;
906}
907
908unique_ptr<LitProto>
909buildFloatingMatcherProto(const RoseBuildImpl &build,
910 const vector<LitFragment> &fragments,
911 size_t longLitLengthThreshold,
912 rose_group *fgroups,
913 size_t *historyRequired) {
914 DEBUG_PRINTF("Floating literal matcher\n");
915 *fgroups = 0;
916
917 auto mp = makeMatcherProto(build, fragments, ROSE_FLOATING, false,
918 longLitLengthThreshold);
919 if (mp.lits.empty()) {
920 DEBUG_PRINTF("empty floating matcher\n");
921 return nullptr;
922 }
923 dumpMatcherLiterals(mp.lits, "floating", build.cc.grey);
924
925 for (const hwlmLiteral &lit : mp.lits) {
926 *fgroups |= lit.groups;
927 }
928
929 if (build.cc.streaming) {
930 DEBUG_PRINTF("history_required=%zu\n", mp.history_required);
931 assert(mp.history_required <= build.cc.grey.maxHistoryAvailable);
932 *historyRequired = max(*historyRequired, mp.history_required);
933 }
934
935 auto proto = hwlmBuildProto(mp.lits, false, build.cc);
936
937 if (!proto) {
938 throw CompileError("Unable to generate literal matcher proto.");
939 }
940
941 return ue2::make_unique<LitProto>(move(proto), mp.accel_lits);
942}
943
944unique_ptr<LitProto>
945buildDelayRebuildMatcherProto(const RoseBuildImpl &build,
946 const vector<LitFragment> &fragments,
947 size_t longLitLengthThreshold) {
948 DEBUG_PRINTF("Delay literal matcher\n");
949 if (!build.cc.streaming) {
950 DEBUG_PRINTF("not streaming\n");
951 return nullptr;
952 }
953
954 auto mp = makeMatcherProto(build, fragments, ROSE_FLOATING, true,
955 longLitLengthThreshold);
956 if (mp.lits.empty()) {
957 DEBUG_PRINTF("empty delay rebuild matcher\n");
958 return nullptr;
959 }
960 dumpMatcherLiterals(mp.lits, "delay_rebuild", build.cc.grey);
961
962
963 auto proto = hwlmBuildProto(mp.lits, false, build.cc);
964
965 if (!proto) {
966 throw CompileError("Unable to generate literal matcher proto.");
967 }
968
969 return ue2::make_unique<LitProto>(move(proto), mp.accel_lits);
970}
971
972unique_ptr<LitProto>
973buildSmallBlockMatcherProto(const RoseBuildImpl &build,
974 const vector<LitFragment> &fragments) {
975 DEBUG_PRINTF("Small block literal matcher\n");
976 if (build.cc.streaming) {
977 DEBUG_PRINTF("streaming mode\n");
978 return nullptr;
979 }
980
981 u32 float_min = findMinWidth(build, ROSE_FLOATING);
982 if (float_min > ROSE_SMALL_BLOCK_LEN) {
983 DEBUG_PRINTF("floating table has large min width %u, fail\n",
984 float_min);
985 return nullptr;
986 }
987
988 auto mp = makeMatcherProto(build, fragments, ROSE_FLOATING, false,
989 ROSE_SMALL_BLOCK_LEN, ROSE_SMALL_BLOCK_LEN);
990 if (mp.lits.empty()) {
991 DEBUG_PRINTF("no floating table\n");
992 return nullptr;
993 } else if (mp.lits.size() == 1) {
994 DEBUG_PRINTF("single floating literal, noodle will be fast enough\n");
995 return nullptr;
996 }
997
998 auto mp_anchored = makeMatcherProto(build, fragments,
999 ROSE_ANCHORED_SMALL_BLOCK, false,
1000 ROSE_SMALL_BLOCK_LEN,
1001 ROSE_SMALL_BLOCK_LEN);
1002 if (mp_anchored.lits.empty()) {
1003 DEBUG_PRINTF("no small-block anchored literals\n");
1004 return nullptr;
1005 }
1006
1007 mp.insert(mp_anchored);
1008 dumpMatcherLiterals(mp.lits, "smallblock", build.cc.grey);
1009
1010 // None of our literals should be longer than the small block limit.
1011 assert(all_of(begin(mp.lits), end(mp.lits), [](const hwlmLiteral &lit) {
1012 return lit.s.length() <= ROSE_SMALL_BLOCK_LEN;
1013 }));
1014
1015 if (mp.lits.empty()) {
1016 DEBUG_PRINTF("no literals shorter than small block len\n");
1017 return nullptr;
1018 }
1019
1020 auto proto = hwlmBuildProto(mp.lits, false, build.cc);
1021
1022 if (!proto) {
1023 throw CompileError("Unable to generate literal matcher proto.");
1024 }
1025
1026 return ue2::make_unique<LitProto>(move(proto), mp.accel_lits);
1027}
1028
1029unique_ptr<LitProto>
1030buildEodAnchoredMatcherProto(const RoseBuildImpl &build,
1031 const vector<LitFragment> &fragments) {
1032 DEBUG_PRINTF("Eod anchored literal matcher\n");
1033 auto mp = makeMatcherProto(build, fragments, ROSE_EOD_ANCHORED, false,
1034 build.ematcher_region_size);
1035
1036 if (mp.lits.empty()) {
1037 DEBUG_PRINTF("no eod anchored literals\n");
1038 assert(!build.ematcher_region_size);
1039 return nullptr;
1040 }
1041 dumpMatcherLiterals(mp.lits, "eod", build.cc.grey);
1042
1043 assert(build.ematcher_region_size);
1044
1045 auto proto = hwlmBuildProto(mp.lits, false, build.cc);
1046
1047 if (!proto) {
1048 throw CompileError("Unable to generate literal matcher proto.");
1049 }
1050
1051 return ue2::make_unique<LitProto>(move(proto), mp.accel_lits);
1052}
1053
1054} // namespace ue2
1055