git.sur5r.net Git - i3/i3/blob - src/commands_parser.c

   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
  49 #include "GENERATED_command_enums.h"
  50
  51 typedef struct token {
  52     char *name;
  53     char *identifier;
  54     /* This might be __CALL */
  55     cmdp_state next_state;
  56     union {
  57         uint16_t call_identifier;
  58     } extra;
  59 } cmdp_token;
  60
  61 typedef struct tokenptr {
  62     cmdp_token *array;
  63     int n;
  64 } cmdp_token_ptr;
  65
  66 #include "GENERATED_command_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. */
  92         stack[c].identifier = identifier;
  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
 178 static cmdp_state state;
 179 #ifndef TEST_PARSER
 180 static Match current_match;
 181 #endif
 182 static struct CommandResultIR subcommand_output;
 183 static struct CommandResultIR command_output;
 184
 185 #include "GENERATED_command_call.h"
 186
 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;
 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 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.
 211  *
 212  */
 213 char *parse_string(const char **walk, bool as_word) {
 214     const char *beginning = *walk;
 215     /* Handle quoted strings (or words). */
 216     if (**walk == '"') {
 217         beginning++;
 218         (*walk)++;
 219         for (; **walk != '\0' && **walk != '"'; (*walk)++)
 220             if (**walk == '\\' && *(*walk + 1) != '\0')
 221                 (*walk)++;
 222     } else {
 223         if (!as_word) {
 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
 227              * end a command. */
 228             while (**walk != ';' && **walk != ',' &&
 229                    **walk != '\0' && **walk != '\r' &&
 230                    **walk != '\n')
 231                 (*walk)++;
 232         } else {
 233             /* For a word, the delimiters are white space (' ' or
 234              * '\t'), closing square bracket (]), comma (,) and
 235              * semicolon (;). */
 236             while (**walk != ' ' && **walk != '\t' &&
 237                    **walk != ']' && **walk != ',' &&
 238                    **walk != ';' && **walk != '\r' &&
 239                    **walk != '\n' && **walk != '\0')
 240                 (*walk)++;
 241         }
 242     }
 243     if (*walk == beginning)
 244         return NULL;
 245
 246     char *str = scalloc(*walk - beginning + 1);
 247     /* We copy manually to handle escaping of characters. */
 248     int inpos, outpos;
 249     for (inpos = 0, outpos = 0;
 250          inpos < (*walk - beginning);
 251          inpos++, outpos++) {
 252         /* We only handle escaped double quotes and backslashes to not break
 253          * backwards compatibility with people using \w in regular expressions
 254          * etc. */
 255         if (beginning[inpos] == '\\' && (beginning[inpos + 1] == '"' || beginning[inpos + 1] == '\\'))
 256             inpos++;
 257         str[outpos] = beginning[inpos];
 258     }
 259
 260     return str;
 261 }
 262
 263 /*
 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.
 267  *
 268  * Free the returned CommandResult with command_result_free().
 269  */
 270 CommandResult *parse_command(const char *input, yajl_gen gen) {
 271     DLOG("COMMAND: *%s*\n", input);
 272     state = INITIAL;
 273     CommandResult *result = scalloc(sizeof(CommandResult));
 274
 275     /* A YAJL JSON generator used for formatting replies. */
 276     command_output.json_gen = gen;
 277
 278     y(array_open);
 279     command_output.needs_tree_render = false;
 280
 281     const char *walk = input;
 282     const size_t len = strlen(input);
 283     int c;
 284     const cmdp_token *token;
 285     bool token_handled;
 286
 287 // TODO: make this testable
 288 #ifndef TEST_PARSER
 289     cmd_criteria_init(&current_match, &subcommand_output);
 290 #endif
 291
 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') &&
 298                *walk != '\0')
 299             walk++;
 300
 301         cmdp_token_ptr *ptr = &(tokens[state]);
 302         token_handled = false;
 303         for (c = 0; c < ptr->n; c++) {
 304             token = &(ptr->array[c]);
 305
 306             /* A literal. */
 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;
 312                     next_state(token);
 313                     token_handled = true;
 314                     break;
 315                 }
 316                 continue;
 317             }
 318
 319             if (strcmp(token->name, "string") == 0 ||
 320                 strcmp(token->name, "word") == 0) {
 321                 char *str = parse_string(&walk, (token->name[0] != 's'));
 322                 if (str != NULL) {
 323                     if (token->identifier)
 324                         push_string(token->identifier, str);
 325                     /* If we are at the end of a quoted string, skip the ending
 326                      * double quote. */
 327                     if (*walk == '"')
 328                         walk++;
 329                     next_state(token);
 330                     token_handled = true;
 331                     break;
 332                 }
 333             }
 334
 335             if (strcmp(token->name, "end") == 0) {
 336                 if (*walk == '\0' || *walk == ',' || *walk == ';') {
 337                     next_state(token);
 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
 342                      * every command. */
 343 // TODO: make this testable
 344 #ifndef TEST_PARSER
 345                     if (*walk == '\0' || *walk == ';')
 346                         cmd_criteria_init(&current_match, &subcommand_output);
 347 #endif
 348                     walk++;
 349                     break;
 350                 }
 351             }
 352         }
 353
 354         if (!token_handled) {
 355             /* Figure out how much memory we will need to fill in the names of
 356              * all tokens afterwards. */
 357             int tokenlen = 0;
 358             for (c = 0; c < ptr->n; c++)
 359                 tokenlen += strlen(ptr->array[c].name) + strlen("'', ");
 360
 361             /* Build up a decent error message. We include the problem, the
 362              * full input, and underline the position where the parser
 363              * currently is. */
 364             char *errormessage;
 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
 371                      * single quotes. */
 372                     *tokenwalk++ = '\'';
 373                     strcpy(tokenwalk, token->name + 1);
 374                     tokenwalk += strlen(token->name + 1);
 375                     *tokenwalk++ = '\'';
 376                 } else {
 377                     /* Any other token is copied to the error message enclosed
 378                      * with angle brackets. */
 379                     *tokenwalk++ = '<';
 380                     strcpy(tokenwalk, token->name);
 381                     tokenwalk += strlen(token->name);
 382                     *tokenwalk++ = '>';
 383                 }
 384                 if (c < (ptr->n - 1)) {
 385                     *tokenwalk++ = ',';
 386                     *tokenwalk++ = ' ';
 387                 }
 388             }
 389             *tokenwalk = '\0';
 390             sasprintf(&errormessage, "Expected one of these tokens: %s",
 391                       possible_tokens);
 392             free(possible_tokens);
 393
 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';
 400
 401             ELOG("%s\n", errormessage);
 402             ELOG("Your command: %s\n", input);
 403             ELOG("              %s\n", position);
 404
 405             result->parse_error = true;
 406             result->error_message = errormessage;
 407
 408             /* Format this error message as a JSON reply. */
 409             y(map_open);
 410             ystr("success");
 411             y(bool, false);
 412             /* We set parse_error to true to distinguish this from other
 413              * errors. i3-nagbar is spawned upon keypresses only for parser
 414              * errors. */
 415             ystr("parse_error");
 416             y(bool, true);
 417             ystr("error");
 418             ystr(errormessage);
 419             ystr("input");
 420             ystr(input);
 421             ystr("errorposition");
 422             ystr(position);
 423             y(map_close);
 424
 425             free(position);
 426             clear_stack();
 427             break;
 428         }
 429     }
 430
 431     y(array_close);
 432
 433     result->needs_tree_render = command_output.needs_tree_render;
 434     return result;
 435 }
 436
 437 /*
 438  * Frees a CommandResult
 439  */
 440 void command_result_free(CommandResult *result) {
 441     if (result == NULL)
 442         return;
 443
 444     FREE(result->error_message);
 445     FREE(result);
 446 }
 447
 448 /*******************************************************************************
 449  * Code for building the stand-alone binary test.commands_parser which is used
 450  * by t/187-commands-parser.t.
 451  ******************************************************************************/
 452
 453 #ifdef TEST_PARSER
 454
 455 /*
 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
 459  *
 460  */
 461 void debuglog(char *fmt, ...) {
 462     va_list args;
 463
 464     va_start(args, fmt);
 465     fprintf(stdout, "# ");
 466     vfprintf(stdout, fmt, args);
 467     va_end(args);
 468 }
 469
 470 void errorlog(char *fmt, ...) {
 471     va_list args;
 472
 473     va_start(args, fmt);
 474     vfprintf(stderr, fmt, args);
 475     va_end(args);
 476 }
 477
 478 int main(int argc, char *argv[]) {
 479     if (argc < 2) {
 480         fprintf(stderr, "Syntax: %s <command>\n", argv[0]);
 481         return 1;
 482     }
 483     yajl_gen gen = yajl_gen_alloc(NULL);
 484
 485     CommandResult *result = parse_command(argv[1], gen);
 486
 487     command_result_free(result);
 488
 489     yajl_gen_free(gen);
 490 }
 491 #endif