Parser.cpp 31 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938939940941942943944945946947948949950951952953954955956957958959960961962963964965966967968969970971972973974975976977978979980981982983984985986987988989990991992993994995996997998999100010011002100310041005100610071008100910101011101210131014101510161017101810191020102110221023102410251026102710281029103010311032103310341035103610371038103910401041104210431044104510461047104810491050
  1. /*
  2. * Copyright (c) 2020, the SerenityOS developers.
  3. * All rights reserved.
  4. *
  5. * Redistribution and use in source and binary forms, with or without
  6. * modification, are permitted provided that the following conditions are met:
  7. *
  8. * 1. Redistributions of source code must retain the above copyright notice, this
  9. * list of conditions and the following disclaimer.
  10. *
  11. * 2. Redistributions in binary form must reproduce the above copyright notice,
  12. * this list of conditions and the following disclaimer in the documentation
  13. * and/or other materials provided with the distribution.
  14. *
  15. * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
  16. * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  17. * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
  18. * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
  19. * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  20. * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
  21. * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  22. * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
  23. * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  24. * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  25. */
  26. #include "Parser.h"
  27. #include <ctype.h>
  28. #include <stdio.h>
  29. #include <unistd.h>
  30. char Parser::peek()
  31. {
  32. if (m_offset == m_input.length())
  33. return 0;
  34. ASSERT(m_offset < m_input.length());
  35. return m_input[m_offset];
  36. }
  37. char Parser::consume()
  38. {
  39. auto ch = peek();
  40. ++m_offset;
  41. return ch;
  42. }
  43. void Parser::putback()
  44. {
  45. ASSERT(m_offset > 0);
  46. --m_offset;
  47. }
  48. bool Parser::expect(char ch)
  49. {
  50. return expect(StringView { &ch, 1 });
  51. }
  52. bool Parser::expect(const StringView& expected)
  53. {
  54. if (expected.length() + m_offset > m_input.length())
  55. return false;
  56. for (size_t i = 0; i < expected.length(); ++i) {
  57. if (peek() != expected[i])
  58. return false;
  59. consume();
  60. }
  61. return true;
  62. }
  63. template<typename A, typename... Args>
  64. NonnullRefPtr<A> Parser::create(Args... args)
  65. {
  66. return adopt(*new A(AST::Position { m_rule_start_offsets.last(), m_offset }, args...));
  67. }
  68. [[nodiscard]] OwnPtr<Parser::ScopedOffset> Parser::push_start()
  69. {
  70. return make<ScopedOffset>(m_rule_start_offsets, m_offset);
  71. }
  72. static constexpr bool is_whitespace(char c)
  73. {
  74. return c == ' ' || c == '\t';
  75. }
  76. static constexpr bool is_word_character(char c)
  77. {
  78. return (c <= '9' && c >= '0') || (c <= 'Z' && c >= 'A') || (c <= 'z' && c >= 'a') || c == '_';
  79. }
  80. static constexpr bool is_digit(char c)
  81. {
  82. return c <= '9' && c >= '0';
  83. }
  84. static constexpr auto is_not(char c)
  85. {
  86. return [c](char ch) { return ch != c; };
  87. }
  88. static constexpr auto is_any_of(StringView s)
  89. {
  90. return [s](char ch) { return s.contains(ch); };
  91. }
  92. static inline char to_byte(char a, char b)
  93. {
  94. char buf[3] { a, b, 0 };
  95. return strtol(buf, nullptr, 16);
  96. }
  97. RefPtr<AST::Node> Parser::parse()
  98. {
  99. m_offset = 0;
  100. auto toplevel = parse_toplevel();
  101. if (m_offset < m_input.length()) {
  102. // Parsing stopped midway, this is a syntax error.
  103. auto error_start = push_start();
  104. m_offset = m_input.length();
  105. auto syntax_error_node = create<AST::SyntaxError>("Unexpected tokens past the end");
  106. if (toplevel)
  107. return create<AST::Join>(move(toplevel), move(syntax_error_node));
  108. return syntax_error_node;
  109. }
  110. return toplevel;
  111. }
  112. RefPtr<AST::Node> Parser::parse_toplevel()
  113. {
  114. auto rule_start = push_start();
  115. if (auto sequence = parse_sequence())
  116. return create<AST::Execute>(sequence);
  117. return nullptr;
  118. }
  119. RefPtr<AST::Node> Parser::parse_sequence()
  120. {
  121. consume_while(is_any_of(" \t\n;")); // ignore whitespaces or terminators without effect.
  122. auto rule_start = push_start();
  123. auto var_decls = parse_variable_decls();
  124. switch (peek()) {
  125. case '}':
  126. return var_decls;
  127. case ';':
  128. case '\n': {
  129. if (!var_decls)
  130. break;
  131. consume_while(is_any_of("\n;"));
  132. auto rest = parse_sequence();
  133. if (rest)
  134. return create<AST::Sequence>(move(var_decls), move(rest));
  135. return var_decls;
  136. }
  137. default:
  138. break;
  139. }
  140. auto first = parse_or_logical_sequence();
  141. if (!first)
  142. return var_decls;
  143. if (var_decls)
  144. first = create<AST::Sequence>(move(var_decls), move(first));
  145. consume_while(is_whitespace);
  146. switch (peek()) {
  147. case ';':
  148. case '\n':
  149. consume_while(is_any_of("\n;"));
  150. if (auto expr = parse_sequence()) {
  151. return create<AST::Sequence>(move(first), move(expr)); // Sequence
  152. }
  153. return first;
  154. case '&': {
  155. auto execute_pipe_seq = first->would_execute() ? first : static_cast<RefPtr<AST::Node>>(create<AST::Execute>(first));
  156. consume();
  157. auto bg = create<AST::Background>(move(first)); // Execute Background
  158. if (auto rest = parse_sequence())
  159. return create<AST::Sequence>(move(bg), move(rest)); // Sequence Background Sequence
  160. return bg;
  161. }
  162. default:
  163. return first;
  164. }
  165. }
  166. RefPtr<AST::Node> Parser::parse_variable_decls()
  167. {
  168. auto rule_start = push_start();
  169. consume_while(is_whitespace);
  170. auto offset_before_name = m_offset;
  171. auto var_name = consume_while(is_word_character);
  172. if (var_name.is_empty())
  173. return nullptr;
  174. if (!expect('=')) {
  175. m_offset = offset_before_name;
  176. return nullptr;
  177. }
  178. auto name_expr = create<AST::BarewordLiteral>(move(var_name));
  179. auto start = push_start();
  180. auto expression = parse_expression();
  181. if (!expression || expression->is_syntax_error()) {
  182. m_offset = start->offset;
  183. if (peek() == '(') {
  184. consume();
  185. auto command = parse_pipe_sequence();
  186. if (!command)
  187. m_offset = start->offset;
  188. else if (!expect(')'))
  189. command->set_is_syntax_error(*create<AST::SyntaxError>("Expected a terminating close paren"));
  190. expression = command;
  191. }
  192. }
  193. if (!expression) {
  194. if (is_whitespace(peek())) {
  195. auto string_start = push_start();
  196. expression = create<AST::StringLiteral>("");
  197. } else {
  198. m_offset = offset_before_name;
  199. return nullptr;
  200. }
  201. }
  202. Vector<AST::VariableDeclarations::Variable> variables;
  203. variables.append({ move(name_expr), expression.release_nonnull() });
  204. if (consume_while(is_whitespace).is_empty())
  205. return create<AST::VariableDeclarations>(move(variables));
  206. auto rest = parse_variable_decls();
  207. if (!rest)
  208. return create<AST::VariableDeclarations>(move(variables));
  209. ASSERT(rest->is_variable_decls());
  210. auto* rest_decl = static_cast<AST::VariableDeclarations*>(rest.ptr());
  211. variables.append(rest_decl->variables());
  212. return create<AST::VariableDeclarations>(move(variables));
  213. }
  214. RefPtr<AST::Node> Parser::parse_or_logical_sequence()
  215. {
  216. consume_while(is_whitespace);
  217. auto rule_start = push_start();
  218. auto and_sequence = parse_and_logical_sequence();
  219. if (!and_sequence)
  220. return nullptr;
  221. consume_while(is_whitespace);
  222. auto saved_offset = m_offset;
  223. if (!expect("||")) {
  224. m_offset = saved_offset;
  225. return and_sequence;
  226. }
  227. auto right_and_sequence = parse_and_logical_sequence();
  228. if (!right_and_sequence)
  229. right_and_sequence = create<AST::SyntaxError>("Expected an expression after '||'");
  230. return create<AST::Or>(move(and_sequence), move(right_and_sequence));
  231. }
  232. RefPtr<AST::Node> Parser::parse_and_logical_sequence()
  233. {
  234. consume_while(is_whitespace);
  235. auto rule_start = push_start();
  236. auto pipe_sequence = parse_pipe_sequence();
  237. if (!pipe_sequence)
  238. return nullptr;
  239. consume_while(is_whitespace);
  240. auto saved_offset = m_offset;
  241. if (!expect("&&")) {
  242. m_offset = saved_offset;
  243. return pipe_sequence;
  244. }
  245. auto right_and_sequence = parse_and_logical_sequence();
  246. if (!right_and_sequence)
  247. right_and_sequence = create<AST::SyntaxError>("Expected an expression after '&&'");
  248. return create<AST::And>(move(pipe_sequence), move(right_and_sequence));
  249. }
  250. RefPtr<AST::Node> Parser::parse_pipe_sequence()
  251. {
  252. auto rule_start = push_start();
  253. auto left = parse_control_structure();
  254. if (!left) {
  255. if (auto cmd = parse_command())
  256. left = cmd;
  257. else
  258. return nullptr;
  259. }
  260. consume_while(is_whitespace);
  261. if (peek() != '|')
  262. return left;
  263. consume();
  264. if (auto pipe_seq = parse_pipe_sequence()) {
  265. return create<AST::Pipe>(move(left), move(pipe_seq)); // Pipe
  266. }
  267. putback();
  268. return left;
  269. }
  270. RefPtr<AST::Node> Parser::parse_command()
  271. {
  272. auto rule_start = push_start();
  273. consume_while(is_whitespace);
  274. auto redir = parse_redirection();
  275. if (!redir) {
  276. auto list_expr = parse_list_expression();
  277. if (!list_expr)
  278. return nullptr;
  279. auto cast = create<AST::CastToCommand>(move(list_expr)); // Cast List Command
  280. auto next_command = parse_command();
  281. if (!next_command)
  282. return cast;
  283. return create<AST::Join>(move(cast), move(next_command)); // Join List Command
  284. }
  285. auto command = parse_command();
  286. if (!command)
  287. return redir;
  288. return create<AST::Join>(move(redir), command); // Join Command Command
  289. }
  290. RefPtr<AST::Node> Parser::parse_control_structure()
  291. {
  292. auto rule_start = push_start();
  293. consume_while(is_whitespace);
  294. if (auto for_loop = parse_for_loop())
  295. return for_loop;
  296. if (auto if_expr = parse_if_expr())
  297. return if_expr;
  298. return nullptr;
  299. }
  300. RefPtr<AST::Node> Parser::parse_for_loop()
  301. {
  302. auto rule_start = push_start();
  303. if (!expect("for")) {
  304. m_offset = rule_start->offset;
  305. return nullptr;
  306. }
  307. if (consume_while(is_any_of(" \t\n")).is_empty()) {
  308. m_offset = rule_start->offset;
  309. return nullptr;
  310. }
  311. auto variable_name = consume_while(is_word_character);
  312. Optional<size_t> in_start_position;
  313. if (variable_name.is_empty()) {
  314. variable_name = "it";
  315. } else {
  316. consume_while(is_whitespace);
  317. auto in_error_start = push_start();
  318. in_start_position = in_error_start->offset;
  319. if (!expect("in")) {
  320. auto syntax_error = create<AST::SyntaxError>("Expected 'in' after a variable name in a 'for' loop");
  321. return create<AST::ForLoop>(move(variable_name), move(syntax_error), nullptr); // ForLoop Var Iterated Block
  322. }
  323. }
  324. consume_while(is_whitespace);
  325. RefPtr<AST::Node> iterated_expression;
  326. {
  327. auto iter_error_start = push_start();
  328. iterated_expression = parse_expression();
  329. if (!iterated_expression) {
  330. auto syntax_error = create<AST::SyntaxError>("Expected an expression in 'for' loop");
  331. return create<AST::ForLoop>(move(variable_name), move(syntax_error), nullptr, move(in_start_position)); // ForLoop Var Iterated Block
  332. }
  333. }
  334. consume_while(is_any_of(" \t\n"));
  335. {
  336. auto obrace_error_start = push_start();
  337. if (!expect('{')) {
  338. auto syntax_error = create<AST::SyntaxError>("Expected an open brace '{' to start a 'for' loop body");
  339. return create<AST::ForLoop>(move(variable_name), move(iterated_expression), move(syntax_error), move(in_start_position)); // ForLoop Var Iterated Block
  340. }
  341. }
  342. auto body = parse_toplevel();
  343. {
  344. auto cbrace_error_start = push_start();
  345. if (!expect('}')) {
  346. auto error_start = push_start();
  347. RefPtr<AST::SyntaxError> syntax_error = create<AST::SyntaxError>("Expected a close brace '}' to end a 'for' loop body");
  348. if (body)
  349. body->set_is_syntax_error(*syntax_error);
  350. else
  351. body = syntax_error;
  352. }
  353. }
  354. return create<AST::ForLoop>(move(variable_name), move(iterated_expression), move(body), move(in_start_position)); // ForLoop Var Iterated Block
  355. }
  356. RefPtr<AST::Node> Parser::parse_if_expr()
  357. {
  358. auto rule_start = push_start();
  359. if (!expect("if")) {
  360. m_offset = rule_start->offset;
  361. return nullptr;
  362. }
  363. if (consume_while(is_any_of(" \t\n")).is_empty()) {
  364. m_offset = rule_start->offset;
  365. return nullptr;
  366. }
  367. RefPtr<AST::Node> condition;
  368. {
  369. auto cond_error_start = push_start();
  370. condition = parse_or_logical_sequence();
  371. if (!condition) {
  372. auto syntax_error = create<AST::SyntaxError>("Expected a logical sequence after 'if'");
  373. return create<AST::IfCond>(Optional<AST::Position> {}, move(syntax_error), nullptr, nullptr);
  374. }
  375. }
  376. auto parse_braced_toplevel = [&]() -> RefPtr<AST::Node> {
  377. {
  378. auto obrace_error_start = push_start();
  379. if (!expect('{')) {
  380. auto syntax_error = create<AST::SyntaxError>("Expected an open brace '{' to start an 'if' true branch");
  381. return syntax_error;
  382. }
  383. }
  384. auto body = parse_toplevel();
  385. {
  386. auto cbrace_error_start = push_start();
  387. if (!expect('}')) {
  388. auto error_start = push_start();
  389. RefPtr<AST::SyntaxError> syntax_error = create<AST::SyntaxError>("Expected a close brace '}' to end an 'if' true branch");
  390. if (body)
  391. body->set_is_syntax_error(*syntax_error);
  392. else
  393. body = syntax_error;
  394. }
  395. }
  396. return body;
  397. };
  398. consume_while(is_whitespace);
  399. auto true_branch = parse_braced_toplevel();
  400. if (true_branch && true_branch->is_syntax_error())
  401. return create<AST::IfCond>(Optional<AST::Position> {}, move(condition), move(true_branch), nullptr); // If expr syntax_error
  402. consume_while(is_whitespace);
  403. Optional<AST::Position> else_position;
  404. {
  405. auto else_start = push_start();
  406. if (expect("else"))
  407. else_position = AST::Position { else_start->offset, m_offset };
  408. }
  409. if (else_position.has_value()) {
  410. consume_while(is_whitespace);
  411. if (peek() == '{') {
  412. auto false_branch = parse_braced_toplevel();
  413. return create<AST::IfCond>(else_position, move(condition), move(true_branch), move(false_branch)); // If expr true_branch Else false_branch
  414. }
  415. auto else_if_branch = parse_if_expr();
  416. return create<AST::IfCond>(else_position, move(condition), move(true_branch), move(else_if_branch)); // If expr true_branch Else If ...
  417. }
  418. return create<AST::IfCond>(else_position, move(condition), move(true_branch), nullptr); // If expr true_branch
  419. }
  420. RefPtr<AST::Node> Parser::parse_redirection()
  421. {
  422. auto rule_start = push_start();
  423. auto pipe_fd = 0;
  424. auto number = consume_while(is_digit);
  425. if (number.is_empty()) {
  426. pipe_fd = -1;
  427. } else {
  428. auto fd = number.to_int();
  429. ASSERT(fd.has_value());
  430. pipe_fd = fd.value();
  431. }
  432. switch (peek()) {
  433. case '>': {
  434. consume();
  435. if (peek() == '>') {
  436. consume();
  437. consume_while(is_whitespace);
  438. pipe_fd = pipe_fd >= 0 ? pipe_fd : STDOUT_FILENO;
  439. auto path = parse_expression();
  440. if (!path) {
  441. if (!at_end()) {
  442. // Eat a character and hope the problem goes away
  443. consume();
  444. }
  445. return create<AST::SyntaxError>("Expected a path");
  446. }
  447. return create<AST::WriteAppendRedirection>(pipe_fd, move(path)); // Redirection WriteAppend
  448. }
  449. if (peek() == '&') {
  450. consume();
  451. // FIXME: 'fd>&-' Syntax not the best. needs discussion.
  452. if (peek() == '-') {
  453. consume();
  454. pipe_fd = pipe_fd >= 0 ? pipe_fd : STDOUT_FILENO;
  455. return create<AST::CloseFdRedirection>(pipe_fd); // Redirection CloseFd
  456. }
  457. int dest_pipe_fd = 0;
  458. auto number = consume_while(is_digit);
  459. pipe_fd = pipe_fd >= 0 ? pipe_fd : STDOUT_FILENO;
  460. if (number.is_empty()) {
  461. dest_pipe_fd = -1;
  462. } else {
  463. auto fd = number.to_int();
  464. ASSERT(fd.has_value());
  465. dest_pipe_fd = fd.value();
  466. }
  467. auto redir = create<AST::Fd2FdRedirection>(pipe_fd, dest_pipe_fd); // Redirection Fd2Fd
  468. if (dest_pipe_fd == -1)
  469. redir->set_is_syntax_error(*create<AST::SyntaxError>("Expected a file descriptor"));
  470. return redir;
  471. }
  472. consume_while(is_whitespace);
  473. pipe_fd = pipe_fd >= 0 ? pipe_fd : STDOUT_FILENO;
  474. auto path = parse_expression();
  475. if (!path) {
  476. if (!at_end()) {
  477. // Eat a character and hope the problem goes away
  478. consume();
  479. }
  480. return create<AST::SyntaxError>("Expected a path");
  481. }
  482. return create<AST::WriteRedirection>(pipe_fd, move(path)); // Redirection Write
  483. }
  484. case '<': {
  485. consume();
  486. enum {
  487. Read,
  488. ReadWrite,
  489. } mode { Read };
  490. if (peek() == '>') {
  491. mode = ReadWrite;
  492. consume();
  493. }
  494. consume_while(is_whitespace);
  495. pipe_fd = pipe_fd >= 0 ? pipe_fd : STDIN_FILENO;
  496. auto path = parse_expression();
  497. if (!path) {
  498. if (!at_end()) {
  499. // Eat a character and hope the problem goes away
  500. consume();
  501. }
  502. return create<AST::SyntaxError>("Expected a path");
  503. }
  504. if (mode == Read)
  505. return create<AST::ReadRedirection>(pipe_fd, move(path)); // Redirection Read
  506. return create<AST::ReadWriteRedirection>(pipe_fd, move(path)); // Redirection ReadWrite
  507. }
  508. default:
  509. m_offset = rule_start->offset;
  510. return nullptr;
  511. }
  512. }
  513. RefPtr<AST::Node> Parser::parse_list_expression()
  514. {
  515. consume_while(is_whitespace);
  516. auto rule_start = push_start();
  517. Vector<RefPtr<AST::Node>> nodes;
  518. do {
  519. auto expr = parse_expression();
  520. if (!expr)
  521. break;
  522. nodes.append(move(expr));
  523. } while (!consume_while(is_whitespace).is_empty());
  524. if (nodes.is_empty())
  525. return nullptr;
  526. return create<AST::ListConcatenate>(move(nodes)); // Concatenate List
  527. }
  528. RefPtr<AST::Node> Parser::parse_expression()
  529. {
  530. auto rule_start = push_start();
  531. auto starting_char = peek();
  532. auto read_concat = [&](auto expr) -> RefPtr<AST::Node> {
  533. if (is_whitespace(peek()))
  534. return expr;
  535. if (auto next_expr = parse_expression())
  536. return create<AST::Juxtaposition>(move(expr), move(next_expr));
  537. return expr;
  538. };
  539. if (strchr("&|){} ;<>\n", starting_char) != nullptr)
  540. return nullptr;
  541. if (isdigit(starting_char)) {
  542. ScopedValueRollback offset_rollback { m_offset };
  543. auto redir = parse_redirection();
  544. if (redir)
  545. return nullptr;
  546. }
  547. if (starting_char == '$') {
  548. if (auto variable = parse_variable())
  549. return read_concat(variable);
  550. if (auto inline_exec = parse_evaluate())
  551. return read_concat(inline_exec);
  552. }
  553. if (starting_char == '#')
  554. return parse_comment();
  555. if (starting_char == '(') {
  556. consume();
  557. auto list = parse_list_expression();
  558. if (!expect(')')) {
  559. m_offset = rule_start->offset;
  560. return nullptr;
  561. }
  562. return read_concat(create<AST::CastToList>(move(list))); // Cast To List
  563. }
  564. return read_concat(parse_string_composite());
  565. }
  566. RefPtr<AST::Node> Parser::parse_string_composite()
  567. {
  568. auto rule_start = push_start();
  569. if (auto string = parse_string()) {
  570. if (auto next_part = parse_string_composite())
  571. return create<AST::Juxtaposition>(move(string), move(next_part)); // Concatenate String StringComposite
  572. return string;
  573. }
  574. if (auto variable = parse_variable()) {
  575. if (auto next_part = parse_string_composite())
  576. return create<AST::Juxtaposition>(move(variable), move(next_part)); // Concatenate Variable StringComposite
  577. return variable;
  578. }
  579. if (auto glob = parse_glob()) {
  580. if (auto next_part = parse_string_composite())
  581. return create<AST::Juxtaposition>(move(glob), move(next_part)); // Concatenate Glob StringComposite
  582. return glob;
  583. }
  584. if (auto bareword = parse_bareword()) {
  585. if (auto next_part = parse_string_composite())
  586. return create<AST::Juxtaposition>(move(bareword), move(next_part)); // Concatenate Bareword StringComposite
  587. return bareword;
  588. }
  589. if (auto inline_command = parse_evaluate()) {
  590. if (auto next_part = parse_string_composite())
  591. return create<AST::Juxtaposition>(move(inline_command), move(next_part)); // Concatenate Execute StringComposite
  592. return inline_command;
  593. }
  594. return nullptr;
  595. }
  596. RefPtr<AST::Node> Parser::parse_string()
  597. {
  598. auto rule_start = push_start();
  599. if (at_end())
  600. return nullptr;
  601. if (peek() == '"') {
  602. consume();
  603. auto inner = parse_doublequoted_string_inner();
  604. if (!inner)
  605. inner = create<AST::SyntaxError>("Unexpected EOF in string");
  606. if (!expect('"')) {
  607. inner = create<AST::DoubleQuotedString>(move(inner));
  608. inner->set_is_syntax_error(*create<AST::SyntaxError>("Expected a terminating double quote"));
  609. return inner;
  610. }
  611. return create<AST::DoubleQuotedString>(move(inner)); // Double Quoted String
  612. }
  613. if (peek() == '\'') {
  614. consume();
  615. auto text = consume_while(is_not('\''));
  616. bool is_error = false;
  617. if (!expect('\''))
  618. is_error = true;
  619. auto result = create<AST::StringLiteral>(move(text)); // String Literal
  620. if (is_error)
  621. result->set_is_syntax_error(*create<AST::SyntaxError>("Expected a terminating single quote"));
  622. return move(result);
  623. }
  624. return nullptr;
  625. }
  626. RefPtr<AST::Node> Parser::parse_doublequoted_string_inner()
  627. {
  628. auto rule_start = push_start();
  629. if (at_end())
  630. return nullptr;
  631. StringBuilder builder;
  632. while (!at_end() && peek() != '"') {
  633. if (peek() == '\\') {
  634. consume();
  635. if (at_end()) {
  636. break;
  637. }
  638. auto ch = consume();
  639. switch (ch) {
  640. case '\\':
  641. default:
  642. builder.append(ch);
  643. break;
  644. case 'x': {
  645. if (m_input.length() <= m_offset + 2)
  646. break;
  647. auto first_nibble = tolower(consume());
  648. auto second_nibble = tolower(consume());
  649. if (!isxdigit(first_nibble) || !isxdigit(second_nibble)) {
  650. builder.append(first_nibble);
  651. builder.append(second_nibble);
  652. break;
  653. }
  654. builder.append(to_byte(first_nibble, second_nibble));
  655. break;
  656. }
  657. case 'a':
  658. builder.append('\a');
  659. break;
  660. case 'b':
  661. builder.append('\b');
  662. break;
  663. case 'e':
  664. builder.append('\x1b');
  665. break;
  666. case 'f':
  667. builder.append('\f');
  668. break;
  669. case 'r':
  670. builder.append('\r');
  671. break;
  672. case 'n':
  673. builder.append('\n');
  674. break;
  675. }
  676. continue;
  677. }
  678. if (peek() == '$') {
  679. auto string_literal = create<AST::StringLiteral>(builder.to_string()); // String Literal
  680. if (auto variable = parse_variable()) {
  681. auto inner = create<AST::StringPartCompose>(
  682. move(string_literal),
  683. move(variable)); // Compose String Variable
  684. if (auto string = parse_doublequoted_string_inner()) {
  685. return create<AST::StringPartCompose>(move(inner), move(string)); // Compose Composition Composition
  686. }
  687. return inner;
  688. }
  689. if (auto evaluate = parse_evaluate()) {
  690. auto composition = create<AST::StringPartCompose>(
  691. move(string_literal),
  692. move(evaluate)); // Compose String Sequence
  693. if (auto string = parse_doublequoted_string_inner()) {
  694. return create<AST::StringPartCompose>(move(composition), move(string)); // Compose Composition Composition
  695. }
  696. return composition;
  697. }
  698. }
  699. builder.append(consume());
  700. }
  701. return create<AST::StringLiteral>(builder.to_string()); // String Literal
  702. }
  703. RefPtr<AST::Node> Parser::parse_variable()
  704. {
  705. auto rule_start = push_start();
  706. if (at_end())
  707. return nullptr;
  708. if (peek() != '$')
  709. return nullptr;
  710. consume();
  711. switch (peek()) {
  712. case '$':
  713. case '?':
  714. case '*':
  715. case '#':
  716. return create<AST::SpecialVariable>(consume()); // Variable Special
  717. default:
  718. break;
  719. }
  720. auto name = consume_while(is_word_character);
  721. if (name.length() == 0) {
  722. putback();
  723. return nullptr;
  724. }
  725. return create<AST::SimpleVariable>(move(name)); // Variable Simple
  726. }
  727. RefPtr<AST::Node> Parser::parse_evaluate()
  728. {
  729. auto rule_start = push_start();
  730. if (at_end())
  731. return nullptr;
  732. if (peek() != '$')
  733. return nullptr;
  734. consume();
  735. if (peek() == '(') {
  736. consume();
  737. auto inner = parse_pipe_sequence();
  738. if (!inner)
  739. inner = create<AST::SyntaxError>("Unexpected EOF in list");
  740. if (!expect(')'))
  741. inner->set_is_syntax_error(*create<AST::SyntaxError>("Expected a terminating close paren"));
  742. return create<AST::Execute>(move(inner), true);
  743. }
  744. auto inner = parse_expression();
  745. if (!inner) {
  746. inner = create<AST::SyntaxError>("Expected a command");
  747. } else {
  748. if (inner->is_list()) {
  749. auto execute_inner = create<AST::Execute>(move(inner), true);
  750. inner = execute_inner;
  751. } else {
  752. auto dyn_inner = create<AST::DynamicEvaluate>(move(inner));
  753. inner = dyn_inner;
  754. }
  755. }
  756. return inner;
  757. }
  758. RefPtr<AST::Node> Parser::parse_comment()
  759. {
  760. if (at_end())
  761. return nullptr;
  762. if (peek() != '#')
  763. return nullptr;
  764. consume();
  765. auto text = consume_while(is_not('\n'));
  766. return create<AST::Comment>(move(text)); // Comment
  767. }
  768. RefPtr<AST::Node> Parser::parse_bareword()
  769. {
  770. auto rule_start = push_start();
  771. StringBuilder builder;
  772. auto is_acceptable_bareword_character = [](char c) {
  773. return strchr("\\\"'*$&#|(){} ?;<>\n", c) == nullptr;
  774. };
  775. while (!at_end()) {
  776. char ch = peek();
  777. if (ch == '\\') {
  778. consume();
  779. if (!at_end()) {
  780. ch = consume();
  781. if (is_acceptable_bareword_character(ch))
  782. builder.append('\\');
  783. }
  784. builder.append(ch);
  785. continue;
  786. }
  787. if (is_acceptable_bareword_character(ch)) {
  788. builder.append(consume());
  789. continue;
  790. }
  791. break;
  792. }
  793. if (builder.is_empty())
  794. return nullptr;
  795. auto current_end = m_offset;
  796. auto string = builder.to_string();
  797. if (string.starts_with('~')) {
  798. String username;
  799. RefPtr<AST::Node> tilde, text;
  800. auto first_slash_index = string.index_of("/");
  801. if (first_slash_index.has_value()) {
  802. username = string.substring_view(1, first_slash_index.value() - 1);
  803. string = string.substring_view(first_slash_index.value(), string.length() - first_slash_index.value());
  804. } else {
  805. username = string.substring_view(1, string.length() - 1);
  806. string = "";
  807. }
  808. // Synthesize a Tilde Node with the correct positioning information.
  809. {
  810. m_offset -= string.length();
  811. tilde = create<AST::Tilde>(move(username));
  812. }
  813. if (string.is_empty())
  814. return tilde;
  815. // Synthesize a BarewordLiteral Node with the correct positioning information.
  816. {
  817. m_offset = tilde->position().end_offset;
  818. auto text_start = push_start();
  819. m_offset = current_end;
  820. text = create<AST::BarewordLiteral>(move(string));
  821. }
  822. return create<AST::Juxtaposition>(move(tilde), move(text)); // Juxtaposition Varible Bareword
  823. }
  824. if (string.starts_with("\\~")) {
  825. // Un-escape the tilde, but only at the start (where it would be an expansion)
  826. string = string.substring(1, string.length() - 1);
  827. }
  828. return create<AST::BarewordLiteral>(move(string)); // Bareword Literal
  829. }
  830. RefPtr<AST::Node> Parser::parse_glob()
  831. {
  832. auto rule_start = push_start();
  833. auto bareword_part = parse_bareword();
  834. if (at_end())
  835. return bareword_part;
  836. char ch = peek();
  837. if (ch == '*' || ch == '?') {
  838. consume();
  839. StringBuilder textbuilder;
  840. if (bareword_part) {
  841. StringView text;
  842. if (bareword_part->is_bareword()) {
  843. auto bareword = static_cast<AST::BarewordLiteral*>(bareword_part.ptr());
  844. text = bareword->text();
  845. } else {
  846. // FIXME: Allow composition of tilde+bareword with globs: '~/foo/bar/baz*'
  847. putback();
  848. bareword_part->set_is_syntax_error(*create<AST::SyntaxError>(String::format("Unexpected %s inside a glob", bareword_part->class_name().characters())));
  849. return bareword_part;
  850. }
  851. textbuilder.append(text);
  852. }
  853. textbuilder.append(ch);
  854. auto glob_after = parse_glob();
  855. if (glob_after) {
  856. if (glob_after->is_glob()) {
  857. auto glob = static_cast<AST::BarewordLiteral*>(glob_after.ptr());
  858. textbuilder.append(glob->text());
  859. } else if (glob_after->is_bareword()) {
  860. auto bareword = static_cast<AST::BarewordLiteral*>(glob_after.ptr());
  861. textbuilder.append(bareword->text());
  862. } else {
  863. ASSERT_NOT_REACHED();
  864. }
  865. }
  866. return create<AST::Glob>(textbuilder.to_string()); // Glob
  867. }
  868. return bareword_part;
  869. }
  870. StringView Parser::consume_while(Function<bool(char)> condition)
  871. {
  872. auto start_offset = m_offset;
  873. while (!at_end() && condition(peek()))
  874. consume();
  875. return m_input.substring_view(start_offset, m_offset - start_offset);
  876. }