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 #include "queue.h"
  35
  36 /*******************************************************************************
  37  * The data structures used for parsing. Essentially the current state and a
  38  * list of tokens for that state.
  39  *
  40  * The GENERATED_* files are generated by generate-commands-parser.pl with the
  41  * input parser-specs/commands.spec.
  42  ******************************************************************************/
  43
  44 #include "GENERATED_enums.h"
  45
  46 typedef struct token {
  47     char *name;
  48     char *identifier;
  49     /* This might be __CALL */
  50     cmdp_state next_state;
  51     union {
  52         uint16_t call_identifier;
  53     } extra;
  54 } cmdp_token;
  55
  56 typedef struct tokenptr {
  57     cmdp_token *array;
  58     int n;
  59 } cmdp_token_ptr;
  60
  61 #include "GENERATED_tokens.h"
  62
  63 /*******************************************************************************
  64  * The (small) stack where identified literals are stored during the parsing
  65  * of a single command (like $workspace).
  66  ******************************************************************************/
  67
  68 struct stack_entry {
  69     /* Just a pointer, not dynamically allocated. */
  70     const char *identifier;
  71     char *str;
  72 };
  73
  74 /* 10 entries should be enough for everybody. */
  75 static struct stack_entry stack[10];
  76
  77 /*
  78  * Pushes a string (identified by 'identifier') on the stack. We simply use a
  79  * single array, since the number of entries we have to store is very small.
  80  *
  81  */
  82 static void push_string(const char *identifier, char *str) {
  83     for (int c = 0; c < 10; c++) {
  84         if (stack[c].identifier != NULL)
  85             continue;
  86         /* Found a free slot, let’s store it here. */
  87         stack[c].identifier = identifier;
  88         stack[c].str = str;
  89         return;
  90     }
  91
  92     /* When we arrive here, the stack is full. This should not happen and
  93      * means there’s either a bug in this parser or the specification
  94      * contains a command with more than 10 identified tokens. */
  95     printf("argh! stack full\n");
  96     exit(1);
  97 }
  98
  99 // XXX: ideally, this would be const char. need to check if that works with all
 100 // called functions.
 101 static char *get_string(const char *identifier) {
 102     DLOG("Getting string %s from stack...\n", identifier);
 103     for (int c = 0; c < 10; c++) {
 104         if (stack[c].identifier == NULL)
 105             break;
 106         if (strcmp(identifier, stack[c].identifier) == 0)
 107             return stack[c].str;
 108     }
 109     return NULL;
 110 }
 111
 112 static void clear_stack() {
 113     DLOG("clearing stack.\n");
 114     for (int c = 0; c < 10; c++) {
 115         if (stack[c].str != NULL)
 116             free(stack[c].str);
 117         stack[c].identifier = NULL;
 118         stack[c].str = NULL;
 119     }
 120 }
 121
 122 // TODO: remove this if it turns out we don’t need it for testing.
 123 #if 0
 124 /*******************************************************************************
 125  * A dynamically growing linked list which holds the criteria for the current
 126  * command.
 127  ******************************************************************************/
 128
 129 typedef struct criterion {
 130     char *type;
 131     char *value;
 132
 133     TAILQ_ENTRY(criterion) criteria;
 134 } criterion;
 135
 136 static TAILQ_HEAD(criteria_head, criterion) criteria =
 137   TAILQ_HEAD_INITIALIZER(criteria);
 138
 139 /*
 140  * Stores the given type/value in the list of criteria.
 141  * Accepts a pointer as first argument, since it is 'call'ed by the parser.
 142  *
 143  */
 144 static void push_criterion(void *unused_criteria, const char *type,
 145                            const char *value) {
 146     struct criterion *criterion = malloc(sizeof(struct criterion));
 147     criterion->type = strdup(type);
 148     criterion->value = strdup(value);
 149     TAILQ_INSERT_TAIL(&criteria, criterion, criteria);
 150 }
 151
 152 /*
 153  * Clears the criteria linked list.
 154  * Accepts a pointer as first argument, since it is 'call'ed by the parser.
 155  *
 156  */
 157 static void clear_criteria(void *unused_criteria) {
 158     struct criterion *criterion;
 159     while (!TAILQ_EMPTY(&criteria)) {
 160         criterion = TAILQ_FIRST(&criteria);
 161         free(criterion->type);
 162         free(criterion->value);
 163         TAILQ_REMOVE(&criteria, criterion, criteria);
 164         free(criterion);
 165     }
 166 }
 167 #endif
 168
 169 /*******************************************************************************
 170  * The parser itself.
 171  ******************************************************************************/
 172
 173 static cmdp_state state;
 174 #ifndef TEST_PARSER
 175 static Match current_match;
 176 #endif
 177 static char *json_output;
 178
 179 #include "GENERATED_call.h"
 180
 181
 182 static void next_state(const cmdp_token *token) {
 183     if (token->next_state == __CALL) {
 184         DLOG("should call stuff, yay. call_id = %d\n",
 185                 token->extra.call_identifier);
 186         json_output = GENERATED_call(token->extra.call_identifier);
 187         clear_stack();
 188         return;
 189     }
 190
 191     state = token->next_state;
 192     if (state == INITIAL) {
 193         clear_stack();
 194     }
 195 }
 196
 197 /* TODO: Return parsing errors via JSON. */
 198 char *parse_command(const char *input) {
 199     DLOG("new parser handling: %s\n", input);
 200     state = INITIAL;
 201     json_output = NULL;
 202
 203     const char *walk = input;
 204     const size_t len = strlen(input);
 205     int c;
 206     const cmdp_token *token;
 207     bool token_handled;
 208
 209     // TODO: make this testable
 210 #ifndef TEST_PARSER
 211     cmd_criteria_init(&current_match);
 212 #endif
 213
 214     /* The "<=" operator is intentional: We also handle the terminating 0-byte
 215      * explicitly by looking for an 'end' token. */
 216     while ((walk - input) <= len) {
 217         /* skip whitespace and newlines before every token */
 218         while ((*walk == ' ' || *walk == '\t' ||
 219                 *walk == '\r' || *walk == '\n') && *walk != '\0')
 220             walk++;
 221
 222         DLOG("remaining input = %s\n", walk);
 223
 224         cmdp_token_ptr *ptr = &(tokens[state]);
 225         token_handled = false;
 226         for (c = 0; c < ptr->n; c++) {
 227             token = &(ptr->array[c]);
 228             DLOG("trying token %d = %s\n", c, token->name);
 229
 230             /* A literal. */
 231             if (token->name[0] == '\'') {
 232                 DLOG("literal\n");
 233                 if (strncasecmp(walk, token->name + 1, strlen(token->name) - 1) == 0) {
 234                     DLOG("found literal, moving to next state\n");
 235                     if (token->identifier != NULL)
 236                         push_string(token->identifier, strdup(token->name + 1));
 237                     walk += strlen(token->name) - 1;
 238                     next_state(token);
 239                     token_handled = true;
 240                     break;
 241                 }
 242                 continue;
 243             }
 244
 245             if (strcmp(token->name, "string") == 0 ||
 246                 strcmp(token->name, "word") == 0) {
 247                 DLOG("parsing this as a string\n");
 248                 const char *beginning = walk;
 249                 /* Handle quoted strings (or words). */
 250                 if (*walk == '"') {
 251                     beginning++;
 252                     walk++;
 253                     while (*walk != '"' || *(walk-1) == '\\')
 254                         walk++;
 255                 } else {
 256                     if (token->name[0] == 's') {
 257                         /* For a string (starting with 's'), the delimiters are
 258                          * comma (,) and semicolon (;) which introduce a new
 259                          * operation or command, respectively. Also, newlines
 260                          * end a command. */
 261                         while (*walk != ';' && *walk != ',' &&
 262                                *walk != '\0' && *walk != '\r' &&
 263                                *walk != '\n')
 264                             walk++;
 265                     } else {
 266                         /* For a word, the delimiters are white space (' ' or
 267                          * '\t'), closing square bracket (]), comma (,) and
 268                          * semicolon (;). */
 269                         while (*walk != ' ' && *walk != '\t' &&
 270                                *walk != ']' && *walk != ',' &&
 271                                *walk !=  ';' && *walk != '\r' &&
 272                                *walk != '\n' && *walk != '\0')
 273                             walk++;
 274                     }
 275                 }
 276                 if (walk != beginning) {
 277                     char *str = calloc(walk-beginning + 1, 1);
 278                     strncpy(str, beginning, walk-beginning);
 279                     if (token->identifier)
 280                         push_string(token->identifier, str);
 281                     DLOG("str is \"%s\"\n", str);
 282                     /* If we are at the end of a quoted string, skip the ending
 283                      * double quote. */
 284                     if (*walk == '"')
 285                         walk++;
 286                     next_state(token);
 287                     token_handled = true;
 288                     break;
 289                 }
 290             }
 291
 292             if (strcmp(token->name, "end") == 0) {
 293                 DLOG("checking for the end token.\n");
 294                 if (*walk == '\0' || *walk == ',' || *walk == ';') {
 295                     DLOG("yes, indeed. end\n");
 296                     next_state(token);
 297                     token_handled = true;
 298                     /* To make sure we start with an appropriate matching
 299                      * datastructure for commands which do *not* specify any
 300                      * criteria, we re-initialize the criteria system after
 301                      * every command. */
 302                     // TODO: make this testable
 303 #ifndef TEST_PARSER
 304                     if (*walk == '\0' || *walk == ';')
 305                         cmd_criteria_init(&current_match);
 306 #endif
 307                     walk++;
 308                     break;
 309                }
 310            }
 311         }
 312
 313         if (!token_handled) {
 314             /* Figure out how much memory we will need to fill in the names of
 315              * all tokens afterwards. */
 316             int tokenlen = 0;
 317             for (c = 0; c < ptr->n; c++)
 318                 tokenlen += strlen(ptr->array[c].name) + strlen("'', ");
 319
 320             /* Build up a decent error message. We include the problem, the
 321              * full input, and underline the position where the parser
 322              * currently is. */
 323             char *errormessage;
 324             char *possible_tokens = malloc(tokenlen + 1);
 325             char *tokenwalk = possible_tokens;
 326             for (c = 0; c < ptr->n; c++) {
 327                 token = &(ptr->array[c]);
 328                 if (token->name[0] == '\'') {
 329                     /* A literal is copied to the error message enclosed with
 330                      * single quotes. */
 331                     *tokenwalk++ = '\'';
 332                     strcpy(tokenwalk, token->name + 1);
 333                     tokenwalk += strlen(token->name + 1);
 334                     *tokenwalk++ = '\'';
 335                 } else {
 336                     /* Any other token is copied to the error message enclosed
 337                      * with angle brackets. */
 338                     *tokenwalk++ = '<';
 339                     strcpy(tokenwalk, token->name);
 340                     tokenwalk += strlen(token->name);
 341                     *tokenwalk++ = '>';
 342                 }
 343                 if (c < (ptr->n - 1)) {
 344                     *tokenwalk++ = ',';
 345                     *tokenwalk++ = ' ';
 346                 }
 347             }
 348             *tokenwalk = '\0';
 349             asprintf(&errormessage, "Expected one of these tokens: %s",
 350                      possible_tokens);
 351             free(possible_tokens);
 352
 353             /* Contains the same amount of characters as 'input' has, but with
 354              * the unparseable part highlighted using ^ characters. */
 355             char *position = malloc(len + 1);
 356             for (const char *copywalk = input; *copywalk != '\0'; copywalk++)
 357                 position[(copywalk - input)] = (copywalk >= walk ? '^' : ' ');
 358             position[len] = '\0';
 359
 360             printf("%s\n", errormessage);
 361             printf("Your command: %s\n", input);
 362             printf("              %s\n", position);
 363
 364             free(position);
 365             free(errormessage);
 366             break;
 367         }
 368     }
 369
 370     DLOG("json_output = %s\n", json_output);
 371     return json_output;
 372 }
 373
 374 /*******************************************************************************
 375  * Code for building the stand-alone binary test.commands_parser which is used
 376  * by t/187-commands-parser.t.
 377  ******************************************************************************/
 378
 379 #ifdef TEST_PARSER
 380
 381 /*
 382  * Logs the given message to stdout while prefixing the current time to it,
 383  * but only if the corresponding debug loglevel was activated.
 384  * This is to be called by DLOG() which includes filename/linenumber
 385  *
 386  */
 387 void debuglog(uint64_t lev, char *fmt, ...) {
 388     va_list args;
 389
 390     va_start(args, fmt);
 391     fprintf(stderr, "# ");
 392     vfprintf(stderr, fmt, args);
 393     va_end(args);
 394 }
 395
 396 int main(int argc, char *argv[]) {
 397     if (argc < 2) {
 398         fprintf(stderr, "Syntax: %s <command>\n", argv[0]);
 399         return 1;
 400     }
 401     parse_command(argv[1]);
 402 }
 403 #endif