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