RegexOptimizer.cpp 38 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930
  1. /*
  2. * Copyright (c) 2021, Ali Mohammad Pur <mpfard@serenityos.org>
  3. *
  4. * SPDX-License-Identifier: BSD-2-Clause
  5. */
  6. #include <AK/QuickSort.h>
  7. #include <AK/RedBlackTree.h>
  8. #include <AK/Stack.h>
  9. #include <LibRegex/Regex.h>
  10. #include <LibRegex/RegexBytecodeStreamOptimizer.h>
  11. #if REGEX_DEBUG
  12. # include <AK/ScopeGuard.h>
  13. # include <AK/ScopeLogger.h>
  14. #endif
  15. namespace regex {
  16. using Detail::Block;
  17. template<typename Parser>
  18. void Regex<Parser>::run_optimization_passes()
  19. {
  20. parser_result.bytecode.flatten();
  21. // Rewrite fork loops as atomic groups
  22. // e.g. a*b -> (ATOMIC a*)b
  23. attempt_rewrite_loops_as_atomic_groups(split_basic_blocks(parser_result.bytecode));
  24. parser_result.bytecode.flatten();
  25. }
  26. template<typename Parser>
  27. typename Regex<Parser>::BasicBlockList Regex<Parser>::split_basic_blocks(ByteCode const& bytecode)
  28. {
  29. BasicBlockList block_boundaries;
  30. size_t end_of_last_block = 0;
  31. auto bytecode_size = bytecode.size();
  32. MatchState state;
  33. state.instruction_position = 0;
  34. auto check_jump = [&]<typename T>(OpCode const& opcode) {
  35. auto& op = static_cast<T const&>(opcode);
  36. ssize_t jump_offset = op.size() + op.offset();
  37. if (jump_offset >= 0) {
  38. block_boundaries.append({ end_of_last_block, state.instruction_position });
  39. end_of_last_block = state.instruction_position + opcode.size();
  40. } else {
  41. // This op jumps back, see if that's within this "block".
  42. if (jump_offset + state.instruction_position > end_of_last_block) {
  43. // Split the block!
  44. block_boundaries.append({ end_of_last_block, jump_offset + state.instruction_position });
  45. block_boundaries.append({ jump_offset + state.instruction_position, state.instruction_position });
  46. end_of_last_block = state.instruction_position + opcode.size();
  47. } else {
  48. // Nope, it's just a jump to another block
  49. block_boundaries.append({ end_of_last_block, state.instruction_position });
  50. end_of_last_block = state.instruction_position + opcode.size();
  51. }
  52. }
  53. };
  54. for (;;) {
  55. auto& opcode = bytecode.get_opcode(state);
  56. switch (opcode.opcode_id()) {
  57. case OpCodeId::Jump:
  58. check_jump.template operator()<OpCode_Jump>(opcode);
  59. break;
  60. case OpCodeId::JumpNonEmpty:
  61. check_jump.template operator()<OpCode_JumpNonEmpty>(opcode);
  62. break;
  63. case OpCodeId::ForkJump:
  64. check_jump.template operator()<OpCode_ForkJump>(opcode);
  65. break;
  66. case OpCodeId::ForkStay:
  67. check_jump.template operator()<OpCode_ForkStay>(opcode);
  68. break;
  69. case OpCodeId::FailForks:
  70. block_boundaries.append({ end_of_last_block, state.instruction_position });
  71. end_of_last_block = state.instruction_position + opcode.size();
  72. break;
  73. case OpCodeId::Repeat: {
  74. // Repeat produces two blocks, one containing its repeated expr, and one after that.
  75. auto repeat_start = state.instruction_position - static_cast<OpCode_Repeat const&>(opcode).offset();
  76. if (repeat_start > end_of_last_block)
  77. block_boundaries.append({ end_of_last_block, repeat_start });
  78. block_boundaries.append({ repeat_start, state.instruction_position });
  79. end_of_last_block = state.instruction_position + opcode.size();
  80. break;
  81. }
  82. default:
  83. break;
  84. }
  85. auto next_ip = state.instruction_position + opcode.size();
  86. if (next_ip < bytecode_size)
  87. state.instruction_position = next_ip;
  88. else
  89. break;
  90. }
  91. if (end_of_last_block < bytecode_size)
  92. block_boundaries.append({ end_of_last_block, bytecode_size });
  93. quick_sort(block_boundaries, [](auto& a, auto& b) { return a.start < b.start; });
  94. return block_boundaries;
  95. }
  96. static bool has_overlap(Vector<CompareTypeAndValuePair> const& lhs, Vector<CompareTypeAndValuePair> const& rhs)
  97. {
  98. // We have to fully interpret the two sequences to determine if they overlap (that is, keep track of inversion state and what ranges they cover).
  99. bool inverse { false };
  100. bool temporary_inverse { false };
  101. bool reset_temporary_inverse { false };
  102. auto current_lhs_inversion_state = [&]() -> bool { return temporary_inverse ^ inverse; };
  103. RedBlackTree<u32, u32> lhs_ranges;
  104. RedBlackTree<u32, u32> lhs_negated_ranges;
  105. HashTable<CharClass> lhs_char_classes;
  106. HashTable<CharClass> lhs_negated_char_classes;
  107. auto range_contains = [&]<typename T>(T& value) -> bool {
  108. u32 start;
  109. u32 end;
  110. if constexpr (IsSame<T, CharRange>) {
  111. start = value.from;
  112. end = value.to;
  113. } else {
  114. start = value;
  115. end = value;
  116. }
  117. auto* max = lhs_ranges.find_smallest_not_below(start);
  118. return max && *max <= end;
  119. };
  120. auto char_class_contains = [&](CharClass const& value) -> bool {
  121. if (lhs_char_classes.contains(value))
  122. return true;
  123. if (lhs_negated_char_classes.contains(value))
  124. return false;
  125. // This char class might match something in the ranges we have, and checking that is far too expensive, so just bail out.
  126. return true;
  127. };
  128. for (auto const& pair : lhs) {
  129. if (reset_temporary_inverse) {
  130. reset_temporary_inverse = false;
  131. temporary_inverse = false;
  132. } else {
  133. reset_temporary_inverse = true;
  134. }
  135. switch (pair.type) {
  136. case CharacterCompareType::Inverse:
  137. inverse = !inverse;
  138. break;
  139. case CharacterCompareType::TemporaryInverse:
  140. temporary_inverse = !temporary_inverse;
  141. break;
  142. case CharacterCompareType::AnyChar:
  143. // Special case: if not inverted, AnyChar is always in the range.
  144. if (!current_lhs_inversion_state())
  145. return true;
  146. break;
  147. case CharacterCompareType::Char:
  148. if (!current_lhs_inversion_state())
  149. lhs_ranges.insert(pair.value, pair.value);
  150. else
  151. lhs_negated_ranges.insert(pair.value, pair.value);
  152. break;
  153. case CharacterCompareType::String:
  154. // FIXME: We just need to look at the last character of this string, but we only have the first character here.
  155. // Just bail out to avoid false positives.
  156. return true;
  157. case CharacterCompareType::CharClass:
  158. if (!current_lhs_inversion_state())
  159. lhs_char_classes.set(static_cast<CharClass>(pair.value));
  160. else
  161. lhs_negated_char_classes.set(static_cast<CharClass>(pair.value));
  162. break;
  163. case CharacterCompareType::CharRange: {
  164. auto range = CharRange(pair.value);
  165. if (!current_lhs_inversion_state())
  166. lhs_ranges.insert(range.from, range.to);
  167. else
  168. lhs_negated_ranges.insert(range.from, range.to);
  169. break;
  170. }
  171. case CharacterCompareType::LookupTable:
  172. // We've transformed this into a series of ranges in flat_compares(), so bail out if we see it.
  173. return true;
  174. case CharacterCompareType::Reference:
  175. // We've handled this before coming here.
  176. break;
  177. case CharacterCompareType::Property:
  178. case CharacterCompareType::GeneralCategory:
  179. case CharacterCompareType::Script:
  180. case CharacterCompareType::ScriptExtension:
  181. // FIXME: These are too difficult to handle, so bail out.
  182. return true;
  183. case CharacterCompareType::Undefined:
  184. case CharacterCompareType::RangeExpressionDummy:
  185. // These do not occur in valid bytecode.
  186. VERIFY_NOT_REACHED();
  187. }
  188. }
  189. if constexpr (REGEX_DEBUG) {
  190. dbgln("lhs ranges:");
  191. for (auto it = lhs_ranges.begin(); it != lhs_ranges.end(); ++it)
  192. dbgln(" {}..{}", it.key(), *it);
  193. dbgln("lhs negated ranges:");
  194. for (auto it = lhs_negated_ranges.begin(); it != lhs_negated_ranges.end(); ++it)
  195. dbgln(" {}..{}", it.key(), *it);
  196. }
  197. for (auto const& pair : rhs) {
  198. if (reset_temporary_inverse) {
  199. reset_temporary_inverse = false;
  200. temporary_inverse = false;
  201. } else {
  202. reset_temporary_inverse = true;
  203. }
  204. dbgln_if(REGEX_DEBUG, "check {} ({})...", character_compare_type_name(pair.type), pair.value);
  205. switch (pair.type) {
  206. case CharacterCompareType::Inverse:
  207. inverse = !inverse;
  208. break;
  209. case CharacterCompareType::TemporaryInverse:
  210. temporary_inverse = !temporary_inverse;
  211. break;
  212. case CharacterCompareType::AnyChar:
  213. // Special case: if not inverted, AnyChar is always in the range.
  214. if (!current_lhs_inversion_state())
  215. return true;
  216. break;
  217. case CharacterCompareType::Char:
  218. if (!current_lhs_inversion_state() && range_contains(pair.value))
  219. return true;
  220. break;
  221. case CharacterCompareType::String:
  222. // FIXME: We just need to look at the last character of this string, but we only have the first character here.
  223. // Just bail out to avoid false positives.
  224. return true;
  225. case CharacterCompareType::CharClass:
  226. if (!current_lhs_inversion_state() && char_class_contains(static_cast<CharClass>(pair.value)))
  227. return true;
  228. break;
  229. case CharacterCompareType::CharRange: {
  230. auto range = CharRange(pair.value);
  231. if (!current_lhs_inversion_state() && range_contains(range))
  232. return true;
  233. break;
  234. }
  235. case CharacterCompareType::LookupTable:
  236. // We've transformed this into a series of ranges in flat_compares(), so bail out if we see it.
  237. return true;
  238. case CharacterCompareType::Reference:
  239. // We've handled this before coming here.
  240. break;
  241. case CharacterCompareType::Property:
  242. case CharacterCompareType::GeneralCategory:
  243. case CharacterCompareType::Script:
  244. case CharacterCompareType::ScriptExtension:
  245. // FIXME: These are too difficult to handle, so bail out.
  246. return true;
  247. case CharacterCompareType::Undefined:
  248. case CharacterCompareType::RangeExpressionDummy:
  249. // These do not occur in valid bytecode.
  250. VERIFY_NOT_REACHED();
  251. }
  252. }
  253. return false;
  254. }
  255. enum class AtomicRewritePreconditionResult {
  256. SatisfiedWithProperHeader,
  257. SatisfiedWithEmptyHeader,
  258. NotSatisfied,
  259. };
  260. static AtomicRewritePreconditionResult block_satisfies_atomic_rewrite_precondition(ByteCode const& bytecode, Block const& repeated_block, Block const& following_block)
  261. {
  262. Vector<Vector<CompareTypeAndValuePair>> repeated_values;
  263. HashTable<size_t> active_capture_groups;
  264. MatchState state;
  265. for (state.instruction_position = repeated_block.start; state.instruction_position < repeated_block.end;) {
  266. auto& opcode = bytecode.get_opcode(state);
  267. switch (opcode.opcode_id()) {
  268. case OpCodeId::Compare: {
  269. auto compares = static_cast<OpCode_Compare const&>(opcode).flat_compares();
  270. if (repeated_values.is_empty() && any_of(compares, [](auto& compare) { return compare.type == CharacterCompareType::AnyChar; }))
  271. return AtomicRewritePreconditionResult::NotSatisfied;
  272. repeated_values.append(move(compares));
  273. break;
  274. }
  275. case OpCodeId::CheckBegin:
  276. case OpCodeId::CheckEnd:
  277. if (repeated_values.is_empty())
  278. return AtomicRewritePreconditionResult::SatisfiedWithProperHeader;
  279. break;
  280. case OpCodeId::CheckBoundary:
  281. // FIXME: What should we do with these? for now, let's fail.
  282. return AtomicRewritePreconditionResult::NotSatisfied;
  283. case OpCodeId::Restore:
  284. case OpCodeId::GoBack:
  285. return AtomicRewritePreconditionResult::NotSatisfied;
  286. case OpCodeId::SaveRightCaptureGroup:
  287. active_capture_groups.set(static_cast<OpCode_SaveRightCaptureGroup const&>(opcode).id());
  288. break;
  289. case OpCodeId::SaveLeftCaptureGroup:
  290. active_capture_groups.set(static_cast<OpCode_SaveLeftCaptureGroup const&>(opcode).id());
  291. break;
  292. default:
  293. break;
  294. }
  295. state.instruction_position += opcode.size();
  296. }
  297. dbgln_if(REGEX_DEBUG, "Found {} entries in reference", repeated_values.size());
  298. dbgln_if(REGEX_DEBUG, "Found {} active capture groups", active_capture_groups.size());
  299. bool following_block_has_at_least_one_compare = false;
  300. // Find the first compare in the following block, it must NOT match any of the values in `repeated_values'.
  301. for (state.instruction_position = following_block.start; state.instruction_position < following_block.end;) {
  302. auto& opcode = bytecode.get_opcode(state);
  303. switch (opcode.opcode_id()) {
  304. // Note: These have to exist since we're effectively repeating the following block as well
  305. case OpCodeId::SaveRightCaptureGroup:
  306. active_capture_groups.set(static_cast<OpCode_SaveRightCaptureGroup const&>(opcode).id());
  307. break;
  308. case OpCodeId::SaveLeftCaptureGroup:
  309. active_capture_groups.set(static_cast<OpCode_SaveLeftCaptureGroup const&>(opcode).id());
  310. break;
  311. case OpCodeId::Compare: {
  312. following_block_has_at_least_one_compare = true;
  313. // We found a compare, let's see what it has.
  314. auto compares = static_cast<OpCode_Compare const&>(opcode).flat_compares();
  315. if (compares.is_empty())
  316. break;
  317. if (any_of(compares, [&](auto& compare) {
  318. return compare.type == CharacterCompareType::AnyChar
  319. || (compare.type == CharacterCompareType::Reference && active_capture_groups.contains(compare.value));
  320. }))
  321. return AtomicRewritePreconditionResult::NotSatisfied;
  322. if (any_of(repeated_values, [&](auto& repeated_value) { return has_overlap(compares, repeated_value); }))
  323. return AtomicRewritePreconditionResult::NotSatisfied;
  324. return AtomicRewritePreconditionResult::SatisfiedWithProperHeader;
  325. }
  326. case OpCodeId::CheckBegin:
  327. case OpCodeId::CheckEnd:
  328. return AtomicRewritePreconditionResult::SatisfiedWithProperHeader; // Nothing can match the end!
  329. case OpCodeId::CheckBoundary:
  330. // FIXME: What should we do with these? For now, consider them a failure.
  331. return AtomicRewritePreconditionResult::NotSatisfied;
  332. default:
  333. break;
  334. }
  335. state.instruction_position += opcode.size();
  336. }
  337. if (following_block_has_at_least_one_compare)
  338. return AtomicRewritePreconditionResult::SatisfiedWithProperHeader;
  339. return AtomicRewritePreconditionResult::SatisfiedWithEmptyHeader;
  340. }
  341. template<typename Parser>
  342. void Regex<Parser>::attempt_rewrite_loops_as_atomic_groups(BasicBlockList const& basic_blocks)
  343. {
  344. auto& bytecode = parser_result.bytecode;
  345. if constexpr (REGEX_DEBUG) {
  346. RegexDebug dbg;
  347. dbg.print_bytecode(*this);
  348. for (auto const& block : basic_blocks)
  349. dbgln("block from {} to {}", block.start, block.end);
  350. }
  351. // A pattern such as:
  352. // bb0 | RE0
  353. // | ForkX bb0
  354. // -------------------------
  355. // bb1 | RE1
  356. // can be rewritten as:
  357. // -------------------------
  358. // bb0 | RE0
  359. // | ForkReplaceX bb0
  360. // -------------------------
  361. // bb1 | RE1
  362. // provided that first(RE1) not-in end(RE0), which is to say
  363. // that RE1 cannot start with whatever RE0 has matched (ever).
  364. //
  365. // Alternatively, a second form of this pattern can also occur:
  366. // bb0 | *
  367. // | ForkX bb2
  368. // ------------------------
  369. // bb1 | RE0
  370. // | Jump bb0
  371. // ------------------------
  372. // bb2 | RE1
  373. // which can be transformed (with the same preconditions) to:
  374. // bb0 | *
  375. // | ForkReplaceX bb2
  376. // ------------------------
  377. // bb1 | RE0
  378. // | Jump bb0
  379. // ------------------------
  380. // bb2 | RE1
  381. enum class AlternateForm {
  382. DirectLoopWithoutHeader, // loop without proper header, a block forking to itself. i.e. the first form.
  383. DirectLoopWithoutHeaderAndEmptyFollow, // loop without proper header, a block forking to itself. i.e. the first form but with RE1 being empty.
  384. DirectLoopWithHeader, // loop with proper header, i.e. the second form.
  385. };
  386. struct CandidateBlock {
  387. Block forking_block;
  388. Optional<Block> new_target_block;
  389. AlternateForm form;
  390. };
  391. Vector<CandidateBlock> candidate_blocks;
  392. auto is_an_eligible_jump = [](OpCode const& opcode, size_t ip, size_t block_start, AlternateForm alternate_form) {
  393. switch (opcode.opcode_id()) {
  394. case OpCodeId::JumpNonEmpty: {
  395. auto const& op = static_cast<OpCode_JumpNonEmpty const&>(opcode);
  396. auto form = op.form();
  397. if (form != OpCodeId::Jump && alternate_form == AlternateForm::DirectLoopWithHeader)
  398. return false;
  399. if (form != OpCodeId::ForkJump && form != OpCodeId::ForkStay && alternate_form == AlternateForm::DirectLoopWithoutHeader)
  400. return false;
  401. return op.offset() + ip + opcode.size() == block_start;
  402. }
  403. case OpCodeId::ForkJump:
  404. if (alternate_form == AlternateForm::DirectLoopWithHeader)
  405. return false;
  406. return static_cast<OpCode_ForkJump const&>(opcode).offset() + ip + opcode.size() == block_start;
  407. case OpCodeId::ForkStay:
  408. if (alternate_form == AlternateForm::DirectLoopWithHeader)
  409. return false;
  410. return static_cast<OpCode_ForkStay const&>(opcode).offset() + ip + opcode.size() == block_start;
  411. case OpCodeId::Jump:
  412. // Infinite loop does *not* produce forks.
  413. if (alternate_form == AlternateForm::DirectLoopWithoutHeader)
  414. return false;
  415. if (alternate_form == AlternateForm::DirectLoopWithHeader)
  416. return static_cast<OpCode_Jump const&>(opcode).offset() + ip + opcode.size() == block_start;
  417. VERIFY_NOT_REACHED();
  418. default:
  419. return false;
  420. }
  421. };
  422. for (size_t i = 0; i < basic_blocks.size(); ++i) {
  423. auto forking_block = basic_blocks[i];
  424. Optional<Block> fork_fallback_block;
  425. if (i + 1 < basic_blocks.size())
  426. fork_fallback_block = basic_blocks[i + 1];
  427. MatchState state;
  428. // Check if the last instruction in this block is a jump to the block itself:
  429. {
  430. state.instruction_position = forking_block.end;
  431. auto& opcode = bytecode.get_opcode(state);
  432. if (is_an_eligible_jump(opcode, state.instruction_position, forking_block.start, AlternateForm::DirectLoopWithoutHeader)) {
  433. // We've found RE0 (and RE1 is just the following block, if any), let's see if the precondition applies.
  434. // if RE1 is empty, there's no first(RE1), so this is an automatic pass.
  435. if (!fork_fallback_block.has_value() || fork_fallback_block->end == fork_fallback_block->start) {
  436. candidate_blocks.append({ forking_block, fork_fallback_block, AlternateForm::DirectLoopWithoutHeader });
  437. break;
  438. }
  439. auto precondition = block_satisfies_atomic_rewrite_precondition(bytecode, forking_block, *fork_fallback_block);
  440. if (precondition == AtomicRewritePreconditionResult::SatisfiedWithProperHeader) {
  441. candidate_blocks.append({ forking_block, fork_fallback_block, AlternateForm::DirectLoopWithoutHeader });
  442. break;
  443. }
  444. if (precondition == AtomicRewritePreconditionResult::SatisfiedWithEmptyHeader) {
  445. candidate_blocks.append({ forking_block, fork_fallback_block, AlternateForm::DirectLoopWithoutHeaderAndEmptyFollow });
  446. break;
  447. }
  448. }
  449. }
  450. // Check if the last instruction in the last block is a direct jump to this block
  451. if (fork_fallback_block.has_value()) {
  452. state.instruction_position = fork_fallback_block->end;
  453. auto& opcode = bytecode.get_opcode(state);
  454. if (is_an_eligible_jump(opcode, state.instruction_position, forking_block.start, AlternateForm::DirectLoopWithHeader)) {
  455. // We've found bb1 and bb0, let's just make sure that bb0 forks to bb2.
  456. state.instruction_position = forking_block.end;
  457. auto& opcode = bytecode.get_opcode(state);
  458. if (opcode.opcode_id() == OpCodeId::ForkJump || opcode.opcode_id() == OpCodeId::ForkStay) {
  459. Optional<Block> block_following_fork_fallback;
  460. if (i + 2 < basic_blocks.size())
  461. block_following_fork_fallback = basic_blocks[i + 2];
  462. if (!block_following_fork_fallback.has_value()
  463. || block_satisfies_atomic_rewrite_precondition(bytecode, *fork_fallback_block, *block_following_fork_fallback) != AtomicRewritePreconditionResult::NotSatisfied) {
  464. candidate_blocks.append({ forking_block, {}, AlternateForm::DirectLoopWithHeader });
  465. break;
  466. }
  467. }
  468. }
  469. }
  470. }
  471. dbgln_if(REGEX_DEBUG, "Found {} candidate blocks", candidate_blocks.size());
  472. if (candidate_blocks.is_empty()) {
  473. dbgln_if(REGEX_DEBUG, "Failed to find anything for {}", pattern_value);
  474. return;
  475. }
  476. RedBlackTree<size_t, size_t> needed_patches;
  477. // Reverse the blocks, so we can patch the bytecode without messing with the latter patches.
  478. quick_sort(candidate_blocks, [](auto& a, auto& b) { return b.forking_block.start > a.forking_block.start; });
  479. for (auto& candidate : candidate_blocks) {
  480. // Note that both forms share a ForkReplace patch in forking_block.
  481. // Patch the ForkX in forking_block to be a ForkReplaceX instead.
  482. auto& opcode_id = bytecode[candidate.forking_block.end];
  483. if (opcode_id == (ByteCodeValueType)OpCodeId::ForkStay) {
  484. opcode_id = (ByteCodeValueType)OpCodeId::ForkReplaceStay;
  485. } else if (opcode_id == (ByteCodeValueType)OpCodeId::ForkJump) {
  486. opcode_id = (ByteCodeValueType)OpCodeId::ForkReplaceJump;
  487. } else if (opcode_id == (ByteCodeValueType)OpCodeId::JumpNonEmpty) {
  488. auto& jump_opcode_id = bytecode[candidate.forking_block.end + 3];
  489. if (jump_opcode_id == (ByteCodeValueType)OpCodeId::ForkStay)
  490. jump_opcode_id = (ByteCodeValueType)OpCodeId::ForkReplaceStay;
  491. else if (jump_opcode_id == (ByteCodeValueType)OpCodeId::ForkJump)
  492. jump_opcode_id = (ByteCodeValueType)OpCodeId::ForkReplaceJump;
  493. else
  494. VERIFY_NOT_REACHED();
  495. } else {
  496. VERIFY_NOT_REACHED();
  497. }
  498. }
  499. if (!needed_patches.is_empty()) {
  500. MatchState state;
  501. auto bytecode_size = bytecode.size();
  502. state.instruction_position = 0;
  503. struct Patch {
  504. ssize_t value;
  505. size_t offset;
  506. bool should_negate { false };
  507. };
  508. for (;;) {
  509. if (state.instruction_position >= bytecode_size)
  510. break;
  511. auto& opcode = bytecode.get_opcode(state);
  512. Stack<Patch, 2> patch_points;
  513. switch (opcode.opcode_id()) {
  514. case OpCodeId::Jump:
  515. patch_points.push({ static_cast<OpCode_Jump const&>(opcode).offset(), state.instruction_position + 1 });
  516. break;
  517. case OpCodeId::JumpNonEmpty:
  518. patch_points.push({ static_cast<OpCode_JumpNonEmpty const&>(opcode).offset(), state.instruction_position + 1 });
  519. patch_points.push({ static_cast<OpCode_JumpNonEmpty const&>(opcode).checkpoint(), state.instruction_position + 2 });
  520. break;
  521. case OpCodeId::ForkJump:
  522. patch_points.push({ static_cast<OpCode_ForkJump const&>(opcode).offset(), state.instruction_position + 1 });
  523. break;
  524. case OpCodeId::ForkStay:
  525. patch_points.push({ static_cast<OpCode_ForkStay const&>(opcode).offset(), state.instruction_position + 1 });
  526. break;
  527. case OpCodeId::Repeat:
  528. patch_points.push({ -(ssize_t) static_cast<OpCode_Repeat const&>(opcode).offset(), state.instruction_position + 1, true });
  529. break;
  530. default:
  531. break;
  532. }
  533. while (!patch_points.is_empty()) {
  534. auto& patch_point = patch_points.top();
  535. auto target_offset = patch_point.value + state.instruction_position + opcode.size();
  536. constexpr auto do_patch = [](auto& patch_it, auto& patch_point, auto& target_offset, auto& bytecode, auto ip) {
  537. if (patch_it.key() == ip)
  538. return;
  539. if (patch_point.value < 0 && target_offset <= patch_it.key() && ip > patch_it.key())
  540. bytecode[patch_point.offset] += (patch_point.should_negate ? 1 : -1) * (*patch_it);
  541. else if (patch_point.value > 0 && target_offset >= patch_it.key() && ip < patch_it.key())
  542. bytecode[patch_point.offset] += (patch_point.should_negate ? -1 : 1) * (*patch_it);
  543. };
  544. if (auto patch_it = needed_patches.find_largest_not_above_iterator(target_offset); !patch_it.is_end())
  545. do_patch(patch_it, patch_point, target_offset, bytecode, state.instruction_position);
  546. else if (auto patch_it = needed_patches.find_largest_not_above_iterator(state.instruction_position); !patch_it.is_end())
  547. do_patch(patch_it, patch_point, target_offset, bytecode, state.instruction_position);
  548. patch_points.pop();
  549. }
  550. state.instruction_position += opcode.size();
  551. }
  552. }
  553. if constexpr (REGEX_DEBUG) {
  554. warnln("Transformed to:");
  555. RegexDebug dbg;
  556. dbg.print_bytecode(*this);
  557. }
  558. }
  559. void Optimizer::append_alternation(ByteCode& target, ByteCode&& left, ByteCode&& right)
  560. {
  561. Array<ByteCode, 2> alternatives;
  562. alternatives[0] = move(left);
  563. alternatives[1] = move(right);
  564. append_alternation(target, alternatives);
  565. }
  566. void Optimizer::append_alternation(ByteCode& target, Span<ByteCode> alternatives)
  567. {
  568. if (alternatives.size() == 0)
  569. return;
  570. if (alternatives.size() == 1)
  571. return target.extend(move(alternatives[0]));
  572. if (all_of(alternatives, [](auto& x) { return x.is_empty(); }))
  573. return;
  574. for (auto& entry : alternatives)
  575. entry.flatten();
  576. #if REGEX_DEBUG
  577. ScopeLogger<true> log;
  578. warnln("Alternations:");
  579. RegexDebug dbg;
  580. for (auto& entry : alternatives) {
  581. warnln("----------");
  582. dbg.print_bytecode(entry);
  583. }
  584. ScopeGuard print_at_end {
  585. [&] {
  586. warnln("======================");
  587. RegexDebug dbg;
  588. dbg.print_bytecode(target);
  589. }
  590. };
  591. #endif
  592. Vector<Vector<Detail::Block>> basic_blocks;
  593. basic_blocks.ensure_capacity(alternatives.size());
  594. for (auto& entry : alternatives)
  595. basic_blocks.append(Regex<PosixBasicParser>::split_basic_blocks(entry));
  596. size_t left_skip = 0;
  597. size_t shared_block_count = basic_blocks.first().size();
  598. for (auto& entry : basic_blocks)
  599. shared_block_count = min(shared_block_count, entry.size());
  600. MatchState state;
  601. for (size_t block_index = 0; block_index < shared_block_count; block_index++) {
  602. auto& left_block = basic_blocks.first()[block_index];
  603. auto left_end = block_index + 1 == basic_blocks.first().size() ? left_block.end : basic_blocks.first()[block_index + 1].start;
  604. auto can_continue = true;
  605. for (size_t i = 1; i < alternatives.size(); ++i) {
  606. auto& right_blocks = basic_blocks[i];
  607. auto& right_block = right_blocks[block_index];
  608. auto right_end = block_index + 1 == right_blocks.size() ? right_block.end : right_blocks[block_index + 1].start;
  609. if (left_end - left_block.start != right_end - right_block.start) {
  610. can_continue = false;
  611. break;
  612. }
  613. if (alternatives[0].spans().slice(left_block.start, left_end - left_block.start) != alternatives[i].spans().slice(right_block.start, right_end - right_block.start)) {
  614. can_continue = false;
  615. break;
  616. }
  617. }
  618. if (!can_continue)
  619. break;
  620. size_t i = 0;
  621. for (auto& entry : alternatives) {
  622. auto& blocks = basic_blocks[i];
  623. auto& block = blocks[block_index];
  624. auto end = block_index + 1 == blocks.size() ? block.end : blocks[block_index + 1].start;
  625. state.instruction_position = block.start;
  626. size_t skip = 0;
  627. while (state.instruction_position < end) {
  628. auto& opcode = entry.get_opcode(state);
  629. state.instruction_position += opcode.size();
  630. skip = state.instruction_position;
  631. }
  632. left_skip = min(skip, left_skip);
  633. }
  634. }
  635. dbgln_if(REGEX_DEBUG, "Skipping {}/{} bytecode entries from {}", left_skip, 0, alternatives[0].size());
  636. if (left_skip > 0) {
  637. target.extend(alternatives[0].release_slice(basic_blocks.first().first().start, left_skip));
  638. auto first = true;
  639. for (auto& entry : alternatives) {
  640. if (first) {
  641. first = false;
  642. continue;
  643. }
  644. entry = entry.release_slice(left_skip);
  645. }
  646. }
  647. if (all_of(alternatives, [](auto& entry) { return entry.is_empty(); }))
  648. return;
  649. size_t patch_start = target.size();
  650. for (size_t i = 1; i < alternatives.size(); ++i) {
  651. target.empend(static_cast<ByteCodeValueType>(OpCodeId::ForkJump));
  652. target.empend(0u); // To be filled later.
  653. }
  654. size_t size_to_jump = 0;
  655. bool seen_one_empty = false;
  656. for (size_t i = alternatives.size(); i > 0; --i) {
  657. auto& entry = alternatives[i - 1];
  658. if (entry.is_empty()) {
  659. if (seen_one_empty)
  660. continue;
  661. seen_one_empty = true;
  662. }
  663. auto is_first = i == 1;
  664. auto instruction_size = entry.size() + (is_first ? 0 : 2); // Jump; -> +2
  665. size_to_jump += instruction_size;
  666. if (!is_first)
  667. target[patch_start + (i - 2) * 2 + 1] = size_to_jump + (alternatives.size() - i) * 2;
  668. dbgln_if(REGEX_DEBUG, "{} size = {}, cum={}", i - 1, instruction_size, size_to_jump);
  669. }
  670. seen_one_empty = false;
  671. for (size_t i = alternatives.size(); i > 0; --i) {
  672. auto& chunk = alternatives[i - 1];
  673. if (chunk.is_empty()) {
  674. if (seen_one_empty)
  675. continue;
  676. seen_one_empty = true;
  677. }
  678. ByteCode* previous_chunk = nullptr;
  679. size_t j = i - 1;
  680. auto seen_one_empty_before = chunk.is_empty();
  681. while (j >= 1) {
  682. --j;
  683. auto& candidate_chunk = alternatives[j];
  684. if (candidate_chunk.is_empty()) {
  685. if (seen_one_empty_before)
  686. continue;
  687. }
  688. previous_chunk = &candidate_chunk;
  689. break;
  690. }
  691. size_to_jump -= chunk.size() + (previous_chunk ? 2 : 0);
  692. target.extend(move(chunk));
  693. target.empend(static_cast<ByteCodeValueType>(OpCodeId::Jump));
  694. target.empend(size_to_jump); // Jump to the _END label
  695. }
  696. }
  697. enum class LookupTableInsertionOutcome {
  698. Successful,
  699. ReplaceWithAnyChar,
  700. TemporaryInversionNeeded,
  701. PermanentInversionNeeded,
  702. CannotPlaceInTable,
  703. };
  704. static LookupTableInsertionOutcome insert_into_lookup_table(RedBlackTree<ByteCodeValueType, CharRange>& table, CompareTypeAndValuePair pair)
  705. {
  706. switch (pair.type) {
  707. case CharacterCompareType::Inverse:
  708. return LookupTableInsertionOutcome::PermanentInversionNeeded;
  709. case CharacterCompareType::TemporaryInverse:
  710. return LookupTableInsertionOutcome::TemporaryInversionNeeded;
  711. case CharacterCompareType::AnyChar:
  712. return LookupTableInsertionOutcome::ReplaceWithAnyChar;
  713. case CharacterCompareType::CharClass:
  714. return LookupTableInsertionOutcome::CannotPlaceInTable;
  715. case CharacterCompareType::Char:
  716. table.insert(pair.value, { (u32)pair.value, (u32)pair.value });
  717. break;
  718. case CharacterCompareType::CharRange: {
  719. CharRange range { pair.value };
  720. table.insert(range.from, range);
  721. break;
  722. }
  723. case CharacterCompareType::Reference:
  724. case CharacterCompareType::Property:
  725. case CharacterCompareType::GeneralCategory:
  726. case CharacterCompareType::Script:
  727. case CharacterCompareType::ScriptExtension:
  728. return LookupTableInsertionOutcome::CannotPlaceInTable;
  729. case CharacterCompareType::Undefined:
  730. case CharacterCompareType::RangeExpressionDummy:
  731. case CharacterCompareType::String:
  732. case CharacterCompareType::LookupTable:
  733. VERIFY_NOT_REACHED();
  734. }
  735. return LookupTableInsertionOutcome::Successful;
  736. }
  737. void Optimizer::append_character_class(ByteCode& target, Vector<CompareTypeAndValuePair>&& pairs)
  738. {
  739. ByteCode arguments;
  740. size_t argument_count = 0;
  741. if (pairs.size() <= 1) {
  742. for (auto& pair : pairs) {
  743. arguments.append(to_underlying(pair.type));
  744. if (pair.type != CharacterCompareType::AnyChar && pair.type != CharacterCompareType::TemporaryInverse && pair.type != CharacterCompareType::Inverse)
  745. arguments.append(pair.value);
  746. ++argument_count;
  747. }
  748. } else {
  749. RedBlackTree<ByteCodeValueType, CharRange> table;
  750. RedBlackTree<ByteCodeValueType, CharRange> inverted_table;
  751. auto* current_table = &table;
  752. auto* current_inverted_table = &inverted_table;
  753. bool invert_for_next_iteration = false;
  754. bool is_currently_inverted = false;
  755. for (auto& value : pairs) {
  756. auto should_invert_after_this_iteration = invert_for_next_iteration;
  757. invert_for_next_iteration = false;
  758. auto insertion_result = insert_into_lookup_table(*current_table, value);
  759. switch (insertion_result) {
  760. case LookupTableInsertionOutcome::Successful:
  761. break;
  762. case LookupTableInsertionOutcome::ReplaceWithAnyChar: {
  763. table.clear();
  764. inverted_table.clear();
  765. arguments.append(to_underlying(CharacterCompareType::AnyChar));
  766. ++argument_count;
  767. break;
  768. }
  769. case LookupTableInsertionOutcome::TemporaryInversionNeeded:
  770. swap(current_table, current_inverted_table);
  771. invert_for_next_iteration = true;
  772. is_currently_inverted = !is_currently_inverted;
  773. break;
  774. case LookupTableInsertionOutcome::PermanentInversionNeeded:
  775. swap(current_table, current_inverted_table);
  776. is_currently_inverted = !is_currently_inverted;
  777. break;
  778. case LookupTableInsertionOutcome::CannotPlaceInTable:
  779. if (is_currently_inverted) {
  780. arguments.append(to_underlying(CharacterCompareType::TemporaryInverse));
  781. ++argument_count;
  782. }
  783. arguments.append(to_underlying(value.type));
  784. arguments.append(value.value);
  785. ++argument_count;
  786. break;
  787. }
  788. if (should_invert_after_this_iteration) {
  789. swap(current_table, current_inverted_table);
  790. is_currently_inverted = !is_currently_inverted;
  791. }
  792. }
  793. auto append_table = [&](auto& table) {
  794. ++argument_count;
  795. arguments.append(to_underlying(CharacterCompareType::LookupTable));
  796. auto size_index = arguments.size();
  797. arguments.append(0);
  798. Optional<CharRange> active_range;
  799. size_t range_count = 0;
  800. for (auto& range : table) {
  801. if (!active_range.has_value()) {
  802. active_range = range;
  803. continue;
  804. }
  805. if (range.from <= active_range->to + 1 && range.to + 1 >= active_range->from) {
  806. active_range = CharRange { min(range.from, active_range->from), max(range.to, active_range->to) };
  807. } else {
  808. ++range_count;
  809. arguments.append(active_range.release_value());
  810. active_range = range;
  811. }
  812. }
  813. if (active_range.has_value()) {
  814. ++range_count;
  815. arguments.append(active_range.release_value());
  816. }
  817. arguments[size_index] = range_count;
  818. };
  819. if (!table.is_empty())
  820. append_table(table);
  821. if (!inverted_table.is_empty()) {
  822. ++argument_count;
  823. arguments.append(to_underlying(CharacterCompareType::TemporaryInverse));
  824. append_table(inverted_table);
  825. }
  826. }
  827. target.empend(static_cast<ByteCodeValueType>(OpCodeId::Compare));
  828. target.empend(argument_count); // number of arguments
  829. target.empend(arguments.size()); // size of arguments
  830. target.extend(move(arguments));
  831. }
  832. template void Regex<PosixBasicParser>::run_optimization_passes();
  833. template void Regex<PosixExtendedParser>::run_optimization_passes();
  834. template void Regex<ECMA262Parser>::run_optimization_passes();
  835. }