RegexByteCode.h 29 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789
  1. /*
  2. * Copyright (c) 2020, Emanuel Sprung <emanuel.sprung@gmail.com>
  3. *
  4. * SPDX-License-Identifier: BSD-2-Clause
  5. */
  6. #pragma once
  7. #include "RegexMatch.h"
  8. #include "RegexOptions.h"
  9. #include <AK/Format.h>
  10. #include <AK/Forward.h>
  11. #include <AK/HashMap.h>
  12. #include <AK/NonnullOwnPtr.h>
  13. #include <AK/OwnPtr.h>
  14. #include <AK/Traits.h>
  15. #include <AK/TypeCasts.h>
  16. #include <AK/Types.h>
  17. #include <AK/Vector.h>
  18. #include <LibUnicode/Forward.h>
  19. namespace regex {
  20. using ByteCodeValueType = u64;
  21. #define ENUMERATE_OPCODES \
  22. __ENUMERATE_OPCODE(Compare) \
  23. __ENUMERATE_OPCODE(Jump) \
  24. __ENUMERATE_OPCODE(ForkJump) \
  25. __ENUMERATE_OPCODE(ForkStay) \
  26. __ENUMERATE_OPCODE(FailForks) \
  27. __ENUMERATE_OPCODE(SaveLeftCaptureGroup) \
  28. __ENUMERATE_OPCODE(SaveRightCaptureGroup) \
  29. __ENUMERATE_OPCODE(SaveLeftNamedCaptureGroup) \
  30. __ENUMERATE_OPCODE(SaveRightNamedCaptureGroup) \
  31. __ENUMERATE_OPCODE(CheckBegin) \
  32. __ENUMERATE_OPCODE(CheckEnd) \
  33. __ENUMERATE_OPCODE(CheckBoundary) \
  34. __ENUMERATE_OPCODE(Save) \
  35. __ENUMERATE_OPCODE(Restore) \
  36. __ENUMERATE_OPCODE(GoBack) \
  37. __ENUMERATE_OPCODE(ClearCaptureGroup) \
  38. __ENUMERATE_OPCODE(ClearNamedCaptureGroup) \
  39. __ENUMERATE_OPCODE(Exit)
  40. // clang-format off
  41. enum class OpCodeId : ByteCodeValueType {
  42. #define __ENUMERATE_OPCODE(x) x,
  43. ENUMERATE_OPCODES
  44. #undef __ENUMERATE_OPCODE
  45. First = Compare,
  46. Last = Exit,
  47. };
  48. // clang-format on
  49. #define ENUMERATE_CHARACTER_COMPARE_TYPES \
  50. __ENUMERATE_CHARACTER_COMPARE_TYPE(Undefined) \
  51. __ENUMERATE_CHARACTER_COMPARE_TYPE(Inverse) \
  52. __ENUMERATE_CHARACTER_COMPARE_TYPE(TemporaryInverse) \
  53. __ENUMERATE_CHARACTER_COMPARE_TYPE(AnyChar) \
  54. __ENUMERATE_CHARACTER_COMPARE_TYPE(Char) \
  55. __ENUMERATE_CHARACTER_COMPARE_TYPE(String) \
  56. __ENUMERATE_CHARACTER_COMPARE_TYPE(CharClass) \
  57. __ENUMERATE_CHARACTER_COMPARE_TYPE(CharRange) \
  58. __ENUMERATE_CHARACTER_COMPARE_TYPE(Reference) \
  59. __ENUMERATE_CHARACTER_COMPARE_TYPE(NamedReference) \
  60. __ENUMERATE_CHARACTER_COMPARE_TYPE(Property) \
  61. __ENUMERATE_CHARACTER_COMPARE_TYPE(GeneralCategory) \
  62. __ENUMERATE_CHARACTER_COMPARE_TYPE(RangeExpressionDummy)
  63. enum class CharacterCompareType : ByteCodeValueType {
  64. #define __ENUMERATE_CHARACTER_COMPARE_TYPE(x) x,
  65. ENUMERATE_CHARACTER_COMPARE_TYPES
  66. #undef __ENUMERATE_CHARACTER_COMPARE_TYPE
  67. };
  68. #define ENUMERATE_CHARACTER_CLASSES \
  69. __ENUMERATE_CHARACTER_CLASS(Alnum) \
  70. __ENUMERATE_CHARACTER_CLASS(Cntrl) \
  71. __ENUMERATE_CHARACTER_CLASS(Lower) \
  72. __ENUMERATE_CHARACTER_CLASS(Space) \
  73. __ENUMERATE_CHARACTER_CLASS(Alpha) \
  74. __ENUMERATE_CHARACTER_CLASS(Digit) \
  75. __ENUMERATE_CHARACTER_CLASS(Print) \
  76. __ENUMERATE_CHARACTER_CLASS(Upper) \
  77. __ENUMERATE_CHARACTER_CLASS(Blank) \
  78. __ENUMERATE_CHARACTER_CLASS(Graph) \
  79. __ENUMERATE_CHARACTER_CLASS(Punct) \
  80. __ENUMERATE_CHARACTER_CLASS(Word) \
  81. __ENUMERATE_CHARACTER_CLASS(Xdigit)
  82. enum class CharClass : ByteCodeValueType {
  83. #define __ENUMERATE_CHARACTER_CLASS(x) x,
  84. ENUMERATE_CHARACTER_CLASSES
  85. #undef __ENUMERATE_CHARACTER_CLASS
  86. };
  87. #define ENUMERATE_BOUNDARY_CHECK_TYPES \
  88. __ENUMERATE_BOUNDARY_CHECK_TYPE(Word) \
  89. __ENUMERATE_BOUNDARY_CHECK_TYPE(NonWord)
  90. enum class BoundaryCheckType : ByteCodeValueType {
  91. #define __ENUMERATE_BOUNDARY_CHECK_TYPE(x) x,
  92. ENUMERATE_BOUNDARY_CHECK_TYPES
  93. #undef __ENUMERATE_BOUNDARY_CHECK_TYPE
  94. };
  95. struct CharRange {
  96. u32 const from;
  97. u32 const to;
  98. CharRange(u64 value)
  99. : from(value >> 32)
  100. , to(value & 0xffffffff)
  101. {
  102. }
  103. CharRange(u32 from, u32 to)
  104. : from(from)
  105. , to(to)
  106. {
  107. }
  108. operator ByteCodeValueType() const { return ((u64)from << 32) | to; }
  109. };
  110. struct CompareTypeAndValuePair {
  111. CharacterCompareType type;
  112. ByteCodeValueType value;
  113. };
  114. class OpCode;
  115. class ByteCode : public Vector<ByteCodeValueType> {
  116. public:
  117. ByteCode()
  118. {
  119. ensure_opcodes_initialized();
  120. }
  121. ByteCode(ByteCode const&) = default;
  122. virtual ~ByteCode() = default;
  123. ByteCode& operator=(ByteCode&&) = default;
  124. void insert_bytecode_compare_values(Vector<CompareTypeAndValuePair>&& pairs)
  125. {
  126. ByteCode bytecode;
  127. bytecode.empend(static_cast<ByteCodeValueType>(OpCodeId::Compare));
  128. bytecode.empend(pairs.size()); // number of arguments
  129. ByteCode arguments;
  130. for (auto& value : pairs) {
  131. VERIFY(value.type != CharacterCompareType::RangeExpressionDummy);
  132. VERIFY(value.type != CharacterCompareType::Undefined);
  133. VERIFY(value.type != CharacterCompareType::String);
  134. VERIFY(value.type != CharacterCompareType::NamedReference);
  135. arguments.append((ByteCodeValueType)value.type);
  136. if (value.type != CharacterCompareType::Inverse && value.type != CharacterCompareType::AnyChar && value.type != CharacterCompareType::TemporaryInverse)
  137. arguments.append(move(value.value));
  138. }
  139. bytecode.empend(arguments.size()); // size of arguments
  140. bytecode.extend(move(arguments));
  141. extend(move(bytecode));
  142. }
  143. void insert_bytecode_check_boundary(BoundaryCheckType type)
  144. {
  145. ByteCode bytecode;
  146. bytecode.empend((ByteCodeValueType)OpCodeId::CheckBoundary);
  147. bytecode.empend((ByteCodeValueType)type);
  148. extend(move(bytecode));
  149. }
  150. void insert_bytecode_clear_capture_group(size_t index)
  151. {
  152. empend(static_cast<ByteCodeValueType>(OpCodeId::ClearCaptureGroup));
  153. empend(index);
  154. }
  155. void insert_bytecode_clear_named_capture_group(StringView name)
  156. {
  157. empend(static_cast<ByteCodeValueType>(OpCodeId::ClearNamedCaptureGroup));
  158. empend(reinterpret_cast<ByteCodeValueType>(name.characters_without_null_termination()));
  159. empend(name.length());
  160. }
  161. void insert_bytecode_compare_string(StringView view)
  162. {
  163. ByteCode bytecode;
  164. bytecode.empend(static_cast<ByteCodeValueType>(OpCodeId::Compare));
  165. bytecode.empend(static_cast<u64>(1)); // number of arguments
  166. ByteCode arguments;
  167. arguments.empend(static_cast<ByteCodeValueType>(CharacterCompareType::String));
  168. arguments.insert_string(view);
  169. bytecode.empend(arguments.size()); // size of arguments
  170. bytecode.extend(move(arguments));
  171. extend(move(bytecode));
  172. }
  173. void insert_bytecode_compare_named_reference(StringView name)
  174. {
  175. ByteCode bytecode;
  176. bytecode.empend(static_cast<ByteCodeValueType>(OpCodeId::Compare));
  177. bytecode.empend(static_cast<u64>(1)); // number of arguments
  178. ByteCode arguments;
  179. arguments.empend(static_cast<ByteCodeValueType>(CharacterCompareType::NamedReference));
  180. arguments.empend(reinterpret_cast<ByteCodeValueType>(name.characters_without_null_termination()));
  181. arguments.empend(name.length());
  182. bytecode.empend(arguments.size()); // size of arguments
  183. bytecode.extend(move(arguments));
  184. extend(move(bytecode));
  185. }
  186. void insert_bytecode_group_capture_left(size_t capture_groups_count)
  187. {
  188. empend(static_cast<ByteCodeValueType>(OpCodeId::SaveLeftCaptureGroup));
  189. empend(capture_groups_count);
  190. }
  191. void insert_bytecode_group_capture_left(StringView const& name)
  192. {
  193. empend(static_cast<ByteCodeValueType>(OpCodeId::SaveLeftNamedCaptureGroup));
  194. empend(reinterpret_cast<ByteCodeValueType>(name.characters_without_null_termination()));
  195. empend(name.length());
  196. }
  197. void insert_bytecode_group_capture_right(size_t capture_groups_count)
  198. {
  199. empend(static_cast<ByteCodeValueType>(OpCodeId::SaveRightCaptureGroup));
  200. empend(capture_groups_count);
  201. }
  202. void insert_bytecode_group_capture_right(StringView const& name)
  203. {
  204. empend(static_cast<ByteCodeValueType>(OpCodeId::SaveRightNamedCaptureGroup));
  205. empend(reinterpret_cast<ByteCodeValueType>(name.characters_without_null_termination()));
  206. empend(name.length());
  207. }
  208. enum class LookAroundType {
  209. LookAhead,
  210. LookBehind,
  211. NegatedLookAhead,
  212. NegatedLookBehind,
  213. };
  214. void insert_bytecode_lookaround(ByteCode&& lookaround_body, LookAroundType type, size_t match_length = 0)
  215. {
  216. // FIXME: The save stack will grow infinitely with repeated failures
  217. // as we do not discard that on failure (we don't necessarily know how many to pop with the current architecture).
  218. switch (type) {
  219. case LookAroundType::LookAhead: {
  220. // SAVE
  221. // REGEXP BODY
  222. // RESTORE
  223. empend((ByteCodeValueType)OpCodeId::Save);
  224. extend(move(lookaround_body));
  225. empend((ByteCodeValueType)OpCodeId::Restore);
  226. return;
  227. }
  228. case LookAroundType::NegatedLookAhead: {
  229. // JUMP _A
  230. // LABEL _L
  231. // REGEXP BODY
  232. // FAIL 2
  233. // LABEL _A
  234. // SAVE
  235. // FORKJUMP _L
  236. // RESTORE
  237. auto body_length = lookaround_body.size();
  238. empend((ByteCodeValueType)OpCodeId::Jump);
  239. empend((ByteCodeValueType)body_length + 2); // JUMP to label _A
  240. extend(move(lookaround_body));
  241. empend((ByteCodeValueType)OpCodeId::FailForks);
  242. empend((ByteCodeValueType)2); // Fail two forks
  243. empend((ByteCodeValueType)OpCodeId::Save);
  244. empend((ByteCodeValueType)OpCodeId::ForkJump);
  245. empend((ByteCodeValueType) - (body_length + 5)); // JUMP to label _L
  246. empend((ByteCodeValueType)OpCodeId::Restore);
  247. return;
  248. }
  249. case LookAroundType::LookBehind:
  250. // SAVE
  251. // GOBACK match_length(BODY)
  252. // REGEXP BODY
  253. // RESTORE
  254. empend((ByteCodeValueType)OpCodeId::Save);
  255. empend((ByteCodeValueType)OpCodeId::GoBack);
  256. empend((ByteCodeValueType)match_length);
  257. extend(move(lookaround_body));
  258. empend((ByteCodeValueType)OpCodeId::Restore);
  259. return;
  260. case LookAroundType::NegatedLookBehind: {
  261. // JUMP _A
  262. // LABEL _L
  263. // GOBACK match_length(BODY)
  264. // REGEXP BODY
  265. // FAIL 2
  266. // LABEL _A
  267. // SAVE
  268. // FORKJUMP _L
  269. // RESTORE
  270. auto body_length = lookaround_body.size();
  271. empend((ByteCodeValueType)OpCodeId::Jump);
  272. empend((ByteCodeValueType)body_length + 4); // JUMP to label _A
  273. empend((ByteCodeValueType)OpCodeId::GoBack);
  274. empend((ByteCodeValueType)match_length);
  275. extend(move(lookaround_body));
  276. empend((ByteCodeValueType)OpCodeId::FailForks);
  277. empend((ByteCodeValueType)2); // Fail two forks
  278. empend((ByteCodeValueType)OpCodeId::Save);
  279. empend((ByteCodeValueType)OpCodeId::ForkJump);
  280. empend((ByteCodeValueType) - (body_length + 7)); // JUMP to label _L
  281. empend((ByteCodeValueType)OpCodeId::Restore);
  282. return;
  283. }
  284. }
  285. VERIFY_NOT_REACHED();
  286. }
  287. void insert_bytecode_alternation(ByteCode&& left, ByteCode&& right)
  288. {
  289. // FORKJUMP _ALT
  290. // REGEXP ALT2
  291. // JUMP _END
  292. // LABEL _ALT
  293. // REGEXP ALT1
  294. // LABEL _END
  295. ByteCode byte_code;
  296. empend(static_cast<ByteCodeValueType>(OpCodeId::ForkJump));
  297. empend(right.size() + 2); // Jump to the _ALT label
  298. for (auto& op : right)
  299. append(move(op));
  300. empend(static_cast<ByteCodeValueType>(OpCodeId::Jump));
  301. empend(left.size()); // Jump to the _END label
  302. // LABEL _ALT = bytecode.size() + 2
  303. for (auto& op : left)
  304. append(move(op));
  305. // LABEL _END = alterantive_bytecode.size
  306. }
  307. static void transform_bytecode_repetition_min_max(ByteCode& bytecode_to_repeat, size_t minimum, Optional<size_t> maximum, bool greedy = true)
  308. {
  309. ByteCode new_bytecode;
  310. new_bytecode.insert_bytecode_repetition_n(bytecode_to_repeat, minimum);
  311. if (maximum.has_value()) {
  312. auto jump_kind = static_cast<ByteCodeValueType>(greedy ? OpCodeId::ForkStay : OpCodeId::ForkJump);
  313. if (maximum.value() > minimum) {
  314. auto diff = maximum.value() - minimum;
  315. new_bytecode.empend(jump_kind);
  316. new_bytecode.empend(diff * (bytecode_to_repeat.size() + 2)); // Jump to the _END label
  317. for (size_t i = 0; i < diff; ++i) {
  318. new_bytecode.extend(bytecode_to_repeat);
  319. new_bytecode.empend(jump_kind);
  320. new_bytecode.empend((diff - i - 1) * (bytecode_to_repeat.size() + 2)); // Jump to the _END label
  321. }
  322. }
  323. } else {
  324. // no maximum value set, repeat finding if possible
  325. auto jump_kind = static_cast<ByteCodeValueType>(greedy ? OpCodeId::ForkJump : OpCodeId::ForkStay);
  326. new_bytecode.empend(jump_kind);
  327. new_bytecode.empend(-bytecode_to_repeat.size() - 2); // Jump to the last iteration
  328. }
  329. bytecode_to_repeat = move(new_bytecode);
  330. }
  331. void insert_bytecode_repetition_n(ByteCode& bytecode_to_repeat, size_t n)
  332. {
  333. for (size_t i = 0; i < n; ++i)
  334. extend(bytecode_to_repeat);
  335. }
  336. static void transform_bytecode_repetition_min_one(ByteCode& bytecode_to_repeat, bool greedy)
  337. {
  338. // LABEL _START = -bytecode_to_repeat.size()
  339. // REGEXP
  340. // FORKSTAY _START (FORKJUMP -> Greedy)
  341. if (greedy)
  342. bytecode_to_repeat.empend(static_cast<ByteCodeValueType>(OpCodeId::ForkJump));
  343. else
  344. bytecode_to_repeat.empend(static_cast<ByteCodeValueType>(OpCodeId::ForkStay));
  345. bytecode_to_repeat.empend(-(bytecode_to_repeat.size() + 1)); // Jump to the _START label
  346. }
  347. static void transform_bytecode_repetition_any(ByteCode& bytecode_to_repeat, bool greedy)
  348. {
  349. // LABEL _START
  350. // FORKJUMP _END (FORKSTAY -> Greedy)
  351. // REGEXP
  352. // JUMP _START
  353. // LABEL _END
  354. // LABEL _START = m_bytes.size();
  355. ByteCode bytecode;
  356. if (greedy)
  357. bytecode.empend(static_cast<ByteCodeValueType>(OpCodeId::ForkStay));
  358. else
  359. bytecode.empend(static_cast<ByteCodeValueType>(OpCodeId::ForkJump));
  360. bytecode.empend(bytecode_to_repeat.size() + 2); // Jump to the _END label
  361. for (auto& op : bytecode_to_repeat)
  362. bytecode.append(move(op));
  363. bytecode.empend(static_cast<ByteCodeValueType>(OpCodeId::Jump));
  364. bytecode.empend(-bytecode.size() - 1); // Jump to the _START label
  365. // LABEL _END = bytecode.size()
  366. bytecode_to_repeat = move(bytecode);
  367. }
  368. static void transform_bytecode_repetition_zero_or_one(ByteCode& bytecode_to_repeat, bool greedy)
  369. {
  370. // FORKJUMP _END (FORKSTAY -> Greedy)
  371. // REGEXP
  372. // LABEL _END
  373. ByteCode bytecode;
  374. if (greedy)
  375. bytecode.empend(static_cast<ByteCodeValueType>(OpCodeId::ForkStay));
  376. else
  377. bytecode.empend(static_cast<ByteCodeValueType>(OpCodeId::ForkJump));
  378. bytecode.empend(bytecode_to_repeat.size()); // Jump to the _END label
  379. for (auto& op : bytecode_to_repeat)
  380. bytecode.append(move(op));
  381. // LABEL _END = bytecode.size()
  382. bytecode_to_repeat = move(bytecode);
  383. }
  384. OpCode& get_opcode(MatchState& state) const;
  385. private:
  386. void insert_string(StringView const& view)
  387. {
  388. empend((ByteCodeValueType)view.length());
  389. for (size_t i = 0; i < view.length(); ++i)
  390. empend((ByteCodeValueType)view[i]);
  391. }
  392. void ensure_opcodes_initialized();
  393. ALWAYS_INLINE OpCode& get_opcode_by_id(OpCodeId id) const;
  394. static OwnPtr<OpCode> s_opcodes[(size_t)OpCodeId::Last + 1];
  395. static bool s_opcodes_initialized;
  396. };
  397. #define ENUMERATE_EXECUTION_RESULTS \
  398. __ENUMERATE_EXECUTION_RESULT(Continue) \
  399. __ENUMERATE_EXECUTION_RESULT(Fork_PrioHigh) \
  400. __ENUMERATE_EXECUTION_RESULT(Fork_PrioLow) \
  401. __ENUMERATE_EXECUTION_RESULT(Failed) \
  402. __ENUMERATE_EXECUTION_RESULT(Failed_ExecuteLowPrioForks) \
  403. __ENUMERATE_EXECUTION_RESULT(Succeeded)
  404. enum class ExecutionResult : u8 {
  405. #define __ENUMERATE_EXECUTION_RESULT(x) x,
  406. ENUMERATE_EXECUTION_RESULTS
  407. #undef __ENUMERATE_EXECUTION_RESULT
  408. };
  409. char const* execution_result_name(ExecutionResult result);
  410. char const* opcode_id_name(OpCodeId opcode_id);
  411. char const* boundary_check_type_name(BoundaryCheckType);
  412. char const* character_compare_type_name(CharacterCompareType result);
  413. char const* execution_result_name(ExecutionResult result);
  414. class OpCode {
  415. public:
  416. OpCode() = default;
  417. virtual ~OpCode() = default;
  418. virtual OpCodeId opcode_id() const = 0;
  419. virtual size_t size() const = 0;
  420. virtual ExecutionResult execute(MatchInput const& input, MatchState& state, MatchOutput& output) const = 0;
  421. ALWAYS_INLINE ByteCodeValueType argument(size_t offset) const
  422. {
  423. VERIFY(state().instruction_position + offset <= m_bytecode->size());
  424. return m_bytecode->at(state().instruction_position + 1 + offset);
  425. }
  426. ALWAYS_INLINE char const* name() const;
  427. static char const* name(OpCodeId const);
  428. ALWAYS_INLINE void set_state(MatchState& state) { m_state = &state; }
  429. ALWAYS_INLINE void set_bytecode(ByteCode& bytecode) { m_bytecode = &bytecode; }
  430. ALWAYS_INLINE MatchState const& state() const
  431. {
  432. VERIFY(m_state);
  433. return *m_state;
  434. }
  435. String const to_string() const
  436. {
  437. return String::formatted("[{:#02X}] {}", (int)opcode_id(), name(opcode_id()));
  438. }
  439. virtual String const arguments_string() const = 0;
  440. ALWAYS_INLINE ByteCode const& bytecode() const { return *m_bytecode; }
  441. protected:
  442. ByteCode* m_bytecode { nullptr };
  443. MatchState* m_state { nullptr };
  444. };
  445. class OpCode_Exit final : public OpCode {
  446. public:
  447. ExecutionResult execute(MatchInput const& input, MatchState& state, MatchOutput& output) const override;
  448. ALWAYS_INLINE OpCodeId opcode_id() const override { return OpCodeId::Exit; }
  449. ALWAYS_INLINE size_t size() const override { return 1; }
  450. String const arguments_string() const override { return ""; }
  451. };
  452. class OpCode_FailForks final : public OpCode {
  453. public:
  454. ExecutionResult execute(MatchInput const& input, MatchState& state, MatchOutput& output) const override;
  455. ALWAYS_INLINE OpCodeId opcode_id() const override { return OpCodeId::FailForks; }
  456. ALWAYS_INLINE size_t size() const override { return 2; }
  457. ALWAYS_INLINE size_t count() const { return argument(0); }
  458. String const arguments_string() const override { return String::formatted("count={}", count()); }
  459. };
  460. class OpCode_Save final : public OpCode {
  461. public:
  462. ExecutionResult execute(MatchInput const& input, MatchState& state, MatchOutput& output) const override;
  463. ALWAYS_INLINE OpCodeId opcode_id() const override { return OpCodeId::Save; }
  464. ALWAYS_INLINE size_t size() const override { return 1; }
  465. String const arguments_string() const override { return ""; }
  466. };
  467. class OpCode_Restore final : public OpCode {
  468. public:
  469. ExecutionResult execute(MatchInput const& input, MatchState& state, MatchOutput& output) const override;
  470. ALWAYS_INLINE OpCodeId opcode_id() const override { return OpCodeId::Restore; }
  471. ALWAYS_INLINE size_t size() const override { return 1; }
  472. String const arguments_string() const override { return ""; }
  473. };
  474. class OpCode_GoBack final : public OpCode {
  475. public:
  476. ExecutionResult execute(MatchInput const& input, MatchState& state, MatchOutput& output) const override;
  477. ALWAYS_INLINE OpCodeId opcode_id() const override { return OpCodeId::GoBack; }
  478. ALWAYS_INLINE size_t size() const override { return 2; }
  479. ALWAYS_INLINE size_t count() const { return argument(0); }
  480. String const arguments_string() const override { return String::formatted("count={}", count()); }
  481. };
  482. class OpCode_Jump final : public OpCode {
  483. public:
  484. ExecutionResult execute(MatchInput const& input, MatchState& state, MatchOutput& output) const override;
  485. ALWAYS_INLINE OpCodeId opcode_id() const override { return OpCodeId::Jump; }
  486. ALWAYS_INLINE size_t size() const override { return 2; }
  487. ALWAYS_INLINE ssize_t offset() const { return argument(0); }
  488. String const arguments_string() const override
  489. {
  490. return String::formatted("offset={} [&{}]", offset(), state().instruction_position + size() + offset());
  491. }
  492. };
  493. class OpCode_ForkJump final : public OpCode {
  494. public:
  495. ExecutionResult execute(MatchInput const& input, MatchState& state, MatchOutput& output) const override;
  496. ALWAYS_INLINE OpCodeId opcode_id() const override { return OpCodeId::ForkJump; }
  497. ALWAYS_INLINE size_t size() const override { return 2; }
  498. ALWAYS_INLINE ssize_t offset() const { return argument(0); }
  499. String const arguments_string() const override
  500. {
  501. return String::formatted("offset={} [&{}], sp: {}", offset(), state().instruction_position + size() + offset(), state().string_position);
  502. }
  503. };
  504. class OpCode_ForkStay final : public OpCode {
  505. public:
  506. ExecutionResult execute(MatchInput const& input, MatchState& state, MatchOutput& output) const override;
  507. ALWAYS_INLINE OpCodeId opcode_id() const override { return OpCodeId::ForkStay; }
  508. ALWAYS_INLINE size_t size() const override { return 2; }
  509. ALWAYS_INLINE ssize_t offset() const { return argument(0); }
  510. String const arguments_string() const override
  511. {
  512. return String::formatted("offset={} [&{}], sp: {}", offset(), state().instruction_position + size() + offset(), state().string_position);
  513. }
  514. };
  515. class OpCode_CheckBegin final : public OpCode {
  516. public:
  517. ExecutionResult execute(MatchInput const& input, MatchState& state, MatchOutput& output) const override;
  518. ALWAYS_INLINE OpCodeId opcode_id() const override { return OpCodeId::CheckBegin; }
  519. ALWAYS_INLINE size_t size() const override { return 1; }
  520. String const arguments_string() const override { return ""; }
  521. };
  522. class OpCode_CheckEnd final : public OpCode {
  523. public:
  524. ExecutionResult execute(MatchInput const& input, MatchState& state, MatchOutput& output) const override;
  525. ALWAYS_INLINE OpCodeId opcode_id() const override { return OpCodeId::CheckEnd; }
  526. ALWAYS_INLINE size_t size() const override { return 1; }
  527. String const arguments_string() const override { return ""; }
  528. };
  529. class OpCode_CheckBoundary final : public OpCode {
  530. public:
  531. ExecutionResult execute(MatchInput const& input, MatchState& state, MatchOutput& output) const override;
  532. ALWAYS_INLINE OpCodeId opcode_id() const override { return OpCodeId::CheckBoundary; }
  533. ALWAYS_INLINE size_t size() const override { return 2; }
  534. ALWAYS_INLINE size_t arguments_count() const { return 1; }
  535. ALWAYS_INLINE BoundaryCheckType type() const { return static_cast<BoundaryCheckType>(argument(0)); }
  536. String const arguments_string() const override { return String::formatted("kind={} ({})", (long unsigned int)argument(0), boundary_check_type_name(type())); }
  537. };
  538. class OpCode_ClearCaptureGroup final : public OpCode {
  539. public:
  540. ExecutionResult execute(MatchInput const& input, MatchState& state, MatchOutput& output) const override;
  541. ALWAYS_INLINE OpCodeId opcode_id() const override { return OpCodeId::ClearCaptureGroup; }
  542. ALWAYS_INLINE size_t size() const override { return 2; }
  543. ALWAYS_INLINE size_t id() const { return argument(0); }
  544. String const arguments_string() const override { return String::formatted("id={}", id()); }
  545. };
  546. class OpCode_ClearNamedCaptureGroup final : public OpCode {
  547. public:
  548. ExecutionResult execute(MatchInput const& input, MatchState& state, MatchOutput& output) const override;
  549. ALWAYS_INLINE OpCodeId opcode_id() const override { return OpCodeId::ClearNamedCaptureGroup; }
  550. ALWAYS_INLINE size_t size() const override { return 3; }
  551. ALWAYS_INLINE StringView name() const { return { reinterpret_cast<char*>(argument(0)), length() }; }
  552. ALWAYS_INLINE size_t length() const { return argument(1); }
  553. String const arguments_string() const override
  554. {
  555. return String::formatted("name={}, length={}", name(), length());
  556. }
  557. };
  558. class OpCode_SaveLeftCaptureGroup final : public OpCode {
  559. public:
  560. ExecutionResult execute(MatchInput const& input, MatchState& state, MatchOutput& output) const override;
  561. ALWAYS_INLINE OpCodeId opcode_id() const override { return OpCodeId::SaveLeftCaptureGroup; }
  562. ALWAYS_INLINE size_t size() const override { return 2; }
  563. ALWAYS_INLINE size_t id() const { return argument(0); }
  564. String const arguments_string() const override { return String::formatted("id={}", id()); }
  565. };
  566. class OpCode_SaveRightCaptureGroup final : public OpCode {
  567. public:
  568. ExecutionResult execute(MatchInput const& input, MatchState& state, MatchOutput& output) const override;
  569. ALWAYS_INLINE OpCodeId opcode_id() const override { return OpCodeId::SaveRightCaptureGroup; }
  570. ALWAYS_INLINE size_t size() const override { return 2; }
  571. ALWAYS_INLINE size_t id() const { return argument(0); }
  572. String const arguments_string() const override { return String::formatted("id={}", id()); }
  573. };
  574. class OpCode_SaveLeftNamedCaptureGroup final : public OpCode {
  575. public:
  576. ExecutionResult execute(MatchInput const& input, MatchState& state, MatchOutput& output) const override;
  577. ALWAYS_INLINE OpCodeId opcode_id() const override { return OpCodeId::SaveLeftNamedCaptureGroup; }
  578. ALWAYS_INLINE size_t size() const override { return 3; }
  579. ALWAYS_INLINE StringView name() const { return { reinterpret_cast<char*>(argument(0)), length() }; }
  580. ALWAYS_INLINE size_t length() const { return argument(1); }
  581. String const arguments_string() const override
  582. {
  583. return String::formatted("name={}, length={}", name(), length());
  584. }
  585. };
  586. class OpCode_SaveRightNamedCaptureGroup final : public OpCode {
  587. public:
  588. ExecutionResult execute(MatchInput const& input, MatchState& state, MatchOutput& output) const override;
  589. ALWAYS_INLINE OpCodeId opcode_id() const override { return OpCodeId::SaveRightNamedCaptureGroup; }
  590. ALWAYS_INLINE size_t size() const override { return 3; }
  591. ALWAYS_INLINE StringView name() const { return { reinterpret_cast<char*>(argument(0)), length() }; }
  592. ALWAYS_INLINE size_t length() const { return argument(1); }
  593. String const arguments_string() const override
  594. {
  595. return String::formatted("name={}, length={}", name(), length());
  596. }
  597. };
  598. class OpCode_Compare final : public OpCode {
  599. public:
  600. ExecutionResult execute(MatchInput const& input, MatchState& state, MatchOutput& output) const override;
  601. ALWAYS_INLINE OpCodeId opcode_id() const override { return OpCodeId::Compare; }
  602. ALWAYS_INLINE size_t size() const override { return arguments_size() + 3; }
  603. ALWAYS_INLINE size_t arguments_count() const { return argument(0); }
  604. ALWAYS_INLINE size_t arguments_size() const { return argument(1); }
  605. String const arguments_string() const override;
  606. Vector<String> const variable_arguments_to_string(Optional<MatchInput> input = {}) const;
  607. private:
  608. ALWAYS_INLINE static void compare_char(MatchInput const& input, MatchState& state, u32 ch1, bool inverse, bool& inverse_matched);
  609. ALWAYS_INLINE static bool compare_string(MatchInput const& input, MatchState& state, RegexStringView const& str, bool& had_zero_length_match);
  610. ALWAYS_INLINE static void compare_character_class(MatchInput const& input, MatchState& state, CharClass character_class, u32 ch, bool inverse, bool& inverse_matched);
  611. ALWAYS_INLINE static void compare_character_range(MatchInput const& input, MatchState& state, u32 from, u32 to, u32 ch, bool inverse, bool& inverse_matched);
  612. ALWAYS_INLINE static void compare_property(MatchInput const& input, MatchState& state, Unicode::Property property, bool inverse, bool& inverse_matched);
  613. ALWAYS_INLINE static void compare_general_category(MatchInput const& input, MatchState& state, Unicode::GeneralCategory general_category, bool inverse, bool& inverse_matched);
  614. };
  615. template<typename T>
  616. bool is(OpCode const&);
  617. template<typename T>
  618. ALWAYS_INLINE bool is(OpCode const&)
  619. {
  620. return false;
  621. }
  622. template<typename T>
  623. ALWAYS_INLINE bool is(OpCode const* opcode)
  624. {
  625. return is<T>(*opcode);
  626. }
  627. template<>
  628. ALWAYS_INLINE bool is<OpCode_ForkStay>(OpCode const& opcode)
  629. {
  630. return opcode.opcode_id() == OpCodeId::ForkStay;
  631. }
  632. template<>
  633. ALWAYS_INLINE bool is<OpCode_Exit>(OpCode const& opcode)
  634. {
  635. return opcode.opcode_id() == OpCodeId::Exit;
  636. }
  637. template<>
  638. ALWAYS_INLINE bool is<OpCode_Compare>(OpCode const& opcode)
  639. {
  640. return opcode.opcode_id() == OpCodeId::Compare;
  641. }
  642. template<typename T>
  643. ALWAYS_INLINE T const& to(OpCode const& opcode)
  644. {
  645. return verify_cast<T>(opcode);
  646. }
  647. template<typename T>
  648. ALWAYS_INLINE T* to(OpCode* opcode)
  649. {
  650. return verify_cast<T>(opcode);
  651. }
  652. template<typename T>
  653. ALWAYS_INLINE T const* to(OpCode const* opcode)
  654. {
  655. return verify_cast<T>(opcode);
  656. }
  657. template<typename T>
  658. ALWAYS_INLINE T& to(OpCode& opcode)
  659. {
  660. return verify_cast<T>(opcode);
  661. }
  662. }