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 // Macros to make the YAJL API a bit easier to use.
  36 #define y(x, ...) yajl_gen_ ## x (command_output.json_gen, ##__VA_ARGS__)
  37 #define ystr(str) yajl_gen_string(command_output.json_gen, (unsigned char*)str, strlen(str))
  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_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_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     char *str;
  75 };
  76
  77 /* 10 entries should be enough for everybody. */
  78 static struct stack_entry stack[10];
  79
  80 /*
  81  * Pushes a string (identified by 'identifier') on the stack. We simply use a
  82  * single array, since the number of entries we have to store is very small.
  83  *
  84  */
  85 static void push_string(const char *identifier, char *str) {
  86     for (int c = 0; c < 10; c++) {
  87         if (stack[c].identifier != NULL)
  88             continue;
  89         /* Found a free slot, let’s store it here. */
  90         stack[c].identifier = identifier;
  91         stack[c].str = str;
  92         return;
  93     }
  94
  95     /* When we arrive here, the stack is full. This should not happen and
  96      * means there’s either a bug in this parser or the specification
  97      * contains a command with more than 10 identified tokens. */
  98     fprintf(stderr, "BUG: commands_parser stack full. This means either a bug "
  99                     "in the code, or a new command which contains more than "
 100                     "10 identified tokens.\n");
 101     exit(1);
 102 }
 103
 104 // XXX: ideally, this would be const char. need to check if that works with all
 105 // called functions.
 106 static char *get_string(const char *identifier) {
 107     for (int c = 0; c < 10; c++) {
 108         if (stack[c].identifier == NULL)
 109             break;
 110         if (strcmp(identifier, stack[c].identifier) == 0)
 111             return stack[c].str;
 112     }
 113     return NULL;
 114 }
 115
 116 static void clear_stack(void) {
 117     for (int c = 0; c < 10; c++) {
 118         if (stack[c].str != NULL)
 119             free(stack[c].str);
 120         stack[c].identifier = NULL;
 121         stack[c].str = NULL;
 122     }
 123 }
 124
 125 // TODO: remove this if it turns out we don’t need it for testing.
 126 #if 0
 127 /*******************************************************************************
 128  * A dynamically growing linked list which holds the criteria for the current
 129  * command.
 130  ******************************************************************************/
 131
 132 typedef struct criterion {
 133     char *type;
 134     char *value;
 135
 136     TAILQ_ENTRY(criterion) criteria;
 137 } criterion;
 138
 139 static TAILQ_HEAD(criteria_head, criterion) criteria =
 140   TAILQ_HEAD_INITIALIZER(criteria);
 141
 142 /*
 143  * Stores the given type/value in the list of criteria.
 144  * Accepts a pointer as first argument, since it is 'call'ed by the parser.
 145  *
 146  */
 147 static void push_criterion(void *unused_criteria, const char *type,
 148                            const char *value) {
 149     struct criterion *criterion = malloc(sizeof(struct criterion));
 150     criterion->type = strdup(type);
 151     criterion->value = strdup(value);
 152     TAILQ_INSERT_TAIL(&criteria, criterion, criteria);
 153 }
 154
 155 /*
 156  * Clears the criteria linked list.
 157  * Accepts a pointer as first argument, since it is 'call'ed by the parser.
 158  *
 159  */
 160 static void clear_criteria(void *unused_criteria) {
 161     struct criterion *criterion;
 162     while (!TAILQ_EMPTY(&criteria)) {
 163         criterion = TAILQ_FIRST(&criteria);
 164         free(criterion->type);
 165         free(criterion->value);
 166         TAILQ_REMOVE(&criteria, criterion, criteria);
 167         free(criterion);
 168     }
 169 }
 170 #endif
 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 CommandResult subcommand_output;
 181 static struct CommandResult command_output;
 182
 183 #include "GENERATED_call.h"
 184
 185
 186 static void next_state(const cmdp_token *token) {
 187     if (token->next_state == __CALL) {
 188         subcommand_output.json_gen = command_output.json_gen;
 189         subcommand_output.needs_tree_render = false;
 190         GENERATED_call(token->extra.call_identifier, &subcommand_output);
 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 /* TODO: Return parsing errors via JSON. */
 206 struct CommandResult *parse_command(const char *input) {
 207     DLOG("COMMAND: *%s*\n", input);
 208     state = INITIAL;
 209
 210 /* A YAJL JSON generator used for formatting replies. */
 211 #if YAJL_MAJOR >= 2
 212     command_output.json_gen = yajl_gen_alloc(NULL);
 213 #else
 214     command_output.json_gen = yajl_gen_alloc(NULL, NULL);
 215 #endif
 216
 217     y(array_open);
 218     command_output.needs_tree_render = false;
 219
 220     const char *walk = input;
 221     const size_t len = strlen(input);
 222     int c;
 223     const cmdp_token *token;
 224     bool token_handled;
 225
 226     // TODO: make this testable
 227 #ifndef TEST_PARSER
 228     cmd_criteria_init(&current_match, &subcommand_output);
 229 #endif
 230
 231     /* The "<=" operator is intentional: We also handle the terminating 0-byte
 232      * explicitly by looking for an 'end' token. */
 233     while ((walk - input) <= len) {
 234         /* skip whitespace and newlines before every token */
 235         while ((*walk == ' ' || *walk == '\t' ||
 236                 *walk == '\r' || *walk == '\n') && *walk != '\0')
 237             walk++;
 238
 239         cmdp_token_ptr *ptr = &(tokens[state]);
 240         token_handled = false;
 241         for (c = 0; c < ptr->n; c++) {
 242             token = &(ptr->array[c]);
 243
 244             /* A literal. */
 245             if (token->name[0] == '\'') {
 246                 if (strncasecmp(walk, token->name + 1, strlen(token->name) - 1) == 0) {
 247                     if (token->identifier != NULL)
 248                         push_string(token->identifier, sstrdup(token->name + 1));
 249                     walk += strlen(token->name) - 1;
 250                     next_state(token);
 251                     token_handled = true;
 252                     break;
 253                 }
 254                 continue;
 255             }
 256
 257             if (strcmp(token->name, "string") == 0 ||
 258                 strcmp(token->name, "word") == 0) {
 259                 const char *beginning = walk;
 260                 /* Handle quoted strings (or words). */
 261                 if (*walk == '"') {
 262                     beginning++;
 263                     walk++;
 264                     while (*walk != '\0' && (*walk != '"' || *(walk-1) == '\\'))
 265                         walk++;
 266                 } else {
 267                     if (token->name[0] == 's') {
 268                         /* For a string (starting with 's'), the delimiters are
 269                          * comma (,) and semicolon (;) which introduce a new
 270                          * operation or command, respectively. Also, newlines
 271                          * end a command. */
 272                         while (*walk != ';' && *walk != ',' &&
 273                                *walk != '\0' && *walk != '\r' &&
 274                                *walk != '\n')
 275                             walk++;
 276                     } else {
 277                         /* For a word, the delimiters are white space (' ' or
 278                          * '\t'), closing square bracket (]), comma (,) and
 279                          * semicolon (;). */
 280                         while (*walk != ' ' && *walk != '\t' &&
 281                                *walk != ']' && *walk != ',' &&
 282                                *walk !=  ';' && *walk != '\r' &&
 283                                *walk != '\n' && *walk != '\0')
 284                             walk++;
 285                     }
 286                 }
 287                 if (walk != beginning) {
 288                     char *str = scalloc(walk-beginning + 1);
 289                     /* We copy manually to handle escaping of characters. */
 290                     int inpos, outpos;
 291                     for (inpos = 0, outpos = 0;
 292                          inpos < (walk-beginning);
 293                          inpos++, outpos++) {
 294                         /* We only handle escaped double quotes to not break
 295                          * backwards compatibility with people using \w in
 296                          * regular expressions etc. */
 297                         if (beginning[inpos] == '\\' && beginning[inpos+1] == '"')
 298                             inpos++;
 299                         str[outpos] = beginning[inpos];
 300                     }
 301                     if (token->identifier)
 302                         push_string(token->identifier, str);
 303                     /* If we are at the end of a quoted string, skip the ending
 304                      * double quote. */
 305                     if (*walk == '"')
 306                         walk++;
 307                     next_state(token);
 308                     token_handled = true;
 309                     break;
 310                 }
 311             }
 312
 313             if (strcmp(token->name, "end") == 0) {
 314                 if (*walk == '\0' || *walk == ',' || *walk == ';') {
 315                     next_state(token);
 316                     token_handled = true;
 317                     /* To make sure we start with an appropriate matching
 318                      * datastructure for commands which do *not* specify any
 319                      * criteria, we re-initialize the criteria system after
 320                      * every command. */
 321                     // TODO: make this testable
 322 #ifndef TEST_PARSER
 323                     if (*walk == '\0' || *walk == ';')
 324                         cmd_criteria_init(&current_match, &subcommand_output);
 325 #endif
 326                     walk++;
 327                     break;
 328                }
 329            }
 330         }
 331
 332         if (!token_handled) {
 333             /* Figure out how much memory we will need to fill in the names of
 334              * all tokens afterwards. */
 335             int tokenlen = 0;
 336             for (c = 0; c < ptr->n; c++)
 337                 tokenlen += strlen(ptr->array[c].name) + strlen("'', ");
 338
 339             /* Build up a decent error message. We include the problem, the
 340              * full input, and underline the position where the parser
 341              * currently is. */
 342             char *errormessage;
 343             char *possible_tokens = smalloc(tokenlen + 1);
 344             char *tokenwalk = possible_tokens;
 345             for (c = 0; c < ptr->n; c++) {
 346                 token = &(ptr->array[c]);
 347                 if (token->name[0] == '\'') {
 348                     /* A literal is copied to the error message enclosed with
 349                      * single quotes. */
 350                     *tokenwalk++ = '\'';
 351                     strcpy(tokenwalk, token->name + 1);
 352                     tokenwalk += strlen(token->name + 1);
 353                     *tokenwalk++ = '\'';
 354                 } else {
 355                     /* Any other token is copied to the error message enclosed
 356                      * with angle brackets. */
 357                     *tokenwalk++ = '<';
 358                     strcpy(tokenwalk, token->name);
 359                     tokenwalk += strlen(token->name);
 360                     *tokenwalk++ = '>';
 361                 }
 362                 if (c < (ptr->n - 1)) {
 363                     *tokenwalk++ = ',';
 364                     *tokenwalk++ = ' ';
 365                 }
 366             }
 367             *tokenwalk = '\0';
 368             sasprintf(&errormessage, "Expected one of these tokens: %s",
 369                       possible_tokens);
 370             free(possible_tokens);
 371
 372             /* Contains the same amount of characters as 'input' has, but with
 373              * the unparseable part highlighted using ^ characters. */
 374             char *position = smalloc(len + 1);
 375             for (const char *copywalk = input; *copywalk != '\0'; copywalk++)
 376                 position[(copywalk - input)] = (copywalk >= walk ? '^' : ' ');
 377             position[len] = '\0';
 378
 379             ELOG("%s\n", errormessage);
 380             ELOG("Your command: %s\n", input);
 381             ELOG("              %s\n", position);
 382
 383             /* Format this error message as a JSON reply. */
 384             y(map_open);
 385             ystr("success");
 386             y(bool, false);
 387             ystr("error");
 388             ystr(errormessage);
 389             ystr("input");
 390             ystr(input);
 391             ystr("errorposition");
 392             ystr(position);
 393             y(map_close);
 394
 395             free(position);
 396             free(errormessage);
 397             clear_stack();
 398             break;
 399         }
 400     }
 401
 402     y(array_close);
 403
 404     return &command_output;
 405 }
 406
 407 /*******************************************************************************
 408  * Code for building the stand-alone binary test.commands_parser which is used
 409  * by t/187-commands-parser.t.
 410  ******************************************************************************/
 411
 412 #ifdef TEST_PARSER
 413
 414 /*
 415  * Logs the given message to stdout while prefixing the current time to it,
 416  * but only if debug logging was activated.
 417  * This is to be called by DLOG() which includes filename/linenumber
 418  *
 419  */
 420 void debuglog(char *fmt, ...) {
 421     va_list args;
 422
 423     va_start(args, fmt);
 424     fprintf(stdout, "# ");
 425     vfprintf(stdout, fmt, args);
 426     va_end(args);
 427 }
 428
 429 void errorlog(char *fmt, ...) {
 430     va_list args;
 431
 432     va_start(args, fmt);
 433     vfprintf(stderr, fmt, args);
 434     va_end(args);
 435 }
 436
 437 int main(int argc, char *argv[]) {
 438     if (argc < 2) {
 439         fprintf(stderr, "Syntax: %s <command>\n", argv[0]);
 440         return 1;
 441     }
 442     parse_command(argv[1]);
 443 }
 444 #endif