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

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