i3
commands_parser.c
Go to the documentation of this file.
1 /*
2  * vim:ts=4:sw=4:expandtab
3  *
4  * i3 - an improved dynamic tiling window manager
5  * © 2009-2012 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 accross 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 <stdio.h>
27 #include <stdlib.h>
28 #include <string.h>
29 #include <unistd.h>
30 #include <stdbool.h>
31 #include <stdint.h>
32 
33 #include "all.h"
34 
35 /*******************************************************************************
36  * The data structures used for parsing. Essentially the current state and a
37  * list of tokens for that state.
38  *
39  * The GENERATED_* files are generated by generate-commands-parser.pl with the
40  * input parser-specs/commands.spec.
41  ******************************************************************************/
42 
43 #include "GENERATED_enums.h"
44 
45 typedef struct token {
46  char *name;
47  char *identifier;
48  /* This might be __CALL */
50  union {
51  uint16_t call_identifier;
52  } extra;
53 } cmdp_token;
54 
55 typedef struct tokenptr {
57  int n;
59 
60 #include "GENERATED_tokens.h"
61 
62 /*******************************************************************************
63  * The (small) stack where identified literals are stored during the parsing
64  * of a single command (like $workspace).
65  ******************************************************************************/
66 
67 struct stack_entry {
68  /* Just a pointer, not dynamically allocated. */
69  const char *identifier;
70  char *str;
71 };
72 
73 /* 10 entries should be enough for everybody. */
74 static struct stack_entry stack[10];
75 
76 /*
77  * Pushes a string (identified by 'identifier') on the stack. We simply use a
78  * single array, since the number of entries we have to store is very small.
79  *
80  */
81 static void push_string(const char *identifier, char *str) {
82  for (int c = 0; c < 10; c++) {
83  if (stack[c].identifier != NULL)
84  continue;
85  /* Found a free slot, let’s store it here. */
87  stack[c].str = str;
88  return;
89  }
90 
91  /* When we arrive here, the stack is full. This should not happen and
92  * means there’s either a bug in this parser or the specification
93  * contains a command with more than 10 identified tokens. */
94  fprintf(stderr, "BUG: commands_parser stack full. This means either a bug "
95  "in the code, or a new command which contains more than "
96  "10 identified tokens.\n");
97  exit(1);
98 }
99 
100 // XXX: ideally, this would be const char. need to check if that works with all
101 // called functions.
102 static char *get_string(const char *identifier) {
103  DLOG("Getting string %s from stack...\n", identifier);
104  for (int c = 0; c < 10; c++) {
105  if (stack[c].identifier == NULL)
106  break;
107  if (strcmp(identifier, stack[c].identifier) == 0)
108  return stack[c].str;
109  }
110  return NULL;
111 }
112 
113 static void clear_stack(void) {
114  DLOG("clearing stack.\n");
115  for (int c = 0; c < 10; c++) {
116  if (stack[c].str != NULL)
117  free(stack[c].str);
118  stack[c].identifier = NULL;
119  stack[c].str = NULL;
120  }
121 }
122 
123 // TODO: remove this if it turns out we don’t need it for testing.
124 #if 0
125 /*******************************************************************************
126  * A dynamically growing linked list which holds the criteria for the current
127  * command.
128  ******************************************************************************/
129 
130 typedef struct criterion {
131  char *type;
132  char *value;
133 
134  TAILQ_ENTRY(criterion) criteria;
135 } criterion;
136 
137 static TAILQ_HEAD(criteria_head, criterion) criteria =
138  TAILQ_HEAD_INITIALIZER(criteria);
139 
140 /*
141  * Stores the given type/value in the list of criteria.
142  * Accepts a pointer as first argument, since it is 'call'ed by the parser.
143  *
144  */
145 static void push_criterion(void *unused_criteria, const char *type,
146  const char *value) {
147  struct criterion *criterion = malloc(sizeof(struct criterion));
148  criterion->type = strdup(type);
149  criterion->value = strdup(value);
150  TAILQ_INSERT_TAIL(&criteria, criterion, criteria);
151 }
152 
153 /*
154  * Clears the criteria linked list.
155  * Accepts a pointer as first argument, since it is 'call'ed by the parser.
156  *
157  */
158 static void clear_criteria(void *unused_criteria) {
159  struct criterion *criterion;
160  while (!TAILQ_EMPTY(&criteria)) {
161  criterion = TAILQ_FIRST(&criteria);
162  free(criterion->type);
163  free(criterion->value);
164  TAILQ_REMOVE(&criteria, criterion, criteria);
165  free(criterion);
166  }
167 }
168 #endif
169 
170 /*******************************************************************************
171  * The parser itself.
172  ******************************************************************************/
173 
175 #ifndef TEST_PARSER
177 #endif
180 
181 #include "GENERATED_call.h"
182 
183 
184 static void next_state(const cmdp_token *token) {
185  if (token->next_state == __CALL) {
186  DLOG("should call stuff, yay. call_id = %d\n",
187  token->extra.call_identifier);
192  DLOG("Subcommand JSON output: %s\n", subcommand_output.json_output);
193  char *buffer;
194  /* In the beginning, the contents of json_output are "[\0". */
195  if (command_output.json_output[1] == '\0')
199  command_output.json_output = buffer;
200  DLOG("merged command JSON output: %s\n", command_output.json_output);
201  }
202  /* If any subcommand requires a tree_render(), we need to make the
203  * whole parser result request a tree_render(). */
206  clear_stack();
207  return;
208  }
209 
210  state = token->next_state;
211  if (state == INITIAL) {
212  clear_stack();
213  }
214 }
215 
216 /* TODO: Return parsing errors via JSON. */
217 struct CommandResult *parse_command(const char *input) {
218  DLOG("new parser handling: %s\n", input);
219  state = INITIAL;
222 
223  const char *walk = input;
224  const size_t len = strlen(input);
225  int c;
226  const cmdp_token *token;
227  bool token_handled;
228 
229  // TODO: make this testable
230 #ifndef TEST_PARSER
232 #endif
233 
234  /* The "<=" operator is intentional: We also handle the terminating 0-byte
235  * explicitly by looking for an 'end' token. */
236  while ((walk - input) <= len) {
237  /* skip whitespace and newlines before every token */
238  while ((*walk == ' ' || *walk == '\t' ||
239  *walk == '\r' || *walk == '\n') && *walk != '\0')
240  walk++;
241 
242  DLOG("remaining input = %s\n", walk);
243 
244  cmdp_token_ptr *ptr = &(tokens[state]);
245  token_handled = false;
246  for (c = 0; c < ptr->n; c++) {
247  token = &(ptr->array[c]);
248  DLOG("trying token %d = %s\n", c, token->name);
249 
250  /* A literal. */
251  if (token->name[0] == '\'') {
252  DLOG("literal\n");
253  if (strncasecmp(walk, token->name + 1, strlen(token->name) - 1) == 0) {
254  DLOG("found literal, moving to next state\n");
255  if (token->identifier != NULL)
256  push_string(token->identifier, sstrdup(token->name + 1));
257  walk += strlen(token->name) - 1;
258  next_state(token);
259  token_handled = true;
260  break;
261  }
262  continue;
263  }
264 
265  if (strcmp(token->name, "string") == 0 ||
266  strcmp(token->name, "word") == 0) {
267  DLOG("parsing this as a string\n");
268  const char *beginning = walk;
269  /* Handle quoted strings (or words). */
270  if (*walk == '"') {
271  beginning++;
272  walk++;
273  while (*walk != '\0' && (*walk != '"' || *(walk-1) == '\\'))
274  walk++;
275  } else {
276  if (token->name[0] == 's') {
277  /* For a string (starting with 's'), the delimiters are
278  * comma (,) and semicolon (;) which introduce a new
279  * operation or command, respectively. Also, newlines
280  * end a command. */
281  while (*walk != ';' && *walk != ',' &&
282  *walk != '\0' && *walk != '\r' &&
283  *walk != '\n')
284  walk++;
285  } else {
286  /* For a word, the delimiters are white space (' ' or
287  * '\t'), closing square bracket (]), comma (,) and
288  * semicolon (;). */
289  while (*walk != ' ' && *walk != '\t' &&
290  *walk != ']' && *walk != ',' &&
291  *walk != ';' && *walk != '\r' &&
292  *walk != '\n' && *walk != '\0')
293  walk++;
294  }
295  }
296  if (walk != beginning) {
297  char *str = scalloc(walk-beginning + 1);
298  /* We copy manually to handle escaping of characters. */
299  int inpos, outpos;
300  for (inpos = 0, outpos = 0;
301  inpos < (walk-beginning);
302  inpos++, outpos++) {
303  /* We only handle escaped double quotes to not break
304  * backwards compatibility with people using \w in
305  * regular expressions etc. */
306  if (beginning[inpos] == '\\' && beginning[inpos+1] == '"')
307  inpos++;
308  str[outpos] = beginning[inpos];
309  }
310  if (token->identifier)
311  push_string(token->identifier, str);
312  DLOG("str is \"%s\"\n", str);
313  /* If we are at the end of a quoted string, skip the ending
314  * double quote. */
315  if (*walk == '"')
316  walk++;
317  next_state(token);
318  token_handled = true;
319  break;
320  }
321  }
322 
323  if (strcmp(token->name, "end") == 0) {
324  DLOG("checking for the end token.\n");
325  if (*walk == '\0' || *walk == ',' || *walk == ';') {
326  DLOG("yes, indeed. end\n");
327  next_state(token);
328  token_handled = true;
329  /* To make sure we start with an appropriate matching
330  * datastructure for commands which do *not* specify any
331  * criteria, we re-initialize the criteria system after
332  * every command. */
333  // TODO: make this testable
334 #ifndef TEST_PARSER
335  if (*walk == '\0' || *walk == ';')
337 #endif
338  walk++;
339  break;
340  }
341  }
342  }
343 
344  if (!token_handled) {
345  /* Figure out how much memory we will need to fill in the names of
346  * all tokens afterwards. */
347  int tokenlen = 0;
348  for (c = 0; c < ptr->n; c++)
349  tokenlen += strlen(ptr->array[c].name) + strlen("'', ");
350 
351  /* Build up a decent error message. We include the problem, the
352  * full input, and underline the position where the parser
353  * currently is. */
354  char *errormessage;
355  char *possible_tokens = smalloc(tokenlen + 1);
356  char *tokenwalk = possible_tokens;
357  for (c = 0; c < ptr->n; c++) {
358  token = &(ptr->array[c]);
359  if (token->name[0] == '\'') {
360  /* A literal is copied to the error message enclosed with
361  * single quotes. */
362  *tokenwalk++ = '\'';
363  strcpy(tokenwalk, token->name + 1);
364  tokenwalk += strlen(token->name + 1);
365  *tokenwalk++ = '\'';
366  } else {
367  /* Any other token is copied to the error message enclosed
368  * with angle brackets. */
369  *tokenwalk++ = '<';
370  strcpy(tokenwalk, token->name);
371  tokenwalk += strlen(token->name);
372  *tokenwalk++ = '>';
373  }
374  if (c < (ptr->n - 1)) {
375  *tokenwalk++ = ',';
376  *tokenwalk++ = ' ';
377  }
378  }
379  *tokenwalk = '\0';
380  sasprintf(&errormessage, "Expected one of these tokens: %s",
381  possible_tokens);
382  free(possible_tokens);
383 
384  /* Contains the same amount of characters as 'input' has, but with
385  * the unparseable part highlighted using ^ characters. */
386  char *position = smalloc(len + 1);
387  for (const char *copywalk = input; *copywalk != '\0'; copywalk++)
388  position[(copywalk - input)] = (copywalk >= walk ? '^' : ' ');
389  position[len] = '\0';
390 
391  printf("%s\n", errormessage);
392  printf("Your command: %s\n", input);
393  printf(" %s\n", position);
394 
395  free(position);
396  free(errormessage);
397  clear_stack();
398  break;
399  }
400  }
401 
402  char *buffer;
403  sasprintf(&buffer, "%s]", command_output.json_output);
405  command_output.json_output = buffer;
406  DLOG("command_output.json_output = %s\n", command_output.json_output);
407  DLOG("command_output.needs_tree_render = %d\n", command_output.needs_tree_render);
408  return &command_output;
409 }
410 
411 /*******************************************************************************
412  * Code for building the stand-alone binary test.commands_parser which is used
413  * by t/187-commands-parser.t.
414  ******************************************************************************/
415 
416 #ifdef TEST_PARSER
417 
418 /*
419  * Logs the given message to stdout while prefixing the current time to it,
420  * but only if the corresponding debug loglevel was activated.
421  * This is to be called by DLOG() which includes filename/linenumber
422  *
423  */
424 void debuglog(uint64_t lev, char *fmt, ...) {
425  va_list args;
426 
427  va_start(args, fmt);
428  fprintf(stderr, "# ");
429  vfprintf(stderr, fmt, args);
430  va_end(args);
431 }
432 
433 int main(int argc, char *argv[]) {
434  if (argc < 2) {
435  fprintf(stderr, "Syntax: %s <command>\n", argv[0]);
436  return 1;
437  }
438  parse_command(argv[1]);
439 }
440 #endif