AST.cpp 18 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681
  1. /*
  2. * Copyright (c) 2020, Andreas Kling <kling@serenityos.org>
  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 <AK/HashMap.h>
  27. #include <AK/StringBuilder.h>
  28. #include <LibJS/AST.h>
  29. #include <LibJS/Interpreter.h>
  30. #include <LibJS/Runtime/PrimitiveString.h>
  31. #include <LibJS/Runtime/ScriptFunction.h>
  32. #include <LibJS/Runtime/Value.h>
  33. #include <stdio.h>
  34. namespace JS {
  35. Value ScopeNode::execute(Interpreter& interpreter) const
  36. {
  37. return interpreter.run(*this);
  38. }
  39. Value FunctionDeclaration::execute(Interpreter& interpreter) const
  40. {
  41. auto* function = interpreter.heap().allocate<ScriptFunction>(body(), parameters());
  42. interpreter.set_variable(name(), function);
  43. return function;
  44. }
  45. Value FunctionExpression::execute(Interpreter& interpreter) const
  46. {
  47. return interpreter.heap().allocate<ScriptFunction>(body(), parameters());
  48. }
  49. Value ExpressionStatement::execute(Interpreter& interpreter) const
  50. {
  51. return m_expression->execute(interpreter);
  52. }
  53. Value CallExpression::execute(Interpreter& interpreter) const
  54. {
  55. auto callee = m_callee->execute(interpreter);
  56. ASSERT(callee.is_object());
  57. ASSERT(callee.as_object()->is_function());
  58. auto* function = static_cast<Function*>(callee.as_object());
  59. auto& call_frame = interpreter.push_call_frame();
  60. for (size_t i = 0; i < m_arguments.size(); ++i)
  61. call_frame.arguments.append(m_arguments[i].execute(interpreter));
  62. if (m_callee->is_member_expression())
  63. call_frame.this_value = static_cast<const MemberExpression&>(*m_callee).object().execute(interpreter).to_object(interpreter.heap());
  64. auto result = function->call(interpreter, call_frame.arguments);
  65. interpreter.pop_call_frame();
  66. return result;
  67. }
  68. Value ReturnStatement::execute(Interpreter& interpreter) const
  69. {
  70. auto value = argument() ? argument()->execute(interpreter) : js_undefined();
  71. interpreter.do_return();
  72. return value;
  73. }
  74. Value IfStatement::execute(Interpreter& interpreter) const
  75. {
  76. auto predicate_result = m_predicate->execute(interpreter);
  77. if (predicate_result.to_boolean())
  78. return interpreter.run(*m_consequent);
  79. else
  80. return interpreter.run(*m_alternate);
  81. }
  82. Value WhileStatement::execute(Interpreter& interpreter) const
  83. {
  84. Value last_value = js_undefined();
  85. while (m_predicate->execute(interpreter).to_boolean()) {
  86. last_value = interpreter.run(*m_body);
  87. }
  88. return last_value;
  89. }
  90. Value ForStatement::execute(Interpreter& interpreter) const
  91. {
  92. RefPtr<BlockStatement> wrapper;
  93. if (m_init->is_variable_declaration() && static_cast<const VariableDeclaration*>(m_init.ptr())->declaration_type() != DeclarationType::Var) {
  94. wrapper = create_ast_node<BlockStatement>();
  95. interpreter.enter_scope(*wrapper, {}, ScopeType::Block);
  96. }
  97. Value last_value = js_undefined();
  98. if (m_init)
  99. m_init->execute(interpreter);
  100. if (m_test) {
  101. while (m_test->execute(interpreter).to_boolean()) {
  102. last_value = interpreter.run(*m_body);
  103. if (m_update)
  104. m_update->execute(interpreter);
  105. }
  106. } else {
  107. while (true) {
  108. last_value = interpreter.run(*m_body);
  109. if (m_update)
  110. m_update->execute(interpreter);
  111. }
  112. }
  113. if (wrapper)
  114. interpreter.exit_scope(*wrapper);
  115. return last_value;
  116. }
  117. Value BinaryExpression::execute(Interpreter& interpreter) const
  118. {
  119. auto lhs_result = m_lhs->execute(interpreter);
  120. auto rhs_result = m_rhs->execute(interpreter);
  121. switch (m_op) {
  122. case BinaryOp::Plus:
  123. return add(lhs_result, rhs_result);
  124. case BinaryOp::Minus:
  125. return sub(lhs_result, rhs_result);
  126. case BinaryOp::Asterisk:
  127. return mul(lhs_result, rhs_result);
  128. case BinaryOp::Slash:
  129. return div(lhs_result, rhs_result);
  130. case BinaryOp::TypedEquals:
  131. return typed_eq(lhs_result, rhs_result);
  132. case BinaryOp::TypedInequals:
  133. return Value(!typed_eq(lhs_result, rhs_result).as_bool());
  134. case BinaryOp::AbstractEquals:
  135. return eq(lhs_result, rhs_result);
  136. case BinaryOp::AbstractInequals:
  137. return Value(!eq(lhs_result, rhs_result).as_bool());
  138. case BinaryOp::GreaterThan:
  139. return greater_than(lhs_result, rhs_result);
  140. case BinaryOp::GreaterThanEquals:
  141. return greater_than_equals(lhs_result, rhs_result);
  142. case BinaryOp::LessThan:
  143. return less_than(lhs_result, rhs_result);
  144. case BinaryOp::LessThanEquals:
  145. return less_than_equals(lhs_result, rhs_result);
  146. case BinaryOp::BitwiseAnd:
  147. return bitwise_and(lhs_result, rhs_result);
  148. case BinaryOp::BitwiseOr:
  149. return bitwise_or(lhs_result, rhs_result);
  150. case BinaryOp::BitwiseXor:
  151. return bitwise_xor(lhs_result, rhs_result);
  152. case BinaryOp::LeftShift:
  153. return left_shift(lhs_result, rhs_result);
  154. case BinaryOp::RightShift:
  155. return right_shift(lhs_result, rhs_result);
  156. }
  157. ASSERT_NOT_REACHED();
  158. }
  159. Value LogicalExpression::execute(Interpreter& interpreter) const
  160. {
  161. auto lhs_result = m_lhs->execute(interpreter).to_boolean();
  162. auto rhs_result = m_rhs->execute(interpreter).to_boolean();
  163. switch (m_op) {
  164. case LogicalOp::And:
  165. return Value(lhs_result && rhs_result);
  166. case LogicalOp::Or:
  167. return Value(lhs_result || rhs_result);
  168. }
  169. ASSERT_NOT_REACHED();
  170. }
  171. Value UnaryExpression::execute(Interpreter& interpreter) const
  172. {
  173. auto lhs_result = m_lhs->execute(interpreter);
  174. switch (m_op) {
  175. case UnaryOp::BitwiseNot:
  176. return bitwise_not(lhs_result);
  177. case UnaryOp::Not:
  178. return Value(!lhs_result.to_boolean());
  179. case UnaryOp::Typeof:
  180. switch (lhs_result.type()) {
  181. case Value::Type::Undefined:
  182. return js_string(interpreter.heap(), "undefined");
  183. case Value::Type::Null:
  184. // yes, this is on purpose. yes, this is how javascript works.
  185. // yes, it's silly.
  186. return js_string(interpreter.heap(), "object");
  187. case Value::Type::Number:
  188. return js_string(interpreter.heap(), "number");
  189. case Value::Type::String:
  190. return js_string(interpreter.heap(), "string");
  191. case Value::Type::Object:
  192. return js_string(interpreter.heap(), "object");
  193. case Value::Type::Boolean:
  194. return js_string(interpreter.heap(), "boolean");
  195. }
  196. }
  197. ASSERT_NOT_REACHED();
  198. }
  199. static void print_indent(int indent)
  200. {
  201. for (int i = 0; i < indent * 2; ++i)
  202. putchar(' ');
  203. }
  204. void ASTNode::dump(int indent) const
  205. {
  206. print_indent(indent);
  207. printf("%s\n", class_name());
  208. }
  209. void ScopeNode::dump(int indent) const
  210. {
  211. ASTNode::dump(indent);
  212. for (auto& child : children())
  213. child.dump(indent + 1);
  214. }
  215. void BinaryExpression::dump(int indent) const
  216. {
  217. const char* op_string = nullptr;
  218. switch (m_op) {
  219. case BinaryOp::Plus:
  220. op_string = "+";
  221. break;
  222. case BinaryOp::Minus:
  223. op_string = "-";
  224. break;
  225. case BinaryOp::Asterisk:
  226. op_string = "*";
  227. break;
  228. case BinaryOp::Slash:
  229. op_string = "/";
  230. break;
  231. case BinaryOp::TypedEquals:
  232. op_string = "===";
  233. break;
  234. case BinaryOp::TypedInequals:
  235. op_string = "!==";
  236. break;
  237. case BinaryOp::AbstractEquals:
  238. op_string = "==";
  239. break;
  240. case BinaryOp::AbstractInequals:
  241. op_string = "!=";
  242. break;
  243. case BinaryOp::GreaterThan:
  244. op_string = ">";
  245. break;
  246. case BinaryOp::GreaterThanEquals:
  247. op_string = ">=";
  248. break;
  249. case BinaryOp::LessThan:
  250. op_string = "<";
  251. break;
  252. case BinaryOp::LessThanEquals:
  253. op_string = "<=";
  254. break;
  255. case BinaryOp::BitwiseAnd:
  256. op_string = "&";
  257. break;
  258. case BinaryOp::BitwiseOr:
  259. op_string = "|";
  260. break;
  261. case BinaryOp::BitwiseXor:
  262. op_string = "^";
  263. break;
  264. case BinaryOp::LeftShift:
  265. op_string = "<<";
  266. break;
  267. case BinaryOp::RightShift:
  268. op_string = ">>";
  269. break;
  270. }
  271. print_indent(indent);
  272. printf("%s\n", class_name());
  273. m_lhs->dump(indent + 1);
  274. print_indent(indent + 1);
  275. printf("%s\n", op_string);
  276. m_rhs->dump(indent + 1);
  277. }
  278. void LogicalExpression::dump(int indent) const
  279. {
  280. const char* op_string = nullptr;
  281. switch (m_op) {
  282. case LogicalOp::And:
  283. op_string = "&&";
  284. break;
  285. case LogicalOp::Or:
  286. op_string = "||";
  287. break;
  288. }
  289. print_indent(indent);
  290. printf("%s\n", class_name());
  291. m_lhs->dump(indent + 1);
  292. print_indent(indent + 1);
  293. printf("%s\n", op_string);
  294. m_rhs->dump(indent + 1);
  295. }
  296. void UnaryExpression::dump(int indent) const
  297. {
  298. const char* op_string = nullptr;
  299. switch (m_op) {
  300. case UnaryOp::BitwiseNot:
  301. op_string = "~";
  302. break;
  303. case UnaryOp::Not:
  304. op_string = "!";
  305. break;
  306. case UnaryOp::Typeof:
  307. op_string = "typeof ";
  308. break;
  309. }
  310. print_indent(indent);
  311. printf("%s\n", class_name());
  312. print_indent(indent + 1);
  313. printf("%s\n", op_string);
  314. m_lhs->dump(indent + 1);
  315. }
  316. void CallExpression::dump(int indent) const
  317. {
  318. ASTNode::dump(indent);
  319. m_callee->dump(indent + 1);
  320. for (auto& argument : m_arguments)
  321. argument.dump(indent + 1);
  322. }
  323. void StringLiteral::dump(int indent) const
  324. {
  325. print_indent(indent);
  326. printf("StringLiteral \"%s\"\n", m_value.characters());
  327. }
  328. void NumericLiteral::dump(int indent) const
  329. {
  330. print_indent(indent);
  331. printf("NumericLiteral %g\n", m_value);
  332. }
  333. void BooleanLiteral::dump(int indent) const
  334. {
  335. print_indent(indent);
  336. printf("BooleanLiteral %s\n", m_value ? "true" : "false");
  337. }
  338. void UndefinedLiteral::dump(int indent) const
  339. {
  340. print_indent(indent);
  341. printf("undefined\n");
  342. }
  343. void NullLiteral::dump(int indent) const
  344. {
  345. print_indent(indent);
  346. printf("null\n");
  347. }
  348. void FunctionNode::dump(int indent, const char* class_name) const
  349. {
  350. bool first_time = true;
  351. StringBuilder parameters_builder;
  352. for (const auto& parameter : parameters()) {
  353. if (first_time)
  354. first_time = false;
  355. else
  356. parameters_builder.append(',');
  357. parameters_builder.append(parameter);
  358. }
  359. print_indent(indent);
  360. printf("%s '%s(%s)'\n", class_name, name().characters(), parameters_builder.build().characters());
  361. body().dump(indent + 1);
  362. }
  363. void FunctionDeclaration::dump(int indent) const
  364. {
  365. FunctionNode::dump(indent, class_name());
  366. }
  367. void FunctionExpression::dump(int indent) const
  368. {
  369. FunctionNode::dump(indent, class_name());
  370. }
  371. void ReturnStatement::dump(int indent) const
  372. {
  373. ASTNode::dump(indent);
  374. if (argument())
  375. argument()->dump(indent + 1);
  376. }
  377. void IfStatement::dump(int indent) const
  378. {
  379. ASTNode::dump(indent);
  380. print_indent(indent);
  381. printf("If\n");
  382. predicate().dump(indent + 1);
  383. consequent().dump(indent + 1);
  384. print_indent(indent);
  385. printf("Else\n");
  386. alternate().dump(indent + 1);
  387. }
  388. void WhileStatement::dump(int indent) const
  389. {
  390. ASTNode::dump(indent);
  391. print_indent(indent);
  392. printf("While\n");
  393. predicate().dump(indent + 1);
  394. body().dump(indent + 1);
  395. }
  396. void ForStatement::dump(int indent) const
  397. {
  398. ASTNode::dump(indent);
  399. print_indent(indent);
  400. printf("For\n");
  401. if (init())
  402. init()->dump(indent + 1);
  403. if (test())
  404. test()->dump(indent + 1);
  405. if (update())
  406. update()->dump(indent + 1);
  407. body().dump(indent + 1);
  408. }
  409. Value Identifier::execute(Interpreter& interpreter) const
  410. {
  411. return interpreter.get_variable(string());
  412. }
  413. void Identifier::dump(int indent) const
  414. {
  415. print_indent(indent);
  416. printf("Identifier \"%s\"\n", m_string.characters());
  417. }
  418. Value AssignmentExpression::execute(Interpreter& interpreter) const
  419. {
  420. ASSERT(m_lhs->is_identifier());
  421. auto name = static_cast<const Identifier&>(*m_lhs).string();
  422. auto rhs_result = m_rhs->execute(interpreter);
  423. switch (m_op) {
  424. case AssignmentOp::Assignment:
  425. interpreter.set_variable(name, rhs_result);
  426. break;
  427. case AssignmentOp::AdditionAssignment:
  428. rhs_result = add(m_lhs->execute(interpreter), rhs_result);
  429. interpreter.set_variable(name, rhs_result);
  430. break;
  431. case AssignmentOp::SubtractionAssignment:
  432. rhs_result = sub(m_lhs->execute(interpreter), rhs_result);
  433. interpreter.set_variable(name, rhs_result);
  434. break;
  435. case AssignmentOp::MultiplicationAssignment:
  436. rhs_result = mul(m_lhs->execute(interpreter), rhs_result);
  437. interpreter.set_variable(name, rhs_result);
  438. break;
  439. case AssignmentOp::DivisionAssignment:
  440. rhs_result = div(m_lhs->execute(interpreter), rhs_result);
  441. interpreter.set_variable(name, rhs_result);
  442. break;
  443. }
  444. return rhs_result;
  445. }
  446. Value UpdateExpression::execute(Interpreter& interpreter) const
  447. {
  448. ASSERT(m_argument->is_identifier());
  449. auto name = static_cast<const Identifier&>(*m_argument).string();
  450. auto previous_value = interpreter.get_variable(name);
  451. ASSERT(previous_value.is_number());
  452. int op_result = 0;
  453. switch (m_op) {
  454. case UpdateOp::Increment:
  455. op_result = 1;
  456. break;
  457. case UpdateOp::Decrement:
  458. op_result = -1;
  459. break;
  460. }
  461. interpreter.set_variable(name, Value(previous_value.as_double() + op_result));
  462. if (m_prefixed)
  463. return JS::Value(previous_value.as_double() + op_result);
  464. return previous_value;
  465. }
  466. void AssignmentExpression::dump(int indent) const
  467. {
  468. const char* op_string = nullptr;
  469. switch (m_op) {
  470. case AssignmentOp::Assignment:
  471. op_string = "=";
  472. break;
  473. case AssignmentOp::AdditionAssignment:
  474. op_string = "+=";
  475. break;
  476. case AssignmentOp::SubtractionAssignment:
  477. op_string = "-=";
  478. break;
  479. case AssignmentOp::MultiplicationAssignment:
  480. op_string = "*=";
  481. break;
  482. case AssignmentOp::DivisionAssignment:
  483. op_string = "/=";
  484. break;
  485. }
  486. ASTNode::dump(indent);
  487. print_indent(indent + 1);
  488. printf("%s\n", op_string);
  489. m_lhs->dump(indent + 1);
  490. m_rhs->dump(indent + 1);
  491. }
  492. void UpdateExpression::dump(int indent) const
  493. {
  494. const char* op_string = nullptr;
  495. switch (m_op) {
  496. case UpdateOp::Increment:
  497. op_string = "++";
  498. break;
  499. case UpdateOp::Decrement:
  500. op_string = "--";
  501. break;
  502. }
  503. ASTNode::dump(indent);
  504. print_indent(indent + 1);
  505. if (m_prefixed)
  506. printf("%s\n", op_string);
  507. m_argument->dump(indent + 1);
  508. if (!m_prefixed) {
  509. print_indent(indent + 1);
  510. printf("%s\n", op_string);
  511. }
  512. }
  513. Value VariableDeclaration::execute(Interpreter& interpreter) const
  514. {
  515. interpreter.declare_variable(name().string(), m_declaration_type);
  516. if (m_initializer) {
  517. auto initalizer_result = m_initializer->execute(interpreter);
  518. interpreter.set_variable(name().string(), initalizer_result, true);
  519. }
  520. return js_undefined();
  521. }
  522. void VariableDeclaration::dump(int indent) const
  523. {
  524. const char* declaration_type_string = nullptr;
  525. switch (m_declaration_type) {
  526. case DeclarationType::Let:
  527. declaration_type_string = "Let";
  528. break;
  529. case DeclarationType::Var:
  530. declaration_type_string = "Var";
  531. break;
  532. case DeclarationType::Const:
  533. declaration_type_string = "Const";
  534. break;
  535. }
  536. ASTNode::dump(indent);
  537. print_indent(indent + 1);
  538. printf("%s\n", declaration_type_string);
  539. m_name->dump(indent + 1);
  540. if (m_initializer)
  541. m_initializer->dump(indent + 1);
  542. }
  543. void ObjectExpression::dump(int indent) const
  544. {
  545. ASTNode::dump(indent);
  546. }
  547. void ExpressionStatement::dump(int indent) const
  548. {
  549. ASTNode::dump(indent);
  550. m_expression->dump(indent + 1);
  551. }
  552. Value ObjectExpression::execute(Interpreter& interpreter) const
  553. {
  554. return interpreter.heap().allocate<Object>();
  555. }
  556. void MemberExpression::dump(int indent) const
  557. {
  558. ASTNode::dump(indent);
  559. m_object->dump(indent + 1);
  560. m_property->dump(indent + 1);
  561. }
  562. Value MemberExpression::execute(Interpreter& interpreter) const
  563. {
  564. auto object_result = m_object->execute(interpreter).to_object(interpreter.heap());
  565. ASSERT(object_result.is_object());
  566. String property_name;
  567. if (m_property->is_identifier()) {
  568. property_name = static_cast<const Identifier&>(*m_property).string();
  569. } else {
  570. ASSERT_NOT_REACHED();
  571. }
  572. return object_result.as_object()->get(property_name);
  573. }
  574. Value StringLiteral::execute(Interpreter& interpreter) const
  575. {
  576. return js_string(interpreter.heap(), m_value);
  577. }
  578. Value NumericLiteral::execute(Interpreter&) const
  579. {
  580. return Value(m_value);
  581. }
  582. Value BooleanLiteral::execute(Interpreter&) const
  583. {
  584. return Value(m_value);
  585. }
  586. Value UndefinedLiteral::execute(Interpreter&) const
  587. {
  588. return js_undefined();
  589. }
  590. Value NullLiteral::execute(Interpreter&) const
  591. {
  592. return js_null();
  593. }
  594. }