RegexByteCode.cpp 43 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050105110521053105410551056105710581059106010611062106310641065106610671068106910701071107210731074107510761077107810791080108110821083108410851086108710881089109010911092109310941095109610971098109911001101110211031104110511061107110811091110
  1. /*
  2. * Copyright (c) 2020, Emanuel Sprung <emanuel.sprung@gmail.com>
  3. *
  4. * SPDX-License-Identifier: BSD-2-Clause
  5. */
  6. #include "RegexByteCode.h"
  7. #include "RegexDebug.h"
  8. #include <AK/BinarySearch.h>
  9. #include <AK/CharacterTypes.h>
  10. #include <AK/StringBuilder.h>
  11. #include <LibUnicode/CharacterTypes.h>
  12. // U+2028 LINE SEPARATOR
  13. constexpr static u32 const LineSeparator { 0x2028 };
  14. // U+2029 PARAGRAPH SEPARATOR
  15. constexpr static u32 const ParagraphSeparator { 0x2029 };
  16. namespace regex {
  17. StringView OpCode::name(OpCodeId opcode_id)
  18. {
  19. switch (opcode_id) {
  20. #define __ENUMERATE_OPCODE(x) \
  21. case OpCodeId::x: \
  22. return #x##sv;
  23. ENUMERATE_OPCODES
  24. #undef __ENUMERATE_OPCODE
  25. default:
  26. VERIFY_NOT_REACHED();
  27. return "<Unknown>"sv;
  28. }
  29. }
  30. StringView OpCode::name() const
  31. {
  32. return name(opcode_id());
  33. }
  34. StringView execution_result_name(ExecutionResult result)
  35. {
  36. switch (result) {
  37. #define __ENUMERATE_EXECUTION_RESULT(x) \
  38. case ExecutionResult::x: \
  39. return #x##sv;
  40. ENUMERATE_EXECUTION_RESULTS
  41. #undef __ENUMERATE_EXECUTION_RESULT
  42. default:
  43. VERIFY_NOT_REACHED();
  44. return "<Unknown>"sv;
  45. }
  46. }
  47. StringView opcode_id_name(OpCodeId opcode)
  48. {
  49. switch (opcode) {
  50. #define __ENUMERATE_OPCODE(x) \
  51. case OpCodeId::x: \
  52. return #x##sv;
  53. ENUMERATE_OPCODES
  54. #undef __ENUMERATE_OPCODE
  55. default:
  56. VERIFY_NOT_REACHED();
  57. return "<Unknown>"sv;
  58. }
  59. }
  60. StringView boundary_check_type_name(BoundaryCheckType ty)
  61. {
  62. switch (ty) {
  63. #define __ENUMERATE_BOUNDARY_CHECK_TYPE(x) \
  64. case BoundaryCheckType::x: \
  65. return #x##sv;
  66. ENUMERATE_BOUNDARY_CHECK_TYPES
  67. #undef __ENUMERATE_BOUNDARY_CHECK_TYPE
  68. default:
  69. VERIFY_NOT_REACHED();
  70. return "<Unknown>"sv;
  71. }
  72. }
  73. StringView character_compare_type_name(CharacterCompareType ch_compare_type)
  74. {
  75. switch (ch_compare_type) {
  76. #define __ENUMERATE_CHARACTER_COMPARE_TYPE(x) \
  77. case CharacterCompareType::x: \
  78. return #x##sv;
  79. ENUMERATE_CHARACTER_COMPARE_TYPES
  80. #undef __ENUMERATE_CHARACTER_COMPARE_TYPE
  81. default:
  82. VERIFY_NOT_REACHED();
  83. return "<Unknown>"sv;
  84. }
  85. }
  86. static StringView character_class_name(CharClass ch_class)
  87. {
  88. switch (ch_class) {
  89. #define __ENUMERATE_CHARACTER_CLASS(x) \
  90. case CharClass::x: \
  91. return #x##sv;
  92. ENUMERATE_CHARACTER_CLASSES
  93. #undef __ENUMERATE_CHARACTER_CLASS
  94. default:
  95. VERIFY_NOT_REACHED();
  96. return "<Unknown>"sv;
  97. }
  98. }
  99. static void advance_string_position(MatchState& state, RegexStringView view, Optional<u32> code_point = {})
  100. {
  101. ++state.string_position;
  102. if (view.unicode()) {
  103. if (!code_point.has_value() && (state.string_position_in_code_units < view.length_in_code_units()))
  104. code_point = view[state.string_position_in_code_units];
  105. if (code_point.has_value())
  106. state.string_position_in_code_units += view.length_of_code_point(*code_point);
  107. } else {
  108. ++state.string_position_in_code_units;
  109. }
  110. }
  111. static void advance_string_position(MatchState& state, RegexStringView, RegexStringView advance_by)
  112. {
  113. state.string_position += advance_by.length();
  114. state.string_position_in_code_units += advance_by.length_in_code_units();
  115. }
  116. static void reverse_string_position(MatchState& state, RegexStringView view, size_t amount)
  117. {
  118. VERIFY(state.string_position >= amount);
  119. state.string_position -= amount;
  120. if (view.unicode())
  121. state.string_position_in_code_units = view.code_unit_offset_of(state.string_position);
  122. else
  123. state.string_position_in_code_units -= amount;
  124. }
  125. static void save_string_position(MatchInput const& input, MatchState const& state)
  126. {
  127. input.saved_positions.append(state.string_position);
  128. input.saved_forks_since_last_save.append(state.forks_since_last_save);
  129. input.saved_code_unit_positions.append(state.string_position_in_code_units);
  130. }
  131. static bool restore_string_position(MatchInput const& input, MatchState& state)
  132. {
  133. if (input.saved_positions.is_empty())
  134. return false;
  135. state.string_position = input.saved_positions.take_last();
  136. state.string_position_in_code_units = input.saved_code_unit_positions.take_last();
  137. state.forks_since_last_save = input.saved_forks_since_last_save.take_last();
  138. return true;
  139. }
  140. OwnPtr<OpCode> ByteCode::s_opcodes[(size_t)OpCodeId::Last + 1];
  141. bool ByteCode::s_opcodes_initialized { false };
  142. void ByteCode::ensure_opcodes_initialized()
  143. {
  144. if (s_opcodes_initialized)
  145. return;
  146. for (u32 i = (u32)OpCodeId::First; i <= (u32)OpCodeId::Last; ++i) {
  147. switch ((OpCodeId)i) {
  148. #define __ENUMERATE_OPCODE(OpCode) \
  149. case OpCodeId::OpCode: \
  150. s_opcodes[i] = make<OpCode_##OpCode>(); \
  151. break;
  152. ENUMERATE_OPCODES
  153. #undef __ENUMERATE_OPCODE
  154. }
  155. }
  156. s_opcodes_initialized = true;
  157. }
  158. ALWAYS_INLINE OpCode& ByteCode::get_opcode_by_id(OpCodeId id) const
  159. {
  160. VERIFY(id >= OpCodeId::First && id <= OpCodeId::Last);
  161. auto& opcode = s_opcodes[(u32)id];
  162. opcode->set_bytecode(*const_cast<ByteCode*>(this));
  163. return *opcode;
  164. }
  165. OpCode& ByteCode::get_opcode(MatchState& state) const
  166. {
  167. OpCodeId opcode_id;
  168. if (auto opcode_ptr = static_cast<DisjointChunks<ByteCodeValueType> const&>(*this).find(state.instruction_position))
  169. opcode_id = (OpCodeId)*opcode_ptr;
  170. else
  171. opcode_id = OpCodeId::Exit;
  172. auto& opcode = get_opcode_by_id(opcode_id);
  173. opcode.set_state(state);
  174. return opcode;
  175. }
  176. ALWAYS_INLINE ExecutionResult OpCode_Exit::execute(MatchInput const& input, MatchState& state) const
  177. {
  178. if (state.string_position > input.view.length() || state.instruction_position >= m_bytecode->size())
  179. return ExecutionResult::Succeeded;
  180. return ExecutionResult::Failed;
  181. }
  182. ALWAYS_INLINE ExecutionResult OpCode_Save::execute(MatchInput const& input, MatchState& state) const
  183. {
  184. save_string_position(input, state);
  185. state.forks_since_last_save = 0;
  186. return ExecutionResult::Continue;
  187. }
  188. ALWAYS_INLINE ExecutionResult OpCode_Restore::execute(MatchInput const& input, MatchState& state) const
  189. {
  190. if (!restore_string_position(input, state))
  191. return ExecutionResult::Failed;
  192. return ExecutionResult::Continue;
  193. }
  194. ALWAYS_INLINE ExecutionResult OpCode_GoBack::execute(MatchInput const& input, MatchState& state) const
  195. {
  196. if (count() > state.string_position)
  197. return ExecutionResult::Failed_ExecuteLowPrioForks;
  198. reverse_string_position(state, input.view, count());
  199. return ExecutionResult::Continue;
  200. }
  201. ALWAYS_INLINE ExecutionResult OpCode_FailForks::execute(MatchInput const& input, MatchState& state) const
  202. {
  203. input.fail_counter += state.forks_since_last_save;
  204. return ExecutionResult::Failed_ExecuteLowPrioForks;
  205. }
  206. ALWAYS_INLINE ExecutionResult OpCode_Jump::execute(MatchInput const&, MatchState& state) const
  207. {
  208. state.instruction_position += offset();
  209. return ExecutionResult::Continue;
  210. }
  211. ALWAYS_INLINE ExecutionResult OpCode_ForkJump::execute(MatchInput const&, MatchState& state) const
  212. {
  213. state.fork_at_position = state.instruction_position + size() + offset();
  214. state.forks_since_last_save++;
  215. return ExecutionResult::Fork_PrioHigh;
  216. }
  217. ALWAYS_INLINE ExecutionResult OpCode_ForkReplaceJump::execute(MatchInput const& input, MatchState& state) const
  218. {
  219. state.fork_at_position = state.instruction_position + size() + offset();
  220. input.fork_to_replace = state.instruction_position;
  221. state.forks_since_last_save++;
  222. return ExecutionResult::Fork_PrioHigh;
  223. }
  224. ALWAYS_INLINE ExecutionResult OpCode_ForkStay::execute(MatchInput const&, MatchState& state) const
  225. {
  226. state.fork_at_position = state.instruction_position + size() + offset();
  227. state.forks_since_last_save++;
  228. return ExecutionResult::Fork_PrioLow;
  229. }
  230. ALWAYS_INLINE ExecutionResult OpCode_ForkReplaceStay::execute(MatchInput const& input, MatchState& state) const
  231. {
  232. state.fork_at_position = state.instruction_position + size() + offset();
  233. input.fork_to_replace = state.instruction_position;
  234. return ExecutionResult::Fork_PrioLow;
  235. }
  236. ALWAYS_INLINE ExecutionResult OpCode_CheckBegin::execute(MatchInput const& input, MatchState& state) const
  237. {
  238. auto is_at_line_boundary = [&] {
  239. if (state.string_position == 0)
  240. return true;
  241. if (input.regex_options.has_flag_set(AllFlags::Multiline) && input.regex_options.has_flag_set(AllFlags::Internal_ConsiderNewline)) {
  242. auto input_view = input.view.substring_view(state.string_position - 1, 1)[0];
  243. return input_view == '\r' || input_view == '\n' || input_view == LineSeparator || input_view == ParagraphSeparator;
  244. }
  245. return false;
  246. }();
  247. if (is_at_line_boundary && (input.regex_options & AllFlags::MatchNotBeginOfLine))
  248. return ExecutionResult::Failed_ExecuteLowPrioForks;
  249. if ((is_at_line_boundary && !(input.regex_options & AllFlags::MatchNotBeginOfLine))
  250. || (!is_at_line_boundary && (input.regex_options & AllFlags::MatchNotBeginOfLine))
  251. || (is_at_line_boundary && (input.regex_options & AllFlags::Global)))
  252. return ExecutionResult::Continue;
  253. return ExecutionResult::Failed_ExecuteLowPrioForks;
  254. }
  255. ALWAYS_INLINE ExecutionResult OpCode_CheckBoundary::execute(MatchInput const& input, MatchState& state) const
  256. {
  257. auto isword = [](auto ch) { return is_ascii_alphanumeric(ch) || ch == '_'; };
  258. auto is_word_boundary = [&] {
  259. if (state.string_position == input.view.length()) {
  260. return (state.string_position > 0 && isword(input.view[state.string_position_in_code_units - 1]));
  261. }
  262. if (state.string_position == 0) {
  263. return (isword(input.view[0]));
  264. }
  265. return !!(isword(input.view[state.string_position_in_code_units]) ^ isword(input.view[state.string_position_in_code_units - 1]));
  266. };
  267. switch (type()) {
  268. case BoundaryCheckType::Word: {
  269. if (is_word_boundary())
  270. return ExecutionResult::Continue;
  271. return ExecutionResult::Failed_ExecuteLowPrioForks;
  272. }
  273. case BoundaryCheckType::NonWord: {
  274. if (!is_word_boundary())
  275. return ExecutionResult::Continue;
  276. return ExecutionResult::Failed_ExecuteLowPrioForks;
  277. }
  278. }
  279. VERIFY_NOT_REACHED();
  280. }
  281. ALWAYS_INLINE ExecutionResult OpCode_CheckEnd::execute(MatchInput const& input, MatchState& state) const
  282. {
  283. auto is_at_line_boundary = [&] {
  284. if (state.string_position == input.view.length())
  285. return true;
  286. if (input.regex_options.has_flag_set(AllFlags::Multiline) && input.regex_options.has_flag_set(AllFlags::Internal_ConsiderNewline)) {
  287. auto input_view = input.view.substring_view(state.string_position, 1)[0];
  288. return input_view == '\r' || input_view == '\n' || input_view == LineSeparator || input_view == ParagraphSeparator;
  289. }
  290. return false;
  291. }();
  292. if (is_at_line_boundary && (input.regex_options & AllFlags::MatchNotEndOfLine))
  293. return ExecutionResult::Failed_ExecuteLowPrioForks;
  294. if ((is_at_line_boundary && !(input.regex_options & AllFlags::MatchNotEndOfLine))
  295. || (!is_at_line_boundary && (input.regex_options & AllFlags::MatchNotEndOfLine || input.regex_options & AllFlags::MatchNotBeginOfLine)))
  296. return ExecutionResult::Continue;
  297. return ExecutionResult::Failed_ExecuteLowPrioForks;
  298. }
  299. ALWAYS_INLINE ExecutionResult OpCode_ClearCaptureGroup::execute(MatchInput const& input, MatchState& state) const
  300. {
  301. if (input.match_index < state.capture_group_matches.size()) {
  302. auto& group = state.capture_group_matches[input.match_index];
  303. auto group_id = id();
  304. if (group_id >= group.size())
  305. group.resize(group_id + 1);
  306. group[group_id].reset();
  307. }
  308. return ExecutionResult::Continue;
  309. }
  310. ALWAYS_INLINE ExecutionResult OpCode_SaveLeftCaptureGroup::execute(MatchInput const& input, MatchState& state) const
  311. {
  312. if (input.match_index >= state.capture_group_matches.size()) {
  313. state.capture_group_matches.ensure_capacity(input.match_index);
  314. auto capacity = state.capture_group_matches.capacity();
  315. for (size_t i = state.capture_group_matches.size(); i <= capacity; ++i)
  316. state.capture_group_matches.empend();
  317. }
  318. if (id() >= state.capture_group_matches.at(input.match_index).size()) {
  319. state.capture_group_matches.at(input.match_index).ensure_capacity(id());
  320. auto capacity = state.capture_group_matches.at(input.match_index).capacity();
  321. for (size_t i = state.capture_group_matches.at(input.match_index).size(); i <= capacity; ++i)
  322. state.capture_group_matches.at(input.match_index).empend();
  323. }
  324. state.capture_group_matches.at(input.match_index).at(id()).left_column = state.string_position;
  325. return ExecutionResult::Continue;
  326. }
  327. ALWAYS_INLINE ExecutionResult OpCode_SaveRightCaptureGroup::execute(MatchInput const& input, MatchState& state) const
  328. {
  329. auto& match = state.capture_group_matches.at(input.match_index).at(id());
  330. auto start_position = match.left_column;
  331. if (state.string_position < start_position) {
  332. dbgln("Right capture group {} is before left capture group {}!", state.string_position, start_position);
  333. return ExecutionResult::Failed_ExecuteLowPrioForks;
  334. }
  335. auto length = state.string_position - start_position;
  336. if (start_position < match.column)
  337. return ExecutionResult::Continue;
  338. VERIFY(start_position + length <= input.view.length());
  339. auto view = input.view.substring_view(start_position, length);
  340. if (input.regex_options & AllFlags::StringCopyMatches) {
  341. match = { view.to_deprecated_string(), input.line, start_position, input.global_offset + start_position }; // create a copy of the original string
  342. } else {
  343. match = { view, input.line, start_position, input.global_offset + start_position }; // take view to original string
  344. }
  345. return ExecutionResult::Continue;
  346. }
  347. ALWAYS_INLINE ExecutionResult OpCode_SaveRightNamedCaptureGroup::execute(MatchInput const& input, MatchState& state) const
  348. {
  349. auto& match = state.capture_group_matches.at(input.match_index).at(id());
  350. auto start_position = match.left_column;
  351. if (state.string_position < start_position)
  352. return ExecutionResult::Failed_ExecuteLowPrioForks;
  353. auto length = state.string_position - start_position;
  354. if (start_position < match.column)
  355. return ExecutionResult::Continue;
  356. VERIFY(start_position + length <= input.view.length());
  357. auto view = input.view.substring_view(start_position, length);
  358. if (input.regex_options & AllFlags::StringCopyMatches) {
  359. match = { view.to_deprecated_string(), name(), input.line, start_position, input.global_offset + start_position }; // create a copy of the original string
  360. } else {
  361. match = { view, name(), input.line, start_position, input.global_offset + start_position }; // take view to original string
  362. }
  363. return ExecutionResult::Continue;
  364. }
  365. ALWAYS_INLINE ExecutionResult OpCode_Compare::execute(MatchInput const& input, MatchState& state) const
  366. {
  367. bool inverse { false };
  368. bool temporary_inverse { false };
  369. bool reset_temp_inverse { false };
  370. struct DisjunctionState {
  371. bool active { false };
  372. bool is_conjunction { false };
  373. bool fail { false };
  374. size_t initial_position;
  375. size_t initial_code_unit_position;
  376. Optional<size_t> last_accepted_position {};
  377. Optional<size_t> last_accepted_code_unit_position {};
  378. };
  379. Vector<DisjunctionState, 4> disjunction_states;
  380. disjunction_states.empend();
  381. auto current_disjunction_state = [&]() -> DisjunctionState& { return disjunction_states.last(); };
  382. auto current_inversion_state = [&]() -> bool { return temporary_inverse ^ inverse; };
  383. size_t string_position = state.string_position;
  384. bool inverse_matched { false };
  385. bool had_zero_length_match { false };
  386. state.string_position_before_match = state.string_position;
  387. size_t offset { state.instruction_position + 3 };
  388. for (size_t i = 0; i < arguments_count(); ++i) {
  389. if (state.string_position > string_position)
  390. break;
  391. if (reset_temp_inverse) {
  392. reset_temp_inverse = false;
  393. temporary_inverse = false;
  394. } else {
  395. reset_temp_inverse = true;
  396. }
  397. auto compare_type = (CharacterCompareType)m_bytecode->at(offset++);
  398. if (compare_type == CharacterCompareType::Inverse) {
  399. inverse = !inverse;
  400. continue;
  401. } else if (compare_type == CharacterCompareType::TemporaryInverse) {
  402. // If "TemporaryInverse" is given, negate the current inversion state only for the next opcode.
  403. // it follows that this cannot be the last compare element.
  404. VERIFY(i != arguments_count() - 1);
  405. temporary_inverse = true;
  406. reset_temp_inverse = false;
  407. continue;
  408. } else if (compare_type == CharacterCompareType::Char) {
  409. u32 ch = m_bytecode->at(offset++);
  410. // We want to compare a string that is longer or equal in length to the available string
  411. if (input.view.length() <= state.string_position)
  412. return ExecutionResult::Failed_ExecuteLowPrioForks;
  413. compare_char(input, state, ch, current_inversion_state(), inverse_matched);
  414. } else if (compare_type == CharacterCompareType::AnyChar) {
  415. // We want to compare a string that is definitely longer than the available string
  416. if (input.view.length() <= state.string_position)
  417. return ExecutionResult::Failed_ExecuteLowPrioForks;
  418. auto input_view = input.view.substring_view(state.string_position, 1)[0];
  419. auto is_equivalent_to_newline = input_view == '\n'
  420. || (input.regex_options.has_flag_set(AllFlags::Internal_ECMA262DotSemantics)
  421. ? (input_view == '\r' || input_view == LineSeparator || input_view == ParagraphSeparator)
  422. : false);
  423. if (!is_equivalent_to_newline || (input.regex_options.has_flag_set(AllFlags::SingleLine) && input.regex_options.has_flag_set(AllFlags::Internal_ConsiderNewline))) {
  424. if (current_inversion_state())
  425. inverse_matched = true;
  426. else
  427. advance_string_position(state, input.view, input_view);
  428. }
  429. } else if (compare_type == CharacterCompareType::String) {
  430. VERIFY(!current_inversion_state());
  431. auto const& length = m_bytecode->at(offset++);
  432. // We want to compare a string that is definitely longer than the available string
  433. if (input.view.length() < state.string_position + length)
  434. return ExecutionResult::Failed_ExecuteLowPrioForks;
  435. Optional<DeprecatedString> str;
  436. Utf16Data utf16;
  437. Vector<u32> data;
  438. data.ensure_capacity(length);
  439. for (size_t i = offset; i < offset + length; ++i)
  440. data.unchecked_append(m_bytecode->at(i));
  441. auto view = input.view.construct_as_same(data, str, utf16);
  442. offset += length;
  443. if (compare_string(input, state, view, had_zero_length_match)) {
  444. if (current_inversion_state())
  445. inverse_matched = true;
  446. }
  447. } else if (compare_type == CharacterCompareType::CharClass) {
  448. if (input.view.length() <= state.string_position_in_code_units)
  449. return ExecutionResult::Failed_ExecuteLowPrioForks;
  450. auto character_class = (CharClass)m_bytecode->at(offset++);
  451. auto ch = input.view[state.string_position_in_code_units];
  452. compare_character_class(input, state, character_class, ch, current_inversion_state(), inverse_matched);
  453. } else if (compare_type == CharacterCompareType::LookupTable) {
  454. if (input.view.length() <= state.string_position)
  455. return ExecutionResult::Failed_ExecuteLowPrioForks;
  456. auto count = m_bytecode->at(offset++);
  457. auto range_data = m_bytecode->template spans<4>().slice(offset, count);
  458. offset += count;
  459. auto ch = input.view.substring_view(state.string_position, 1)[0];
  460. auto const* matching_range = binary_search(range_data, ch, nullptr, [insensitive = input.regex_options & AllFlags::Insensitive](auto needle, CharRange range) {
  461. auto upper_case_needle = needle;
  462. auto lower_case_needle = needle;
  463. if (insensitive) {
  464. upper_case_needle = to_ascii_uppercase(needle);
  465. lower_case_needle = to_ascii_lowercase(needle);
  466. }
  467. if (lower_case_needle >= range.from && lower_case_needle <= range.to)
  468. return 0;
  469. if (upper_case_needle >= range.from && upper_case_needle <= range.to)
  470. return 0;
  471. if (lower_case_needle > range.to || upper_case_needle > range.to)
  472. return 1;
  473. return -1;
  474. });
  475. if (matching_range) {
  476. if (current_inversion_state())
  477. inverse_matched = true;
  478. else
  479. advance_string_position(state, input.view, ch);
  480. }
  481. } else if (compare_type == CharacterCompareType::CharRange) {
  482. if (input.view.length() <= state.string_position)
  483. return ExecutionResult::Failed_ExecuteLowPrioForks;
  484. auto value = (CharRange)m_bytecode->at(offset++);
  485. auto from = value.from;
  486. auto to = value.to;
  487. auto ch = input.view[state.string_position_in_code_units];
  488. compare_character_range(input, state, from, to, ch, current_inversion_state(), inverse_matched);
  489. } else if (compare_type == CharacterCompareType::Reference) {
  490. auto reference_number = (size_t)m_bytecode->at(offset++);
  491. auto& groups = state.capture_group_matches.at(input.match_index);
  492. if (groups.size() <= reference_number)
  493. return ExecutionResult::Failed_ExecuteLowPrioForks;
  494. auto str = groups.at(reference_number).view;
  495. // We want to compare a string that is definitely longer than the available string
  496. if (input.view.length() < state.string_position + str.length())
  497. return ExecutionResult::Failed_ExecuteLowPrioForks;
  498. if (compare_string(input, state, str, had_zero_length_match)) {
  499. if (current_inversion_state())
  500. inverse_matched = true;
  501. }
  502. } else if (compare_type == CharacterCompareType::Property) {
  503. auto property = static_cast<Unicode::Property>(m_bytecode->at(offset++));
  504. compare_property(input, state, property, current_inversion_state(), inverse_matched);
  505. } else if (compare_type == CharacterCompareType::GeneralCategory) {
  506. auto general_category = static_cast<Unicode::GeneralCategory>(m_bytecode->at(offset++));
  507. compare_general_category(input, state, general_category, current_inversion_state(), inverse_matched);
  508. } else if (compare_type == CharacterCompareType::Script) {
  509. auto script = static_cast<Unicode::Script>(m_bytecode->at(offset++));
  510. compare_script(input, state, script, current_inversion_state(), inverse_matched);
  511. } else if (compare_type == CharacterCompareType::ScriptExtension) {
  512. auto script = static_cast<Unicode::Script>(m_bytecode->at(offset++));
  513. compare_script_extension(input, state, script, current_inversion_state(), inverse_matched);
  514. } else if (compare_type == CharacterCompareType::And) {
  515. disjunction_states.append({
  516. .active = true,
  517. .is_conjunction = false,
  518. .fail = false,
  519. .initial_position = state.string_position,
  520. .initial_code_unit_position = state.string_position_in_code_units,
  521. });
  522. continue;
  523. } else if (compare_type == CharacterCompareType::Or) {
  524. disjunction_states.append({
  525. .active = true,
  526. .is_conjunction = true,
  527. .fail = true,
  528. .initial_position = state.string_position,
  529. .initial_code_unit_position = state.string_position_in_code_units,
  530. });
  531. continue;
  532. } else if (compare_type == CharacterCompareType::EndAndOr) {
  533. auto disjunction_state = disjunction_states.take_last();
  534. if (!disjunction_state.fail) {
  535. state.string_position = disjunction_state.last_accepted_position.value_or(disjunction_state.initial_position);
  536. state.string_position_in_code_units = disjunction_state.last_accepted_code_unit_position.value_or(disjunction_state.initial_code_unit_position);
  537. }
  538. } else {
  539. warnln("Undefined comparison: {}", (int)compare_type);
  540. VERIFY_NOT_REACHED();
  541. break;
  542. }
  543. auto& new_disjunction_state = current_disjunction_state();
  544. if (current_inversion_state() && (!inverse || new_disjunction_state.active) && !inverse_matched) {
  545. advance_string_position(state, input.view);
  546. inverse_matched = true;
  547. }
  548. if (new_disjunction_state.active) {
  549. auto failed = (!had_zero_length_match && string_position == state.string_position) || state.string_position > input.view.length();
  550. if (!failed) {
  551. new_disjunction_state.last_accepted_position = state.string_position;
  552. new_disjunction_state.last_accepted_code_unit_position = state.string_position_in_code_units;
  553. }
  554. if (new_disjunction_state.is_conjunction)
  555. new_disjunction_state.fail = failed && new_disjunction_state.fail;
  556. else
  557. new_disjunction_state.fail = failed || new_disjunction_state.fail;
  558. state.string_position = new_disjunction_state.initial_position;
  559. state.string_position_in_code_units = new_disjunction_state.initial_code_unit_position;
  560. }
  561. }
  562. auto& new_disjunction_state = current_disjunction_state();
  563. if (new_disjunction_state.active) {
  564. if (!new_disjunction_state.fail) {
  565. state.string_position = new_disjunction_state.last_accepted_position.value_or(new_disjunction_state.initial_position);
  566. state.string_position_in_code_units = new_disjunction_state.last_accepted_code_unit_position.value_or(new_disjunction_state.initial_code_unit_position);
  567. }
  568. }
  569. if (current_inversion_state() && !inverse_matched)
  570. advance_string_position(state, input.view);
  571. if ((!had_zero_length_match && string_position == state.string_position) || state.string_position > input.view.length())
  572. return ExecutionResult::Failed_ExecuteLowPrioForks;
  573. return ExecutionResult::Continue;
  574. }
  575. ALWAYS_INLINE void OpCode_Compare::compare_char(MatchInput const& input, MatchState& state, u32 ch1, bool inverse, bool& inverse_matched)
  576. {
  577. if (state.string_position == input.view.length())
  578. return;
  579. auto input_view = input.view.substring_view(state.string_position, 1)[0];
  580. bool equal;
  581. if (input.regex_options & AllFlags::Insensitive)
  582. equal = to_ascii_lowercase(input_view) == to_ascii_lowercase(ch1); // FIXME: Implement case-insensitive matching for non-ascii characters
  583. else
  584. equal = input_view == ch1;
  585. if (equal) {
  586. if (inverse)
  587. inverse_matched = true;
  588. else
  589. advance_string_position(state, input.view, ch1);
  590. }
  591. }
  592. ALWAYS_INLINE bool OpCode_Compare::compare_string(MatchInput const& input, MatchState& state, RegexStringView str, bool& had_zero_length_match)
  593. {
  594. if (state.string_position + str.length() > input.view.length()) {
  595. if (str.is_empty()) {
  596. had_zero_length_match = true;
  597. return true;
  598. }
  599. return false;
  600. }
  601. if (str.length() == 0) {
  602. had_zero_length_match = true;
  603. return true;
  604. }
  605. auto subject = input.view.substring_view(state.string_position, str.length());
  606. bool equals;
  607. if (input.regex_options & AllFlags::Insensitive)
  608. equals = subject.equals_ignoring_case(str);
  609. else
  610. equals = subject.equals(str);
  611. if (equals)
  612. advance_string_position(state, input.view, str);
  613. return equals;
  614. }
  615. ALWAYS_INLINE void OpCode_Compare::compare_character_class(MatchInput const& input, MatchState& state, CharClass character_class, u32 ch, bool inverse, bool& inverse_matched)
  616. {
  617. if (matches_character_class(character_class, ch, input.regex_options & AllFlags::Insensitive)) {
  618. if (inverse)
  619. inverse_matched = true;
  620. else
  621. advance_string_position(state, input.view, ch);
  622. }
  623. }
  624. bool OpCode_Compare::matches_character_class(CharClass character_class, u32 ch, bool insensitive)
  625. {
  626. constexpr auto is_space_or_line_terminator = [](u32 code_point) {
  627. static auto space_separator = Unicode::general_category_from_string("Space_Separator"sv);
  628. if (!space_separator.has_value())
  629. return is_ascii_space(code_point);
  630. if ((code_point == 0x0a) || (code_point == 0x0d) || (code_point == 0x2028) || (code_point == 0x2029))
  631. return true;
  632. if ((code_point == 0x09) || (code_point == 0x0b) || (code_point == 0x0c) || (code_point == 0xfeff))
  633. return true;
  634. return Unicode::code_point_has_general_category(code_point, *space_separator);
  635. };
  636. switch (character_class) {
  637. case CharClass::Alnum:
  638. return is_ascii_alphanumeric(ch);
  639. case CharClass::Alpha:
  640. return is_ascii_alpha(ch);
  641. case CharClass::Blank:
  642. return is_ascii_blank(ch);
  643. case CharClass::Cntrl:
  644. return is_ascii_control(ch);
  645. case CharClass::Digit:
  646. return is_ascii_digit(ch);
  647. case CharClass::Graph:
  648. return is_ascii_graphical(ch);
  649. case CharClass::Lower:
  650. return is_ascii_lower_alpha(ch) || (insensitive && is_ascii_upper_alpha(ch));
  651. case CharClass::Print:
  652. return is_ascii_printable(ch);
  653. case CharClass::Punct:
  654. return is_ascii_punctuation(ch);
  655. case CharClass::Space:
  656. return is_space_or_line_terminator(ch);
  657. case CharClass::Upper:
  658. return is_ascii_upper_alpha(ch) || (insensitive && is_ascii_lower_alpha(ch));
  659. case CharClass::Word:
  660. return is_ascii_alphanumeric(ch) || ch == '_';
  661. case CharClass::Xdigit:
  662. return is_ascii_hex_digit(ch);
  663. }
  664. VERIFY_NOT_REACHED();
  665. }
  666. ALWAYS_INLINE void OpCode_Compare::compare_character_range(MatchInput const& input, MatchState& state, u32 from, u32 to, u32 ch, bool inverse, bool& inverse_matched)
  667. {
  668. if (input.regex_options & AllFlags::Insensitive) {
  669. from = to_ascii_lowercase(from);
  670. to = to_ascii_lowercase(to);
  671. ch = to_ascii_lowercase(ch);
  672. }
  673. if (ch >= from && ch <= to) {
  674. if (inverse)
  675. inverse_matched = true;
  676. else
  677. advance_string_position(state, input.view, ch);
  678. }
  679. }
  680. ALWAYS_INLINE void OpCode_Compare::compare_property(MatchInput const& input, MatchState& state, Unicode::Property property, bool inverse, bool& inverse_matched)
  681. {
  682. if (state.string_position == input.view.length())
  683. return;
  684. u32 code_point = input.view[state.string_position_in_code_units];
  685. bool equal = Unicode::code_point_has_property(code_point, property);
  686. if (equal) {
  687. if (inverse)
  688. inverse_matched = true;
  689. else
  690. advance_string_position(state, input.view, code_point);
  691. }
  692. }
  693. ALWAYS_INLINE void OpCode_Compare::compare_general_category(MatchInput const& input, MatchState& state, Unicode::GeneralCategory general_category, bool inverse, bool& inverse_matched)
  694. {
  695. if (state.string_position == input.view.length())
  696. return;
  697. u32 code_point = input.view[state.string_position_in_code_units];
  698. bool equal = Unicode::code_point_has_general_category(code_point, general_category);
  699. if (equal) {
  700. if (inverse)
  701. inverse_matched = true;
  702. else
  703. advance_string_position(state, input.view, code_point);
  704. }
  705. }
  706. ALWAYS_INLINE void OpCode_Compare::compare_script(MatchInput const& input, MatchState& state, Unicode::Script script, bool inverse, bool& inverse_matched)
  707. {
  708. if (state.string_position == input.view.length())
  709. return;
  710. u32 code_point = input.view[state.string_position_in_code_units];
  711. bool equal = Unicode::code_point_has_script(code_point, script);
  712. if (equal) {
  713. if (inverse)
  714. inverse_matched = true;
  715. else
  716. advance_string_position(state, input.view, code_point);
  717. }
  718. }
  719. ALWAYS_INLINE void OpCode_Compare::compare_script_extension(MatchInput const& input, MatchState& state, Unicode::Script script, bool inverse, bool& inverse_matched)
  720. {
  721. if (state.string_position == input.view.length())
  722. return;
  723. u32 code_point = input.view[state.string_position_in_code_units];
  724. bool equal = Unicode::code_point_has_script_extension(code_point, script);
  725. if (equal) {
  726. if (inverse)
  727. inverse_matched = true;
  728. else
  729. advance_string_position(state, input.view, code_point);
  730. }
  731. }
  732. DeprecatedString OpCode_Compare::arguments_string() const
  733. {
  734. return DeprecatedString::formatted("argc={}, args={} ", arguments_count(), arguments_size());
  735. }
  736. Vector<CompareTypeAndValuePair> OpCode_Compare::flat_compares() const
  737. {
  738. Vector<CompareTypeAndValuePair> result;
  739. size_t offset { state().instruction_position + 3 };
  740. for (size_t i = 0; i < arguments_count(); ++i) {
  741. auto compare_type = (CharacterCompareType)m_bytecode->at(offset++);
  742. if (compare_type == CharacterCompareType::Char) {
  743. auto ch = m_bytecode->at(offset++);
  744. result.append({ compare_type, ch });
  745. } else if (compare_type == CharacterCompareType::Reference) {
  746. auto ref = m_bytecode->at(offset++);
  747. result.append({ compare_type, ref });
  748. } else if (compare_type == CharacterCompareType::String) {
  749. auto& length = m_bytecode->at(offset++);
  750. if (length > 0)
  751. result.append({ compare_type, m_bytecode->at(offset) });
  752. StringBuilder str_builder;
  753. offset += length;
  754. } else if (compare_type == CharacterCompareType::CharClass) {
  755. auto character_class = m_bytecode->at(offset++);
  756. result.append({ compare_type, character_class });
  757. } else if (compare_type == CharacterCompareType::CharRange) {
  758. auto value = m_bytecode->at(offset++);
  759. result.append({ compare_type, value });
  760. } else if (compare_type == CharacterCompareType::LookupTable) {
  761. auto count = m_bytecode->at(offset++);
  762. for (size_t i = 0; i < count; ++i)
  763. result.append({ CharacterCompareType::CharRange, m_bytecode->at(offset++) });
  764. } else if (compare_type == CharacterCompareType::GeneralCategory
  765. || compare_type == CharacterCompareType::Property
  766. || compare_type == CharacterCompareType::Script
  767. || compare_type == CharacterCompareType::ScriptExtension) {
  768. auto value = m_bytecode->at(offset++);
  769. result.append({ compare_type, value });
  770. } else {
  771. result.append({ compare_type, 0 });
  772. }
  773. }
  774. return result;
  775. }
  776. Vector<DeprecatedString> OpCode_Compare::variable_arguments_to_deprecated_string(Optional<MatchInput const&> input) const
  777. {
  778. Vector<DeprecatedString> result;
  779. size_t offset { state().instruction_position + 3 };
  780. RegexStringView const& view = ((input.has_value()) ? input.value().view : StringView {});
  781. for (size_t i = 0; i < arguments_count(); ++i) {
  782. auto compare_type = (CharacterCompareType)m_bytecode->at(offset++);
  783. result.empend(DeprecatedString::formatted("type={} [{}]", (size_t)compare_type, character_compare_type_name(compare_type)));
  784. auto string_start_offset = state().string_position_before_match;
  785. if (compare_type == CharacterCompareType::Char) {
  786. auto ch = m_bytecode->at(offset++);
  787. auto is_ascii = is_ascii_printable(ch);
  788. if (is_ascii)
  789. result.empend(DeprecatedString::formatted(" value='{:c}'", static_cast<char>(ch)));
  790. else
  791. result.empend(DeprecatedString::formatted(" value={:x}", ch));
  792. if (!view.is_null() && view.length() > string_start_offset) {
  793. if (is_ascii) {
  794. result.empend(DeprecatedString::formatted(
  795. " compare against: '{}'",
  796. view.substring_view(string_start_offset, string_start_offset > view.length() ? 0 : 1).to_deprecated_string()));
  797. } else {
  798. auto str = view.substring_view(string_start_offset, string_start_offset > view.length() ? 0 : 1).to_deprecated_string();
  799. u8 buf[8] { 0 };
  800. __builtin_memcpy(buf, str.characters(), min(str.length(), sizeof(buf)));
  801. result.empend(DeprecatedString::formatted(" compare against: {:x},{:x},{:x},{:x},{:x},{:x},{:x},{:x}",
  802. buf[0], buf[1], buf[2], buf[3], buf[4], buf[5], buf[6], buf[7]));
  803. }
  804. }
  805. } else if (compare_type == CharacterCompareType::Reference) {
  806. auto ref = m_bytecode->at(offset++);
  807. result.empend(DeprecatedString::formatted(" number={}", ref));
  808. if (input.has_value()) {
  809. if (state().capture_group_matches.size() > input->match_index) {
  810. auto& match = state().capture_group_matches[input->match_index];
  811. if (match.size() > ref) {
  812. auto& group = match[ref];
  813. result.empend(DeprecatedString::formatted(" left={}", group.left_column));
  814. result.empend(DeprecatedString::formatted(" right={}", group.left_column + group.view.length_in_code_units()));
  815. result.empend(DeprecatedString::formatted(" contents='{}'", group.view));
  816. } else {
  817. result.empend(DeprecatedString::formatted(" (invalid ref, max={})", match.size() - 1));
  818. }
  819. } else {
  820. result.empend(DeprecatedString::formatted(" (invalid index {}, max={})", input->match_index, state().capture_group_matches.size() - 1));
  821. }
  822. }
  823. } else if (compare_type == CharacterCompareType::String) {
  824. auto& length = m_bytecode->at(offset++);
  825. StringBuilder str_builder;
  826. for (size_t i = 0; i < length; ++i)
  827. str_builder.append(m_bytecode->at(offset++));
  828. result.empend(DeprecatedString::formatted(" value=\"{}\"", str_builder.string_view().substring_view(0, length)));
  829. if (!view.is_null() && view.length() > state().string_position)
  830. result.empend(DeprecatedString::formatted(
  831. " compare against: \"{}\"",
  832. input.value().view.substring_view(string_start_offset, string_start_offset + length > view.length() ? 0 : length).to_deprecated_string()));
  833. } else if (compare_type == CharacterCompareType::CharClass) {
  834. auto character_class = (CharClass)m_bytecode->at(offset++);
  835. result.empend(DeprecatedString::formatted(" ch_class={} [{}]", (size_t)character_class, character_class_name(character_class)));
  836. if (!view.is_null() && view.length() > state().string_position)
  837. result.empend(DeprecatedString::formatted(
  838. " compare against: '{}'",
  839. input.value().view.substring_view(string_start_offset, state().string_position > view.length() ? 0 : 1).to_deprecated_string()));
  840. } else if (compare_type == CharacterCompareType::CharRange) {
  841. auto value = (CharRange)m_bytecode->at(offset++);
  842. result.empend(DeprecatedString::formatted(" ch_range={:x}-{:x}", value.from, value.to));
  843. if (!view.is_null() && view.length() > state().string_position)
  844. result.empend(DeprecatedString::formatted(
  845. " compare against: '{}'",
  846. input.value().view.substring_view(string_start_offset, state().string_position > view.length() ? 0 : 1).to_deprecated_string()));
  847. } else if (compare_type == CharacterCompareType::LookupTable) {
  848. auto count = m_bytecode->at(offset++);
  849. for (size_t j = 0; j < count; ++j) {
  850. auto range = (CharRange)m_bytecode->at(offset++);
  851. result.append(DeprecatedString::formatted(" {:x}-{:x}", range.from, range.to));
  852. }
  853. if (!view.is_null() && view.length() > state().string_position)
  854. result.empend(DeprecatedString::formatted(
  855. " compare against: '{}'",
  856. input.value().view.substring_view(string_start_offset, state().string_position > view.length() ? 0 : 1).to_deprecated_string()));
  857. } else if (compare_type == CharacterCompareType::GeneralCategory
  858. || compare_type == CharacterCompareType::Property
  859. || compare_type == CharacterCompareType::Script
  860. || compare_type == CharacterCompareType::ScriptExtension) {
  861. auto value = m_bytecode->at(offset++);
  862. result.empend(DeprecatedString::formatted(" value={}", value));
  863. }
  864. }
  865. return result;
  866. }
  867. ALWAYS_INLINE ExecutionResult OpCode_Repeat::execute(MatchInput const&, MatchState& state) const
  868. {
  869. VERIFY(count() > 0);
  870. if (id() >= state.repetition_marks.size())
  871. state.repetition_marks.resize(id() + 1);
  872. auto& repetition_mark = state.repetition_marks.at(id());
  873. if (repetition_mark == count() - 1) {
  874. repetition_mark = 0;
  875. } else {
  876. state.instruction_position -= offset() + size();
  877. ++repetition_mark;
  878. }
  879. return ExecutionResult::Continue;
  880. }
  881. ALWAYS_INLINE ExecutionResult OpCode_ResetRepeat::execute(MatchInput const&, MatchState& state) const
  882. {
  883. if (id() >= state.repetition_marks.size())
  884. state.repetition_marks.resize(id() + 1);
  885. state.repetition_marks.at(id()) = 0;
  886. return ExecutionResult::Continue;
  887. }
  888. ALWAYS_INLINE ExecutionResult OpCode_Checkpoint::execute(MatchInput const& input, MatchState& state) const
  889. {
  890. input.checkpoints.set(state.instruction_position, state.string_position);
  891. return ExecutionResult::Continue;
  892. }
  893. ALWAYS_INLINE ExecutionResult OpCode_JumpNonEmpty::execute(MatchInput const& input, MatchState& state) const
  894. {
  895. u64 current_position = state.string_position;
  896. auto checkpoint_ip = state.instruction_position + size() + checkpoint();
  897. auto checkpoint_position = input.checkpoints.find(checkpoint_ip);
  898. if (checkpoint_position != input.checkpoints.end() && checkpoint_position->value != current_position) {
  899. auto form = this->form();
  900. if (form == OpCodeId::Jump) {
  901. state.instruction_position += offset();
  902. return ExecutionResult::Continue;
  903. }
  904. state.fork_at_position = state.instruction_position + size() + offset();
  905. if (form == OpCodeId::ForkJump) {
  906. state.forks_since_last_save++;
  907. return ExecutionResult::Fork_PrioHigh;
  908. }
  909. if (form == OpCodeId::ForkStay) {
  910. state.forks_since_last_save++;
  911. return ExecutionResult::Fork_PrioLow;
  912. }
  913. if (form == OpCodeId::ForkReplaceStay) {
  914. input.fork_to_replace = state.instruction_position;
  915. return ExecutionResult::Fork_PrioLow;
  916. }
  917. if (form == OpCodeId::ForkReplaceJump) {
  918. input.fork_to_replace = state.instruction_position;
  919. return ExecutionResult::Fork_PrioHigh;
  920. }
  921. }
  922. return ExecutionResult::Continue;
  923. }
  924. }