RegexMatch.h 21 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678
  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 "Forward.h"
  8. #include "RegexOptions.h"
  9. #include <AK/Error.h>
  10. #include <AK/DeprecatedFlyString.h>
  11. #include <AK/DeprecatedString.h>
  12. #include <AK/HashMap.h>
  13. #include <AK/MemMem.h>
  14. #include <AK/RedBlackTree.h>
  15. #include <AK/StringBuilder.h>
  16. #include <AK/StringView.h>
  17. #include <AK/Utf16View.h>
  18. #include <AK/Utf32View.h>
  19. #include <AK/Utf8View.h>
  20. #include <AK/Variant.h>
  21. #include <AK/Vector.h>
  22. namespace regex {
  23. template<typename T>
  24. class COWVector {
  25. struct Detail : RefCounted<Detail> {
  26. Vector<T> m_members;
  27. };
  28. public:
  29. COWVector()
  30. : m_detail(make_ref_counted<Detail>())
  31. {
  32. }
  33. COWVector(COWVector const&) = default;
  34. COWVector(COWVector&&) = default;
  35. COWVector& operator=(COWVector const&) = default;
  36. COWVector& operator=(COWVector&&) = default;
  37. Vector<T> release() &&
  38. {
  39. if (m_detail->ref_count() == 1)
  40. return exchange(m_detail->m_members, Vector<T>());
  41. return m_detail->m_members;
  42. }
  43. void append(T const& value)
  44. {
  45. return append(T { value });
  46. }
  47. void append(T&& value)
  48. {
  49. copy();
  50. m_detail->m_members.append(move(value));
  51. }
  52. void resize(size_t size)
  53. {
  54. copy();
  55. m_detail->m_members.resize(size);
  56. }
  57. void ensure_capacity(size_t capacity)
  58. {
  59. if (m_detail->m_members.capacity() >= capacity)
  60. return;
  61. copy();
  62. m_detail->m_members.ensure_capacity(capacity);
  63. }
  64. template<typename... Args>
  65. void empend(Args&&... args)
  66. {
  67. copy();
  68. m_detail->m_members.empend(forward<Args>(args)...);
  69. }
  70. void clear()
  71. {
  72. if (m_detail->ref_count() > 1)
  73. m_detail = make_ref_counted<Detail>();
  74. else
  75. m_detail->m_members.clear();
  76. }
  77. T& at(size_t index)
  78. {
  79. // We're handing out a mutable reference, so make sure we own the data exclusively.
  80. copy();
  81. return m_detail->m_members.at(index);
  82. }
  83. T const& at(size_t index) const
  84. {
  85. return m_detail->m_members.at(index);
  86. }
  87. T& operator[](size_t index)
  88. {
  89. // We're handing out a mutable reference, so make sure we own the data exclusively.
  90. copy();
  91. return m_detail->m_members[index];
  92. }
  93. T const& operator[](size_t index) const
  94. {
  95. return m_detail->m_members[index];
  96. }
  97. size_t capacity() const
  98. {
  99. return m_detail->m_members.capacity();
  100. }
  101. size_t size() const
  102. {
  103. return m_detail->m_members.size();
  104. }
  105. bool is_empty() const
  106. {
  107. return m_detail->m_members.is_empty();
  108. }
  109. T const& first() const
  110. {
  111. return m_detail->m_members.first();
  112. }
  113. T const& last() const
  114. {
  115. return m_detail->m_members.last();
  116. }
  117. private:
  118. void copy()
  119. {
  120. if (m_detail->ref_count() <= 1)
  121. return;
  122. auto new_detail = make_ref_counted<Detail>();
  123. new_detail->m_members = m_detail->m_members;
  124. m_detail = new_detail;
  125. }
  126. NonnullRefPtr<Detail> m_detail;
  127. };
  128. class RegexStringView {
  129. public:
  130. RegexStringView() = default;
  131. RegexStringView(DeprecatedString const& string)
  132. : m_view(string.view())
  133. {
  134. }
  135. RegexStringView(String const& string)
  136. : m_view(string.bytes_as_string_view())
  137. {
  138. }
  139. RegexStringView(StringView const view)
  140. : m_view(view)
  141. {
  142. }
  143. RegexStringView(Utf32View view)
  144. : m_view(view)
  145. {
  146. }
  147. RegexStringView(Utf16View view)
  148. : m_view(view)
  149. {
  150. }
  151. RegexStringView(Utf8View view)
  152. : m_view(view)
  153. {
  154. }
  155. explicit RegexStringView(DeprecatedString&&) = delete;
  156. StringView string_view() const
  157. {
  158. return m_view.get<StringView>();
  159. }
  160. Utf32View const& u32_view() const
  161. {
  162. return m_view.get<Utf32View>();
  163. }
  164. Utf16View const& u16_view() const
  165. {
  166. return m_view.get<Utf16View>();
  167. }
  168. Utf8View const& u8_view() const
  169. {
  170. return m_view.get<Utf8View>();
  171. }
  172. bool unicode() const { return m_unicode; }
  173. void set_unicode(bool unicode) { m_unicode = unicode; }
  174. bool is_empty() const
  175. {
  176. return m_view.visit([](auto& view) { return view.is_empty(); });
  177. }
  178. bool is_null() const
  179. {
  180. return m_view.visit([](auto& view) { return view.is_null(); });
  181. }
  182. size_t length() const
  183. {
  184. if (unicode()) {
  185. return m_view.visit(
  186. [](Utf16View const& view) { return view.length_in_code_points(); },
  187. [](auto const& view) { return view.length(); });
  188. }
  189. return length_in_code_units();
  190. }
  191. size_t length_in_code_units() const
  192. {
  193. return m_view.visit(
  194. [](Utf16View const& view) { return view.length_in_code_units(); },
  195. [](Utf8View const& view) { return view.byte_length(); },
  196. [](auto const& view) { return view.length(); });
  197. }
  198. size_t length_of_code_point(u32 code_point) const
  199. {
  200. return m_view.visit(
  201. [](Utf32View const&) { return 1; },
  202. [&](Utf16View const&) {
  203. if (code_point < 0x10000)
  204. return 1;
  205. return 2;
  206. },
  207. [&](auto const&) {
  208. if (code_point <= 0x7f)
  209. return 1;
  210. if (code_point <= 0x07ff)
  211. return 2;
  212. if (code_point <= 0xffff)
  213. return 3;
  214. return 4;
  215. });
  216. }
  217. RegexStringView typed_null_view()
  218. {
  219. auto view = m_view.visit(
  220. [&]<typename T>(T const&) {
  221. return RegexStringView { T {} };
  222. });
  223. view.set_unicode(unicode());
  224. return view;
  225. }
  226. RegexStringView construct_as_same(Span<u32> data, Optional<DeprecatedString>& optional_string_storage, Utf16Data& optional_utf16_storage) const
  227. {
  228. auto view = m_view.visit(
  229. [&]<typename T>(T const&) {
  230. StringBuilder builder;
  231. for (auto ch : data)
  232. builder.append(ch); // Note: The type conversion is intentional.
  233. optional_string_storage = builder.to_deprecated_string();
  234. return RegexStringView { T { *optional_string_storage } };
  235. },
  236. [&](Utf32View) {
  237. return RegexStringView { Utf32View { data.data(), data.size() } };
  238. },
  239. [&](Utf16View) {
  240. optional_utf16_storage = AK::utf32_to_utf16(Utf32View { data.data(), data.size() }).release_value_but_fixme_should_propagate_errors();
  241. return RegexStringView { Utf16View { optional_utf16_storage } };
  242. });
  243. view.set_unicode(unicode());
  244. return view;
  245. }
  246. Vector<RegexStringView> lines() const
  247. {
  248. return m_view.visit(
  249. [](StringView view) {
  250. auto views = view.lines(false);
  251. Vector<RegexStringView> new_views;
  252. for (auto& view : views)
  253. new_views.empend(view);
  254. return new_views;
  255. },
  256. [](Utf32View view) {
  257. if (view.is_empty())
  258. return Vector<RegexStringView> { view };
  259. Vector<RegexStringView> views;
  260. u32 newline = '\n';
  261. while (!view.is_empty()) {
  262. auto position = AK::memmem_optional(view.code_points(), view.length() * sizeof(u32), &newline, sizeof(u32));
  263. if (!position.has_value())
  264. break;
  265. auto offset = position.value() / sizeof(u32);
  266. views.empend(view.substring_view(0, offset));
  267. view = view.substring_view(offset + 1, view.length() - offset - 1);
  268. }
  269. if (!view.is_empty())
  270. views.empend(view);
  271. return views;
  272. },
  273. [](Utf16View view) {
  274. if (view.is_empty())
  275. return Vector<RegexStringView> { view };
  276. Vector<RegexStringView> views;
  277. u16 newline = '\n';
  278. while (!view.is_empty()) {
  279. auto position = AK::memmem_optional(view.data(), view.length_in_code_units() * sizeof(u16), &newline, sizeof(u16));
  280. if (!position.has_value())
  281. break;
  282. auto offset = position.value() / sizeof(u16);
  283. views.empend(view.substring_view(0, offset));
  284. view = view.substring_view(offset + 1, view.length_in_code_units() - offset - 1);
  285. }
  286. if (!view.is_empty())
  287. views.empend(view);
  288. return views;
  289. },
  290. [](Utf8View const& view) {
  291. if (view.is_empty())
  292. return Vector<RegexStringView> { view };
  293. Vector<RegexStringView> views;
  294. auto it = view.begin();
  295. auto previous_newline_position_it = it;
  296. for (;;) {
  297. if (*it == '\n') {
  298. auto previous_offset = view.byte_offset_of(previous_newline_position_it);
  299. auto new_offset = view.byte_offset_of(it);
  300. auto slice = view.substring_view(previous_offset, new_offset - previous_offset);
  301. views.empend(slice);
  302. ++it;
  303. previous_newline_position_it = it;
  304. }
  305. if (it.done())
  306. break;
  307. ++it;
  308. }
  309. if (it != previous_newline_position_it) {
  310. auto previous_offset = view.byte_offset_of(previous_newline_position_it);
  311. auto new_offset = view.byte_offset_of(it);
  312. auto slice = view.substring_view(previous_offset, new_offset - previous_offset);
  313. views.empend(slice);
  314. }
  315. return views;
  316. });
  317. }
  318. RegexStringView substring_view(size_t offset, size_t length) const
  319. {
  320. if (unicode()) {
  321. auto view = m_view.visit(
  322. [&](auto view) { return RegexStringView { view.substring_view(offset, length) }; },
  323. [&](Utf16View const& view) { return RegexStringView { view.unicode_substring_view(offset, length) }; },
  324. [&](Utf8View const& view) { return RegexStringView { view.unicode_substring_view(offset, length) }; });
  325. view.set_unicode(unicode());
  326. return view;
  327. }
  328. auto view = m_view.visit([&](auto view) { return RegexStringView { view.substring_view(offset, length) }; });
  329. view.set_unicode(unicode());
  330. return view;
  331. }
  332. DeprecatedString to_deprecated_string() const
  333. {
  334. return m_view.visit(
  335. [](StringView view) { return view.to_deprecated_string(); },
  336. [](Utf16View view) { return view.to_deprecated_string(Utf16View::AllowInvalidCodeUnits::Yes).release_value_but_fixme_should_propagate_errors(); },
  337. [](auto& view) {
  338. StringBuilder builder;
  339. for (auto it = view.begin(); it != view.end(); ++it)
  340. builder.append_code_point(*it);
  341. return builder.to_deprecated_string();
  342. });
  343. }
  344. ErrorOr<String> to_string() const
  345. {
  346. return m_view.visit(
  347. [](StringView view) { return String::from_utf8(view); },
  348. [](Utf16View view) { return view.to_utf8(Utf16View::AllowInvalidCodeUnits::Yes); },
  349. [](auto& view) -> ErrorOr<String> {
  350. StringBuilder builder;
  351. for (auto it = view.begin(); it != view.end(); ++it)
  352. TRY(builder.try_append_code_point(*it));
  353. return builder.to_string();
  354. });
  355. }
  356. // Note: index must always be the code unit offset to return.
  357. u32 operator[](size_t index) const
  358. {
  359. return m_view.visit(
  360. [&](StringView view) -> u32 {
  361. auto ch = view[index];
  362. if constexpr (IsSigned<char>) {
  363. if (ch < 0)
  364. return 256u + ch;
  365. return ch;
  366. }
  367. },
  368. [&](Utf32View const& view) -> u32 { return view[index]; },
  369. [&](Utf16View const& view) -> u32 { return view.code_point_at(index); },
  370. [&](Utf8View const& view) -> u32 {
  371. auto it = view.iterator_at_byte_offset(index);
  372. VERIFY(it != view.end());
  373. return *it;
  374. });
  375. }
  376. size_t code_unit_offset_of(size_t code_point_index) const
  377. {
  378. return m_view.visit(
  379. [&](StringView view) -> u32 {
  380. Utf8View utf8_view { view };
  381. return utf8_view.byte_offset_of(code_point_index);
  382. },
  383. [&](Utf32View const&) -> u32 { return code_point_index; },
  384. [&](Utf16View const& view) -> u32 {
  385. return view.code_unit_offset_of(code_point_index);
  386. },
  387. [&](Utf8View const& view) -> u32 {
  388. return view.byte_offset_of(code_point_index);
  389. });
  390. }
  391. bool operator==(char const* cstring) const
  392. {
  393. return m_view.visit(
  394. [&](Utf32View) { return to_deprecated_string() == cstring; },
  395. [&](Utf16View) { return to_deprecated_string() == cstring; },
  396. [&](Utf8View const& view) { return view.as_string() == cstring; },
  397. [&](StringView view) { return view == cstring; });
  398. }
  399. bool operator==(DeprecatedString const& string) const
  400. {
  401. return m_view.visit(
  402. [&](Utf32View) { return to_deprecated_string() == string; },
  403. [&](Utf16View) { return to_deprecated_string() == string; },
  404. [&](Utf8View const& view) { return view.as_string() == string; },
  405. [&](StringView view) { return view == string; });
  406. }
  407. bool operator==(StringView string) const
  408. {
  409. return m_view.visit(
  410. [&](Utf32View) { return to_deprecated_string() == string; },
  411. [&](Utf16View) { return to_deprecated_string() == string; },
  412. [&](Utf8View const& view) { return view.as_string() == string; },
  413. [&](StringView view) { return view == string; });
  414. }
  415. bool operator==(Utf32View const& other) const
  416. {
  417. return m_view.visit(
  418. [&](Utf32View view) {
  419. return view.length() == other.length() && __builtin_memcmp(view.code_points(), other.code_points(), view.length() * sizeof(u32)) == 0;
  420. },
  421. [&](Utf16View) { return to_deprecated_string() == RegexStringView { other }.to_deprecated_string(); },
  422. [&](Utf8View const& view) { return view.as_string() == RegexStringView { other }.to_deprecated_string(); },
  423. [&](StringView view) { return view == RegexStringView { other }.to_deprecated_string(); });
  424. }
  425. bool operator==(Utf16View const& other) const
  426. {
  427. return m_view.visit(
  428. [&](Utf32View) { return to_deprecated_string() == RegexStringView { other }.to_deprecated_string(); },
  429. [&](Utf16View const& view) { return view == other; },
  430. [&](Utf8View const& view) { return view.as_string() == RegexStringView { other }.to_deprecated_string(); },
  431. [&](StringView view) { return view == RegexStringView { other }.to_deprecated_string(); });
  432. }
  433. bool operator==(Utf8View const& other) const
  434. {
  435. return m_view.visit(
  436. [&](Utf32View) { return to_deprecated_string() == other.as_string(); },
  437. [&](Utf16View) { return to_deprecated_string() == other.as_string(); },
  438. [&](Utf8View const& view) { return view.as_string() == other.as_string(); },
  439. [&](StringView view) { return other.as_string() == view; });
  440. }
  441. bool equals(RegexStringView other) const
  442. {
  443. return other.m_view.visit([this](auto const& view) { return operator==(view); });
  444. }
  445. bool equals_ignoring_case(RegexStringView other) const
  446. {
  447. // FIXME: Implement equals_ignoring_case() for unicode.
  448. return m_view.visit(
  449. [&](StringView view) {
  450. return other.m_view.visit(
  451. [&](StringView other_view) { return view.equals_ignoring_ascii_case(other_view); },
  452. [](auto&) -> bool { TODO(); });
  453. },
  454. [&](Utf16View view) {
  455. return other.m_view.visit(
  456. [&](Utf16View other_view) { return view.equals_ignoring_case(other_view); },
  457. [](auto&) -> bool { TODO(); });
  458. },
  459. [](auto&) -> bool { TODO(); });
  460. }
  461. bool starts_with(StringView str) const
  462. {
  463. return m_view.visit(
  464. [&](Utf32View) -> bool {
  465. TODO();
  466. },
  467. [&](Utf16View) -> bool {
  468. TODO();
  469. },
  470. [&](Utf8View const& view) { return view.as_string().starts_with(str); },
  471. [&](StringView view) { return view.starts_with(str); });
  472. }
  473. bool starts_with(Utf32View const& str) const
  474. {
  475. return m_view.visit(
  476. [&](Utf32View view) -> bool {
  477. if (str.length() > view.length())
  478. return false;
  479. if (str.length() == view.length())
  480. return operator==(str);
  481. for (size_t i = 0; i < str.length(); ++i) {
  482. if (str.at(i) != view.at(i))
  483. return false;
  484. }
  485. return true;
  486. },
  487. [&](Utf16View) -> bool { TODO(); },
  488. [&](Utf8View const& view) {
  489. auto it = view.begin();
  490. for (auto code_point : str) {
  491. if (it.done())
  492. return false;
  493. if (code_point != *it)
  494. return false;
  495. ++it;
  496. }
  497. return true;
  498. },
  499. [&](StringView) -> bool { TODO(); });
  500. }
  501. private:
  502. Variant<StringView, Utf8View, Utf16View, Utf32View> m_view { StringView {} };
  503. bool m_unicode { false };
  504. };
  505. class Match final {
  506. private:
  507. Optional<DeprecatedFlyString> string;
  508. public:
  509. Match() = default;
  510. ~Match() = default;
  511. Match(RegexStringView view_, size_t const line_, size_t const column_, size_t const global_offset_)
  512. : view(view_)
  513. , line(line_)
  514. , column(column_)
  515. , global_offset(global_offset_)
  516. , left_column(column_)
  517. {
  518. }
  519. Match(DeprecatedString string_, size_t const line_, size_t const column_, size_t const global_offset_)
  520. : string(move(string_))
  521. , view(string.value().view())
  522. , line(line_)
  523. , column(column_)
  524. , global_offset(global_offset_)
  525. {
  526. }
  527. Match(RegexStringView const view_, StringView capture_group_name_, size_t const line_, size_t const column_, size_t const global_offset_)
  528. : view(view_)
  529. , capture_group_name(capture_group_name_)
  530. , line(line_)
  531. , column(column_)
  532. , global_offset(global_offset_)
  533. , left_column(column_)
  534. {
  535. }
  536. void reset()
  537. {
  538. view = view.typed_null_view();
  539. capture_group_name.clear();
  540. line = 0;
  541. column = 0;
  542. global_offset = 0;
  543. left_column = 0;
  544. }
  545. RegexStringView view {};
  546. Optional<DeprecatedFlyString> capture_group_name {};
  547. size_t line { 0 };
  548. size_t column { 0 };
  549. size_t global_offset { 0 };
  550. // ugly, as not usable by user, but needed to prevent to create extra vectors that are
  551. // able to store the column when the left paren has been found
  552. size_t left_column { 0 };
  553. };
  554. struct MatchInput {
  555. RegexStringView view {};
  556. AllOptions regex_options {};
  557. size_t start_offset { 0 }; // For Stateful matches, saved and restored from Regex::start_offset.
  558. size_t match_index { 0 };
  559. size_t line { 0 };
  560. size_t column { 0 };
  561. size_t global_offset { 0 }; // For multiline matching, knowing the offset from start could be important
  562. mutable size_t fail_counter { 0 };
  563. mutable Vector<size_t> saved_positions;
  564. mutable Vector<size_t> saved_code_unit_positions;
  565. mutable Vector<size_t> saved_forks_since_last_save;
  566. mutable HashMap<u64, u64> checkpoints;
  567. mutable Optional<size_t> fork_to_replace;
  568. };
  569. struct MatchState {
  570. size_t string_position_before_match { 0 };
  571. size_t string_position { 0 };
  572. size_t string_position_in_code_units { 0 };
  573. size_t instruction_position { 0 };
  574. size_t fork_at_position { 0 };
  575. size_t forks_since_last_save { 0 };
  576. Optional<size_t> initiating_fork;
  577. COWVector<Match> matches;
  578. COWVector<Vector<Match>> capture_group_matches;
  579. COWVector<u64> repetition_marks;
  580. };
  581. }
  582. using regex::RegexStringView;
  583. template<>
  584. struct AK::Formatter<regex::RegexStringView> : Formatter<StringView> {
  585. ErrorOr<void> format(FormatBuilder& builder, regex::RegexStringView value)
  586. {
  587. auto string = value.to_deprecated_string();
  588. return Formatter<StringView>::format(builder, string);
  589. }
  590. };