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 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     enum {
  77         STACK_STR = 0,
  78         STACK_LONG = 1,
  79     } type;
  80     union {
  81         char *str;
  82         long num;
  83     } val;
  84 };
  85
  86 /* 10 entries should be enough for everybody. */
  87 static struct stack_entry stack[10];
  88
  89 /*
  90  * Pushes a string (identified by 'identifier') on the stack. We simply use a
  91  * single array, since the number of entries we have to store is very small.
  92  *
  93  */
  94 static void push_string(const char *identifier, char *str) {
  95     for (int c = 0; c < 10; c++) {
  96         if (stack[c].identifier != NULL)
  97             continue;
  98         /* Found a free slot, let’s store it here. */
  99         stack[c].identifier = identifier;
 100         stack[c].val.str = str;
 101         stack[c].type = STACK_STR;
 102         return;
 103     }
 104
 105     /* When we arrive here, the stack is full. This should not happen and
 106      * means there’s either a bug in this parser or the specification
 107      * contains a command with more than 10 identified tokens. */
 108     fprintf(stderr, "BUG: commands_parser stack full. This means either a bug "
 109                     "in the code, or a new command which contains more than "
 110                     "10 identified tokens.\n");
 111     exit(1);
 112 }
 113
 114 // TODO move to a common util
 115 static void push_long(const char *identifier, long num) {
 116     for (int c = 0; c < 10; c++) {
 117         if (stack[c].identifier != NULL) {
 118             continue;
 119         }
 120
 121         stack[c].identifier = identifier;
 122         stack[c].val.num = num;
 123         stack[c].type = STACK_LONG;
 124         return;
 125     }
 126
 127     /* When we arrive here, the stack is full. This should not happen and
 128      * means there’s either a bug in this parser or the specification
 129      * contains a command with more than 10 identified tokens. */
 130     fprintf(stderr, "BUG: commands_parser stack full. This means either a bug "
 131                     "in the code, or a new command which contains more than "
 132                     "10 identified tokens.\n");
 133     exit(1);
 134 }
 135
 136 // XXX: ideally, this would be const char. need to check if that works with all
 137 // called functions.
 138 // TODO move to a common util
 139 static char *get_string(const char *identifier) {
 140     for (int c = 0; c < 10; c++) {
 141         if (stack[c].identifier == NULL)
 142             break;
 143         if (strcmp(identifier, stack[c].identifier) == 0)
 144             return stack[c].val.str;
 145     }
 146     return NULL;
 147 }
 148
 149 // TODO move to a common util
 150 static long get_long(const char *identifier) {
 151     for (int c = 0; c < 10; c++) {
 152         if (stack[c].identifier == NULL)
 153             break;
 154         if (strcmp(identifier, stack[c].identifier) == 0)
 155             return stack[c].val.num;
 156     }
 157
 158     return 0;
 159 }
 160
 161 // TODO move to a common util
 162 static void clear_stack(void) {
 163     for (int c = 0; c < 10; c++) {
 164         if (stack[c].type == STACK_STR && stack[c].val.str != NULL)
 165             free(stack[c].val.str);
 166         stack[c].identifier = NULL;
 167         stack[c].val.str = NULL;
 168         stack[c].val.num = 0;
 169     }
 170 }
 171
 172 /*******************************************************************************
 173  * The parser itself.
 174  ******************************************************************************/
 175
 176 static cmdp_state state;
 177 #ifndef TEST_PARSER
 178 static Match current_match;
 179 #endif
 180 static struct CommandResultIR subcommand_output;
 181 static struct CommandResultIR command_output;
 182
 183 #include "GENERATED_command_call.h"
 184
 185 static void next_state(const cmdp_token *token) {
 186     if (token->next_state == __CALL) {
 187         subcommand_output.json_gen = command_output.json_gen;
 188         subcommand_output.needs_tree_render = false;
 189         GENERATED_call(token->extra.call_identifier, &subcommand_output);
 190         state = subcommand_output.next_state;
 191         /* If any subcommand requires a tree_render(), we need to make the
 192          * whole parser result request a tree_render(). */
 193         if (subcommand_output.needs_tree_render)
 194             command_output.needs_tree_render = true;
 195         clear_stack();
 196         return;
 197     }
 198
 199     state = token->next_state;
 200     if (state == INITIAL) {
 201         clear_stack();
 202     }
 203 }
 204
 205 /*
 206  * Parses a string (or word, if as_word is true). Extracted out of
 207  * parse_command so that it can be used in src/workspace.c for interpreting
 208  * workspace commands.
 209  *
 210  */
 211 char *parse_string(const char **walk, bool as_word) {
 212     const char *beginning = *walk;
 213     /* Handle quoted strings (or words). */
 214     if (**walk == '"') {
 215         beginning++;
 216         (*walk)++;
 217         for (; **walk != '\0' && **walk != '"'; (*walk)++)
 218             if (**walk == '\\' && *(*walk + 1) != '\0')
 219                 (*walk)++;
 220     } else {
 221         if (!as_word) {
 222             /* For a string (starting with 's'), the delimiters are
 223              * comma (,) and semicolon (;) which introduce a new
 224              * operation or command, respectively. Also, newlines
 225              * end a command. */
 226             while (**walk != ';' && **walk != ',' &&
 227                    **walk != '\0' && **walk != '\r' &&
 228                    **walk != '\n')
 229                 (*walk)++;
 230         } else {
 231             /* For a word, the delimiters are white space (' ' or
 232              * '\t'), closing square bracket (]), comma (,) and
 233              * semicolon (;). */
 234             while (**walk != ' ' && **walk != '\t' &&
 235                    **walk != ']' && **walk != ',' &&
 236                    **walk != ';' && **walk != '\r' &&
 237                    **walk != '\n' && **walk != '\0')
 238                 (*walk)++;
 239         }
 240     }
 241     if (*walk == beginning)
 242         return NULL;
 243
 244     char *str = scalloc(*walk - beginning + 1, 1);
 245     /* We copy manually to handle escaping of characters. */
 246     int inpos, outpos;
 247     for (inpos = 0, outpos = 0;
 248          inpos < (*walk - beginning);
 249          inpos++, outpos++) {
 250         /* We only handle escaped double quotes and backslashes to not break
 251          * backwards compatibility with people using \w in regular expressions
 252          * etc. */
 253         if (beginning[inpos] == '\\' && (beginning[inpos + 1] == '"' || beginning[inpos + 1] == '\\'))
 254             inpos++;
 255         str[outpos] = beginning[inpos];
 256     }
 257
 258     return str;
 259 }
 260
 261 /*
 262  * Parses and executes the given command. If a caller-allocated yajl_gen is
 263  * passed, a json reply will be generated in the format specified by the ipc
 264  * protocol. Pass NULL if no json reply is required.
 265  *
 266  * Free the returned CommandResult with command_result_free().
 267  */
 268 CommandResult *parse_command(const char *input, yajl_gen gen) {
 269     DLOG("COMMAND: *%s*\n", input);
 270     state = INITIAL;
 271     CommandResult *result = scalloc(1, sizeof(CommandResult));
 272
 273     /* A YAJL JSON generator used for formatting replies. */
 274     command_output.json_gen = gen;
 275
 276     y(array_open);
 277     command_output.needs_tree_render = false;
 278
 279     const char *walk = input;
 280     const size_t len = strlen(input);
 281     int c;
 282     const cmdp_token *token;
 283     bool token_handled;
 284
 285 // TODO: make this testable
 286 #ifndef TEST_PARSER
 287     cmd_criteria_init(&current_match, &subcommand_output);
 288 #endif
 289
 290     /* The "<=" operator is intentional: We also handle the terminating 0-byte
 291      * explicitly by looking for an 'end' token. */
 292     while ((size_t)(walk - input) <= len) {
 293         /* skip whitespace and newlines before every token */
 294         while ((*walk == ' ' || *walk == '\t' ||
 295                 *walk == '\r' || *walk == '\n') &&
 296                *walk != '\0')
 297             walk++;
 298
 299         cmdp_token_ptr *ptr = &(tokens[state]);
 300         token_handled = false;
 301         for (c = 0; c < ptr->n; c++) {
 302             token = &(ptr->array[c]);
 303
 304             /* A literal. */
 305             if (token->name[0] == '\'') {
 306                 if (strncasecmp(walk, token->name + 1, strlen(token->name) - 1) == 0) {
 307                     if (token->identifier != NULL)
 308                         push_string(token->identifier, sstrdup(token->name + 1));
 309                     walk += strlen(token->name) - 1;
 310                     next_state(token);
 311                     token_handled = true;
 312                     break;
 313                 }
 314                 continue;
 315             }
 316
 317             if (strcmp(token->name, "number") == 0) {
 318                 /* Handle numbers. We only accept decimal numbers for now. */
 319                 char *end = NULL;
 320                 errno = 0;
 321                 long int num = strtol(walk, &end, 10);
 322                 if ((errno == ERANGE && (num == LONG_MIN || num == LONG_MAX)) ||
 323                     (errno != 0 && num == 0))
 324                     continue;
 325
 326                 /* No valid numbers found */
 327                 if (end == walk)
 328                     continue;
 329
 330                 if (token->identifier != NULL)
 331                     push_long(token->identifier, num);
 332
 333                 /* Set walk to the first non-number character */
 334                 walk = end;
 335                 next_state(token);
 336                 token_handled = true;
 337                 break;
 338             }
 339
 340             if (strcmp(token->name, "string") == 0 ||
 341                 strcmp(token->name, "word") == 0) {
 342                 char *str = parse_string(&walk, (token->name[0] != 's'));
 343                 if (str != NULL) {
 344                     if (token->identifier)
 345                         push_string(token->identifier, str);
 346                     /* If we are at the end of a quoted string, skip the ending
 347                      * double quote. */
 348                     if (*walk == '"')
 349                         walk++;
 350                     next_state(token);
 351                     token_handled = true;
 352                     break;
 353                 }
 354             }
 355
 356             if (strcmp(token->name, "end") == 0) {
 357                 if (*walk == '\0' || *walk == ',' || *walk == ';') {
 358                     next_state(token);
 359                     token_handled = true;
 360 /* To make sure we start with an appropriate matching
 361                      * datastructure for commands which do *not* specify any
 362                      * criteria, we re-initialize the criteria system after
 363                      * every command. */
 364 // TODO: make this testable
 365 #ifndef TEST_PARSER
 366                     if (*walk == '\0' || *walk == ';')
 367                         cmd_criteria_init(&current_match, &subcommand_output);
 368 #endif
 369                     walk++;
 370                     break;
 371                 }
 372             }
 373         }
 374
 375         if (!token_handled) {
 376             /* Figure out how much memory we will need to fill in the names of
 377              * all tokens afterwards. */
 378             int tokenlen = 0;
 379             for (c = 0; c < ptr->n; c++)
 380                 tokenlen += strlen(ptr->array[c].name) + strlen("'', ");
 381
 382             /* Build up a decent error message. We include the problem, the
 383              * full input, and underline the position where the parser
 384              * currently is. */
 385             char *errormessage;
 386             char *possible_tokens = smalloc(tokenlen + 1);
 387             char *tokenwalk = possible_tokens;
 388             for (c = 0; c < ptr->n; c++) {
 389                 token = &(ptr->array[c]);
 390                 if (token->name[0] == '\'') {
 391                     /* A literal is copied to the error message enclosed with
 392                      * single quotes. */
 393                     *tokenwalk++ = '\'';
 394                     strcpy(tokenwalk, token->name + 1);
 395                     tokenwalk += strlen(token->name + 1);
 396                     *tokenwalk++ = '\'';
 397                 } else {
 398                     /* Any other token is copied to the error message enclosed
 399                      * with angle brackets. */
 400                     *tokenwalk++ = '<';
 401                     strcpy(tokenwalk, token->name);
 402                     tokenwalk += strlen(token->name);
 403                     *tokenwalk++ = '>';
 404                 }
 405                 if (c < (ptr->n - 1)) {
 406                     *tokenwalk++ = ',';
 407                     *tokenwalk++ = ' ';
 408                 }
 409             }
 410             *tokenwalk = '\0';
 411             sasprintf(&errormessage, "Expected one of these tokens: %s",
 412                       possible_tokens);
 413             free(possible_tokens);
 414
 415             /* Contains the same amount of characters as 'input' has, but with
 416              * the unparseable part highlighted using ^ characters. */
 417             char *position = smalloc(len + 1);
 418             for (const char *copywalk = input; *copywalk != '\0'; copywalk++)
 419                 position[(copywalk - input)] = (copywalk >= walk ? '^' : ' ');
 420             position[len] = '\0';
 421
 422             ELOG("%s\n", errormessage);
 423             ELOG("Your command: %s\n", input);
 424             ELOG("              %s\n", position);
 425
 426             result->parse_error = true;
 427             result->error_message = errormessage;
 428
 429             /* Format this error message as a JSON reply. */
 430             y(map_open);
 431             ystr("success");
 432             y(bool, false);
 433             /* We set parse_error to true to distinguish this from other
 434              * errors. i3-nagbar is spawned upon keypresses only for parser
 435              * errors. */
 436             ystr("parse_error");
 437             y(bool, true);
 438             ystr("error");
 439             ystr(errormessage);
 440             ystr("input");
 441             ystr(input);
 442             ystr("errorposition");
 443             ystr(position);
 444             y(map_close);
 445
 446             free(position);
 447             clear_stack();
 448             break;
 449         }
 450     }
 451
 452     y(array_close);
 453
 454     result->needs_tree_render = command_output.needs_tree_render;
 455     return result;
 456 }
 457
 458 /*
 459  * Frees a CommandResult
 460  */
 461 void command_result_free(CommandResult *result) {
 462     if (result == NULL)
 463         return;
 464
 465     FREE(result->error_message);
 466     FREE(result);
 467 }
 468
 469 /*******************************************************************************
 470  * Code for building the stand-alone binary test.commands_parser which is used
 471  * by t/187-commands-parser.t.
 472  ******************************************************************************/
 473
 474 #ifdef TEST_PARSER
 475
 476 /*
 477  * Logs the given message to stdout while prefixing the current time to it,
 478  * but only if debug logging was activated.
 479  * This is to be called by DLOG() which includes filename/linenumber
 480  *
 481  */
 482 void debuglog(char *fmt, ...) {
 483     va_list args;
 484
 485     va_start(args, fmt);
 486     fprintf(stdout, "# ");
 487     vfprintf(stdout, fmt, args);
 488     va_end(args);
 489 }
 490
 491 void errorlog(char *fmt, ...) {
 492     va_list args;
 493
 494     va_start(args, fmt);
 495     vfprintf(stderr, fmt, args);
 496     va_end(args);
 497 }
 498
 499 int main(int argc, char *argv[]) {
 500     if (argc < 2) {
 501         fprintf(stderr, "Syntax: %s <command>\n", argv[0]);
 502         return 1;
 503     }
 504     yajl_gen gen = yajl_gen_alloc(NULL);
 505
 506     CommandResult *result = parse_command(argv[1], gen);
 507
 508     command_result_free(result);
 509
 510     yajl_gen_free(gen);
 511 }
 512 #endif