Parser.cpp 39 KB

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