Parser.cpp 42 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929394959697989910010110210310410510610710810911011111211311411511611711811912012112212312412512612712812913013113213313413513613713813914014114214314414514614714814915015115215315415515615715815916016116216316416516616716816917017117217317417517617717817918018118218318418518618718818919019119219319419519619719819920020120220320420520620720820921021121221321421521621721821922022122222322422522622722822923023123223323423523623723823924024124224324424524624724824925025125225325425525625725825926026126226326426526626726826927027127227327427527627727827928028128228328428528628728828929029129229329429529629729829930030130230330430530630730830931031131231331431531631731831932032132232332432532632732832933033133233333433533633733833934034134234334434534634734834935035135235335435535635735835936036136236336436536636736836937037137237337437537637737837938038138238338438538638738838939039139239339439539639739839940040140240340440540640740840941041141241341441541641741841942042142242342442542642742842943043143243343443543643743843944044144244344444544644744844945045145245345445545645745845946046146246346446546646746846947047147247347447547647747847948048148248348448548648748848949049149249349449549649749849950050150250350450550650750850951051151251351451551651751851952052152252352452552652752852953053153253353453553653753853954054154254354454554654754854955055155255355455555655755855956056156256356456556656756856957057157257357457557657757857958058158258358458558658758858959059159259359459559659759859960060160260360460560660760860961061161261361461561661761861962062162262362462562662762862963063163263363463563663763863964064164264364464564664764864965065165265365465565665765865966066166266366466566666766866967067167267367467567667767867968068168268368468568668768868969069169269369469569669769869970070170270370470570670770870971071171271371471571671771871972072172272372472572672772872973073173273373473573673773873974074174274374474574674774874975075175275375475575675775875976076176276376476576676776876977077177277377477577677777877978078178278378478578678778878979079179279379479579679779879980080180280380480580680780880981081181281381481581681781881982082182282382482582682782882983083183283383483583683783883984084184284384484584684784884985085185285385485585685785885986086186286386486586686786886987087187287387487587687787887988088188288388488588688788888989089189289389489589689789889990090190290390490590690790890991091191291391491591691791891992092192292392492592692792892993093193293393493593693793893994094194294394494594694794894995095195295395495595695795895996096196296396496596696796896997097197297397497597697797897998098198298398498598698798898999099199299399499599699799899910001001100210031004100510061007100810091010101110121013101410151016101710181019102010211022102310241025102610271028102910301031103210331034103510361037103810391040104110421043104410451046104710481049105010511052105310541055105610571058105910601061106210631064106510661067106810691070107110721073107410751076107710781079108010811082108310841085108610871088108910901091109210931094109510961097109810991100110111021103110411051106110711081109111011111112111311141115111611171118111911201121112211231124112511261127112811291130113111321133113411351136113711381139114011411142114311441145114611471148114911501151115211531154115511561157115811591160116111621163116411651166116711681169117011711172117311741175
  1. /*
  2. * Copyright (c) 2021, Tim Flynn <trflynn89@serenityos.org>
  3. * Copyright (c) 2021, Mahmoud Mandour <ma.mandourr@gmail.com>
  4. *
  5. * SPDX-License-Identifier: BSD-2-Clause
  6. */
  7. #include "Parser.h"
  8. #include <AK/ScopeGuard.h>
  9. #include <AK/TypeCasts.h>
  10. namespace SQL::AST {
  11. Parser::Parser(Lexer lexer)
  12. : m_parser_state(move(lexer))
  13. {
  14. }
  15. NonnullRefPtr<Statement> Parser::next_statement()
  16. {
  17. auto terminate_statement = [this](auto statement) {
  18. consume(TokenType::SemiColon);
  19. return statement;
  20. };
  21. if (match(TokenType::With)) {
  22. auto common_table_expression_list = parse_common_table_expression_list();
  23. if (!common_table_expression_list)
  24. return create_ast_node<ErrorStatement>();
  25. return terminate_statement(parse_statement_with_expression_list(move(common_table_expression_list)));
  26. }
  27. return terminate_statement(parse_statement());
  28. }
  29. NonnullRefPtr<Statement> Parser::parse_statement()
  30. {
  31. switch (m_parser_state.m_token.type()) {
  32. case TokenType::Create:
  33. consume();
  34. if (match(TokenType::Schema))
  35. return parse_create_schema_statement();
  36. else
  37. return parse_create_table_statement();
  38. case TokenType::Alter:
  39. return parse_alter_table_statement();
  40. case TokenType::Drop:
  41. return parse_drop_table_statement();
  42. case TokenType::Describe:
  43. return parse_describe_table_statement();
  44. case TokenType::Insert:
  45. return parse_insert_statement({});
  46. case TokenType::Update:
  47. return parse_update_statement({});
  48. case TokenType::Delete:
  49. return parse_delete_statement({});
  50. case TokenType::Select:
  51. return parse_select_statement({});
  52. default:
  53. expected("CREATE, ALTER, DROP, DESCRIBE, INSERT, UPDATE, DELETE, or SELECT"sv);
  54. return create_ast_node<ErrorStatement>();
  55. }
  56. }
  57. NonnullRefPtr<Statement> Parser::parse_statement_with_expression_list(RefPtr<CommonTableExpressionList> common_table_expression_list)
  58. {
  59. switch (m_parser_state.m_token.type()) {
  60. case TokenType::Insert:
  61. return parse_insert_statement(move(common_table_expression_list));
  62. case TokenType::Update:
  63. return parse_update_statement(move(common_table_expression_list));
  64. case TokenType::Delete:
  65. return parse_delete_statement(move(common_table_expression_list));
  66. case TokenType::Select:
  67. return parse_select_statement(move(common_table_expression_list));
  68. default:
  69. expected("INSERT, UPDATE, DELETE, or SELECT"sv);
  70. return create_ast_node<ErrorStatement>();
  71. }
  72. }
  73. NonnullRefPtr<CreateSchema> Parser::parse_create_schema_statement()
  74. {
  75. consume(TokenType::Schema);
  76. bool is_error_if_exists = true;
  77. if (consume_if(TokenType::If)) {
  78. consume(TokenType::Not);
  79. consume(TokenType::Exists);
  80. is_error_if_exists = false;
  81. }
  82. DeprecatedString schema_name = consume(TokenType::Identifier).value();
  83. return create_ast_node<CreateSchema>(move(schema_name), is_error_if_exists);
  84. }
  85. NonnullRefPtr<CreateTable> Parser::parse_create_table_statement()
  86. {
  87. // https://sqlite.org/lang_createtable.html
  88. bool is_temporary = false;
  89. if (consume_if(TokenType::Temp) || consume_if(TokenType::Temporary))
  90. is_temporary = true;
  91. consume(TokenType::Table);
  92. bool is_error_if_table_exists = true;
  93. if (consume_if(TokenType::If)) {
  94. consume(TokenType::Not);
  95. consume(TokenType::Exists);
  96. is_error_if_table_exists = false;
  97. }
  98. DeprecatedString schema_name;
  99. DeprecatedString table_name;
  100. parse_schema_and_table_name(schema_name, table_name);
  101. if (consume_if(TokenType::As)) {
  102. auto select_statement = parse_select_statement({});
  103. return create_ast_node<CreateTable>(move(schema_name), move(table_name), move(select_statement), is_temporary, is_error_if_table_exists);
  104. }
  105. Vector<NonnullRefPtr<ColumnDefinition>> column_definitions;
  106. parse_comma_separated_list(true, [&]() { column_definitions.append(parse_column_definition()); });
  107. // FIXME: Parse "table-constraint".
  108. return create_ast_node<CreateTable>(move(schema_name), move(table_name), move(column_definitions), is_temporary, is_error_if_table_exists);
  109. }
  110. NonnullRefPtr<AlterTable> Parser::parse_alter_table_statement()
  111. {
  112. // https://sqlite.org/lang_altertable.html
  113. consume(TokenType::Alter);
  114. consume(TokenType::Table);
  115. DeprecatedString schema_name;
  116. DeprecatedString table_name;
  117. parse_schema_and_table_name(schema_name, table_name);
  118. if (consume_if(TokenType::Add)) {
  119. consume_if(TokenType::Column); // COLUMN is optional.
  120. auto column = parse_column_definition();
  121. return create_ast_node<AddColumn>(move(schema_name), move(table_name), move(column));
  122. }
  123. if (consume_if(TokenType::Drop)) {
  124. consume_if(TokenType::Column); // COLUMN is optional.
  125. auto column = consume(TokenType::Identifier).value();
  126. return create_ast_node<DropColumn>(move(schema_name), move(table_name), move(column));
  127. }
  128. consume(TokenType::Rename);
  129. if (consume_if(TokenType::To)) {
  130. auto new_table_name = consume(TokenType::Identifier).value();
  131. return create_ast_node<RenameTable>(move(schema_name), move(table_name), move(new_table_name));
  132. }
  133. consume_if(TokenType::Column); // COLUMN is optional.
  134. auto column_name = consume(TokenType::Identifier).value();
  135. consume(TokenType::To);
  136. auto new_column_name = consume(TokenType::Identifier).value();
  137. return create_ast_node<RenameColumn>(move(schema_name), move(table_name), move(column_name), move(new_column_name));
  138. }
  139. NonnullRefPtr<DropTable> Parser::parse_drop_table_statement()
  140. {
  141. // https://sqlite.org/lang_droptable.html
  142. consume(TokenType::Drop);
  143. consume(TokenType::Table);
  144. bool is_error_if_table_does_not_exist = true;
  145. if (consume_if(TokenType::If)) {
  146. consume(TokenType::Exists);
  147. is_error_if_table_does_not_exist = false;
  148. }
  149. DeprecatedString schema_name;
  150. DeprecatedString table_name;
  151. parse_schema_and_table_name(schema_name, table_name);
  152. return create_ast_node<DropTable>(move(schema_name), move(table_name), is_error_if_table_does_not_exist);
  153. }
  154. NonnullRefPtr<DescribeTable> Parser::parse_describe_table_statement()
  155. {
  156. consume(TokenType::Describe);
  157. consume(TokenType::Table);
  158. auto table_name = parse_qualified_table_name();
  159. return create_ast_node<DescribeTable>(move(table_name));
  160. }
  161. NonnullRefPtr<Insert> Parser::parse_insert_statement(RefPtr<CommonTableExpressionList> common_table_expression_list)
  162. {
  163. // https://sqlite.org/lang_insert.html
  164. consume(TokenType::Insert);
  165. auto conflict_resolution = parse_conflict_resolution();
  166. consume(TokenType::Into);
  167. DeprecatedString schema_name;
  168. DeprecatedString table_name;
  169. parse_schema_and_table_name(schema_name, table_name);
  170. DeprecatedString alias;
  171. if (consume_if(TokenType::As))
  172. alias = consume(TokenType::Identifier).value();
  173. Vector<DeprecatedString> column_names;
  174. if (match(TokenType::ParenOpen))
  175. parse_comma_separated_list(true, [&]() { column_names.append(consume(TokenType::Identifier).value()); });
  176. Vector<NonnullRefPtr<ChainedExpression>> chained_expressions;
  177. RefPtr<Select> select_statement;
  178. if (consume_if(TokenType::Values)) {
  179. parse_comma_separated_list(false, [&]() {
  180. if (auto chained_expression = parse_chained_expression()) {
  181. auto* chained_expr = verify_cast<ChainedExpression>(chained_expression.ptr());
  182. if ((column_names.size() > 0) && (chained_expr->expressions().size() != column_names.size())) {
  183. syntax_error("Number of expressions does not match number of columns");
  184. } else {
  185. chained_expressions.append(static_ptr_cast<ChainedExpression>(chained_expression.release_nonnull()));
  186. }
  187. } else {
  188. expected("Chained expression"sv);
  189. }
  190. });
  191. } else if (match(TokenType::Select)) {
  192. select_statement = parse_select_statement({});
  193. } else {
  194. consume(TokenType::Default);
  195. consume(TokenType::Values);
  196. }
  197. RefPtr<ReturningClause> returning_clause;
  198. if (match(TokenType::Returning))
  199. returning_clause = parse_returning_clause();
  200. // FIXME: Parse 'upsert-clause'.
  201. if (!chained_expressions.is_empty())
  202. return create_ast_node<Insert>(move(common_table_expression_list), conflict_resolution, move(schema_name), move(table_name), move(alias), move(column_names), move(chained_expressions));
  203. if (!select_statement.is_null())
  204. return create_ast_node<Insert>(move(common_table_expression_list), conflict_resolution, move(schema_name), move(table_name), move(alias), move(column_names), move(select_statement));
  205. return create_ast_node<Insert>(move(common_table_expression_list), conflict_resolution, move(schema_name), move(table_name), move(alias), move(column_names));
  206. }
  207. NonnullRefPtr<Update> Parser::parse_update_statement(RefPtr<CommonTableExpressionList> common_table_expression_list)
  208. {
  209. // https://sqlite.org/lang_update.html
  210. consume(TokenType::Update);
  211. auto conflict_resolution = parse_conflict_resolution();
  212. auto qualified_table_name = parse_qualified_table_name();
  213. consume(TokenType::Set);
  214. Vector<Update::UpdateColumns> update_columns;
  215. parse_comma_separated_list(false, [&]() {
  216. Vector<DeprecatedString> column_names;
  217. if (match(TokenType::ParenOpen)) {
  218. parse_comma_separated_list(true, [&]() { column_names.append(consume(TokenType::Identifier).value()); });
  219. } else {
  220. column_names.append(consume(TokenType::Identifier).value());
  221. }
  222. consume(TokenType::Equals);
  223. update_columns.append({ move(column_names), parse_expression() });
  224. });
  225. Vector<NonnullRefPtr<TableOrSubquery>> table_or_subquery_list;
  226. if (consume_if(TokenType::From)) {
  227. // FIXME: Parse join-clause.
  228. parse_comma_separated_list(false, [&]() { table_or_subquery_list.append(parse_table_or_subquery()); });
  229. }
  230. RefPtr<Expression> where_clause;
  231. if (consume_if(TokenType::Where))
  232. where_clause = parse_expression();
  233. RefPtr<ReturningClause> returning_clause;
  234. if (match(TokenType::Returning))
  235. returning_clause = parse_returning_clause();
  236. return create_ast_node<Update>(move(common_table_expression_list), conflict_resolution, move(qualified_table_name), move(update_columns), move(table_or_subquery_list), move(where_clause), move(returning_clause));
  237. }
  238. NonnullRefPtr<Delete> Parser::parse_delete_statement(RefPtr<CommonTableExpressionList> common_table_expression_list)
  239. {
  240. // https://sqlite.org/lang_delete.html
  241. consume(TokenType::Delete);
  242. consume(TokenType::From);
  243. auto qualified_table_name = parse_qualified_table_name();
  244. RefPtr<Expression> where_clause;
  245. if (consume_if(TokenType::Where))
  246. where_clause = parse_expression();
  247. RefPtr<ReturningClause> returning_clause;
  248. if (match(TokenType::Returning))
  249. returning_clause = parse_returning_clause();
  250. return create_ast_node<Delete>(move(common_table_expression_list), move(qualified_table_name), move(where_clause), move(returning_clause));
  251. }
  252. NonnullRefPtr<Select> Parser::parse_select_statement(RefPtr<CommonTableExpressionList> common_table_expression_list)
  253. {
  254. // https://sqlite.org/lang_select.html
  255. consume(TokenType::Select);
  256. bool select_all = !consume_if(TokenType::Distinct);
  257. consume_if(TokenType::All); // ALL is the default, so ignore it if specified.
  258. Vector<NonnullRefPtr<ResultColumn>> result_column_list;
  259. parse_comma_separated_list(false, [&]() { result_column_list.append(parse_result_column()); });
  260. Vector<NonnullRefPtr<TableOrSubquery>> table_or_subquery_list;
  261. if (consume_if(TokenType::From)) {
  262. // FIXME: Parse join-clause.
  263. parse_comma_separated_list(false, [&]() { table_or_subquery_list.append(parse_table_or_subquery()); });
  264. }
  265. RefPtr<Expression> where_clause;
  266. if (consume_if(TokenType::Where))
  267. where_clause = parse_expression();
  268. RefPtr<GroupByClause> group_by_clause;
  269. if (consume_if(TokenType::Group)) {
  270. consume(TokenType::By);
  271. Vector<NonnullRefPtr<Expression>> group_by_list;
  272. parse_comma_separated_list(false, [&]() { group_by_list.append(parse_expression()); });
  273. if (!group_by_list.is_empty()) {
  274. RefPtr<Expression> having_clause;
  275. if (consume_if(TokenType::Having))
  276. having_clause = parse_expression();
  277. group_by_clause = create_ast_node<GroupByClause>(move(group_by_list), move(having_clause));
  278. }
  279. }
  280. // FIXME: Parse 'WINDOW window-name AS window-defn'.
  281. // FIXME: Parse 'compound-operator'.
  282. Vector<NonnullRefPtr<OrderingTerm>> ordering_term_list;
  283. if (consume_if(TokenType::Order)) {
  284. consume(TokenType::By);
  285. parse_comma_separated_list(false, [&]() { ordering_term_list.append(parse_ordering_term()); });
  286. }
  287. RefPtr<LimitClause> limit_clause;
  288. if (consume_if(TokenType::Limit)) {
  289. auto limit_expression = parse_expression();
  290. RefPtr<Expression> offset_expression;
  291. if (consume_if(TokenType::Offset)) {
  292. offset_expression = parse_expression();
  293. } else if (consume_if(TokenType::Comma)) {
  294. // Note: The limit clause may instead be defined as "offset-expression, limit-expression", effectively reversing the
  295. // order of the expressions. SQLite notes "this is counter-intuitive" and "to avoid confusion, programmers are strongly
  296. // encouraged to ... avoid using a LIMIT clause with a comma-separated offset."
  297. syntax_error("LIMIT clauses of the form 'LIMIT <expr>, <expr>' are not supported");
  298. }
  299. limit_clause = create_ast_node<LimitClause>(move(limit_expression), move(offset_expression));
  300. }
  301. return create_ast_node<Select>(move(common_table_expression_list), select_all, move(result_column_list), move(table_or_subquery_list), move(where_clause), move(group_by_clause), move(ordering_term_list), move(limit_clause));
  302. }
  303. RefPtr<CommonTableExpressionList> Parser::parse_common_table_expression_list()
  304. {
  305. consume(TokenType::With);
  306. bool recursive = consume_if(TokenType::Recursive);
  307. Vector<NonnullRefPtr<CommonTableExpression>> common_table_expression;
  308. parse_comma_separated_list(false, [&]() { common_table_expression.append(parse_common_table_expression()); });
  309. if (common_table_expression.is_empty()) {
  310. expected("Common table expression list"sv);
  311. return {};
  312. }
  313. return create_ast_node<CommonTableExpressionList>(recursive, move(common_table_expression));
  314. }
  315. NonnullRefPtr<Expression> Parser::parse_expression()
  316. {
  317. if (++m_parser_state.m_current_expression_depth > Limits::maximum_expression_tree_depth) {
  318. syntax_error(DeprecatedString::formatted("Exceeded maximum expression tree depth of {}", Limits::maximum_expression_tree_depth));
  319. return create_ast_node<ErrorExpression>();
  320. }
  321. // https://sqlite.org/lang_expr.html
  322. auto expression = parse_primary_expression();
  323. if (match_secondary_expression())
  324. expression = parse_secondary_expression(move(expression));
  325. // FIXME: Parse 'function-name'.
  326. // FIXME: Parse 'raise-function'.
  327. --m_parser_state.m_current_expression_depth;
  328. return expression;
  329. }
  330. NonnullRefPtr<Expression> Parser::parse_primary_expression()
  331. {
  332. if (auto expression = parse_literal_value_expression())
  333. return expression.release_nonnull();
  334. if (auto expression = parse_bind_parameter_expression())
  335. return expression.release_nonnull();
  336. if (auto expression = parse_column_name_expression())
  337. return expression.release_nonnull();
  338. if (auto expression = parse_unary_operator_expression())
  339. return expression.release_nonnull();
  340. if (auto expression = parse_cast_expression())
  341. return expression.release_nonnull();
  342. if (auto expression = parse_case_expression())
  343. return expression.release_nonnull();
  344. if (auto invert_expression = consume_if(TokenType::Not); invert_expression || consume_if(TokenType::Exists)) {
  345. if (auto expression = parse_exists_expression(invert_expression))
  346. return expression.release_nonnull();
  347. expected("Exists expression"sv);
  348. }
  349. if (consume_if(TokenType::ParenOpen)) {
  350. // Encountering a Select token at this point means this must be an ExistsExpression with no EXISTS keyword.
  351. if (match(TokenType::Select)) {
  352. auto select_statement = parse_select_statement({});
  353. consume(TokenType::ParenClose);
  354. return create_ast_node<ExistsExpression>(move(select_statement), false);
  355. }
  356. if (auto expression = parse_chained_expression(false)) {
  357. consume(TokenType::ParenClose);
  358. return expression.release_nonnull();
  359. }
  360. expected("Chained expression"sv);
  361. }
  362. expected("Primary Expression"sv);
  363. consume();
  364. return create_ast_node<ErrorExpression>();
  365. }
  366. NonnullRefPtr<Expression> Parser::parse_secondary_expression(NonnullRefPtr<Expression> primary)
  367. {
  368. if (auto expression = parse_binary_operator_expression(primary))
  369. return expression.release_nonnull();
  370. if (auto expression = parse_collate_expression(primary))
  371. return expression.release_nonnull();
  372. if (auto expression = parse_is_expression(primary))
  373. return expression.release_nonnull();
  374. bool invert_expression = false;
  375. if (consume_if(TokenType::Not))
  376. invert_expression = true;
  377. if (auto expression = parse_match_expression(primary, invert_expression))
  378. return expression.release_nonnull();
  379. if (auto expression = parse_null_expression(primary, invert_expression))
  380. return expression.release_nonnull();
  381. if (auto expression = parse_between_expression(primary, invert_expression))
  382. return expression.release_nonnull();
  383. if (auto expression = parse_in_expression(primary, invert_expression))
  384. return expression.release_nonnull();
  385. expected("Secondary Expression"sv);
  386. consume();
  387. return create_ast_node<ErrorExpression>();
  388. }
  389. bool Parser::match_secondary_expression() const
  390. {
  391. return match(TokenType::Not)
  392. || match(TokenType::DoublePipe)
  393. || match(TokenType::Asterisk)
  394. || match(TokenType::Divide)
  395. || match(TokenType::Modulus)
  396. || match(TokenType::Plus)
  397. || match(TokenType::Minus)
  398. || match(TokenType::ShiftLeft)
  399. || match(TokenType::ShiftRight)
  400. || match(TokenType::Ampersand)
  401. || match(TokenType::Pipe)
  402. || match(TokenType::LessThan)
  403. || match(TokenType::LessThanEquals)
  404. || match(TokenType::GreaterThan)
  405. || match(TokenType::GreaterThanEquals)
  406. || match(TokenType::Equals)
  407. || match(TokenType::EqualsEquals)
  408. || match(TokenType::NotEquals1)
  409. || match(TokenType::NotEquals2)
  410. || match(TokenType::And)
  411. || match(TokenType::Or)
  412. || match(TokenType::Collate)
  413. || match(TokenType::Is)
  414. || match(TokenType::Like)
  415. || match(TokenType::Glob)
  416. || match(TokenType::Match)
  417. || match(TokenType::Regexp)
  418. || match(TokenType::Isnull)
  419. || match(TokenType::Notnull)
  420. || match(TokenType::Between)
  421. || match(TokenType::In);
  422. }
  423. RefPtr<Expression> Parser::parse_literal_value_expression()
  424. {
  425. if (match(TokenType::NumericLiteral)) {
  426. auto value = consume().double_value();
  427. return create_ast_node<NumericLiteral>(value);
  428. }
  429. if (match(TokenType::StringLiteral)) {
  430. // TODO: Should the surrounding ' ' be removed here?
  431. auto value = consume().value();
  432. return create_ast_node<StringLiteral>(value);
  433. }
  434. if (match(TokenType::BlobLiteral)) {
  435. // TODO: Should the surrounding x' ' be removed here?
  436. auto value = consume().value();
  437. return create_ast_node<BlobLiteral>(value);
  438. }
  439. if (consume_if(TokenType::True))
  440. return create_ast_node<BooleanLiteral>(true);
  441. if (consume_if(TokenType::False))
  442. return create_ast_node<BooleanLiteral>(false);
  443. if (consume_if(TokenType::Null))
  444. return create_ast_node<NullLiteral>();
  445. return {};
  446. }
  447. // https://sqlite.org/lang_expr.html#varparam
  448. RefPtr<Expression> Parser::parse_bind_parameter_expression()
  449. {
  450. // FIXME: Support ?NNN, :AAAA, @AAAA, and $AAAA forms.
  451. if (consume_if(TokenType::Placeholder)) {
  452. auto parameter = m_parser_state.m_bound_parameters;
  453. if (++m_parser_state.m_bound_parameters > Limits::maximum_bound_parameters)
  454. syntax_error(DeprecatedString::formatted("Exceeded maximum number of bound parameters {}", Limits::maximum_bound_parameters));
  455. return create_ast_node<Placeholder>(parameter);
  456. }
  457. return {};
  458. }
  459. RefPtr<Expression> Parser::parse_column_name_expression(Optional<DeprecatedString> with_parsed_identifier, bool with_parsed_period)
  460. {
  461. if (!with_parsed_identifier.has_value() && !match(TokenType::Identifier))
  462. return {};
  463. DeprecatedString first_identifier;
  464. if (!with_parsed_identifier.has_value())
  465. first_identifier = consume(TokenType::Identifier).value();
  466. else
  467. first_identifier = with_parsed_identifier.release_value();
  468. DeprecatedString schema_name;
  469. DeprecatedString table_name;
  470. DeprecatedString column_name;
  471. if (with_parsed_period || consume_if(TokenType::Period)) {
  472. DeprecatedString second_identifier = consume(TokenType::Identifier).value();
  473. if (consume_if(TokenType::Period)) {
  474. schema_name = move(first_identifier);
  475. table_name = move(second_identifier);
  476. column_name = consume(TokenType::Identifier).value();
  477. } else {
  478. table_name = move(first_identifier);
  479. column_name = move(second_identifier);
  480. }
  481. } else {
  482. column_name = move(first_identifier);
  483. }
  484. return create_ast_node<ColumnNameExpression>(move(schema_name), move(table_name), move(column_name));
  485. }
  486. RefPtr<Expression> Parser::parse_unary_operator_expression()
  487. {
  488. if (consume_if(TokenType::Minus))
  489. return create_ast_node<UnaryOperatorExpression>(UnaryOperator::Minus, parse_expression());
  490. if (consume_if(TokenType::Plus))
  491. return create_ast_node<UnaryOperatorExpression>(UnaryOperator::Plus, parse_expression());
  492. if (consume_if(TokenType::Tilde))
  493. return create_ast_node<UnaryOperatorExpression>(UnaryOperator::BitwiseNot, parse_expression());
  494. if (consume_if(TokenType::Not)) {
  495. if (match(TokenType::Exists))
  496. return parse_exists_expression(true);
  497. else
  498. return create_ast_node<UnaryOperatorExpression>(UnaryOperator::Not, parse_expression());
  499. }
  500. return {};
  501. }
  502. RefPtr<Expression> Parser::parse_binary_operator_expression(NonnullRefPtr<Expression> lhs)
  503. {
  504. if (consume_if(TokenType::DoublePipe))
  505. return create_ast_node<BinaryOperatorExpression>(BinaryOperator::Concatenate, move(lhs), parse_expression());
  506. if (consume_if(TokenType::Asterisk))
  507. return create_ast_node<BinaryOperatorExpression>(BinaryOperator::Multiplication, move(lhs), parse_expression());
  508. if (consume_if(TokenType::Divide))
  509. return create_ast_node<BinaryOperatorExpression>(BinaryOperator::Division, move(lhs), parse_expression());
  510. if (consume_if(TokenType::Modulus))
  511. return create_ast_node<BinaryOperatorExpression>(BinaryOperator::Modulo, move(lhs), parse_expression());
  512. if (consume_if(TokenType::Plus))
  513. return create_ast_node<BinaryOperatorExpression>(BinaryOperator::Plus, move(lhs), parse_expression());
  514. if (consume_if(TokenType::Minus))
  515. return create_ast_node<BinaryOperatorExpression>(BinaryOperator::Minus, move(lhs), parse_expression());
  516. if (consume_if(TokenType::ShiftLeft))
  517. return create_ast_node<BinaryOperatorExpression>(BinaryOperator::ShiftLeft, move(lhs), parse_expression());
  518. if (consume_if(TokenType::ShiftRight))
  519. return create_ast_node<BinaryOperatorExpression>(BinaryOperator::ShiftRight, move(lhs), parse_expression());
  520. if (consume_if(TokenType::Ampersand))
  521. return create_ast_node<BinaryOperatorExpression>(BinaryOperator::BitwiseAnd, move(lhs), parse_expression());
  522. if (consume_if(TokenType::Pipe))
  523. return create_ast_node<BinaryOperatorExpression>(BinaryOperator::BitwiseOr, move(lhs), parse_expression());
  524. if (consume_if(TokenType::LessThan))
  525. return create_ast_node<BinaryOperatorExpression>(BinaryOperator::LessThan, move(lhs), parse_expression());
  526. if (consume_if(TokenType::LessThanEquals))
  527. return create_ast_node<BinaryOperatorExpression>(BinaryOperator::LessThanEquals, move(lhs), parse_expression());
  528. if (consume_if(TokenType::GreaterThan))
  529. return create_ast_node<BinaryOperatorExpression>(BinaryOperator::GreaterThan, move(lhs), parse_expression());
  530. if (consume_if(TokenType::GreaterThanEquals))
  531. return create_ast_node<BinaryOperatorExpression>(BinaryOperator::GreaterThanEquals, move(lhs), parse_expression());
  532. if (consume_if(TokenType::Equals) || consume_if(TokenType::EqualsEquals))
  533. return create_ast_node<BinaryOperatorExpression>(BinaryOperator::Equals, move(lhs), parse_expression());
  534. if (consume_if(TokenType::NotEquals1) || consume_if(TokenType::NotEquals2))
  535. return create_ast_node<BinaryOperatorExpression>(BinaryOperator::NotEquals, move(lhs), parse_expression());
  536. if (consume_if(TokenType::And))
  537. return create_ast_node<BinaryOperatorExpression>(BinaryOperator::And, move(lhs), parse_expression());
  538. if (consume_if(TokenType::Or))
  539. return create_ast_node<BinaryOperatorExpression>(BinaryOperator::Or, move(lhs), parse_expression());
  540. return {};
  541. }
  542. RefPtr<Expression> Parser::parse_chained_expression(bool surrounded_by_parentheses)
  543. {
  544. if (surrounded_by_parentheses && !consume_if(TokenType::ParenOpen))
  545. return {};
  546. Vector<NonnullRefPtr<Expression>> expressions;
  547. parse_comma_separated_list(false, [&]() { expressions.append(parse_expression()); });
  548. if (surrounded_by_parentheses)
  549. consume(TokenType::ParenClose);
  550. return create_ast_node<ChainedExpression>(move(expressions));
  551. }
  552. RefPtr<Expression> Parser::parse_cast_expression()
  553. {
  554. if (!match(TokenType::Cast))
  555. return {};
  556. consume(TokenType::Cast);
  557. consume(TokenType::ParenOpen);
  558. auto expression = parse_expression();
  559. consume(TokenType::As);
  560. auto type_name = parse_type_name();
  561. consume(TokenType::ParenClose);
  562. return create_ast_node<CastExpression>(move(expression), move(type_name));
  563. }
  564. RefPtr<Expression> Parser::parse_case_expression()
  565. {
  566. if (!match(TokenType::Case))
  567. return {};
  568. consume();
  569. RefPtr<Expression> case_expression;
  570. if (!match(TokenType::When)) {
  571. case_expression = parse_expression();
  572. }
  573. Vector<CaseExpression::WhenThenClause> when_then_clauses;
  574. do {
  575. consume(TokenType::When);
  576. auto when = parse_expression();
  577. consume(TokenType::Then);
  578. auto then = parse_expression();
  579. when_then_clauses.append({ move(when), move(then) });
  580. if (!match(TokenType::When))
  581. break;
  582. } while (!match(TokenType::Eof));
  583. RefPtr<Expression> else_expression;
  584. if (consume_if(TokenType::Else))
  585. else_expression = parse_expression();
  586. consume(TokenType::End);
  587. return create_ast_node<CaseExpression>(move(case_expression), move(when_then_clauses), move(else_expression));
  588. }
  589. RefPtr<Expression> Parser::parse_exists_expression(bool invert_expression)
  590. {
  591. if (!(match(TokenType::Exists) || match(TokenType::ParenOpen)))
  592. return {};
  593. consume_if(TokenType::Exists);
  594. consume(TokenType::ParenOpen);
  595. auto select_statement = parse_select_statement({});
  596. consume(TokenType::ParenClose);
  597. return create_ast_node<ExistsExpression>(move(select_statement), invert_expression);
  598. }
  599. RefPtr<Expression> Parser::parse_collate_expression(NonnullRefPtr<Expression> expression)
  600. {
  601. if (!match(TokenType::Collate))
  602. return {};
  603. consume();
  604. DeprecatedString collation_name = consume(TokenType::Identifier).value();
  605. return create_ast_node<CollateExpression>(move(expression), move(collation_name));
  606. }
  607. RefPtr<Expression> Parser::parse_is_expression(NonnullRefPtr<Expression> expression)
  608. {
  609. if (!match(TokenType::Is))
  610. return {};
  611. consume();
  612. bool invert_expression = false;
  613. if (match(TokenType::Not)) {
  614. consume();
  615. invert_expression = true;
  616. }
  617. auto rhs = parse_expression();
  618. return create_ast_node<IsExpression>(move(expression), move(rhs), invert_expression);
  619. }
  620. RefPtr<Expression> Parser::parse_match_expression(NonnullRefPtr<Expression> lhs, bool invert_expression)
  621. {
  622. auto parse_escape = [this]() {
  623. RefPtr<Expression> escape;
  624. if (consume_if(TokenType::Escape)) {
  625. escape = parse_expression();
  626. }
  627. return escape;
  628. };
  629. if (consume_if(TokenType::Like)) {
  630. NonnullRefPtr<Expression> rhs = parse_expression();
  631. RefPtr<Expression> escape = parse_escape();
  632. return create_ast_node<MatchExpression>(MatchOperator::Like, move(lhs), move(rhs), move(escape), invert_expression);
  633. }
  634. if (consume_if(TokenType::Glob)) {
  635. NonnullRefPtr<Expression> rhs = parse_expression();
  636. RefPtr<Expression> escape = parse_escape();
  637. return create_ast_node<MatchExpression>(MatchOperator::Glob, move(lhs), move(rhs), move(escape), invert_expression);
  638. }
  639. if (consume_if(TokenType::Match)) {
  640. NonnullRefPtr<Expression> rhs = parse_expression();
  641. RefPtr<Expression> escape = parse_escape();
  642. return create_ast_node<MatchExpression>(MatchOperator::Match, move(lhs), move(rhs), move(escape), invert_expression);
  643. }
  644. if (consume_if(TokenType::Regexp)) {
  645. NonnullRefPtr<Expression> rhs = parse_expression();
  646. RefPtr<Expression> escape = parse_escape();
  647. return create_ast_node<MatchExpression>(MatchOperator::Regexp, move(lhs), move(rhs), move(escape), invert_expression);
  648. }
  649. return {};
  650. }
  651. RefPtr<Expression> Parser::parse_null_expression(NonnullRefPtr<Expression> expression, bool invert_expression)
  652. {
  653. if (!match(TokenType::Isnull) && !match(TokenType::Notnull) && !(invert_expression && match(TokenType::Null)))
  654. return {};
  655. auto type = consume().type();
  656. invert_expression |= (type == TokenType::Notnull);
  657. return create_ast_node<NullExpression>(move(expression), invert_expression);
  658. }
  659. RefPtr<Expression> Parser::parse_between_expression(NonnullRefPtr<Expression> expression, bool invert_expression)
  660. {
  661. if (!match(TokenType::Between))
  662. return {};
  663. consume();
  664. auto nested = parse_expression();
  665. if (!is<BinaryOperatorExpression>(*nested)) {
  666. expected("Binary Expression"sv);
  667. return create_ast_node<ErrorExpression>();
  668. }
  669. auto const& binary_expression = static_cast<BinaryOperatorExpression const&>(*nested);
  670. if (binary_expression.type() != BinaryOperator::And) {
  671. expected("AND Expression"sv);
  672. return create_ast_node<ErrorExpression>();
  673. }
  674. return create_ast_node<BetweenExpression>(move(expression), binary_expression.lhs(), binary_expression.rhs(), invert_expression);
  675. }
  676. RefPtr<Expression> Parser::parse_in_expression(NonnullRefPtr<Expression> expression, bool invert_expression)
  677. {
  678. if (!match(TokenType::In))
  679. return {};
  680. consume();
  681. if (consume_if(TokenType::ParenOpen)) {
  682. if (match(TokenType::Select)) {
  683. auto select_statement = parse_select_statement({});
  684. return create_ast_node<InSelectionExpression>(move(expression), move(select_statement), invert_expression);
  685. }
  686. // FIXME: Consolidate this with parse_chained_expression(). That method consumes the opening paren as
  687. // well, and also requires at least one expression (whereas this allows for an empty chain).
  688. Vector<NonnullRefPtr<Expression>> expressions;
  689. if (!match(TokenType::ParenClose))
  690. parse_comma_separated_list(false, [&]() { expressions.append(parse_expression()); });
  691. consume(TokenType::ParenClose);
  692. auto chain = create_ast_node<ChainedExpression>(move(expressions));
  693. return create_ast_node<InChainedExpression>(move(expression), move(chain), invert_expression);
  694. }
  695. DeprecatedString schema_name;
  696. DeprecatedString table_name;
  697. parse_schema_and_table_name(schema_name, table_name);
  698. if (match(TokenType::ParenOpen)) {
  699. // FIXME: Parse "table-function".
  700. return {};
  701. }
  702. return create_ast_node<InTableExpression>(move(expression), move(schema_name), move(table_name), invert_expression);
  703. }
  704. NonnullRefPtr<ColumnDefinition> Parser::parse_column_definition()
  705. {
  706. // https://sqlite.org/syntax/column-def.html
  707. auto name = consume(TokenType::Identifier).value();
  708. auto type_name = match(TokenType::Identifier)
  709. ? parse_type_name()
  710. // https://www.sqlite.org/datatype3.html: If no type is specified then the column has affinity BLOB.
  711. : create_ast_node<TypeName>("BLOB", Vector<NonnullRefPtr<SignedNumber>> {});
  712. // FIXME: Parse "column-constraint".
  713. return create_ast_node<ColumnDefinition>(move(name), move(type_name));
  714. }
  715. NonnullRefPtr<TypeName> Parser::parse_type_name()
  716. {
  717. // https: //sqlite.org/syntax/type-name.html
  718. auto name = consume(TokenType::Identifier).value();
  719. Vector<NonnullRefPtr<SignedNumber>> signed_numbers;
  720. if (consume_if(TokenType::ParenOpen)) {
  721. signed_numbers.append(parse_signed_number());
  722. if (consume_if(TokenType::Comma))
  723. signed_numbers.append(parse_signed_number());
  724. consume(TokenType::ParenClose);
  725. }
  726. return create_ast_node<TypeName>(move(name), move(signed_numbers));
  727. }
  728. NonnullRefPtr<SignedNumber> Parser::parse_signed_number()
  729. {
  730. // https://sqlite.org/syntax/signed-number.html
  731. bool is_positive = true;
  732. if (consume_if(TokenType::Plus))
  733. is_positive = true;
  734. else if (consume_if(TokenType::Minus))
  735. is_positive = false;
  736. if (match(TokenType::NumericLiteral)) {
  737. auto number = consume(TokenType::NumericLiteral).double_value();
  738. return create_ast_node<SignedNumber>(is_positive ? number : (number * -1));
  739. }
  740. expected("NumericLiteral"sv);
  741. return create_ast_node<SignedNumber>(0);
  742. }
  743. NonnullRefPtr<CommonTableExpression> Parser::parse_common_table_expression()
  744. {
  745. // https://sqlite.org/syntax/common-table-expression.html
  746. auto table_name = consume(TokenType::Identifier).value();
  747. Vector<DeprecatedString> column_names;
  748. if (match(TokenType::ParenOpen))
  749. parse_comma_separated_list(true, [&]() { column_names.append(consume(TokenType::Identifier).value()); });
  750. consume(TokenType::As);
  751. consume(TokenType::ParenOpen);
  752. auto select_statement = parse_select_statement({});
  753. consume(TokenType::ParenClose);
  754. return create_ast_node<CommonTableExpression>(move(table_name), move(column_names), move(select_statement));
  755. }
  756. NonnullRefPtr<QualifiedTableName> Parser::parse_qualified_table_name()
  757. {
  758. // https://sqlite.org/syntax/qualified-table-name.html
  759. DeprecatedString schema_name;
  760. DeprecatedString table_name;
  761. parse_schema_and_table_name(schema_name, table_name);
  762. DeprecatedString alias;
  763. if (consume_if(TokenType::As))
  764. alias = consume(TokenType::Identifier).value();
  765. // Note: The qualified-table-name spec may include an "INDEXED BY index-name" or "NOT INDEXED" clause. This is a SQLite extension
  766. // "designed to help detect undesirable query plan changes during regression testing", and "application developers are admonished
  767. // to omit all use of INDEXED BY during application design, implementation, testing, and tuning". Our implementation purposefully
  768. // omits parsing INDEXED BY for now until there is good reason to add support.
  769. return create_ast_node<QualifiedTableName>(move(schema_name), move(table_name), move(alias));
  770. }
  771. NonnullRefPtr<ReturningClause> Parser::parse_returning_clause()
  772. {
  773. // https://sqlite.org/syntax/returning-clause.html
  774. consume(TokenType::Returning);
  775. if (consume_if(TokenType::Asterisk))
  776. return create_ast_node<ReturningClause>();
  777. Vector<ReturningClause::ColumnClause> columns;
  778. parse_comma_separated_list(false, [&]() {
  779. auto expression = parse_expression();
  780. DeprecatedString column_alias;
  781. if (consume_if(TokenType::As) || match(TokenType::Identifier))
  782. column_alias = consume(TokenType::Identifier).value();
  783. columns.append({ move(expression), move(column_alias) });
  784. });
  785. return create_ast_node<ReturningClause>(move(columns));
  786. }
  787. NonnullRefPtr<ResultColumn> Parser::parse_result_column()
  788. {
  789. // https://sqlite.org/syntax/result-column.html
  790. if (consume_if(TokenType::Asterisk))
  791. return create_ast_node<ResultColumn>();
  792. // If we match an identifier now, we don't know whether it is a table-name of the form "table-name.*", or if it is the start of a
  793. // column-name-expression, until we try to parse the asterisk. So if we consume an identifier and a period, but don't find an
  794. // asterisk, hold onto that information to form a column-name-expression later.
  795. Optional<DeprecatedString> table_name;
  796. bool parsed_period = false;
  797. if (match(TokenType::Identifier)) {
  798. table_name = consume().value();
  799. parsed_period = consume_if(TokenType::Period);
  800. if (parsed_period && consume_if(TokenType::Asterisk))
  801. return create_ast_node<ResultColumn>(table_name.release_value());
  802. }
  803. auto expression = !table_name.has_value()
  804. ? parse_expression()
  805. : static_cast<NonnullRefPtr<Expression>>(*parse_column_name_expression(move(table_name), parsed_period));
  806. DeprecatedString column_alias;
  807. if (consume_if(TokenType::As) || match(TokenType::Identifier))
  808. column_alias = consume(TokenType::Identifier).value();
  809. return create_ast_node<ResultColumn>(move(expression), move(column_alias));
  810. }
  811. NonnullRefPtr<TableOrSubquery> Parser::parse_table_or_subquery()
  812. {
  813. if (++m_parser_state.m_current_subquery_depth > Limits::maximum_subquery_depth)
  814. syntax_error(DeprecatedString::formatted("Exceeded maximum subquery depth of {}", Limits::maximum_subquery_depth));
  815. ScopeGuard guard([&]() { --m_parser_state.m_current_subquery_depth; });
  816. // https://sqlite.org/syntax/table-or-subquery.html
  817. if (match(TokenType::Identifier)) {
  818. DeprecatedString schema_name;
  819. DeprecatedString table_name;
  820. parse_schema_and_table_name(schema_name, table_name);
  821. DeprecatedString table_alias;
  822. if (consume_if(TokenType::As) || match(TokenType::Identifier))
  823. table_alias = consume(TokenType::Identifier).value();
  824. return create_ast_node<TableOrSubquery>(move(schema_name), move(table_name), move(table_alias));
  825. }
  826. // FIXME: Parse join-clause.
  827. Vector<NonnullRefPtr<TableOrSubquery>> subqueries;
  828. parse_comma_separated_list(true, [&]() { subqueries.append(parse_table_or_subquery()); });
  829. return create_ast_node<TableOrSubquery>(move(subqueries));
  830. }
  831. NonnullRefPtr<OrderingTerm> Parser::parse_ordering_term()
  832. {
  833. // https://sqlite.org/syntax/ordering-term.html
  834. auto expression = parse_expression();
  835. DeprecatedString collation_name;
  836. if (is<CollateExpression>(*expression)) {
  837. auto const& collate = static_cast<CollateExpression const&>(*expression);
  838. collation_name = collate.collation_name();
  839. expression = collate.expression();
  840. } else if (consume_if(TokenType::Collate)) {
  841. collation_name = consume(TokenType::Identifier).value();
  842. }
  843. Order order = consume_if(TokenType::Desc) ? Order::Descending : Order::Ascending;
  844. consume_if(TokenType::Asc); // ASC is the default, so ignore it if specified.
  845. Nulls nulls = order == Order::Ascending ? Nulls::First : Nulls::Last;
  846. if (consume_if(TokenType::Nulls)) {
  847. if (consume_if(TokenType::First))
  848. nulls = Nulls::First;
  849. else if (consume_if(TokenType::Last))
  850. nulls = Nulls::Last;
  851. else
  852. expected("FIRST or LAST"sv);
  853. }
  854. return create_ast_node<OrderingTerm>(move(expression), move(collation_name), order, nulls);
  855. }
  856. void Parser::parse_schema_and_table_name(DeprecatedString& schema_name, DeprecatedString& table_name)
  857. {
  858. DeprecatedString schema_or_table_name = consume(TokenType::Identifier).value();
  859. if (consume_if(TokenType::Period)) {
  860. schema_name = move(schema_or_table_name);
  861. table_name = consume(TokenType::Identifier).value();
  862. } else {
  863. table_name = move(schema_or_table_name);
  864. }
  865. }
  866. ConflictResolution Parser::parse_conflict_resolution()
  867. {
  868. // https://sqlite.org/lang_conflict.html
  869. if (consume_if(TokenType::Or)) {
  870. if (consume_if(TokenType::Abort))
  871. return ConflictResolution::Abort;
  872. if (consume_if(TokenType::Fail))
  873. return ConflictResolution::Fail;
  874. if (consume_if(TokenType::Ignore))
  875. return ConflictResolution::Ignore;
  876. if (consume_if(TokenType::Replace))
  877. return ConflictResolution::Replace;
  878. if (consume_if(TokenType::Rollback))
  879. return ConflictResolution::Rollback;
  880. expected("ABORT, FAIL, IGNORE, REPLACE, or ROLLBACK"sv);
  881. }
  882. return ConflictResolution::Abort;
  883. }
  884. Token Parser::consume()
  885. {
  886. auto old_token = m_parser_state.m_token;
  887. m_parser_state.m_token = m_parser_state.m_lexer.next();
  888. return old_token;
  889. }
  890. Token Parser::consume(TokenType expected_type)
  891. {
  892. if (!match(expected_type)) {
  893. expected(Token::name(expected_type));
  894. }
  895. return consume();
  896. }
  897. bool Parser::consume_if(TokenType expected_type)
  898. {
  899. if (!match(expected_type))
  900. return false;
  901. consume();
  902. return true;
  903. }
  904. bool Parser::match(TokenType type) const
  905. {
  906. return m_parser_state.m_token.type() == type;
  907. }
  908. void Parser::expected(StringView what)
  909. {
  910. syntax_error(DeprecatedString::formatted("Unexpected token {}, expected {}", m_parser_state.m_token.name(), what));
  911. }
  912. void Parser::syntax_error(DeprecatedString message)
  913. {
  914. m_parser_state.m_errors.append({ move(message), position() });
  915. }
  916. SourcePosition Parser::position() const
  917. {
  918. return m_parser_state.m_token.start_position();
  919. }
  920. Parser::ParserState::ParserState(Lexer lexer)
  921. : m_lexer(move(lexer))
  922. , m_token(m_lexer.next())
  923. {
  924. }
  925. }