RegexParser.cpp 84 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711171217131714171517161717171817191720172117221723172417251726172717281729173017311732173317341735173617371738173917401741174217431744174517461747174817491750175117521753175417551756175717581759176017611762176317641765176617671768176917701771177217731774177517761777177817791780178117821783178417851786178717881789179017911792179317941795179617971798179918001801180218031804180518061807180818091810181118121813181418151816181718181819182018211822182318241825182618271828182918301831183218331834183518361837183818391840184118421843184418451846184718481849185018511852185318541855185618571858185918601861186218631864186518661867186818691870187118721873187418751876187718781879188018811882188318841885188618871888188918901891189218931894189518961897189818991900190119021903190419051906190719081909191019111912191319141915191619171918191919201921192219231924192519261927192819291930193119321933193419351936193719381939194019411942194319441945194619471948194919501951195219531954195519561957195819591960196119621963196419651966196719681969197019711972197319741975197619771978197919801981198219831984198519861987198819891990199119921993199419951996199719981999200020012002200320042005200620072008200920102011201220132014201520162017201820192020202120222023202420252026202720282029203020312032203320342035203620372038203920402041204220432044204520462047204820492050205120522053205420552056205720582059206020612062206320642065206620672068206920702071207220732074207520762077207820792080208120822083208420852086208720882089209020912092209320942095209620972098209921002101210221032104210521062107210821092110211121122113211421152116211721182119212021212122212321242125212621272128212921302131213221332134213521362137213821392140214121422143214421452146214721482149215021512152215321542155215621572158215921602161216221632164216521662167216821692170217121722173217421752176217721782179218021812182218321842185218621872188218921902191219221932194219521962197219821992200220122022203220422052206220722082209221022112212221322142215221622172218221922202221222222232224222522262227222822292230223122322233223422352236223722382239224022412242224322442245224622472248224922502251225222532254225522562257225822592260226122622263226422652266226722682269227022712272227322742275227622772278227922802281228222832284228522862287228822892290229122922293229422952296229722982299230023012302230323042305230623072308230923102311231223132314231523162317231823192320232123222323232423252326232723282329233023312332233323342335233623372338233923402341234223432344234523462347234823492350235123522353235423552356
  1. /*
  2. * Copyright (c) 2020, Emanuel Sprung <emanuel.sprung@gmail.com>
  3. * Copyright (c) 2020-2021, the SerenityOS developers.
  4. *
  5. * SPDX-License-Identifier: BSD-2-Clause
  6. */
  7. #include "RegexParser.h"
  8. #include "RegexDebug.h"
  9. #include <AK/AnyOf.h>
  10. #include <AK/CharacterTypes.h>
  11. #include <AK/GenericLexer.h>
  12. #include <AK/ScopeGuard.h>
  13. #include <AK/String.h>
  14. #include <AK/StringBuilder.h>
  15. #include <AK/StringUtils.h>
  16. #include <AK/TemporaryChange.h>
  17. #include <AK/Utf16View.h>
  18. #include <LibUnicode/CharacterTypes.h>
  19. namespace regex {
  20. static constexpr size_t s_maximum_repetition_count = 1024 * 1024;
  21. static constexpr u64 s_ecma262_maximum_repetition_count = (1ull << 53) - 1;
  22. static constexpr auto s_alphabetic_characters = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"sv;
  23. static constexpr auto s_decimal_characters = "0123456789"sv;
  24. static constexpr StringView identity_escape_characters(bool unicode, bool browser_extended)
  25. {
  26. if (unicode)
  27. return "^$\\.*+?()[]{}|/"sv;
  28. if (browser_extended)
  29. return "^$\\.*+?()[|"sv;
  30. return "^$\\.*+?()[]{}|"sv;
  31. }
  32. ALWAYS_INLINE bool Parser::set_error(Error error)
  33. {
  34. if (m_parser_state.error == Error::NoError) {
  35. m_parser_state.error = error;
  36. m_parser_state.error_token = m_parser_state.current_token;
  37. }
  38. return false; // always return false, that eases the API usage (return set_error(...)) :^)
  39. }
  40. ALWAYS_INLINE bool Parser::done() const
  41. {
  42. return match(TokenType::Eof);
  43. }
  44. ALWAYS_INLINE bool Parser::match(TokenType type) const
  45. {
  46. return m_parser_state.current_token.type() == type;
  47. }
  48. ALWAYS_INLINE bool Parser::match(char ch) const
  49. {
  50. return m_parser_state.current_token.type() == TokenType::Char && m_parser_state.current_token.value().length() == 1 && m_parser_state.current_token.value()[0] == ch;
  51. }
  52. ALWAYS_INLINE Token Parser::consume()
  53. {
  54. auto old_token = m_parser_state.current_token;
  55. m_parser_state.current_token = m_parser_state.lexer.next();
  56. return old_token;
  57. }
  58. ALWAYS_INLINE Token Parser::consume(TokenType type, Error error)
  59. {
  60. if (m_parser_state.current_token.type() != type) {
  61. set_error(error);
  62. dbgln_if(REGEX_DEBUG, "[PARSER] Error: Unexpected token {}. Expected: {}", m_parser_state.current_token.name(), Token::name(type));
  63. }
  64. return consume();
  65. }
  66. ALWAYS_INLINE bool Parser::consume(String const& str)
  67. {
  68. size_t potentially_go_back { 1 };
  69. for (auto ch : str) {
  70. if (match(TokenType::Char)) {
  71. if (m_parser_state.current_token.value()[0] != ch) {
  72. m_parser_state.lexer.back(potentially_go_back);
  73. m_parser_state.current_token = m_parser_state.lexer.next();
  74. return false;
  75. }
  76. } else {
  77. m_parser_state.lexer.back(potentially_go_back);
  78. m_parser_state.current_token = m_parser_state.lexer.next();
  79. return false;
  80. }
  81. consume(TokenType::Char, Error::NoError);
  82. ++potentially_go_back;
  83. }
  84. return true;
  85. }
  86. ALWAYS_INLINE Optional<u32> Parser::consume_escaped_code_point(bool unicode)
  87. {
  88. if (match(TokenType::LeftCurly) && !unicode) {
  89. // In non-Unicode mode, this should be parsed as a repetition symbol (repeating the 'u').
  90. return static_cast<u32>('u');
  91. }
  92. m_parser_state.lexer.retreat(2 + !done()); // Go back to just before '\u' (+1 char, because we will have consumed an extra character)
  93. if (auto code_point_or_error = m_parser_state.lexer.consume_escaped_code_point(unicode); !code_point_or_error.is_error()) {
  94. m_parser_state.current_token = m_parser_state.lexer.next();
  95. return code_point_or_error.value();
  96. }
  97. if (!unicode) {
  98. // '\u' is allowed in non-unicode mode, just matches 'u'.
  99. return static_cast<u32>('u');
  100. }
  101. set_error(Error::InvalidPattern);
  102. return {};
  103. }
  104. ALWAYS_INLINE bool Parser::try_skip(StringView str)
  105. {
  106. if (str.starts_with(m_parser_state.current_token.value()))
  107. str = str.substring_view(m_parser_state.current_token.value().length(), str.length() - m_parser_state.current_token.value().length());
  108. else
  109. return false;
  110. size_t potentially_go_back { 0 };
  111. for (auto ch : str) {
  112. if (!m_parser_state.lexer.consume_specific(ch)) {
  113. m_parser_state.lexer.back(potentially_go_back);
  114. return false;
  115. }
  116. ++potentially_go_back;
  117. }
  118. m_parser_state.current_token = m_parser_state.lexer.next();
  119. return true;
  120. }
  121. ALWAYS_INLINE bool Parser::lookahead_any(StringView str)
  122. {
  123. return AK::any_of(str, [this](auto ch) { return match(ch); });
  124. }
  125. ALWAYS_INLINE unsigned char Parser::skip()
  126. {
  127. unsigned char ch;
  128. if (m_parser_state.current_token.value().length() == 1) {
  129. ch = m_parser_state.current_token.value()[0];
  130. } else {
  131. m_parser_state.lexer.back(m_parser_state.current_token.value().length());
  132. ch = m_parser_state.lexer.consume();
  133. }
  134. m_parser_state.current_token = m_parser_state.lexer.next();
  135. return ch;
  136. }
  137. ALWAYS_INLINE void Parser::back(size_t count)
  138. {
  139. m_parser_state.lexer.back(count);
  140. m_parser_state.current_token = m_parser_state.lexer.next();
  141. }
  142. ALWAYS_INLINE void Parser::reset()
  143. {
  144. m_parser_state.bytecode.clear();
  145. m_parser_state.lexer.reset();
  146. m_parser_state.current_token = m_parser_state.lexer.next();
  147. m_parser_state.error = Error::NoError;
  148. m_parser_state.error_token = { TokenType::Eof, 0, StringView(nullptr) };
  149. m_parser_state.capture_group_minimum_lengths.clear();
  150. m_parser_state.capture_groups_count = 0;
  151. m_parser_state.named_capture_groups_count = 0;
  152. m_parser_state.named_capture_groups.clear();
  153. }
  154. Parser::Result Parser::parse(Optional<AllOptions> regex_options)
  155. {
  156. reset();
  157. if (regex_options.has_value())
  158. m_parser_state.regex_options = regex_options.value();
  159. if (parse_internal(m_parser_state.bytecode, m_parser_state.match_length_minimum))
  160. consume(TokenType::Eof, Error::InvalidPattern);
  161. else
  162. set_error(Error::InvalidPattern);
  163. dbgln_if(REGEX_DEBUG, "[PARSER] Produced bytecode with {} entries (opcodes + arguments)", m_parser_state.bytecode.size());
  164. return {
  165. move(m_parser_state.bytecode),
  166. move(m_parser_state.capture_groups_count),
  167. move(m_parser_state.named_capture_groups_count),
  168. move(m_parser_state.match_length_minimum),
  169. move(m_parser_state.error),
  170. move(m_parser_state.error_token),
  171. m_parser_state.named_capture_groups.keys()
  172. };
  173. }
  174. ALWAYS_INLINE bool Parser::match_ordinary_characters()
  175. {
  176. // NOTE: This method must not be called during bracket and repetition parsing!
  177. // FIXME: Add assertion for that?
  178. auto type = m_parser_state.current_token.type();
  179. return (type == TokenType::Char
  180. || type == TokenType::Comma
  181. || type == TokenType::Slash
  182. || type == TokenType::EqualSign
  183. || type == TokenType::HyphenMinus
  184. || type == TokenType::Colon);
  185. }
  186. // =============================
  187. // Abstract Posix Parser
  188. // =============================
  189. ALWAYS_INLINE bool AbstractPosixParser::parse_bracket_expression(Vector<CompareTypeAndValuePair>& values, size_t& match_length_minimum)
  190. {
  191. for (; !done();) {
  192. if (match(TokenType::HyphenMinus)) {
  193. consume();
  194. if (values.is_empty() || (values.size() == 1 && values.last().type == CharacterCompareType::Inverse)) {
  195. // first in the bracket expression
  196. values.append({ CharacterCompareType::Char, (ByteCodeValueType)'-' });
  197. } else if (match(TokenType::RightBracket)) {
  198. // Last in the bracket expression
  199. values.append({ CharacterCompareType::Char, (ByteCodeValueType)'-' });
  200. } else if (values.last().type == CharacterCompareType::Char) {
  201. values.append({ CharacterCompareType::RangeExpressionDummy, 0 });
  202. if (done())
  203. return set_error(Error::MismatchingBracket);
  204. if (match(TokenType::HyphenMinus)) {
  205. consume();
  206. // Valid range, add ordinary character
  207. values.append({ CharacterCompareType::Char, (ByteCodeValueType)'-' });
  208. }
  209. } else {
  210. return set_error(Error::InvalidRange);
  211. }
  212. } else if (match(TokenType::Circumflex)) {
  213. auto t = consume();
  214. if (values.is_empty())
  215. values.append({ CharacterCompareType::Inverse, 0 });
  216. else
  217. values.append({ CharacterCompareType::Char, (ByteCodeValueType)*t.value().characters_without_null_termination() });
  218. } else if (match(TokenType::LeftBracket)) {
  219. consume();
  220. if (match(TokenType::Period)) {
  221. consume();
  222. // FIXME: Parse collating element, this is needed when we have locale support
  223. // This could have impact on length parameter, I guess.
  224. set_error(Error::InvalidCollationElement);
  225. consume(TokenType::Period, Error::InvalidCollationElement);
  226. consume(TokenType::RightBracket, Error::MismatchingBracket);
  227. } else if (match(TokenType::EqualSign)) {
  228. consume();
  229. // FIXME: Parse collating element, this is needed when we have locale support
  230. // This could have impact on length parameter, I guess.
  231. set_error(Error::InvalidCollationElement);
  232. consume(TokenType::EqualSign, Error::InvalidCollationElement);
  233. consume(TokenType::RightBracket, Error::MismatchingBracket);
  234. } else if (match(TokenType::Colon)) {
  235. consume();
  236. CharClass ch_class;
  237. // parse character class
  238. if (match(TokenType::Char)) {
  239. if (consume("alnum"))
  240. ch_class = CharClass::Alnum;
  241. else if (consume("alpha"))
  242. ch_class = CharClass::Alpha;
  243. else if (consume("blank"))
  244. ch_class = CharClass::Blank;
  245. else if (consume("cntrl"))
  246. ch_class = CharClass::Cntrl;
  247. else if (consume("digit"))
  248. ch_class = CharClass::Digit;
  249. else if (consume("graph"))
  250. ch_class = CharClass::Graph;
  251. else if (consume("lower"))
  252. ch_class = CharClass::Lower;
  253. else if (consume("print"))
  254. ch_class = CharClass::Print;
  255. else if (consume("punct"))
  256. ch_class = CharClass::Punct;
  257. else if (consume("space"))
  258. ch_class = CharClass::Space;
  259. else if (consume("upper"))
  260. ch_class = CharClass::Upper;
  261. else if (consume("xdigit"))
  262. ch_class = CharClass::Xdigit;
  263. else
  264. return set_error(Error::InvalidCharacterClass);
  265. values.append({ CharacterCompareType::CharClass, (ByteCodeValueType)ch_class });
  266. } else
  267. return set_error(Error::InvalidCharacterClass);
  268. // FIXME: we do not support locale specific character classes until locales are implemented
  269. consume(TokenType::Colon, Error::InvalidCharacterClass);
  270. consume(TokenType::RightBracket, Error::MismatchingBracket);
  271. } else {
  272. return set_error(Error::MismatchingBracket);
  273. }
  274. } else if (match(TokenType::RightBracket)) {
  275. if (values.is_empty() || (values.size() == 1 && values.last().type == CharacterCompareType::Inverse)) {
  276. // handle bracket as ordinary character
  277. values.append({ CharacterCompareType::Char, (ByteCodeValueType)*consume().value().characters_without_null_termination() });
  278. } else {
  279. // closing bracket expression
  280. break;
  281. }
  282. } else {
  283. values.append({ CharacterCompareType::Char, (ByteCodeValueType)skip() });
  284. }
  285. // check if range expression has to be completed...
  286. if (values.size() >= 3 && values.at(values.size() - 2).type == CharacterCompareType::RangeExpressionDummy) {
  287. if (values.last().type != CharacterCompareType::Char)
  288. return set_error(Error::InvalidRange);
  289. auto value2 = values.take_last();
  290. values.take_last(); // RangeExpressionDummy
  291. auto value1 = values.take_last();
  292. values.append({ CharacterCompareType::CharRange, static_cast<ByteCodeValueType>(CharRange { (u32)value1.value, (u32)value2.value }) });
  293. }
  294. }
  295. if (!values.is_empty()) {
  296. match_length_minimum = 1;
  297. if (values.first().type == CharacterCompareType::Inverse)
  298. match_length_minimum = 0;
  299. }
  300. return true;
  301. }
  302. // =============================
  303. // PosixBasic Parser
  304. // =============================
  305. bool PosixBasicParser::parse_internal(ByteCode& stack, size_t& match_length_minimum)
  306. {
  307. return parse_root(stack, match_length_minimum);
  308. }
  309. bool PosixBasicParser::parse_root(ByteCode& bytecode, size_t& match_length_minimum)
  310. {
  311. // basic_reg_exp : L_ANCHOR? RE_expression R_ANCHOR?
  312. if (match(TokenType::Circumflex)) {
  313. consume();
  314. bytecode.empend((ByteCodeValueType)OpCodeId::CheckBegin);
  315. }
  316. if (!parse_re_expression(bytecode, match_length_minimum))
  317. return false;
  318. if (match(TokenType::Dollar)) {
  319. consume();
  320. bytecode.empend((ByteCodeValueType)OpCodeId::CheckEnd);
  321. }
  322. return !has_error();
  323. }
  324. bool PosixBasicParser::parse_re_expression(ByteCode& bytecode, size_t& match_length_minimum)
  325. {
  326. // RE_expression : RE_expression? simple_RE
  327. while (!done()) {
  328. if (!parse_simple_re(bytecode, match_length_minimum))
  329. break;
  330. }
  331. return !has_error();
  332. }
  333. bool PosixBasicParser::parse_simple_re(ByteCode& bytecode, size_t& match_length_minimum)
  334. {
  335. // simple_RE : nondupl_RE RE_dupl_symbol?
  336. ByteCode simple_re_bytecode;
  337. size_t re_match_length_minimum = 0;
  338. if (!parse_nonduplicating_re(simple_re_bytecode, re_match_length_minimum))
  339. return false;
  340. // RE_dupl_symbol : '*' | Back_open_brace DUP_COUNT (',' DUP_COUNT?)? Back_close_brace
  341. if (match(TokenType::Asterisk)) {
  342. consume();
  343. ByteCode::transform_bytecode_repetition_any(simple_re_bytecode, true);
  344. } else if (try_skip("\\{")) {
  345. auto read_number = [&]() -> Optional<size_t> {
  346. if (!match(TokenType::Char))
  347. return {};
  348. size_t value = 0;
  349. while (match(TokenType::Char)) {
  350. auto c = m_parser_state.current_token.value().substring_view(0, 1);
  351. auto c_value = c.to_uint();
  352. if (!c_value.has_value())
  353. break;
  354. value *= 10;
  355. value += *c_value;
  356. consume();
  357. }
  358. return value;
  359. };
  360. size_t min_limit;
  361. Optional<size_t> max_limit;
  362. if (auto limit = read_number(); !limit.has_value())
  363. return set_error(Error::InvalidRepetitionMarker);
  364. else
  365. min_limit = *limit;
  366. if (match(TokenType::Comma)) {
  367. consume();
  368. max_limit = read_number();
  369. }
  370. if (!try_skip("\\}"))
  371. return set_error(Error::MismatchingBrace);
  372. if (max_limit.value_or(min_limit) < min_limit)
  373. return set_error(Error::InvalidBraceContent);
  374. if (min_limit > s_maximum_repetition_count || (max_limit.has_value() && *max_limit > s_maximum_repetition_count))
  375. return set_error(Error::InvalidBraceContent);
  376. auto min_repetition_mark_id = m_parser_state.repetition_mark_count++;
  377. auto max_repetition_mark_id = m_parser_state.repetition_mark_count++;
  378. ByteCode::transform_bytecode_repetition_min_max(simple_re_bytecode, min_limit, max_limit, min_repetition_mark_id, max_repetition_mark_id, true);
  379. match_length_minimum += re_match_length_minimum * min_limit;
  380. } else {
  381. match_length_minimum += re_match_length_minimum;
  382. }
  383. bytecode.extend(move(simple_re_bytecode));
  384. return true;
  385. }
  386. bool PosixBasicParser::parse_nonduplicating_re(ByteCode& bytecode, size_t& match_length_minimum)
  387. {
  388. // nondupl_RE : one_char_or_coll_elem_RE | Back_open_paren RE_expression Back_close_paren | BACKREF
  389. if (try_skip("\\(")) {
  390. TemporaryChange change { m_current_capture_group_depth, m_current_capture_group_depth + 1 };
  391. // Max number of addressable capture groups is 10, let's just be lenient
  392. // and accept 20; anything past that is probably a silly pattern anyway.
  393. if (m_current_capture_group_depth > 20)
  394. return set_error(Error::InvalidPattern);
  395. ByteCode capture_bytecode;
  396. size_t capture_length_minimum = 0;
  397. auto capture_group_index = ++m_parser_state.capture_groups_count;
  398. if (!parse_re_expression(capture_bytecode, capture_length_minimum))
  399. return false;
  400. if (!try_skip("\\)"))
  401. return set_error(Error::MismatchingParen);
  402. match_length_minimum += capture_length_minimum;
  403. if (capture_group_index <= number_of_addressable_capture_groups) {
  404. m_capture_group_minimum_lengths[capture_group_index - 1] = capture_length_minimum;
  405. m_capture_group_seen[capture_group_index - 1] = true;
  406. bytecode.insert_bytecode_group_capture_left(capture_group_index);
  407. }
  408. bytecode.extend(capture_bytecode);
  409. if (capture_group_index <= number_of_addressable_capture_groups)
  410. bytecode.insert_bytecode_group_capture_right(capture_group_index);
  411. return true;
  412. }
  413. for (size_t i = 1; i < 10; ++i) {
  414. char backref_name[2] { '\\', '0' };
  415. backref_name[1] += i;
  416. if (try_skip({ backref_name, 2 })) {
  417. if (!m_capture_group_seen[i - 1])
  418. return set_error(Error::InvalidNumber);
  419. match_length_minimum += m_capture_group_minimum_lengths[i - 1];
  420. bytecode.insert_bytecode_compare_values({ { CharacterCompareType::Reference, (ByteCodeValueType)i } });
  421. return true;
  422. }
  423. }
  424. return parse_one_char_or_collation_element(bytecode, match_length_minimum);
  425. }
  426. bool PosixBasicParser::parse_one_char_or_collation_element(ByteCode& bytecode, size_t& match_length_minimum)
  427. {
  428. // one_char_or_coll_elem_RE : ORD_CHAR | QUOTED_CHAR | '.' | bracket_expression
  429. if (match(TokenType::Period)) {
  430. consume();
  431. bytecode.insert_bytecode_compare_values({ { CharacterCompareType::AnyChar, 0 } });
  432. match_length_minimum += 1;
  433. return true;
  434. }
  435. // Dollars are special if at the end of a pattern.
  436. if (match(TokenType::Dollar)) {
  437. consume();
  438. // If we are at the end of a pattern, emit an end check instruction.
  439. if (match(TokenType::Eof)) {
  440. bytecode.empend((ByteCodeValueType)OpCodeId::CheckEnd);
  441. return true;
  442. }
  443. // We are not at the end of the string, so we should roll back and continue as normal.
  444. back(2);
  445. }
  446. // None of these are special in BRE.
  447. if (match(TokenType::Char) || match(TokenType::Questionmark) || match(TokenType::RightParen) || match(TokenType::HyphenMinus)
  448. || match(TokenType::Circumflex) || match(TokenType::RightCurly) || match(TokenType::Comma) || match(TokenType::Colon)
  449. || match(TokenType::Dollar) || match(TokenType::EqualSign) || match(TokenType::LeftCurly) || match(TokenType::LeftParen)
  450. || match(TokenType::Pipe) || match(TokenType::Slash) || match(TokenType::RightBracket) || match(TokenType::RightParen)) {
  451. auto ch = consume().value()[0];
  452. bytecode.insert_bytecode_compare_values({ { CharacterCompareType::Char, (ByteCodeValueType)ch } });
  453. match_length_minimum += 1;
  454. return true;
  455. }
  456. if (match(TokenType::EscapeSequence)) {
  457. if (m_parser_state.current_token.value().is_one_of("\\)"sv, "\\}"sv, "\\("sv, "\\{"sv))
  458. return false;
  459. auto ch = consume().value()[1];
  460. bytecode.insert_bytecode_compare_values({ { CharacterCompareType::Char, (ByteCodeValueType)ch } });
  461. match_length_minimum += 1;
  462. return true;
  463. }
  464. Vector<CompareTypeAndValuePair> values;
  465. size_t bracket_minimum_length = 0;
  466. if (match(TokenType::LeftBracket)) {
  467. consume();
  468. if (!AbstractPosixParser::parse_bracket_expression(values, bracket_minimum_length))
  469. return false;
  470. consume(TokenType::RightBracket, Error::MismatchingBracket);
  471. if (!has_error())
  472. bytecode.insert_bytecode_compare_values(move(values));
  473. match_length_minimum += bracket_minimum_length;
  474. return !has_error();
  475. }
  476. return set_error(Error::InvalidPattern);
  477. }
  478. // =============================
  479. // PosixExtended Parser
  480. // =============================
  481. bool PosixExtendedParser::parse_internal(ByteCode& stack, size_t& match_length_minimum)
  482. {
  483. return parse_root(stack, match_length_minimum);
  484. }
  485. ALWAYS_INLINE bool PosixExtendedParser::match_repetition_symbol()
  486. {
  487. auto type = m_parser_state.current_token.type();
  488. return (type == TokenType::Asterisk
  489. || type == TokenType::Plus
  490. || type == TokenType::Questionmark
  491. || type == TokenType::LeftCurly);
  492. }
  493. ALWAYS_INLINE bool PosixExtendedParser::parse_repetition_symbol(ByteCode& bytecode_to_repeat, size_t& match_length_minimum)
  494. {
  495. if (match(TokenType::LeftCurly)) {
  496. consume();
  497. StringBuilder number_builder;
  498. while (match(TokenType::Char)) {
  499. number_builder.append(consume().value());
  500. }
  501. auto maybe_minimum = number_builder.build().to_uint();
  502. if (!maybe_minimum.has_value())
  503. return set_error(Error::InvalidBraceContent);
  504. auto minimum = maybe_minimum.value();
  505. match_length_minimum *= minimum;
  506. if (minimum > s_maximum_repetition_count)
  507. return set_error(Error::InvalidBraceContent);
  508. if (match(TokenType::Comma)) {
  509. consume();
  510. } else {
  511. auto repetition_mark_id = m_parser_state.repetition_mark_count++;
  512. ByteCode bytecode;
  513. bytecode.insert_bytecode_repetition_n(bytecode_to_repeat, minimum, repetition_mark_id);
  514. bytecode_to_repeat = move(bytecode);
  515. consume(TokenType::RightCurly, Error::MismatchingBrace);
  516. return !has_error();
  517. }
  518. Optional<u32> maybe_maximum {};
  519. number_builder.clear();
  520. while (match(TokenType::Char)) {
  521. number_builder.append(consume().value());
  522. }
  523. if (!number_builder.is_empty()) {
  524. auto value = number_builder.build().to_uint();
  525. if (!value.has_value() || minimum > value.value() || *value > s_maximum_repetition_count)
  526. return set_error(Error::InvalidBraceContent);
  527. maybe_maximum = value.value();
  528. }
  529. auto min_repetition_mark_id = m_parser_state.repetition_mark_count++;
  530. auto max_repetition_mark_id = m_parser_state.repetition_mark_count++;
  531. ByteCode::transform_bytecode_repetition_min_max(bytecode_to_repeat, minimum, maybe_maximum, min_repetition_mark_id, max_repetition_mark_id);
  532. consume(TokenType::RightCurly, Error::MismatchingBrace);
  533. return !has_error();
  534. }
  535. if (match(TokenType::Plus)) {
  536. consume();
  537. bool nongreedy = match(TokenType::Questionmark);
  538. if (nongreedy)
  539. consume();
  540. // Note: don't touch match_length_minimum, it's already correct
  541. ByteCode::transform_bytecode_repetition_min_one(bytecode_to_repeat, !nongreedy);
  542. return !has_error();
  543. }
  544. if (match(TokenType::Asterisk)) {
  545. consume();
  546. match_length_minimum = 0;
  547. bool nongreedy = match(TokenType::Questionmark);
  548. if (nongreedy)
  549. consume();
  550. ByteCode::transform_bytecode_repetition_any(bytecode_to_repeat, !nongreedy);
  551. return !has_error();
  552. }
  553. if (match(TokenType::Questionmark)) {
  554. consume();
  555. match_length_minimum = 0;
  556. bool nongreedy = match(TokenType::Questionmark);
  557. if (nongreedy)
  558. consume();
  559. ByteCode::transform_bytecode_repetition_zero_or_one(bytecode_to_repeat, !nongreedy);
  560. return !has_error();
  561. }
  562. return false;
  563. }
  564. ALWAYS_INLINE bool PosixExtendedParser::parse_bracket_expression(ByteCode& stack, size_t& match_length_minimum)
  565. {
  566. Vector<CompareTypeAndValuePair> values;
  567. if (!AbstractPosixParser::parse_bracket_expression(values, match_length_minimum))
  568. return false;
  569. if (!has_error())
  570. stack.insert_bytecode_compare_values(move(values));
  571. return !has_error();
  572. }
  573. ALWAYS_INLINE bool PosixExtendedParser::parse_sub_expression(ByteCode& stack, size_t& match_length_minimum)
  574. {
  575. ByteCode bytecode;
  576. size_t length = 0;
  577. bool should_parse_repetition_symbol { false };
  578. for (;;) {
  579. if (match_ordinary_characters()) {
  580. Token start_token = m_parser_state.current_token;
  581. Token last_token = m_parser_state.current_token;
  582. for (;;) {
  583. if (!match_ordinary_characters())
  584. break;
  585. ++length;
  586. last_token = consume();
  587. }
  588. if (length > 1) {
  589. // last character is inserted into 'bytecode' for duplication symbol handling
  590. auto new_length = length - ((match_repetition_symbol() && length > 1) ? 1 : 0);
  591. stack.insert_bytecode_compare_string({ start_token.value().characters_without_null_termination(), new_length });
  592. }
  593. if ((match_repetition_symbol() && length > 1) || length == 1) // Create own compare opcode for last character before duplication symbol
  594. bytecode.insert_bytecode_compare_values({ { CharacterCompareType::Char, (ByteCodeValueType)last_token.value().characters_without_null_termination()[0] } });
  595. should_parse_repetition_symbol = true;
  596. break;
  597. }
  598. if (match_repetition_symbol())
  599. return set_error(Error::InvalidRepetitionMarker);
  600. if (match(TokenType::Period)) {
  601. length = 1;
  602. consume();
  603. bytecode.insert_bytecode_compare_values({ { CharacterCompareType::AnyChar, 0 } });
  604. should_parse_repetition_symbol = true;
  605. break;
  606. }
  607. if (match(TokenType::EscapeSequence)) {
  608. length = 1;
  609. Token t = consume();
  610. dbgln_if(REGEX_DEBUG, "[PARSER] EscapeSequence with substring {}", t.value());
  611. bytecode.insert_bytecode_compare_values({ { CharacterCompareType::Char, (u32)t.value().characters_without_null_termination()[1] } });
  612. should_parse_repetition_symbol = true;
  613. break;
  614. }
  615. if (match(TokenType::LeftBracket)) {
  616. consume();
  617. ByteCode sub_ops;
  618. if (!parse_bracket_expression(sub_ops, length) || !sub_ops.size())
  619. return set_error(Error::InvalidBracketContent);
  620. bytecode.extend(move(sub_ops));
  621. consume(TokenType::RightBracket, Error::MismatchingBracket);
  622. should_parse_repetition_symbol = true;
  623. break;
  624. }
  625. if (match(TokenType::RightBracket)) {
  626. return set_error(Error::MismatchingBracket);
  627. }
  628. if (match(TokenType::RightCurly)) {
  629. return set_error(Error::MismatchingBrace);
  630. }
  631. if (match(TokenType::Circumflex)) {
  632. consume();
  633. bytecode.empend((ByteCodeValueType)OpCodeId::CheckBegin);
  634. break;
  635. }
  636. if (match(TokenType::Dollar)) {
  637. consume();
  638. bytecode.empend((ByteCodeValueType)OpCodeId::CheckEnd);
  639. break;
  640. }
  641. if (match(TokenType::RightParen))
  642. return false;
  643. if (match(TokenType::LeftParen)) {
  644. enum GroupMode {
  645. Normal,
  646. Lookahead,
  647. NegativeLookahead,
  648. Lookbehind,
  649. NegativeLookbehind,
  650. } group_mode { Normal };
  651. consume();
  652. Optional<StringView> capture_group_name;
  653. bool prevent_capture_group = false;
  654. if (match(TokenType::Questionmark)) {
  655. consume();
  656. if (match(TokenType::Colon)) {
  657. consume();
  658. prevent_capture_group = true;
  659. } else if (consume("<")) { // named capturing group
  660. Token start_token = m_parser_state.current_token;
  661. Token last_token = m_parser_state.current_token;
  662. size_t capture_group_name_length = 0;
  663. for (;;) {
  664. if (!match_ordinary_characters())
  665. return set_error(Error::InvalidNameForCaptureGroup);
  666. if (match(TokenType::Char) && m_parser_state.current_token.value()[0] == '>') {
  667. consume();
  668. break;
  669. }
  670. ++capture_group_name_length;
  671. last_token = consume();
  672. }
  673. capture_group_name = StringView(start_token.value().characters_without_null_termination(), capture_group_name_length);
  674. ++m_parser_state.named_capture_groups_count;
  675. } else if (match(TokenType::EqualSign)) { // positive lookahead
  676. consume();
  677. group_mode = Lookahead;
  678. } else if (consume("!")) { // negative lookahead
  679. group_mode = NegativeLookahead;
  680. } else if (consume("<")) {
  681. if (match(TokenType::EqualSign)) { // positive lookbehind
  682. consume();
  683. group_mode = Lookbehind;
  684. }
  685. if (consume("!")) // negative lookbehind
  686. group_mode = NegativeLookbehind;
  687. } else {
  688. return set_error(Error::InvalidRepetitionMarker);
  689. }
  690. }
  691. auto current_capture_group = m_parser_state.capture_groups_count;
  692. if (!(m_parser_state.regex_options & AllFlags::SkipSubExprResults || prevent_capture_group)) {
  693. bytecode.insert_bytecode_group_capture_left(current_capture_group);
  694. m_parser_state.capture_groups_count++;
  695. }
  696. ByteCode capture_group_bytecode;
  697. if (!parse_root(capture_group_bytecode, length))
  698. return set_error(Error::InvalidPattern);
  699. switch (group_mode) {
  700. case Normal:
  701. bytecode.extend(move(capture_group_bytecode));
  702. break;
  703. case Lookahead:
  704. bytecode.insert_bytecode_lookaround(move(capture_group_bytecode), ByteCode::LookAroundType::LookAhead, length);
  705. break;
  706. case NegativeLookahead:
  707. bytecode.insert_bytecode_lookaround(move(capture_group_bytecode), ByteCode::LookAroundType::NegatedLookAhead, length);
  708. break;
  709. case Lookbehind:
  710. bytecode.insert_bytecode_lookaround(move(capture_group_bytecode), ByteCode::LookAroundType::LookBehind, length);
  711. break;
  712. case NegativeLookbehind:
  713. bytecode.insert_bytecode_lookaround(move(capture_group_bytecode), ByteCode::LookAroundType::NegatedLookBehind, length);
  714. break;
  715. }
  716. consume(TokenType::RightParen, Error::MismatchingParen);
  717. if (!(m_parser_state.regex_options & AllFlags::SkipSubExprResults || prevent_capture_group)) {
  718. if (capture_group_name.has_value())
  719. bytecode.insert_bytecode_group_capture_right(current_capture_group, capture_group_name.value());
  720. else
  721. bytecode.insert_bytecode_group_capture_right(current_capture_group);
  722. }
  723. should_parse_repetition_symbol = true;
  724. break;
  725. }
  726. return false;
  727. }
  728. if (match_repetition_symbol()) {
  729. if (should_parse_repetition_symbol)
  730. parse_repetition_symbol(bytecode, length);
  731. else
  732. return set_error(Error::InvalidRepetitionMarker);
  733. }
  734. stack.extend(move(bytecode));
  735. match_length_minimum += length;
  736. return true;
  737. }
  738. bool PosixExtendedParser::parse_root(ByteCode& stack, size_t& match_length_minimum)
  739. {
  740. ByteCode bytecode_left;
  741. size_t match_length_minimum_left { 0 };
  742. if (match_repetition_symbol())
  743. return set_error(Error::InvalidRepetitionMarker);
  744. for (;;) {
  745. if (!parse_sub_expression(bytecode_left, match_length_minimum_left))
  746. break;
  747. if (match(TokenType::Pipe)) {
  748. consume();
  749. ByteCode bytecode_right;
  750. size_t match_length_minimum_right { 0 };
  751. if (!parse_root(bytecode_right, match_length_minimum_right) || bytecode_right.is_empty())
  752. return set_error(Error::InvalidPattern);
  753. ByteCode new_bytecode;
  754. new_bytecode.insert_bytecode_alternation(move(bytecode_left), move(bytecode_right));
  755. bytecode_left = move(new_bytecode);
  756. match_length_minimum_left = min(match_length_minimum_right, match_length_minimum_left);
  757. }
  758. }
  759. if (bytecode_left.is_empty())
  760. set_error(Error::EmptySubExpression);
  761. stack.extend(move(bytecode_left));
  762. match_length_minimum = match_length_minimum_left;
  763. return !has_error();
  764. }
  765. // =============================
  766. // ECMA262 Parser
  767. // =============================
  768. bool ECMA262Parser::parse_internal(ByteCode& stack, size_t& match_length_minimum)
  769. {
  770. if (m_parser_state.regex_options.has_flag_set(AllFlags::Unicode)) {
  771. return parse_pattern(stack, match_length_minimum, true, true);
  772. }
  773. ByteCode new_stack;
  774. size_t new_match_length = 0;
  775. auto res = parse_pattern(new_stack, new_match_length, false, false);
  776. if (m_parser_state.named_capture_groups_count > 0) {
  777. reset();
  778. return parse_pattern(stack, match_length_minimum, false, true);
  779. }
  780. if (!res)
  781. return false;
  782. stack.extend(new_stack);
  783. match_length_minimum = new_match_length;
  784. return res;
  785. }
  786. bool ECMA262Parser::parse_pattern(ByteCode& stack, size_t& match_length_minimum, bool unicode, bool named)
  787. {
  788. return parse_disjunction(stack, match_length_minimum, unicode, named);
  789. }
  790. bool ECMA262Parser::parse_disjunction(ByteCode& stack, size_t& match_length_minimum, bool unicode, bool named)
  791. {
  792. ByteCode left_alternative_stack;
  793. size_t left_alternative_min_length = 0;
  794. auto alt_ok = parse_alternative(left_alternative_stack, left_alternative_min_length, unicode, named);
  795. if (!alt_ok)
  796. return false;
  797. if (!match(TokenType::Pipe)) {
  798. stack.extend(left_alternative_stack);
  799. match_length_minimum = left_alternative_min_length;
  800. return alt_ok;
  801. }
  802. consume();
  803. ByteCode right_alternative_stack;
  804. size_t right_alternative_min_length = 0;
  805. auto continuation_ok = parse_disjunction(right_alternative_stack, right_alternative_min_length, unicode, named);
  806. if (!continuation_ok)
  807. return false;
  808. stack.insert_bytecode_alternation(move(left_alternative_stack), move(right_alternative_stack));
  809. match_length_minimum = min(left_alternative_min_length, right_alternative_min_length);
  810. return continuation_ok;
  811. }
  812. bool ECMA262Parser::parse_alternative(ByteCode& stack, size_t& match_length_minimum, bool unicode, bool named)
  813. {
  814. for (;;) {
  815. if (match(TokenType::Eof))
  816. return true;
  817. if (parse_term(stack, match_length_minimum, unicode, named))
  818. continue;
  819. return !has_error();
  820. }
  821. }
  822. bool ECMA262Parser::parse_term(ByteCode& stack, size_t& match_length_minimum, bool unicode, bool named)
  823. {
  824. if (parse_assertion(stack, match_length_minimum, unicode, named))
  825. return true;
  826. ByteCode atom_stack;
  827. size_t minimum_atom_length = 0;
  828. auto parse_with_quantifier = [&] {
  829. bool did_parse_one = false;
  830. if (m_should_use_browser_extended_grammar)
  831. did_parse_one = parse_extended_atom(atom_stack, minimum_atom_length, named);
  832. if (!did_parse_one)
  833. did_parse_one = parse_atom(atom_stack, minimum_atom_length, unicode, named);
  834. if (!did_parse_one)
  835. return false;
  836. VERIFY(did_parse_one);
  837. return parse_quantifier(atom_stack, minimum_atom_length, unicode, named);
  838. };
  839. if (!parse_with_quantifier())
  840. return false;
  841. stack.extend(move(atom_stack));
  842. match_length_minimum += minimum_atom_length;
  843. return true;
  844. }
  845. bool ECMA262Parser::parse_assertion(ByteCode& stack, [[maybe_unused]] size_t& match_length_minimum, bool unicode, bool named)
  846. {
  847. if (match(TokenType::Circumflex)) {
  848. consume();
  849. stack.empend((ByteCodeValueType)OpCodeId::CheckBegin);
  850. return true;
  851. }
  852. if (match(TokenType::Dollar)) {
  853. consume();
  854. stack.empend((ByteCodeValueType)OpCodeId::CheckEnd);
  855. return true;
  856. }
  857. if (try_skip("\\b")) {
  858. stack.insert_bytecode_check_boundary(BoundaryCheckType::Word);
  859. return true;
  860. }
  861. if (try_skip("\\B")) {
  862. stack.insert_bytecode_check_boundary(BoundaryCheckType::NonWord);
  863. return true;
  864. }
  865. if (match(TokenType::LeftParen)) {
  866. if (!try_skip("(?"))
  867. return false;
  868. if (done()) {
  869. set_error(Error::InvalidCaptureGroup);
  870. return false;
  871. }
  872. ByteCode assertion_stack;
  873. size_t length_dummy = 0;
  874. bool should_parse_forward_assertion = m_should_use_browser_extended_grammar ? unicode : true;
  875. if (should_parse_forward_assertion && try_skip("=")) {
  876. if (!parse_inner_disjunction(assertion_stack, length_dummy, unicode, named))
  877. return false;
  878. stack.insert_bytecode_lookaround(move(assertion_stack), ByteCode::LookAroundType::LookAhead);
  879. return true;
  880. }
  881. if (should_parse_forward_assertion && try_skip("!")) {
  882. enter_capture_group_scope();
  883. ScopeGuard quit_scope {
  884. [this] {
  885. exit_capture_group_scope();
  886. }
  887. };
  888. if (!parse_inner_disjunction(assertion_stack, length_dummy, unicode, named))
  889. return false;
  890. stack.insert_bytecode_lookaround(move(assertion_stack), ByteCode::LookAroundType::NegatedLookAhead);
  891. clear_all_capture_groups_in_scope(stack);
  892. return true;
  893. }
  894. if (m_should_use_browser_extended_grammar) {
  895. if (!unicode) {
  896. if (parse_quantifiable_assertion(assertion_stack, match_length_minimum, named)) {
  897. stack.extend(move(assertion_stack));
  898. return true;
  899. }
  900. }
  901. }
  902. if (try_skip("<=")) {
  903. if (!parse_inner_disjunction(assertion_stack, length_dummy, unicode, named))
  904. return false;
  905. // FIXME: Somehow ensure that this assertion regexp has a fixed length.
  906. stack.insert_bytecode_lookaround(move(assertion_stack), ByteCode::LookAroundType::LookBehind, length_dummy);
  907. return true;
  908. }
  909. if (try_skip("<!")) {
  910. enter_capture_group_scope();
  911. ScopeGuard quit_scope {
  912. [this] {
  913. exit_capture_group_scope();
  914. }
  915. };
  916. if (!parse_inner_disjunction(assertion_stack, length_dummy, unicode, named))
  917. return false;
  918. stack.insert_bytecode_lookaround(move(assertion_stack), ByteCode::LookAroundType::NegatedLookBehind, length_dummy);
  919. clear_all_capture_groups_in_scope(stack);
  920. return true;
  921. }
  922. // If none of these matched, put the '(?' back.
  923. m_parser_state.lexer.back(3);
  924. m_parser_state.current_token = m_parser_state.lexer.next();
  925. return false;
  926. }
  927. return false;
  928. }
  929. bool ECMA262Parser::parse_inner_disjunction(ByteCode& bytecode_stack, size_t& length, bool unicode, bool named)
  930. {
  931. auto disjunction_ok = parse_disjunction(bytecode_stack, length, unicode, named);
  932. if (!disjunction_ok)
  933. return false;
  934. consume(TokenType::RightParen, Error::MismatchingParen);
  935. return true;
  936. }
  937. bool ECMA262Parser::parse_quantifiable_assertion(ByteCode& stack, size_t&, bool named)
  938. {
  939. VERIFY(m_should_use_browser_extended_grammar);
  940. ByteCode assertion_stack;
  941. size_t match_length_minimum = 0;
  942. if (try_skip("=")) {
  943. if (!parse_inner_disjunction(assertion_stack, match_length_minimum, false, named))
  944. return false;
  945. stack.insert_bytecode_lookaround(move(assertion_stack), ByteCode::LookAroundType::LookAhead);
  946. return true;
  947. }
  948. if (try_skip("!")) {
  949. enter_capture_group_scope();
  950. ScopeGuard quit_scope {
  951. [this] {
  952. exit_capture_group_scope();
  953. }
  954. };
  955. if (!parse_inner_disjunction(assertion_stack, match_length_minimum, false, named))
  956. return false;
  957. stack.insert_bytecode_lookaround(move(assertion_stack), ByteCode::LookAroundType::NegatedLookAhead);
  958. clear_all_capture_groups_in_scope(stack);
  959. return true;
  960. }
  961. return false;
  962. }
  963. StringView ECMA262Parser::read_digits_as_string(ReadDigitsInitialZeroState initial_zero, bool hex, int max_count, int min_count)
  964. {
  965. if (!match(TokenType::Char))
  966. return {};
  967. if (initial_zero == ReadDigitsInitialZeroState::Disallow && m_parser_state.current_token.value() == "0")
  968. return {};
  969. int count = 0;
  970. size_t offset = 0;
  971. auto start_token = m_parser_state.current_token;
  972. while (match(TokenType::Char)) {
  973. auto const c = m_parser_state.current_token.value();
  974. if (max_count > 0 && count >= max_count)
  975. break;
  976. if (hex && !AK::StringUtils::convert_to_uint_from_hex(c).has_value())
  977. break;
  978. if (!hex && !c.to_uint().has_value())
  979. break;
  980. offset += consume().value().length();
  981. ++count;
  982. }
  983. if (count < min_count)
  984. return {};
  985. return StringView { start_token.value().characters_without_null_termination(), offset };
  986. }
  987. Optional<unsigned> ECMA262Parser::read_digits(ECMA262Parser::ReadDigitsInitialZeroState initial_zero, bool hex, int max_count, int min_count)
  988. {
  989. auto str = read_digits_as_string(initial_zero, hex, max_count, min_count);
  990. if (str.is_empty())
  991. return {};
  992. if (hex)
  993. return AK::StringUtils::convert_to_uint_from_hex(str);
  994. return str.to_uint();
  995. }
  996. bool ECMA262Parser::parse_quantifier(ByteCode& stack, size_t& match_length_minimum, bool unicode, bool)
  997. {
  998. enum class Repetition {
  999. OneOrMore,
  1000. ZeroOrMore,
  1001. Optional,
  1002. Explicit,
  1003. None,
  1004. } repetition_mark { Repetition::None };
  1005. bool ungreedy = false;
  1006. Optional<u64> repeat_min, repeat_max;
  1007. if (match(TokenType::Asterisk)) {
  1008. consume();
  1009. repetition_mark = Repetition::ZeroOrMore;
  1010. } else if (match(TokenType::Plus)) {
  1011. consume();
  1012. repetition_mark = Repetition::OneOrMore;
  1013. } else if (match(TokenType::Questionmark)) {
  1014. consume();
  1015. repetition_mark = Repetition::Optional;
  1016. } else if (match(TokenType::LeftCurly)) {
  1017. repetition_mark = Repetition::Explicit;
  1018. if (!parse_interval_quantifier(repeat_min, repeat_max)) {
  1019. if (unicode) {
  1020. // Invalid interval quantifiers are disallowed in Unicode mod - they must be escaped with '\{'.
  1021. set_error(Error::InvalidPattern);
  1022. }
  1023. return !has_error();
  1024. }
  1025. } else {
  1026. return true;
  1027. }
  1028. if (match(TokenType::Questionmark)) {
  1029. consume();
  1030. ungreedy = true;
  1031. }
  1032. switch (repetition_mark) {
  1033. case Repetition::OneOrMore:
  1034. ByteCode::transform_bytecode_repetition_min_one(stack, !ungreedy);
  1035. break;
  1036. case Repetition::ZeroOrMore:
  1037. ByteCode::transform_bytecode_repetition_any(stack, !ungreedy);
  1038. match_length_minimum = 0;
  1039. break;
  1040. case Repetition::Optional:
  1041. ByteCode::transform_bytecode_repetition_zero_or_one(stack, !ungreedy);
  1042. match_length_minimum = 0;
  1043. break;
  1044. case Repetition::Explicit: {
  1045. auto min_repetition_mark_id = m_parser_state.repetition_mark_count++;
  1046. auto max_repetition_mark_id = m_parser_state.repetition_mark_count++;
  1047. ByteCode::transform_bytecode_repetition_min_max(stack, repeat_min.value(), repeat_max, min_repetition_mark_id, max_repetition_mark_id, !ungreedy);
  1048. match_length_minimum *= repeat_min.value();
  1049. break;
  1050. }
  1051. case Repetition::None:
  1052. VERIFY_NOT_REACHED();
  1053. }
  1054. return true;
  1055. }
  1056. bool ECMA262Parser::parse_interval_quantifier(Optional<u64>& repeat_min, Optional<u64>& repeat_max)
  1057. {
  1058. VERIFY(match(TokenType::LeftCurly));
  1059. consume();
  1060. auto chars_consumed = 1;
  1061. auto low_bound_string = read_digits_as_string();
  1062. chars_consumed += low_bound_string.length();
  1063. auto low_bound = low_bound_string.to_uint<u64>();
  1064. if (!low_bound.has_value()) {
  1065. if (!m_should_use_browser_extended_grammar && done())
  1066. return set_error(Error::MismatchingBrace);
  1067. back(chars_consumed + !done());
  1068. return false;
  1069. }
  1070. repeat_min = low_bound.value();
  1071. if (match(TokenType::Comma)) {
  1072. consume();
  1073. ++chars_consumed;
  1074. auto high_bound_string = read_digits_as_string();
  1075. auto high_bound = high_bound_string.to_uint<u64>();
  1076. if (high_bound.has_value()) {
  1077. repeat_max = high_bound.value();
  1078. chars_consumed += high_bound_string.length();
  1079. }
  1080. } else {
  1081. repeat_max = repeat_min;
  1082. }
  1083. if (!match(TokenType::RightCurly)) {
  1084. if (!m_should_use_browser_extended_grammar && done())
  1085. return set_error(Error::MismatchingBrace);
  1086. back(chars_consumed + !done());
  1087. return false;
  1088. }
  1089. consume();
  1090. ++chars_consumed;
  1091. if (repeat_max.has_value()) {
  1092. if (repeat_min.value() > repeat_max.value())
  1093. set_error(Error::InvalidBraceContent);
  1094. }
  1095. if ((*repeat_min > s_ecma262_maximum_repetition_count) || (repeat_max.has_value() && (*repeat_max > s_ecma262_maximum_repetition_count)))
  1096. return set_error(Error::InvalidBraceContent);
  1097. return true;
  1098. }
  1099. bool ECMA262Parser::parse_atom(ByteCode& stack, size_t& match_length_minimum, bool unicode, bool named)
  1100. {
  1101. if (match(TokenType::EscapeSequence)) {
  1102. // Also part of AtomEscape.
  1103. auto token = consume();
  1104. match_length_minimum += 1;
  1105. stack.insert_bytecode_compare_values({ { CharacterCompareType::Char, (u8)token.value()[1] } });
  1106. return true;
  1107. }
  1108. if (try_skip("\\")) {
  1109. // AtomEscape.
  1110. return parse_atom_escape(stack, match_length_minimum, unicode, named);
  1111. }
  1112. if (match(TokenType::LeftBracket)) {
  1113. // Character class.
  1114. return parse_character_class(stack, match_length_minimum, unicode, named);
  1115. }
  1116. if (match(TokenType::LeftParen)) {
  1117. // Non-capturing group, or a capture group.
  1118. return parse_capture_group(stack, match_length_minimum, unicode, named);
  1119. }
  1120. if (match(TokenType::Period)) {
  1121. consume();
  1122. match_length_minimum += 1;
  1123. stack.insert_bytecode_compare_values({ { CharacterCompareType::AnyChar, 0 } });
  1124. return true;
  1125. }
  1126. if (match(TokenType::Circumflex) || match(TokenType::Dollar) || match(TokenType::RightParen)
  1127. || match(TokenType::Pipe) || match(TokenType::Plus) || match(TokenType::Asterisk)
  1128. || match(TokenType::Questionmark)) {
  1129. return false;
  1130. }
  1131. if (match(TokenType::RightBracket) || match(TokenType::RightCurly) || match(TokenType::LeftCurly)) {
  1132. if (unicode)
  1133. return set_error(Error::InvalidPattern);
  1134. if (m_should_use_browser_extended_grammar) {
  1135. auto token = consume();
  1136. match_length_minimum += 1;
  1137. stack.insert_bytecode_compare_values({ { CharacterCompareType::Char, (u8)token.value()[0] } });
  1138. return true;
  1139. }
  1140. return false;
  1141. }
  1142. if (match_ordinary_characters()) {
  1143. auto token = consume().value();
  1144. match_length_minimum += 1;
  1145. stack.insert_bytecode_compare_values({ { CharacterCompareType::Char, (u8)token[0] } });
  1146. return true;
  1147. }
  1148. set_error(Error::InvalidPattern);
  1149. return false;
  1150. }
  1151. bool ECMA262Parser::parse_extended_atom(ByteCode&, size_t&, bool)
  1152. {
  1153. // Note: This includes only rules *not* present in parse_atom()
  1154. VERIFY(m_should_use_browser_extended_grammar);
  1155. return parse_invalid_braced_quantifier(); // FAIL FAIL FAIL
  1156. }
  1157. bool ECMA262Parser::parse_invalid_braced_quantifier()
  1158. {
  1159. if (!match(TokenType::LeftCurly))
  1160. return false;
  1161. consume();
  1162. size_t chars_consumed = 1;
  1163. auto low_bound = read_digits_as_string();
  1164. StringView high_bound;
  1165. if (low_bound.is_empty()) {
  1166. back(chars_consumed + !done());
  1167. return false;
  1168. }
  1169. chars_consumed += low_bound.length();
  1170. if (match(TokenType::Comma)) {
  1171. consume();
  1172. ++chars_consumed;
  1173. high_bound = read_digits_as_string();
  1174. chars_consumed += high_bound.length();
  1175. }
  1176. if (!match(TokenType::RightCurly)) {
  1177. back(chars_consumed + !done());
  1178. return false;
  1179. }
  1180. consume();
  1181. set_error(Error::InvalidPattern);
  1182. return true;
  1183. }
  1184. bool ECMA262Parser::parse_atom_escape(ByteCode& stack, size_t& match_length_minimum, bool unicode, bool named)
  1185. {
  1186. if (auto escape_str = read_digits_as_string(ReadDigitsInitialZeroState::Disallow); !escape_str.is_empty()) {
  1187. if (auto escape = escape_str.to_uint(); escape.has_value()) {
  1188. // See if this is a "back"-reference (we've already parsed the group it refers to)
  1189. auto maybe_length = m_parser_state.capture_group_minimum_lengths.get(escape.value());
  1190. if (maybe_length.has_value()) {
  1191. match_length_minimum += maybe_length.value();
  1192. stack.insert_bytecode_compare_values({ { CharacterCompareType::Reference, (ByteCodeValueType)escape.value() } });
  1193. return true;
  1194. }
  1195. // It's not a pattern seen before, so we have to see if it's a valid reference to a future group.
  1196. if (escape.value() <= ensure_total_number_of_capturing_parenthesis()) {
  1197. // This refers to a future group, and it will _always_ be matching an empty string
  1198. // So just match nothing and move on.
  1199. return true;
  1200. }
  1201. if (!m_should_use_browser_extended_grammar) {
  1202. set_error(Error::InvalidNumber);
  1203. return false;
  1204. }
  1205. }
  1206. // If not, put the characters back.
  1207. back(escape_str.length());
  1208. }
  1209. // CharacterEscape > ControlEscape
  1210. if (try_skip("f")) {
  1211. match_length_minimum += 1;
  1212. stack.insert_bytecode_compare_values({ { CharacterCompareType::Char, (ByteCodeValueType)'\f' } });
  1213. return true;
  1214. }
  1215. if (try_skip("n")) {
  1216. match_length_minimum += 1;
  1217. stack.insert_bytecode_compare_values({ { CharacterCompareType::Char, (ByteCodeValueType)'\n' } });
  1218. return true;
  1219. }
  1220. if (try_skip("r")) {
  1221. match_length_minimum += 1;
  1222. stack.insert_bytecode_compare_values({ { CharacterCompareType::Char, (ByteCodeValueType)'\r' } });
  1223. return true;
  1224. }
  1225. if (try_skip("t")) {
  1226. match_length_minimum += 1;
  1227. stack.insert_bytecode_compare_values({ { CharacterCompareType::Char, (ByteCodeValueType)'\t' } });
  1228. return true;
  1229. }
  1230. if (try_skip("v")) {
  1231. match_length_minimum += 1;
  1232. stack.insert_bytecode_compare_values({ { CharacterCompareType::Char, (ByteCodeValueType)'\v' } });
  1233. return true;
  1234. }
  1235. // CharacterEscape > ControlLetter
  1236. if (try_skip("c")) {
  1237. for (auto c : s_alphabetic_characters) {
  1238. if (try_skip({ &c, 1 })) {
  1239. match_length_minimum += 1;
  1240. stack.insert_bytecode_compare_values({ { CharacterCompareType::Char, (ByteCodeValueType)(c % 32) } });
  1241. return true;
  1242. }
  1243. }
  1244. if (unicode) {
  1245. set_error(Error::InvalidPattern);
  1246. return false;
  1247. }
  1248. if (m_should_use_browser_extended_grammar) {
  1249. back(1 + !done());
  1250. stack.insert_bytecode_compare_values({ { CharacterCompareType::Char, (ByteCodeValueType)'\\' } });
  1251. match_length_minimum += 1;
  1252. return true;
  1253. }
  1254. // Allow '\c' in non-unicode mode, just matches 'c'.
  1255. match_length_minimum += 1;
  1256. stack.insert_bytecode_compare_values({ { CharacterCompareType::Char, (ByteCodeValueType)'c' } });
  1257. return true;
  1258. }
  1259. // '\0'
  1260. if (try_skip("0")) {
  1261. if (!lookahead_any(s_decimal_characters)) {
  1262. match_length_minimum += 1;
  1263. stack.insert_bytecode_compare_values({ { CharacterCompareType::Char, (ByteCodeValueType)0 } });
  1264. return true;
  1265. }
  1266. back();
  1267. }
  1268. // LegacyOctalEscapeSequence
  1269. if (m_should_use_browser_extended_grammar) {
  1270. if (!unicode) {
  1271. if (auto escape = parse_legacy_octal_escape(); escape.has_value()) {
  1272. stack.insert_bytecode_compare_values({ { CharacterCompareType::Char, (ByteCodeValueType)escape.value() } });
  1273. match_length_minimum += 1;
  1274. return true;
  1275. }
  1276. }
  1277. }
  1278. // HexEscape
  1279. if (try_skip("x")) {
  1280. if (auto hex_escape = read_digits(ReadDigitsInitialZeroState::Allow, true, 2, 2); hex_escape.has_value()) {
  1281. match_length_minimum += 1;
  1282. stack.insert_bytecode_compare_values({ { CharacterCompareType::Char, (ByteCodeValueType)hex_escape.value() } });
  1283. return true;
  1284. }
  1285. if (!unicode) {
  1286. // '\x' is allowed in non-unicode mode, just matches 'x'.
  1287. match_length_minimum += 1;
  1288. stack.insert_bytecode_compare_values({ { CharacterCompareType::Char, (ByteCodeValueType)'x' } });
  1289. return true;
  1290. }
  1291. set_error(Error::InvalidPattern);
  1292. return false;
  1293. }
  1294. if (try_skip("u")) {
  1295. if (auto code_point = consume_escaped_code_point(unicode); code_point.has_value()) {
  1296. match_length_minimum += 1;
  1297. stack.insert_bytecode_compare_values({ { CharacterCompareType::Char, (ByteCodeValueType)code_point.value() } });
  1298. return true;
  1299. }
  1300. return false;
  1301. }
  1302. // IdentityEscape
  1303. for (auto ch : identity_escape_characters(unicode, m_should_use_browser_extended_grammar)) {
  1304. if (try_skip({ &ch, 1 })) {
  1305. match_length_minimum += 1;
  1306. stack.insert_bytecode_compare_values({ { CharacterCompareType::Char, (ByteCodeValueType)ch } });
  1307. return true;
  1308. }
  1309. }
  1310. if (unicode) {
  1311. if (try_skip("/")) {
  1312. match_length_minimum += 1;
  1313. stack.insert_bytecode_compare_values({ { CharacterCompareType::Char, (ByteCodeValueType)'/' } });
  1314. return true;
  1315. }
  1316. }
  1317. if (named && try_skip("k")) {
  1318. auto name = read_capture_group_specifier(true);
  1319. if (name.is_empty()) {
  1320. set_error(Error::InvalidNameForCaptureGroup);
  1321. return false;
  1322. }
  1323. auto maybe_capture_group = m_parser_state.named_capture_groups.get(name);
  1324. if (!maybe_capture_group.has_value()) {
  1325. set_error(Error::InvalidNameForCaptureGroup);
  1326. return false;
  1327. }
  1328. match_length_minimum += maybe_capture_group->minimum_length;
  1329. stack.insert_bytecode_compare_values({ { CharacterCompareType::Reference, (ByteCodeValueType)maybe_capture_group->group_index } });
  1330. return true;
  1331. }
  1332. if (unicode) {
  1333. PropertyEscape property {};
  1334. bool negated = false;
  1335. if (parse_unicode_property_escape(property, negated)) {
  1336. Vector<CompareTypeAndValuePair> compares;
  1337. if (negated)
  1338. compares.empend(CompareTypeAndValuePair { CharacterCompareType::Inverse, 0 });
  1339. property.visit(
  1340. [&](Unicode::Property property) {
  1341. compares.empend(CompareTypeAndValuePair { CharacterCompareType::Property, (ByteCodeValueType)property });
  1342. },
  1343. [&](Unicode::GeneralCategory general_category) {
  1344. compares.empend(CompareTypeAndValuePair { CharacterCompareType::GeneralCategory, (ByteCodeValueType)general_category });
  1345. },
  1346. [&](Script script) {
  1347. if (script.is_extension)
  1348. compares.empend(CompareTypeAndValuePair { CharacterCompareType::ScriptExtension, (ByteCodeValueType)script.script });
  1349. else
  1350. compares.empend(CompareTypeAndValuePair { CharacterCompareType::Script, (ByteCodeValueType)script.script });
  1351. },
  1352. [](Empty&) { VERIFY_NOT_REACHED(); });
  1353. stack.insert_bytecode_compare_values(move(compares));
  1354. match_length_minimum += 1;
  1355. return true;
  1356. }
  1357. }
  1358. if (done())
  1359. return set_error(Error::InvalidTrailingEscape);
  1360. bool negate = false;
  1361. auto ch = parse_character_class_escape(negate);
  1362. if (!ch.has_value()) {
  1363. if (!unicode) {
  1364. // Allow all SourceCharacter's as escapes here.
  1365. auto token = consume();
  1366. match_length_minimum += 1;
  1367. stack.insert_bytecode_compare_values({ { CharacterCompareType::Char, (u8)token.value()[0] } });
  1368. return true;
  1369. }
  1370. set_error(Error::InvalidCharacterClass);
  1371. return false;
  1372. }
  1373. Vector<CompareTypeAndValuePair> compares;
  1374. if (negate)
  1375. compares.empend(CompareTypeAndValuePair { CharacterCompareType::Inverse, 0 });
  1376. compares.empend(CompareTypeAndValuePair { CharacterCompareType::CharClass, (ByteCodeValueType)ch.value() });
  1377. match_length_minimum += 1;
  1378. stack.insert_bytecode_compare_values(move(compares));
  1379. return true;
  1380. }
  1381. Optional<u8> ECMA262Parser::parse_legacy_octal_escape()
  1382. {
  1383. constexpr auto all_octal_digits = "01234567";
  1384. auto read_octal_digit = [&](auto start, auto end, bool should_ensure_no_following_octal_digit) -> Optional<u8> {
  1385. for (char c = '0' + start; c <= '0' + end; ++c) {
  1386. if (try_skip({ &c, 1 })) {
  1387. if (!should_ensure_no_following_octal_digit || !lookahead_any(all_octal_digits))
  1388. return c - '0';
  1389. back(2);
  1390. return {};
  1391. }
  1392. }
  1393. return {};
  1394. };
  1395. // OctalDigit(1)
  1396. if (auto digit = read_octal_digit(0, 7, true); digit.has_value()) {
  1397. return digit.value();
  1398. }
  1399. // OctalDigit(2)
  1400. if (auto left_digit = read_octal_digit(0, 3, false); left_digit.has_value()) {
  1401. if (auto right_digit = read_octal_digit(0, 7, true); right_digit.has_value()) {
  1402. return left_digit.value() * 8 + right_digit.value();
  1403. }
  1404. back(2);
  1405. }
  1406. // OctalDigit(2)
  1407. if (auto left_digit = read_octal_digit(4, 7, false); left_digit.has_value()) {
  1408. if (auto right_digit = read_octal_digit(0, 7, false); right_digit.has_value()) {
  1409. return left_digit.value() * 8 + right_digit.value();
  1410. }
  1411. back(2);
  1412. }
  1413. // OctalDigit(3)
  1414. if (auto left_digit = read_octal_digit(0, 3, false); left_digit.has_value()) {
  1415. size_t chars_consumed = 1;
  1416. if (auto mid_digit = read_octal_digit(0, 7, false); mid_digit.has_value()) {
  1417. ++chars_consumed;
  1418. if (auto right_digit = read_octal_digit(0, 7, false); right_digit.has_value()) {
  1419. return left_digit.value() * 64 + mid_digit.value() * 8 + right_digit.value();
  1420. }
  1421. }
  1422. back(chars_consumed);
  1423. }
  1424. return {};
  1425. }
  1426. Optional<CharClass> ECMA262Parser::parse_character_class_escape(bool& negate, bool expect_backslash)
  1427. {
  1428. if (expect_backslash && !try_skip("\\"))
  1429. return {};
  1430. // CharacterClassEscape
  1431. CharClass ch_class;
  1432. if (try_skip("d")) {
  1433. ch_class = CharClass::Digit;
  1434. } else if (try_skip("D")) {
  1435. ch_class = CharClass::Digit;
  1436. negate = true;
  1437. } else if (try_skip("s")) {
  1438. ch_class = CharClass::Space;
  1439. } else if (try_skip("S")) {
  1440. ch_class = CharClass::Space;
  1441. negate = true;
  1442. } else if (try_skip("w")) {
  1443. ch_class = CharClass::Word;
  1444. } else if (try_skip("W")) {
  1445. ch_class = CharClass::Word;
  1446. negate = true;
  1447. } else {
  1448. return {};
  1449. }
  1450. return ch_class;
  1451. }
  1452. bool ECMA262Parser::parse_character_class(ByteCode& stack, size_t& match_length_minimum, bool unicode, bool)
  1453. {
  1454. consume(TokenType::LeftBracket, Error::InvalidPattern);
  1455. Vector<CompareTypeAndValuePair> compares;
  1456. if (match(TokenType::Circumflex)) {
  1457. // Negated charclass
  1458. consume();
  1459. compares.empend(CompareTypeAndValuePair { CharacterCompareType::Inverse, 0 });
  1460. }
  1461. if (match(TokenType::RightBracket)) {
  1462. consume();
  1463. // Should only have at most an 'Inverse'
  1464. VERIFY(compares.size() <= 1);
  1465. stack.insert_bytecode_compare_values(move(compares));
  1466. return true;
  1467. }
  1468. if (!parse_nonempty_class_ranges(compares, unicode))
  1469. return false;
  1470. match_length_minimum += 1;
  1471. stack.insert_bytecode_compare_values(move(compares));
  1472. return true;
  1473. }
  1474. struct CharClassRangeElement {
  1475. union {
  1476. CharClass character_class;
  1477. u32 code_point { 0 };
  1478. Unicode::Property property;
  1479. Unicode::GeneralCategory general_category;
  1480. Unicode::Script script;
  1481. };
  1482. bool is_negated { false };
  1483. bool is_character_class { false };
  1484. bool is_property { false };
  1485. bool is_general_category { false };
  1486. bool is_script { false };
  1487. bool is_script_extension { false };
  1488. };
  1489. bool ECMA262Parser::parse_nonempty_class_ranges(Vector<CompareTypeAndValuePair>& ranges, bool unicode)
  1490. {
  1491. auto read_class_atom_no_dash = [&]() -> Optional<CharClassRangeElement> {
  1492. if (match(TokenType::EscapeSequence)) {
  1493. auto token = consume().value();
  1494. return { CharClassRangeElement { .code_point = (u32)token[1], .is_character_class = false } };
  1495. }
  1496. if (try_skip("\\")) {
  1497. if (done()) {
  1498. set_error(Error::InvalidTrailingEscape);
  1499. return {};
  1500. }
  1501. if (try_skip("f"))
  1502. return { CharClassRangeElement { .code_point = '\f', .is_character_class = false } };
  1503. if (try_skip("n"))
  1504. return { CharClassRangeElement { .code_point = '\n', .is_character_class = false } };
  1505. if (try_skip("r"))
  1506. return { CharClassRangeElement { .code_point = '\r', .is_character_class = false } };
  1507. if (try_skip("t"))
  1508. return { CharClassRangeElement { .code_point = '\t', .is_character_class = false } };
  1509. if (try_skip("v"))
  1510. return { CharClassRangeElement { .code_point = '\v', .is_character_class = false } };
  1511. if (try_skip("b"))
  1512. return { CharClassRangeElement { .code_point = '\b', .is_character_class = false } };
  1513. if (try_skip("/"))
  1514. return { CharClassRangeElement { .code_point = '/', .is_character_class = false } };
  1515. // CharacterEscape > ControlLetter
  1516. if (try_skip("c")) {
  1517. for (auto c : s_alphabetic_characters) {
  1518. if (try_skip({ &c, 1 })) {
  1519. return { CharClassRangeElement { .code_point = (u32)(c % 32), .is_character_class = false } };
  1520. }
  1521. }
  1522. if (unicode) {
  1523. set_error(Error::InvalidPattern);
  1524. return {};
  1525. }
  1526. if (m_should_use_browser_extended_grammar) {
  1527. for (auto c = '0'; c <= '9'; ++c) {
  1528. if (try_skip({ &c, 1 }))
  1529. return { CharClassRangeElement { .code_point = (u32)(c % 32), .is_character_class = false } };
  1530. }
  1531. if (try_skip("_"))
  1532. return { CharClassRangeElement { .code_point = (u32)('_' % 32), .is_character_class = false } };
  1533. back(1 + !done());
  1534. return { CharClassRangeElement { .code_point = '\\', .is_character_class = false } };
  1535. }
  1536. }
  1537. // '\0'
  1538. if (try_skip("0")) {
  1539. if (!lookahead_any(s_decimal_characters))
  1540. return { CharClassRangeElement { .code_point = 0, .is_character_class = false } };
  1541. back();
  1542. }
  1543. // LegacyOctalEscapeSequence
  1544. if (m_should_use_browser_extended_grammar && !unicode) {
  1545. if (auto escape = parse_legacy_octal_escape(); escape.has_value())
  1546. return { CharClassRangeElement { .code_point = escape.value(), .is_character_class = false } };
  1547. }
  1548. // HexEscape
  1549. if (try_skip("x")) {
  1550. if (auto hex_escape = read_digits(ReadDigitsInitialZeroState::Allow, true, 2, 2); hex_escape.has_value()) {
  1551. return { CharClassRangeElement { .code_point = hex_escape.value(), .is_character_class = false } };
  1552. } else if (!unicode) {
  1553. // '\x' is allowed in non-unicode mode, just matches 'x'.
  1554. return { CharClassRangeElement { .code_point = 'x', .is_character_class = false } };
  1555. } else {
  1556. set_error(Error::InvalidPattern);
  1557. return {};
  1558. }
  1559. }
  1560. if (try_skip("u")) {
  1561. if (auto code_point = consume_escaped_code_point(unicode); code_point.has_value()) {
  1562. // FIXME: While code point ranges are supported, code point matches as "Char" are not!
  1563. return { CharClassRangeElement { .code_point = code_point.value(), .is_character_class = false } };
  1564. }
  1565. return {};
  1566. }
  1567. // IdentityEscape
  1568. for (auto ch : identity_escape_characters(unicode, m_should_use_browser_extended_grammar)) {
  1569. if (try_skip({ &ch, 1 }))
  1570. return { CharClassRangeElement { .code_point = (u32)ch, .is_character_class = false } };
  1571. }
  1572. if (unicode) {
  1573. if (try_skip("-"))
  1574. return { CharClassRangeElement { .code_point = '-', .is_character_class = false } };
  1575. PropertyEscape property {};
  1576. bool negated = false;
  1577. if (parse_unicode_property_escape(property, negated)) {
  1578. return property.visit(
  1579. [&](Unicode::Property property) {
  1580. return CharClassRangeElement { .property = property, .is_negated = negated, .is_character_class = true, .is_property = true };
  1581. },
  1582. [&](Unicode::GeneralCategory general_category) {
  1583. return CharClassRangeElement { .general_category = general_category, .is_negated = negated, .is_character_class = true, .is_general_category = true };
  1584. },
  1585. [&](Script script) {
  1586. if (script.is_extension)
  1587. return CharClassRangeElement { .script = script.script, .is_negated = negated, .is_character_class = true, .is_script_extension = true };
  1588. return CharClassRangeElement { .script = script.script, .is_negated = negated, .is_character_class = true, .is_script = true };
  1589. },
  1590. [](Empty&) -> CharClassRangeElement { VERIFY_NOT_REACHED(); });
  1591. }
  1592. }
  1593. if (try_skip("d"))
  1594. return { CharClassRangeElement { .character_class = CharClass::Digit, .is_character_class = true } };
  1595. if (try_skip("s"))
  1596. return { CharClassRangeElement { .character_class = CharClass::Space, .is_character_class = true } };
  1597. if (try_skip("w"))
  1598. return { CharClassRangeElement { .character_class = CharClass::Word, .is_character_class = true } };
  1599. if (try_skip("D"))
  1600. return { CharClassRangeElement { .character_class = CharClass::Digit, .is_negated = true, .is_character_class = true } };
  1601. if (try_skip("S"))
  1602. return { CharClassRangeElement { .character_class = CharClass::Space, .is_negated = true, .is_character_class = true } };
  1603. if (try_skip("W"))
  1604. return { CharClassRangeElement { .character_class = CharClass::Word, .is_negated = true, .is_character_class = true } };
  1605. if (!unicode) {
  1606. // Any unrecognised escape is allowed in non-unicode mode.
  1607. return { CharClassRangeElement { .code_point = (u32)skip(), .is_character_class = false } };
  1608. }
  1609. set_error(Error::InvalidPattern);
  1610. return {};
  1611. }
  1612. if (match(TokenType::RightBracket) || match(TokenType::HyphenMinus))
  1613. return {};
  1614. // Allow any (other) SourceCharacter.
  1615. return { CharClassRangeElement { .code_point = (u32)skip(), .is_character_class = false } };
  1616. };
  1617. auto read_class_atom = [&]() -> Optional<CharClassRangeElement> {
  1618. if (match(TokenType::HyphenMinus)) {
  1619. consume();
  1620. return { CharClassRangeElement { .code_point = '-', .is_character_class = false } };
  1621. }
  1622. return read_class_atom_no_dash();
  1623. };
  1624. auto empend_atom = [&](auto& atom) {
  1625. if (atom.is_character_class) {
  1626. if (atom.is_negated)
  1627. ranges.empend(CompareTypeAndValuePair { CharacterCompareType::TemporaryInverse, 0 });
  1628. if (atom.is_property)
  1629. ranges.empend(CompareTypeAndValuePair { CharacterCompareType::Property, (ByteCodeValueType)(atom.property) });
  1630. else if (atom.is_general_category)
  1631. ranges.empend(CompareTypeAndValuePair { CharacterCompareType::GeneralCategory, (ByteCodeValueType)(atom.general_category) });
  1632. else if (atom.is_script)
  1633. ranges.empend(CompareTypeAndValuePair { CharacterCompareType::Script, (ByteCodeValueType)(atom.script) });
  1634. else if (atom.is_script_extension)
  1635. ranges.empend(CompareTypeAndValuePair { CharacterCompareType::ScriptExtension, (ByteCodeValueType)(atom.script) });
  1636. else
  1637. ranges.empend(CompareTypeAndValuePair { CharacterCompareType::CharClass, (ByteCodeValueType)atom.character_class });
  1638. } else {
  1639. VERIFY(!atom.is_negated);
  1640. ranges.empend(CompareTypeAndValuePair { CharacterCompareType::Char, atom.code_point });
  1641. }
  1642. };
  1643. while (!match(TokenType::RightBracket)) {
  1644. if (match(TokenType::Eof)) {
  1645. set_error(Error::MismatchingBracket);
  1646. return false;
  1647. }
  1648. auto first_atom = read_class_atom();
  1649. if (!first_atom.has_value())
  1650. return false;
  1651. if (match(TokenType::HyphenMinus)) {
  1652. consume();
  1653. if (match(TokenType::RightBracket)) {
  1654. // Allow '-' as the last element in a charclass, even after an atom.
  1655. m_parser_state.lexer.back(2); // -]
  1656. m_parser_state.current_token = m_parser_state.lexer.next();
  1657. goto read_as_single_atom;
  1658. }
  1659. auto second_atom = read_class_atom();
  1660. if (!second_atom.has_value())
  1661. return false;
  1662. if (first_atom.value().is_character_class || second_atom.value().is_character_class) {
  1663. if (m_should_use_browser_extended_grammar) {
  1664. if (unicode) {
  1665. set_error(Error::InvalidRange);
  1666. return false;
  1667. }
  1668. // CharacterRangeOrUnion > !Unicode > CharClass
  1669. empend_atom(*first_atom);
  1670. ranges.empend(CompareTypeAndValuePair { CharacterCompareType::Char, (ByteCodeValueType)'-' });
  1671. empend_atom(*second_atom);
  1672. continue;
  1673. }
  1674. set_error(Error::InvalidRange);
  1675. return false;
  1676. }
  1677. if (first_atom.value().code_point > second_atom.value().code_point) {
  1678. set_error(Error::InvalidRange);
  1679. return false;
  1680. }
  1681. VERIFY(!first_atom.value().is_negated);
  1682. VERIFY(!second_atom.value().is_negated);
  1683. ranges.empend(CompareTypeAndValuePair { CharacterCompareType::CharRange, CharRange { first_atom.value().code_point, second_atom.value().code_point } });
  1684. continue;
  1685. }
  1686. read_as_single_atom:;
  1687. auto atom = first_atom.value();
  1688. empend_atom(atom);
  1689. }
  1690. consume(TokenType::RightBracket, Error::MismatchingBracket);
  1691. return true;
  1692. }
  1693. bool ECMA262Parser::parse_unicode_property_escape(PropertyEscape& property, bool& negated)
  1694. {
  1695. negated = false;
  1696. if (try_skip("p"))
  1697. negated = false;
  1698. else if (try_skip("P"))
  1699. negated = true;
  1700. else
  1701. return false;
  1702. auto parsed_property = read_unicode_property_escape();
  1703. if (!parsed_property.has_value()) {
  1704. set_error(Error::InvalidNameForProperty);
  1705. return false;
  1706. }
  1707. property = move(*parsed_property);
  1708. return property.visit(
  1709. [this](Unicode::Property property) {
  1710. if (!Unicode::is_ecma262_property(property)) {
  1711. set_error(Error::InvalidNameForProperty);
  1712. return false;
  1713. }
  1714. return true;
  1715. },
  1716. [](Unicode::GeneralCategory) { return true; },
  1717. [](Script) { return true; },
  1718. [](Empty&) -> bool { VERIFY_NOT_REACHED(); });
  1719. }
  1720. FlyString ECMA262Parser::read_capture_group_specifier(bool take_starting_angle_bracket)
  1721. {
  1722. static auto id_start_category = Unicode::property_from_string("ID_Start"sv);
  1723. static auto id_continue_category = Unicode::property_from_string("ID_Continue"sv);
  1724. static constexpr const u32 REPLACEMENT_CHARACTER = 0xFFFD;
  1725. constexpr const u32 ZERO_WIDTH_NON_JOINER { 0x200C };
  1726. constexpr const u32 ZERO_WIDTH_JOINER { 0x200D };
  1727. if (take_starting_angle_bracket && !consume("<"))
  1728. return {};
  1729. StringBuilder builder;
  1730. auto consume_code_point = [&] {
  1731. Utf8View utf_8_view { m_parser_state.lexer.source().substring_view(m_parser_state.lexer.tell() - 1) };
  1732. if (utf_8_view.is_empty())
  1733. return REPLACEMENT_CHARACTER;
  1734. u32 code_point = *utf_8_view.begin();
  1735. auto characters = utf_8_view.byte_offset_of(1);
  1736. while (characters-- > 0)
  1737. consume();
  1738. return code_point;
  1739. };
  1740. {
  1741. // The first character is limited to: https://tc39.es/ecma262/#prod-RegExpIdentifierStart
  1742. // RegExpIdentifierStart[UnicodeMode] ::
  1743. // IdentifierStartChar
  1744. // \ RegExpUnicodeEscapeSequence[+UnicodeMode]
  1745. // [~UnicodeMode] UnicodeLeadSurrogate UnicodeTrailSurrogate
  1746. auto code_point = consume_code_point();
  1747. if (code_point == '\\' && match('u')) {
  1748. consume();
  1749. if (auto maybe_code_point = consume_escaped_code_point(true); maybe_code_point.has_value()) {
  1750. code_point = *maybe_code_point;
  1751. } else {
  1752. set_error(Error::InvalidNameForCaptureGroup);
  1753. return {};
  1754. }
  1755. }
  1756. if (is_ascii(code_point)) {
  1757. // The only valid ID_Start unicode characters in ascii are the letters.
  1758. if (!is_ascii_alpha(code_point) && code_point != '$' && code_point != '_') {
  1759. set_error(Error::InvalidNameForCaptureGroup);
  1760. return {};
  1761. }
  1762. } else if (id_start_category.has_value() && !Unicode::code_point_has_property(code_point, *id_start_category)) {
  1763. set_error(Error::InvalidNameForCaptureGroup);
  1764. return {};
  1765. }
  1766. builder.append_code_point(code_point);
  1767. }
  1768. bool hit_end = false;
  1769. // Any following characters are limited to:
  1770. // RegExpIdentifierPart[UnicodeMode] ::
  1771. // IdentifierPartChar
  1772. // \ RegExpUnicodeEscapeSequence[+UnicodeMode]
  1773. // [~UnicodeMode] UnicodeLeadSurrogate UnicodeTrailSurrogate
  1774. while (match(TokenType::Char) || match(TokenType::Dollar) || match(TokenType::LeftCurly) || match(TokenType::RightCurly)) {
  1775. auto code_point = consume_code_point();
  1776. if (code_point == '>') {
  1777. hit_end = true;
  1778. break;
  1779. }
  1780. if (code_point == '\\') {
  1781. if (!try_skip("u")) {
  1782. set_error(Error::InvalidNameForCaptureGroup);
  1783. return {};
  1784. }
  1785. if (auto maybe_code_point = consume_escaped_code_point(true); maybe_code_point.has_value()) {
  1786. code_point = *maybe_code_point;
  1787. } else {
  1788. set_error(Error::InvalidNameForCaptureGroup);
  1789. return {};
  1790. }
  1791. }
  1792. if (is_ascii(code_point)) {
  1793. // The only valid ID_Continue unicode characters in ascii are the letters and numbers.
  1794. if (!is_ascii_alphanumeric(code_point) && code_point != '$' && code_point != '_') {
  1795. set_error(Error::InvalidNameForCaptureGroup);
  1796. return {};
  1797. }
  1798. } else if (code_point != ZERO_WIDTH_JOINER && code_point != ZERO_WIDTH_NON_JOINER) {
  1799. if (id_continue_category.has_value() && !Unicode::code_point_has_property(code_point, *id_continue_category)) {
  1800. set_error(Error::InvalidNameForCaptureGroup);
  1801. return {};
  1802. }
  1803. }
  1804. builder.append_code_point(code_point);
  1805. }
  1806. FlyString name = builder.build();
  1807. if (!hit_end || name.is_empty())
  1808. set_error(Error::InvalidNameForCaptureGroup);
  1809. return name;
  1810. }
  1811. Optional<ECMA262Parser::PropertyEscape> ECMA262Parser::read_unicode_property_escape()
  1812. {
  1813. consume(TokenType::LeftCurly, Error::InvalidPattern);
  1814. // Note: clang-format is disabled here because it doesn't handle templated lambdas yet.
  1815. // clang-format off
  1816. auto read_until = [&]<typename... Ts>(Ts&&... terminators) {
  1817. auto start_token = m_parser_state.current_token;
  1818. size_t offset = 0;
  1819. while (match(TokenType::Char)) {
  1820. if (m_parser_state.current_token.value().is_one_of(forward<Ts>(terminators)...))
  1821. break;
  1822. offset += consume().value().length();
  1823. }
  1824. return StringView { start_token.value().characters_without_null_termination(), offset };
  1825. };
  1826. // clang-format on
  1827. StringView property_type;
  1828. StringView property_name = read_until("="sv, "}"sv);
  1829. if (try_skip("="sv)) {
  1830. if (property_name.is_empty())
  1831. return {};
  1832. property_type = property_name;
  1833. property_name = read_until("}"sv);
  1834. }
  1835. consume(TokenType::RightCurly, Error::InvalidPattern);
  1836. if (property_type.is_empty()) {
  1837. if (auto property = Unicode::property_from_string(property_name); property.has_value())
  1838. return { *property };
  1839. if (auto general_category = Unicode::general_category_from_string(property_name); general_category.has_value())
  1840. return { *general_category };
  1841. } else if ((property_type == "General_Category"sv) || (property_type == "gc"sv)) {
  1842. if (auto general_category = Unicode::general_category_from_string(property_name); general_category.has_value())
  1843. return { *general_category };
  1844. } else if ((property_type == "Script"sv) || (property_type == "sc"sv)) {
  1845. if (auto script = Unicode::script_from_string(property_name); script.has_value())
  1846. return Script { *script, false };
  1847. } else if ((property_type == "Script_Extensions"sv) || (property_type == "scx"sv)) {
  1848. if (auto script = Unicode::script_from_string(property_name); script.has_value())
  1849. return Script { *script, true };
  1850. }
  1851. return {};
  1852. }
  1853. bool ECMA262Parser::parse_capture_group(ByteCode& stack, size_t& match_length_minimum, bool unicode, bool named)
  1854. {
  1855. consume(TokenType::LeftParen, Error::InvalidPattern);
  1856. auto register_capture_group_in_current_scope = [&](auto identifier) {
  1857. m_capture_groups_in_scope.last().empend(identifier);
  1858. };
  1859. if (match(TokenType::Questionmark)) {
  1860. // Non-capturing group or group with specifier.
  1861. consume();
  1862. if (match(TokenType::Colon)) {
  1863. consume();
  1864. ByteCode noncapture_group_bytecode;
  1865. size_t length = 0;
  1866. enter_capture_group_scope();
  1867. if (!parse_disjunction(noncapture_group_bytecode, length, unicode, named))
  1868. return set_error(Error::InvalidPattern);
  1869. clear_all_capture_groups_in_scope(stack);
  1870. exit_capture_group_scope();
  1871. consume(TokenType::RightParen, Error::MismatchingParen);
  1872. stack.extend(move(noncapture_group_bytecode));
  1873. match_length_minimum += length;
  1874. return true;
  1875. }
  1876. if (consume("<")) {
  1877. ++m_parser_state.named_capture_groups_count;
  1878. auto group_index = ++m_parser_state.capture_groups_count; // Named capture groups count as normal capture groups too.
  1879. auto name = read_capture_group_specifier();
  1880. if (name.is_empty()) {
  1881. set_error(Error::InvalidNameForCaptureGroup);
  1882. return false;
  1883. }
  1884. if (m_parser_state.named_capture_groups.contains(name)) {
  1885. set_error(Error::DuplicateNamedCapture);
  1886. return false;
  1887. }
  1888. ByteCode capture_group_bytecode;
  1889. size_t length = 0;
  1890. enter_capture_group_scope();
  1891. if (!parse_disjunction(capture_group_bytecode, length, unicode, named))
  1892. return set_error(Error::InvalidPattern);
  1893. clear_all_capture_groups_in_scope(stack);
  1894. exit_capture_group_scope();
  1895. register_capture_group_in_current_scope(group_index);
  1896. consume(TokenType::RightParen, Error::MismatchingParen);
  1897. stack.insert_bytecode_group_capture_left(group_index);
  1898. stack.extend(move(capture_group_bytecode));
  1899. stack.insert_bytecode_group_capture_right(group_index, name.view());
  1900. match_length_minimum += length;
  1901. m_parser_state.capture_group_minimum_lengths.set(group_index, length);
  1902. m_parser_state.named_capture_groups.set(name, { group_index, length });
  1903. return true;
  1904. }
  1905. set_error(Error::InvalidCaptureGroup);
  1906. return false;
  1907. }
  1908. auto group_index = ++m_parser_state.capture_groups_count;
  1909. enter_capture_group_scope();
  1910. ByteCode capture_group_bytecode;
  1911. size_t length = 0;
  1912. if (!parse_disjunction(capture_group_bytecode, length, unicode, named))
  1913. return set_error(Error::InvalidPattern);
  1914. clear_all_capture_groups_in_scope(stack);
  1915. exit_capture_group_scope();
  1916. register_capture_group_in_current_scope(group_index);
  1917. stack.insert_bytecode_group_capture_left(group_index);
  1918. stack.extend(move(capture_group_bytecode));
  1919. m_parser_state.capture_group_minimum_lengths.set(group_index, length);
  1920. consume(TokenType::RightParen, Error::MismatchingParen);
  1921. stack.insert_bytecode_group_capture_right(group_index);
  1922. match_length_minimum += length;
  1923. return true;
  1924. }
  1925. size_t ECMA262Parser::ensure_total_number_of_capturing_parenthesis()
  1926. {
  1927. if (m_total_number_of_capturing_parenthesis.has_value())
  1928. return m_total_number_of_capturing_parenthesis.value();
  1929. GenericLexer lexer { m_parser_state.lexer.source() };
  1930. size_t count = 0;
  1931. while (!lexer.is_eof()) {
  1932. switch (lexer.peek()) {
  1933. case '\\':
  1934. lexer.consume(2);
  1935. continue;
  1936. case '[':
  1937. while (!lexer.is_eof()) {
  1938. if (lexer.consume_specific('\\'))
  1939. lexer.consume();
  1940. else if (lexer.consume_specific(']'))
  1941. break;
  1942. lexer.consume();
  1943. }
  1944. break;
  1945. case '(':
  1946. lexer.consume();
  1947. if (lexer.consume_specific('?')) {
  1948. // non-capturing group '(?:', lookaround '(?<='/'(?<!', or named capture '(?<'
  1949. if (!lexer.consume_specific('<'))
  1950. break;
  1951. if (lexer.next_is(is_any_of("=!")))
  1952. break;
  1953. ++count;
  1954. } else {
  1955. ++count;
  1956. }
  1957. break;
  1958. default:
  1959. lexer.consume();
  1960. break;
  1961. }
  1962. }
  1963. m_total_number_of_capturing_parenthesis = count;
  1964. return count;
  1965. }
  1966. }