RegexMatcher.cpp 18 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525
  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, static_cast<decltype(regex_options.value())>(parser_result.options.value()));
  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 | static_cast<decltype(regex_options.value())>(parse_result.options.value()));
  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"sv);
  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 constexpr (!IsSame<Parser, ECMA262>) {
  90. if (options.has_flag_set(AllFlags::Multiline))
  91. 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...
  92. }
  93. Vector<RegexStringView> views;
  94. views.append(view);
  95. return match(views, regex_options);
  96. }
  97. template<typename Parser>
  98. RegexResult Matcher<Parser>::match(Vector<RegexStringView> const& views, Optional<typename ParserTraits<Parser>::OptionsType> regex_options) const
  99. {
  100. // If the pattern *itself* isn't stateful, reset any changes to start_offset.
  101. if (!((AllFlags)m_regex_options.value() & AllFlags::Internal_Stateful))
  102. m_pattern->start_offset = 0;
  103. size_t match_count { 0 };
  104. MatchInput input;
  105. MatchState state;
  106. size_t operations = 0;
  107. input.regex_options = m_regex_options | regex_options.value_or({}).value();
  108. input.start_offset = m_pattern->start_offset;
  109. size_t lines_to_skip = 0;
  110. bool unicode = input.regex_options.has_flag_set(AllFlags::Unicode);
  111. for (auto const& view : views)
  112. const_cast<RegexStringView&>(view).set_unicode(unicode);
  113. if (input.regex_options.has_flag_set(AllFlags::Internal_Stateful)) {
  114. if (views.size() > 1 && input.start_offset > views.first().length()) {
  115. dbgln_if(REGEX_DEBUG, "Started with start={}, goff={}, skip={}", input.start_offset, input.global_offset, lines_to_skip);
  116. for (auto const& view : views) {
  117. if (input.start_offset < view.length() + 1)
  118. break;
  119. ++lines_to_skip;
  120. input.start_offset -= view.length() + 1;
  121. input.global_offset += view.length() + 1;
  122. }
  123. dbgln_if(REGEX_DEBUG, "Ended with start={}, goff={}, skip={}", input.start_offset, input.global_offset, lines_to_skip);
  124. }
  125. }
  126. if (c_match_preallocation_count) {
  127. state.matches.ensure_capacity(c_match_preallocation_count);
  128. state.capture_group_matches.ensure_capacity(c_match_preallocation_count);
  129. auto& capture_groups_count = m_pattern->parser_result.capture_groups_count;
  130. for (size_t j = 0; j < c_match_preallocation_count; ++j) {
  131. state.matches.empend();
  132. state.capture_group_matches.empend();
  133. state.capture_group_matches.at(j).ensure_capacity(capture_groups_count);
  134. for (size_t k = 0; k < capture_groups_count; ++k)
  135. state.capture_group_matches.at(j).unchecked_append({});
  136. }
  137. }
  138. auto append_match = [](auto& input, auto& state, auto& start_position) {
  139. if (state.matches.size() == input.match_index)
  140. state.matches.empend();
  141. VERIFY(start_position + state.string_position - start_position <= input.view.length());
  142. if (input.regex_options.has_flag_set(AllFlags::StringCopyMatches)) {
  143. 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 };
  144. } else { // let the view point to the original string ...
  145. 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 };
  146. }
  147. };
  148. #if REGEX_DEBUG
  149. s_regex_dbg.print_header();
  150. #endif
  151. bool continue_search = input.regex_options.has_flag_set(AllFlags::Global) || input.regex_options.has_flag_set(AllFlags::Multiline);
  152. if (input.regex_options.has_flag_set(AllFlags::Sticky))
  153. continue_search = false;
  154. auto single_match_only = input.regex_options.has_flag_set(AllFlags::SingleMatch);
  155. for (auto const& view : views) {
  156. if (lines_to_skip != 0) {
  157. ++input.line;
  158. --lines_to_skip;
  159. continue;
  160. }
  161. input.view = view;
  162. dbgln_if(REGEX_DEBUG, "[match] Starting match with view ({}): _{}_", view.length(), view);
  163. auto view_length = view.length();
  164. size_t view_index = m_pattern->start_offset;
  165. state.string_position = view_index;
  166. state.string_position_in_code_units = view_index;
  167. bool succeeded = false;
  168. if (view_index == view_length && m_pattern->parser_result.match_length_minimum == 0) {
  169. // Run the code until it tries to consume something.
  170. // This allows non-consuming code to run on empty strings, for instance
  171. // e.g. "Exit"
  172. size_t temp_operations = operations;
  173. input.column = match_count;
  174. input.match_index = match_count;
  175. state.string_position = view_index;
  176. state.string_position_in_code_units = view_index;
  177. state.instruction_position = 0;
  178. state.repetition_marks.clear();
  179. auto success = execute(input, state, temp_operations);
  180. // This success is acceptable only if it doesn't read anything from the input (input length is 0).
  181. if (success && (state.string_position <= view_index)) {
  182. operations = temp_operations;
  183. if (!match_count) {
  184. // Nothing was *actually* matched, so append an empty match.
  185. append_match(input, state, view_index);
  186. ++match_count;
  187. }
  188. }
  189. }
  190. for (; view_index <= view_length; ++view_index) {
  191. if (view_index == view_length && input.regex_options.has_flag_set(AllFlags::Multiline))
  192. break;
  193. auto& match_length_minimum = m_pattern->parser_result.match_length_minimum;
  194. // FIXME: More performant would be to know the remaining minimum string
  195. // length needed to match from the current position onwards within
  196. // the vm. Add new OpCode for MinMatchLengthFromSp with the value of
  197. // the remaining string length from the current path. The value though
  198. // has to be filled in reverse. That implies a second run over bytecode
  199. // after generation has finished.
  200. if (match_length_minimum && match_length_minimum > view_length - view_index)
  201. break;
  202. input.column = match_count;
  203. input.match_index = match_count;
  204. state.string_position = view_index;
  205. state.string_position_in_code_units = view_index;
  206. state.instruction_position = 0;
  207. state.repetition_marks.clear();
  208. auto success = execute(input, state, operations);
  209. if (success) {
  210. succeeded = true;
  211. if (input.regex_options.has_flag_set(AllFlags::MatchNotEndOfLine) && state.string_position == input.view.length()) {
  212. if (!continue_search)
  213. break;
  214. continue;
  215. }
  216. if (input.regex_options.has_flag_set(AllFlags::MatchNotBeginOfLine) && view_index == 0) {
  217. if (!continue_search)
  218. break;
  219. continue;
  220. }
  221. dbgln_if(REGEX_DEBUG, "state.string_position={}, view_index={}", state.string_position, view_index);
  222. 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));
  223. ++match_count;
  224. if (continue_search) {
  225. append_match(input, state, view_index);
  226. bool has_zero_length = state.string_position == view_index;
  227. view_index = state.string_position - (has_zero_length ? 0 : 1);
  228. if (single_match_only)
  229. break;
  230. continue;
  231. }
  232. if (input.regex_options.has_flag_set(AllFlags::Internal_Stateful)) {
  233. append_match(input, state, view_index);
  234. break;
  235. }
  236. if (state.string_position < view_length) {
  237. return { false, 0, {}, {}, {}, operations };
  238. }
  239. append_match(input, state, view_index);
  240. break;
  241. }
  242. if (!continue_search)
  243. break;
  244. }
  245. ++input.line;
  246. input.global_offset += view.length() + 1; // +1 includes the line break character
  247. if (input.regex_options.has_flag_set(AllFlags::Internal_Stateful))
  248. m_pattern->start_offset = state.string_position;
  249. if (succeeded && !continue_search)
  250. break;
  251. }
  252. RegexResult result {
  253. match_count != 0,
  254. match_count,
  255. move(state.matches).release(),
  256. move(state.capture_group_matches).release(),
  257. operations,
  258. m_pattern->parser_result.capture_groups_count,
  259. m_pattern->parser_result.named_capture_groups_count,
  260. };
  261. if (match_count) {
  262. // Make sure there are as many capture matches as there are actual matches.
  263. if (result.capture_group_matches.size() < match_count)
  264. result.capture_group_matches.resize(match_count);
  265. for (auto& matches : result.capture_group_matches)
  266. matches.resize(m_pattern->parser_result.capture_groups_count + 1);
  267. if (!input.regex_options.has_flag_set(AllFlags::SkipTrimEmptyMatches)) {
  268. for (auto& matches : result.capture_group_matches)
  269. matches.template remove_all_matching([](auto& match) { return match.view.is_null(); });
  270. }
  271. } else {
  272. result.capture_group_matches.clear_with_capacity();
  273. }
  274. return result;
  275. }
  276. template<typename T>
  277. class BumpAllocatedLinkedList {
  278. public:
  279. BumpAllocatedLinkedList() = default;
  280. ALWAYS_INLINE void append(T value)
  281. {
  282. auto node_ptr = m_allocator.allocate(move(value));
  283. VERIFY(node_ptr);
  284. if (!m_first) {
  285. m_first = node_ptr;
  286. m_last = node_ptr;
  287. return;
  288. }
  289. node_ptr->previous = m_last;
  290. m_last->next = node_ptr;
  291. m_last = node_ptr;
  292. }
  293. ALWAYS_INLINE T take_last()
  294. {
  295. VERIFY(m_last);
  296. T value = move(m_last->value);
  297. if (m_last == m_first) {
  298. m_last = nullptr;
  299. m_first = nullptr;
  300. } else {
  301. m_last = m_last->previous;
  302. m_last->next = nullptr;
  303. }
  304. return value;
  305. }
  306. ALWAYS_INLINE T& last()
  307. {
  308. return m_last->value;
  309. }
  310. ALWAYS_INLINE bool is_empty() const
  311. {
  312. return m_first == nullptr;
  313. }
  314. auto reverse_begin() { return ReverseIterator(m_last); }
  315. auto reverse_end() { return ReverseIterator(); }
  316. private:
  317. struct Node {
  318. T value;
  319. Node* next { nullptr };
  320. Node* previous { nullptr };
  321. };
  322. struct ReverseIterator {
  323. ReverseIterator() = default;
  324. explicit ReverseIterator(Node* node)
  325. : m_node(node)
  326. {
  327. }
  328. T* operator->() { return &m_node->value; }
  329. T& operator*() { return m_node->value; }
  330. bool operator==(ReverseIterator const& it) const { return m_node == it.m_node; }
  331. ReverseIterator& operator++()
  332. {
  333. if (m_node)
  334. m_node = m_node->previous;
  335. return *this;
  336. }
  337. private:
  338. Node* m_node;
  339. };
  340. UniformBumpAllocator<Node, true, 2 * MiB> m_allocator;
  341. Node* m_first { nullptr };
  342. Node* m_last { nullptr };
  343. };
  344. template<class Parser>
  345. bool Matcher<Parser>::execute(MatchInput const& input, MatchState& state, size_t& operations) const
  346. {
  347. BumpAllocatedLinkedList<MatchState> states_to_try_next;
  348. #if REGEX_DEBUG
  349. size_t recursion_level = 0;
  350. #endif
  351. auto& bytecode = m_pattern->parser_result.bytecode;
  352. for (;;) {
  353. auto& opcode = bytecode.get_opcode(state);
  354. ++operations;
  355. #if REGEX_DEBUG
  356. s_regex_dbg.print_opcode("VM", opcode, state, recursion_level, false);
  357. #endif
  358. ExecutionResult result;
  359. if (input.fail_counter > 0) {
  360. --input.fail_counter;
  361. result = ExecutionResult::Failed_ExecuteLowPrioForks;
  362. } else {
  363. result = opcode.execute(input, state);
  364. }
  365. #if REGEX_DEBUG
  366. s_regex_dbg.print_result(opcode, bytecode, input, state, result);
  367. #endif
  368. state.instruction_position += opcode.size();
  369. switch (result) {
  370. case ExecutionResult::Fork_PrioLow: {
  371. bool found = false;
  372. if (input.fork_to_replace.has_value()) {
  373. for (auto it = states_to_try_next.reverse_begin(); it != states_to_try_next.reverse_end(); ++it) {
  374. if (it->initiating_fork == input.fork_to_replace.value()) {
  375. (*it) = state;
  376. it->instruction_position = state.fork_at_position;
  377. it->initiating_fork = *input.fork_to_replace;
  378. found = true;
  379. break;
  380. }
  381. }
  382. input.fork_to_replace.clear();
  383. }
  384. if (!found) {
  385. states_to_try_next.append(state);
  386. states_to_try_next.last().initiating_fork = state.instruction_position - opcode.size();
  387. states_to_try_next.last().instruction_position = state.fork_at_position;
  388. }
  389. continue;
  390. }
  391. case ExecutionResult::Fork_PrioHigh: {
  392. bool found = false;
  393. if (input.fork_to_replace.has_value()) {
  394. for (auto it = states_to_try_next.reverse_begin(); it != states_to_try_next.reverse_end(); ++it) {
  395. if (it->initiating_fork == input.fork_to_replace.value()) {
  396. (*it) = state;
  397. it->initiating_fork = *input.fork_to_replace;
  398. found = true;
  399. break;
  400. }
  401. }
  402. input.fork_to_replace.clear();
  403. }
  404. if (!found) {
  405. states_to_try_next.append(state);
  406. states_to_try_next.last().initiating_fork = state.instruction_position - opcode.size();
  407. }
  408. state.instruction_position = state.fork_at_position;
  409. #if REGEX_DEBUG
  410. ++recursion_level;
  411. #endif
  412. continue;
  413. }
  414. case ExecutionResult::Continue:
  415. continue;
  416. case ExecutionResult::Succeeded:
  417. return true;
  418. case ExecutionResult::Failed:
  419. if (!states_to_try_next.is_empty()) {
  420. state = states_to_try_next.take_last();
  421. continue;
  422. }
  423. return false;
  424. case ExecutionResult::Failed_ExecuteLowPrioForks: {
  425. if (states_to_try_next.is_empty()) {
  426. return false;
  427. }
  428. state = states_to_try_next.take_last();
  429. #if REGEX_DEBUG
  430. ++recursion_level;
  431. #endif
  432. continue;
  433. }
  434. }
  435. }
  436. VERIFY_NOT_REACHED();
  437. }
  438. template class Matcher<PosixBasicParser>;
  439. template class Regex<PosixBasicParser>;
  440. template class Matcher<PosixExtendedParser>;
  441. template class Regex<PosixExtendedParser>;
  442. template class Matcher<ECMA262Parser>;
  443. template class Regex<ECMA262Parser>;
  444. }