RegexMatcher.cpp 19 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528
  1. /*
  2. * Copyright (c) 2020, Emanuel Sprung <emanuel.sprung@gmail.com>
  3. *
  4. * SPDX-License-Identifier: BSD-2-Clause
  5. */
  6. #include <AK/BumpAllocator.h>
  7. #include <AK/Debug.h>
  8. #include <AK/String.h>
  9. #include <AK/StringBuilder.h>
  10. #include <LibRegex/RegexMatcher.h>
  11. #include <LibRegex/RegexParser.h>
  12. #if REGEX_DEBUG
  13. # include <LibRegex/RegexDebug.h>
  14. #endif
  15. namespace regex {
  16. #if REGEX_DEBUG
  17. static RegexDebug s_regex_dbg(stderr);
  18. #endif
  19. template<class Parser>
  20. regex::Parser::Result Regex<Parser>::parse_pattern(StringView pattern, typename ParserTraits<Parser>::OptionsType regex_options)
  21. {
  22. regex::Lexer lexer(pattern);
  23. Parser parser(lexer, regex_options);
  24. return parser.parse();
  25. }
  26. template<class Parser>
  27. Regex<Parser>::Regex(String pattern, typename ParserTraits<Parser>::OptionsType regex_options)
  28. : pattern_value(move(pattern))
  29. {
  30. regex::Lexer lexer(pattern_value);
  31. Parser parser(lexer, regex_options);
  32. parser_result = parser.parse();
  33. run_optimization_passes();
  34. if (parser_result.error == regex::Error::NoError)
  35. matcher = make<Matcher<Parser>>(this, regex_options);
  36. }
  37. template<class Parser>
  38. Regex<Parser>::Regex(regex::Parser::Result parse_result, String pattern, typename ParserTraits<Parser>::OptionsType regex_options)
  39. : pattern_value(move(pattern))
  40. , parser_result(move(parse_result))
  41. {
  42. run_optimization_passes();
  43. if (parser_result.error == regex::Error::NoError)
  44. matcher = make<Matcher<Parser>>(this, regex_options);
  45. }
  46. template<class Parser>
  47. Regex<Parser>::Regex(Regex&& regex)
  48. : pattern_value(move(regex.pattern_value))
  49. , parser_result(move(regex.parser_result))
  50. , matcher(move(regex.matcher))
  51. , start_offset(regex.start_offset)
  52. {
  53. if (matcher)
  54. matcher->reset_pattern({}, this);
  55. }
  56. template<class Parser>
  57. Regex<Parser>& Regex<Parser>::operator=(Regex&& regex)
  58. {
  59. pattern_value = move(regex.pattern_value);
  60. parser_result = move(regex.parser_result);
  61. matcher = move(regex.matcher);
  62. if (matcher)
  63. matcher->reset_pattern({}, this);
  64. start_offset = regex.start_offset;
  65. return *this;
  66. }
  67. template<class Parser>
  68. typename ParserTraits<Parser>::OptionsType Regex<Parser>::options() const
  69. {
  70. if (!matcher || parser_result.error != Error::NoError)
  71. return {};
  72. return matcher->options();
  73. }
  74. template<class Parser>
  75. String Regex<Parser>::error_string(Optional<String> message) const
  76. {
  77. StringBuilder eb;
  78. eb.append("Error during parsing of regular expression:\n");
  79. eb.appendff(" {}\n ", pattern_value);
  80. for (size_t i = 0; i < parser_result.error_token.position(); ++i)
  81. eb.append(' ');
  82. eb.appendff("^---- {}", message.value_or(get_error_string(parser_result.error)));
  83. return eb.build();
  84. }
  85. template<typename Parser>
  86. RegexResult Matcher<Parser>::match(RegexStringView view, Optional<typename ParserTraits<Parser>::OptionsType> regex_options) const
  87. {
  88. AllOptions options = m_regex_options | regex_options.value_or({}).value();
  89. if (options.has_flag_set(AllFlags::Multiline))
  90. return match(view.lines(), regex_options); // FIXME: how do we know, which line ending a line has (1char or 2char)? This is needed to get the correct match offsets from start of string...
  91. Vector<RegexStringView> views;
  92. views.append(view);
  93. return match(views, regex_options);
  94. }
  95. template<typename Parser>
  96. RegexResult Matcher<Parser>::match(Vector<RegexStringView> const& views, Optional<typename ParserTraits<Parser>::OptionsType> regex_options) const
  97. {
  98. // If the pattern *itself* isn't stateful, reset any changes to start_offset.
  99. if (!((AllFlags)m_regex_options.value() & AllFlags::Internal_Stateful))
  100. m_pattern->start_offset = 0;
  101. size_t match_count { 0 };
  102. MatchInput input;
  103. MatchState state;
  104. size_t operations = 0;
  105. input.regex_options = m_regex_options | regex_options.value_or({}).value();
  106. input.start_offset = m_pattern->start_offset;
  107. size_t lines_to_skip = 0;
  108. bool unicode = input.regex_options.has_flag_set(AllFlags::Unicode);
  109. for (auto const& view : views)
  110. const_cast<RegexStringView&>(view).set_unicode(unicode);
  111. if (input.regex_options.has_flag_set(AllFlags::Internal_Stateful)) {
  112. if (views.size() > 1 && input.start_offset > views.first().length()) {
  113. dbgln_if(REGEX_DEBUG, "Started with start={}, goff={}, skip={}", input.start_offset, input.global_offset, lines_to_skip);
  114. for (auto const& view : views) {
  115. if (input.start_offset < view.length() + 1)
  116. break;
  117. ++lines_to_skip;
  118. input.start_offset -= view.length() + 1;
  119. input.global_offset += view.length() + 1;
  120. }
  121. dbgln_if(REGEX_DEBUG, "Ended with start={}, goff={}, skip={}", input.start_offset, input.global_offset, lines_to_skip);
  122. }
  123. }
  124. if (c_match_preallocation_count) {
  125. state.matches.ensure_capacity(c_match_preallocation_count);
  126. state.capture_group_matches.ensure_capacity(c_match_preallocation_count);
  127. auto& capture_groups_count = m_pattern->parser_result.capture_groups_count;
  128. for (size_t j = 0; j < c_match_preallocation_count; ++j) {
  129. state.matches.empend();
  130. state.capture_group_matches.unchecked_append({});
  131. state.capture_group_matches.at(j).ensure_capacity(capture_groups_count);
  132. for (size_t k = 0; k < capture_groups_count; ++k)
  133. state.capture_group_matches.at(j).unchecked_append({});
  134. }
  135. }
  136. auto append_match = [](auto& input, auto& state, auto& start_position) {
  137. if (state.matches.size() == input.match_index)
  138. state.matches.empend();
  139. VERIFY(start_position + state.string_position - start_position <= input.view.length());
  140. if (input.regex_options.has_flag_set(AllFlags::StringCopyMatches)) {
  141. state.matches.at(input.match_index) = { input.view.substring_view(start_position, state.string_position - start_position).to_string(), input.line, start_position, input.global_offset + start_position };
  142. } else { // let the view point to the original string ...
  143. state.matches.at(input.match_index) = { input.view.substring_view(start_position, state.string_position - start_position), input.line, start_position, input.global_offset + start_position };
  144. }
  145. };
  146. #if REGEX_DEBUG
  147. s_regex_dbg.print_header();
  148. #endif
  149. bool continue_search = input.regex_options.has_flag_set(AllFlags::Global) || input.regex_options.has_flag_set(AllFlags::Multiline);
  150. if (input.regex_options.has_flag_set(AllFlags::Internal_Stateful))
  151. continue_search = false;
  152. for (auto const& view : views) {
  153. if (lines_to_skip != 0) {
  154. ++input.line;
  155. --lines_to_skip;
  156. continue;
  157. }
  158. input.view = view;
  159. dbgln_if(REGEX_DEBUG, "[match] Starting match with view ({}): _{}_", view.length(), view);
  160. auto view_length = view.length();
  161. size_t view_index = m_pattern->start_offset;
  162. state.string_position = view_index;
  163. state.string_position_in_code_units = view_index;
  164. bool succeeded = false;
  165. if (view_index == view_length && m_pattern->parser_result.match_length_minimum == 0) {
  166. // Run the code until it tries to consume something.
  167. // This allows non-consuming code to run on empty strings, for instance
  168. // e.g. "Exit"
  169. size_t temp_operations = operations;
  170. input.column = match_count;
  171. input.match_index = match_count;
  172. state.string_position = view_index;
  173. state.string_position_in_code_units = view_index;
  174. state.instruction_position = 0;
  175. state.repetition_marks.clear();
  176. auto success = execute(input, state, temp_operations);
  177. // This success is acceptable only if it doesn't read anything from the input (input length is 0).
  178. if (state.string_position <= view_index) {
  179. if (success.has_value() && success.value()) {
  180. operations = temp_operations;
  181. if (!match_count) {
  182. // Nothing was *actually* matched, so append an empty match.
  183. append_match(input, state, view_index);
  184. ++match_count;
  185. }
  186. }
  187. }
  188. }
  189. for (; view_index < view_length; ++view_index) {
  190. auto& match_length_minimum = m_pattern->parser_result.match_length_minimum;
  191. // FIXME: More performant would be to know the remaining minimum string
  192. // length needed to match from the current position onwards within
  193. // the vm. Add new OpCode for MinMatchLengthFromSp with the value of
  194. // the remaining string length from the current path. The value though
  195. // has to be filled in reverse. That implies a second run over bytecode
  196. // after generation has finished.
  197. if (match_length_minimum && match_length_minimum > view_length - view_index)
  198. break;
  199. input.column = match_count;
  200. input.match_index = match_count;
  201. state.string_position = view_index;
  202. state.string_position_in_code_units = view_index;
  203. state.instruction_position = 0;
  204. state.repetition_marks.clear();
  205. auto success = execute(input, state, operations);
  206. if (!success.has_value())
  207. return { false, 0, {}, {}, {}, operations };
  208. if (success.value()) {
  209. succeeded = true;
  210. if (input.regex_options.has_flag_set(AllFlags::MatchNotEndOfLine) && state.string_position == input.view.length()) {
  211. if (!continue_search)
  212. break;
  213. continue;
  214. }
  215. if (input.regex_options.has_flag_set(AllFlags::MatchNotBeginOfLine) && view_index == 0) {
  216. if (!continue_search)
  217. break;
  218. continue;
  219. }
  220. dbgln_if(REGEX_DEBUG, "state.string_position={}, view_index={}", state.string_position, view_index);
  221. dbgln_if(REGEX_DEBUG, "[match] Found a match (length={}): '{}'", state.string_position - view_index, input.view.substring_view(view_index, state.string_position - view_index));
  222. ++match_count;
  223. if (continue_search) {
  224. append_match(input, state, view_index);
  225. bool has_zero_length = state.string_position == view_index;
  226. view_index = state.string_position - (has_zero_length ? 0 : 1);
  227. continue;
  228. }
  229. if (input.regex_options.has_flag_set(AllFlags::Internal_Stateful)) {
  230. append_match(input, state, view_index);
  231. break;
  232. }
  233. if (state.string_position < view_length) {
  234. return { false, 0, {}, {}, {}, operations };
  235. }
  236. append_match(input, state, view_index);
  237. break;
  238. }
  239. if (!continue_search)
  240. break;
  241. }
  242. ++input.line;
  243. input.global_offset += view.length() + 1; // +1 includes the line break character
  244. if (input.regex_options.has_flag_set(AllFlags::Internal_Stateful))
  245. m_pattern->start_offset = state.string_position;
  246. if (succeeded && !continue_search)
  247. break;
  248. }
  249. RegexResult result {
  250. match_count != 0,
  251. match_count,
  252. move(state.matches),
  253. move(state.capture_group_matches),
  254. operations,
  255. m_pattern->parser_result.capture_groups_count,
  256. m_pattern->parser_result.named_capture_groups_count,
  257. };
  258. if (match_count) {
  259. // Make sure there are as many capture matches as there are actual matches.
  260. if (result.capture_group_matches.size() < match_count)
  261. result.capture_group_matches.resize(match_count);
  262. for (auto& matches : result.capture_group_matches)
  263. matches.resize(m_pattern->parser_result.capture_groups_count + 1);
  264. if (!input.regex_options.has_flag_set(AllFlags::SkipTrimEmptyMatches)) {
  265. for (auto& matches : result.capture_group_matches)
  266. matches.template remove_all_matching([](auto& match) { return match.view.is_null(); });
  267. }
  268. } else {
  269. result.capture_group_matches.clear_with_capacity();
  270. }
  271. return result;
  272. }
  273. template<typename T>
  274. class BumpAllocatedLinkedList {
  275. public:
  276. BumpAllocatedLinkedList() = default;
  277. ALWAYS_INLINE void append(T value)
  278. {
  279. auto node_ptr = m_allocator.allocate(move(value));
  280. VERIFY(node_ptr);
  281. if (!m_first) {
  282. m_first = node_ptr;
  283. m_last = node_ptr;
  284. return;
  285. }
  286. node_ptr->previous = m_last;
  287. m_last->next = node_ptr;
  288. m_last = node_ptr;
  289. }
  290. ALWAYS_INLINE T take_last()
  291. {
  292. VERIFY(m_last);
  293. T value = move(m_last->value);
  294. if (m_last == m_first) {
  295. m_last = nullptr;
  296. m_first = nullptr;
  297. } else {
  298. m_last = m_last->previous;
  299. m_last->next = nullptr;
  300. }
  301. return value;
  302. }
  303. ALWAYS_INLINE T& last()
  304. {
  305. return m_last->value;
  306. }
  307. ALWAYS_INLINE bool is_empty() const
  308. {
  309. return m_first == nullptr;
  310. }
  311. auto reverse_begin() { return ReverseIterator(m_last); }
  312. auto reverse_end() { return ReverseIterator(); }
  313. private:
  314. struct Node {
  315. T value;
  316. Node* next { nullptr };
  317. Node* previous { nullptr };
  318. };
  319. struct ReverseIterator {
  320. ReverseIterator() = default;
  321. explicit ReverseIterator(Node* node)
  322. : m_node(node)
  323. {
  324. }
  325. T* operator->() { return &m_node->value; }
  326. T& operator*() { return m_node->value; }
  327. bool operator==(ReverseIterator const& it) const { return m_node == it.m_node; }
  328. ReverseIterator& operator++()
  329. {
  330. if (m_node)
  331. m_node = m_node->previous;
  332. return *this;
  333. }
  334. private:
  335. Node* m_node;
  336. };
  337. UniformBumpAllocator<Node, true, 2 * MiB> m_allocator;
  338. Node* m_first { nullptr };
  339. Node* m_last { nullptr };
  340. };
  341. template<class Parser>
  342. Optional<bool> Matcher<Parser>::execute(MatchInput const& input, MatchState& state, size_t& operations) const
  343. {
  344. BumpAllocatedLinkedList<MatchState> states_to_try_next;
  345. size_t recursion_level = 0;
  346. auto& bytecode = m_pattern->parser_result.bytecode;
  347. for (;;) {
  348. auto& opcode = bytecode.get_opcode(state);
  349. ++operations;
  350. #if REGEX_DEBUG
  351. s_regex_dbg.print_opcode("VM", opcode, state, recursion_level, false);
  352. #endif
  353. ExecutionResult result;
  354. if (input.fail_counter > 0) {
  355. --input.fail_counter;
  356. result = ExecutionResult::Failed_ExecuteLowPrioForks;
  357. } else {
  358. result = opcode.execute(input, state);
  359. }
  360. #if REGEX_DEBUG
  361. s_regex_dbg.print_result(opcode, bytecode, input, state, result);
  362. #endif
  363. state.instruction_position += opcode.size();
  364. switch (result) {
  365. case ExecutionResult::Fork_PrioLow: {
  366. bool found = false;
  367. if (input.fork_to_replace.has_value()) {
  368. for (auto it = states_to_try_next.reverse_begin(); it != states_to_try_next.reverse_end(); ++it) {
  369. if (it->initiating_fork == input.fork_to_replace.value()) {
  370. (*it) = state;
  371. it->instruction_position = state.fork_at_position;
  372. it->initiating_fork = *input.fork_to_replace;
  373. found = true;
  374. break;
  375. }
  376. }
  377. input.fork_to_replace.clear();
  378. }
  379. if (!found) {
  380. states_to_try_next.append(state);
  381. states_to_try_next.last().initiating_fork = state.instruction_position - opcode.size();
  382. states_to_try_next.last().instruction_position = state.fork_at_position;
  383. }
  384. continue;
  385. }
  386. case ExecutionResult::Fork_PrioHigh: {
  387. bool found = false;
  388. if (input.fork_to_replace.has_value()) {
  389. for (auto it = states_to_try_next.reverse_begin(); it != states_to_try_next.reverse_end(); ++it) {
  390. if (it->initiating_fork == input.fork_to_replace.value()) {
  391. (*it) = state;
  392. it->initiating_fork = *input.fork_to_replace;
  393. found = true;
  394. break;
  395. }
  396. }
  397. input.fork_to_replace.clear();
  398. }
  399. if (!found) {
  400. states_to_try_next.append(state);
  401. states_to_try_next.last().initiating_fork = state.instruction_position - opcode.size();
  402. }
  403. state.instruction_position = state.fork_at_position;
  404. ++recursion_level;
  405. continue;
  406. }
  407. case ExecutionResult::Continue:
  408. continue;
  409. case ExecutionResult::Succeeded:
  410. return true;
  411. case ExecutionResult::Failed:
  412. if (!states_to_try_next.is_empty()) {
  413. auto next_state = states_to_try_next.take_last();
  414. // Note: ECMA262 quirk: Note 3, https://tc39.es/ecma262/#sec-runtime-semantics-canonicalize-ch
  415. // capture groups defined in lookarounds "leak" outside the regex,
  416. // but their contents are empty if the lookaround fails.
  417. // This is done by manually clearing the groups where needed, and leaking their contents here.
  418. if constexpr (IsSame<Parser, ECMA262>)
  419. swap(next_state.capture_group_matches, state.capture_group_matches);
  420. state = move(next_state);
  421. continue;
  422. }
  423. return false;
  424. case ExecutionResult::Failed_ExecuteLowPrioForks: {
  425. if (states_to_try_next.is_empty()) {
  426. if (input.regex_options.has_flag_set(AllFlags::Internal_Stateful))
  427. return {};
  428. return false;
  429. }
  430. auto next_state = states_to_try_next.take_last();
  431. // See note above about an ECMA262 quirk.
  432. if constexpr (IsSame<Parser, ECMA262>)
  433. swap(next_state.capture_group_matches, state.capture_group_matches);
  434. state = move(next_state);
  435. ++recursion_level;
  436. continue;
  437. }
  438. }
  439. }
  440. VERIFY_NOT_REACHED();
  441. }
  442. template class Matcher<PosixBasicParser>;
  443. template class Regex<PosixBasicParser>;
  444. template class Matcher<PosixExtendedParser>;
  445. template class Regex<PosixExtendedParser>;
  446. template class Matcher<ECMA262Parser>;
  447. template class Regex<ECMA262Parser>;
  448. }