src/xkbcomp/rules.c

   1 /************************************************************
   2  * Copyright (c) 1996 by Silicon Graphics Computer Systems, Inc.
   3  *
   4  * Permission to use, copy, modify, and distribute this
   5  * software and its documentation for any purpose and without
   6  * fee is hereby granted, provided that the above copyright
   7  * notice appear in all copies and that both that copyright
   8  * notice and this permission notice appear in supporting
   9  * documentation, and that the name of Silicon Graphics not be
  10  * used in advertising or publicity pertaining to distribution
  11  * of the software without specific prior written permission.
  12  * Silicon Graphics makes no representation about the suitability
  13  * of this software for any purpose. It is provided "as is"
  14  * without any express or implied warranty.
  15  *
  16  * SILICON GRAPHICS DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS
  17  * SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
  18  * AND FITNESS FOR A PARTICULAR PURPOSE. IN NO EVENT SHALL SILICON
  19  * GRAPHICS BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
  20  * DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
  21  * DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
  22  * OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION  WITH
  23  * THE USE OR PERFORMANCE OF THIS SOFTWARE.
  24  *
  25  ********************************************************/
  26
  27 /*
  28  * Copyright © 2012 Ran Benita <ran234@gmail.com>
  29  *
  30  * Permission is hereby granted, free of charge, to any person obtaining a
  31  * copy of this software and associated documentation files (the "Software"),
  32  * to deal in the Software without restriction, including without limitation
  33  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
  34  * and/or sell copies of the Software, and to permit persons to whom the
  35  * Software is furnished to do so, subject to the following conditions:
  36  *
  37  * The above copyright notice and this permission notice (including the next
  38  * paragraph) shall be included in all copies or substantial portions of the
  39  * Software.
  40  *
  41  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  42  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  43  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  44  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  45  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  46  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  47  * DEALINGS IN THE SOFTWARE.
  48  */
  49
  50 #include "xkbcomp-priv.h"
  51 #include "rules.h"
  52 #include "include.h"
  53 #include "scanner-utils.h"
  54
  55 /* Scanner / Lexer */
  56
  57 /* Values returned with some tokens, like yylval. */
  58 union lvalue {
  59     struct sval string;
  60 };
  61
  62 enum rules_token {
  63     TOK_END_OF_FILE = 0,
  64     TOK_END_OF_LINE,
  65     TOK_IDENTIFIER,
  66     TOK_GROUP_NAME,
  67     TOK_BANG,
  68     TOK_EQUALS,
  69     TOK_STAR,
  70     TOK_ERROR
  71 };
  72
  73 /* C99 is stupid. Just use the 1 variant when there are no args. */
  74 #define scanner_error1(scanner, msg) \
  75     log_warn((scanner)->ctx, "rules/%s:%u:%u: %s\n", \
  76              (scanner)->file_name, \
  77              (scanner)->token_line, (scanner)->token_column, msg)
  78 #define scanner_error(scanner, fmt, ...) \
  79     log_warn((scanner)->ctx, "rules/%s:%u:%u: " fmt "\n", \
  80              (scanner)->file_name, \
  81              (scanner)->token_line, (scanner)->token_column, __VA_ARGS__)
  82
  83 static inline bool
  84 is_ident(char ch)
  85 {
  86     return is_graph(ch) && ch != '\\';
  87 }
  88
  89 static enum rules_token
  90 lex(struct scanner *s, union lvalue *val)
  91 {
  92 skip_more_whitespace_and_comments:
  93     /* Skip spaces. */
  94     while (chr(s, ' ') || chr(s, '\t'));
  95
  96     /* Skip comments. */
  97     if (lit(s, "//")) {
  98         while (!eof(s) && !eol(s)) next(s);
  99     }
 100
 101     /* New line. */
 102     if (eol(s)) {
 103         while (eol(s)) next(s);
 104         return TOK_END_OF_LINE;
 105     }
 106
 107     /* Escaped line continuation. */
 108     if (chr(s, '\\')) {
 109         if (!eol(s)) {
 110             scanner_error1(s, "illegal new line escape; must appear at end of line");
 111             return TOK_ERROR;
 112         }
 113         next(s);
 114         goto skip_more_whitespace_and_comments;
 115     }
 116
 117     /* See if we're done. */
 118     if (eof(s)) return TOK_END_OF_FILE;
 119
 120     /* New token. */
 121     s->token_line = s->line;
 122     s->token_column = s->column;
 123
 124     /* Operators and punctuation. */
 125     if (chr(s, '!')) return TOK_BANG;
 126     if (chr(s, '=')) return TOK_EQUALS;
 127     if (chr(s, '*')) return TOK_STAR;
 128
 129     /* Group name. */
 130     if (chr(s, '$')) {
 131         val->string.start = s->s + s->pos;
 132         val->string.len = 0;
 133         while (is_ident(peek(s))) {
 134             next(s);
 135             val->string.len++;
 136         }
 137         if (val->string.len == 0) {
 138             scanner_error1(s, "unexpected character after \'$\'; expected name");
 139             return TOK_ERROR;
 140         }
 141         return TOK_GROUP_NAME;
 142     }
 143
 144     /* Identifier. */
 145     if (is_ident(peek(s))) {
 146         val->string.start = s->s + s->pos;
 147         val->string.len = 0;
 148         while (is_ident(peek(s))) {
 149             next(s);
 150             val->string.len++;
 151         }
 152         return TOK_IDENTIFIER;
 153     }
 154
 155     scanner_error1(s, "unrecognized token");
 156     return TOK_ERROR;
 157 }
 158
 159 /***====================================================================***/
 160
 161 enum rules_mlvo {
 162     MLVO_MODEL,
 163     MLVO_LAYOUT,
 164     MLVO_VARIANT,
 165     MLVO_OPTION,
 166     _MLVO_NUM_ENTRIES
 167 };
 168
 169 #define SVAL_LIT(literal) { literal, sizeof(literal) - 1 }
 170
 171 static const struct sval rules_mlvo_svals[_MLVO_NUM_ENTRIES] = {
 172     [MLVO_MODEL] = SVAL_LIT("model"),
 173     [MLVO_LAYOUT] = SVAL_LIT("layout"),
 174     [MLVO_VARIANT] = SVAL_LIT("variant"),
 175     [MLVO_OPTION] = SVAL_LIT("option"),
 176 };
 177
 178 enum rules_kccgst {
 179     KCCGST_KEYCODES,
 180     KCCGST_TYPES,
 181     KCCGST_COMPAT,
 182     KCCGST_SYMBOLS,
 183     KCCGST_GEOMETRY,
 184     _KCCGST_NUM_ENTRIES
 185 };
 186
 187 static const struct sval rules_kccgst_svals[_KCCGST_NUM_ENTRIES] = {
 188     [KCCGST_KEYCODES] = SVAL_LIT("keycodes"),
 189     [KCCGST_TYPES] = SVAL_LIT("types"),
 190     [KCCGST_COMPAT] = SVAL_LIT("compat"),
 191     [KCCGST_SYMBOLS] = SVAL_LIT("symbols"),
 192     [KCCGST_GEOMETRY] = SVAL_LIT("geometry"),
 193 };
 194
 195 /*
 196  * A broken-down version of xkb_rule_names (without the rules,
 197  * obviously).
 198  */
 199 struct rule_names {
 200     struct sval model;
 201     darray_sval layouts;
 202     darray_sval variants;
 203     darray_sval options;
 204 };
 205
 206 struct group {
 207     struct sval name;
 208     darray_sval elements;
 209 };
 210
 211 struct mapping {
 212     int mlvo_at_pos[_MLVO_NUM_ENTRIES];
 213     unsigned int num_mlvo;
 214     unsigned int defined_mlvo_mask;
 215     xkb_layout_index_t layout_idx, variant_idx;
 216     int kccgst_at_pos[_KCCGST_NUM_ENTRIES];
 217     unsigned int num_kccgst;
 218     unsigned int defined_kccgst_mask;
 219     bool skip;
 220 };
 221
 222 enum mlvo_match_type {
 223     MLVO_MATCH_NORMAL = 0,
 224     MLVO_MATCH_WILDCARD,
 225     MLVO_MATCH_GROUP,
 226 };
 227
 228 struct rule {
 229     struct sval mlvo_value_at_pos[_MLVO_NUM_ENTRIES];
 230     enum mlvo_match_type match_type_at_pos[_MLVO_NUM_ENTRIES];
 231     unsigned int num_mlvo_values;
 232     struct sval kccgst_value_at_pos[_KCCGST_NUM_ENTRIES];
 233     unsigned int num_kccgst_values;
 234     bool skip;
 235 };
 236
 237 /*
 238  * This is the main object used to match a given RMLVO against a rules
 239  * file and aggragate the results in a KcCGST. It goes through a simple
 240  * matching state machine, with tokens as transitions (see
 241  * matcher_match()).
 242  */
 243 struct matcher {
 244     struct xkb_context *ctx;
 245     /* Input.*/
 246     struct rule_names rmlvo;
 247     union lvalue val;
 248     struct scanner scanner;
 249     darray(struct group) groups;
 250     /* Current mapping. */
 251     struct mapping mapping;
 252     /* Current rule. */
 253     struct rule rule;
 254     /* Output. */
 255     darray_char kccgst[_KCCGST_NUM_ENTRIES];
 256 };
 257
 258 static struct sval
 259 strip_spaces(struct sval v)
 260 {
 261     while (v.len > 0 && is_space(v.start[0])) { v.len--; v.start++; }
 262     while (v.len > 0 && is_space(v.start[v.len - 1])) v.len--;
 263     return v;
 264 }
 265
 266 static darray_sval
 267 split_comma_separated_string(const char *s)
 268 {
 269     darray_sval arr = darray_new();
 270
 271     /*
 272      * Make sure the array returned by this function always includes at
 273      * least one value, e.g. "" -> { "" } and "," -> { "", "" }.
 274      */
 275
 276     if (!s) {
 277         struct sval val = { NULL, 0 };
 278         darray_append(arr, val);
 279         return arr;
 280     }
 281
 282     while (true) {
 283         struct sval val = { s, 0 };
 284         while (*s != '\0' && *s != ',') { s++; val.len++; }
 285         darray_append(arr, strip_spaces(val));
 286         if (*s == '\0') break;
 287         if (*s == ',') s++;
 288     }
 289
 290     return arr;
 291 }
 292
 293 static struct matcher *
 294 matcher_new(struct xkb_context *ctx,
 295             const struct xkb_rule_names *rmlvo)
 296 {
 297     struct matcher *m = calloc(1, sizeof(*m));
 298     if (!m)
 299         return NULL;
 300
 301     m->ctx = ctx;
 302     m->rmlvo.model.start = rmlvo->model;
 303     m->rmlvo.model.len = strlen_safe(rmlvo->model);
 304     m->rmlvo.layouts = split_comma_separated_string(rmlvo->layout);
 305     m->rmlvo.variants = split_comma_separated_string(rmlvo->variant);
 306     m->rmlvo.options = split_comma_separated_string(rmlvo->options);
 307
 308     return m;
 309 }
 310
 311 static void
 312 matcher_free(struct matcher *m)
 313 {
 314     struct group *group;
 315     if (!m)
 316         return;
 317     darray_free(m->rmlvo.layouts);
 318     darray_free(m->rmlvo.variants);
 319     darray_free(m->rmlvo.options);
 320     darray_foreach(group, m->groups)
 321         darray_free(group->elements);
 322     darray_free(m->groups);
 323     free(m);
 324 }
 325
 326 #define matcher_error1(matcher, msg) \
 327     scanner_error1(&(matcher)->scanner, msg)
 328 #define matcher_error(matcher, fmt, ...) \
 329     scanner_error(&(matcher)->scanner, fmt, __VA_ARGS__)
 330
 331 static void
 332 matcher_group_start_new(struct matcher *m, struct sval name)
 333 {
 334     struct group group = { .name = name, .elements = darray_new() };
 335     darray_append(m->groups, group);
 336 }
 337
 338 static void
 339 matcher_group_add_element(struct matcher *m, struct sval element)
 340 {
 341     darray_append(darray_item(m->groups, darray_size(m->groups) - 1).elements,
 342                   element);
 343 }
 344
 345 static void
 346 matcher_mapping_start_new(struct matcher *m)
 347 {
 348     for (unsigned i = 0; i < _MLVO_NUM_ENTRIES; i++)
 349         m->mapping.mlvo_at_pos[i] = -1;
 350     for (unsigned i = 0; i < _KCCGST_NUM_ENTRIES; i++)
 351         m->mapping.kccgst_at_pos[i] = -1;
 352     m->mapping.layout_idx = m->mapping.variant_idx = XKB_LAYOUT_INVALID;
 353     m->mapping.num_mlvo = m->mapping.num_kccgst = 0;
 354     m->mapping.defined_mlvo_mask = 0;
 355     m->mapping.defined_kccgst_mask = 0;
 356     m->mapping.skip = false;
 357 }
 358
 359 static int
 360 extract_layout_index(const char *s, size_t max_len, xkb_layout_index_t *out)
 361 {
 362     /* This function is pretty stupid, but works for now. */
 363     *out = XKB_LAYOUT_INVALID;
 364     if (max_len < 3)
 365         return -1;
 366     if (s[0] != '[' || !is_digit(s[1]) || s[2] != ']')
 367         return -1;
 368     if (s[1] - '0' < 1 || s[1] - '0' > XKB_MAX_GROUPS)
 369         return -1;
 370     /* To zero-based index. */
 371     *out = s[1] - '0' - 1;
 372     return 3;
 373 }
 374
 375 static void
 376 matcher_mapping_set_mlvo(struct matcher *m, struct sval ident)
 377 {
 378     enum rules_mlvo mlvo;
 379     struct sval mlvo_sval;
 380
 381     for (mlvo = 0; mlvo < _MLVO_NUM_ENTRIES; mlvo++) {
 382         mlvo_sval = rules_mlvo_svals[mlvo];
 383
 384         if (svaleq_prefix(mlvo_sval, ident))
 385             break;
 386     }
 387
 388     /* Not found. */
 389     if (mlvo >= _MLVO_NUM_ENTRIES) {
 390         matcher_error(m,
 391                       "invalid mapping: %.*s is not a valid value here; "
 392                       "ignoring rule set",
 393                       ident.len, ident.start);
 394         m->mapping.skip = true;
 395         return;
 396     }
 397
 398     if (m->mapping.defined_mlvo_mask & (1u << mlvo)) {
 399         matcher_error(m,
 400                       "invalid mapping: %.*s appears twice on the same line; "
 401                       "ignoring rule set",
 402                       mlvo_sval.len, mlvo_sval.start);
 403         m->mapping.skip = true;
 404         return;
 405     }
 406
 407     /* If there are leftovers still, it must be an index. */
 408     if (mlvo_sval.len < ident.len) {
 409         xkb_layout_index_t idx;
 410         int consumed = extract_layout_index(ident.start + mlvo_sval.len,
 411                                             ident.len - mlvo_sval.len, &idx);
 412         if ((int) (ident.len - mlvo_sval.len) != consumed) {
 413             matcher_error(m,
 414                           "invalid mapping:\" %.*s\" may only be followed by a valid group index; "
 415                           "ignoring rule set",
 416                           mlvo_sval.len, mlvo_sval.start);
 417             m->mapping.skip = true;
 418             return;
 419         }
 420
 421         if (mlvo == MLVO_LAYOUT) {
 422             m->mapping.layout_idx = idx;
 423         }
 424         else if (mlvo == MLVO_VARIANT) {
 425             m->mapping.variant_idx = idx;
 426         }
 427         else {
 428             matcher_error(m,
 429                           "invalid mapping: \"%.*s\" cannot be followed by a group index; "
 430                           "ignoring rule set",
 431                           mlvo_sval.len, mlvo_sval.start);
 432             m->mapping.skip = true;
 433             return;
 434         }
 435     }
 436
 437     m->mapping.mlvo_at_pos[m->mapping.num_mlvo] = mlvo;
 438     m->mapping.defined_mlvo_mask |= 1u << mlvo;
 439     m->mapping.num_mlvo++;
 440 }
 441
 442 static void
 443 matcher_mapping_set_kccgst(struct matcher *m, struct sval ident)
 444 {
 445     enum rules_kccgst kccgst;
 446     struct sval kccgst_sval;
 447
 448     for (kccgst = 0; kccgst < _KCCGST_NUM_ENTRIES; kccgst++) {
 449         kccgst_sval = rules_kccgst_svals[kccgst];
 450
 451         if (svaleq(rules_kccgst_svals[kccgst], ident))
 452             break;
 453     }
 454
 455     /* Not found. */
 456     if (kccgst >= _KCCGST_NUM_ENTRIES) {
 457         matcher_error(m,
 458                       "invalid mapping: %.*s is not a valid value here; "
 459                       "ignoring rule set",
 460                       ident.len, ident.start);
 461         m->mapping.skip = true;
 462         return;
 463     }
 464
 465     if (m->mapping.defined_kccgst_mask & (1u << kccgst)) {
 466         matcher_error(m,
 467                       "invalid mapping: %.*s appears twice on the same line; "
 468                       "ignoring rule set",
 469                       kccgst_sval.len, kccgst_sval.start);
 470         m->mapping.skip = true;
 471         return;
 472     }
 473
 474     m->mapping.kccgst_at_pos[m->mapping.num_kccgst] = kccgst;
 475     m->mapping.defined_kccgst_mask |= 1u << kccgst;
 476     m->mapping.num_kccgst++;
 477 }
 478
 479 static void
 480 matcher_mapping_verify(struct matcher *m)
 481 {
 482     if (m->mapping.num_mlvo == 0) {
 483         matcher_error1(m,
 484                        "invalid mapping: must have at least one value on the left hand side; "
 485                        "ignoring rule set");
 486         goto skip;
 487     }
 488
 489     if (m->mapping.num_kccgst == 0) {
 490         matcher_error1(m,
 491                        "invalid mapping: must have at least one value on the right hand side; "
 492                        "ignoring rule set");
 493         goto skip;
 494     }
 495
 496     /*
 497      * This following is very stupid, but this is how it works.
 498      * See the "Notes" section in the overview above.
 499      */
 500
 501     if (m->mapping.defined_mlvo_mask & (1u << MLVO_LAYOUT)) {
 502         if (m->mapping.layout_idx == XKB_LAYOUT_INVALID) {
 503             if (darray_size(m->rmlvo.layouts) > 1)
 504                 goto skip;
 505         }
 506         else {
 507             if (darray_size(m->rmlvo.layouts) == 1 ||
 508                 m->mapping.layout_idx >= darray_size(m->rmlvo.layouts))
 509                 goto skip;
 510         }
 511     }
 512
 513     if (m->mapping.defined_mlvo_mask & (1u << MLVO_VARIANT)) {
 514         if (m->mapping.variant_idx == XKB_LAYOUT_INVALID) {
 515             if (darray_size(m->rmlvo.variants) > 1)
 516                 goto skip;
 517         }
 518         else {
 519             if (darray_size(m->rmlvo.variants) == 1 ||
 520                 m->mapping.variant_idx >= darray_size(m->rmlvo.variants))
 521                 goto skip;
 522         }
 523     }
 524
 525     return;
 526
 527 skip:
 528     m->mapping.skip = true;
 529 }
 530
 531 static void
 532 matcher_rule_start_new(struct matcher *m)
 533 {
 534     memset(&m->rule, 0, sizeof(m->rule));
 535     m->rule.skip = m->mapping.skip;
 536 }
 537
 538 static void
 539 matcher_rule_set_mlvo_common(struct matcher *m, struct sval ident,
 540                              enum mlvo_match_type match_type)
 541 {
 542     if (m->rule.num_mlvo_values + 1 > m->mapping.num_mlvo) {
 543         matcher_error1(m,
 544                        "invalid rule: has more values than the mapping line; "
 545                        "ignoring rule");
 546         m->rule.skip = true;
 547         return;
 548     }
 549     m->rule.match_type_at_pos[m->rule.num_mlvo_values] = match_type;
 550     m->rule.mlvo_value_at_pos[m->rule.num_mlvo_values] = ident;
 551     m->rule.num_mlvo_values++;
 552 }
 553
 554 static void
 555 matcher_rule_set_mlvo_wildcard(struct matcher *m)
 556 {
 557     struct sval dummy = { NULL, 0 };
 558     matcher_rule_set_mlvo_common(m, dummy, MLVO_MATCH_WILDCARD);
 559 }
 560
 561 static void
 562 matcher_rule_set_mlvo_group(struct matcher *m, struct sval ident)
 563 {
 564     matcher_rule_set_mlvo_common(m, ident, MLVO_MATCH_GROUP);
 565 }
 566
 567 static void
 568 matcher_rule_set_mlvo(struct matcher *m, struct sval ident)
 569 {
 570     matcher_rule_set_mlvo_common(m, ident, MLVO_MATCH_NORMAL);
 571 }
 572
 573 static void
 574 matcher_rule_set_kccgst(struct matcher *m, struct sval ident)
 575 {
 576     if (m->rule.num_kccgst_values + 1 > m->mapping.num_kccgst) {
 577         matcher_error1(m,
 578                        "invalid rule: has more values than the mapping line; "
 579                        "ignoring rule");
 580         m->rule.skip = true;
 581         return;
 582     }
 583     m->rule.kccgst_value_at_pos[m->rule.num_kccgst_values] = ident;
 584     m->rule.num_kccgst_values++;
 585 }
 586
 587 static bool
 588 match_group(struct matcher *m, struct sval group_name, struct sval to)
 589 {
 590     struct group *group;
 591     struct sval *element;
 592     bool found = false;
 593
 594     darray_foreach(group, m->groups) {
 595         if (svaleq(group->name, group_name)) {
 596             found = true;
 597             break;
 598         }
 599     }
 600
 601     if (!found) {
 602         /*
 603          * rules/evdev intentionally uses some undeclared group names
 604          * in rules (e.g. commented group definitions which may be
 605          * uncommented if needed). So we continue silently.
 606          */
 607         return false;
 608     }
 609
 610     darray_foreach(element, group->elements)
 611         if (svaleq(to, *element))
 612             return true;
 613
 614     return false;
 615 }
 616
 617 static bool
 618 match_value(struct matcher *m, struct sval val, struct sval to,
 619           enum mlvo_match_type match_type)
 620 {
 621     if (match_type == MLVO_MATCH_WILDCARD)
 622         return true;
 623     if (match_type == MLVO_MATCH_GROUP)
 624         return match_group(m, val, to);
 625     return svaleq(val, to);
 626 }
 627
 628 /*
 629  * This function performs %-expansion on @value (see overview above),
 630  * and appends the result to @to.
 631  */
 632 static bool
 633 append_expanded_kccgst_value(struct matcher *m, darray_char *to,
 634                              struct sval value)
 635 {
 636     const unsigned original_size = darray_size(*to);
 637     const char *s = value.start;
 638
 639     /*
 640      * Appending  bar to  foo ->  foo (not an error if this happens)
 641      * Appending +bar to  foo ->  foo+bar
 642      * Appending  bar to +foo ->  bar+foo
 643      * Appending +bar to +foo -> +foo+bar
 644      */
 645     if (!darray_empty(*to) && s[0] != '+' && s[0] != '|') {
 646         if (darray_item(*to, 0) == '+' || darray_item(*to, 0) == '|')
 647             darray_prepends_nullterminate(*to, value.start, value.len);
 648         return true;
 649     }
 650
 651     /*
 652      * Some ugly hand-lexing here, but going through the scanner is more
 653      * trouble than it's worth, and the format is ugly on its own merit.
 654      */
 655     for (unsigned i = 0; i < value.len; ) {
 656         enum rules_mlvo mlv;
 657         xkb_layout_index_t idx;
 658         char pfx, sfx;
 659         struct sval expanded;
 660
 661         /* Check if that's a start of an expansion. */
 662         if (s[i] != '%') {
 663             /* Just a normal character. */
 664             darray_appends_nullterminate(*to, &s[i++], 1);
 665             continue;
 666         }
 667         if (++i >= value.len) goto error;
 668
 669         pfx = sfx = 0;
 670
 671         /* Check for prefix. */
 672         if (s[i] == '(' || s[i] == '+' || s[i] == '|' ||
 673             s[i] == '_' || s[i] == '-') {
 674             pfx = s[i];
 675             if (s[i] == '(') sfx = ')';
 676             if (++i >= value.len) goto error;
 677         }
 678
 679         /* Mandatory model/layout/variant specifier. */
 680         switch (s[i++]) {
 681         case 'm': mlv = MLVO_MODEL; break;
 682         case 'l': mlv = MLVO_LAYOUT; break;
 683         case 'v': mlv = MLVO_VARIANT; break;
 684         default: goto error;
 685         }
 686
 687         /* Check for index. */
 688         idx = XKB_LAYOUT_INVALID;
 689         if (i < value.len && s[i] == '[') {
 690             int consumed;
 691
 692             if (mlv != MLVO_LAYOUT && mlv != MLVO_VARIANT) {
 693                 matcher_error1(m,
 694                                 "invalid index in %%-expansion; "
 695                                 "may only index layout or variant");
 696                 goto error;
 697             }
 698
 699             consumed = extract_layout_index(s + i, value.len - i, &idx);
 700             if (consumed == -1) goto error;
 701             i += consumed;
 702         }
 703
 704         /* Check for suffix, if there supposed to be one. */
 705         if (sfx != 0) {
 706             if (i >= value.len) goto error;
 707             if (s[i++] != sfx) goto error;
 708         }
 709
 710         /* Get the expanded value. */
 711         expanded.len = 0;
 712
 713         if (mlv == MLVO_LAYOUT) {
 714             if (idx != XKB_LAYOUT_INVALID &&
 715                 idx < darray_size(m->rmlvo.layouts) &&
 716                 darray_size(m->rmlvo.layouts) > 1)
 717                 expanded = darray_item(m->rmlvo.layouts, idx);
 718             else if (idx == XKB_LAYOUT_INVALID &&
 719                      darray_size(m->rmlvo.layouts) == 1)
 720                 expanded = darray_item(m->rmlvo.layouts, 0);
 721         }
 722         else if (mlv == MLVO_VARIANT) {
 723             if (idx != XKB_LAYOUT_INVALID &&
 724                 idx < darray_size(m->rmlvo.variants) &&
 725                 darray_size(m->rmlvo.variants) > 1)
 726                 expanded = darray_item(m->rmlvo.variants, idx);
 727             else if (idx == XKB_LAYOUT_INVALID &&
 728                      darray_size(m->rmlvo.variants) == 1)
 729                 expanded = darray_item(m->rmlvo.variants, 0);
 730         }
 731         else if (mlv == MLVO_MODEL) {
 732             expanded = m->rmlvo.model;
 733         }
 734
 735         /* If we didn't get one, skip silently. */
 736         if (expanded.len <= 0)
 737             continue;
 738
 739         if (pfx != 0)
 740             darray_appends_nullterminate(*to, &pfx, 1);
 741         darray_appends_nullterminate(*to, expanded.start, expanded.len);
 742         if (sfx != 0)
 743             darray_appends_nullterminate(*to, &sfx, 1);
 744     }
 745
 746     return true;
 747
 748 error:
 749     matcher_error1(m, "invalid %%-expansion in value; not used");
 750     darray_resize(*to, original_size);
 751     return false;
 752 }
 753
 754 static void
 755 matcher_rule_verify(struct matcher *m)
 756 {
 757     if (m->rule.num_mlvo_values != m->mapping.num_mlvo ||
 758         m->rule.num_kccgst_values != m->mapping.num_kccgst) {
 759         matcher_error1(m,
 760                        "invalid rule: must have same number of values as mapping line;"
 761                        "ignoring rule");
 762         m->rule.skip = true;
 763     }
 764 }
 765
 766 static void
 767 matcher_rule_apply_if_matches(struct matcher *m)
 768 {
 769     for (unsigned i = 0; i < m->mapping.num_mlvo; i++) {
 770         enum rules_mlvo mlvo = m->mapping.mlvo_at_pos[i];
 771         struct sval value = m->rule.mlvo_value_at_pos[i];
 772         enum mlvo_match_type match_type = m->rule.match_type_at_pos[i];
 773         bool matched = false;
 774
 775         if (mlvo == MLVO_MODEL) {
 776             matched = match_value(m, value, m->rmlvo.model, match_type);
 777         }
 778         else if (mlvo == MLVO_LAYOUT) {
 779             xkb_layout_index_t idx = m->mapping.layout_idx;
 780             idx = (idx == XKB_LAYOUT_INVALID ? 0 : idx);
 781             matched = match_value(m, value,
 782                                   darray_item(m->rmlvo.layouts, idx),
 783                                   match_type);
 784         }
 785         else if (mlvo == MLVO_VARIANT) {
 786             xkb_layout_index_t idx = m->mapping.layout_idx;
 787             idx = (idx == XKB_LAYOUT_INVALID ? 0 : idx);
 788             matched = match_value(m, value,
 789                                   darray_item(m->rmlvo.variants, idx),
 790                                   match_type);
 791         }
 792         else if (mlvo == MLVO_OPTION) {
 793             struct sval *option;
 794             darray_foreach(option, m->rmlvo.options) {
 795                 matched = match_value(m, value, *option, match_type);
 796                 if (matched)
 797                     break;
 798             }
 799         }
 800
 801         if (!matched)
 802             return;
 803     }
 804
 805     for (unsigned i = 0; i < m->mapping.num_kccgst; i++) {
 806         enum rules_kccgst kccgst = m->mapping.kccgst_at_pos[i];
 807         struct sval value = m->rule.kccgst_value_at_pos[i];
 808         append_expanded_kccgst_value(m, &m->kccgst[kccgst], value);
 809     }
 810
 811     /*
 812      * If a rule matches in a rule set, the rest of the set should be
 813      * skipped. However, rule sets matching against options may contain
 814      * several legitimate rules, so they are processed entirely.
 815      */
 816     if (!(m->mapping.defined_mlvo_mask & (1 << MLVO_OPTION)))
 817         m->mapping.skip = true;
 818 }
 819
 820 static enum rules_token
 821 gettok(struct matcher *m)
 822 {
 823     return lex(&m->scanner, &m->val);
 824 }
 825
 826 static bool
 827 matcher_match(struct matcher *m, const char *string, size_t len,
 828               const char *file_name, struct xkb_component_names *out)
 829 {
 830     enum rules_token tok;
 831
 832     if (!m)
 833         return false;
 834
 835     scanner_init(&m->scanner, m->ctx, string, len, file_name);
 836
 837 initial:
 838     switch (tok = gettok(m)) {
 839     case TOK_BANG:
 840         goto bang;
 841     case TOK_END_OF_LINE:
 842         goto initial;
 843     case TOK_END_OF_FILE:
 844         goto finish;
 845     default:
 846         goto unexpected;
 847     }
 848
 849 bang:
 850     switch (tok = gettok(m)) {
 851     case TOK_GROUP_NAME:
 852         matcher_group_start_new(m, m->val.string);
 853         goto group_name;
 854     case TOK_IDENTIFIER:
 855         matcher_mapping_start_new(m);
 856         matcher_mapping_set_mlvo(m, m->val.string);
 857         goto mapping_mlvo;
 858     default:
 859         goto unexpected;
 860     }
 861
 862 group_name:
 863     switch (tok = gettok(m)) {
 864     case TOK_EQUALS:
 865         goto group_element;
 866     default:
 867         goto unexpected;
 868     }
 869
 870 group_element:
 871     switch (tok = gettok(m)) {
 872     case TOK_IDENTIFIER:
 873         matcher_group_add_element(m, m->val.string);
 874         goto group_element;
 875     case TOK_END_OF_LINE:
 876         goto initial;
 877     default:
 878         goto unexpected;
 879     }
 880
 881 mapping_mlvo:
 882     switch (tok = gettok(m)) {
 883     case TOK_IDENTIFIER:
 884         if (!m->mapping.skip)
 885             matcher_mapping_set_mlvo(m, m->val.string);
 886         goto mapping_mlvo;
 887     case TOK_EQUALS:
 888         goto mapping_kccgst;
 889     default:
 890         goto unexpected;
 891     }
 892
 893 mapping_kccgst:
 894     switch (tok = gettok(m)) {
 895     case TOK_IDENTIFIER:
 896         if (!m->mapping.skip)
 897             matcher_mapping_set_kccgst(m, m->val.string);
 898         goto mapping_kccgst;
 899     case TOK_END_OF_LINE:
 900         if (!m->mapping.skip)
 901             matcher_mapping_verify(m);
 902         goto rule_mlvo_first;
 903     default:
 904         goto unexpected;
 905     }
 906
 907 rule_mlvo_first:
 908     switch (tok = gettok(m)) {
 909     case TOK_BANG:
 910         goto bang;
 911     case TOK_END_OF_LINE:
 912         goto rule_mlvo_first;
 913     case TOK_END_OF_FILE:
 914         goto finish;
 915     default:
 916         matcher_rule_start_new(m);
 917         goto rule_mlvo_no_tok;
 918     }
 919
 920 rule_mlvo:
 921     tok = gettok(m);
 922 rule_mlvo_no_tok:
 923     switch (tok) {
 924     case TOK_IDENTIFIER:
 925         if (!m->rule.skip)
 926             matcher_rule_set_mlvo(m, m->val.string);
 927         goto rule_mlvo;
 928     case TOK_STAR:
 929         if (!m->rule.skip)
 930             matcher_rule_set_mlvo_wildcard(m);
 931         goto rule_mlvo;
 932     case TOK_GROUP_NAME:
 933         if (!m->rule.skip)
 934             matcher_rule_set_mlvo_group(m, m->val.string);
 935         goto rule_mlvo;
 936     case TOK_EQUALS:
 937         goto rule_kccgst;
 938     default:
 939         goto unexpected;
 940     }
 941
 942 rule_kccgst:
 943     switch (tok = gettok(m)) {
 944     case TOK_IDENTIFIER:
 945         if (!m->rule.skip)
 946             matcher_rule_set_kccgst(m, m->val.string);
 947         goto rule_kccgst;
 948     case TOK_END_OF_LINE:
 949         if (!m->rule.skip)
 950             matcher_rule_verify(m);
 951         if (!m->rule.skip)
 952             matcher_rule_apply_if_matches(m);
 953         goto rule_mlvo_first;
 954     default:
 955         goto unexpected;
 956     }
 957
 958 unexpected:
 959     switch (tok) {
 960     case TOK_ERROR:
 961         goto error;
 962     default:
 963         goto state_error;
 964     }
 965
 966 finish:
 967     if (darray_empty(m->kccgst[KCCGST_KEYCODES]) ||
 968         darray_empty(m->kccgst[KCCGST_TYPES]) ||
 969         darray_empty(m->kccgst[KCCGST_COMPAT]) ||
 970         /* darray_empty(m->kccgst[KCCGST_GEOMETRY]) || */
 971         darray_empty(m->kccgst[KCCGST_SYMBOLS]))
 972         goto error;
 973
 974     out->keycodes = darray_mem(m->kccgst[KCCGST_KEYCODES], 0);
 975     out->types = darray_mem(m->kccgst[KCCGST_TYPES], 0);
 976     out->compat = darray_mem(m->kccgst[KCCGST_COMPAT], 0);
 977     /* out->geometry = darray_mem(m->kccgst[KCCGST_GEOMETRY], 0); */
 978     darray_free(m->kccgst[KCCGST_GEOMETRY]);
 979     out->symbols = darray_mem(m->kccgst[KCCGST_SYMBOLS], 0);
 980
 981     return true;
 982
 983 state_error:
 984     matcher_error1(m, "unexpected token");
 985 error:
 986     return false;
 987 }
 988
 989 bool
 990 xkb_components_from_rules(struct xkb_context *ctx,
 991                           const struct xkb_rule_names *rmlvo,
 992                           struct xkb_component_names *out)
 993 {
 994     bool ret = false;
 995     FILE *file;
 996     char *path;
 997     const char *string;
 998     size_t size;
 999     struct matcher *matcher;
1000
1001     file = FindFileInXkbPath(ctx, rmlvo->rules, FILE_TYPE_RULES, &path);
1002     if (!file)
1003         goto err_out;
1004
1005     ret = map_file(file, &string, &size);
1006     if (!ret) {
1007         log_err(ctx, "Couldn't read rules file: %s\n", strerror(errno));
1008         goto err_file;
1009     }
1010
1011     matcher = matcher_new(ctx, rmlvo);
1012     ret = matcher_match(matcher, string, size, rmlvo->rules, out);
1013     if (!ret)
1014         log_err(ctx, "No components returned from XKB rules \"%s\"\n", path);
1015     matcher_free(matcher);
1016
1017     unmap_file(string, size);
1018 err_file:
1019     free(path);
1020     fclose(file);
1021 err_out:
1022     return ret;
1023 }