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 | |
61 | using namespace std; |
62 | using boost::adaptors::map_values; |
63 | |
64 | namespace ue2 { |
65 | |
66 | static const size_t MAX_ACCEL_STRING_LEN = 16; |
67 | |
68 | #if defined(DEBUG) || defined(DUMP_SUPPORT) |
69 | static UNUSED |
70 | string 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 | |
79 | static |
80 | bool 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 | |
126 | static |
127 | bool 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 | |
161 | static |
162 | bool 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 | |
177 | static |
178 | bool 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 | |
235 | static |
236 | bool 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 | |
260 | static |
261 | bool 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 | |
281 | static |
282 | bool 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 | |
332 | void 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. |
396 | static |
397 | void 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 | |
439 | static |
440 | bool 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. |
464 | static |
465 | bool 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 | |
511 | static |
512 | bool 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 | |
560 | static |
561 | bool 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 | |
571 | static |
572 | const 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 | */ |
597 | static |
598 | u64a 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 | |
673 | template<class Container> |
674 | void 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 | |
683 | namespace { |
684 | |
685 | /** \brief Prototype for literal matcher construction. */ |
686 | struct 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 | |
701 | static |
702 | void 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 | |
747 | static |
748 | void 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 | */ |
781 | static |
782 | MatcherProto 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 | |
868 | void 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 | |
876 | static |
877 | void 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 | |
890 | bytecode_ptr<HWLM> |
891 | buildHWLMMatcher(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 | |
908 | unique_ptr<LitProto> |
909 | buildFloatingMatcherProto(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 | |
944 | unique_ptr<LitProto> |
945 | buildDelayRebuildMatcherProto(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 | |
972 | unique_ptr<LitProto> |
973 | buildSmallBlockMatcherProto(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 | |
1029 | unique_ptr<LitProto> |
1030 | buildEodAnchoredMatcherProto(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 | |