jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2021, Daniel Bertalan <dani@danielbertalan.dev>
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 */
6
7#include <AK/DeprecatedString.h>
8#include <AK/GenericLexer.h>
9#include <AK/HashTable.h>
10#include <AK/OwnPtr.h>
11#include <AK/SourceGenerator.h>
12#include <AK/StringBuilder.h>
13#include <AK/Types.h>
14#include <LibCore/ArgsParser.h>
15#include <LibCore/File.h>
16#include <LibMain/Main.h>
17#include <ctype.h>
18
19struct Range {
20 int begin;
21 int end;
22};
23
24struct StateTransition {
25 Optional<DeprecatedString> new_state;
26 Optional<DeprecatedString> action;
27};
28
29struct MatchedAction {
30 Range range;
31 StateTransition action;
32};
33
34struct State {
35 DeprecatedString name;
36 Vector<MatchedAction> actions;
37 Optional<DeprecatedString> entry_action;
38 Optional<DeprecatedString> exit_action;
39};
40
41struct StateMachine {
42 DeprecatedString name;
43 DeprecatedString initial_state;
44 Vector<State> states;
45 Optional<State> anywhere;
46 Optional<DeprecatedString> namespaces;
47};
48
49static OwnPtr<StateMachine>
50parse_state_machine(StringView input)
51{
52 auto state_machine = make<StateMachine>();
53 GenericLexer lexer(input);
54
55 auto consume_whitespace = [&] {
56 bool consumed = true;
57 while (consumed) {
58 consumed = lexer.consume_while(isspace).length() > 0;
59 if (lexer.consume_specific("//")) {
60 lexer.consume_line();
61 consumed = true;
62 }
63 }
64 };
65
66 auto consume_identifier = [&] {
67 consume_whitespace();
68 return lexer.consume_while([](char c) { return isalnum(c) || c == '_'; });
69 };
70
71 auto get_hex_value = [&](char c) {
72 if (isdigit(c))
73 return c - '0';
74 else
75 return c - 'a' + 10;
76 };
77
78 auto consume_number = [&] {
79 int num = 0;
80 consume_whitespace();
81 if (lexer.consume_specific("0x")) {
82 auto hex_digits = lexer.consume_while([](char c) {
83 if (isdigit(c)) return true;
84 else {
85 c = tolower(c);
86 return (c >= 'a' && c <= 'f');
87 } });
88 for (auto c : hex_digits)
89 num = 16 * num + get_hex_value(c);
90 } else {
91 lexer.consume_specific('\'');
92 if (lexer.next_is('\\')) {
93 num = (int)lexer.consume_escaped_character('\\');
94 } else {
95 num = lexer.consume_until('\'').to_int().value();
96 lexer.ignore();
97 }
98 lexer.consume_specific('\'');
99 }
100 return num;
101 };
102
103 auto consume_condition = [&] {
104 Range condition;
105 consume_whitespace();
106 if (lexer.consume_specific('[')) {
107 consume_whitespace();
108 condition.begin = consume_number();
109 consume_whitespace();
110 lexer.consume_specific("..");
111 consume_whitespace();
112 condition.end = consume_number();
113 consume_whitespace();
114 lexer.consume_specific(']');
115 } else {
116 auto num = consume_number();
117 condition.begin = num;
118 condition.end = num;
119 }
120 return condition;
121 };
122
123 auto consume_action = [&]() {
124 StateTransition action;
125 consume_whitespace();
126 lexer.consume_specific("=>");
127 consume_whitespace();
128 lexer.consume_specific('(');
129 consume_whitespace();
130 if (!lexer.consume_specific("_"))
131 action.new_state = consume_identifier();
132 consume_whitespace();
133 lexer.consume_specific(',');
134 consume_whitespace();
135 if (!lexer.consume_specific("_"))
136 action.action = consume_identifier();
137 consume_whitespace();
138 lexer.consume_specific(')');
139 return action;
140 };
141
142 auto consume_state_description
143 = [&] {
144 State state;
145 consume_whitespace();
146 state.name = consume_identifier();
147 consume_whitespace();
148 consume_whitespace();
149 lexer.consume_specific('{');
150 for (;;) {
151 consume_whitespace();
152 if (lexer.consume_specific('}')) {
153 break;
154 }
155 if (lexer.consume_specific("@entry")) {
156 consume_whitespace();
157 state.entry_action = consume_identifier();
158 } else if (lexer.consume_specific("@exit")) {
159 consume_whitespace();
160 state.exit_action = consume_identifier();
161 } else if (lexer.next_is('@')) {
162 auto directive = consume_identifier().to_deprecated_string();
163 fprintf(stderr, "Unimplemented @ directive %s\n", directive.characters());
164 exit(1);
165 } else {
166 MatchedAction matched_action;
167 matched_action.range = consume_condition();
168 matched_action.action = consume_action();
169 state.actions.append(matched_action);
170 }
171 }
172 return state;
173 };
174
175 while (!lexer.is_eof()) {
176 consume_whitespace();
177 if (lexer.is_eof())
178 break;
179 if (lexer.consume_specific("@namespace")) {
180 consume_whitespace();
181 state_machine->namespaces = lexer.consume_while([](char c) { return isalpha(c) || c == ':'; });
182 } else if (lexer.consume_specific("@begin")) {
183 consume_whitespace();
184 state_machine->initial_state = consume_identifier();
185 } else if (lexer.consume_specific("@name")) {
186 consume_whitespace();
187 state_machine->name = consume_identifier();
188 } else if (lexer.next_is("@anywhere")) {
189 lexer.consume_specific('@');
190 state_machine->anywhere = consume_state_description();
191 } else if (lexer.consume_specific('@')) {
192 auto directive = consume_identifier().to_deprecated_string();
193 fprintf(stderr, "Unimplemented @ directive %s\n", directive.characters());
194 exit(1);
195 } else {
196 auto description = consume_state_description();
197 state_machine->states.append(description);
198 }
199 }
200
201 if (state_machine->initial_state.is_empty()) {
202 fprintf(stderr, "Missing @begin directive\n");
203 exit(1);
204 } else if (state_machine->name.is_empty()) {
205 fprintf(stderr, "Missing @name directive\n");
206 exit(1);
207 }
208
209 if (state_machine->anywhere.has_value()) {
210 state_machine->anywhere.value().name = "_Anywhere";
211 }
212 return state_machine;
213}
214
215void output_header(StateMachine const&, SourceGenerator&);
216
217ErrorOr<int> serenity_main(Main::Arguments arguments)
218{
219 Core::ArgsParser args_parser;
220 StringView path;
221 args_parser.add_positional_argument(path, "Path to parser description", "input", Core::ArgsParser::Required::Yes);
222 args_parser.parse(arguments);
223
224 auto file = TRY(Core::File::open(path, Core::File::OpenMode::Read));
225 auto content = TRY(file->read_until_eof());
226 auto state_machine = parse_state_machine(content);
227
228 StringBuilder builder;
229 SourceGenerator generator { builder };
230 output_header(*state_machine, generator);
231 outln("{}", generator.as_string_view());
232 return 0;
233}
234
235HashTable<DeprecatedString> actions(StateMachine const& machine)
236{
237 HashTable<DeprecatedString> table;
238
239 auto do_state = [&](State const& state) {
240 if (state.entry_action.has_value())
241 table.set(state.entry_action.value());
242 if (state.exit_action.has_value())
243 table.set(state.exit_action.value());
244 for (auto action : state.actions) {
245 if (action.action.action.has_value())
246 table.set(action.action.action.value());
247 }
248 };
249 for (auto state : machine.states) {
250 do_state(state);
251 }
252 if (machine.anywhere.has_value())
253 do_state(machine.anywhere.value());
254 return table;
255}
256
257void generate_lookup_table(StateMachine const& machine, SourceGenerator& generator)
258{
259 generator.append(R"~~~(
260 static constexpr StateTransition STATE_TRANSITION_TABLE[][256] = {
261)~~~");
262
263 auto generate_for_state = [&](State const& s) {
264 auto table_generator = generator.fork();
265 table_generator.set("active_state", s.name);
266 table_generator.append("/* @active_state@ */ { ");
267 VERIFY(!s.name.is_empty());
268 Vector<StateTransition> row;
269 for (int i = 0; i < 256; i++)
270 row.append({ s.name, "_Ignore" });
271 for (auto action : s.actions) {
272 for (int range_element = action.range.begin; range_element <= action.range.end; range_element++) {
273 row[range_element] = { action.action.new_state, action.action.action };
274 }
275 }
276 for (int i = 0; i < 256; ++i) {
277 auto cell_generator = table_generator.fork();
278 cell_generator.set("cell_new_state", row[i].new_state.value_or(s.name));
279 cell_generator.set("cell_action", row[i].action.value_or("_Ignore"));
280 cell_generator.append(" {State::@cell_new_state@, Action::@cell_action@}, ");
281 }
282 table_generator.append("},\n");
283 };
284 if (machine.anywhere.has_value()) {
285 generate_for_state(machine.anywhere.value());
286 }
287 for (auto s : machine.states) {
288 generate_for_state(s);
289 }
290 generator.append(R"~~~(
291 };
292)~~~");
293}
294
295void output_header(StateMachine const& machine, SourceGenerator& generator)
296{
297 generator.set("class_name", machine.name);
298 generator.set("initial_state", machine.initial_state);
299 generator.set("state_count", DeprecatedString::number(machine.states.size() + 1));
300
301 generator.append(R"~~~(
302#pragma once
303
304#include <AK/Function.h>
305#include <AK/Platform.h>
306#include <AK/Types.h>
307 )~~~");
308 if (machine.namespaces.has_value()) {
309 generator.set("namespace", machine.namespaces.value());
310 generator.append(R"~~~(
311namespace @namespace@ {
312)~~~");
313 }
314 generator.append(R"~~~(
315class @class_name@ {
316public:
317 enum class Action : u8 {
318 _Ignore,
319)~~~");
320 for (auto a : actions(machine)) {
321 if (a.is_empty())
322 continue;
323 auto action_generator = generator.fork();
324 action_generator.set("action.name", a);
325 action_generator.append(R"~~~(
326 @action.name@,
327 )~~~");
328 }
329
330 generator.append(R"~~~(
331 }; // end Action
332
333 using Handler = Function<void(Action, u8)>;
334
335 @class_name@(Handler handler)
336 : m_handler(move(handler))
337 {
338 }
339
340 void advance(u8 byte)
341 {
342 auto next_state = lookup_state_transition(byte);
343 bool state_will_change = next_state.new_state != m_state && next_state.new_state != State::_Anywhere;
344
345 // only run exit directive if state is being changed
346 if (state_will_change) {
347 switch (m_state) {
348)~~~");
349 for (auto s : machine.states) {
350 auto state_generator = generator.fork();
351 if (s.exit_action.has_value()) {
352 state_generator.set("state_name", s.name);
353 state_generator.set("action", s.exit_action.value());
354 state_generator.append(R"~~~(
355 case State::@state_name@:
356 m_handler(Action::@action@, byte);
357 break;
358)~~~");
359 }
360 }
361 generator.append(R"~~~(
362 default:
363 break;
364 }
365 }
366
367 if (next_state.action != Action::_Ignore)
368 m_handler(next_state.action, byte);
369 m_state = next_state.new_state;
370
371 // only run entry directive if state is being changed
372 if (state_will_change)
373 {
374 switch (next_state.new_state)
375 {
376)~~~");
377 for (auto state : machine.states) {
378 auto state_generator = generator.fork();
379 if (state.entry_action.has_value()) {
380 state_generator.set("state_name", state.name);
381 state_generator.set("action", state.entry_action.value());
382 state_generator.append(R"~~~(
383 case State::@state_name@:
384 m_handler(Action::@action@, byte);
385 break;
386)~~~");
387 }
388 }
389 generator.append(R"~~~(
390 default:
391 break;
392 }
393 }
394 }
395
396private:
397 enum class State : u8 {
398 _Anywhere,
399)~~~");
400
401 for (auto s : machine.states) {
402 auto state_generator = generator.fork();
403 state_generator.set("state.name", s.name);
404 state_generator.append(R"~~~(
405 @state.name@,
406)~~~");
407 }
408 generator.append(R"~~~(
409 }; // end State
410
411 struct StateTransition {
412 State new_state;
413 Action action;
414 };
415
416 State m_state { State::@initial_state@ };
417
418 Handler m_handler;
419
420 ALWAYS_INLINE StateTransition lookup_state_transition(u8 byte)
421 {
422 VERIFY((u8)m_state < @state_count@);
423)~~~");
424 if (machine.anywhere.has_value()) {
425 generator.append(R"~~~(
426 auto anywhere_state = STATE_TRANSITION_TABLE[0][byte];
427 if (anywhere_state.new_state != State::_Anywhere || anywhere_state.action != Action::_Ignore)
428 return anywhere_state;
429 else
430)~~~");
431 }
432 generator.append(R"~~~(
433 return STATE_TRANSITION_TABLE[(u8)m_state][byte];
434 }
435)~~~");
436
437 auto table_generator = generator.fork();
438 generate_lookup_table(machine, table_generator);
439 generator.append(R"~~~(
440}; // end @class_name@
441)~~~");
442
443 if (machine.namespaces.has_value()) {
444 generator.append(R"~~~(
445} // end namespace
446)~~~");
447 }
448}