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