Regex.cpp 48 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135
  1. /*
  2. * Copyright (c) 2020, Emanuel Sprung <emanuel.sprung@gmail.com>
  3. *
  4. * SPDX-License-Identifier: BSD-2-Clause
  5. */
  6. #include <LibTest/TestCase.h> // import first, to prevent warning of VERIFY* redefinition
  7. #include <AK/Debug.h>
  8. #include <AK/StringBuilder.h>
  9. #include <AK/Tuple.h>
  10. #include <LibRegex/Regex.h>
  11. #include <LibRegex/RegexDebug.h>
  12. #include <LibRegex/RegexMatcher.h>
  13. #include <stdio.h>
  14. static ECMAScriptOptions match_test_api_options(const ECMAScriptOptions options)
  15. {
  16. return options;
  17. }
  18. static PosixOptions match_test_api_options(const PosixOptions options)
  19. {
  20. return options;
  21. }
  22. template<typename... Flags>
  23. static constexpr ECMAScriptFlags combine_flags(Flags&&... flags)
  24. requires((IsSame<Flags, ECMAScriptFlags> && ...))
  25. {
  26. return static_cast<ECMAScriptFlags>((static_cast<regex::FlagsUnderlyingType>(flags) | ...));
  27. }
  28. TEST_CASE(regex_options_ecmascript)
  29. {
  30. ECMAScriptOptions eo;
  31. eo |= ECMAScriptFlags::Global;
  32. EXPECT(eo.has_flag_set(ECMAScriptFlags::Global));
  33. EXPECT(!eo.has_flag_set(ECMAScriptFlags::Insensitive));
  34. eo = match_test_api_options(ECMAScriptFlags::Global | ECMAScriptFlags::Insensitive | ECMAScriptFlags::Sticky);
  35. EXPECT(eo.has_flag_set(ECMAScriptFlags::Global));
  36. EXPECT(eo.has_flag_set(ECMAScriptFlags::Insensitive));
  37. EXPECT(eo.has_flag_set(ECMAScriptFlags::Sticky));
  38. EXPECT(!eo.has_flag_set(ECMAScriptFlags::Unicode));
  39. EXPECT(!eo.has_flag_set(ECMAScriptFlags::Multiline));
  40. EXPECT(!eo.has_flag_set(ECMAScriptFlags::SingleLine));
  41. eo &= ECMAScriptFlags::Insensitive;
  42. EXPECT(!eo.has_flag_set(ECMAScriptFlags::Global));
  43. EXPECT(eo.has_flag_set(ECMAScriptFlags::Insensitive));
  44. EXPECT(!eo.has_flag_set(ECMAScriptFlags::Multiline));
  45. eo &= ECMAScriptFlags::Sticky;
  46. EXPECT(!eo.has_flag_set(ECMAScriptFlags::Global));
  47. EXPECT(!eo.has_flag_set(ECMAScriptFlags::Insensitive));
  48. EXPECT(!eo.has_flag_set(ECMAScriptFlags::Multiline));
  49. EXPECT(!eo.has_flag_set(ECMAScriptFlags::Sticky));
  50. eo = ~ECMAScriptFlags::Insensitive;
  51. EXPECT(eo.has_flag_set(ECMAScriptFlags::Global));
  52. EXPECT(!eo.has_flag_set(ECMAScriptFlags::Insensitive));
  53. EXPECT(eo.has_flag_set(ECMAScriptFlags::Multiline));
  54. EXPECT(eo.has_flag_set(ECMAScriptFlags::Sticky));
  55. }
  56. TEST_CASE(regex_options_posix)
  57. {
  58. PosixOptions eo;
  59. eo |= PosixFlags::Global;
  60. EXPECT(eo.has_flag_set(PosixFlags::Global));
  61. EXPECT(!eo.has_flag_set(PosixFlags::Insensitive));
  62. eo = match_test_api_options(PosixFlags::Global | PosixFlags::Insensitive | PosixFlags::MatchNotBeginOfLine);
  63. EXPECT(eo.has_flag_set(PosixFlags::Global));
  64. EXPECT(eo.has_flag_set(PosixFlags::Insensitive));
  65. EXPECT(eo.has_flag_set(PosixFlags::MatchNotBeginOfLine));
  66. EXPECT(!eo.has_flag_set(PosixFlags::Unicode));
  67. EXPECT(!eo.has_flag_set(PosixFlags::Multiline));
  68. eo &= PosixFlags::Insensitive;
  69. EXPECT(!eo.has_flag_set(PosixFlags::Global));
  70. EXPECT(eo.has_flag_set(PosixFlags::Insensitive));
  71. EXPECT(!eo.has_flag_set(PosixFlags::Multiline));
  72. eo &= PosixFlags::MatchNotBeginOfLine;
  73. EXPECT(!eo.has_flag_set(PosixFlags::Global));
  74. EXPECT(!eo.has_flag_set(PosixFlags::Insensitive));
  75. EXPECT(!eo.has_flag_set(PosixFlags::Multiline));
  76. eo = ~PosixFlags::Insensitive;
  77. EXPECT(eo.has_flag_set(PosixFlags::Global));
  78. EXPECT(!eo.has_flag_set(PosixFlags::Insensitive));
  79. EXPECT(eo.has_flag_set(PosixFlags::Multiline));
  80. }
  81. TEST_CASE(regex_lexer)
  82. {
  83. Lexer l("/[.*+?^${}()|[\\]\\\\]/g"sv);
  84. EXPECT(l.next().type() == regex::TokenType::Slash);
  85. EXPECT(l.next().type() == regex::TokenType::LeftBracket);
  86. EXPECT(l.next().type() == regex::TokenType::Period);
  87. EXPECT(l.next().type() == regex::TokenType::Asterisk);
  88. EXPECT(l.next().type() == regex::TokenType::Plus);
  89. EXPECT(l.next().type() == regex::TokenType::Questionmark);
  90. EXPECT(l.next().type() == regex::TokenType::Circumflex);
  91. EXPECT(l.next().type() == regex::TokenType::Dollar);
  92. EXPECT(l.next().type() == regex::TokenType::LeftCurly);
  93. EXPECT(l.next().type() == regex::TokenType::RightCurly);
  94. EXPECT(l.next().type() == regex::TokenType::LeftParen);
  95. EXPECT(l.next().type() == regex::TokenType::RightParen);
  96. EXPECT(l.next().type() == regex::TokenType::Pipe);
  97. EXPECT(l.next().type() == regex::TokenType::LeftBracket);
  98. EXPECT(l.next().type() == regex::TokenType::EscapeSequence);
  99. EXPECT(l.next().type() == regex::TokenType::EscapeSequence);
  100. EXPECT(l.next().type() == regex::TokenType::RightBracket);
  101. EXPECT(l.next().type() == regex::TokenType::Slash);
  102. EXPECT(l.next().type() == regex::TokenType::Char);
  103. }
  104. TEST_CASE(parser_error_parens)
  105. {
  106. DeprecatedString pattern = "test()test";
  107. Lexer l(pattern);
  108. PosixExtendedParser p(l);
  109. p.parse();
  110. EXPECT(p.has_error());
  111. EXPECT(p.error() == regex::Error::EmptySubExpression);
  112. }
  113. TEST_CASE(parser_error_special_characters_used_at_wrong_place)
  114. {
  115. DeprecatedString pattern;
  116. Vector<char, 5> chars = { '*', '+', '?', '{' };
  117. StringBuilder b;
  118. Lexer l;
  119. PosixExtended p(l);
  120. for (auto& ch : chars) {
  121. // First in ere
  122. b.clear();
  123. b.append(ch);
  124. pattern = b.to_deprecated_string();
  125. l.set_source(pattern);
  126. p.parse();
  127. EXPECT(p.has_error());
  128. EXPECT(p.error() == regex::Error::InvalidRepetitionMarker);
  129. // After vertical line
  130. b.clear();
  131. b.append("a|"sv);
  132. b.append(ch);
  133. pattern = b.to_deprecated_string();
  134. l.set_source(pattern);
  135. p.parse();
  136. EXPECT(p.has_error());
  137. EXPECT(p.error() == regex::Error::InvalidRepetitionMarker);
  138. // After circumflex
  139. b.clear();
  140. b.append('^');
  141. b.append(ch);
  142. pattern = b.to_deprecated_string();
  143. l.set_source(pattern);
  144. p.parse();
  145. EXPECT(p.has_error());
  146. EXPECT(p.error() == regex::Error::InvalidRepetitionMarker);
  147. // After dollar
  148. b.clear();
  149. b.append('$');
  150. b.append(ch);
  151. pattern = b.to_deprecated_string();
  152. l.set_source(pattern);
  153. p.parse();
  154. EXPECT(p.has_error());
  155. EXPECT(p.error() == regex::Error::InvalidRepetitionMarker);
  156. // After left parens
  157. b.clear();
  158. b.append('(');
  159. b.append(ch);
  160. b.append(')');
  161. pattern = b.to_deprecated_string();
  162. l.set_source(pattern);
  163. p.parse();
  164. EXPECT(p.has_error());
  165. EXPECT(p.error() == regex::Error::InvalidRepetitionMarker);
  166. }
  167. }
  168. TEST_CASE(parser_error_vertical_line_used_at_wrong_place)
  169. {
  170. Lexer l;
  171. PosixExtended p(l);
  172. // First in ere
  173. l.set_source("|asdf"sv);
  174. p.parse();
  175. EXPECT(p.has_error());
  176. EXPECT(p.error() == regex::Error::EmptySubExpression);
  177. // Last in ere
  178. l.set_source("asdf|"sv);
  179. p.parse();
  180. EXPECT(p.has_error());
  181. EXPECT(p.error() == regex::Error::EmptySubExpression);
  182. // After left parens
  183. l.set_source("(|asdf)"sv);
  184. p.parse();
  185. EXPECT(p.has_error());
  186. EXPECT(p.error() == regex::Error::EmptySubExpression);
  187. // Proceed right parens
  188. l.set_source("(asdf)|"sv);
  189. p.parse();
  190. EXPECT(p.has_error());
  191. EXPECT(p.error() == regex::Error::EmptySubExpression);
  192. }
  193. TEST_CASE(catch_all_first)
  194. {
  195. Regex<PosixExtended> re("^.*$");
  196. RegexResult m;
  197. re.match("Hello World"sv, m);
  198. EXPECT(m.count == 1);
  199. EXPECT(re.match("Hello World"sv, m));
  200. }
  201. TEST_CASE(catch_all)
  202. {
  203. Regex<PosixExtended> re("^.*$", PosixFlags::Global);
  204. EXPECT(re.has_match("Hello World"sv));
  205. EXPECT(re.match("Hello World"sv).success);
  206. EXPECT(re.match("Hello World"sv).count == 1);
  207. EXPECT(has_match("Hello World"sv, re));
  208. auto res = match("Hello World"sv, re);
  209. EXPECT(res.success);
  210. EXPECT(res.count == 1);
  211. EXPECT(res.matches.size() == 1);
  212. EXPECT(res.matches.first().view == "Hello World");
  213. }
  214. TEST_CASE(catch_all_again)
  215. {
  216. Regex<PosixExtended> re("^.*$", PosixFlags::Extra);
  217. EXPECT_EQ(has_match("Hello World"sv, re), true);
  218. }
  219. TEST_CASE(char_utf8)
  220. {
  221. Regex<PosixExtended> re("😀");
  222. RegexResult result;
  223. EXPECT_EQ((result = match(Utf8View { "Привет, мир! 😀 γειά σου κόσμος 😀 こんにちは世界"sv }, re, PosixFlags::Global)).success, true);
  224. EXPECT_EQ(result.count, 2u);
  225. }
  226. TEST_CASE(catch_all_newline)
  227. {
  228. Regex<PosixExtended> re("^.*$", PosixFlags::Multiline | PosixFlags::StringCopyMatches);
  229. RegexResult result;
  230. auto lambda = [&result, &re]() {
  231. DeprecatedString aaa = "Hello World\nTest\n1234\n";
  232. result = match(aaa, re);
  233. EXPECT_EQ(result.success, true);
  234. };
  235. lambda();
  236. EXPECT_EQ(result.count, 3u);
  237. EXPECT_EQ(result.matches.at(0).view, "Hello World");
  238. EXPECT_EQ(result.matches.at(1).view, "Test");
  239. EXPECT_EQ(result.matches.at(2).view, "1234");
  240. }
  241. TEST_CASE(catch_all_newline_view)
  242. {
  243. Regex<PosixExtended> re("^.*$", PosixFlags::Multiline);
  244. RegexResult result;
  245. DeprecatedString aaa = "Hello World\nTest\n1234\n";
  246. result = match(aaa, re);
  247. EXPECT_EQ(result.success, true);
  248. EXPECT_EQ(result.count, 3u);
  249. DeprecatedString str = "Hello World";
  250. EXPECT_EQ(result.matches.at(0).view, str.view());
  251. EXPECT_EQ(result.matches.at(1).view, "Test");
  252. EXPECT_EQ(result.matches.at(2).view, "1234");
  253. }
  254. TEST_CASE(catch_all_newline_2)
  255. {
  256. Regex<PosixExtended> re("^.*$");
  257. RegexResult result;
  258. result = match("Hello World\nTest\n1234\n"sv, re, PosixFlags::Multiline | PosixFlags::StringCopyMatches);
  259. EXPECT_EQ(result.success, true);
  260. EXPECT_EQ(result.count, 3u);
  261. EXPECT_EQ(result.matches.at(0).view, "Hello World");
  262. EXPECT_EQ(result.matches.at(1).view, "Test");
  263. EXPECT_EQ(result.matches.at(2).view, "1234");
  264. result = match("Hello World\nTest\n1234\n"sv, re);
  265. EXPECT_EQ(result.success, true);
  266. EXPECT_EQ(result.count, 1u);
  267. EXPECT_EQ(result.matches.at(0).view, "Hello World\nTest\n1234\n");
  268. }
  269. TEST_CASE(match_all_character_class)
  270. {
  271. Regex<PosixExtended> re("[[:alpha:]]");
  272. DeprecatedString str = "[Window]\nOpacity=255\nAudibleBeep=0\n";
  273. RegexResult result = match(str, re, PosixFlags::Global | PosixFlags::StringCopyMatches);
  274. EXPECT_EQ(result.success, true);
  275. EXPECT_EQ(result.count, 24u);
  276. EXPECT_EQ(result.matches.at(0).view, "W");
  277. EXPECT_EQ(result.matches.at(1).view, "i");
  278. EXPECT_EQ(result.matches.at(2).view, "n");
  279. }
  280. TEST_CASE(match_character_class_with_assertion)
  281. {
  282. Regex<PosixExtended> re("[[:alpha:]]+$");
  283. DeprecatedString str = "abcdef";
  284. RegexResult result = match(str, re);
  285. EXPECT_EQ(result.success, true);
  286. EXPECT_EQ(result.count, 1u);
  287. }
  288. TEST_CASE(example_for_git_commit)
  289. {
  290. Regex<PosixExtended> re("^.*$");
  291. auto result = re.match("Well, hello friends!\nHello World!"sv);
  292. EXPECT(result.success);
  293. EXPECT(result.count == 1);
  294. EXPECT(result.matches.at(0).view.starts_with("Well"sv));
  295. EXPECT(result.matches.at(0).view.length() == 33);
  296. EXPECT(re.has_match("Well,...."sv));
  297. result = re.match("Well, hello friends!\nHello World!"sv, PosixFlags::Multiline);
  298. EXPECT(result.success);
  299. EXPECT(result.count == 2);
  300. EXPECT(result.matches.at(0).view == "Well, hello friends!");
  301. EXPECT(result.matches.at(1).view == "Hello World!");
  302. }
  303. TEST_CASE(email_address)
  304. {
  305. Regex<PosixExtended> re("^[A-Z0-9a-z._%+-]{1,64}@([A-Za-z0-9-]{1,63}\\.){1,125}[A-Za-z]{2,63}$");
  306. EXPECT(re.has_match("hello.world@domain.tld"sv));
  307. EXPECT(re.has_match("this.is.a.very_long_email_address@world.wide.web"sv));
  308. }
  309. TEST_CASE(ini_file_entries)
  310. {
  311. Regex<PosixExtended> re("[[:alpha:]]*=([[:digit:]]*)|\\[(.*)\\]");
  312. RegexResult result;
  313. if constexpr (REGEX_DEBUG) {
  314. RegexDebug regex_dbg(stderr);
  315. regex_dbg.print_raw_bytecode(re);
  316. regex_dbg.print_header();
  317. regex_dbg.print_bytecode(re);
  318. }
  319. DeprecatedString haystack = "[Window]\nOpacity=255\nAudibleBeep=0\n";
  320. EXPECT_EQ(re.search(haystack.view(), result, PosixFlags::Multiline), true);
  321. EXPECT_EQ(result.count, 3u);
  322. if constexpr (REGEX_DEBUG) {
  323. for (auto& v : result.matches)
  324. fprintf(stderr, "%s\n", v.view.to_deprecated_string().characters());
  325. }
  326. EXPECT_EQ(result.matches.at(0).view, "[Window]");
  327. EXPECT_EQ(result.capture_group_matches.at(0).at(0).view, "Window");
  328. EXPECT_EQ(result.matches.at(1).view, "Opacity=255");
  329. EXPECT_EQ(result.matches.at(1).line, 1u);
  330. EXPECT_EQ(result.matches.at(1).column, 0u);
  331. EXPECT_EQ(result.capture_group_matches.at(1).at(0).view, "255");
  332. EXPECT_EQ(result.capture_group_matches.at(1).at(0).line, 1u);
  333. EXPECT_EQ(result.capture_group_matches.at(1).at(0).column, 8u);
  334. EXPECT_EQ(result.matches.at(2).view, "AudibleBeep=0");
  335. EXPECT_EQ(result.capture_group_matches.at(2).at(0).view, "0");
  336. EXPECT_EQ(result.capture_group_matches.at(2).at(0).line, 2u);
  337. EXPECT_EQ(result.capture_group_matches.at(2).at(0).column, 12u);
  338. }
  339. TEST_CASE(ini_file_entries2)
  340. {
  341. Regex<PosixExtended> re("[[:alpha:]]*=([[:digit:]]*)");
  342. RegexResult result;
  343. DeprecatedString haystack = "ViewMode=Icon";
  344. EXPECT_EQ(re.match(haystack.view(), result), false);
  345. EXPECT_EQ(result.count, 0u);
  346. EXPECT_EQ(re.search(haystack.view(), result), true);
  347. EXPECT_EQ(result.count, 1u);
  348. }
  349. TEST_CASE(named_capture_group)
  350. {
  351. Regex<PosixExtended> re("[[:alpha:]]*=(?<Test>[[:digit:]]*)");
  352. RegexResult result;
  353. if constexpr (REGEX_DEBUG) {
  354. RegexDebug regex_dbg(stderr);
  355. regex_dbg.print_raw_bytecode(re);
  356. regex_dbg.print_header();
  357. regex_dbg.print_bytecode(re);
  358. }
  359. DeprecatedString haystack = "[Window]\nOpacity=255\nAudibleBeep=0\n";
  360. EXPECT_EQ(re.search(haystack, result, PosixFlags::Multiline), true);
  361. EXPECT_EQ(result.count, 2u);
  362. EXPECT_EQ(result.matches.at(0).view, "Opacity=255");
  363. EXPECT_EQ(result.capture_group_matches.at(0).at(0).view, "255");
  364. EXPECT_EQ(result.capture_group_matches.at(0).at(0).capture_group_name, "Test");
  365. EXPECT_EQ(result.matches.at(1).view, "AudibleBeep=0");
  366. EXPECT_EQ(result.capture_group_matches.at(1).at(0).view, "0");
  367. EXPECT_EQ(result.capture_group_matches.at(1).at(0).capture_group_name, "Test");
  368. }
  369. TEST_CASE(ecma262_named_capture_group_with_dollar_sign)
  370. {
  371. Regex<ECMA262> re("[a-zA-Z]*=(?<$Test$>[0-9]*)");
  372. RegexResult result;
  373. if constexpr (REGEX_DEBUG) {
  374. RegexDebug regex_dbg(stderr);
  375. regex_dbg.print_raw_bytecode(re);
  376. regex_dbg.print_header();
  377. regex_dbg.print_bytecode(re);
  378. }
  379. DeprecatedString haystack = "[Window]\nOpacity=255\nAudibleBeep=0\n";
  380. EXPECT_EQ(re.search(haystack, result, ECMAScriptFlags::Multiline), true);
  381. EXPECT_EQ(result.count, 2u);
  382. EXPECT_EQ(result.matches.at(0).view, "Opacity=255");
  383. EXPECT_EQ(result.capture_group_matches.at(0).at(0).view, "255");
  384. EXPECT_EQ(result.capture_group_matches.at(0).at(0).capture_group_name, "$Test$");
  385. EXPECT_EQ(result.matches.at(1).view, "AudibleBeep=0");
  386. EXPECT_EQ(result.capture_group_matches.at(1).at(0).view, "0");
  387. EXPECT_EQ(result.capture_group_matches.at(1).at(0).capture_group_name, "$Test$");
  388. }
  389. TEST_CASE(a_star)
  390. {
  391. Regex<PosixExtended> re("a*");
  392. RegexResult result;
  393. if constexpr (REGEX_DEBUG) {
  394. RegexDebug regex_dbg(stderr);
  395. regex_dbg.print_raw_bytecode(re);
  396. regex_dbg.print_header();
  397. regex_dbg.print_bytecode(re);
  398. }
  399. DeprecatedString haystack = "[Window]\nOpacity=255\nAudibleBeep=0\n";
  400. EXPECT_EQ(re.search(haystack.view(), result, PosixFlags::Multiline), true);
  401. EXPECT_EQ(result.count, 32u);
  402. if (result.count == 32u) {
  403. EXPECT_EQ(result.matches.at(0).view.length(), 0u);
  404. EXPECT_EQ(result.matches.at(10).view.length(), 1u);
  405. EXPECT_EQ(result.matches.at(10).view, "a");
  406. EXPECT_EQ(result.matches.at(31).view.length(), 0u);
  407. }
  408. }
  409. TEST_CASE(simple_period_end_benchmark)
  410. {
  411. Regex<PosixExtended> re("hello.$");
  412. RegexResult m;
  413. EXPECT_EQ(re.search("Hello1"sv, m), false);
  414. EXPECT_EQ(re.search("hello1hello1"sv, m), true);
  415. EXPECT_EQ(re.search("hello2hell"sv, m), false);
  416. EXPECT_EQ(re.search("hello?"sv, m), true);
  417. }
  418. TEST_CASE(posix_extended_nested_capture_group)
  419. {
  420. Regex<PosixExtended> re("(h(e(?<llo>llo)))"); // group 0 -> "hello", group 1 -> "ello", group 2/"llo" -> "llo"
  421. auto result = re.match("hello"sv);
  422. EXPECT(result.success);
  423. EXPECT_EQ(result.capture_group_matches.size(), 1u);
  424. EXPECT_EQ(result.capture_group_matches[0].size(), 3u);
  425. EXPECT_EQ(result.capture_group_matches[0][0].view, "hello"sv);
  426. EXPECT_EQ(result.capture_group_matches[0][1].view, "ello"sv);
  427. EXPECT_EQ(result.capture_group_matches[0][2].view, "llo"sv);
  428. }
  429. auto parse_test_case_long_disjunction_chain = DeprecatedString::repeated("a|"sv, 100000);
  430. TEST_CASE(ECMA262_parse)
  431. {
  432. struct _test {
  433. StringView pattern;
  434. regex::Error expected_error { regex::Error::NoError };
  435. regex::ECMAScriptFlags flags {};
  436. };
  437. _test const tests[] {
  438. { "^hello.$"sv },
  439. { "^(hello.)$"sv },
  440. { "^h{0,1}ello.$"sv },
  441. { "^hello\\W$"sv },
  442. { "^hell\\w.$"sv },
  443. { "^hell\\x6f1$"sv }, // ^hello1$
  444. { "^hel(?:l\\w).$"sv },
  445. { "^hel(?<LO>l\\w).$"sv },
  446. { "^[-a-zA-Z\\w\\s]+$"sv },
  447. { "\\bhello\\B"sv },
  448. { "^[\\w+/_-]+[=]{0,2}$"sv }, // #4189
  449. { "^(?:[^<]*(<[\\w\\W]+>)[^>]*$|#([\\w\\-]*)$)"sv }, // #4189
  450. { "\\/"sv }, // #4189
  451. { ",/=-:"sv }, // #4243
  452. { "\\x"sv }, // Even invalid escapes are allowed if ~unicode.
  453. { "\\x1"sv }, // Even invalid escapes are allowed if ~unicode.
  454. { "\\x1"sv, regex::Error::InvalidPattern, regex::ECMAScriptFlags::Unicode },
  455. { "\\x11"sv },
  456. { "\\x11"sv, regex::Error::NoError, regex::ECMAScriptFlags::Unicode },
  457. { "\\"sv, regex::Error::InvalidTrailingEscape },
  458. { "(?"sv, regex::Error::InvalidCaptureGroup },
  459. { "\\u1234"sv, regex::Error::NoError, regex::ECMAScriptFlags::Unicode },
  460. { "[\\u1234]"sv, regex::Error::NoError, regex::ECMAScriptFlags::Unicode },
  461. { "\\u1"sv, regex::Error::InvalidPattern, regex::ECMAScriptFlags::Unicode },
  462. { "[\\u1]"sv, regex::Error::InvalidPattern, regex::ECMAScriptFlags::Unicode },
  463. { ",(?"sv, regex::Error::InvalidCaptureGroup }, // #4583
  464. { "{1}"sv, regex::Error::InvalidPattern },
  465. { "{1,2}"sv, regex::Error::InvalidPattern },
  466. { "\\uxxxx"sv, regex::Error::NoError },
  467. { "\\uxxxx"sv, regex::Error::InvalidPattern, ECMAScriptFlags::Unicode },
  468. { "\\ud83d"sv, regex::Error::NoError, ECMAScriptFlags::Unicode },
  469. { "\\ud83d\\uxxxx"sv, regex::Error::InvalidPattern, ECMAScriptFlags::Unicode },
  470. { "\\u{0}"sv },
  471. { "\\u{0}"sv, regex::Error::NoError, ECMAScriptFlags::Unicode },
  472. { "\\u{10ffff}"sv, regex::Error::NoError, ECMAScriptFlags::Unicode },
  473. { "\\u{10ffff"sv, regex::Error::InvalidPattern, ECMAScriptFlags::Unicode },
  474. { "\\u{10ffffx"sv, regex::Error::InvalidPattern, ECMAScriptFlags::Unicode },
  475. { "\\u{110000}"sv, regex::Error::InvalidPattern, ECMAScriptFlags::Unicode },
  476. { "\\p"sv, regex::Error::InvalidPattern, ECMAScriptFlags::Unicode },
  477. { "\\p{"sv, regex::Error::InvalidPattern, ECMAScriptFlags::Unicode },
  478. { "\\p{}"sv, regex::Error::InvalidNameForProperty, ECMAScriptFlags::Unicode },
  479. { "\\p{AsCiI}"sv, regex::Error::InvalidNameForProperty, ECMAScriptFlags::Unicode },
  480. { "\\p{hello friends}"sv, regex::Error::InvalidNameForProperty, ECMAScriptFlags::Unicode },
  481. { "\\p{Prepended_Concatenation_Mark}"sv, regex::Error::InvalidNameForProperty, ECMAScriptFlags::Unicode },
  482. { "\\p{ASCII}"sv, regex::Error::NoError, ECMAScriptFlags::Unicode },
  483. { "\\\\p{1}"sv, regex::Error::NoError, ECMAScriptFlags::Unicode },
  484. { "\\\\p{AsCiI}"sv, regex::Error::InvalidPattern, ECMAScriptFlags::Unicode },
  485. { "\\\\p{ASCII}"sv, regex::Error::InvalidPattern, ECMAScriptFlags::Unicode },
  486. { "\\c"sv, regex::Error::NoError, ECMAScriptFlags::BrowserExtended },
  487. { "\\c"sv, regex::Error::InvalidPattern, ECMAScriptFlags::Unicode },
  488. { "[\\c]"sv, regex::Error::NoError, ECMAScriptFlags::BrowserExtended },
  489. { "[\\c]"sv, regex::Error::InvalidPattern, ECMAScriptFlags::Unicode },
  490. { "\\c`"sv, regex::Error::NoError, ECMAScriptFlags::BrowserExtended },
  491. { "\\c`"sv, regex::Error::InvalidPattern, ECMAScriptFlags::Unicode },
  492. { "[\\c`]"sv, regex::Error::NoError, ECMAScriptFlags::BrowserExtended },
  493. { "[\\c`]"sv, regex::Error::InvalidPattern, ECMAScriptFlags::Unicode },
  494. { "\\A"sv, regex::Error::NoError, ECMAScriptFlags::BrowserExtended },
  495. { "\\A"sv, regex::Error::InvalidCharacterClass, ECMAScriptFlags::Unicode },
  496. { "[\\A]"sv, regex::Error::NoError, ECMAScriptFlags::BrowserExtended },
  497. { "[\\A]"sv, regex::Error::InvalidPattern, ECMAScriptFlags::Unicode },
  498. { "\\0"sv, regex::Error::NoError, ECMAScriptFlags::BrowserExtended },
  499. { "\\0"sv, regex::Error::NoError, combine_flags(ECMAScriptFlags::Unicode, ECMAScriptFlags::BrowserExtended) },
  500. { "\\00"sv, regex::Error::NoError, ECMAScriptFlags::BrowserExtended },
  501. { "\\00"sv, regex::Error::InvalidCharacterClass, combine_flags(ECMAScriptFlags::Unicode, ECMAScriptFlags::BrowserExtended) },
  502. { "[\\0]"sv, regex::Error::NoError, ECMAScriptFlags::BrowserExtended },
  503. { "[\\0]"sv, regex::Error::NoError, combine_flags(ECMAScriptFlags::Unicode, ECMAScriptFlags::BrowserExtended) },
  504. { "[\\00]"sv, regex::Error::NoError, ECMAScriptFlags::BrowserExtended },
  505. { "[\\00]"sv, regex::Error::InvalidPattern, combine_flags(ECMAScriptFlags::Unicode, ECMAScriptFlags::BrowserExtended) },
  506. { "\\^\\$\\\\\\.\\*\\+\\?\\(\\)\\[\\]\\{\\}\\|\\/"sv, regex::Error::NoError, ECMAScriptFlags::Unicode },
  507. { "[\\^\\$\\\\\\.\\*\\+\\?\\(\\)\\[\\]\\{\\}\\|\\/]"sv, regex::Error::NoError, ECMAScriptFlags::Unicode },
  508. { "]"sv, regex::Error::NoError, ECMAScriptFlags::BrowserExtended },
  509. { "]"sv, regex::Error::InvalidPattern, ECMAScriptFlags::Unicode },
  510. { "\\]"sv, regex::Error::NoError, ECMAScriptFlags::Unicode },
  511. { "}"sv, regex::Error::NoError, ECMAScriptFlags::BrowserExtended },
  512. { "}"sv, regex::Error::InvalidPattern, ECMAScriptFlags::Unicode },
  513. { "\\}"sv, regex::Error::NoError, ECMAScriptFlags::Unicode },
  514. { "a{9007199254740991}"sv }, // 2^53 - 1
  515. { "a{9007199254740991,}"sv },
  516. { "a{9007199254740991,9007199254740991}"sv },
  517. { "a{9007199254740992}"sv, regex::Error::InvalidBraceContent },
  518. { "a{9007199254740992,}"sv, regex::Error::InvalidBraceContent },
  519. { "a{9007199254740991,9007199254740992}"sv, regex::Error::InvalidBraceContent },
  520. { "a{9007199254740992,9007199254740991}"sv, regex::Error::InvalidBraceContent },
  521. { "a{9007199254740992,9007199254740992}"sv, regex::Error::InvalidBraceContent },
  522. { "(?<a>a)(?<a>b)"sv, regex::Error::DuplicateNamedCapture },
  523. { "(?<a>a)(?<b>b)(?<a>c)"sv, regex::Error::DuplicateNamedCapture },
  524. { "(?<1a>a)"sv, regex::Error::InvalidNameForCaptureGroup },
  525. { "(?<\\a>a)"sv, regex::Error::InvalidNameForCaptureGroup },
  526. { "(?<\ta>a)"sv, regex::Error::InvalidNameForCaptureGroup },
  527. { "(?<$$_$$>a)"sv },
  528. { "(?<ÿ>a)"sv },
  529. { "(?<𝓑𝓻𝓸𝔀𝓷>a)"sv },
  530. { "((?=lg)?[vl]k\\-?\\d{3}) bui| 3\\.[-\\w; ]{10}lg?-([06cv9]{3,4})"sv, regex::Error::NoError, ECMAScriptFlags::BrowserExtended }, // #12373, quantifiable assertions.
  531. { parse_test_case_long_disjunction_chain.view() }, // A whole lot of disjunctions, should not overflow the stack.
  532. { "(\"|')(?:(?!\\2)[^\\\\\\r\\n]|\\\\.)*\\2"sv, regex::Error::NoError, ECMAScriptFlags::BrowserExtended }, // LegacyOctalEscapeSequence should not consume too many chars (and should not crash)
  533. };
  534. for (auto& test : tests) {
  535. Regex<ECMA262> re(test.pattern, test.flags);
  536. EXPECT_EQ(re.parser_result.error, test.expected_error);
  537. if constexpr (REGEX_DEBUG) {
  538. dbgln("\n");
  539. RegexDebug regex_dbg(stderr);
  540. regex_dbg.print_raw_bytecode(re);
  541. regex_dbg.print_header();
  542. regex_dbg.print_bytecode(re);
  543. dbgln("\n");
  544. }
  545. }
  546. }
  547. TEST_CASE(ECMA262_match)
  548. {
  549. constexpr auto global_multiline = ECMAScriptFlags::Global | ECMAScriptFlags::Multiline;
  550. struct _test {
  551. StringView pattern;
  552. StringView subject;
  553. bool matches { true };
  554. ECMAScriptFlags options {};
  555. };
  556. // clang-format off
  557. constexpr _test tests[] {
  558. { "^hello.$"sv, "hello1"sv },
  559. { "^(hello.)$"sv, "hello1"sv },
  560. { "^h{0,1}ello.$"sv, "ello1"sv },
  561. { "^hello\\W$"sv, "hello!"sv },
  562. { "^hell\\w.$"sv, "hellx!"sv },
  563. { "^hell\\x6f1$"sv, "hello1"sv },
  564. { "^hel(?<LO>l.)1$"sv, "hello1"sv },
  565. { "^hel(?<LO>l.)1*\\k<LO>.$"sv, "hello1lo1"sv },
  566. { "^[-a-z1-3\\s]+$"sv, "hell2 o1"sv },
  567. { "^[\\0-\\x1f]$"sv, "\n"sv },
  568. { .pattern = "\\bhello\\B"sv, .subject = "hello1"sv, .options = ECMAScriptFlags::Global },
  569. { "\\b.*\\b"sv, "hello1"sv },
  570. { "[^\\D\\S]{2}"sv, "1 "sv },
  571. { "bar(?=f.)foo"sv, "barfoo"sv },
  572. { "bar(?=foo)bar"sv, "barbar"sv, false },
  573. { "bar(?!foo)bar"sv, "barbar"sv, true },
  574. { "bar(?!bar)bar"sv, "barbar"sv, false },
  575. { "bar.*(?<=foo)"sv, "barbar"sv, false },
  576. { "bar.*(?<!foo)"sv, "barbar"sv, true },
  577. { "((...)X)+"sv, "fooXbarXbazX"sv, true },
  578. { "(?:)"sv, ""sv, true },
  579. { "\\^"sv, "^"sv },
  580. { "\\^\\$\\\\\\.\\*\\+\\?\\(\\)\\[\\]\\{\\}\\|\\/"sv, "^$\\.*+?()[]{}|/"sv, true, ECMAScriptFlags::Unicode },
  581. { "[\\^\\$\\\\\\.\\*\\+\\?\\(\\)\\[\\]\\{\\}\\|\\/]{15}"sv, "^$\\.*+?()[]{}|/"sv, true, ECMAScriptFlags::Unicode },
  582. { "(a{2}){3}"sv, "aaaaaa"sv },
  583. { "(a{2}){3}"sv, "aaaabaa"sv, false },
  584. { "(a{2}){4}"sv, "aaaaaaaa"sv },
  585. { "(a{2}){4}"sv, "aaaaaabaa"sv, false },
  586. { "(a{3}){2}"sv, "aaaaaa"sv },
  587. { "(a{3}){2}"sv, "aaaabaa"sv, false },
  588. { "(a{4}){2}"sv, "aaaaaaaa"sv },
  589. { "(a{4}){2}"sv, "aaaaaabaa"sv, false },
  590. { "\\u{4}"sv, "uuuu"sv },
  591. { "(?<=.{3})f"sv, "abcdef"sv, true, (ECMAScriptFlags)regex::AllFlags::Global },
  592. { "(?<=.{3})f"sv, "abc😀ef"sv, true, (ECMAScriptFlags)regex::AllFlags::Global },
  593. // ECMA262, B.1.4. Regular Expression Pattern extensions for browsers
  594. { "{"sv, "{"sv, true, ECMAScriptFlags::BrowserExtended },
  595. { "\\5"sv, "\5"sv, true, ECMAScriptFlags::BrowserExtended },
  596. { "\\05"sv, "\5"sv, true, ECMAScriptFlags::BrowserExtended },
  597. { "\\455"sv, "\45""5"sv, true, ECMAScriptFlags::BrowserExtended },
  598. { "\\314"sv, "\314"sv, true, ECMAScriptFlags::BrowserExtended },
  599. { "\\c"sv, "\\c"sv, true, ECMAScriptFlags::BrowserExtended },
  600. { "\\cf"sv, "\06"sv, true, ECMAScriptFlags::BrowserExtended },
  601. { "\\c1"sv, "\\c1"sv, true, ECMAScriptFlags::BrowserExtended },
  602. { "[\\c1]"sv, "\x11"sv, true, ECMAScriptFlags::BrowserExtended },
  603. { "[\\w-\\d]"sv, "-"sv, true, ECMAScriptFlags::BrowserExtended },
  604. { "^(?:^^\\.?|[!+-]|!=|!==|#|%|%=|&|&&|&&=|&=|\\(|\\*|\\*=|\\+=|,|-=|->|\\/|\\/=|:|::|;|<|<<|<<=|<=|=|==|===|>|>=|>>|>>=|>>>|>>>=|[?@[^]|\\^=|\\^\\^|\\^\\^=|{|\\||\\|=|\\|\\||\\|\\|=|~|break|case|continue|delete|do|else|finally|instanceof|return|throw|try|typeof)\\s*(\\/(?=[^*/])(?:[^/[\\\\]|\\\\[\\S\\s]|\\[(?:[^\\\\\\]]|\\\\[\\S\\s])*(?:]|$))+\\/)"sv,
  605. "return /xx/"sv, true, ECMAScriptFlags::BrowserExtended
  606. }, // #5517, appears to be matching JS expressions that involve regular expressions...
  607. { "a{2,}"sv, "aaaa"sv }, // #5518
  608. { "\\0"sv, "\0"sv, true, ECMAScriptFlags::BrowserExtended },
  609. { "\\0"sv, "\0"sv, true, combine_flags(ECMAScriptFlags::Unicode, ECMAScriptFlags::BrowserExtended) },
  610. { "\\01"sv, "\1"sv, true, ECMAScriptFlags::BrowserExtended },
  611. { "[\\0]"sv, "\0"sv, true, ECMAScriptFlags::BrowserExtended },
  612. { "[\\0]"sv, "\0"sv, true, combine_flags(ECMAScriptFlags::Unicode, ECMAScriptFlags::BrowserExtended) },
  613. { "[\\01]"sv, "\1"sv, true, ECMAScriptFlags::BrowserExtended },
  614. { "(\0|a)"sv, "a"sv, true }, // #9686, Should allow null bytes in pattern
  615. { "(.*?)a(?!(a+)b\\2c)\\2(.*)"sv, "baaabaac"sv, true }, // #6042, Groups inside lookarounds may be referenced outside, but their contents appear empty if the pattern in the lookaround fails.
  616. { "a|$"sv, "x"sv, true, (ECMAScriptFlags)regex::AllFlags::Global }, // #11940, Global (not the 'g' flag) regexps should attempt to match the zero-length end of the string too.
  617. { "foo\nbar"sv, "foo\nbar"sv, true }, // #12126, ECMA262 regexp should match literal newlines without the 's' flag.
  618. { "foo[^]bar"sv, "foo\nbar"sv, true }, // #12126, ECMA262 regexp should match newline with [^].
  619. { "^[_A-Z]+$"sv, "_aA"sv, true, ECMAScriptFlags::Insensitive }, // Insensitive lookup table: characters in a range do not necessarily lie in the same range after being converted to lowercase.
  620. { "^[a-sy-z]$"sv, "b"sv, true, ECMAScriptFlags::Insensitive },
  621. { "^[a-sy-z]$"sv, "y"sv, true, ECMAScriptFlags::Insensitive },
  622. { "^[a-sy-z]$"sv, "u"sv, false, ECMAScriptFlags::Insensitive },
  623. { "."sv, "\n\r\u2028\u2029"sv, false }, // Dot should not match any of CR/LF/LS/PS in ECMA262 mode without DotAll.
  624. { "a$"sv, "a\r\n"sv, true, global_multiline.value() }, // $ should accept all LineTerminators in ECMA262 mode with Multiline.
  625. { "^a"sv, "\ra"sv, true, global_multiline.value() },
  626. { "^(.*?):[ \\t]*([^\\r\\n]*)$"sv, "content-length: 488\r\ncontent-type: application/json; charset=utf-8\r\n"sv, true, global_multiline.value() },
  627. };
  628. // clang-format on
  629. for (auto& test : tests) {
  630. Regex<ECMA262> re(test.pattern, test.options);
  631. if constexpr (REGEX_DEBUG) {
  632. dbgln("\n");
  633. RegexDebug regex_dbg(stderr);
  634. regex_dbg.print_raw_bytecode(re);
  635. regex_dbg.print_header();
  636. regex_dbg.print_bytecode(re);
  637. dbgln("\n");
  638. }
  639. EXPECT_EQ(re.parser_result.error, regex::Error::NoError);
  640. EXPECT_EQ(re.match(test.subject).success, test.matches);
  641. }
  642. }
  643. TEST_CASE(ECMA262_unicode_match)
  644. {
  645. constexpr auto space_and_line_terminator_code_points = Array { 0x0009, 0x000A, 0x000B, 0x000C, 0x000D, 0x0020, 0x00A0, 0x1680, 0x2000, 0x2001, 0x2002, 0x2003, 0x2004, 0x2005, 0x2006, 0x2007, 0x2008, 0x2009, 0x200A, 0x2028, 0x2029, 0x202F, 0x205F, 0x3000, 0xFEFF };
  646. StringBuilder builder;
  647. for (u32 code_point : space_and_line_terminator_code_points)
  648. builder.append_code_point(code_point);
  649. auto space_and_line_terminators = builder.to_deprecated_string();
  650. struct _test {
  651. StringView pattern;
  652. StringView subject;
  653. bool matches { true };
  654. ECMAScriptFlags options {};
  655. };
  656. _test tests[] {
  657. { "\xf0\x9d\x8c\x86"sv, "abcdef"sv, false, ECMAScriptFlags::Unicode },
  658. { "[\xf0\x9d\x8c\x86]"sv, "abcdef"sv, false, ECMAScriptFlags::Unicode },
  659. { "\\ud83d"sv, "😀"sv, true },
  660. { "\\ud83d"sv, "😀"sv, false, ECMAScriptFlags::Unicode },
  661. { "\\ude00"sv, "😀"sv, true },
  662. { "\\ude00"sv, "😀"sv, false, ECMAScriptFlags::Unicode },
  663. { "\\ud83d\\ude00"sv, "😀"sv, true },
  664. { "\\ud83d\\ude00"sv, "😀"sv, true, ECMAScriptFlags::Unicode },
  665. { "\\u{1f600}"sv, "😀"sv, true, ECMAScriptFlags::Unicode },
  666. { "\\ud83d\\ud83d"sv, "\xed\xa0\xbd\xed\xa0\xbd"sv, true },
  667. { "\\ud83d\\ud83d"sv, "\xed\xa0\xbd\xed\xa0\xbd"sv, true, ECMAScriptFlags::Unicode },
  668. { "(?<=.{3})f"sv, "abcdef"sv, true, ECMAScriptFlags::Unicode },
  669. { "(?<=.{3})f"sv, "abc😀ef"sv, true, ECMAScriptFlags::Unicode },
  670. { "(?<𝓑𝓻𝓸𝔀𝓷>brown)"sv, "brown"sv, true, ECMAScriptFlags::Unicode },
  671. { "(?<\\u{1d4d1}\\u{1d4fb}\\u{1d4f8}\\u{1d500}\\u{1d4f7}>brown)"sv, "brown"sv, true, ECMAScriptFlags::Unicode },
  672. { "(?<\\ud835\\udcd1\\ud835\\udcfb\\ud835\\udcf8\\ud835\\udd00\\ud835\\udcf7>brown)"sv, "brown"sv, true, ECMAScriptFlags::Unicode },
  673. { "^\\s+$"sv, space_and_line_terminators },
  674. { "^\\s+$"sv, space_and_line_terminators, true, ECMAScriptFlags::Unicode },
  675. };
  676. for (auto& test : tests) {
  677. Regex<ECMA262> re(test.pattern, (ECMAScriptFlags)regex::AllFlags::Global | test.options);
  678. auto subject = MUST(AK::utf8_to_utf16(test.subject));
  679. Utf16View view { subject };
  680. if constexpr (REGEX_DEBUG) {
  681. dbgln("\n");
  682. RegexDebug regex_dbg(stderr);
  683. regex_dbg.print_raw_bytecode(re);
  684. regex_dbg.print_header();
  685. regex_dbg.print_bytecode(re);
  686. dbgln("\n");
  687. }
  688. EXPECT_EQ(re.parser_result.error, regex::Error::NoError);
  689. EXPECT_EQ(re.match(view).success, test.matches);
  690. }
  691. }
  692. TEST_CASE(ECMA262_unicode_sets_match)
  693. {
  694. struct _test {
  695. StringView pattern;
  696. StringView subject;
  697. bool matches { true };
  698. ECMAScriptFlags options {};
  699. };
  700. constexpr _test tests[] {
  701. { "[\\w--x]"sv, "x"sv, false },
  702. { "[\\w&&x]"sv, "y"sv, false },
  703. { "[\\w--x]"sv, "y"sv, true },
  704. { "[\\w&&x]"sv, "x"sv, true },
  705. { "[[0-9\\w]--x--6]"sv, "6"sv, false },
  706. { "[[0-9\\w]--x--6]"sv, "x"sv, false },
  707. { "[[0-9\\w]--x--6]"sv, "y"sv, true },
  708. { "[[0-9\\w]--x--6]"sv, "9"sv, true },
  709. { "[\\w&&\\d]"sv, "a"sv, false },
  710. { "[\\w&&\\d]"sv, "4"sv, true },
  711. };
  712. for (auto& test : tests) {
  713. Regex<ECMA262> re(test.pattern, (ECMAScriptFlags)regex::AllFlags::UnicodeSets | test.options);
  714. if constexpr (REGEX_DEBUG) {
  715. dbgln("\n");
  716. RegexDebug regex_dbg(stderr);
  717. regex_dbg.print_raw_bytecode(re);
  718. regex_dbg.print_header();
  719. regex_dbg.print_bytecode(re);
  720. dbgln("\n");
  721. }
  722. EXPECT_EQ(re.parser_result.error, regex::Error::NoError);
  723. auto result = re.match(test.subject).success;
  724. EXPECT_EQ(result, test.matches);
  725. }
  726. }
  727. TEST_CASE(ECMA262_property_match)
  728. {
  729. struct _test {
  730. StringView pattern;
  731. StringView subject;
  732. bool matches { true };
  733. ECMAScriptFlags options {};
  734. };
  735. constexpr _test tests[] {
  736. { "\\p{ASCII}"sv, "a"sv, false },
  737. { "\\p{ASCII}"sv, "p{ASCII}"sv, true },
  738. { "\\p{ASCII}"sv, "a"sv, true, ECMAScriptFlags::Unicode },
  739. { "\\p{ASCII}"sv, "😀"sv, false, ECMAScriptFlags::Unicode },
  740. { "\\P{ASCII}"sv, "a"sv, false, ECMAScriptFlags::Unicode },
  741. { "\\P{ASCII}"sv, "😀"sv, true, ECMAScriptFlags::Unicode },
  742. { "\\p{ASCII_Hex_Digit}"sv, "1"sv, true, ECMAScriptFlags::Unicode },
  743. { "\\p{ASCII_Hex_Digit}"sv, "a"sv, true, ECMAScriptFlags::Unicode },
  744. { "\\p{ASCII_Hex_Digit}"sv, "x"sv, false, ECMAScriptFlags::Unicode },
  745. { "\\P{ASCII_Hex_Digit}"sv, "1"sv, false, ECMAScriptFlags::Unicode },
  746. { "\\P{ASCII_Hex_Digit}"sv, "a"sv, false, ECMAScriptFlags::Unicode },
  747. { "\\P{ASCII_Hex_Digit}"sv, "x"sv, true, ECMAScriptFlags::Unicode },
  748. { "\\p{Any}"sv, "\xcd\xb8"sv, true, ECMAScriptFlags::Unicode }, // U+0378, which is an unassigned code point.
  749. { "\\P{Any}"sv, "\xcd\xb8"sv, false, ECMAScriptFlags::Unicode }, // U+0378, which is an unassigned code point.
  750. { "\\p{Assigned}"sv, "\xcd\xb8"sv, false, ECMAScriptFlags::Unicode }, // U+0378, which is an unassigned code point.
  751. { "\\P{Assigned}"sv, "\xcd\xb8"sv, true, ECMAScriptFlags::Unicode }, // U+0378, which is an unassigned code point.
  752. { "\\p{Lu}"sv, "a"sv, false, ECMAScriptFlags::Unicode },
  753. { "\\p{Lu}"sv, "A"sv, true, ECMAScriptFlags::Unicode },
  754. { "\\p{Lu}"sv, "9"sv, false, ECMAScriptFlags::Unicode },
  755. { "\\p{Cased_Letter}"sv, "a"sv, true, ECMAScriptFlags::Unicode },
  756. { "\\p{Cased_Letter}"sv, "A"sv, true, ECMAScriptFlags::Unicode },
  757. { "\\p{Cased_Letter}"sv, "9"sv, false, ECMAScriptFlags::Unicode },
  758. { "\\P{Cased_Letter}"sv, "a"sv, false, ECMAScriptFlags::Unicode },
  759. { "\\P{Cased_Letter}"sv, "A"sv, false, ECMAScriptFlags::Unicode },
  760. { "\\P{Cased_Letter}"sv, "9"sv, true, ECMAScriptFlags::Unicode },
  761. { "\\p{General_Category=Cased_Letter}"sv, "a"sv, true, ECMAScriptFlags::Unicode },
  762. { "\\p{General_Category=Cased_Letter}"sv, "A"sv, true, ECMAScriptFlags::Unicode },
  763. { "\\p{General_Category=Cased_Letter}"sv, "9"sv, false, ECMAScriptFlags::Unicode },
  764. { "\\p{gc=Cased_Letter}"sv, "a"sv, true, ECMAScriptFlags::Unicode },
  765. { "\\p{gc=Cased_Letter}"sv, "A"sv, true, ECMAScriptFlags::Unicode },
  766. { "\\p{gc=Cased_Letter}"sv, "9"sv, false, ECMAScriptFlags::Unicode },
  767. { "\\p{Script=Latin}"sv, "a"sv, true, ECMAScriptFlags::Unicode },
  768. { "\\p{Script=Latin}"sv, "A"sv, true, ECMAScriptFlags::Unicode },
  769. { "\\p{Script=Latin}"sv, "9"sv, false, ECMAScriptFlags::Unicode },
  770. { "\\p{sc=Latin}"sv, "a"sv, true, ECMAScriptFlags::Unicode },
  771. { "\\p{sc=Latin}"sv, "A"sv, true, ECMAScriptFlags::Unicode },
  772. { "\\p{sc=Latin}"sv, "9"sv, false, ECMAScriptFlags::Unicode },
  773. { "\\p{Script_Extensions=Deva}"sv, "a"sv, false, ECMAScriptFlags::Unicode },
  774. { "\\p{Script_Extensions=Beng}"sv, "\xe1\xb3\x95"sv, true, ECMAScriptFlags::Unicode }, // U+01CD5
  775. { "\\p{Script_Extensions=Deva}"sv, "\xe1\xb3\x95"sv, true, ECMAScriptFlags::Unicode }, // U+01CD5
  776. { "\\p{scx=Deva}"sv, "a"sv, false, ECMAScriptFlags::Unicode },
  777. { "\\p{scx=Beng}"sv, "\xe1\xb3\x95"sv, true, ECMAScriptFlags::Unicode }, // U+01CD5
  778. { "\\p{scx=Deva}"sv, "\xe1\xb3\x95"sv, true, ECMAScriptFlags::Unicode }, // U+01CD5
  779. };
  780. for (auto& test : tests) {
  781. Regex<ECMA262> re(test.pattern, (ECMAScriptFlags)regex::AllFlags::Global | regex::ECMAScriptFlags::BrowserExtended | test.options);
  782. auto subject = MUST(AK::utf8_to_utf16(test.subject));
  783. Utf16View view { subject };
  784. if constexpr (REGEX_DEBUG) {
  785. dbgln("\n");
  786. RegexDebug regex_dbg(stderr);
  787. regex_dbg.print_raw_bytecode(re);
  788. regex_dbg.print_header();
  789. regex_dbg.print_bytecode(re);
  790. dbgln("\n");
  791. }
  792. EXPECT_EQ(re.parser_result.error, regex::Error::NoError);
  793. EXPECT_EQ(re.match(view).success, test.matches);
  794. }
  795. }
  796. TEST_CASE(replace)
  797. {
  798. struct _test {
  799. StringView pattern;
  800. StringView replacement;
  801. StringView subject;
  802. StringView expected;
  803. ECMAScriptFlags options {};
  804. };
  805. constexpr _test tests[] {
  806. { "foo(.+)"sv, "aaa"sv, "test"sv, "test"sv },
  807. { "foo(.+)"sv, "test\\1"sv, "foobar"sv, "testbar"sv },
  808. { "foo(.+)"sv, "\\2\\1"sv, "foobar"sv, "\\2bar"sv },
  809. { "foo(.+)"sv, "\\\\\\1"sv, "foobar"sv, "\\bar"sv },
  810. { "foo(.)"sv, "a\\1"sv, "fooxfooy"sv, "axay"sv, ECMAScriptFlags::Multiline },
  811. };
  812. for (auto& test : tests) {
  813. Regex<ECMA262> re(test.pattern, test.options);
  814. if constexpr (REGEX_DEBUG) {
  815. dbgln("\n");
  816. RegexDebug regex_dbg(stderr);
  817. regex_dbg.print_raw_bytecode(re);
  818. regex_dbg.print_header();
  819. regex_dbg.print_bytecode(re);
  820. dbgln("\n");
  821. }
  822. EXPECT_EQ(re.parser_result.error, regex::Error::NoError);
  823. EXPECT_EQ(re.replace(test.subject, test.replacement), test.expected);
  824. }
  825. }
  826. TEST_CASE(case_insensitive_match)
  827. {
  828. Regex<PosixExtended> re("cd", PosixFlags::Insensitive | PosixFlags::Global);
  829. auto result = re.match("AEKFCD"sv);
  830. EXPECT_EQ(result.success, true);
  831. if (result.success) {
  832. EXPECT_EQ(result.matches.at(0).column, 4ul);
  833. }
  834. }
  835. TEST_CASE(extremely_long_fork_chain)
  836. {
  837. Regex<ECMA262> re("(?:aa)*");
  838. auto result = re.match(DeprecatedString::repeated('a', 1000));
  839. EXPECT_EQ(result.success, true);
  840. }
  841. TEST_CASE(theoretically_infinite_loop)
  842. {
  843. Array patterns {
  844. "(a*)*"sv, // Infinitely matching empty substrings, the outer loop should short-circuit.
  845. "(a*?)*"sv, // Infinitely matching empty substrings, the outer loop should short-circuit.
  846. "(a*)*?"sv, // Should match exactly nothing.
  847. "(?:)*?"sv, // Should not generate an infinite fork loop.
  848. };
  849. for (auto& pattern : patterns) {
  850. Regex<ECMA262> re(pattern);
  851. auto result = re.match(""sv);
  852. EXPECT_EQ(result.success, true);
  853. }
  854. }
  855. static auto g_lots_of_a_s = DeprecatedString::repeated('a', 10'000'000);
  856. BENCHMARK_CASE(fork_performance)
  857. {
  858. Regex<ECMA262> re("(?:aa)*");
  859. auto result = re.match(g_lots_of_a_s);
  860. EXPECT_EQ(result.success, true);
  861. }
  862. TEST_CASE(optimizer_atomic_groups)
  863. {
  864. Array tests {
  865. // Fork -> ForkReplace
  866. Tuple { "a*b"sv, "aaaaa"sv, false },
  867. Tuple { "a+b"sv, "aaaaa"sv, false },
  868. Tuple { "\\\\(\\d+)"sv, "\\\\"sv, false }, // Rewrite bug turning a+ to a*, see #10952.
  869. Tuple { "[a-z.]+\\."sv, "..."sv, true }, // Rewrite bug, incorrect interpretation of Compare.
  870. Tuple { "[.-]+\\."sv, ".-."sv, true },
  871. // Alternative fuse
  872. Tuple { "(abcfoo|abcbar|abcbaz).*x"sv, "abcbarx"sv, true },
  873. Tuple { "(a|a)"sv, "a"sv, true },
  874. Tuple { "(a|)"sv, ""sv, true }, // Ensure that empty alternatives are not outright removed
  875. Tuple { "a{2,3}|a{5,8}"sv, "abc"sv, false }, // Optimizer should not mess up the instruction stream by ignoring inter-insn dependencies, see #11247.
  876. Tuple { "^(a{2,3}|a{5,8})$"sv, "aaaa"sv, false }, // Optimizer should not mess up the instruction stream by ignoring inter-insn dependencies, see #11247.
  877. // Optimizer should not chop off *half* of an instruction when fusing instructions.
  878. Tuple { "cubic-bezier\\(\\s*(-?\\d+\\.?\\d*|-?\\.\\d+)\\s*,\\s*(-?\\d+\\.?\\d*|-?\\.\\d+)\\s*,\\s*(-?\\d+\\.?\\d*|-?\\.\\d+)\\s*,\\s*(-?\\d+\\.?\\d*|-?\\.\\d+)\\s*\\)"sv, "cubic-bezier(.05, 0, 0, 1)"sv, true },
  879. // ForkReplace shouldn't be applied where it would change the semantics
  880. Tuple { "(1+)\\1"sv, "11"sv, true },
  881. Tuple { "(1+)1"sv, "11"sv, true },
  882. Tuple { "(1+)0"sv, "10"sv, true },
  883. // Rewrite should not skip over first required iteration of <x>+.
  884. Tuple { "a+"sv, ""sv, false },
  885. // 'y' and [^x] have an overlap ('y'), the loop should not be rewritten here.
  886. Tuple { "[^x]+y"sv, "ay"sv, true },
  887. // .+ should not be rewritten here, as it's followed by something that would be matched by `.`.
  888. Tuple { ".+(a|b|c)"sv, "xxa"sv, true },
  889. };
  890. for (auto& test : tests) {
  891. Regex<ECMA262> re(test.get<0>());
  892. auto result = re.match(test.get<1>());
  893. EXPECT_EQ(result.success, test.get<2>());
  894. }
  895. }
  896. TEST_CASE(optimizer_char_class_lut)
  897. {
  898. Regex<ECMA262> re(R"([\f\n\r\t\v\u00a0\u1680\u2000\u2001\u2002\u2003\u2004\u2005\u2006\u2007\u2008\u2009\u200a\u2028\u2029\u202f\u205f\u3000\ufeff]+$)");
  899. if constexpr (REGEX_DEBUG) {
  900. dbgln("\n");
  901. RegexDebug regex_dbg(stderr);
  902. regex_dbg.print_raw_bytecode(re);
  903. regex_dbg.print_header();
  904. regex_dbg.print_bytecode(re);
  905. dbgln("\n");
  906. }
  907. // This will go through _all_ alternatives in the character class, and then fail.
  908. for (size_t i = 0; i < 1'000'000; ++i)
  909. EXPECT_EQ(re.match("1635488940000"sv).success, false);
  910. }
  911. TEST_CASE(optimizer_alternation)
  912. {
  913. Array tests {
  914. // Pattern, Subject, Expected length
  915. Tuple { "a|"sv, "a"sv, 1u },
  916. };
  917. for (auto& test : tests) {
  918. Regex<ECMA262> re(test.get<0>());
  919. auto result = re.match(test.get<1>());
  920. EXPECT(result.success);
  921. EXPECT_EQ(result.matches.first().view.length(), test.get<2>());
  922. }
  923. }
  924. TEST_CASE(posix_basic_dollar_is_end_anchor)
  925. {
  926. // Ensure that a dollar sign at the end only matches the end of the line.
  927. {
  928. Regex<PosixBasic> re("abc$");
  929. EXPECT_EQ(re.match("123abcdef"sv, PosixFlags::Global).success, false);
  930. EXPECT_EQ(re.match("123abc"sv, PosixFlags::Global).success, true);
  931. EXPECT_EQ(re.match("123abc$def"sv, PosixFlags::Global).success, false);
  932. EXPECT_EQ(re.match("123abc$"sv, PosixFlags::Global).success, false);
  933. }
  934. }
  935. TEST_CASE(posix_basic_dollar_is_literal)
  936. {
  937. // Ensure that a dollar sign in the middle is treated as a literal.
  938. {
  939. Regex<PosixBasic> re("abc$d");
  940. EXPECT_EQ(re.match("123abcdef"sv, PosixFlags::Global).success, false);
  941. EXPECT_EQ(re.match("123abc"sv, PosixFlags::Global).success, false);
  942. EXPECT_EQ(re.match("123abc$def"sv, PosixFlags::Global).success, true);
  943. EXPECT_EQ(re.match("123abc$"sv, PosixFlags::Global).success, false);
  944. }
  945. // Ensure that a dollar sign is always treated as a literal if escaped, even if at the end of the pattern.
  946. {
  947. Regex<PosixBasic> re("abc\\$");
  948. EXPECT_EQ(re.match("123abcdef"sv, PosixFlags::Global).success, false);
  949. EXPECT_EQ(re.match("123abc"sv, PosixFlags::Global).success, false);
  950. EXPECT_EQ(re.match("123abc$def"sv, PosixFlags::Global).success, true);
  951. EXPECT_EQ(re.match("123abc$"sv, PosixFlags::Global).success, true);
  952. }
  953. }
  954. TEST_CASE(negative_lookahead)
  955. {
  956. {
  957. // Negative lookahead with more than 2 forks difference between lookahead init and finish.
  958. auto options = ECMAScriptOptions { ECMAScriptFlags::Global };
  959. options.reset_flag((ECMAScriptFlags)regex::AllFlags::Internal_Stateful);
  960. Regex<ECMA262> re(":(?!\\^\\)|1)", options);
  961. EXPECT_EQ(re.match(":^)"sv).success, false);
  962. EXPECT_EQ(re.match(":1"sv).success, false);
  963. EXPECT_EQ(re.match(":foobar"sv).success, true);
  964. }
  965. {
  966. // Correctly count forks with nested groups and optimised loops
  967. Regex<ECMA262> re("^((?:[^\\n]|\\n(?! *\\n))+)(?:\\n *)+\\n");
  968. EXPECT_EQ(re.match("foo\n\n"sv).success, true);
  969. EXPECT_EQ(re.match("foo\n"sv).success, false);
  970. }
  971. }
  972. TEST_CASE(single_match_flag)
  973. {
  974. {
  975. // Ensure that only a single match is produced and nothing past that.
  976. Regex<ECMA262> re("[\\u0008-\\uffff]"sv, ECMAScriptFlags::Global | (ECMAScriptFlags)regex::AllFlags::SingleMatch);
  977. auto result = re.match("ABC"sv);
  978. EXPECT_EQ(result.success, true);
  979. EXPECT_EQ(result.matches.size(), 1u);
  980. EXPECT_EQ(result.matches.first().view.to_deprecated_string(), "A"sv);
  981. }
  982. }
  983. TEST_CASE(empty_string_wildcard_match)
  984. {
  985. {
  986. // Ensure that the wildcard ".*" matches the empty string exactly once
  987. Regex<ECMA262> re(".*"sv, ECMAScriptFlags::Global);
  988. auto result = re.match(""sv);
  989. EXPECT_EQ(result.success, true);
  990. EXPECT_EQ(result.matches.size(), 1u);
  991. EXPECT_EQ(result.matches.first().view.to_deprecated_string(), ""sv);
  992. }
  993. }
  994. TEST_CASE(inversion_state_in_char_class)
  995. {
  996. {
  997. // #13755, /[\S\s]/.exec("hello") should be [ "h" ], not null.
  998. Regex<ECMA262> re("[\\S\\s]", ECMAScriptFlags::Global | (ECMAScriptFlags)regex::AllFlags::SingleMatch);
  999. auto result = re.match("hello"sv);
  1000. EXPECT_EQ(result.success, true);
  1001. EXPECT_EQ(result.matches.size(), 1u);
  1002. EXPECT_EQ(result.matches.first().view.to_deprecated_string(), "h"sv);
  1003. }
  1004. {
  1005. Regex<ECMA262> re("^(?:([^\\s!\"#%-,\\./;->@\\[-\\^`\\{-~]+(?=([=~}\\s/.)|]))))"sv, ECMAScriptFlags::Global);
  1006. auto result = re.match("slideNumbers}}"sv);
  1007. EXPECT_EQ(result.success, true);
  1008. EXPECT_EQ(result.matches.size(), 1u);
  1009. EXPECT_EQ(result.matches.first().view.to_deprecated_string(), "slideNumbers"sv);
  1010. EXPECT_EQ(result.capture_group_matches.first()[0].view.to_deprecated_string(), "slideNumbers"sv);
  1011. EXPECT_EQ(result.capture_group_matches.first()[1].view.to_deprecated_string(), "}"sv);
  1012. }
  1013. }