Parser.cpp 41 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156
  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. NonnullRefPtrVector<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. NonnullRefPtrVector<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 = dynamic_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. NonnullRefPtrVector<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. NonnullRefPtrVector<ResultColumn> result_column_list;
  259. parse_comma_separated_list(false, [&]() { result_column_list.append(parse_result_column()); });
  260. NonnullRefPtrVector<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. NonnullRefPtrVector<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. NonnullRefPtrVector<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. NonnullRefPtrVector<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_chained_expression())
  341. return expression.release_nonnull();
  342. if (auto expression = parse_cast_expression())
  343. return expression.release_nonnull();
  344. if (auto expression = parse_case_expression())
  345. return expression.release_nonnull();
  346. if (auto expression = parse_exists_expression(false))
  347. return expression.release_nonnull();
  348. expected("Primary Expression"sv);
  349. consume();
  350. return create_ast_node<ErrorExpression>();
  351. }
  352. NonnullRefPtr<Expression> Parser::parse_secondary_expression(NonnullRefPtr<Expression> primary)
  353. {
  354. if (auto expression = parse_binary_operator_expression(primary))
  355. return expression.release_nonnull();
  356. if (auto expression = parse_collate_expression(primary))
  357. return expression.release_nonnull();
  358. if (auto expression = parse_is_expression(primary))
  359. return expression.release_nonnull();
  360. bool invert_expression = false;
  361. if (consume_if(TokenType::Not))
  362. invert_expression = true;
  363. if (auto expression = parse_match_expression(primary, invert_expression))
  364. return expression.release_nonnull();
  365. if (auto expression = parse_null_expression(primary, invert_expression))
  366. return expression.release_nonnull();
  367. if (auto expression = parse_between_expression(primary, invert_expression))
  368. return expression.release_nonnull();
  369. if (auto expression = parse_in_expression(primary, invert_expression))
  370. return expression.release_nonnull();
  371. expected("Secondary Expression"sv);
  372. consume();
  373. return create_ast_node<ErrorExpression>();
  374. }
  375. bool Parser::match_secondary_expression() const
  376. {
  377. return match(TokenType::Not)
  378. || match(TokenType::DoublePipe)
  379. || match(TokenType::Asterisk)
  380. || match(TokenType::Divide)
  381. || match(TokenType::Modulus)
  382. || match(TokenType::Plus)
  383. || match(TokenType::Minus)
  384. || match(TokenType::ShiftLeft)
  385. || match(TokenType::ShiftRight)
  386. || match(TokenType::Ampersand)
  387. || match(TokenType::Pipe)
  388. || match(TokenType::LessThan)
  389. || match(TokenType::LessThanEquals)
  390. || match(TokenType::GreaterThan)
  391. || match(TokenType::GreaterThanEquals)
  392. || match(TokenType::Equals)
  393. || match(TokenType::EqualsEquals)
  394. || match(TokenType::NotEquals1)
  395. || match(TokenType::NotEquals2)
  396. || match(TokenType::And)
  397. || match(TokenType::Or)
  398. || match(TokenType::Collate)
  399. || match(TokenType::Is)
  400. || match(TokenType::Like)
  401. || match(TokenType::Glob)
  402. || match(TokenType::Match)
  403. || match(TokenType::Regexp)
  404. || match(TokenType::Isnull)
  405. || match(TokenType::Notnull)
  406. || match(TokenType::Between)
  407. || match(TokenType::In);
  408. }
  409. RefPtr<Expression> Parser::parse_literal_value_expression()
  410. {
  411. if (match(TokenType::NumericLiteral)) {
  412. auto value = consume().double_value();
  413. return create_ast_node<NumericLiteral>(value);
  414. }
  415. if (match(TokenType::StringLiteral)) {
  416. // TODO: Should the surrounding ' ' be removed here?
  417. auto value = consume().value();
  418. return create_ast_node<StringLiteral>(value);
  419. }
  420. if (match(TokenType::BlobLiteral)) {
  421. // TODO: Should the surrounding x' ' be removed here?
  422. auto value = consume().value();
  423. return create_ast_node<BlobLiteral>(value);
  424. }
  425. if (consume_if(TokenType::Null))
  426. return create_ast_node<NullLiteral>();
  427. return {};
  428. }
  429. // https://sqlite.org/lang_expr.html#varparam
  430. RefPtr<Expression> Parser::parse_bind_parameter_expression()
  431. {
  432. // FIXME: Support ?NNN, :AAAA, @AAAA, and $AAAA forms.
  433. if (consume_if(TokenType::Placeholder)) {
  434. auto parameter = m_parser_state.m_bound_parameters;
  435. if (++m_parser_state.m_bound_parameters > Limits::maximum_bound_parameters)
  436. syntax_error(DeprecatedString::formatted("Exceeded maximum number of bound parameters {}", Limits::maximum_bound_parameters));
  437. return create_ast_node<Placeholder>(parameter);
  438. }
  439. return {};
  440. }
  441. RefPtr<Expression> Parser::parse_column_name_expression(DeprecatedString with_parsed_identifier, bool with_parsed_period)
  442. {
  443. if (with_parsed_identifier.is_null() && !match(TokenType::Identifier))
  444. return {};
  445. DeprecatedString first_identifier;
  446. if (with_parsed_identifier.is_null())
  447. first_identifier = consume(TokenType::Identifier).value();
  448. else
  449. first_identifier = move(with_parsed_identifier);
  450. DeprecatedString schema_name;
  451. DeprecatedString table_name;
  452. DeprecatedString column_name;
  453. if (with_parsed_period || consume_if(TokenType::Period)) {
  454. DeprecatedString second_identifier = consume(TokenType::Identifier).value();
  455. if (consume_if(TokenType::Period)) {
  456. schema_name = move(first_identifier);
  457. table_name = move(second_identifier);
  458. column_name = consume(TokenType::Identifier).value();
  459. } else {
  460. table_name = move(first_identifier);
  461. column_name = move(second_identifier);
  462. }
  463. } else {
  464. column_name = move(first_identifier);
  465. }
  466. return create_ast_node<ColumnNameExpression>(move(schema_name), move(table_name), move(column_name));
  467. }
  468. RefPtr<Expression> Parser::parse_unary_operator_expression()
  469. {
  470. if (consume_if(TokenType::Minus))
  471. return create_ast_node<UnaryOperatorExpression>(UnaryOperator::Minus, parse_expression());
  472. if (consume_if(TokenType::Plus))
  473. return create_ast_node<UnaryOperatorExpression>(UnaryOperator::Plus, parse_expression());
  474. if (consume_if(TokenType::Tilde))
  475. return create_ast_node<UnaryOperatorExpression>(UnaryOperator::BitwiseNot, parse_expression());
  476. if (consume_if(TokenType::Not)) {
  477. if (match(TokenType::Exists))
  478. return parse_exists_expression(true);
  479. else
  480. return create_ast_node<UnaryOperatorExpression>(UnaryOperator::Not, parse_expression());
  481. }
  482. return {};
  483. }
  484. RefPtr<Expression> Parser::parse_binary_operator_expression(NonnullRefPtr<Expression> lhs)
  485. {
  486. if (consume_if(TokenType::DoublePipe))
  487. return create_ast_node<BinaryOperatorExpression>(BinaryOperator::Concatenate, move(lhs), parse_expression());
  488. if (consume_if(TokenType::Asterisk))
  489. return create_ast_node<BinaryOperatorExpression>(BinaryOperator::Multiplication, move(lhs), parse_expression());
  490. if (consume_if(TokenType::Divide))
  491. return create_ast_node<BinaryOperatorExpression>(BinaryOperator::Division, move(lhs), parse_expression());
  492. if (consume_if(TokenType::Modulus))
  493. return create_ast_node<BinaryOperatorExpression>(BinaryOperator::Modulo, move(lhs), parse_expression());
  494. if (consume_if(TokenType::Plus))
  495. return create_ast_node<BinaryOperatorExpression>(BinaryOperator::Plus, move(lhs), parse_expression());
  496. if (consume_if(TokenType::Minus))
  497. return create_ast_node<BinaryOperatorExpression>(BinaryOperator::Minus, move(lhs), parse_expression());
  498. if (consume_if(TokenType::ShiftLeft))
  499. return create_ast_node<BinaryOperatorExpression>(BinaryOperator::ShiftLeft, move(lhs), parse_expression());
  500. if (consume_if(TokenType::ShiftRight))
  501. return create_ast_node<BinaryOperatorExpression>(BinaryOperator::ShiftRight, move(lhs), parse_expression());
  502. if (consume_if(TokenType::Ampersand))
  503. return create_ast_node<BinaryOperatorExpression>(BinaryOperator::BitwiseAnd, move(lhs), parse_expression());
  504. if (consume_if(TokenType::Pipe))
  505. return create_ast_node<BinaryOperatorExpression>(BinaryOperator::BitwiseOr, move(lhs), parse_expression());
  506. if (consume_if(TokenType::LessThan))
  507. return create_ast_node<BinaryOperatorExpression>(BinaryOperator::LessThan, move(lhs), parse_expression());
  508. if (consume_if(TokenType::LessThanEquals))
  509. return create_ast_node<BinaryOperatorExpression>(BinaryOperator::LessThanEquals, move(lhs), parse_expression());
  510. if (consume_if(TokenType::GreaterThan))
  511. return create_ast_node<BinaryOperatorExpression>(BinaryOperator::GreaterThan, move(lhs), parse_expression());
  512. if (consume_if(TokenType::GreaterThanEquals))
  513. return create_ast_node<BinaryOperatorExpression>(BinaryOperator::GreaterThanEquals, move(lhs), parse_expression());
  514. if (consume_if(TokenType::Equals) || consume_if(TokenType::EqualsEquals))
  515. return create_ast_node<BinaryOperatorExpression>(BinaryOperator::Equals, move(lhs), parse_expression());
  516. if (consume_if(TokenType::NotEquals1) || consume_if(TokenType::NotEquals2))
  517. return create_ast_node<BinaryOperatorExpression>(BinaryOperator::NotEquals, move(lhs), parse_expression());
  518. if (consume_if(TokenType::And))
  519. return create_ast_node<BinaryOperatorExpression>(BinaryOperator::And, move(lhs), parse_expression());
  520. if (consume_if(TokenType::Or))
  521. return create_ast_node<BinaryOperatorExpression>(BinaryOperator::Or, move(lhs), parse_expression());
  522. return {};
  523. }
  524. RefPtr<Expression> Parser::parse_chained_expression()
  525. {
  526. if (!consume_if(TokenType::ParenOpen))
  527. return {};
  528. if (match(TokenType::Select))
  529. return parse_exists_expression(false, TokenType::Select);
  530. NonnullRefPtrVector<Expression> expressions;
  531. parse_comma_separated_list(false, [&]() { expressions.append(parse_expression()); });
  532. consume(TokenType::ParenClose);
  533. return create_ast_node<ChainedExpression>(move(expressions));
  534. }
  535. RefPtr<Expression> Parser::parse_cast_expression()
  536. {
  537. if (!match(TokenType::Cast))
  538. return {};
  539. consume(TokenType::Cast);
  540. consume(TokenType::ParenOpen);
  541. auto expression = parse_expression();
  542. consume(TokenType::As);
  543. auto type_name = parse_type_name();
  544. consume(TokenType::ParenClose);
  545. return create_ast_node<CastExpression>(move(expression), move(type_name));
  546. }
  547. RefPtr<Expression> Parser::parse_case_expression()
  548. {
  549. if (!match(TokenType::Case))
  550. return {};
  551. consume();
  552. RefPtr<Expression> case_expression;
  553. if (!match(TokenType::When)) {
  554. case_expression = parse_expression();
  555. }
  556. Vector<CaseExpression::WhenThenClause> when_then_clauses;
  557. do {
  558. consume(TokenType::When);
  559. auto when = parse_expression();
  560. consume(TokenType::Then);
  561. auto then = parse_expression();
  562. when_then_clauses.append({ move(when), move(then) });
  563. if (!match(TokenType::When))
  564. break;
  565. } while (!match(TokenType::Eof));
  566. RefPtr<Expression> else_expression;
  567. if (consume_if(TokenType::Else))
  568. else_expression = parse_expression();
  569. consume(TokenType::End);
  570. return create_ast_node<CaseExpression>(move(case_expression), move(when_then_clauses), move(else_expression));
  571. }
  572. RefPtr<Expression> Parser::parse_exists_expression(bool invert_expression, TokenType opening_token)
  573. {
  574. VERIFY((opening_token == TokenType::Exists) || (opening_token == TokenType::Select));
  575. if ((opening_token == TokenType::Exists) && !consume_if(TokenType::Exists))
  576. return {};
  577. if (opening_token == TokenType::Exists)
  578. consume(TokenType::ParenOpen);
  579. auto select_statement = parse_select_statement({});
  580. consume(TokenType::ParenClose);
  581. return create_ast_node<ExistsExpression>(move(select_statement), invert_expression);
  582. }
  583. RefPtr<Expression> Parser::parse_collate_expression(NonnullRefPtr<Expression> expression)
  584. {
  585. if (!match(TokenType::Collate))
  586. return {};
  587. consume();
  588. DeprecatedString collation_name = consume(TokenType::Identifier).value();
  589. return create_ast_node<CollateExpression>(move(expression), move(collation_name));
  590. }
  591. RefPtr<Expression> Parser::parse_is_expression(NonnullRefPtr<Expression> expression)
  592. {
  593. if (!match(TokenType::Is))
  594. return {};
  595. consume();
  596. bool invert_expression = false;
  597. if (match(TokenType::Not)) {
  598. consume();
  599. invert_expression = true;
  600. }
  601. auto rhs = parse_expression();
  602. return create_ast_node<IsExpression>(move(expression), move(rhs), invert_expression);
  603. }
  604. RefPtr<Expression> Parser::parse_match_expression(NonnullRefPtr<Expression> lhs, bool invert_expression)
  605. {
  606. auto parse_escape = [this]() {
  607. RefPtr<Expression> escape;
  608. if (consume_if(TokenType::Escape)) {
  609. escape = parse_expression();
  610. }
  611. return escape;
  612. };
  613. if (consume_if(TokenType::Like)) {
  614. NonnullRefPtr<Expression> rhs = parse_expression();
  615. RefPtr<Expression> escape = parse_escape();
  616. return create_ast_node<MatchExpression>(MatchOperator::Like, move(lhs), move(rhs), move(escape), invert_expression);
  617. }
  618. if (consume_if(TokenType::Glob)) {
  619. NonnullRefPtr<Expression> rhs = parse_expression();
  620. RefPtr<Expression> escape = parse_escape();
  621. return create_ast_node<MatchExpression>(MatchOperator::Glob, move(lhs), move(rhs), move(escape), invert_expression);
  622. }
  623. if (consume_if(TokenType::Match)) {
  624. NonnullRefPtr<Expression> rhs = parse_expression();
  625. RefPtr<Expression> escape = parse_escape();
  626. return create_ast_node<MatchExpression>(MatchOperator::Match, move(lhs), move(rhs), move(escape), invert_expression);
  627. }
  628. if (consume_if(TokenType::Regexp)) {
  629. NonnullRefPtr<Expression> rhs = parse_expression();
  630. RefPtr<Expression> escape = parse_escape();
  631. return create_ast_node<MatchExpression>(MatchOperator::Regexp, move(lhs), move(rhs), move(escape), invert_expression);
  632. }
  633. return {};
  634. }
  635. RefPtr<Expression> Parser::parse_null_expression(NonnullRefPtr<Expression> expression, bool invert_expression)
  636. {
  637. if (!match(TokenType::Isnull) && !match(TokenType::Notnull) && !(invert_expression && match(TokenType::Null)))
  638. return {};
  639. auto type = consume().type();
  640. invert_expression |= (type == TokenType::Notnull);
  641. return create_ast_node<NullExpression>(move(expression), invert_expression);
  642. }
  643. RefPtr<Expression> Parser::parse_between_expression(NonnullRefPtr<Expression> expression, bool invert_expression)
  644. {
  645. if (!match(TokenType::Between))
  646. return {};
  647. consume();
  648. auto nested = parse_expression();
  649. if (!is<BinaryOperatorExpression>(*nested)) {
  650. expected("Binary Expression"sv);
  651. return create_ast_node<ErrorExpression>();
  652. }
  653. auto const& binary_expression = static_cast<BinaryOperatorExpression const&>(*nested);
  654. if (binary_expression.type() != BinaryOperator::And) {
  655. expected("AND Expression"sv);
  656. return create_ast_node<ErrorExpression>();
  657. }
  658. return create_ast_node<BetweenExpression>(move(expression), binary_expression.lhs(), binary_expression.rhs(), invert_expression);
  659. }
  660. RefPtr<Expression> Parser::parse_in_expression(NonnullRefPtr<Expression> expression, bool invert_expression)
  661. {
  662. if (!match(TokenType::In))
  663. return {};
  664. consume();
  665. if (consume_if(TokenType::ParenOpen)) {
  666. if (match(TokenType::Select)) {
  667. auto select_statement = parse_select_statement({});
  668. return create_ast_node<InSelectionExpression>(move(expression), move(select_statement), invert_expression);
  669. }
  670. // FIXME: Consolidate this with parse_chained_expression(). That method consumes the opening paren as
  671. // well, and also requires at least one expression (whereas this allows for an empty chain).
  672. NonnullRefPtrVector<Expression> expressions;
  673. if (!match(TokenType::ParenClose))
  674. parse_comma_separated_list(false, [&]() { expressions.append(parse_expression()); });
  675. consume(TokenType::ParenClose);
  676. auto chain = create_ast_node<ChainedExpression>(move(expressions));
  677. return create_ast_node<InChainedExpression>(move(expression), move(chain), invert_expression);
  678. }
  679. DeprecatedString schema_name;
  680. DeprecatedString table_name;
  681. parse_schema_and_table_name(schema_name, table_name);
  682. if (match(TokenType::ParenOpen)) {
  683. // FIXME: Parse "table-function".
  684. return {};
  685. }
  686. return create_ast_node<InTableExpression>(move(expression), move(schema_name), move(table_name), invert_expression);
  687. }
  688. NonnullRefPtr<ColumnDefinition> Parser::parse_column_definition()
  689. {
  690. // https://sqlite.org/syntax/column-def.html
  691. auto name = consume(TokenType::Identifier).value();
  692. auto type_name = match(TokenType::Identifier)
  693. ? parse_type_name()
  694. // https://www.sqlite.org/datatype3.html: If no type is specified then the column has affinity BLOB.
  695. : create_ast_node<TypeName>("BLOB", NonnullRefPtrVector<SignedNumber> {});
  696. // FIXME: Parse "column-constraint".
  697. return create_ast_node<ColumnDefinition>(move(name), move(type_name));
  698. }
  699. NonnullRefPtr<TypeName> Parser::parse_type_name()
  700. {
  701. // https: //sqlite.org/syntax/type-name.html
  702. auto name = consume(TokenType::Identifier).value();
  703. NonnullRefPtrVector<SignedNumber> signed_numbers;
  704. if (consume_if(TokenType::ParenOpen)) {
  705. signed_numbers.append(parse_signed_number());
  706. if (consume_if(TokenType::Comma))
  707. signed_numbers.append(parse_signed_number());
  708. consume(TokenType::ParenClose);
  709. }
  710. return create_ast_node<TypeName>(move(name), move(signed_numbers));
  711. }
  712. NonnullRefPtr<SignedNumber> Parser::parse_signed_number()
  713. {
  714. // https://sqlite.org/syntax/signed-number.html
  715. bool is_positive = true;
  716. if (consume_if(TokenType::Plus))
  717. is_positive = true;
  718. else if (consume_if(TokenType::Minus))
  719. is_positive = false;
  720. if (match(TokenType::NumericLiteral)) {
  721. auto number = consume(TokenType::NumericLiteral).double_value();
  722. return create_ast_node<SignedNumber>(is_positive ? number : (number * -1));
  723. }
  724. expected("NumericLiteral"sv);
  725. return create_ast_node<SignedNumber>(0);
  726. }
  727. NonnullRefPtr<CommonTableExpression> Parser::parse_common_table_expression()
  728. {
  729. // https://sqlite.org/syntax/common-table-expression.html
  730. auto table_name = consume(TokenType::Identifier).value();
  731. Vector<DeprecatedString> column_names;
  732. if (match(TokenType::ParenOpen))
  733. parse_comma_separated_list(true, [&]() { column_names.append(consume(TokenType::Identifier).value()); });
  734. consume(TokenType::As);
  735. consume(TokenType::ParenOpen);
  736. auto select_statement = parse_select_statement({});
  737. consume(TokenType::ParenClose);
  738. return create_ast_node<CommonTableExpression>(move(table_name), move(column_names), move(select_statement));
  739. }
  740. NonnullRefPtr<QualifiedTableName> Parser::parse_qualified_table_name()
  741. {
  742. // https://sqlite.org/syntax/qualified-table-name.html
  743. DeprecatedString schema_name;
  744. DeprecatedString table_name;
  745. parse_schema_and_table_name(schema_name, table_name);
  746. DeprecatedString alias;
  747. if (consume_if(TokenType::As))
  748. alias = consume(TokenType::Identifier).value();
  749. // Note: The qualified-table-name spec may include an "INDEXED BY index-name" or "NOT INDEXED" clause. This is a SQLite extension
  750. // "designed to help detect undesirable query plan changes during regression testing", and "application developers are admonished
  751. // to omit all use of INDEXED BY during application design, implementation, testing, and tuning". Our implementation purposefully
  752. // omits parsing INDEXED BY for now until there is good reason to add support.
  753. return create_ast_node<QualifiedTableName>(move(schema_name), move(table_name), move(alias));
  754. }
  755. NonnullRefPtr<ReturningClause> Parser::parse_returning_clause()
  756. {
  757. // https://sqlite.org/syntax/returning-clause.html
  758. consume(TokenType::Returning);
  759. if (consume_if(TokenType::Asterisk))
  760. return create_ast_node<ReturningClause>();
  761. Vector<ReturningClause::ColumnClause> columns;
  762. parse_comma_separated_list(false, [&]() {
  763. auto expression = parse_expression();
  764. DeprecatedString column_alias;
  765. if (consume_if(TokenType::As) || match(TokenType::Identifier))
  766. column_alias = consume(TokenType::Identifier).value();
  767. columns.append({ move(expression), move(column_alias) });
  768. });
  769. return create_ast_node<ReturningClause>(move(columns));
  770. }
  771. NonnullRefPtr<ResultColumn> Parser::parse_result_column()
  772. {
  773. // https://sqlite.org/syntax/result-column.html
  774. if (consume_if(TokenType::Asterisk))
  775. return create_ast_node<ResultColumn>();
  776. // 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
  777. // column-name-expression, until we try to parse the asterisk. So if we consume an identifier and a period, but don't find an
  778. // asterisk, hold onto that information to form a column-name-expression later.
  779. DeprecatedString table_name;
  780. bool parsed_period = false;
  781. if (match(TokenType::Identifier)) {
  782. table_name = consume().value();
  783. parsed_period = consume_if(TokenType::Period);
  784. if (parsed_period && consume_if(TokenType::Asterisk))
  785. return create_ast_node<ResultColumn>(move(table_name));
  786. }
  787. auto expression = table_name.is_null()
  788. ? parse_expression()
  789. : static_cast<NonnullRefPtr<Expression>>(*parse_column_name_expression(move(table_name), parsed_period));
  790. DeprecatedString column_alias;
  791. if (consume_if(TokenType::As) || match(TokenType::Identifier))
  792. column_alias = consume(TokenType::Identifier).value();
  793. return create_ast_node<ResultColumn>(move(expression), move(column_alias));
  794. }
  795. NonnullRefPtr<TableOrSubquery> Parser::parse_table_or_subquery()
  796. {
  797. if (++m_parser_state.m_current_subquery_depth > Limits::maximum_subquery_depth)
  798. syntax_error(DeprecatedString::formatted("Exceeded maximum subquery depth of {}", Limits::maximum_subquery_depth));
  799. ScopeGuard guard([&]() { --m_parser_state.m_current_subquery_depth; });
  800. // https://sqlite.org/syntax/table-or-subquery.html
  801. if (match(TokenType::Identifier)) {
  802. DeprecatedString schema_name;
  803. DeprecatedString table_name;
  804. parse_schema_and_table_name(schema_name, table_name);
  805. DeprecatedString table_alias;
  806. if (consume_if(TokenType::As) || match(TokenType::Identifier))
  807. table_alias = consume(TokenType::Identifier).value();
  808. return create_ast_node<TableOrSubquery>(move(schema_name), move(table_name), move(table_alias));
  809. }
  810. // FIXME: Parse join-clause.
  811. NonnullRefPtrVector<TableOrSubquery> subqueries;
  812. parse_comma_separated_list(true, [&]() { subqueries.append(parse_table_or_subquery()); });
  813. return create_ast_node<TableOrSubquery>(move(subqueries));
  814. }
  815. NonnullRefPtr<OrderingTerm> Parser::parse_ordering_term()
  816. {
  817. // https://sqlite.org/syntax/ordering-term.html
  818. auto expression = parse_expression();
  819. DeprecatedString collation_name;
  820. if (is<CollateExpression>(*expression)) {
  821. auto const& collate = static_cast<CollateExpression const&>(*expression);
  822. collation_name = collate.collation_name();
  823. expression = collate.expression();
  824. } else if (consume_if(TokenType::Collate)) {
  825. collation_name = consume(TokenType::Identifier).value();
  826. }
  827. Order order = consume_if(TokenType::Desc) ? Order::Descending : Order::Ascending;
  828. consume_if(TokenType::Asc); // ASC is the default, so ignore it if specified.
  829. Nulls nulls = order == Order::Ascending ? Nulls::First : Nulls::Last;
  830. if (consume_if(TokenType::Nulls)) {
  831. if (consume_if(TokenType::First))
  832. nulls = Nulls::First;
  833. else if (consume_if(TokenType::Last))
  834. nulls = Nulls::Last;
  835. else
  836. expected("FIRST or LAST"sv);
  837. }
  838. return create_ast_node<OrderingTerm>(move(expression), move(collation_name), order, nulls);
  839. }
  840. void Parser::parse_schema_and_table_name(DeprecatedString& schema_name, DeprecatedString& table_name)
  841. {
  842. DeprecatedString schema_or_table_name = consume(TokenType::Identifier).value();
  843. if (consume_if(TokenType::Period)) {
  844. schema_name = move(schema_or_table_name);
  845. table_name = consume(TokenType::Identifier).value();
  846. } else {
  847. table_name = move(schema_or_table_name);
  848. }
  849. }
  850. ConflictResolution Parser::parse_conflict_resolution()
  851. {
  852. // https://sqlite.org/lang_conflict.html
  853. if (consume_if(TokenType::Or)) {
  854. if (consume_if(TokenType::Abort))
  855. return ConflictResolution::Abort;
  856. if (consume_if(TokenType::Fail))
  857. return ConflictResolution::Fail;
  858. if (consume_if(TokenType::Ignore))
  859. return ConflictResolution::Ignore;
  860. if (consume_if(TokenType::Replace))
  861. return ConflictResolution::Replace;
  862. if (consume_if(TokenType::Rollback))
  863. return ConflictResolution::Rollback;
  864. expected("ABORT, FAIL, IGNORE, REPLACE, or ROLLBACK"sv);
  865. }
  866. return ConflictResolution::Abort;
  867. }
  868. Token Parser::consume()
  869. {
  870. auto old_token = m_parser_state.m_token;
  871. m_parser_state.m_token = m_parser_state.m_lexer.next();
  872. return old_token;
  873. }
  874. Token Parser::consume(TokenType expected_type)
  875. {
  876. if (!match(expected_type)) {
  877. expected(Token::name(expected_type));
  878. }
  879. return consume();
  880. }
  881. bool Parser::consume_if(TokenType expected_type)
  882. {
  883. if (!match(expected_type))
  884. return false;
  885. consume();
  886. return true;
  887. }
  888. bool Parser::match(TokenType type) const
  889. {
  890. return m_parser_state.m_token.type() == type;
  891. }
  892. void Parser::expected(StringView what)
  893. {
  894. syntax_error(DeprecatedString::formatted("Unexpected token {}, expected {}", m_parser_state.m_token.name(), what));
  895. }
  896. void Parser::syntax_error(DeprecatedString message)
  897. {
  898. m_parser_state.m_errors.append({ move(message), position() });
  899. }
  900. SourcePosition Parser::position() const
  901. {
  902. return m_parser_state.m_token.start_position();
  903. }
  904. Parser::ParserState::ParserState(Lexer lexer)
  905. : m_lexer(move(lexer))
  906. , m_token(m_lexer.next())
  907. {
  908. }
  909. }