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-2012 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 accross 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 <stdio.h>
  27 #include <stdlib.h>
  28 #include <string.h>
  29 #include <unistd.h>
  30 #include <stdbool.h>
  31 #include <stdint.h>
  32
  33 #include "all.h"
  34
  35 /*******************************************************************************
  36  * The data structures used for parsing. Essentially the current state and a
  37  * list of tokens for that state.
  38  *
  39  * The GENERATED_* files are generated by generate-commands-parser.pl with the
  40  * input parser-specs/commands.spec.
  41  ******************************************************************************/
  42
  43 #include "GENERATED_enums.h"
  44
  45 typedef struct token {
  46     char *name;
  47     char *identifier;
  48     /* This might be __CALL */
  49     cmdp_state next_state;
  50     union {
  51         uint16_t call_identifier;
  52     } extra;
  53 } cmdp_token;
  54
  55 typedef struct tokenptr {
  56     cmdp_token *array;
  57     int n;
  58 } cmdp_token_ptr;
  59
  60 #include "GENERATED_tokens.h"
  61
  62 /*******************************************************************************
  63  * The (small) stack where identified literals are stored during the parsing
  64  * of a single command (like $workspace).
  65  ******************************************************************************/
  66
  67 struct stack_entry {
  68     /* Just a pointer, not dynamically allocated. */
  69     const char *identifier;
  70     char *str;
  71 };
  72
  73 /* 10 entries should be enough for everybody. */
  74 static struct stack_entry stack[10];
  75
  76 /*
  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.
  79  *
  80  */
  81 static void push_string(const char *identifier, char *str) {
  82     for (int c = 0; c < 10; c++) {
  83         if (stack[c].identifier != NULL)
  84             continue;
  85         /* Found a free slot, let’s store it here. */
  86         stack[c].identifier = identifier;
  87         stack[c].str = str;
  88         return;
  89     }
  90
  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");
  97     exit(1);
  98 }
  99
 100 // XXX: ideally, this would be const char. need to check if that works with all
 101 // called functions.
 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)
 106             break;
 107         if (strcmp(identifier, stack[c].identifier) == 0)
 108             return stack[c].str;
 109     }
 110     return NULL;
 111 }
 112
 113 static void clear_stack(void) {
 114     DLOG("clearing stack.\n");
 115     for (int c = 0; c < 10; c++) {
 116         if (stack[c].str != NULL)
 117             free(stack[c].str);
 118         stack[c].identifier = NULL;
 119         stack[c].str = NULL;
 120     }
 121 }
 122
 123 // TODO: remove this if it turns out we don’t need it for testing.
 124 #if 0
 125 /*******************************************************************************
 126  * A dynamically growing linked list which holds the criteria for the current
 127  * command.
 128  ******************************************************************************/
 129
 130 typedef struct criterion {
 131     char *type;
 132     char *value;
 133
 134     TAILQ_ENTRY(criterion) criteria;
 135 } criterion;
 136
 137 static TAILQ_HEAD(criteria_head, criterion) criteria =
 138   TAILQ_HEAD_INITIALIZER(criteria);
 139
 140 /*
 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.
 143  *
 144  */
 145 static void push_criterion(void *unused_criteria, const char *type,
 146                            const char *value) {
 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);
 151 }
 152
 153 /*
 154  * Clears the criteria linked list.
 155  * Accepts a pointer as first argument, since it is 'call'ed by the parser.
 156  *
 157  */
 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);
 165         free(criterion);
 166     }
 167 }
 168 #endif
 169
 170 /*******************************************************************************
 171  * The parser itself.
 172  ******************************************************************************/
 173
 174 static cmdp_state state;
 175 #ifndef TEST_PARSER
 176 static Match current_match;
 177 #endif
 178 static struct CommandResult subcommand_output;
 179 static struct CommandResult command_output;
 180
 181 #include "GENERATED_call.h"
 182
 183
 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);
 193             char *buffer;
 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);
 201         }
 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;
 206         clear_stack();
 207         return;
 208     }
 209
 210     state = token->next_state;
 211     if (state == INITIAL) {
 212         clear_stack();
 213     }
 214 }
 215
 216 /* TODO: Return parsing errors via JSON. */
 217 struct CommandResult *parse_command(const char *input) {
 218     DLOG("new parser handling: %s\n", input);
 219     state = INITIAL;
 220     command_output.json_output = sstrdup("[");
 221     command_output.needs_tree_render = false;
 222
 223     const char *walk = input;
 224     const size_t len = strlen(input);
 225     int c;
 226     const cmdp_token *token;
 227     bool token_handled;
 228
 229     // TODO: make this testable
 230 #ifndef TEST_PARSER
 231     cmd_criteria_init(&current_match, &subcommand_output);
 232 #endif
 233
 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')
 240             walk++;
 241
 242         DLOG("remaining input = %s\n", walk);
 243
 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);
 249
 250             /* A literal. */
 251             if (token->name[0] == '\'') {
 252                 DLOG("literal\n");
 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;
 258                     next_state(token);
 259                     token_handled = true;
 260                     break;
 261                 }
 262                 continue;
 263             }
 264
 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). */
 270                 if (*walk == '"') {
 271                     beginning++;
 272                     walk++;
 273                     while (*walk != '\0' && (*walk != '"' || *(walk-1) == '\\'))
 274                         walk++;
 275                 } else {
 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
 280                          * end a command. */
 281                         while (*walk != ';' && *walk != ',' &&
 282                                *walk != '\0' && *walk != '\r' &&
 283                                *walk != '\n')
 284                             walk++;
 285                     } else {
 286                         /* For a word, the delimiters are white space (' ' or
 287                          * '\t'), closing square bracket (]), comma (,) and
 288                          * semicolon (;). */
 289                         while (*walk != ' ' && *walk != '\t' &&
 290                                *walk != ']' && *walk != ',' &&
 291                                *walk !=  ';' && *walk != '\r' &&
 292                                *walk != '\n' && *walk != '\0')
 293                             walk++;
 294                     }
 295                 }
 296                 if (walk != beginning) {
 297                     char *str = scalloc(walk-beginning + 1);
 298                     /* We copy manually to handle escaping of characters. */
 299                     int inpos, outpos;
 300                     for (inpos = 0, outpos = 0;
 301                          inpos < (walk-beginning);
 302                          inpos++, outpos++) {
 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] == '"')
 307                             inpos++;
 308                         str[outpos] = beginning[inpos];
 309                     }
 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
 314                      * double quote. */
 315                     if (*walk == '"')
 316                         walk++;
 317                     next_state(token);
 318                     token_handled = true;
 319                     break;
 320                 }
 321             }
 322
 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");
 327                     next_state(token);
 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
 332                      * every command. */
 333                     // TODO: make this testable
 334 #ifndef TEST_PARSER
 335                     if (*walk == '\0' || *walk == ';')
 336                         cmd_criteria_init(&current_match, &subcommand_output);
 337 #endif
 338                     walk++;
 339                     break;
 340                }
 341            }
 342         }
 343
 344         if (!token_handled) {
 345             /* Figure out how much memory we will need to fill in the names of
 346              * all tokens afterwards. */
 347             int tokenlen = 0;
 348             for (c = 0; c < ptr->n; c++)
 349                 tokenlen += strlen(ptr->array[c].name) + strlen("'', ");
 350
 351             /* Build up a decent error message. We include the problem, the
 352              * full input, and underline the position where the parser
 353              * currently is. */
 354             char *errormessage;
 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
 361                      * single quotes. */
 362                     *tokenwalk++ = '\'';
 363                     strcpy(tokenwalk, token->name + 1);
 364                     tokenwalk += strlen(token->name + 1);
 365                     *tokenwalk++ = '\'';
 366                 } else {
 367                     /* Any other token is copied to the error message enclosed
 368                      * with angle brackets. */
 369                     *tokenwalk++ = '<';
 370                     strcpy(tokenwalk, token->name);
 371                     tokenwalk += strlen(token->name);
 372                     *tokenwalk++ = '>';
 373                 }
 374                 if (c < (ptr->n - 1)) {
 375                     *tokenwalk++ = ',';
 376                     *tokenwalk++ = ' ';
 377                 }
 378             }
 379             *tokenwalk = '\0';
 380             sasprintf(&errormessage, "Expected one of these tokens: %s",
 381                       possible_tokens);
 382             free(possible_tokens);
 383
 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';
 390
 391             printf("%s\n", errormessage);
 392             printf("Your command: %s\n", input);
 393             printf("              %s\n", position);
 394
 395             free(position);
 396             free(errormessage);
 397             clear_stack();
 398             break;
 399         }
 400     }
 401
 402     char *buffer;
 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;
 409 }
 410
 411 /*******************************************************************************
 412  * Code for building the stand-alone binary test.commands_parser which is used
 413  * by t/187-commands-parser.t.
 414  ******************************************************************************/
 415
 416 #ifdef TEST_PARSER
 417
 418 /*
 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
 422  *
 423  */
 424 void debuglog(uint64_t lev, char *fmt, ...) {
 425     va_list args;
 426
 427     va_start(args, fmt);
 428     fprintf(stderr, "# ");
 429     vfprintf(stderr, fmt, args);
 430     va_end(args);
 431 }
 432
 433 int main(int argc, char *argv[]) {
 434     if (argc < 2) {
 435         fprintf(stderr, "Syntax: %s <command>\n", argv[0]);
 436         return 1;
 437     }
 438     parse_command(argv[1]);
 439 }
 440 #endif