RegexParser.cpp 76 KB

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