2 #define I3__FILE__ "commands_parser.c"
4 * vim:ts=4:sw=4:expandtab
6 * i3 - an improved dynamic tiling window manager
7 * © 2009-2012 Michael Stapelberg and contributors (see also: LICENSE)
9 * commands_parser.c: hand-written parser to parse commands (commands are what
10 * you bind on keys and what you can send to i3 using the IPC interface, like
11 * 'move left' or 'workspace 4').
13 * We use a hand-written parser instead of lex/yacc because our commands are
14 * easy for humans, not for computers. Thus, it’s quite hard to specify a
15 * context-free grammar for the commands. A PEG grammar would be easier, but
16 * there’s downsides to every PEG parser generator I have come across so far.
18 * This parser is basically a state machine which looks for literals or strings
19 * and can push either on a stack. After identifying a literal or string, it
20 * will either transition to the current state, to a different state, or call a
21 * function (like cmd_move()).
23 * Special care has been taken that error messages are useful and the code is
24 * well testable (when compiled with -DTEST_PARSER it will output to stdout
25 * instead of actually calling any function).
37 // Macros to make the YAJL API a bit easier to use.
38 #define y(x, ...) (command_output.json_gen != NULL ? yajl_gen_##x(command_output.json_gen, ##__VA_ARGS__) : 0)
39 #define ystr(str) (command_output.json_gen != NULL ? yajl_gen_string(command_output.json_gen, (unsigned char *)str, strlen(str)) : 0)
41 /*******************************************************************************
42 * The data structures used for parsing. Essentially the current state and a
43 * list of tokens for that state.
45 * The GENERATED_* files are generated by generate-commands-parser.pl with the
46 * input parser-specs/commands.spec.
47 ******************************************************************************/
49 #include "GENERATED_command_enums.h"
51 typedef struct token {
54 /* This might be __CALL */
55 cmdp_state next_state;
57 uint16_t call_identifier;
61 typedef struct tokenptr {
66 #include "GENERATED_command_tokens.h"
68 /*******************************************************************************
69 * The (small) stack where identified literals are stored during the parsing
70 * of a single command (like $workspace).
71 ******************************************************************************/
74 /* Just a pointer, not dynamically allocated. */
75 const char *identifier;
79 /* 10 entries should be enough for everybody. */
80 static struct stack_entry stack[10];
83 * Pushes a string (identified by 'identifier') on the stack. We simply use a
84 * single array, since the number of entries we have to store is very small.
87 static void push_string(const char *identifier, char *str) {
88 for (int c = 0; c < 10; c++) {
89 if (stack[c].identifier != NULL)
91 /* Found a free slot, let’s store it here. */
92 stack[c].identifier = identifier;
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");
106 // XXX: ideally, this would be const char. need to check if that works with all
108 static char *get_string(const char *identifier) {
109 for (int c = 0; c < 10; c++) {
110 if (stack[c].identifier == NULL)
112 if (strcmp(identifier, stack[c].identifier) == 0)
118 static void clear_stack(void) {
119 for (int c = 0; c < 10; c++) {
120 if (stack[c].str != NULL)
122 stack[c].identifier = NULL;
127 // TODO: remove this if it turns out we don’t need it for testing.
129 /*******************************************************************************
130 * A dynamically growing linked list which holds the criteria for the current
132 ******************************************************************************/
134 typedef struct criterion {
138 TAILQ_ENTRY(criterion) criteria;
141 static TAILQ_HEAD(criteria_head, criterion) criteria =
142 TAILQ_HEAD_INITIALIZER(criteria);
145 * Stores the given type/value in the list of criteria.
146 * Accepts a pointer as first argument, since it is 'call'ed by the parser.
149 static void push_criterion(void *unused_criteria, const char *type,
151 struct criterion *criterion = malloc(sizeof(struct criterion));
152 criterion->type = strdup(type);
153 criterion->value = strdup(value);
154 TAILQ_INSERT_TAIL(&criteria, criterion, criteria);
158 * Clears the criteria linked list.
159 * Accepts a pointer as first argument, since it is 'call'ed by the parser.
162 static void clear_criteria(void *unused_criteria) {
163 struct criterion *criterion;
164 while (!TAILQ_EMPTY(&criteria)) {
165 criterion = TAILQ_FIRST(&criteria);
166 free(criterion->type);
167 free(criterion->value);
168 TAILQ_REMOVE(&criteria, criterion, criteria);
174 /*******************************************************************************
176 ******************************************************************************/
178 static cmdp_state state;
180 static Match current_match;
182 static struct CommandResultIR subcommand_output;
183 static struct CommandResultIR command_output;
185 #include "GENERATED_command_call.h"
187 static void next_state(const cmdp_token *token) {
188 if (token->next_state == __CALL) {
189 subcommand_output.json_gen = command_output.json_gen;
190 subcommand_output.needs_tree_render = false;
191 GENERATED_call(token->extra.call_identifier, &subcommand_output);
192 state = subcommand_output.next_state;
193 /* If any subcommand requires a tree_render(), we need to make the
194 * whole parser result request a tree_render(). */
195 if (subcommand_output.needs_tree_render)
196 command_output.needs_tree_render = true;
201 state = token->next_state;
202 if (state == INITIAL) {
208 * Parses a string (or word, if as_word is true). Extracted out of
209 * parse_command so that it can be used in src/workspace.c for interpreting
210 * workspace commands.
213 char *parse_string(const char **walk, bool as_word) {
214 const char *beginning = *walk;
215 /* Handle quoted strings (or words). */
219 for (; **walk != '\0' && **walk != '"'; (*walk)++)
220 if (**walk == '\\' && *(*walk + 1) != '\0')
224 /* For a string (starting with 's'), the delimiters are
225 * comma (,) and semicolon (;) which introduce a new
226 * operation or command, respectively. Also, newlines
228 while (**walk != ';' && **walk != ',' &&
229 **walk != '\0' && **walk != '\r' &&
233 /* For a word, the delimiters are white space (' ' or
234 * '\t'), closing square bracket (]), comma (,) and
236 while (**walk != ' ' && **walk != '\t' &&
237 **walk != ']' && **walk != ',' &&
238 **walk != ';' && **walk != '\r' &&
239 **walk != '\n' && **walk != '\0')
243 if (*walk == beginning)
246 char *str = scalloc(*walk - beginning + 1);
247 /* We copy manually to handle escaping of characters. */
249 for (inpos = 0, outpos = 0;
250 inpos < (*walk - beginning);
252 /* We only handle escaped double quotes and backslashes to not break
253 * backwards compatibility with people using \w in regular expressions
255 if (beginning[inpos] == '\\' && (beginning[inpos + 1] == '"' || beginning[inpos + 1] == '\\'))
257 str[outpos] = beginning[inpos];
264 * Parses and executes the given command. If a caller-allocated yajl_gen is
265 * passed, a json reply will be generated in the format specified by the ipc
266 * protocol. Pass NULL if no json reply is required.
268 * Free the returned CommandResult with command_result_free().
270 CommandResult *parse_command(const char *input, yajl_gen gen) {
271 DLOG("COMMAND: *%s*\n", input);
273 CommandResult *result = scalloc(sizeof(CommandResult));
275 /* A YAJL JSON generator used for formatting replies. */
276 command_output.json_gen = gen;
279 command_output.needs_tree_render = false;
281 const char *walk = input;
282 const size_t len = strlen(input);
284 const cmdp_token *token;
287 // TODO: make this testable
289 cmd_criteria_init(¤t_match, &subcommand_output);
292 /* The "<=" operator is intentional: We also handle the terminating 0-byte
293 * explicitly by looking for an 'end' token. */
294 while ((size_t)(walk - input) <= len) {
295 /* skip whitespace and newlines before every token */
296 while ((*walk == ' ' || *walk == '\t' ||
297 *walk == '\r' || *walk == '\n') &&
301 cmdp_token_ptr *ptr = &(tokens[state]);
302 token_handled = false;
303 for (c = 0; c < ptr->n; c++) {
304 token = &(ptr->array[c]);
307 if (token->name[0] == '\'') {
308 if (strncasecmp(walk, token->name + 1, strlen(token->name) - 1) == 0) {
309 if (token->identifier != NULL)
310 push_string(token->identifier, sstrdup(token->name + 1));
311 walk += strlen(token->name) - 1;
313 token_handled = true;
319 if (strcmp(token->name, "string") == 0 ||
320 strcmp(token->name, "word") == 0) {
321 char *str = parse_string(&walk, (token->name[0] != 's'));
323 if (token->identifier)
324 push_string(token->identifier, str);
325 /* If we are at the end of a quoted string, skip the ending
330 token_handled = true;
335 if (strcmp(token->name, "end") == 0) {
336 if (*walk == '\0' || *walk == ',' || *walk == ';') {
338 token_handled = true;
339 /* To make sure we start with an appropriate matching
340 * datastructure for commands which do *not* specify any
341 * criteria, we re-initialize the criteria system after
343 // TODO: make this testable
345 if (*walk == '\0' || *walk == ';')
346 cmd_criteria_init(¤t_match, &subcommand_output);
354 if (!token_handled) {
355 /* Figure out how much memory we will need to fill in the names of
356 * all tokens afterwards. */
358 for (c = 0; c < ptr->n; c++)
359 tokenlen += strlen(ptr->array[c].name) + strlen("'', ");
361 /* Build up a decent error message. We include the problem, the
362 * full input, and underline the position where the parser
365 char *possible_tokens = smalloc(tokenlen + 1);
366 char *tokenwalk = possible_tokens;
367 for (c = 0; c < ptr->n; c++) {
368 token = &(ptr->array[c]);
369 if (token->name[0] == '\'') {
370 /* A literal is copied to the error message enclosed with
373 strcpy(tokenwalk, token->name + 1);
374 tokenwalk += strlen(token->name + 1);
377 /* Any other token is copied to the error message enclosed
378 * with angle brackets. */
380 strcpy(tokenwalk, token->name);
381 tokenwalk += strlen(token->name);
384 if (c < (ptr->n - 1)) {
390 sasprintf(&errormessage, "Expected one of these tokens: %s",
392 free(possible_tokens);
394 /* Contains the same amount of characters as 'input' has, but with
395 * the unparseable part highlighted using ^ characters. */
396 char *position = smalloc(len + 1);
397 for (const char *copywalk = input; *copywalk != '\0'; copywalk++)
398 position[(copywalk - input)] = (copywalk >= walk ? '^' : ' ');
399 position[len] = '\0';
401 ELOG("%s\n", errormessage);
402 ELOG("Your command: %s\n", input);
403 ELOG(" %s\n", position);
405 result->parse_error = true;
406 result->error_message = errormessage;
408 /* Format this error message as a JSON reply. */
412 /* We set parse_error to true to distinguish this from other
413 * errors. i3-nagbar is spawned upon keypresses only for parser
421 ystr("errorposition");
433 result->needs_tree_render = command_output.needs_tree_render;
438 * Frees a CommandResult
440 void command_result_free(CommandResult *result) {
444 FREE(result->error_message);
448 /*******************************************************************************
449 * Code for building the stand-alone binary test.commands_parser which is used
450 * by t/187-commands-parser.t.
451 ******************************************************************************/
456 * Logs the given message to stdout while prefixing the current time to it,
457 * but only if debug logging was activated.
458 * This is to be called by DLOG() which includes filename/linenumber
461 void debuglog(char *fmt, ...) {
465 fprintf(stdout, "# ");
466 vfprintf(stdout, fmt, args);
470 void errorlog(char *fmt, ...) {
474 vfprintf(stderr, fmt, args);
478 int main(int argc, char *argv[]) {
480 fprintf(stderr, "Syntax: %s <command>\n", argv[0]);
483 yajl_gen gen = yajl_gen_alloc(NULL);
485 CommandResult *result = parse_command(argv[1], gen);
487 command_result_free(result);