Parser.cpp 50 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175117611771178117911801181118211831184118511861187118811891190119111921193119411951196119711981199120012011202120312041205120612071208120912101211121212131214121512161217121812191220122112221223122412251226122712281229123012311232123312341235123612371238123912401241124212431244124512461247124812491250125112521253125412551256125712581259126012611262126312641265126612671268126912701271127212731274127512761277127812791280128112821283128412851286128712881289129012911292129312941295129612971298129913001301130213031304130513061307130813091310131113121313131413151316131713181319132013211322132313241325132613271328132913301331133213331334133513361337133813391340134113421343134413451346134713481349135013511352135313541355135613571358135913601361136213631364136513661367136813691370137113721373137413751376137713781379138013811382138313841385138613871388138913901391139213931394139513961397139813991400140114021403140414051406140714081409141014111412141314141415141614171418141914201421142214231424142514261427142814291430143114321433143414351436143714381439144014411442144314441445144614471448144914501451145214531454145514561457145814591460146114621463146414651466146714681469147014711472147314741475147614771478147914801481148214831484148514861487148814891490149114921493149414951496149714981499150015011502150315041505150615071508150915101511151215131514151515161517151815191520152115221523152415251526152715281529153015311532153315341535153615371538153915401541154215431544154515461547154815491550155115521553155415551556155715581559156015611562156315641565156615671568156915701571157215731574157515761577157815791580158115821583158415851586158715881589159015911592159315941595159615971598159916001601160216031604160516061607160816091610161116121613161416151616161716181619162016211622162316241625162616271628162916301631163216331634163516361637163816391640164116421643164416451646164716481649165016511652165316541655165616571658165916601661166216631664166516661667166816691670167116721673167416751676167716781679168016811682168316841685168616871688168916901691169216931694169516961697169816991700
  1. /*
  2. * Copyright (c) 2021, Itamar S. <itamar8910@gmail.com>
  3. *
  4. * SPDX-License-Identifier: BSD-2-Clause
  5. */
  6. #include "Parser.h"
  7. #include "AST.h"
  8. #include <AK/Debug.h>
  9. #include <AK/ScopeGuard.h>
  10. #include <AK/ScopeLogger.h>
  11. #include <LibCpp/Lexer.h>
  12. #define LOG_SCOPE() ScopeLogger<CPP_DEBUG> logger(String::formatted("'{}' - {} ({})", peek().text(), peek().type_as_string(), m_state.token_index))
  13. namespace Cpp {
  14. Parser::Parser(Vector<Token> tokens, String const& filename)
  15. : m_filename(filename)
  16. , m_tokens(move(tokens))
  17. {
  18. if constexpr (CPP_DEBUG) {
  19. dbgln("Tokens:");
  20. for (size_t i = 0; i < m_tokens.size(); ++i) {
  21. dbgln("{}- {}", i, m_tokens[i].to_string());
  22. }
  23. }
  24. }
  25. NonnullRefPtr<TranslationUnit> Parser::parse()
  26. {
  27. LOG_SCOPE();
  28. if (m_tokens.is_empty())
  29. return create_root_ast_node({}, {});
  30. auto unit = create_root_ast_node(m_tokens.first().start(), m_tokens.last().end());
  31. unit->set_declarations(parse_declarations_in_translation_unit(*unit));
  32. return unit;
  33. }
  34. NonnullRefPtrVector<Declaration> Parser::parse_declarations_in_translation_unit(ASTNode& parent)
  35. {
  36. NonnullRefPtrVector<Declaration> declarations;
  37. while (!eof()) {
  38. auto declaration = parse_single_declaration_in_translation_unit(parent);
  39. if (declaration) {
  40. declarations.append(declaration.release_nonnull());
  41. } else {
  42. error("unexpected token");
  43. consume();
  44. }
  45. }
  46. return declarations;
  47. }
  48. RefPtr<Declaration> Parser::parse_single_declaration_in_translation_unit(ASTNode& parent)
  49. {
  50. while (!eof()) {
  51. if (match_comment()) {
  52. consume(Token::Type::Comment);
  53. continue;
  54. }
  55. if (match_preprocessor()) {
  56. consume_preprocessor();
  57. continue;
  58. }
  59. auto declaration = match_declaration_in_translation_unit();
  60. if (declaration.has_value()) {
  61. return parse_declaration(parent, declaration.value());
  62. }
  63. return {};
  64. }
  65. return {};
  66. }
  67. NonnullRefPtr<Declaration> Parser::parse_declaration(ASTNode& parent, DeclarationType declaration_type)
  68. {
  69. switch (declaration_type) {
  70. case DeclarationType::Function:
  71. return parse_function_declaration(parent);
  72. case DeclarationType::Variable:
  73. return parse_variable_declaration(parent);
  74. case DeclarationType::Enum:
  75. return parse_enum_declaration(parent);
  76. case DeclarationType::Class:
  77. return parse_class_declaration(parent);
  78. case DeclarationType::Namespace:
  79. return parse_namespace_declaration(parent);
  80. case DeclarationType::Constructor:
  81. return parse_constructor(parent);
  82. case DeclarationType::Destructor:
  83. return parse_destructor(parent);
  84. default:
  85. error("unexpected declaration type");
  86. return create_ast_node<InvalidDeclaration>(parent, position(), position());
  87. }
  88. }
  89. NonnullRefPtr<FunctionDeclaration> Parser::parse_function_declaration(ASTNode& parent)
  90. {
  91. auto func = create_ast_node<FunctionDeclaration>(parent, position(), {});
  92. func->set_qualifiers(parse_function_qualifiers());
  93. func->set_return_type(parse_type(*func));
  94. auto function_name = consume(Token::Type::Identifier);
  95. func->set_name(text_of_token(function_name));
  96. consume(Token::Type::LeftParen);
  97. auto parameters = parse_parameter_list(*func);
  98. if (parameters.has_value())
  99. func->set_parameters(parameters.value());
  100. consume(Token::Type::RightParen);
  101. while (match_keyword("const") || match_keyword("override")) {
  102. consume();
  103. // FIXME: Note that this function is supposed to be a class member, and `this` has to be const, somehow.
  104. }
  105. RefPtr<FunctionDefinition> body;
  106. Position func_end {};
  107. if (peek(Token::Type::LeftCurly).has_value()) {
  108. body = parse_function_definition(*func);
  109. func_end = body->end();
  110. } else {
  111. func_end = position();
  112. if (match_attribute_specification())
  113. consume_attribute_specification(); // we don't use the value of __attribute__
  114. consume(Token::Type::Semicolon);
  115. }
  116. func->set_definition(move(body));
  117. func->set_end(func_end);
  118. return func;
  119. }
  120. NonnullRefPtr<FunctionDefinition> Parser::parse_function_definition(ASTNode& parent)
  121. {
  122. LOG_SCOPE();
  123. auto func = create_ast_node<FunctionDefinition>(parent, position(), {});
  124. consume(Token::Type::LeftCurly);
  125. while (!eof() && peek().type() != Token::Type::RightCurly) {
  126. func->add_statement(parse_statement(func));
  127. }
  128. func->set_end(position());
  129. if (!eof())
  130. consume(Token::Type::RightCurly);
  131. return func;
  132. }
  133. NonnullRefPtr<Statement> Parser::parse_statement(ASTNode& parent)
  134. {
  135. LOG_SCOPE();
  136. ArmedScopeGuard consume_semicolon([this]() {
  137. consume(Token::Type::Semicolon);
  138. });
  139. if (match_block_statement()) {
  140. consume_semicolon.disarm();
  141. return parse_block_statement(parent);
  142. }
  143. if (match_comment()) {
  144. consume_semicolon.disarm();
  145. return parse_comment(parent);
  146. }
  147. if (match_variable_declaration()) {
  148. return parse_variable_declaration(parent, false);
  149. }
  150. if (match_expression()) {
  151. return parse_expression(parent);
  152. }
  153. if (match_keyword("return")) {
  154. return parse_return_statement(parent);
  155. }
  156. if (match_keyword("for")) {
  157. consume_semicolon.disarm();
  158. return parse_for_statement(parent);
  159. }
  160. if (match_keyword("if")) {
  161. consume_semicolon.disarm();
  162. return parse_if_statement(parent);
  163. } else {
  164. error("unexpected statement type");
  165. consume_semicolon.disarm();
  166. consume();
  167. return create_ast_node<InvalidStatement>(parent, position(), position());
  168. }
  169. }
  170. NonnullRefPtr<Comment> Parser::parse_comment(ASTNode& parent)
  171. {
  172. auto comment = create_ast_node<Comment>(parent, position(), {});
  173. consume(Token::Type::Comment);
  174. comment->set_end(position());
  175. return comment;
  176. }
  177. bool Parser::match_block_statement()
  178. {
  179. return peek().type() == Token::Type::LeftCurly;
  180. }
  181. NonnullRefPtr<BlockStatement> Parser::parse_block_statement(ASTNode& parent)
  182. {
  183. LOG_SCOPE();
  184. auto block_statement = create_ast_node<BlockStatement>(parent, position(), {});
  185. consume(Token::Type::LeftCurly);
  186. while (!eof() && peek().type() != Token::Type::RightCurly) {
  187. block_statement->add_statement(parse_statement(*block_statement));
  188. }
  189. consume(Token::Type::RightCurly);
  190. block_statement->set_end(position());
  191. return block_statement;
  192. }
  193. bool Parser::match_type()
  194. {
  195. return match_named_type();
  196. }
  197. bool Parser::match_named_type()
  198. {
  199. save_state();
  200. ScopeGuard state_guard = [this] { load_state(); };
  201. parse_type_qualifiers();
  202. if (match_keyword("auto")) {
  203. return true;
  204. }
  205. if (match_keyword("struct")) {
  206. consume(Token::Type::Keyword); // Consume struct prefix
  207. }
  208. if (!match_name())
  209. return false;
  210. return true;
  211. }
  212. bool Parser::match_template_arguments()
  213. {
  214. save_state();
  215. ScopeGuard state_guard = [this] { load_state(); };
  216. if (!peek(Token::Type::Less).has_value())
  217. return false;
  218. consume();
  219. while (!eof() && peek().type() != Token::Type::Greater) {
  220. if (!match_named_type())
  221. return false;
  222. parse_type(get_dummy_node());
  223. }
  224. return peek().type() == Token::Type::Greater;
  225. }
  226. NonnullRefPtrVector<Type> Parser::parse_template_arguments(ASTNode& parent)
  227. {
  228. LOG_SCOPE();
  229. consume(Token::Type::Less);
  230. NonnullRefPtrVector<Type> template_arguments;
  231. while (!eof() && peek().type() != Token::Type::Greater) {
  232. template_arguments.append(parse_type(parent));
  233. }
  234. consume(Token::Type::Greater);
  235. return template_arguments;
  236. }
  237. bool Parser::match_variable_declaration()
  238. {
  239. LOG_SCOPE();
  240. save_state();
  241. ScopeGuard state_guard = [this] { load_state(); };
  242. if (!match_type()) {
  243. return false;
  244. }
  245. VERIFY(m_root_node);
  246. parse_type(get_dummy_node());
  247. // Identifier
  248. if (!match_name())
  249. return false;
  250. parse_name(get_dummy_node());
  251. if (match(Token::Type::Equals)) {
  252. consume(Token::Type::Equals);
  253. if (!match_expression()) {
  254. error("initial value of variable is not an expression");
  255. return false;
  256. }
  257. return true;
  258. }
  259. if (match_braced_init_list())
  260. parse_braced_init_list(get_dummy_node());
  261. return match(Token::Type::Semicolon);
  262. }
  263. NonnullRefPtr<VariableDeclaration> Parser::parse_variable_declaration(ASTNode& parent, bool expect_semicolon)
  264. {
  265. LOG_SCOPE();
  266. auto var = create_ast_node<VariableDeclaration>(parent, position(), {});
  267. if (!match_variable_declaration()) {
  268. error("unexpected token for variable type");
  269. var->set_end(position());
  270. return var;
  271. }
  272. var->set_type(parse_type(var));
  273. auto identifier_token = consume(Token::Type::Identifier);
  274. RefPtr<Expression> initial_value;
  275. if (match(Token::Type::Equals)) {
  276. consume(Token::Type::Equals);
  277. initial_value = parse_expression(var);
  278. }
  279. if (match_braced_init_list()) {
  280. initial_value = parse_braced_init_list(var);
  281. }
  282. if (expect_semicolon)
  283. consume(Token::Type::Semicolon);
  284. var->set_end(position());
  285. var->set_name(text_of_token(identifier_token));
  286. var->set_initial_value(move(initial_value));
  287. return var;
  288. }
  289. NonnullRefPtr<Expression> Parser::parse_expression(ASTNode& parent)
  290. {
  291. LOG_SCOPE();
  292. auto expression = parse_primary_expression(parent);
  293. // TODO: remove eof() logic, should still work without it
  294. if (eof() || match(Token::Type::Semicolon)) {
  295. return expression;
  296. }
  297. NonnullRefPtrVector<Expression> secondary_expressions;
  298. while (match_secondary_expression()) {
  299. // FIXME: Handle operator precedence
  300. expression = parse_secondary_expression(parent, expression);
  301. secondary_expressions.append(expression);
  302. }
  303. for (size_t i = 0; secondary_expressions.size() != 0 && i < secondary_expressions.size() - 1; ++i) {
  304. secondary_expressions[i].set_parent(secondary_expressions[i + 1]);
  305. }
  306. return expression;
  307. }
  308. bool Parser::match_secondary_expression()
  309. {
  310. auto type = peek().type();
  311. return type == Token::Type::Plus
  312. || type == Token::Type::PlusEquals
  313. || type == Token::Type::Minus
  314. || type == Token::Type::MinusEquals
  315. || type == Token::Type::Asterisk
  316. || type == Token::Type::AsteriskEquals
  317. || type == Token::Type::Percent
  318. || type == Token::Type::PercentEquals
  319. || type == Token::Type::Equals
  320. || type == Token::Type::Greater
  321. || type == Token::Type::Greater
  322. || type == Token::Type::Less
  323. || type == Token::Type::LessEquals
  324. || type == Token::Type::Dot
  325. || type == Token::Type::PlusPlus
  326. || type == Token::Type::MinusMinus
  327. || type == Token::Type::And
  328. || type == Token::Type::AndEquals
  329. || type == Token::Type::Pipe
  330. || type == Token::Type::PipeEquals
  331. || type == Token::Type::Caret
  332. || type == Token::Type::CaretEquals
  333. || type == Token::Type::LessLess
  334. || type == Token::Type::LessLessEquals
  335. || type == Token::Type::GreaterGreater
  336. || type == Token::Type::GreaterGreaterEquals
  337. || type == Token::Type::EqualsEquals
  338. || type == Token::Type::AndAnd
  339. || type == Token::Type::PipePipe
  340. || type == Token::Type::ExclamationMarkEquals
  341. || type == Token::Type::PipePipe
  342. || type == Token::Type::Arrow
  343. || type == Token::Type::LeftParen;
  344. }
  345. NonnullRefPtr<Expression> Parser::parse_primary_expression(ASTNode& parent)
  346. {
  347. LOG_SCOPE();
  348. // TODO: remove eof() logic, should still work without it
  349. if (eof()) {
  350. auto node = create_ast_node<Identifier>(parent, position(), position());
  351. return node;
  352. }
  353. if (match_unary_expression())
  354. return parse_unary_expression(parent);
  355. if (match_literal()) {
  356. return parse_literal(parent);
  357. }
  358. if (match_cpp_cast_expression())
  359. return parse_cpp_cast_expression(parent);
  360. if (match_c_style_cast_expression())
  361. return parse_c_style_cast_expression(parent);
  362. if (match_sizeof_expression())
  363. return parse_sizeof_expression(parent);
  364. if (match_braced_init_list())
  365. return parse_braced_init_list(parent);
  366. if (match_name()) {
  367. return parse_name(parent);
  368. }
  369. error("could not parse primary expression");
  370. auto token = consume();
  371. return create_ast_node<InvalidExpression>(parent, token.start(), token.end());
  372. }
  373. bool Parser::match_literal()
  374. {
  375. switch (peek().type()) {
  376. case Token::Type::Integer:
  377. return true;
  378. case Token::Type::SingleQuotedString:
  379. return true;
  380. case Token::Type::DoubleQuotedString:
  381. return true;
  382. case Token::Type::Float:
  383. return true;
  384. case Token::Type::Keyword: {
  385. return match_boolean_literal() || peek().text() == "nullptr";
  386. }
  387. default:
  388. return false;
  389. }
  390. }
  391. bool Parser::match_unary_expression()
  392. {
  393. auto type = peek().type();
  394. return type == Token::Type::PlusPlus
  395. || type == Token::Type::MinusMinus
  396. || type == Token::Type::ExclamationMark
  397. || type == Token::Type::Tilde
  398. || type == Token::Type::Plus
  399. || type == Token::Type::Minus
  400. || type == Token::Type::And;
  401. }
  402. NonnullRefPtr<UnaryExpression> Parser::parse_unary_expression(ASTNode& parent)
  403. {
  404. auto unary_exp = create_ast_node<UnaryExpression>(parent, position(), {});
  405. auto op_token = consume();
  406. UnaryOp op { UnaryOp::Invalid };
  407. switch (op_token.type()) {
  408. case Token::Type::Minus:
  409. op = UnaryOp::Minus;
  410. break;
  411. case Token::Type::Plus:
  412. op = UnaryOp::Plus;
  413. break;
  414. case Token::Type::ExclamationMark:
  415. op = UnaryOp::Not;
  416. break;
  417. case Token::Type::Tilde:
  418. op = UnaryOp::BitwiseNot;
  419. break;
  420. case Token::Type::PlusPlus:
  421. op = UnaryOp::PlusPlus;
  422. break;
  423. case Token::Type::And:
  424. op = UnaryOp::Address;
  425. break;
  426. default:
  427. break;
  428. }
  429. unary_exp->set_op(op);
  430. auto lhs = parse_expression(*unary_exp);
  431. unary_exp->set_lhs(lhs);
  432. unary_exp->set_end(lhs->end());
  433. return unary_exp;
  434. }
  435. NonnullRefPtr<Expression> Parser::parse_literal(ASTNode& parent)
  436. {
  437. switch (peek().type()) {
  438. case Token::Type::Integer: {
  439. auto token = consume();
  440. return create_ast_node<NumericLiteral>(parent, token.start(), token.end(), text_of_token(token));
  441. }
  442. case Token::Type::SingleQuotedString:
  443. [[fallthrough]];
  444. case Token::Type::DoubleQuotedString:
  445. return parse_string_literal(parent);
  446. case Token::Type::Keyword: {
  447. if (match_boolean_literal())
  448. return parse_boolean_literal(parent);
  449. if (peek().text() == "nullptr") {
  450. auto token = consume();
  451. return create_ast_node<NullPointerLiteral>(parent, token.start(), token.end());
  452. }
  453. [[fallthrough]];
  454. }
  455. default: {
  456. error("could not parse literal");
  457. auto token = consume();
  458. return create_ast_node<InvalidExpression>(parent, token.start(), token.end());
  459. }
  460. }
  461. }
  462. NonnullRefPtr<Expression> Parser::parse_secondary_expression(ASTNode& parent, NonnullRefPtr<Expression> lhs)
  463. {
  464. LOG_SCOPE();
  465. switch (peek().type()) {
  466. case Token::Type::Plus:
  467. return parse_binary_expression(parent, lhs, BinaryOp::Addition);
  468. case Token::Type::Less:
  469. return parse_binary_expression(parent, lhs, BinaryOp::LessThan);
  470. case Token::Type::EqualsEquals:
  471. return parse_binary_expression(parent, lhs, BinaryOp::EqualsEquals);
  472. case Token::Type::ExclamationMarkEquals:
  473. return parse_binary_expression(parent, lhs, BinaryOp::NotEqual);
  474. case Token::Type::And:
  475. return parse_binary_expression(parent, lhs, BinaryOp::BitwiseAnd);
  476. case Token::Type::AndAnd:
  477. return parse_binary_expression(parent, lhs, BinaryOp::LogicalAnd);
  478. case Token::Type::Pipe:
  479. return parse_binary_expression(parent, lhs, BinaryOp::BitwiseOr);
  480. case Token::Type::PipePipe:
  481. return parse_binary_expression(parent, lhs, BinaryOp::LogicalOr);
  482. case Token::Type::Arrow:
  483. return parse_binary_expression(parent, lhs, BinaryOp::Arrow);
  484. case Token::Type::Equals:
  485. return parse_assignment_expression(parent, lhs, AssignmentOp::Assignment);
  486. case Token::Type::Dot: {
  487. consume();
  488. auto exp = create_ast_node<MemberExpression>(parent, lhs->start(), {});
  489. lhs->set_parent(*exp);
  490. exp->set_object(move(lhs));
  491. auto identifier_token = consume(Token::Type::Identifier);
  492. exp->set_property(create_ast_node<Identifier>(*exp, identifier_token.start(), identifier_token.end(), identifier_token.text()));
  493. exp->set_end(position());
  494. return exp;
  495. }
  496. case Token::Type::LeftParen: {
  497. consume();
  498. auto func = create_ast_node<FunctionCall>(parent, lhs->start(), {});
  499. lhs->set_parent(*func);
  500. func->set_callee(move(lhs));
  501. while (peek().type() != Token::Type::RightParen && !eof()) {
  502. func->add_argument(parse_expression(*func));
  503. if (peek().type() == Token::Type::Comma)
  504. consume(Token::Type::Comma);
  505. }
  506. consume(Token::Type::RightParen);
  507. func->set_end(position());
  508. return func;
  509. }
  510. default: {
  511. error(String::formatted("unexpected operator for expression. operator: {}", peek().to_string()));
  512. auto token = consume();
  513. return create_ast_node<InvalidExpression>(parent, token.start(), token.end());
  514. }
  515. }
  516. }
  517. NonnullRefPtr<BinaryExpression> Parser::parse_binary_expression(ASTNode& parent, NonnullRefPtr<Expression> lhs, BinaryOp op)
  518. {
  519. consume(); // Operator
  520. auto exp = create_ast_node<BinaryExpression>(parent, lhs->start(), {});
  521. lhs->set_parent(*exp);
  522. exp->set_op(op);
  523. exp->set_lhs(move(lhs));
  524. auto rhs = parse_expression(exp);
  525. exp->set_end(rhs->end());
  526. exp->set_rhs(move(rhs));
  527. return exp;
  528. }
  529. NonnullRefPtr<AssignmentExpression> Parser::parse_assignment_expression(ASTNode& parent, NonnullRefPtr<Expression> lhs, AssignmentOp op)
  530. {
  531. consume(); // Operator
  532. auto exp = create_ast_node<AssignmentExpression>(parent, lhs->start(), {});
  533. lhs->set_parent(*exp);
  534. exp->set_op(op);
  535. exp->set_lhs(move(lhs));
  536. auto rhs = parse_expression(exp);
  537. exp->set_end(rhs->end());
  538. exp->set_rhs(move(rhs));
  539. return exp;
  540. }
  541. Optional<Parser::DeclarationType> Parser::match_declaration_in_translation_unit()
  542. {
  543. if (match_function_declaration())
  544. return DeclarationType::Function;
  545. if (match_enum_declaration())
  546. return DeclarationType::Enum;
  547. if (match_class_declaration())
  548. return DeclarationType::Class;
  549. if (match_namespace_declaration())
  550. return DeclarationType::Namespace;
  551. if (match_variable_declaration())
  552. return DeclarationType::Variable;
  553. return {};
  554. }
  555. Optional<Parser::DeclarationType> Parser::match_class_member(const StringView& class_name)
  556. {
  557. if (match_function_declaration())
  558. return DeclarationType::Function;
  559. if (match_enum_declaration())
  560. return DeclarationType::Enum;
  561. if (match_class_declaration())
  562. return DeclarationType::Class;
  563. if (match_variable_declaration())
  564. return DeclarationType::Variable;
  565. if (match_constructor(class_name))
  566. return DeclarationType::Constructor;
  567. if (match_destructor(class_name))
  568. return DeclarationType::Destructor;
  569. return {};
  570. }
  571. bool Parser::match_enum_declaration()
  572. {
  573. save_state();
  574. ScopeGuard state_guard = [this] { load_state(); };
  575. if (!match_keyword("enum"))
  576. return false;
  577. consume(Token::Type::Keyword);
  578. if (match_keyword("class"))
  579. consume(Token::Type::Keyword);
  580. if (!match(Token::Type::Identifier))
  581. return false;
  582. consume(Token::Type::Identifier);
  583. return match(Token::Type::LeftCurly);
  584. }
  585. bool Parser::match_class_declaration()
  586. {
  587. save_state();
  588. ScopeGuard state_guard = [this] { load_state(); };
  589. if (!match_keyword("struct") && !match_keyword("class"))
  590. return false;
  591. consume(Token::Type::Keyword);
  592. if (!match(Token::Type::Identifier))
  593. return false;
  594. consume(Token::Type::Identifier);
  595. auto has_final = match_keyword("final");
  596. if (peek(has_final ? 1 : 0).type() == Token::Type::Colon) {
  597. if (has_final)
  598. consume();
  599. do {
  600. consume();
  601. while (match_keyword("private") || match_keyword("public") || match_keyword("protected") || match_keyword("virtual"))
  602. consume();
  603. if (!match_name())
  604. return false;
  605. parse_name(get_dummy_node());
  606. } while (peek().type() == Token::Type::Comma);
  607. }
  608. return match(Token::Type::LeftCurly);
  609. }
  610. bool Parser::match_namespace_declaration()
  611. {
  612. return match_keyword("namespace");
  613. }
  614. bool Parser::match_function_declaration()
  615. {
  616. save_state();
  617. ScopeGuard state_guard = [this] { load_state(); };
  618. parse_function_qualifiers();
  619. if (!match_type())
  620. return false;
  621. VERIFY(m_root_node);
  622. parse_type(get_dummy_node());
  623. if (!peek(Token::Type::Identifier).has_value())
  624. return false;
  625. consume();
  626. if (!peek(Token::Type::LeftParen).has_value())
  627. return false;
  628. consume();
  629. while (consume().type() != Token::Type::RightParen && !eof()) { };
  630. while (match_keyword("const") || match_keyword("override"))
  631. consume();
  632. if (peek(Token::Type::Semicolon).has_value() || peek(Token::Type::LeftCurly).has_value())
  633. return true;
  634. if (match_attribute_specification()) {
  635. consume_attribute_specification();
  636. return peek(Token::Type::Semicolon).has_value();
  637. }
  638. return false;
  639. }
  640. Optional<NonnullRefPtrVector<Parameter>> Parser::parse_parameter_list(ASTNode& parent)
  641. {
  642. LOG_SCOPE();
  643. NonnullRefPtrVector<Parameter> parameters;
  644. while (peek().type() != Token::Type::RightParen && !eof()) {
  645. if (match_ellipsis()) {
  646. auto param = create_ast_node<Parameter>(parent, position(), {}, StringView {});
  647. consume(Token::Type::Dot);
  648. consume(Token::Type::Dot);
  649. auto last_dot = consume(Token::Type::Dot);
  650. param->set_ellipsis(true);
  651. param->set_end(last_dot.end());
  652. parameters.append(move(param));
  653. } else {
  654. auto type = parse_type(parent);
  655. auto name_identifier = peek(Token::Type::Identifier);
  656. if (name_identifier.has_value())
  657. consume(Token::Type::Identifier);
  658. StringView name;
  659. if (name_identifier.has_value())
  660. name = text_of_token(name_identifier.value());
  661. auto param = create_ast_node<Parameter>(parent, type->start(), name_identifier.has_value() ? name_identifier.value().end() : type->end(), name);
  662. param->set_type(move(type));
  663. parameters.append(move(param));
  664. }
  665. if (peek(Token::Type::Comma).has_value())
  666. consume(Token::Type::Comma);
  667. }
  668. return parameters;
  669. }
  670. bool Parser::match_comment()
  671. {
  672. return match(Token::Type::Comment);
  673. }
  674. bool Parser::match_whitespace()
  675. {
  676. return match(Token::Type::Whitespace);
  677. }
  678. bool Parser::match_preprocessor()
  679. {
  680. return match(Token::Type::PreprocessorStatement) || match(Token::Type::IncludeStatement);
  681. }
  682. void Parser::consume_preprocessor()
  683. {
  684. LOG_SCOPE();
  685. switch (peek().type()) {
  686. case Token::Type::PreprocessorStatement:
  687. consume();
  688. break;
  689. case Token::Type::IncludeStatement:
  690. consume();
  691. consume(Token::Type::IncludePath);
  692. break;
  693. default:
  694. error("unexpected token while parsing preprocessor statement");
  695. consume();
  696. }
  697. }
  698. Optional<Token> Parser::consume_whitespace()
  699. {
  700. LOG_SCOPE();
  701. return consume(Token::Type::Whitespace);
  702. }
  703. Token Parser::consume(Token::Type type)
  704. {
  705. auto token = consume();
  706. if (token.type() != type)
  707. error(String::formatted("expected {} at {}:{}, found: {}", Token::type_to_string(type), token.start().line, token.start().column, Token::type_to_string(token.type())));
  708. return token;
  709. }
  710. bool Parser::match(Token::Type type)
  711. {
  712. return peek().type() == type;
  713. }
  714. Token Parser::consume()
  715. {
  716. if (eof()) {
  717. error("C++ Parser: out of tokens");
  718. return { Token::Type::EOF_TOKEN, position(), position(), {} };
  719. }
  720. return m_tokens[m_state.token_index++];
  721. }
  722. Token Parser::peek(size_t offset) const
  723. {
  724. if (m_state.token_index + offset >= m_tokens.size())
  725. return { Token::Type::EOF_TOKEN, position(), position(), {} };
  726. return m_tokens[m_state.token_index + offset];
  727. }
  728. Optional<Token> Parser::peek(Token::Type type) const
  729. {
  730. auto token = peek();
  731. if (token.type() == type)
  732. return token;
  733. return {};
  734. }
  735. void Parser::save_state()
  736. {
  737. m_saved_states.append(m_state);
  738. m_state.state_nodes.clear();
  739. }
  740. void Parser::load_state()
  741. {
  742. m_state = m_saved_states.take_last();
  743. }
  744. StringView Parser::text_of_token(const Cpp::Token& token) const
  745. {
  746. return token.text();
  747. }
  748. String Parser::text_of_node(const ASTNode& node) const
  749. {
  750. return text_in_range(node.start(), node.end());
  751. }
  752. String Parser::text_in_range(Position start, Position end) const
  753. {
  754. StringBuilder builder;
  755. for (auto token : tokens_in_range(start, end)) {
  756. builder.append(token.text());
  757. }
  758. return builder.to_string();
  759. }
  760. Vector<Token> Parser::tokens_in_range(Position start, Position end) const
  761. {
  762. auto start_token_index = index_of_token_at(start);
  763. auto end_node_index = index_of_token_at(end);
  764. VERIFY(start_token_index.has_value());
  765. VERIFY(end_node_index.has_value());
  766. Vector<Token> tokens;
  767. for (size_t i = start_token_index.value(); i <= end_node_index.value(); ++i) {
  768. tokens.append(m_tokens[i]);
  769. }
  770. return tokens;
  771. }
  772. void Parser::error(StringView message)
  773. {
  774. LOG_SCOPE();
  775. if (!m_saved_states.is_empty())
  776. return;
  777. if (message.is_null() || message.is_empty())
  778. message = "<empty>";
  779. String formatted_message;
  780. if (m_state.token_index >= m_tokens.size()) {
  781. formatted_message = String::formatted("C++ Parsed error on EOF.{}", message);
  782. } else {
  783. formatted_message = String::formatted("C++ Parser error: {}. token: {} ({}:{})",
  784. message,
  785. m_state.token_index < m_tokens.size() ? text_of_token(m_tokens[m_state.token_index]) : "EOF",
  786. m_tokens[m_state.token_index].start().line,
  787. m_tokens[m_state.token_index].start().column);
  788. }
  789. m_errors.append(formatted_message);
  790. }
  791. bool Parser::match_expression()
  792. {
  793. return match_literal()
  794. || match_name()
  795. || match_unary_expression()
  796. || match_cpp_cast_expression()
  797. || match_c_style_cast_expression()
  798. || match_sizeof_expression()
  799. || match_braced_init_list();
  800. }
  801. bool Parser::eof() const
  802. {
  803. return m_state.token_index >= m_tokens.size();
  804. }
  805. Position Parser::position() const
  806. {
  807. if (m_tokens.is_empty())
  808. return {};
  809. if (eof())
  810. return m_tokens.last().end();
  811. return peek().start();
  812. }
  813. RefPtr<ASTNode> Parser::node_at(Position pos) const
  814. {
  815. VERIFY(m_saved_states.is_empty());
  816. auto index = index_of_node_at(pos);
  817. if (!index.has_value())
  818. return nullptr;
  819. return m_nodes[index.value()];
  820. }
  821. Optional<size_t> Parser::index_of_node_at(Position pos) const
  822. {
  823. VERIFY(!m_tokens.is_empty());
  824. VERIFY(m_saved_states.is_empty());
  825. Optional<size_t> match_node_index;
  826. auto node_span = [](const ASTNode& node) {
  827. VERIFY(node.end().line >= node.start().line);
  828. VERIFY((node.end().line > node.start().line) || (node.end().column >= node.start().column));
  829. return Position { node.end().line - node.start().line, node.start().line != node.end().line ? 0 : node.end().column - node.start().column };
  830. };
  831. for (size_t node_index = 0; node_index < m_nodes.size(); ++node_index) {
  832. auto& node = m_nodes[node_index];
  833. if (node.start() > pos || node.end() < pos)
  834. continue;
  835. if (!match_node_index.has_value() || (node_span(node) <= node_span(m_nodes[match_node_index.value()])))
  836. match_node_index = node_index;
  837. }
  838. return match_node_index;
  839. }
  840. Optional<Token> Parser::token_at(Position pos) const
  841. {
  842. auto index = index_of_token_at(pos);
  843. if (!index.has_value())
  844. return {};
  845. return m_tokens[index.value()];
  846. }
  847. Optional<size_t> Parser::index_of_token_at(Position pos) const
  848. {
  849. for (size_t token_index = 0; token_index < m_tokens.size(); ++token_index) {
  850. auto token = m_tokens[token_index];
  851. if (token.start() > pos || token.end() < pos)
  852. continue;
  853. return token_index;
  854. }
  855. return {};
  856. }
  857. void Parser::print_tokens() const
  858. {
  859. for (auto& token : m_tokens) {
  860. outln("{}", token.to_string());
  861. }
  862. }
  863. Vector<Parser::TodoEntry> Parser::get_todo_entries() const
  864. {
  865. Vector<TodoEntry> ret;
  866. for (auto& token : m_tokens) {
  867. if (token.type() == Token::Type::Comment) {
  868. if (token.text().contains("TODO")) {
  869. ret.append({ token.text(), m_filename, token.start().line, token.start().column });
  870. }
  871. }
  872. }
  873. return ret;
  874. }
  875. NonnullRefPtr<StringLiteral> Parser::parse_string_literal(ASTNode& parent)
  876. {
  877. LOG_SCOPE();
  878. Optional<size_t> start_token_index;
  879. Optional<size_t> end_token_index;
  880. while (!eof()) {
  881. auto token = peek();
  882. if (token.type() != Token::Type::DoubleQuotedString && token.type() != Token::Type::SingleQuotedString && token.type() != Token::Type::EscapeSequence) {
  883. VERIFY(start_token_index.has_value());
  884. end_token_index = m_state.token_index - 1;
  885. break;
  886. }
  887. if (!start_token_index.has_value())
  888. start_token_index = m_state.token_index;
  889. consume();
  890. }
  891. // String was not terminated
  892. if (!end_token_index.has_value()) {
  893. end_token_index = m_tokens.size() - 1;
  894. }
  895. VERIFY(start_token_index.has_value());
  896. VERIFY(end_token_index.has_value());
  897. Token start_token = m_tokens[start_token_index.value()];
  898. Token end_token = m_tokens[end_token_index.value()];
  899. auto text = text_in_range(start_token.start(), end_token.end());
  900. auto string_literal = create_ast_node<StringLiteral>(parent, start_token.start(), end_token.end());
  901. string_literal->set_value(move(text));
  902. return string_literal;
  903. }
  904. NonnullRefPtr<ReturnStatement> Parser::parse_return_statement(ASTNode& parent)
  905. {
  906. LOG_SCOPE();
  907. auto return_statement = create_ast_node<ReturnStatement>(parent, position(), {});
  908. consume(Token::Type::Keyword);
  909. if (!peek(Token::Type::Semicolon).has_value()) {
  910. return_statement->set_value(parse_expression(*return_statement));
  911. }
  912. return_statement->set_end(position());
  913. return return_statement;
  914. }
  915. NonnullRefPtr<EnumDeclaration> Parser::parse_enum_declaration(ASTNode& parent)
  916. {
  917. LOG_SCOPE();
  918. auto enum_decl = create_ast_node<EnumDeclaration>(parent, position(), {});
  919. consume_keyword("enum");
  920. if (match_keyword("class")) {
  921. consume(Token::Type::Keyword);
  922. enum_decl->set_type(EnumDeclaration::Type::EnumClass);
  923. } else {
  924. enum_decl->set_type(EnumDeclaration::Type::RegularEnum);
  925. }
  926. auto name_token = consume(Token::Type::Identifier);
  927. enum_decl->set_name(text_of_token(name_token));
  928. consume(Token::Type::LeftCurly);
  929. while (!eof() && peek().type() != Token::Type::RightCurly) {
  930. auto name = text_of_token(consume(Token::Type::Identifier));
  931. RefPtr<Expression> value;
  932. if (peek().type() == Token::Type::Equals) {
  933. consume();
  934. value = parse_expression(enum_decl);
  935. }
  936. enum_decl->add_entry(name, move(value));
  937. if (peek().type() != Token::Type::Comma) {
  938. break;
  939. }
  940. consume(Token::Type::Comma);
  941. }
  942. consume(Token::Type::RightCurly);
  943. consume(Token::Type::Semicolon);
  944. enum_decl->set_end(position());
  945. return enum_decl;
  946. }
  947. Token Parser::consume_keyword(const String& keyword)
  948. {
  949. auto token = consume();
  950. if (token.type() != Token::Type::Keyword) {
  951. error(String::formatted("unexpected token: {}, expected Keyword", token.to_string()));
  952. return token;
  953. }
  954. if (text_of_token(token) != keyword) {
  955. error(String::formatted("unexpected keyword: {}, expected {}", text_of_token(token), keyword));
  956. return token;
  957. }
  958. return token;
  959. }
  960. bool Parser::match_keyword(const String& keyword)
  961. {
  962. auto token = peek();
  963. if (token.type() != Token::Type::Keyword) {
  964. return false;
  965. }
  966. if (text_of_token(token) != keyword) {
  967. return false;
  968. }
  969. return true;
  970. }
  971. NonnullRefPtr<StructOrClassDeclaration> Parser::parse_class_declaration(ASTNode& parent)
  972. {
  973. LOG_SCOPE();
  974. auto type_token = consume(Token::Type::Keyword);
  975. StructOrClassDeclaration::Type type {};
  976. if (type_token.text() == "struct")
  977. type = StructOrClassDeclaration::Type::Struct;
  978. if (type_token.text() == "class")
  979. type = StructOrClassDeclaration::Type::Class;
  980. auto decl = create_ast_node<StructOrClassDeclaration>(parent, position(), {}, type);
  981. auto name_token = consume(Token::Type::Identifier);
  982. decl->set_name(text_of_token(name_token));
  983. auto has_final = match_keyword("final");
  984. // FIXME: Don't ignore this.
  985. if (peek(has_final ? 1 : 0).type() == Token::Type::Colon) {
  986. if (has_final)
  987. consume();
  988. do {
  989. consume();
  990. while (match_keyword("private") || match_keyword("public") || match_keyword("protected") || match_keyword("virtual"))
  991. consume();
  992. parse_name(get_dummy_node());
  993. } while (peek().type() == Token::Type::Comma);
  994. }
  995. consume(Token::Type::LeftCurly);
  996. while (!eof() && peek().type() != Token::Type::RightCurly) {
  997. decl->set_members(parse_class_members(*decl));
  998. }
  999. consume(Token::Type::RightCurly);
  1000. consume(Token::Type::Semicolon);
  1001. decl->set_end(position());
  1002. return decl;
  1003. }
  1004. NonnullRefPtr<BooleanLiteral> Parser::parse_boolean_literal(ASTNode& parent)
  1005. {
  1006. LOG_SCOPE();
  1007. auto token = consume(Token::Type::Keyword);
  1008. auto text = text_of_token(token);
  1009. // text == "true" || text == "false";
  1010. bool value = (text == "true");
  1011. return create_ast_node<BooleanLiteral>(parent, token.start(), token.end(), value);
  1012. }
  1013. bool Parser::match_boolean_literal()
  1014. {
  1015. auto token = peek();
  1016. if (token.type() != Token::Type::Keyword)
  1017. return false;
  1018. auto text = text_of_token(token);
  1019. return text == "true" || text == "false";
  1020. }
  1021. NonnullRefPtr<Type> Parser::parse_type(ASTNode& parent)
  1022. {
  1023. LOG_SCOPE();
  1024. if (!match_named_type()) {
  1025. error("expected named named_type");
  1026. auto token = consume();
  1027. return create_ast_node<NamedType>(parent, token.start(), token.end());
  1028. }
  1029. auto named_type = create_ast_node<NamedType>(parent, position(), {});
  1030. auto qualifiers = parse_type_qualifiers();
  1031. named_type->set_qualifiers(move(qualifiers));
  1032. if (match_keyword("auto")) {
  1033. consume(Token::Type::Keyword);
  1034. named_type->set_auto(true);
  1035. auto original_qualifiers = named_type->qualifiers();
  1036. original_qualifiers.extend(parse_type_qualifiers());
  1037. named_type->set_qualifiers(move(original_qualifiers));
  1038. named_type->set_end(position());
  1039. return named_type;
  1040. }
  1041. if (match_keyword("struct")) {
  1042. consume(Token::Type::Keyword); // Consume struct prefix
  1043. }
  1044. if (!match_name()) {
  1045. named_type->set_end(position());
  1046. error(String::formatted("expected name instead of: {}", peek().text()));
  1047. return named_type;
  1048. }
  1049. named_type->set_name(parse_name(*named_type));
  1050. auto original_qualifiers = named_type->qualifiers();
  1051. original_qualifiers.extend(parse_type_qualifiers());
  1052. named_type->set_qualifiers(move(original_qualifiers));
  1053. NonnullRefPtr<Type> type = named_type;
  1054. while (!eof() && peek().type() == Token::Type::Asterisk) {
  1055. type->set_end(position());
  1056. auto asterisk = consume();
  1057. auto ptr = create_ast_node<Pointer>(parent, type->start(), asterisk.end());
  1058. type->set_parent(*ptr);
  1059. ptr->set_pointee(type);
  1060. ptr->set_qualifiers(parse_type_qualifiers());
  1061. ptr->set_end(position());
  1062. type = ptr;
  1063. }
  1064. if (!eof() && (peek().type() == Token::Type::And || peek().type() == Token::Type::AndAnd)) {
  1065. type->set_end(position());
  1066. auto ref_token = consume();
  1067. auto ref = create_ast_node<Reference>(parent, type->start(), ref_token.end(), ref_token.type() == Token::Type::And ? Reference::Kind::Lvalue : Reference::Kind::Rvalue);
  1068. type->set_parent(*ref);
  1069. ref->set_referenced_type(type);
  1070. ref->set_end(position());
  1071. type = ref;
  1072. }
  1073. if (peek().type() == Token::Type::LeftParen) {
  1074. consume();
  1075. auto fn_type = create_ast_node<FunctionType>(parent, type->start(), position());
  1076. fn_type->set_return_type(*type);
  1077. type->set_parent(*fn_type);
  1078. if (auto parameters = parse_parameter_list(*type); parameters.has_value())
  1079. fn_type->set_parameters(parameters.release_value());
  1080. consume(Token::Type::RightParen);
  1081. type = fn_type;
  1082. }
  1083. type->set_end(position());
  1084. return type;
  1085. }
  1086. NonnullRefPtr<ForStatement> Parser::parse_for_statement(ASTNode& parent)
  1087. {
  1088. LOG_SCOPE();
  1089. auto for_statement = create_ast_node<ForStatement>(parent, position(), {});
  1090. consume(Token::Type::Keyword);
  1091. consume(Token::Type::LeftParen);
  1092. if (peek().type() != Token::Type::Semicolon)
  1093. for_statement->set_init(parse_variable_declaration(*for_statement, false));
  1094. consume(Token::Type::Semicolon);
  1095. if (peek().type() != Token::Type::Semicolon)
  1096. for_statement->set_test(parse_expression(*for_statement));
  1097. consume(Token::Type::Semicolon);
  1098. if (peek().type() != Token::Type::RightParen)
  1099. for_statement->set_update(parse_expression(*for_statement));
  1100. consume(Token::Type::RightParen);
  1101. for_statement->set_body(parse_statement(*for_statement));
  1102. for_statement->set_end(for_statement->body()->end());
  1103. return for_statement;
  1104. }
  1105. NonnullRefPtr<IfStatement> Parser::parse_if_statement(ASTNode& parent)
  1106. {
  1107. LOG_SCOPE();
  1108. auto if_statement = create_ast_node<IfStatement>(parent, position(), {});
  1109. consume(Token::Type::Keyword);
  1110. consume(Token::Type::LeftParen);
  1111. if_statement->set_predicate(parse_expression(*if_statement));
  1112. consume(Token::Type::RightParen);
  1113. if_statement->set_then_statement(parse_statement(*if_statement));
  1114. if (match_keyword("else")) {
  1115. consume(Token::Type::Keyword);
  1116. if_statement->set_else_statement(parse_statement(*if_statement));
  1117. if_statement->set_end(if_statement->else_statement()->end());
  1118. } else {
  1119. if_statement->set_end(if_statement->then_statement()->end());
  1120. }
  1121. return if_statement;
  1122. }
  1123. Vector<StringView> Parser::parse_type_qualifiers()
  1124. {
  1125. LOG_SCOPE();
  1126. Vector<StringView> qualifiers;
  1127. while (!eof()) {
  1128. auto token = peek();
  1129. if (token.type() != Token::Type::Keyword)
  1130. break;
  1131. auto text = text_of_token(token);
  1132. if (text == "static" || text == "const" || text == "extern") {
  1133. qualifiers.append(text);
  1134. consume();
  1135. } else {
  1136. break;
  1137. }
  1138. }
  1139. return qualifiers;
  1140. }
  1141. Vector<StringView> Parser::parse_function_qualifiers()
  1142. {
  1143. LOG_SCOPE();
  1144. Vector<StringView> qualifiers;
  1145. while (!eof()) {
  1146. auto token = peek();
  1147. if (token.type() != Token::Type::Keyword)
  1148. break;
  1149. auto text = text_of_token(token);
  1150. if (text == "static" || text == "inline" || text == "extern" || text == "virtual") {
  1151. qualifiers.append(text);
  1152. consume();
  1153. } else {
  1154. break;
  1155. }
  1156. }
  1157. return qualifiers;
  1158. }
  1159. bool Parser::match_attribute_specification()
  1160. {
  1161. return text_of_token(peek()) == "__attribute__";
  1162. }
  1163. void Parser::consume_attribute_specification()
  1164. {
  1165. consume(); // __attribute__
  1166. consume(Token::Type::LeftParen);
  1167. size_t left_count = 1;
  1168. while (!eof()) {
  1169. auto token = consume();
  1170. if (token.type() == Token::Type::LeftParen) {
  1171. ++left_count;
  1172. }
  1173. if (token.type() == Token::Type::RightParen) {
  1174. --left_count;
  1175. }
  1176. if (left_count == 0)
  1177. return;
  1178. }
  1179. }
  1180. bool Parser::match_ellipsis()
  1181. {
  1182. if (m_state.token_index > m_tokens.size() - 3)
  1183. return false;
  1184. return peek().type() == Token::Type::Dot && peek(1).type() == Token::Type::Dot && peek(2).type() == Token::Type::Dot;
  1185. }
  1186. NonnullRefPtr<NamespaceDeclaration> Parser::parse_namespace_declaration(ASTNode& parent, bool is_nested_namespace)
  1187. {
  1188. auto namespace_decl = create_ast_node<NamespaceDeclaration>(parent, position(), {});
  1189. if (!is_nested_namespace)
  1190. consume(Token::Type::Keyword);
  1191. auto name_token = consume(Token::Type::Identifier);
  1192. namespace_decl->set_name(name_token.text());
  1193. if (peek().type() == Token::Type::ColonColon) {
  1194. consume(Token::Type::ColonColon);
  1195. namespace_decl->add_declaration(parse_namespace_declaration(*namespace_decl, true));
  1196. namespace_decl->set_end(position());
  1197. return namespace_decl;
  1198. }
  1199. consume(Token::Type::LeftCurly);
  1200. while (!eof() && peek().type() != Token::Type::RightCurly) {
  1201. auto declaration = parse_single_declaration_in_translation_unit(*namespace_decl);
  1202. if (declaration) {
  1203. namespace_decl->add_declaration(declaration.release_nonnull());
  1204. } else {
  1205. error("unexpected token");
  1206. consume();
  1207. }
  1208. }
  1209. consume(Token::Type::RightCurly);
  1210. namespace_decl->set_end(position());
  1211. return namespace_decl;
  1212. }
  1213. bool Parser::match_name()
  1214. {
  1215. auto type = peek().type();
  1216. return type == Token::Type::Identifier || type == Token::Type::KnownType;
  1217. }
  1218. NonnullRefPtr<Name> Parser::parse_name(ASTNode& parent)
  1219. {
  1220. LOG_SCOPE();
  1221. NonnullRefPtr<Name> name_node = create_ast_node<Name>(parent, position(), {});
  1222. while (!eof() && (peek().type() == Token::Type::Identifier || peek().type() == Token::Type::KnownType) && peek(1).type() == Token::Type::ColonColon) {
  1223. auto token = consume();
  1224. name_node->add_to_scope(create_ast_node<Identifier>(*name_node, token.start(), token.end(), token.text()));
  1225. consume(Token::Type::ColonColon);
  1226. }
  1227. if (peek().type() == Token::Type::Identifier || peek().type() == Token::Type::KnownType) {
  1228. auto token = consume();
  1229. name_node->set_name(create_ast_node<Identifier>(*name_node, token.start(), token.end(), token.text()));
  1230. } else {
  1231. name_node->set_end(position());
  1232. return name_node;
  1233. }
  1234. if (match_template_arguments()) {
  1235. consume(Token::Type::Less);
  1236. NonnullRefPtr<TemplatizedName> templatized_name = create_ast_node<TemplatizedName>(parent, name_node->start(), {});
  1237. templatized_name->set_name(name_node->name());
  1238. templatized_name->set_scope(name_node->scope());
  1239. name_node->set_end(position());
  1240. name_node = templatized_name;
  1241. while (peek().type() != Token::Type::Greater && !eof()) {
  1242. templatized_name->add_template_argument(parse_type(*templatized_name));
  1243. if (peek().type() == Token::Type::Comma)
  1244. consume(Token::Type::Comma);
  1245. }
  1246. consume(Token::Type::Greater);
  1247. }
  1248. name_node->set_end(position());
  1249. return name_node;
  1250. }
  1251. bool Parser::match_cpp_cast_expression()
  1252. {
  1253. save_state();
  1254. ScopeGuard state_guard = [this] { load_state(); };
  1255. auto token = consume();
  1256. if (token.type() != Token::Type::Keyword)
  1257. return false;
  1258. auto text = token.text();
  1259. if (text == "static_cast" || text == "reinterpret_cast" || text == "dynamic_cast" || text == "const_cast")
  1260. return true;
  1261. return false;
  1262. }
  1263. bool Parser::match_c_style_cast_expression()
  1264. {
  1265. save_state();
  1266. ScopeGuard state_guard = [this] { load_state(); };
  1267. if (consume().type() != Token::Type::LeftParen)
  1268. return false;
  1269. if (!match_type())
  1270. return false;
  1271. parse_type(get_dummy_node());
  1272. if (consume().type() != Token::Type::RightParen)
  1273. return false;
  1274. if (!match_expression())
  1275. return false;
  1276. return true;
  1277. }
  1278. NonnullRefPtr<CStyleCastExpression> Parser::parse_c_style_cast_expression(ASTNode& parent)
  1279. {
  1280. auto parse_exp = create_ast_node<CStyleCastExpression>(parent, position(), {});
  1281. consume(Token::Type::LeftParen);
  1282. parse_exp->set_type(parse_type(*parse_exp));
  1283. consume(Token::Type::RightParen);
  1284. parse_exp->set_expression(parse_expression(*parse_exp));
  1285. parse_exp->set_end(position());
  1286. return parse_exp;
  1287. }
  1288. NonnullRefPtr<CppCastExpression> Parser::parse_cpp_cast_expression(ASTNode& parent)
  1289. {
  1290. auto cast_expression = create_ast_node<CppCastExpression>(parent, position(), {});
  1291. cast_expression->set_cast_type(consume(Token::Type::Keyword).text());
  1292. consume(Token::Type::Less);
  1293. cast_expression->set_type(parse_type(*cast_expression));
  1294. consume(Token::Type::Greater);
  1295. consume(Token::Type::LeftParen);
  1296. cast_expression->set_expression(parse_expression(*cast_expression));
  1297. consume(Token::Type::RightParen);
  1298. cast_expression->set_end(position());
  1299. return cast_expression;
  1300. }
  1301. bool Parser::match_sizeof_expression()
  1302. {
  1303. return match_keyword("sizeof");
  1304. }
  1305. NonnullRefPtr<SizeofExpression> Parser::parse_sizeof_expression(ASTNode& parent)
  1306. {
  1307. auto exp = create_ast_node<SizeofExpression>(parent, position(), {});
  1308. consume(Token::Type::Keyword);
  1309. consume(Token::Type::LeftParen);
  1310. exp->set_type(parse_type(parent));
  1311. consume(Token::Type::RightParen);
  1312. exp->set_end(position());
  1313. return exp;
  1314. }
  1315. bool Parser::match_braced_init_list()
  1316. {
  1317. return match(Token::Type::LeftCurly);
  1318. }
  1319. NonnullRefPtr<BracedInitList> Parser::parse_braced_init_list(ASTNode& parent)
  1320. {
  1321. auto init_list = create_ast_node<BracedInitList>(parent, position(), {});
  1322. consume(Token::Type::LeftCurly);
  1323. while (!eof() && peek().type() != Token::Type::RightCurly) {
  1324. init_list->add_expression(parse_expression(*init_list));
  1325. }
  1326. consume(Token::Type::RightCurly);
  1327. init_list->set_end(position());
  1328. return init_list;
  1329. }
  1330. NonnullRefPtrVector<Declaration> Parser::parse_class_members(StructOrClassDeclaration& parent)
  1331. {
  1332. auto& class_name = parent.name();
  1333. NonnullRefPtrVector<Declaration> members;
  1334. while (!eof() && peek().type() != Token::Type::RightCurly) {
  1335. if (match_access_specifier())
  1336. consume_access_specifier(); // FIXME: Do not ignore access specifiers
  1337. auto member_type = match_class_member(class_name);
  1338. if (member_type.has_value()) {
  1339. members.append(parse_declaration(parent, member_type.value()));
  1340. } else {
  1341. error("Expected class member");
  1342. consume();
  1343. }
  1344. }
  1345. return members;
  1346. }
  1347. bool Parser::match_access_specifier()
  1348. {
  1349. if (peek(1).type() != Token::Type::Colon)
  1350. return false;
  1351. return match_keyword("private") || match_keyword("protected") || match_keyword("public");
  1352. }
  1353. void Parser::consume_access_specifier()
  1354. {
  1355. consume(Token::Type::Keyword);
  1356. consume(Token::Type::Colon);
  1357. }
  1358. bool Parser::match_constructor(const StringView& class_name)
  1359. {
  1360. save_state();
  1361. ScopeGuard state_guard = [this] { load_state(); };
  1362. auto token = consume();
  1363. if (token.text() != class_name)
  1364. return false;
  1365. if (!peek(Token::Type::LeftParen).has_value())
  1366. return false;
  1367. consume();
  1368. while (consume().type() != Token::Type::RightParen && !eof()) { };
  1369. return (peek(Token::Type::Semicolon).has_value() || peek(Token::Type::LeftCurly).has_value());
  1370. }
  1371. bool Parser::match_destructor(const StringView& class_name)
  1372. {
  1373. save_state();
  1374. ScopeGuard state_guard = [this] { load_state(); };
  1375. if (match_keyword("virtual"))
  1376. consume();
  1377. if (!match(Token::Type::Tilde))
  1378. return false;
  1379. consume();
  1380. auto token = peek();
  1381. if (token.text() != class_name)
  1382. return false;
  1383. consume();
  1384. if (!peek(Token::Type::LeftParen).has_value())
  1385. return false;
  1386. consume();
  1387. while (consume().type() != Token::Type::RightParen && !eof()) { };
  1388. if (match_keyword("override"))
  1389. consume();
  1390. return (peek(Token::Type::Semicolon).has_value() || peek(Token::Type::LeftCurly).has_value());
  1391. }
  1392. void Parser::parse_constructor_or_destructor_impl(FunctionDeclaration& func, CtorOrDtor type)
  1393. {
  1394. if (type == CtorOrDtor::Dtor) {
  1395. if (match_keyword("virtual"))
  1396. func.set_qualifiers({ consume().text() });
  1397. consume(Token::Type::Tilde);
  1398. }
  1399. auto name_token = consume();
  1400. if (name_token.type() != Token::Type::Identifier && name_token.type() != Token::Type::KnownType) {
  1401. error("Unexpected constructor name");
  1402. }
  1403. func.set_name(name_token.text());
  1404. consume(Token::Type::LeftParen);
  1405. auto parameters = parse_parameter_list(func);
  1406. if (parameters.has_value()) {
  1407. if (type == CtorOrDtor::Dtor && !parameters->is_empty())
  1408. error("Destructor declaration that takes parameters");
  1409. else
  1410. func.set_parameters(parameters.value());
  1411. }
  1412. consume(Token::Type::RightParen);
  1413. if (type == CtorOrDtor::Dtor && match_keyword("override"))
  1414. consume();
  1415. // TODO: Parse =default, =delete.
  1416. RefPtr<FunctionDefinition> body;
  1417. Position ctor_end {};
  1418. if (peek(Token::Type::LeftCurly).has_value()) {
  1419. body = parse_function_definition(func);
  1420. ctor_end = body->end();
  1421. } else {
  1422. ctor_end = position();
  1423. if (match_attribute_specification())
  1424. consume_attribute_specification(); // we don't use the value of __attribute__
  1425. consume(Token::Type::Semicolon);
  1426. }
  1427. func.set_definition(move(body));
  1428. func.set_end(ctor_end);
  1429. }
  1430. NonnullRefPtr<Constructor> Parser::parse_constructor(ASTNode& parent)
  1431. {
  1432. auto ctor = create_ast_node<Constructor>(parent, position(), {});
  1433. parse_constructor_or_destructor_impl(*ctor, CtorOrDtor::Ctor);
  1434. return ctor;
  1435. }
  1436. NonnullRefPtr<Destructor> Parser::parse_destructor(ASTNode& parent)
  1437. {
  1438. auto ctor = create_ast_node<Destructor>(parent, position(), {});
  1439. parse_constructor_or_destructor_impl(*ctor, CtorOrDtor::Dtor);
  1440. return ctor;
  1441. }
  1442. }