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

   1 #line 2 "commands_parser.c"
   2 /*
   3  * vim:ts=4:sw=4:expandtab
   4  *
   5  * i3 - an improved dynamic tiling window manager
   6  * © 2009-2012 Michael Stapelberg and contributors (see also: LICENSE)
   7  *
   8  * commands_parser.c: hand-written parser to parse commands (commands are what
   9  * you bind on keys and what you can send to i3 using the IPC interface, like
  10  * 'move left' or 'workspace 4').
  11  *
  12  * We use a hand-written parser instead of lex/yacc because our commands are
  13  * easy for humans, not for computers. Thus, it’s quite hard to specify a
  14  * context-free grammar for the commands. A PEG grammar would be easier, but
  15  * there’s downsides to every PEG parser generator I have come accross so far.
  16  *
  17  * This parser is basically a state machine which looks for literals or strings
  18  * and can push either on a stack. After identifying a literal or string, it
  19  * will either transition to the current state, to a different state, or call a
  20  * function (like cmd_move()).
  21  *
  22  * Special care has been taken that error messages are useful and the code is
  23  * well testable (when compiled with -DTEST_PARSER it will output to stdout
  24  * instead of actually calling any function).
  25  *
  26  */
  27 #include <stdio.h>
  28 #include <stdlib.h>
  29 #include <string.h>
  30 #include <unistd.h>
  31 #include <stdbool.h>
  32 #include <stdint.h>
  33
  34 #include "all.h"
  35
  36 // Macros to make the YAJL API a bit easier to use.
  37 #define y(x, ...) yajl_gen_ ## x (command_output.json_gen, ##__VA_ARGS__)
  38 #define ystr(str) yajl_gen_string(command_output.json_gen, (unsigned char*)str, strlen(str))
  39
  40 /*******************************************************************************
  41  * The data structures used for parsing. Essentially the current state and a
  42  * list of tokens for that state.
  43  *
  44  * The GENERATED_* files are generated by generate-commands-parser.pl with the
  45  * input parser-specs/commands.spec.
  46  ******************************************************************************/
  47
  48 #include "GENERATED_enums.h"
  49
  50 typedef struct token {
  51     char *name;
  52     char *identifier;
  53     /* This might be __CALL */
  54     cmdp_state next_state;
  55     union {
  56         uint16_t call_identifier;
  57     } extra;
  58 } cmdp_token;
  59
  60 typedef struct tokenptr {
  61     cmdp_token *array;
  62     int n;
  63 } cmdp_token_ptr;
  64
  65 #include "GENERATED_tokens.h"
  66
  67 /*******************************************************************************
  68  * The (small) stack where identified literals are stored during the parsing
  69  * of a single command (like $workspace).
  70  ******************************************************************************/
  71
  72 struct stack_entry {
  73     /* Just a pointer, not dynamically allocated. */
  74     const char *identifier;
  75     char *str;
  76 };
  77
  78 /* 10 entries should be enough for everybody. */
  79 static struct stack_entry stack[10];
  80
  81 /*
  82  * Pushes a string (identified by 'identifier') on the stack. We simply use a
  83  * single array, since the number of entries we have to store is very small.
  84  *
  85  */
  86 static void push_string(const char *identifier, char *str) {
  87     for (int c = 0; c < 10; c++) {
  88         if (stack[c].identifier != NULL)
  89             continue;
  90         /* Found a free slot, let’s store it here. */
  91         stack[c].identifier = identifier;
  92         stack[c].str = str;
  93         return;
  94     }
  95
  96     /* When we arrive here, the stack is full. This should not happen and
  97      * means there’s either a bug in this parser or the specification
  98      * contains a command with more than 10 identified tokens. */
  99     fprintf(stderr, "BUG: commands_parser stack full. This means either a bug "
 100                     "in the code, or a new command which contains more than "
 101                     "10 identified tokens.\n");
 102     exit(1);
 103 }
 104
 105 // XXX: ideally, this would be const char. need to check if that works with all
 106 // called functions.
 107 static char *get_string(const char *identifier) {
 108     for (int c = 0; c < 10; c++) {
 109         if (stack[c].identifier == NULL)
 110             break;
 111         if (strcmp(identifier, stack[c].identifier) == 0)
 112             return stack[c].str;
 113     }
 114     return NULL;
 115 }
 116
 117 static void clear_stack(void) {
 118     for (int c = 0; c < 10; c++) {
 119         if (stack[c].str != NULL)
 120             free(stack[c].str);
 121         stack[c].identifier = NULL;
 122         stack[c].str = NULL;
 123     }
 124 }
 125
 126 // TODO: remove this if it turns out we don’t need it for testing.
 127 #if 0
 128 /*******************************************************************************
 129  * A dynamically growing linked list which holds the criteria for the current
 130  * command.
 131  ******************************************************************************/
 132
 133 typedef struct criterion {
 134     char *type;
 135     char *value;
 136
 137     TAILQ_ENTRY(criterion) criteria;
 138 } criterion;
 139
 140 static TAILQ_HEAD(criteria_head, criterion) criteria =
 141   TAILQ_HEAD_INITIALIZER(criteria);
 142
 143 /*
 144  * Stores the given type/value in the list of criteria.
 145  * Accepts a pointer as first argument, since it is 'call'ed by the parser.
 146  *
 147  */
 148 static void push_criterion(void *unused_criteria, const char *type,
 149                            const char *value) {
 150     struct criterion *criterion = malloc(sizeof(struct criterion));
 151     criterion->type = strdup(type);
 152     criterion->value = strdup(value);
 153     TAILQ_INSERT_TAIL(&criteria, criterion, criteria);
 154 }
 155
 156 /*
 157  * Clears the criteria linked list.
 158  * Accepts a pointer as first argument, since it is 'call'ed by the parser.
 159  *
 160  */
 161 static void clear_criteria(void *unused_criteria) {
 162     struct criterion *criterion;
 163     while (!TAILQ_EMPTY(&criteria)) {
 164         criterion = TAILQ_FIRST(&criteria);
 165         free(criterion->type);
 166         free(criterion->value);
 167         TAILQ_REMOVE(&criteria, criterion, criteria);
 168         free(criterion);
 169     }
 170 }
 171 #endif
 172
 173 /*******************************************************************************
 174  * The parser itself.
 175  ******************************************************************************/
 176
 177 static cmdp_state state;
 178 #ifndef TEST_PARSER
 179 static Match current_match;
 180 #endif
 181 static struct CommandResult subcommand_output;
 182 static struct CommandResult command_output;
 183
 184 #include "GENERATED_call.h"
 185
 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         /* If any subcommand requires a tree_render(), we need to make the
 193          * whole parser result request a tree_render(). */
 194         if (subcommand_output.needs_tree_render)
 195             command_output.needs_tree_render = true;
 196         clear_stack();
 197         return;
 198     }
 199
 200     state = token->next_state;
 201     if (state == INITIAL) {
 202         clear_stack();
 203     }
 204 }
 205
 206 /* TODO: Return parsing errors via JSON. */
 207 struct CommandResult *parse_command(const char *input) {
 208     DLOG("COMMAND: *%s*\n", input);
 209     state = INITIAL;
 210
 211 /* A YAJL JSON generator used for formatting replies. */
 212 #if YAJL_MAJOR >= 2
 213     command_output.json_gen = yajl_gen_alloc(NULL);
 214 #else
 215     command_output.json_gen = yajl_gen_alloc(NULL, NULL);
 216 #endif
 217
 218     y(array_open);
 219     command_output.needs_tree_render = false;
 220
 221     const char *walk = input;
 222     const size_t len = strlen(input);
 223     int c;
 224     const cmdp_token *token;
 225     bool token_handled;
 226
 227     // TODO: make this testable
 228 #ifndef TEST_PARSER
 229     cmd_criteria_init(&current_match, &subcommand_output);
 230 #endif
 231
 232     /* The "<=" operator is intentional: We also handle the terminating 0-byte
 233      * explicitly by looking for an 'end' token. */
 234     while ((walk - input) <= len) {
 235         /* skip whitespace and newlines before every token */
 236         while ((*walk == ' ' || *walk == '\t' ||
 237                 *walk == '\r' || *walk == '\n') && *walk != '\0')
 238             walk++;
 239
 240         cmdp_token_ptr *ptr = &(tokens[state]);
 241         token_handled = false;
 242         for (c = 0; c < ptr->n; c++) {
 243             token = &(ptr->array[c]);
 244
 245             /* A literal. */
 246             if (token->name[0] == '\'') {
 247                 if (strncasecmp(walk, token->name + 1, strlen(token->name) - 1) == 0) {
 248                     if (token->identifier != NULL)
 249                         push_string(token->identifier, sstrdup(token->name + 1));
 250                     walk += strlen(token->name) - 1;
 251                     next_state(token);
 252                     token_handled = true;
 253                     break;
 254                 }
 255                 continue;
 256             }
 257
 258             if (strcmp(token->name, "string") == 0 ||
 259                 strcmp(token->name, "word") == 0) {
 260                 const char *beginning = walk;
 261                 /* Handle quoted strings (or words). */
 262                 if (*walk == '"') {
 263                     beginning++;
 264                     walk++;
 265                     while (*walk != '\0' && (*walk != '"' || *(walk-1) == '\\'))
 266                         walk++;
 267                 } else {
 268                     if (token->name[0] == 's') {
 269                         /* For a string (starting with 's'), the delimiters are
 270                          * comma (,) and semicolon (;) which introduce a new
 271                          * operation or command, respectively. Also, newlines
 272                          * end a command. */
 273                         while (*walk != ';' && *walk != ',' &&
 274                                *walk != '\0' && *walk != '\r' &&
 275                                *walk != '\n')
 276                             walk++;
 277                     } else {
 278                         /* For a word, the delimiters are white space (' ' or
 279                          * '\t'), closing square bracket (]), comma (,) and
 280                          * semicolon (;). */
 281                         while (*walk != ' ' && *walk != '\t' &&
 282                                *walk != ']' && *walk != ',' &&
 283                                *walk !=  ';' && *walk != '\r' &&
 284                                *walk != '\n' && *walk != '\0')
 285                             walk++;
 286                     }
 287                 }
 288                 if (walk != beginning) {
 289                     char *str = scalloc(walk-beginning + 1);
 290                     /* We copy manually to handle escaping of characters. */
 291                     int inpos, outpos;
 292                     for (inpos = 0, outpos = 0;
 293                          inpos < (walk-beginning);
 294                          inpos++, outpos++) {
 295                         /* We only handle escaped double quotes to not break
 296                          * backwards compatibility with people using \w in
 297                          * regular expressions etc. */
 298                         if (beginning[inpos] == '\\' && beginning[inpos+1] == '"')
 299                             inpos++;
 300                         str[outpos] = beginning[inpos];
 301                     }
 302                     if (token->identifier)
 303                         push_string(token->identifier, str);
 304                     /* If we are at the end of a quoted string, skip the ending
 305                      * double quote. */
 306                     if (*walk == '"')
 307                         walk++;
 308                     next_state(token);
 309                     token_handled = true;
 310                     break;
 311                 }
 312             }
 313
 314             if (strcmp(token->name, "end") == 0) {
 315                 if (*walk == '\0' || *walk == ',' || *walk == ';') {
 316                     next_state(token);
 317                     token_handled = true;
 318                     /* To make sure we start with an appropriate matching
 319                      * datastructure for commands which do *not* specify any
 320                      * criteria, we re-initialize the criteria system after
 321                      * every command. */
 322                     // TODO: make this testable
 323 #ifndef TEST_PARSER
 324                     if (*walk == '\0' || *walk == ';')
 325                         cmd_criteria_init(&current_match, &subcommand_output);
 326 #endif
 327                     walk++;
 328                     break;
 329                }
 330            }
 331         }
 332
 333         if (!token_handled) {
 334             /* Figure out how much memory we will need to fill in the names of
 335              * all tokens afterwards. */
 336             int tokenlen = 0;
 337             for (c = 0; c < ptr->n; c++)
 338                 tokenlen += strlen(ptr->array[c].name) + strlen("'', ");
 339
 340             /* Build up a decent error message. We include the problem, the
 341              * full input, and underline the position where the parser
 342              * currently is. */
 343             char *errormessage;
 344             char *possible_tokens = smalloc(tokenlen + 1);
 345             char *tokenwalk = possible_tokens;
 346             for (c = 0; c < ptr->n; c++) {
 347                 token = &(ptr->array[c]);
 348                 if (token->name[0] == '\'') {
 349                     /* A literal is copied to the error message enclosed with
 350                      * single quotes. */
 351                     *tokenwalk++ = '\'';
 352                     strcpy(tokenwalk, token->name + 1);
 353                     tokenwalk += strlen(token->name + 1);
 354                     *tokenwalk++ = '\'';
 355                 } else {
 356                     /* Any other token is copied to the error message enclosed
 357                      * with angle brackets. */
 358                     *tokenwalk++ = '<';
 359                     strcpy(tokenwalk, token->name);
 360                     tokenwalk += strlen(token->name);
 361                     *tokenwalk++ = '>';
 362                 }
 363                 if (c < (ptr->n - 1)) {
 364                     *tokenwalk++ = ',';
 365                     *tokenwalk++ = ' ';
 366                 }
 367             }
 368             *tokenwalk = '\0';
 369             sasprintf(&errormessage, "Expected one of these tokens: %s",
 370                       possible_tokens);
 371             free(possible_tokens);
 372
 373             /* Contains the same amount of characters as 'input' has, but with
 374              * the unparseable part highlighted using ^ characters. */
 375             char *position = smalloc(len + 1);
 376             for (const char *copywalk = input; *copywalk != '\0'; copywalk++)
 377                 position[(copywalk - input)] = (copywalk >= walk ? '^' : ' ');
 378             position[len] = '\0';
 379
 380             ELOG("%s\n", errormessage);
 381             ELOG("Your command: %s\n", input);
 382             ELOG("              %s\n", position);
 383
 384             /* Format this error message as a JSON reply. */
 385             y(map_open);
 386             ystr("success");
 387             y(bool, false);
 388             ystr("error");
 389             ystr(errormessage);
 390             ystr("input");
 391             ystr(input);
 392             ystr("errorposition");
 393             ystr(position);
 394             y(map_close);
 395
 396             free(position);
 397             free(errormessage);
 398             clear_stack();
 399             break;
 400         }
 401     }
 402
 403     y(array_close);
 404
 405     return &command_output;
 406 }
 407
 408 /*******************************************************************************
 409  * Code for building the stand-alone binary test.commands_parser which is used
 410  * by t/187-commands-parser.t.
 411  ******************************************************************************/
 412
 413 #ifdef TEST_PARSER
 414
 415 /*
 416  * Logs the given message to stdout while prefixing the current time to it,
 417  * but only if debug logging was activated.
 418  * This is to be called by DLOG() which includes filename/linenumber
 419  *
 420  */
 421 void debuglog(char *fmt, ...) {
 422     va_list args;
 423
 424     va_start(args, fmt);
 425     fprintf(stdout, "# ");
 426     vfprintf(stdout, fmt, args);
 427     va_end(args);
 428 }
 429
 430 void errorlog(char *fmt, ...) {
 431     va_list args;
 432
 433     va_start(args, fmt);
 434     vfprintf(stderr, fmt, args);
 435     va_end(args);
 436 }
 437
 438 int main(int argc, char *argv[]) {
 439     if (argc < 2) {
 440         fprintf(stderr, "Syntax: %s <command>\n", argv[0]);
 441         return 1;
 442     }
 443     parse_command(argv[1]);
 444 }
 445 #endif