2 * vim:ts=4:sw=4:expandtab
4 * i3 - an improved dynamic tiling window manager
5 * © 2009 Michael Stapelberg and contributors (see also: LICENSE)
7 * commands_parser.c: hand-written parser to parse commands (commands are what
8 * you bind on keys and what you can send to i3 using the IPC interface, like
9 * 'move left' or 'workspace 4').
11 * We use a hand-written parser instead of lex/yacc because our commands are
12 * easy for humans, not for computers. Thus, it’s quite hard to specify a
13 * context-free grammar for the commands. A PEG grammar would be easier, but
14 * there’s downsides to every PEG parser generator I have come across so far.
16 * This parser is basically a state machine which looks for literals or strings
17 * and can push either on a stack. After identifying a literal or string, it
18 * will either transition to the current state, to a different state, or call a
19 * function (like cmd_move()).
21 * Special care has been taken that error messages are useful and the code is
22 * well testable (when compiled with -DTEST_PARSER it will output to stdout
23 * instead of actually calling any function).
35 // Macros to make the YAJL API a bit easier to use.
36 #define y(x, ...) (command_output.json_gen != NULL ? yajl_gen_##x(command_output.json_gen, ##__VA_ARGS__) : 0)
37 #define ystr(str) (command_output.json_gen != NULL ? yajl_gen_string(command_output.json_gen, (unsigned char *)str, strlen(str)) : 0)
39 /*******************************************************************************
40 * The data structures used for parsing. Essentially the current state and a
41 * list of tokens for that state.
43 * The GENERATED_* files are generated by generate-commands-parser.pl with the
44 * input parser-specs/commands.spec.
45 ******************************************************************************/
47 #include "GENERATED_command_enums.h"
49 typedef struct token {
52 /* This might be __CALL */
53 cmdp_state next_state;
55 uint16_t call_identifier;
59 typedef struct tokenptr {
64 #include "GENERATED_command_tokens.h"
66 /*******************************************************************************
67 * The (small) stack where identified literals are stored during the parsing
68 * of a single command (like $workspace).
69 ******************************************************************************/
72 /* Just a pointer, not dynamically allocated. */
73 const char *identifier;
84 /* 10 entries should be enough for everybody. */
85 static struct stack_entry stack[10];
88 * Pushes a string (identified by 'identifier') on the stack. We simply use a
89 * single array, since the number of entries we have to store is very small.
92 static void push_string(const char *identifier, char *str) {
93 for (int c = 0; c < 10; c++) {
94 if (stack[c].identifier != NULL)
96 /* Found a free slot, let’s store it here. */
97 stack[c].identifier = identifier;
98 stack[c].val.str = str;
99 stack[c].type = STACK_STR;
103 /* When we arrive here, the stack is full. This should not happen and
104 * means there’s either a bug in this parser or the specification
105 * contains a command with more than 10 identified tokens. */
106 fprintf(stderr, "BUG: commands_parser stack full. This means either a bug "
107 "in the code, or a new command which contains more than "
108 "10 identified tokens.\n");
112 // TODO move to a common util
113 static void push_long(const char *identifier, long num) {
114 for (int c = 0; c < 10; c++) {
115 if (stack[c].identifier != NULL) {
119 stack[c].identifier = identifier;
120 stack[c].val.num = num;
121 stack[c].type = STACK_LONG;
125 /* When we arrive here, the stack is full. This should not happen and
126 * means there’s either a bug in this parser or the specification
127 * contains a command with more than 10 identified tokens. */
128 fprintf(stderr, "BUG: commands_parser stack full. This means either a bug "
129 "in the code, or a new command which contains more than "
130 "10 identified tokens.\n");
134 // TODO move to a common util
135 static const char *get_string(const char *identifier) {
136 for (int c = 0; c < 10; c++) {
137 if (stack[c].identifier == NULL)
139 if (strcmp(identifier, stack[c].identifier) == 0)
140 return stack[c].val.str;
145 // TODO move to a common util
146 static long get_long(const char *identifier) {
147 for (int c = 0; c < 10; c++) {
148 if (stack[c].identifier == NULL)
150 if (strcmp(identifier, stack[c].identifier) == 0)
151 return stack[c].val.num;
157 // TODO move to a common util
158 static void clear_stack(void) {
159 for (int c = 0; c < 10; c++) {
160 if (stack[c].type == STACK_STR)
161 free(stack[c].val.str);
162 stack[c].identifier = NULL;
163 stack[c].val.str = NULL;
164 stack[c].val.num = 0;
168 /*******************************************************************************
170 ******************************************************************************/
172 static cmdp_state state;
174 static Match current_match;
176 static struct CommandResultIR subcommand_output;
177 static struct CommandResultIR command_output;
179 #include "GENERATED_command_call.h"
181 static void next_state(const cmdp_token *token) {
182 if (token->next_state == __CALL) {
183 subcommand_output.json_gen = command_output.json_gen;
184 subcommand_output.needs_tree_render = false;
185 GENERATED_call(token->extra.call_identifier, &subcommand_output);
186 state = subcommand_output.next_state;
187 /* If any subcommand requires a tree_render(), we need to make the
188 * whole parser result request a tree_render(). */
189 if (subcommand_output.needs_tree_render)
190 command_output.needs_tree_render = true;
195 state = token->next_state;
196 if (state == INITIAL) {
202 * Parses a string (or word, if as_word is true). Extracted out of
203 * parse_command so that it can be used in src/workspace.c for interpreting
204 * workspace commands.
207 char *parse_string(const char **walk, bool as_word) {
208 const char *beginning = *walk;
209 /* Handle quoted strings (or words). */
213 for (; **walk != '\0' && **walk != '"'; (*walk)++)
214 if (**walk == '\\' && *(*walk + 1) != '\0')
218 /* For a string (starting with 's'), the delimiters are
219 * comma (,) and semicolon (;) which introduce a new
220 * operation or command, respectively. Also, newlines
222 while (**walk != ';' && **walk != ',' &&
223 **walk != '\0' && **walk != '\r' &&
227 /* For a word, the delimiters are white space (' ' or
228 * '\t'), closing square bracket (]), comma (,) and
230 while (**walk != ' ' && **walk != '\t' &&
231 **walk != ']' && **walk != ',' &&
232 **walk != ';' && **walk != '\r' &&
233 **walk != '\n' && **walk != '\0')
237 if (*walk == beginning)
240 char *str = scalloc(*walk - beginning + 1, 1);
241 /* We copy manually to handle escaping of characters. */
243 for (inpos = 0, outpos = 0;
244 inpos < (*walk - beginning);
246 /* We only handle escaped double quotes and backslashes to not break
247 * backwards compatibility with people using \w in regular expressions
249 if (beginning[inpos] == '\\' && (beginning[inpos + 1] == '"' || beginning[inpos + 1] == '\\'))
251 str[outpos] = beginning[inpos];
258 * Parses and executes the given command. If a caller-allocated yajl_gen is
259 * passed, a json reply will be generated in the format specified by the ipc
260 * protocol. Pass NULL if no json reply is required.
262 * Free the returned CommandResult with command_result_free().
264 CommandResult *parse_command(const char *input, yajl_gen gen) {
265 DLOG("COMMAND: *%s*\n", input);
267 CommandResult *result = scalloc(1, sizeof(CommandResult));
269 /* A YAJL JSON generator used for formatting replies. */
270 command_output.json_gen = gen;
273 command_output.needs_tree_render = false;
275 const char *walk = input;
276 const size_t len = strlen(input);
278 const cmdp_token *token;
281 // TODO: make this testable
283 cmd_criteria_init(¤t_match, &subcommand_output);
286 /* The "<=" operator is intentional: We also handle the terminating 0-byte
287 * explicitly by looking for an 'end' token. */
288 while ((size_t)(walk - input) <= len) {
289 /* skip whitespace and newlines before every token */
290 while ((*walk == ' ' || *walk == '\t' ||
291 *walk == '\r' || *walk == '\n') &&
295 cmdp_token_ptr *ptr = &(tokens[state]);
296 token_handled = false;
297 for (c = 0; c < ptr->n; c++) {
298 token = &(ptr->array[c]);
301 if (token->name[0] == '\'') {
302 if (strncasecmp(walk, token->name + 1, strlen(token->name) - 1) == 0) {
303 if (token->identifier != NULL)
304 push_string(token->identifier, sstrdup(token->name + 1));
305 walk += strlen(token->name) - 1;
307 token_handled = true;
313 if (strcmp(token->name, "number") == 0) {
314 /* Handle numbers. We only accept decimal numbers for now. */
317 long int num = strtol(walk, &end, 10);
318 if ((errno == ERANGE && (num == LONG_MIN || num == LONG_MAX)) ||
319 (errno != 0 && num == 0))
322 /* No valid numbers found */
326 if (token->identifier != NULL)
327 push_long(token->identifier, num);
329 /* Set walk to the first non-number character */
332 token_handled = true;
336 if (strcmp(token->name, "string") == 0 ||
337 strcmp(token->name, "word") == 0) {
338 char *str = parse_string(&walk, (token->name[0] != 's'));
340 if (token->identifier)
341 push_string(token->identifier, str);
342 /* If we are at the end of a quoted string, skip the ending
347 token_handled = true;
352 if (strcmp(token->name, "end") == 0) {
353 if (*walk == '\0' || *walk == ',' || *walk == ';') {
355 token_handled = true;
356 /* To make sure we start with an appropriate matching
357 * datastructure for commands which do *not* specify any
358 * criteria, we re-initialize the criteria system after
360 // TODO: make this testable
362 if (*walk == '\0' || *walk == ';')
363 cmd_criteria_init(¤t_match, &subcommand_output);
371 if (!token_handled) {
372 /* Figure out how much memory we will need to fill in the names of
373 * all tokens afterwards. */
375 for (c = 0; c < ptr->n; c++)
376 tokenlen += strlen(ptr->array[c].name) + strlen("'', ");
378 /* Build up a decent error message. We include the problem, the
379 * full input, and underline the position where the parser
382 char *possible_tokens = smalloc(tokenlen + 1);
383 char *tokenwalk = possible_tokens;
384 for (c = 0; c < ptr->n; c++) {
385 token = &(ptr->array[c]);
386 if (token->name[0] == '\'') {
387 /* A literal is copied to the error message enclosed with
390 strcpy(tokenwalk, token->name + 1);
391 tokenwalk += strlen(token->name + 1);
394 /* Any other token is copied to the error message enclosed
395 * with angle brackets. */
397 strcpy(tokenwalk, token->name);
398 tokenwalk += strlen(token->name);
401 if (c < (ptr->n - 1)) {
407 sasprintf(&errormessage, "Expected one of these tokens: %s",
409 free(possible_tokens);
411 /* Contains the same amount of characters as 'input' has, but with
412 * the unparseable part highlighted using ^ characters. */
413 char *position = smalloc(len + 1);
414 for (const char *copywalk = input; *copywalk != '\0'; copywalk++)
415 position[(copywalk - input)] = (copywalk >= walk ? '^' : ' ');
416 position[len] = '\0';
418 ELOG("%s\n", errormessage);
419 ELOG("Your command: %s\n", input);
420 ELOG(" %s\n", position);
422 result->parse_error = true;
423 result->error_message = errormessage;
425 /* Format this error message as a JSON reply. */
429 /* We set parse_error to true to distinguish this from other
430 * errors. i3-nagbar is spawned upon keypresses only for parser
438 ystr("errorposition");
450 result->needs_tree_render = command_output.needs_tree_render;
455 * Frees a CommandResult
457 void command_result_free(CommandResult *result) {
461 FREE(result->error_message);
465 /*******************************************************************************
466 * Code for building the stand-alone binary test.commands_parser which is used
467 * by t/187-commands-parser.t.
468 ******************************************************************************/
473 * Logs the given message to stdout while prefixing the current time to it,
474 * but only if debug logging was activated.
475 * This is to be called by DLOG() which includes filename/linenumber
478 void debuglog(char *fmt, ...) {
482 fprintf(stdout, "# ");
483 vfprintf(stdout, fmt, args);
487 void errorlog(char *fmt, ...) {
491 vfprintf(stderr, fmt, args);
495 int main(int argc, char *argv[]) {
497 fprintf(stderr, "Syntax: %s <command>\n", argv[0]);
500 yajl_gen gen = yajl_gen_alloc(NULL);
502 CommandResult *result = parse_command(argv[1], gen);
504 command_result_free(result);