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