2 * vim:ts=4:sw=4:expandtab
4 * i3 - an improved dynamic tiling window manager
5 * © 2009-2012 Michael Stapelberg and contributors (see also: LICENSE)
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').
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.
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()).
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).
35 /*******************************************************************************
36 * The data structures used for parsing. Essentially the current state and a
37 * list of tokens for that state.
39 * The GENERATED_* files are generated by generate-commands-parser.pl with the
40 * input parser-specs/commands.spec.
41 ******************************************************************************/
43 #include "GENERATED_enums.h"
45 typedef struct token {
48 /* This might be __CALL */
49 cmdp_state next_state;
51 uint16_t call_identifier;
55 typedef struct tokenptr {
60 #include "GENERATED_tokens.h"
62 /*******************************************************************************
63 * The (small) stack where identified literals are stored during the parsing
64 * of a single command (like $workspace).
65 ******************************************************************************/
68 /* Just a pointer, not dynamically allocated. */
69 const char *identifier;
73 /* 10 entries should be enough for everybody. */
74 static struct stack_entry stack[10];
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.
81 static void push_string(const char *identifier, char *str) {
82 for (int c = 0; c < 10; c++) {
83 if (stack[c].identifier != NULL)
85 /* Found a free slot, let’s store it here. */
86 stack[c].identifier = identifier;
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");
100 // XXX: ideally, this would be const char. need to check if that works with all
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)
107 if (strcmp(identifier, stack[c].identifier) == 0)
113 static void clear_stack() {
114 DLOG("clearing stack.\n");
115 for (int c = 0; c < 10; c++) {
116 if (stack[c].str != NULL)
118 stack[c].identifier = NULL;
123 // TODO: remove this if it turns out we don’t need it for testing.
125 /*******************************************************************************
126 * A dynamically growing linked list which holds the criteria for the current
128 ******************************************************************************/
130 typedef struct criterion {
134 TAILQ_ENTRY(criterion) criteria;
137 static TAILQ_HEAD(criteria_head, criterion) criteria =
138 TAILQ_HEAD_INITIALIZER(criteria);
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.
145 static void push_criterion(void *unused_criteria, const char *type,
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);
154 * Clears the criteria linked list.
155 * Accepts a pointer as first argument, since it is 'call'ed by the parser.
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);
170 /*******************************************************************************
172 ******************************************************************************/
174 static cmdp_state state;
176 static Match current_match;
178 static struct CommandResult subcommand_output;
179 static struct CommandResult command_output;
181 #include "GENERATED_call.h"
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);
188 subcommand_output.json_output = NULL;
189 subcommand_output.needs_tree_render = false;
190 GENERATED_call(token->extra.call_identifier, &subcommand_output);
191 if (subcommand_output.json_output) {
192 DLOG("Subcommand JSON output: %s\n", subcommand_output.json_output);
194 /* In the beginning, the contents of json_output are "[\0". */
195 if (command_output.json_output[1] == '\0')
196 sasprintf(&buffer, "%s%s", command_output.json_output, subcommand_output.json_output);
197 else sasprintf(&buffer, "%s, %s", command_output.json_output, subcommand_output.json_output);
198 free(command_output.json_output);
199 command_output.json_output = buffer;
200 DLOG("merged command JSON output: %s\n", command_output.json_output);
202 /* If any subcommand requires a tree_render(), we need to make the
203 * whole parser result request a tree_render(). */
204 if (subcommand_output.needs_tree_render)
205 command_output.needs_tree_render = true;
210 state = token->next_state;
211 if (state == INITIAL) {
216 /* TODO: Return parsing errors via JSON. */
217 struct CommandResult *parse_command(const char *input) {
218 DLOG("new parser handling: %s\n", input);
220 command_output.json_output = sstrdup("[");
221 command_output.needs_tree_render = false;
223 const char *walk = input;
224 const size_t len = strlen(input);
226 const cmdp_token *token;
229 // TODO: make this testable
231 cmd_criteria_init(¤t_match, &subcommand_output);
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')
242 DLOG("remaining input = %s\n", walk);
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);
251 if (token->name[0] == '\'') {
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;
259 token_handled = true;
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). */
273 while (*walk != '\0' && (*walk != '"' || *(walk-1) == '\\'))
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
281 while (*walk != ';' && *walk != ',' &&
282 *walk != '\0' && *walk != '\r' &&
286 /* For a word, the delimiters are white space (' ' or
287 * '\t'), closing square bracket (]), comma (,) and
289 while (*walk != ' ' && *walk != '\t' &&
290 *walk != ']' && *walk != ',' &&
291 *walk != ';' && *walk != '\r' &&
292 *walk != '\n' && *walk != '\0')
296 if (walk != beginning) {
297 char *str = scalloc(walk-beginning + 1);
298 /* We copy manually to handle escaping of characters. */
300 for (inpos = 0, outpos = 0;
301 inpos < (walk-beginning);
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] == '"')
308 str[outpos] = beginning[inpos];
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
318 token_handled = true;
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");
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
333 // TODO: make this testable
335 if (*walk == '\0' || *walk == ';')
336 cmd_criteria_init(¤t_match, &subcommand_output);
344 if (!token_handled) {
345 /* Figure out how much memory we will need to fill in the names of
346 * all tokens afterwards. */
348 for (c = 0; c < ptr->n; c++)
349 tokenlen += strlen(ptr->array[c].name) + strlen("'', ");
351 /* Build up a decent error message. We include the problem, the
352 * full input, and underline the position where the parser
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
363 strcpy(tokenwalk, token->name + 1);
364 tokenwalk += strlen(token->name + 1);
367 /* Any other token is copied to the error message enclosed
368 * with angle brackets. */
370 strcpy(tokenwalk, token->name);
371 tokenwalk += strlen(token->name);
374 if (c < (ptr->n - 1)) {
380 sasprintf(&errormessage, "Expected one of these tokens: %s",
382 free(possible_tokens);
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';
391 printf("%s\n", errormessage);
392 printf("Your command: %s\n", input);
393 printf(" %s\n", position);
403 sasprintf(&buffer, "%s]", command_output.json_output);
404 free(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;
411 /*******************************************************************************
412 * Code for building the stand-alone binary test.commands_parser which is used
413 * by t/187-commands-parser.t.
414 ******************************************************************************/
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
424 void debuglog(uint64_t lev, char *fmt, ...) {
428 fprintf(stderr, "# ");
429 vfprintf(stderr, fmt, args);
433 int main(int argc, char *argv[]) {
435 fprintf(stderr, "Syntax: %s <command>\n", argv[0]);
438 parse_command(argv[1]);