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 across 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, ...) (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)
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 
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 
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_command_call.h"
186 
187 static void next_state(const cmdp_token *token) {
188  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 /*
208  * Parses and executes the given command. If a caller-allocated yajl_gen is
209  * passed, a json reply will be generated in the format specified by the ipc
210  * protocol. Pass NULL if no json reply is required.
211  *
212  * Free the returned CommandResult with command_result_free().
213  */
214 CommandResult *parse_command(const char *input, yajl_gen gen) {
215  DLOG("COMMAND: *%s*\n", input);
216  state = INITIAL;
217  CommandResult *result = scalloc(sizeof(CommandResult));
218 
219  /* A YAJL JSON generator used for formatting replies. */
220  command_output.json_gen = gen;
221 
222  y(array_open);
224 
225  const char *walk = input;
226  const size_t len = strlen(input);
227  int c;
228  const cmdp_token *token;
229  bool token_handled;
230 
231 // TODO: make this testable
232 #ifndef TEST_PARSER
234 #endif
235 
236  /* The "<=" operator is intentional: We also handle the terminating 0-byte
237  * explicitly by looking for an 'end' token. */
238  while ((size_t)(walk - input) <= len) {
239  /* skip whitespace and newlines before every token */
240  while ((*walk == ' ' || *walk == '\t' ||
241  *walk == '\r' || *walk == '\n') &&
242  *walk != '\0')
243  walk++;
244 
245  cmdp_token_ptr *ptr = &(tokens[state]);
246  token_handled = false;
247  for (c = 0; c < ptr->n; c++) {
248  token = &(ptr->array[c]);
249 
250  /* A literal. */
251  if (token->name[0] == '\'') {
252  if (strncasecmp(walk, token->name + 1, strlen(token->name) - 1) == 0) {
253  if (token->identifier != NULL)
254  push_string(token->identifier, sstrdup(token->name + 1));
255  walk += strlen(token->name) - 1;
256  next_state(token);
257  token_handled = true;
258  break;
259  }
260  continue;
261  }
262 
263  if (strcmp(token->name, "string") == 0 ||
264  strcmp(token->name, "word") == 0) {
265  const char *beginning = walk;
266  /* Handle quoted strings (or words). */
267  if (*walk == '"') {
268  beginning++;
269  walk++;
270  while (*walk != '\0' && (*walk != '"' || *(walk - 1) == '\\'))
271  walk++;
272  } else {
273  if (token->name[0] == 's') {
274  /* For a string (starting with 's'), the delimiters are
275  * comma (,) and semicolon (;) which introduce a new
276  * operation or command, respectively. Also, newlines
277  * end a command. */
278  while (*walk != ';' && *walk != ',' &&
279  *walk != '\0' && *walk != '\r' &&
280  *walk != '\n')
281  walk++;
282  } else {
283  /* For a word, the delimiters are white space (' ' or
284  * '\t'), closing square bracket (]), comma (,) and
285  * semicolon (;). */
286  while (*walk != ' ' && *walk != '\t' &&
287  *walk != ']' && *walk != ',' &&
288  *walk != ';' && *walk != '\r' &&
289  *walk != '\n' && *walk != '\0')
290  walk++;
291  }
292  }
293  if (walk != beginning) {
294  char *str = scalloc(walk - beginning + 1);
295  /* We copy manually to handle escaping of characters. */
296  int inpos, outpos;
297  for (inpos = 0, outpos = 0;
298  inpos < (walk - beginning);
299  inpos++, outpos++) {
300  /* We only handle escaped double quotes to not break
301  * backwards compatibility with people using \w in
302  * regular expressions etc. */
303  if (beginning[inpos] == '\\' && beginning[inpos + 1] == '"')
304  inpos++;
305  str[outpos] = beginning[inpos];
306  }
307  if (token->identifier)
308  push_string(token->identifier, str);
309  /* If we are at the end of a quoted string, skip the ending
310  * double quote. */
311  if (*walk == '"')
312  walk++;
313  next_state(token);
314  token_handled = true;
315  break;
316  }
317  }
318 
319  if (strcmp(token->name, "end") == 0) {
320  if (*walk == '\0' || *walk == ',' || *walk == ';') {
321  next_state(token);
322  token_handled = true;
323 /* To make sure we start with an appropriate matching
324  * datastructure for commands which do *not* specify any
325  * criteria, we re-initialize the criteria system after
326  * every command. */
327 // TODO: make this testable
328 #ifndef TEST_PARSER
329  if (*walk == '\0' || *walk == ';')
331 #endif
332  walk++;
333  break;
334  }
335  }
336  }
337 
338  if (!token_handled) {
339  /* Figure out how much memory we will need to fill in the names of
340  * all tokens afterwards. */
341  int tokenlen = 0;
342  for (c = 0; c < ptr->n; c++)
343  tokenlen += strlen(ptr->array[c].name) + strlen("'', ");
344 
345  /* Build up a decent error message. We include the problem, the
346  * full input, and underline the position where the parser
347  * currently is. */
348  char *errormessage;
349  char *possible_tokens = smalloc(tokenlen + 1);
350  char *tokenwalk = possible_tokens;
351  for (c = 0; c < ptr->n; c++) {
352  token = &(ptr->array[c]);
353  if (token->name[0] == '\'') {
354  /* A literal is copied to the error message enclosed with
355  * single quotes. */
356  *tokenwalk++ = '\'';
357  strcpy(tokenwalk, token->name + 1);
358  tokenwalk += strlen(token->name + 1);
359  *tokenwalk++ = '\'';
360  } else {
361  /* Any other token is copied to the error message enclosed
362  * with angle brackets. */
363  *tokenwalk++ = '<';
364  strcpy(tokenwalk, token->name);
365  tokenwalk += strlen(token->name);
366  *tokenwalk++ = '>';
367  }
368  if (c < (ptr->n - 1)) {
369  *tokenwalk++ = ',';
370  *tokenwalk++ = ' ';
371  }
372  }
373  *tokenwalk = '\0';
374  sasprintf(&errormessage, "Expected one of these tokens: %s",
375  possible_tokens);
376  free(possible_tokens);
377 
378  /* Contains the same amount of characters as 'input' has, but with
379  * the unparseable part highlighted using ^ characters. */
380  char *position = smalloc(len + 1);
381  for (const char *copywalk = input; *copywalk != '\0'; copywalk++)
382  position[(copywalk - input)] = (copywalk >= walk ? '^' : ' ');
383  position[len] = '\0';
384 
385  ELOG("%s\n", errormessage);
386  ELOG("Your command: %s\n", input);
387  ELOG(" %s\n", position);
388 
389  result->parse_error = true;
390  result->error_message = errormessage;
391 
392  /* Format this error message as a JSON reply. */
393  y(map_open);
394  ystr("success");
395  y(bool, false);
396  /* We set parse_error to true to distinguish this from other
397  * errors. i3-nagbar is spawned upon keypresses only for parser
398  * errors. */
399  ystr("parse_error");
400  y(bool, true);
401  ystr("error");
402  ystr(errormessage);
403  ystr("input");
404  ystr(input);
405  ystr("errorposition");
406  ystr(position);
407  y(map_close);
408 
409  free(position);
410  clear_stack();
411  break;
412  }
413  }
414 
415  y(array_close);
416 
418  return result;
419 }
420 
421 /*
422  * Frees a CommandResult
423  */
425  if (result == NULL)
426  return;
427 
428  FREE(result->error_message);
429  FREE(result);
430 }
431 
432 /*******************************************************************************
433  * Code for building the stand-alone binary test.commands_parser which is used
434  * by t/187-commands-parser.t.
435  ******************************************************************************/
436 
437 #ifdef TEST_PARSER
438 
439 /*
440  * Logs the given message to stdout while prefixing the current time to it,
441  * but only if debug logging was activated.
442  * This is to be called by DLOG() which includes filename/linenumber
443  *
444  */
445 void debuglog(char *fmt, ...) {
446  va_list args;
447 
448  va_start(args, fmt);
449  fprintf(stdout, "# ");
450  vfprintf(stdout, fmt, args);
451  va_end(args);
452 }
453 
454 void errorlog(char *fmt, ...) {
455  va_list args;
456 
457  va_start(args, fmt);
458  vfprintf(stderr, fmt, args);
459  va_end(args);
460 }
461 
462 int main(int argc, char *argv[]) {
463  if (argc < 2) {
464  fprintf(stderr, "Syntax: %s <command>\n", argv[0]);
465  return 1;
466  }
467  yajl_gen gen = yajl_gen_alloc(NULL);
468 
469  CommandResult *result = parse_command(argv[1], gen);
470 
471  command_result_free(result);
472 
473  yajl_gen_free(gen);
474 }
475 #endif
char * sstrdup(const char *str)
Safe-wrapper around strdup which exits if malloc returns NULL (meaning that there is no more memory a...
static struct CommandResultIR command_output
static void GENERATED_call(const int call_identifier, struct CommandResultIR *result)
#define TAILQ_REMOVE(head, elm, field)
Definition: queue.h:386
static void next_state(const cmdp_token *token)
struct tokenptr cmdp_token_ptr
CommandResult * parse_command(const char *input, yajl_gen gen)
Parses and executes the given command.
#define TAILQ_FIRST(head)
Definition: queue.h:323
union token::@0 extra
void command_result_free(CommandResult *result)
Frees a CommandResult.
uint16_t call_identifier
static Match current_match
static struct stack_entry stack[10]
#define DLOG(fmt,...)
Definition: libi3.h:86
static cmdp_state state
A struct that contains useful information about the result of a command as a whole (e...
int sasprintf(char **strp, const char *fmt,...)
Safe-wrapper around asprintf which exits if it returns -1 (meaning that there is no more memory avail...
static char * get_string(const char *identifier)
static void clear_stack(void)
void errorlog(char *fmt,...)
Definition: log.c:295
char * error_message
char * identifier
static void push_string(const char *identifier, char *str)
#define TAILQ_EMPTY(head)
Definition: queue.h:331
#define TAILQ_ENTRY(type)
Definition: queue.h:314
#define ELOG(fmt,...)
Definition: libi3.h:81
A "match" is a data structure which acts like a mask or expression to match certain windows or not...
Definition: data.h:390
static struct CommandResultIR subcommand_output
#define y(x,...)
void debuglog(char *fmt,...)
Definition: log.c:315
cmdp_token * array
static cmdp_token_ptr tokens[51]
void * scalloc(size_t size)
Safe-wrapper around calloc which exits if malloc returns NULL (meaning that there is no more memory a...
#define ystr(str)
const char * identifier
struct token cmdp_token
#define TAILQ_INSERT_TAIL(head, elm, field)
Definition: queue.h:362
#define TAILQ_HEAD_INITIALIZER(head)
Definition: queue.h:311
void cmd_criteria_init(I3_CMD)
Initializes the specified 'Match' data structure and the initial state of commands.c for matching target windows of a command.
int main(int argc, char *argv[])
Definition: main.c:268
void * smalloc(size_t size)
Safe-wrapper around malloc which exits if malloc returns NULL (meaning that there is no more memory a...
char * name
#define FREE(pointer)
Definition: util.h:46
cmdp_state next_state
#define TAILQ_HEAD(name, type)
Definition: queue.h:305