Lexer.cpp 9.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256
  1. /*
  2. * Copyright (c) 2023, Dan Klishch <danilklishch@gmail.com>
  3. *
  4. * SPDX-License-Identifier: BSD-2-Clause
  5. */
  6. #include <AK/NonnullOwnPtr.h>
  7. #include <LibXML/Parser/Parser.h>
  8. #include "Parser/Lexer.h"
  9. #include "Parser/SpecificationParsing.h"
  10. #include "Parser/XMLUtils.h"
  11. namespace JSSpecCompiler {
  12. namespace {
  13. Optional<Token> consume_number(LineTrackingLexer& lexer, Location& location)
  14. {
  15. u64 start = lexer.tell();
  16. if (lexer.next_is('-'))
  17. lexer.consume(1);
  18. if (!lexer.next_is(is_ascii_digit)) {
  19. lexer.retreat(lexer.tell() - start);
  20. return {};
  21. }
  22. lexer.consume_while(is_ascii_digit);
  23. if (lexer.next_is('.')) {
  24. lexer.consume(1);
  25. if (lexer.consume_while(is_ascii_digit).length() == 0)
  26. lexer.retreat(1);
  27. }
  28. auto length = lexer.tell() - start;
  29. lexer.retreat(length);
  30. return { Token { TokenType::Number, lexer.consume(length), move(location) } };
  31. }
  32. bool can_end_word_token(char c)
  33. {
  34. return is_ascii_space(c) || ".,"sv.contains(c);
  35. }
  36. void tokenize_string(SpecificationParsingContext& ctx, XML::Node const* node, StringView view, Vector<Token>& tokens)
  37. {
  38. static constexpr struct {
  39. StringView text_to_match;
  40. TokenType token_type;
  41. } choices[] = {
  42. { "-"sv, TokenType::AmbiguousMinus },
  43. { "}"sv, TokenType::BraceClose },
  44. { "{"sv, TokenType::BraceOpen },
  45. { ":"sv, TokenType::Colon },
  46. { ","sv, TokenType::Comma },
  47. { "/"sv, TokenType::Division },
  48. { ". "sv, TokenType::Dot },
  49. { ".\n"sv, TokenType::Dot },
  50. { "="sv, TokenType::Equals },
  51. { "is equal to"sv, TokenType::Equals },
  52. { "!"sv, TokenType::ExclamationMark },
  53. { ">"sv, TokenType::Greater },
  54. { "is"sv, TokenType::Is },
  55. { "<"sv, TokenType::Less },
  56. { "»"sv, TokenType::ListEnd },
  57. { "«"sv, TokenType::ListStart },
  58. { "."sv, TokenType::MemberAccess },
  59. { "×"sv, TokenType::Multiplication },
  60. { "is not equal to"sv, TokenType::NotEquals },
  61. { "≠"sv, TokenType::NotEquals },
  62. { ")"sv, TokenType::ParenClose },
  63. { "("sv, TokenType::ParenOpen },
  64. { "+"sv, TokenType::Plus },
  65. { "?"sv, TokenType::QuestionMark },
  66. { "]"sv, TokenType::SquareBracketClose },
  67. { "["sv, TokenType::SquareBracketOpen },
  68. { "NewTarget"sv, TokenType::WellKnownValue },
  69. };
  70. LineTrackingLexer lexer(view, node->offset);
  71. while (!lexer.is_eof()) {
  72. lexer.ignore_while(is_ascii_space);
  73. // FIXME: This is incorrect since we count text offset after XML reference resolution. To do
  74. // this properly, we need support from XML::Parser.
  75. Location token_location = ctx.location_from_xml_offset(lexer.position_for(lexer.tell()));
  76. if (auto result = consume_number(lexer, token_location); result.has_value()) {
  77. tokens.append(result.release_value());
  78. continue;
  79. }
  80. bool matched = false;
  81. for (auto const& [text_to_match, token_type] : choices) {
  82. if (lexer.consume_specific(text_to_match)) {
  83. tokens.append({ token_type, text_to_match, move(token_location) });
  84. matched = true;
  85. break;
  86. }
  87. }
  88. if (matched)
  89. continue;
  90. StringView word = lexer.consume_until(can_end_word_token);
  91. if (word.length())
  92. tokens.append({ TokenType::Word, word, move(token_location) });
  93. }
  94. }
  95. enum class TreeType {
  96. AlgorithmStep,
  97. NestedExpression,
  98. Header,
  99. };
  100. struct TokenizerState {
  101. Vector<Token> tokens;
  102. XML::Node const* substeps = nullptr;
  103. bool has_errors = false;
  104. };
  105. void tokenize_tree(SpecificationParsingContext& ctx, TokenizerState& state, XML::Node const* node, TreeType tree_type)
  106. {
  107. // FIXME: Use structured binding once macOS Lagom CI updates to Clang >= 16.
  108. auto& tokens = state.tokens;
  109. auto& substeps = state.substeps;
  110. auto& has_errors = state.has_errors;
  111. for (auto const& child : node->as_element().children) {
  112. if (has_errors)
  113. break;
  114. child->content.visit(
  115. [&](XML::Node::Element const& element) -> void {
  116. Location child_location = ctx.location_from_xml_offset(child->offset);
  117. auto report_error = [&]<typename... Parameters>(AK::CheckedFormatString<Parameters...>&& fmt, Parameters const&... parameters) {
  118. ctx.diag().error(child_location, move(fmt), parameters...);
  119. has_errors = true;
  120. };
  121. if (substeps) {
  122. report_error("substeps list must be the last child of algorithm step");
  123. return;
  124. }
  125. if (element.name == tag_var) {
  126. auto variable_name = get_text_contents(child);
  127. if (!variable_name.has_value())
  128. report_error("malformed <var> subtree, expected single text child node");
  129. tokens.append({ TokenType::Identifier, variable_name.value_or(""sv), move(child_location) });
  130. return;
  131. }
  132. if (element.name == tag_emu_val) {
  133. auto maybe_contents = get_text_contents(child);
  134. if (!maybe_contents.has_value())
  135. report_error("malformed <emu-val> subtree, expected single text child node");
  136. auto contents = maybe_contents.value_or(""sv);
  137. if (contents.length() >= 2 && contents.starts_with('"') && contents.ends_with('"'))
  138. tokens.append({ TokenType::String, contents.substring_view(1, contents.length() - 2), move(child_location) });
  139. else if (contents.is_one_of("undefined", "null", "this", "true", "false"))
  140. tokens.append({ TokenType::WellKnownValue, contents, move(child_location) });
  141. else
  142. tokens.append({ TokenType::Identifier, contents, move(child_location) });
  143. return;
  144. }
  145. if (element.name == tag_emu_xref) {
  146. auto identifier = get_single_child_with_tag(child, "a"sv).map([](XML::Node const* node) {
  147. return get_text_contents(node).value_or(""sv);
  148. });
  149. if (!identifier.has_value() || identifier.value().is_empty())
  150. report_error("malformed <emu-xref> subtree, expected <a> with nested single text node");
  151. tokens.append({ TokenType::Identifier, identifier.value_or(""sv), move(child_location) });
  152. return;
  153. }
  154. if (element.name == tag_sup) {
  155. tokens.append({ TokenType::Superscript, ""sv, move(child_location) });
  156. tokens.append({ TokenType::ParenOpen, ""sv, move(child_location) });
  157. tokenize_tree(ctx, state, child, TreeType::NestedExpression);
  158. tokens.append({ TokenType::ParenClose, ""sv, move(child_location) });
  159. return;
  160. }
  161. if (element.name == tag_emu_const) {
  162. auto maybe_contents = get_text_contents(child);
  163. if (!maybe_contents.has_value())
  164. report_error("malformed <emu-const> subtree, expected single text child node");
  165. tokens.append({ TokenType::Enumerator, maybe_contents.value_or(""sv), move(child_location) });
  166. return;
  167. }
  168. if (tree_type == TreeType::Header && element.name == tag_span) {
  169. auto element_class = get_attribute_by_name(child, attribute_class);
  170. if (element_class != class_secnum)
  171. report_error("expected <span> to have class='secnum' attribute");
  172. auto section_number = get_text_contents(child);
  173. if (!section_number.has_value())
  174. report_error("malformed section number span subtree, expected single text child node");
  175. tokens.append({ TokenType::SectionNumber, section_number.value_or(""sv), move(child_location) });
  176. return;
  177. }
  178. if (tree_type == TreeType::AlgorithmStep && element.name == tag_ol) {
  179. substeps = child;
  180. return;
  181. }
  182. report_error("<{}> should not be a child of algorithm step", element.name);
  183. },
  184. [&](XML::Node::Text const& text) {
  185. auto view = text.builder.string_view();
  186. if (substeps != nullptr && !contains_empty_text(child)) {
  187. ctx.diag().error(ctx.location_from_xml_offset(child->offset),
  188. "substeps list must be the last child of algorithm step");
  189. } else {
  190. tokenize_string(ctx, child, view, tokens);
  191. }
  192. },
  193. [&](auto const&) {});
  194. }
  195. if (tree_type == TreeType::AlgorithmStep && tokens.size() && tokens.last().type == TokenType::MemberAccess)
  196. tokens.last().type = TokenType::Dot;
  197. }
  198. }
  199. StepTokenizationResult tokenize_step(SpecificationParsingContext& ctx, XML::Node const* node)
  200. {
  201. TokenizerState state;
  202. tokenize_tree(ctx, state, node, TreeType::AlgorithmStep);
  203. return {
  204. .tokens = state.has_errors ? OptionalNone {} : Optional<Vector<Token>> { move(state.tokens) },
  205. .substeps = state.substeps,
  206. };
  207. }
  208. Optional<Vector<Token>> tokenize_header(SpecificationParsingContext& ctx, XML::Node const* node)
  209. {
  210. TokenizerState state;
  211. tokenize_tree(ctx, state, node, TreeType::Header);
  212. return state.has_errors ? OptionalNone {} : Optional<Vector<Token>> { state.tokens };
  213. }
  214. }