1 /*
2 * vim:ts=4:sw=4:expandtab
3 *
4 * i3 - an improved dynamic tiling window manager
5 * © 2009 Michael Stapelberg and contributors (see also: LICENSE)
6 *
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').
10 *
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.
15 *
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()).
20 *
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).
24 *
25 */
26 #include "all.h"
27
28 // Macros to make the YAJL API a bit easier to use.
29 #define y(x, ...) (command_output.json_gen != NULL ? yajl_gen_##x(command_output.json_gen, ##__VA_ARGS__) : 0)
30 #define ystr(str) (command_output.json_gen != NULL ? yajl_gen_string(command_output.json_gen, (unsigned char *)str, strlen(str)) : 0)
31
32 /*******************************************************************************
33 * The data structures used for parsing. Essentially the current state and a
34 * list of tokens for that state.
35 *
36 * The GENERATED_* files are generated by generate-commands-parser.pl with the
37 * input parser-specs/commands.spec.
38 ******************************************************************************/
39
40 #include "GENERATED_command_enums.h"
41
42 typedef struct token {
43 char *name;
44 char *identifier;
45 /* This might be __CALL */
46 cmdp_state next_state;
47 union {
48 uint16_t call_identifier;
49 } extra;
50 } cmdp_token;
51
52 typedef struct tokenptr {
53 cmdp_token *array;
54 int n;
55 } cmdp_token_ptr;
56
57 #include "GENERATED_command_tokens.h"
58
59 /*
60 * Pushes a string (identified by 'identifier') on the stack. We simply use a
61 * single array, since the number of entries we have to store is very small.
62 *
63 */
push_string(struct stack * stack,const char * identifier,char * str)64 static void push_string(struct stack *stack, const char *identifier, char *str) {
65 for (int c = 0; c < 10; c++) {
66 if (stack->stack[c].identifier != NULL)
67 continue;
68 /* Found a free slot, let’s store it here. */
69 stack->stack[c].identifier = identifier;
70 stack->stack[c].val.str = str;
71 stack->stack[c].type = STACK_STR;
72 return;
73 }
74
75 /* When we arrive here, the stack is full. This should not happen and
76 * means there’s either a bug in this parser or the specification
77 * contains a command with more than 10 identified tokens. */
78 fprintf(stderr, "BUG: commands_parser stack full. This means either a bug "
79 "in the code, or a new command which contains more than "
80 "10 identified tokens.\n");
81 exit(EXIT_FAILURE);
82 }
83
84 // TODO move to a common util
push_long(struct stack * stack,const char * identifier,long num)85 static void push_long(struct stack *stack, const char *identifier, long num) {
86 for (int c = 0; c < 10; c++) {
87 if (stack->stack[c].identifier != NULL) {
88 continue;
89 }
90
91 stack->stack[c].identifier = identifier;
92 stack->stack[c].val.num = num;
93 stack->stack[c].type = STACK_LONG;
94 return;
95 }
96
97 /* When we arrive here, the stack is full. This should not happen and
98 * means there’s either a bug in this parser or the specification
99 * contains a command with more than 10 identified tokens. */
100 fprintf(stderr, "BUG: commands_parser stack full. This means either a bug "
101 "in the code, or a new command which contains more than "
102 "10 identified tokens.\n");
103 exit(EXIT_FAILURE);
104 }
105
106 // TODO move to a common util
get_string(struct stack * stack,const char * identifier)107 static const char *get_string(struct stack *stack, const char *identifier) {
108 for (int c = 0; c < 10; c++) {
109 if (stack->stack[c].identifier == NULL)
110 break;
111 if (strcmp(identifier, stack->stack[c].identifier) == 0)
112 return stack->stack[c].val.str;
113 }
114 return NULL;
115 }
116
117 // TODO move to a common util
get_long(struct stack * stack,const char * identifier)118 static long get_long(struct stack *stack, const char *identifier) {
119 for (int c = 0; c < 10; c++) {
120 if (stack->stack[c].identifier == NULL)
121 break;
122 if (strcmp(identifier, stack->stack[c].identifier) == 0)
123 return stack->stack[c].val.num;
124 }
125
126 return 0;
127 }
128
129 // TODO move to a common util
clear_stack(struct stack * stack)130 static void clear_stack(struct stack *stack) {
131 for (int c = 0; c < 10; c++) {
132 if (stack->stack[c].type == STACK_STR)
133 free(stack->stack[c].val.str);
134 stack->stack[c].identifier = NULL;
135 stack->stack[c].val.str = NULL;
136 stack->stack[c].val.num = 0;
137 }
138 }
139
140 /*******************************************************************************
141 * The parser itself.
142 ******************************************************************************/
143
144 static cmdp_state state;
145 static Match current_match;
146 /*******************************************************************************
147 * The (small) stack where identified literals are stored during the parsing
148 * of a single command (like $workspace).
149 ******************************************************************************/
150 static struct stack stack;
151 static struct CommandResultIR subcommand_output;
152 static struct CommandResultIR command_output;
153
154 #include "GENERATED_command_call.h"
155
next_state(const cmdp_token * token)156 static void next_state(const cmdp_token *token) {
157 if (token->next_state == __CALL) {
158 subcommand_output.json_gen = command_output.json_gen;
159 subcommand_output.client = command_output.client;
160 subcommand_output.needs_tree_render = false;
161 GENERATED_call(¤t_match, &stack, token->extra.call_identifier, &subcommand_output);
162 state = subcommand_output.next_state;
163 /* If any subcommand requires a tree_render(), we need to make the
164 * whole parser result request a tree_render(). */
165 if (subcommand_output.needs_tree_render)
166 command_output.needs_tree_render = true;
167 clear_stack(&stack);
168 return;
169 }
170
171 state = token->next_state;
172 if (state == INITIAL) {
173 clear_stack(&stack);
174 }
175 }
176
177 /*
178 * Parses a string (or word, if as_word is true). Extracted out of
179 * parse_command so that it can be used in src/workspace.c for interpreting
180 * workspace commands.
181 *
182 */
parse_string(const char ** walk,bool as_word)183 char *parse_string(const char **walk, bool as_word) {
184 const char *beginning = *walk;
185 /* Handle quoted strings (or words). */
186 if (**walk == '"') {
187 beginning++;
188 (*walk)++;
189 for (; **walk != '\0' && **walk != '"'; (*walk)++)
190 if (**walk == '\\' && *(*walk + 1) != '\0')
191 (*walk)++;
192 } else {
193 if (!as_word) {
194 /* For a string (starting with 's'), the delimiters are
195 * comma (,) and semicolon (;) which introduce a new
196 * operation or command, respectively. Also, newlines
197 * end a command. */
198 while (**walk != ';' && **walk != ',' &&
199 **walk != '\0' && **walk != '\r' &&
200 **walk != '\n')
201 (*walk)++;
202 } else {
203 /* For a word, the delimiters are white space (' ' or
204 * '\t'), closing square bracket (]), comma (,) and
205 * semicolon (;). */
206 while (**walk != ' ' && **walk != '\t' &&
207 **walk != ']' && **walk != ',' &&
208 **walk != ';' && **walk != '\r' &&
209 **walk != '\n' && **walk != '\0')
210 (*walk)++;
211 }
212 }
213 if (*walk == beginning)
214 return NULL;
215
216 char *str = scalloc(*walk - beginning + 1, 1);
217 /* We copy manually to handle escaping of characters. */
218 int inpos, outpos;
219 for (inpos = 0, outpos = 0;
220 inpos < (*walk - beginning);
221 inpos++, outpos++) {
222 /* We only handle escaped double quotes and backslashes to not break
223 * backwards compatibility with people using \w in regular expressions
224 * etc. */
225 if (beginning[inpos] == '\\' && (beginning[inpos + 1] == '"' || beginning[inpos + 1] == '\\'))
226 inpos++;
227 str[outpos] = beginning[inpos];
228 }
229
230 return str;
231 }
232
233 /*
234 * Parses and executes the given command. If a caller-allocated yajl_gen is
235 * passed, a json reply will be generated in the format specified by the ipc
236 * protocol. Pass NULL if no json reply is required.
237 *
238 * Free the returned CommandResult with command_result_free().
239 */
parse_command(const char * input,yajl_gen gen,ipc_client * client)240 CommandResult *parse_command(const char *input, yajl_gen gen, ipc_client *client) {
241 DLOG("COMMAND: *%.4000s*\n", input);
242 state = INITIAL;
243 CommandResult *result = scalloc(1, sizeof(CommandResult));
244
245 command_output.client = client;
246
247 /* A YAJL JSON generator used for formatting replies. */
248 command_output.json_gen = gen;
249
250 y(array_open);
251 command_output.needs_tree_render = false;
252
253 const char *walk = input;
254 const size_t len = strlen(input);
255 int c;
256 const cmdp_token *token;
257 bool token_handled;
258
259 // TODO: make this testable
260 #ifndef TEST_PARSER
261 cmd_criteria_init(¤t_match, &subcommand_output);
262 #endif
263
264 /* The "<=" operator is intentional: We also handle the terminating 0-byte
265 * explicitly by looking for an 'end' token. */
266 while ((size_t)(walk - input) <= len) {
267 /* skip whitespace and newlines before every token */
268 while ((*walk == ' ' || *walk == '\t' ||
269 *walk == '\r' || *walk == '\n') &&
270 *walk != '\0')
271 walk++;
272
273 cmdp_token_ptr *ptr = &(tokens[state]);
274 token_handled = false;
275 for (c = 0; c < ptr->n; c++) {
276 token = &(ptr->array[c]);
277
278 /* A literal. */
279 if (token->name[0] == '\'') {
280 if (strncasecmp(walk, token->name + 1, strlen(token->name) - 1) == 0) {
281 if (token->identifier != NULL) {
282 push_string(&stack, token->identifier, sstrdup(token->name + 1));
283 }
284 walk += strlen(token->name) - 1;
285 next_state(token);
286 token_handled = true;
287 break;
288 }
289 continue;
290 }
291
292 if (strcmp(token->name, "number") == 0) {
293 /* Handle numbers. We only accept decimal numbers for now. */
294 char *end = NULL;
295 errno = 0;
296 long int num = strtol(walk, &end, 10);
297 if ((errno == ERANGE && (num == LONG_MIN || num == LONG_MAX)) ||
298 (errno != 0 && num == 0))
299 continue;
300
301 /* No valid numbers found */
302 if (end == walk)
303 continue;
304
305 if (token->identifier != NULL) {
306 push_long(&stack, token->identifier, num);
307 }
308
309 /* Set walk to the first non-number character */
310 walk = end;
311 next_state(token);
312 token_handled = true;
313 break;
314 }
315
316 if (strcmp(token->name, "string") == 0 ||
317 strcmp(token->name, "word") == 0) {
318 char *str = parse_string(&walk, (token->name[0] != 's'));
319 if (str != NULL) {
320 if (token->identifier) {
321 push_string(&stack, token->identifier, str);
322 }
323 /* If we are at the end of a quoted string, skip the ending
324 * double quote. */
325 if (*walk == '"')
326 walk++;
327 next_state(token);
328 token_handled = true;
329 break;
330 }
331 }
332
333 if (strcmp(token->name, "end") == 0) {
334 if (*walk == '\0' || *walk == ',' || *walk == ';') {
335 next_state(token);
336 token_handled = true;
337 /* To make sure we start with an appropriate matching
338 * datastructure for commands which do *not* specify any
339 * criteria, we re-initialize the criteria system after
340 * every command. */
341 // TODO: make this testable
342 #ifndef TEST_PARSER
343 if (*walk == '\0' || *walk == ';')
344 cmd_criteria_init(¤t_match, &subcommand_output);
345 #endif
346 walk++;
347 break;
348 }
349 }
350 }
351
352 if (!token_handled) {
353 /* Figure out how much memory we will need to fill in the names of
354 * all tokens afterwards. */
355 int tokenlen = 0;
356 for (c = 0; c < ptr->n; c++)
357 tokenlen += strlen(ptr->array[c].name) + strlen("'', ");
358
359 /* Build up a decent error message. We include the problem, the
360 * full input, and underline the position where the parser
361 * currently is. */
362 char *errormessage;
363 char *possible_tokens = smalloc(tokenlen + 1);
364 char *tokenwalk = possible_tokens;
365 for (c = 0; c < ptr->n; c++) {
366 token = &(ptr->array[c]);
367 if (token->name[0] == '\'') {
368 /* A literal is copied to the error message enclosed with
369 * single quotes. */
370 *tokenwalk++ = '\'';
371 strcpy(tokenwalk, token->name + 1);
372 tokenwalk += strlen(token->name + 1);
373 *tokenwalk++ = '\'';
374 } else {
375 /* Any other token is copied to the error message enclosed
376 * with angle brackets. */
377 *tokenwalk++ = '<';
378 strcpy(tokenwalk, token->name);
379 tokenwalk += strlen(token->name);
380 *tokenwalk++ = '>';
381 }
382 if (c < (ptr->n - 1)) {
383 *tokenwalk++ = ',';
384 *tokenwalk++ = ' ';
385 }
386 }
387 *tokenwalk = '\0';
388 sasprintf(&errormessage, "Expected one of these tokens: %s",
389 possible_tokens);
390 free(possible_tokens);
391
392 /* Contains the same amount of characters as 'input' has, but with
393 * the unparseable part highlighted using ^ characters. */
394 char *position = smalloc(len + 1);
395 for (const char *copywalk = input; *copywalk != '\0'; copywalk++)
396 position[(copywalk - input)] = (copywalk >= walk ? '^' : ' ');
397 position[len] = '\0';
398
399 ELOG("%s\n", errormessage);
400 ELOG("Your command: %s\n", input);
401 ELOG(" %s\n", position);
402
403 result->parse_error = true;
404 result->error_message = errormessage;
405
406 /* Format this error message as a JSON reply. */
407 y(map_open);
408 ystr("success");
409 y(bool, false);
410 /* We set parse_error to true to distinguish this from other
411 * errors. i3-nagbar is spawned upon keypresses only for parser
412 * errors. */
413 ystr("parse_error");
414 y(bool, true);
415 ystr("error");
416 ystr(errormessage);
417 ystr("input");
418 ystr(input);
419 ystr("errorposition");
420 ystr(position);
421 y(map_close);
422
423 free(position);
424 clear_stack(&stack);
425 break;
426 }
427 }
428
429 y(array_close);
430
431 result->needs_tree_render = command_output.needs_tree_render;
432 return result;
433 }
434
435 /*
436 * Frees a CommandResult
437 */
command_result_free(CommandResult * result)438 void command_result_free(CommandResult *result) {
439 if (result == NULL)
440 return;
441
442 FREE(result->error_message);
443 FREE(result);
444 }
445
446 /*******************************************************************************
447 * Code for building the stand-alone binary test.commands_parser which is used
448 * by t/187-commands-parser.t.
449 ******************************************************************************/
450
451 #ifdef TEST_PARSER
452
453 /*
454 * Logs the given message to stdout while prefixing the current time to it,
455 * but only if debug logging was activated.
456 * This is to be called by DLOG() which includes filename/linenumber
457 *
458 */
debuglog(char * fmt,...)459 void debuglog(char *fmt, ...) {
460 va_list args;
461
462 va_start(args, fmt);
463 fprintf(stdout, "# ");
464 vfprintf(stdout, fmt, args);
465 va_end(args);
466 }
467
errorlog(char * fmt,...)468 void errorlog(char *fmt, ...) {
469 va_list args;
470
471 va_start(args, fmt);
472 vfprintf(stderr, fmt, args);
473 va_end(args);
474 }
475
main(int argc,char * argv[])476 int main(int argc, char *argv[]) {
477 if (argc < 2) {
478 fprintf(stderr, "Syntax: %s <command>\n", argv[0]);
479 return 1;
480 }
481 yajl_gen gen = yajl_gen_alloc(NULL);
482
483 CommandResult *result = parse_command(argv[1], gen, NULL);
484
485 command_result_free(result);
486
487 yajl_gen_free(gen);
488 }
489 #endif
490