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 <ctype.h>
  51 #include <fcntl.h>
  52 #include <unistd.h>
  53 #include <sys/mman.h>
  54 #include <sys/stat.h>
  55 #include <sys/types.h>
  56
  57 #include "xkbcomp-priv.h"
  58 #include "rules.h"
  59 #include "include.h"
  60
  61 /*
  62  * The rules file
  63  * ==============
  64  * The purpose of this file is to map between configuration values that
  65  * are easy for a user to specify and understand, and the configuration
  66  * values xkbcomp uses and understands.
  67  * xkbcomp uses the xkb_component_names struct, which maps directly to
  68  * include statements of the appropriate sections, called for short
  69  * KcCGST (see keycodes.c, types.c, compat.c, symbols.c; geometry.c was
  70  * removed). These are not really intuitive or straight-forward for
  71  * the uninitiated.
  72  * Instead, the user passes in a xkb_rule_names struct, which consists
  73  * of the name of a rules file (in Linux this is usually "evdev"), a
  74  * keyboard model (e.g. "pc105"), a set of layouts (which will end up
  75  * in different groups, e.g. "us,fr"), variants (used to alter/augment
  76  * the respective layout, e.g. "intl,dvorak"), and a set of options
  77  * (used to tweak some general behavior of the keyboard, e.g.
  78  * "ctrl:nocaps,compose:menu" to make the Caps Lock key act like Ctrl
  79  * and the Menu key like Compose). We call these RMLVO.
  80  *
  81  * Format of the file
  82  * ------------------
  83  * The file consists of rule sets, each consisting of rules (one per
  84  * line), which match the MLVO values on the left hand side, and, if
  85  * the values match to the values the user passed in, results in the
  86  * values on the right hand side being added to the resulting KcCGST.
  87  * Since some values are related and repeated often, it is possible
  88  * to group them together and refer to them by a group name in the
  89  * rules.
  90  * Along with matching values by simple string equality, and for
  91  * membership in a group defined previously, rules may also contain
  92  * "wildcard" values - "*" - which always match. These usually appear
  93  * near the end.
  94  *
  95  * Grammer
  96  * -------
  97  * (It might be helpful to look at a file like rules/evdev along with
  98  * this grammer. Comments, whitespace, etc. are not shown.)
  99  *
 100  * File         ::= { "!" (Group | RuleSet) }
 101  *
 102  * Group        ::= GroupName "=" { GroupElement } "\n"
 103  * GroupName    ::= "$"<ident>
 104  * GroupElement ::= <ident>
 105  *
 106  * RuleSet      ::= Mapping { Rule }
 107  *
 108  * Mapping      ::= { Mlvo } "=" { Kccgst } "\n"
 109  * Mlvo         ::= "model" | "option" | ("layout" | "variant") [ Index ]
 110  * Index        ::= "[" 1..XKB_NUM_GROUPS "]"
 111  * Kccgst       ::= "keycodes" | "symbols" | "types" | "compat" | "geometry"
 112  *
 113  * Rule         ::= { MlvoValue } "=" { KccgstValue } "\n"
 114  * MlvoValue    ::= "*" | GroupName | <ident>
 115  * KccgstValue  ::= <ident>
 116  *
 117  * Notes:
 118  * - The order of values in a Rule must be the same as the Mapping it
 119  *   follows. The mapping line determines the meaning of the values in
 120  *   the rules which follow in the RuleSet.
 121  * - If a Rule is matched, %-expansion is performed on the KccgstValue,
 122  *   as follows:
 123  *   %m, %l, %v:
 124  *      The model, layout or variant, if only one was given (e.g.
 125  *      %l for "us,il" is invalid).
 126  *   %l[1], %v[1]:
 127  *      Layout or variant for the specified group Index, if more than
 128  *      one was given (e.g. %l[1] for "us" is invalid).
 129  *   %+m, %+l, %+v, %+l[1], %+v[1]
 130  *      As above, but prefixed with '+'. Similarly, '|', '-', '_' may be
 131  *      used instead of '+'.
 132  *   %(m), %(l), %(l[1]), %(v), %(v[1]):
 133  *      As above, but prefixed by '(' and suffixed by ')'.
 134  *   In case the expansion is invalid, as described above, it is
 135  *   skipped (the rest of the string is still processed); this includes
 136  *   the prefix and suffix (that's why you shouldn't use e.g. "(%v[1])").
 137  */
 138
 139 /* Scanner / Lexer */
 140
 141 /* Point to some substring in the file; used to avoid copying. */
 142 struct sval {
 143     const char *start;
 144     unsigned int len;
 145 };
 146 typedef darray(struct sval) darray_sval;
 147
 148 static inline bool
 149 svaleq(struct sval s1, struct sval s2)
 150 {
 151     return s1.len == s2.len && strncmp(s1.start, s2.start, s1.len) == 0;
 152 }
 153
 154 static inline bool
 155 svaleq_prefix(struct sval s1, struct sval s2)
 156 {
 157     return s1.len <= s2.len && strncmp(s1.start, s2.start, s1.len) == 0;
 158 }
 159
 160 /* Values returned with some tokens, like yylval. */
 161 union lvalue {
 162     struct sval string;
 163 };
 164
 165 /*
 166  * Holds the location in the file of the last processed token,
 167  * like yylloc.
 168  */
 169 struct location {
 170     int line, column;
 171 };
 172
 173 struct scanner {
 174     const char *s;
 175     size_t pos;
 176     size_t len;
 177     int line, column;
 178     const char *file_name;
 179     struct xkb_context *ctx;
 180 };
 181
 182 enum rules_token {
 183     TOK_END_OF_FILE = 0,
 184     TOK_END_OF_LINE,
 185     TOK_IDENTIFIER,
 186     TOK_GROUP_NAME,
 187     TOK_BANG,
 188     TOK_EQUALS,
 189     TOK_STAR,
 190     TOK_ERROR
 191 };
 192
 193 static void
 194 scanner_init(struct scanner *s, struct xkb_context *ctx,
 195              const char *string, size_t len, const char *file_name)
 196 {
 197     s->s = string;
 198     s->len = len;
 199     s->pos = 0;
 200     s->line = s->column = 1;
 201     s->file_name = file_name;
 202     s->ctx = ctx;
 203 }
 204
 205 /* C99 is stupid. Just use the 1 variant when there are no args. */
 206 #define scanner_error1(scanner, loc, msg) \
 207     log_warn(scanner->ctx, "rules/%s:%d:%d: " msg "\n", \
 208              scanner->file_name, loc->line, loc->column)
 209 #define scanner_error(scanner, loc, fmt, ...) \
 210     log_warn(scanner->ctx, "rules/%s:%d:%d: " fmt "\n", \
 211              scanner->file_name, loc->line, loc->column, __VA_ARGS__)
 212
 213 static char
 214 peek(struct scanner *s)
 215 {
 216     return s->s[s->pos];
 217 }
 218
 219 static bool
 220 eof(struct scanner *s)
 221 {
 222     return s->s[s->pos] == '\0' || s->pos >= s->len;
 223 }
 224
 225 static bool
 226 eol(struct scanner *s)
 227 {
 228     return s->s[s->pos] == '\n';
 229 }
 230
 231 /*
 232  * Use the check_nl variant when the current char might be a new line;
 233  * just an optimization.
 234  */
 235 static char
 236 next(struct scanner *s)
 237 {
 238     s->column++;
 239     return s->s[s->pos++];
 240 }
 241
 242 static char
 243 next_check_nl(struct scanner *s)
 244 {
 245     if (eol(s)) {
 246         s->line++;
 247         s->column = 1;
 248     }
 249     else {
 250         s->column++;
 251     }
 252     return s->s[s->pos++];
 253 }
 254
 255 static bool
 256 chr(struct scanner *s, char ch)
 257 {
 258     if (peek(s) != ch)
 259         return false;
 260     s->pos++; s->column++;
 261     return true;
 262 }
 263
 264 static bool
 265 str(struct scanner *s, const char *string, size_t len)
 266 {
 267     if (strncasecmp(s->s + s->pos, string, len) != 0)
 268         return false;
 269     s->pos += len; s->column += len;
 270     return true;
 271 }
 272
 273 #define lit(s, literal) str(s, literal, sizeof(literal) - 1)
 274
 275 static enum rules_token
 276 lex(struct scanner *s, union lvalue *val, struct location *loc)
 277 {
 278 skip_more_whitespace_and_comments:
 279     /* Skip spaces. */
 280     while (chr(s, ' ') || chr(s, '\t'));
 281
 282     /* Skip comments. */
 283     if (lit(s, "//")) {
 284         while (!eof(s) && !eol(s)) next(s);
 285     }
 286
 287     /* New line. */
 288     if (eol(s)) {
 289         while (eol(s)) next_check_nl(s);
 290         return TOK_END_OF_LINE;
 291     }
 292
 293     /* Escaped line continuation. */
 294     if (chr(s, '\\')) {
 295         if (!eol(s)) {
 296             scanner_error1(s, loc,
 297                            "illegal new line escape; must appear at end of line");
 298             return TOK_ERROR;
 299         }
 300         next_check_nl(s);
 301         goto skip_more_whitespace_and_comments;
 302     }
 303
 304     /* See if we're done. */
 305     if (eof(s)) return TOK_END_OF_FILE;
 306
 307     /* New token. */
 308     loc->line = s->line;
 309     loc->column = s->column;
 310
 311     /* Operators and punctuation. */
 312     if (chr(s, '!')) return TOK_BANG;
 313     if (chr(s, '=')) return TOK_EQUALS;
 314     if (chr(s, '*')) return TOK_STAR;
 315
 316     /* Group name. */
 317     if (chr(s, '$')) {
 318         val->string.start = s->s + s->pos;
 319         val->string.len = 0;
 320         while (isgraph(peek(s))) {
 321             next(s);
 322             val->string.len++;
 323         }
 324         if (val->string.len == 0) {
 325             scanner_error1(s, loc,
 326                            "unexpected character after \'$\'; expected name");
 327             return TOK_ERROR;
 328         }
 329         return TOK_GROUP_NAME;
 330     }
 331
 332     /* Identifier. */
 333     if (isgraph(peek(s))) {
 334         val->string.start = s->s + s->pos;
 335         val->string.len = 0;
 336         while (isgraph(peek(s))) {
 337             next(s);
 338             val->string.len++;
 339         }
 340         return TOK_IDENTIFIER;
 341     }
 342
 343     scanner_error1(s, loc, "unrecognized token");
 344     return TOK_ERROR;
 345 }
 346
 347 /***====================================================================***/
 348
 349 enum rules_mlvo {
 350     MLVO_MODEL,
 351     MLVO_LAYOUT,
 352     MLVO_VARIANT,
 353     MLVO_OPTION,
 354     _MLVO_NUM_ENTRIES
 355 };
 356
 357 #define SVAL_LIT(literal) { literal, sizeof(literal) - 1 }
 358
 359 static const struct sval rules_mlvo_svals[_MLVO_NUM_ENTRIES] = {
 360     [MLVO_MODEL] = SVAL_LIT("model"),
 361     [MLVO_LAYOUT] = SVAL_LIT("layout"),
 362     [MLVO_VARIANT] = SVAL_LIT("variant"),
 363     [MLVO_OPTION] = SVAL_LIT("option"),
 364 };
 365
 366 enum rules_kccgst {
 367     KCCGST_KEYCODES,
 368     KCCGST_TYPES,
 369     KCCGST_COMPAT,
 370     KCCGST_SYMBOLS,
 371     KCCGST_GEOMETRY,
 372     _KCCGST_NUM_ENTRIES
 373 };
 374
 375 static const struct sval rules_kccgst_svals[_KCCGST_NUM_ENTRIES] = {
 376     [KCCGST_KEYCODES] = SVAL_LIT("keycodes"),
 377     [KCCGST_TYPES] = SVAL_LIT("types"),
 378     [KCCGST_COMPAT] = SVAL_LIT("compat"),
 379     [KCCGST_SYMBOLS] = SVAL_LIT("symbols"),
 380     [KCCGST_GEOMETRY] = SVAL_LIT("geometry"),
 381 };
 382
 383 /*
 384  * A broken-down version of xkb_rule_names (without the rules,
 385  * obviously).
 386  */
 387 struct rule_names {
 388     struct sval model;
 389     darray_sval layouts;
 390     darray_sval variants;
 391     darray_sval options;
 392 };
 393
 394 struct group {
 395     struct sval name;
 396     darray_sval elements;
 397 };
 398
 399 struct mapping {
 400     int mlvo_at_pos[_MLVO_NUM_ENTRIES];
 401     unsigned int num_mlvo;
 402     unsigned int defined_mlvo_mask;
 403     xkb_layout_index_t layout_idx, variant_idx;
 404     int kccgst_at_pos[_KCCGST_NUM_ENTRIES];
 405     unsigned int num_kccgst;
 406     unsigned int defined_kccgst_mask;
 407     bool skip;
 408 };
 409
 410 enum mlvo_match_type {
 411     MLVO_MATCH_NORMAL = 0,
 412     MLVO_MATCH_WILDCARD,
 413     MLVO_MATCH_GROUP,
 414 };
 415
 416 struct rule {
 417     struct sval mlvo_value_at_pos[_MLVO_NUM_ENTRIES];
 418     enum mlvo_match_type match_type_at_pos[_MLVO_NUM_ENTRIES];
 419     unsigned int num_mlvo_values;
 420     struct sval kccgst_value_at_pos[_KCCGST_NUM_ENTRIES];
 421     unsigned int num_kccgst_values;
 422     bool skip;
 423 };
 424
 425 /*
 426  * This is the main object used to match a given RMLVO against a rules
 427  * file and aggragate the results in a KcCGST. It goes through a simple
 428  * matching state machine, with tokens as transitions (see
 429  * matcher_match()).
 430  */
 431 struct matcher {
 432     struct xkb_context *ctx;
 433     /* Input.*/
 434     struct rule_names rmlvo;
 435     struct location loc;
 436     union lvalue val;
 437     struct scanner scanner;
 438     darray(struct group) groups;
 439     /* Current mapping. */
 440     struct mapping mapping;
 441     /* Current rule. */
 442     struct rule rule;
 443     /* Output. */
 444     darray_char kccgst[_KCCGST_NUM_ENTRIES];
 445 };
 446
 447 static struct sval
 448 strip_spaces(struct sval v)
 449 {
 450     while (v.len > 0 && isspace(v.start[0])) { v.len--; v.start++; }
 451     while (v.len > 0 && isspace(v.start[v.len - 1])) v.len--;
 452     return v;
 453 }
 454
 455 static darray_sval
 456 split_comma_separated_string(const char *s)
 457 {
 458     darray_sval arr = darray_new();
 459     struct sval val = { NULL, 0 };
 460
 461     /*
 462      * Make sure the array returned by this function always includes at
 463      * least one value, e.g. "" -> { "" } and "," -> { "", "" }.
 464      */
 465
 466     if (!s) {
 467         darray_append(arr, val);
 468         return arr;
 469     }
 470
 471     while (true) {
 472         val.start = s; val.len = 0;
 473         while (*s != '\0' && *s != ',') { s++; val.len++; }
 474         darray_append(arr, strip_spaces(val));
 475         if (*s == '\0') break;
 476         if (*s == ',') s++;
 477     }
 478
 479     return arr;
 480 }
 481
 482 static struct matcher *
 483 matcher_new(struct xkb_context *ctx,
 484             const struct xkb_rule_names *rmlvo)
 485 {
 486     struct matcher *m = calloc(1, sizeof(*m));
 487     if (!m)
 488         return NULL;
 489
 490     m->ctx = ctx;
 491     m->rmlvo.model.start = rmlvo->model;
 492     m->rmlvo.model.len = rmlvo->model ? strlen(rmlvo->model) : 0;
 493     m->rmlvo.layouts = split_comma_separated_string(rmlvo->layout);
 494     m->rmlvo.variants = split_comma_separated_string(rmlvo->variant);
 495     m->rmlvo.options = split_comma_separated_string(rmlvo->options);
 496
 497     return m;
 498 }
 499
 500 static void
 501 matcher_free(struct matcher *m)
 502 {
 503     struct group *group;
 504     if (!m)
 505         return;
 506     darray_free(m->rmlvo.layouts);
 507     darray_free(m->rmlvo.variants);
 508     darray_free(m->rmlvo.options);
 509     darray_foreach(group, m->groups)
 510         darray_free(group->elements);
 511     darray_free(m->groups);
 512     free(m);
 513 }
 514
 515 /* C99 is stupid. Just use the 1 variant when there are no args. */
 516 #define matcher_error1(matcher, msg) \
 517     log_warn(matcher->ctx, "rules/%s:%d:%d: " msg "\n", \
 518              matcher->scanner.file_name, matcher->loc.line, \
 519              matcher->loc.column)
 520 #define matcher_error(matcher, fmt, ...) \
 521     log_warn(matcher->ctx, "rules/%s:%d:%d: " fmt "\n", \
 522              matcher->scanner.file_name, matcher->loc.line, \
 523              matcher->loc.column, __VA_ARGS__)
 524
 525 static void
 526 matcher_group_start_new(struct matcher *m, struct sval name)
 527 {
 528     struct group group = { .name = name, .elements = darray_new() };
 529     darray_append(m->groups, group);
 530 }
 531
 532 static void
 533 matcher_group_add_element(struct matcher *m, struct sval element)
 534 {
 535     darray_append(darray_item(m->groups, darray_size(m->groups) - 1).elements,
 536                   element);
 537 }
 538
 539 static void
 540 matcher_mapping_start_new(struct matcher *m)
 541 {
 542     unsigned int i;
 543     for (i = 0; i < _MLVO_NUM_ENTRIES; i++)
 544         m->mapping.mlvo_at_pos[i] = -1;
 545     for (i = 0; i < _KCCGST_NUM_ENTRIES; i++)
 546         m->mapping.kccgst_at_pos[i] = -1;
 547     m->mapping.layout_idx = m->mapping.variant_idx = XKB_LAYOUT_INVALID;
 548     m->mapping.num_mlvo = m->mapping.num_kccgst = 0;
 549     m->mapping.defined_mlvo_mask = 0;
 550     m->mapping.defined_kccgst_mask = 0;
 551     m->mapping.skip = false;
 552 }
 553
 554 static int
 555 extract_layout_index(const char *s, size_t max_len, xkb_layout_index_t *out)
 556 {
 557     /* This function is pretty stupid, but works for now. */
 558     if (max_len < 3)
 559         return -1;
 560     if (s[0] != '[' || !isdigit(s[1]) || s[2] != ']')
 561         return -1;
 562     if (s[1] - '0' < 1 || s[1] - '0' > XKB_NUM_GROUPS)
 563         return -1;
 564     /* To zero-based index. */
 565     *out = s[1] - '0' - 1;
 566     return 3;
 567 }
 568
 569 static void
 570 matcher_mapping_set_mlvo(struct matcher *m, struct sval ident)
 571 {
 572     enum rules_mlvo mlvo;
 573     struct sval mlvo_sval;
 574     xkb_layout_index_t idx;
 575     int consumed;
 576
 577     for (mlvo = 0; mlvo < _MLVO_NUM_ENTRIES; mlvo++) {
 578         mlvo_sval = rules_mlvo_svals[mlvo];
 579
 580         if (svaleq_prefix(mlvo_sval, ident))
 581             break;
 582     }
 583
 584     /* Not found. */
 585     if (mlvo >= _MLVO_NUM_ENTRIES) {
 586         matcher_error(m,
 587                       "invalid mapping: %.*s is not a valid value here; "
 588                       "ignoring rule set",
 589                       ident.len, ident.start);
 590         m->mapping.skip = true;
 591         return;
 592     }
 593
 594     if (m->mapping.defined_mlvo_mask & (1 << mlvo)) {
 595         matcher_error(m,
 596                       "invalid mapping: %.*s appears twice on the same line; "
 597                       "ignoring rule set",
 598                       mlvo_sval.len, mlvo_sval.start);
 599         m->mapping.skip = true;
 600         return;
 601     }
 602
 603     /* If there are leftovers still, it must be an index. */
 604     if (mlvo_sval.len < ident.len) {
 605         consumed = extract_layout_index(ident.start + mlvo_sval.len,
 606                                        ident.len - mlvo_sval.len, &idx);
 607         if ((int) (ident.len - mlvo_sval.len) != consumed) {
 608             matcher_error(m,
 609                           "invalid mapping:\" %.*s\" may only be followed by a valid group index; "
 610                           "ignoring rule set",
 611                           mlvo_sval.len, mlvo_sval.start);
 612             m->mapping.skip = true;
 613             return;
 614         }
 615
 616         if (mlvo == MLVO_LAYOUT) {
 617             m->mapping.layout_idx = idx;
 618         }
 619         else if (mlvo == MLVO_VARIANT) {
 620             m->mapping.variant_idx = idx;
 621         }
 622         else {
 623             matcher_error(m,
 624                           "invalid mapping: \"%.*s\" cannot be followed by a group index; "
 625                           "ignoring rule set",
 626                           mlvo_sval.len, mlvo_sval.start);
 627             m->mapping.skip = true;
 628             return;
 629         }
 630     }
 631
 632     m->mapping.mlvo_at_pos[m->mapping.num_mlvo] = mlvo;
 633     m->mapping.defined_mlvo_mask |= 1 << mlvo;
 634     m->mapping.num_mlvo++;
 635 }
 636
 637 static void
 638 matcher_mapping_set_kccgst(struct matcher *m, struct sval ident)
 639 {
 640     enum rules_kccgst kccgst;
 641     struct sval kccgst_sval;
 642
 643     for (kccgst = 0; kccgst < _KCCGST_NUM_ENTRIES; kccgst++) {
 644         kccgst_sval = rules_kccgst_svals[kccgst];
 645
 646         if (svaleq(rules_kccgst_svals[kccgst], ident))
 647             break;
 648     }
 649
 650     /* Not found. */
 651     if (kccgst >= _KCCGST_NUM_ENTRIES) {
 652         matcher_error(m,
 653                       "invalid mapping: %.*s is not a valid value here; "
 654                       "ignoring rule set",
 655                       ident.len, ident.start);
 656         m->mapping.skip = true;
 657         return;
 658     }
 659
 660     if (m->mapping.defined_kccgst_mask & (1 << kccgst)) {
 661         matcher_error(m,
 662                       "invalid mapping: %.*s appears twice on the same line; "
 663                       "ignoring rule set",
 664                       kccgst_sval.len, kccgst_sval.start);
 665         m->mapping.skip = true;
 666         return;
 667     }
 668
 669     m->mapping.kccgst_at_pos[m->mapping.num_kccgst] = kccgst;
 670     m->mapping.defined_kccgst_mask |= 1 << kccgst;
 671     m->mapping.num_kccgst++;
 672 }
 673
 674 static void
 675 matcher_mapping_verify(struct matcher *m)
 676 {
 677     if (m->mapping.num_mlvo == 0) {
 678         matcher_error1(m,
 679                        "invalid mapping: must have at least one value on the left hand side; "
 680                        "ignoring rule set");
 681         goto skip;
 682     }
 683
 684     if (m->mapping.num_kccgst == 0) {
 685         matcher_error1(m,
 686                        "invalid mapping: must have at least one value on the right hand side; "
 687                        "ignoring rule set");
 688         goto skip;
 689     }
 690
 691     /*
 692      * This following is very stupid, but this is how it works.
 693      * See the "Notes" section in the overview above.
 694      */
 695
 696     if (m->mapping.defined_mlvo_mask & (1 << MLVO_LAYOUT)) {
 697         if (m->mapping.layout_idx == XKB_LAYOUT_INVALID) {
 698             if (darray_size(m->rmlvo.layouts) > 1)
 699                 goto skip;
 700         }
 701         else {
 702             if (darray_size(m->rmlvo.layouts) == 1 ||
 703                 m->mapping.layout_idx >= darray_size(m->rmlvo.layouts))
 704                 goto skip;
 705         }
 706     }
 707
 708     if (m->mapping.defined_mlvo_mask & (1 << MLVO_VARIANT)) {
 709         if (m->mapping.variant_idx == XKB_LAYOUT_INVALID) {
 710             if (darray_size(m->rmlvo.variants) > 1)
 711                 goto skip;
 712         }
 713         else {
 714             if (darray_size(m->rmlvo.variants) == 1 ||
 715                 m->mapping.variant_idx >= darray_size(m->rmlvo.variants))
 716                 goto skip;
 717         }
 718     }
 719
 720     return;
 721
 722 skip:
 723     m->mapping.skip = true;
 724 }
 725
 726 static void
 727 matcher_rule_start_new(struct matcher *m)
 728 {
 729     memset(&m->rule, 0, sizeof(m->rule));
 730     m->rule.skip = m->mapping.skip;
 731 }
 732
 733 static void
 734 matcher_rule_set_mlvo_common(struct matcher *m, struct sval ident,
 735                              enum mlvo_match_type match_type)
 736 {
 737     if (m->rule.num_mlvo_values + 1 > m->mapping.num_mlvo) {
 738         matcher_error1(m,
 739                        "invalid rule: has more values than the mapping line; "
 740                        "ignoring rule");
 741         m->rule.skip = true;
 742         return;
 743     }
 744     m->rule.match_type_at_pos[m->rule.num_mlvo_values] = match_type;
 745     m->rule.mlvo_value_at_pos[m->rule.num_mlvo_values] = ident;
 746     m->rule.num_mlvo_values++;
 747 }
 748
 749 static void
 750 matcher_rule_set_mlvo_wildcard(struct matcher *m)
 751 {
 752     struct sval dummy = { NULL, 0 };
 753     matcher_rule_set_mlvo_common(m, dummy, MLVO_MATCH_WILDCARD);
 754 }
 755
 756 static void
 757 matcher_rule_set_mlvo_group(struct matcher *m, struct sval ident)
 758 {
 759     matcher_rule_set_mlvo_common(m, ident, MLVO_MATCH_GROUP);
 760 }
 761
 762 static void
 763 matcher_rule_set_mlvo(struct matcher *m, struct sval ident)
 764 {
 765     matcher_rule_set_mlvo_common(m, ident, MLVO_MATCH_NORMAL);
 766 }
 767
 768 static void
 769 matcher_rule_set_kccgst(struct matcher *m, struct sval ident)
 770 {
 771     if (m->rule.num_kccgst_values + 1 > m->mapping.num_kccgst) {
 772         matcher_error1(m,
 773                        "invalid rule: has more values than the mapping line; "
 774                        "ignoring rule");
 775         m->rule.skip = true;
 776         return;
 777     }
 778     m->rule.kccgst_value_at_pos[m->rule.num_kccgst_values] = ident;
 779     m->rule.num_kccgst_values++;
 780 }
 781
 782 static bool
 783 match_group(struct matcher *m, struct sval group_name, struct sval to)
 784 {
 785     struct group *group;
 786     struct sval *element;
 787     bool found = false;
 788
 789     darray_foreach(group, m->groups) {
 790         if (svaleq(group->name, group_name)) {
 791             found = true;
 792             break;
 793         }
 794     }
 795
 796     if (!found) {
 797         /*
 798          * rules/evdev intentionally uses some undeclared group names
 799          * in rules (e.g. commented group definitions which may be
 800          * uncommented if needed). So we continue silently.
 801          */
 802         return false;
 803     }
 804
 805     darray_foreach(element, group->elements)
 806         if (svaleq(to, *element))
 807             return true;
 808
 809     return false;
 810 }
 811
 812 static bool
 813 match_value(struct matcher *m, struct sval val, struct sval to,
 814           enum mlvo_match_type match_type)
 815 {
 816     if (match_type == MLVO_MATCH_WILDCARD)
 817         return true;
 818     if (match_type == MLVO_MATCH_GROUP)
 819         return match_group(m, val, to);
 820     return svaleq(val, to);
 821 }
 822
 823 /*
 824  * This function performs %-expansion on @value (see overview above),
 825  * and appends the result to @to.
 826  */
 827 static bool
 828 append_expanded_kccgst_value(struct matcher *m, darray_char *to,
 829                              struct sval value)
 830 {
 831     unsigned int i;
 832     size_t original_size = darray_size(*to);
 833     const char *s = value.start;
 834     xkb_layout_index_t idx;
 835     int consumed;
 836     enum rules_mlvo mlv;
 837     struct sval expanded;
 838     char pfx, sfx;
 839
 840     /*
 841      * Appending  bar to  foo ->  foo (not an error if this happens)
 842      * Appending +bar to  foo ->  foo+bar
 843      * Appending  bar to +foo ->  bar+foo
 844      * Appending +bar to +foo -> +foo+bar
 845      */
 846     if (!darray_empty(*to) && s[0] != '+' && s[0] != '|') {
 847         if (darray_item(*to, 0) == '+' || darray_item(*to, 0) == '|')
 848             darray_prepend_items_nullterminate(*to, value.start, value.len);
 849         return true;
 850     }
 851
 852     /*
 853      * Some ugly hand-lexing here, but going through the scanner is more
 854      * trouble than it's worth, and the format is ugly on its own merit.
 855      */
 856     for (i = 0; i < value.len; ) {
 857         /* Check if that's a start of an expansion. */
 858         if (s[i] != '%') {
 859             /* Just a normal character. */
 860             darray_append_items_nullterminate(*to, &s[i++], 1);
 861             continue;
 862         }
 863         if (++i >= value.len) goto error;
 864
 865         pfx = sfx = 0;
 866
 867         /* Check for prefix. */
 868         if (s[i] == '(' || s[i] == '+' || s[i] == '|' ||
 869             s[i] == '_' || s[i] == '-') {
 870             pfx = s[i];
 871             if (s[i] == '(') sfx = ')';
 872             if (++i >= value.len) goto error;
 873         }
 874
 875         /* Mandatory model/layout/variant specifier. */
 876         switch (s[i++]) {
 877         case 'm': mlv = MLVO_MODEL; break;
 878         case 'l': mlv = MLVO_LAYOUT; break;
 879         case 'v': mlv = MLVO_VARIANT; break;
 880         default: goto error;
 881         }
 882
 883         /* Check for index. */
 884         idx = XKB_LAYOUT_INVALID;
 885         if (i < value.len) {
 886             if (s[i] == '[') {
 887                 if (mlv != MLVO_LAYOUT && mlv != MLVO_VARIANT) {
 888                     matcher_error1(m,
 889                                    "invalid index in %%-expansion; "
 890                                    "may only index layout or variant");
 891                     goto error;
 892                 }
 893
 894                 consumed = extract_layout_index(s + i, value.len - i, &idx);
 895                 if (consumed == -1) goto error;
 896                 i += consumed;
 897             }
 898             else {
 899                 idx = XKB_LAYOUT_INVALID;
 900             }
 901         }
 902
 903         /* Check for suffix, if there supposed to be one. */
 904         if (sfx != 0) {
 905             if (i >= value.len) goto error;
 906             if (s[i++] != sfx) goto error;
 907         }
 908
 909         /* Get the expanded value. */
 910         expanded.len = 0;
 911
 912         if (mlv == MLVO_LAYOUT) {
 913             if (idx != XKB_LAYOUT_INVALID &&
 914                 idx < darray_size(m->rmlvo.layouts) &&
 915                 darray_size(m->rmlvo.layouts) > 1)
 916                 expanded = darray_item(m->rmlvo.layouts, idx);
 917             else if (idx == XKB_LAYOUT_INVALID &&
 918                      darray_size(m->rmlvo.layouts) == 1)
 919                 expanded = darray_item(m->rmlvo.layouts, 0);
 920         }
 921         else if (mlv == MLVO_VARIANT) {
 922             if (idx != XKB_LAYOUT_INVALID &&
 923                 idx < darray_size(m->rmlvo.variants) &&
 924                 darray_size(m->rmlvo.variants) > 1)
 925                 expanded = darray_item(m->rmlvo.variants, idx);
 926             else if (idx == XKB_LAYOUT_INVALID &&
 927                      darray_size(m->rmlvo.variants) == 1)
 928                 expanded = darray_item(m->rmlvo.variants, 0);
 929         }
 930         else if (mlv == MLVO_MODEL) {
 931             expanded = m->rmlvo.model;
 932         }
 933
 934         /* If we didn't get one, skip silently. */
 935         if (expanded.len <= 0)
 936             continue;
 937
 938         if (pfx != 0)
 939             darray_append_items_nullterminate(*to, &pfx, 1);
 940         darray_append_items_nullterminate(*to, expanded.start, expanded.len);
 941         if (sfx != 0)
 942             darray_append_items_nullterminate(*to, &sfx, 1);
 943     }
 944
 945     return true;
 946
 947 error:
 948     matcher_error1(m, "invalid %%-expansion in value; not used");
 949     darray_resize(*to, original_size);
 950     return false;
 951 }
 952
 953 static void
 954 matcher_rule_verify(struct matcher *m)
 955 {
 956     if (m->rule.num_mlvo_values != m->mapping.num_mlvo ||
 957         m->rule.num_kccgst_values != m->mapping.num_kccgst) {
 958         matcher_error1(m,
 959                        "invalid rule: must have same number of values as mapping line;"
 960                        "ignoring rule");
 961         m->rule.skip = true;
 962     }
 963 }
 964
 965 static void
 966 matcher_rule_apply_if_matches(struct matcher *m)
 967 {
 968     unsigned int i;
 969     enum rules_mlvo mlvo;
 970     enum rules_kccgst kccgst;
 971     struct sval value, *option;
 972     enum mlvo_match_type match_type;
 973     bool matched = false;
 974     xkb_layout_index_t idx;
 975
 976     for (i = 0; i < m->mapping.num_mlvo; i++) {
 977         mlvo = m->mapping.mlvo_at_pos[i];
 978         value = m->rule.mlvo_value_at_pos[i];
 979         match_type = m->rule.match_type_at_pos[i];
 980
 981         if (mlvo == MLVO_MODEL) {
 982             matched = match_value(m, value, m->rmlvo.model, match_type);
 983         }
 984         else if (mlvo == MLVO_LAYOUT) {
 985             idx = m->mapping.layout_idx;
 986             idx = (idx == XKB_LAYOUT_INVALID ? 0 : idx);
 987             matched = match_value(m, value,
 988                                   darray_item(m->rmlvo.layouts, idx),
 989                                   match_type);
 990         }
 991         else if (mlvo == MLVO_VARIANT) {
 992             idx = m->mapping.layout_idx;
 993             idx = (idx == XKB_LAYOUT_INVALID ? 0 : idx);
 994             matched = match_value(m, value,
 995                                   darray_item(m->rmlvo.variants, idx),
 996                                   match_type);
 997         }
 998         else if (mlvo == MLVO_OPTION) {
 999             darray_foreach(option, m->rmlvo.options) {
1000                 matched = match_value(m, value, *option, match_type);
1001                 if (matched)
1002                     break;
1003             }
1004         }
1005
1006         if (!matched)
1007             return;
1008     }
1009
1010     for (i = 0; i < m->mapping.num_kccgst; i++) {
1011         kccgst = m->mapping.kccgst_at_pos[i];
1012         value = m->rule.kccgst_value_at_pos[i];
1013         append_expanded_kccgst_value(m, &m->kccgst[kccgst], value);
1014     }
1015
1016     /*
1017      * If a rule matches in a rule set, the rest of the set should be
1018      * skipped. However, rule sets matching against options may contain
1019      * several legitimate rules, so they are processed entirely.
1020      */
1021     if (!(m->mapping.defined_mlvo_mask & (1 << MLVO_OPTION)))
1022         m->mapping.skip = true;
1023 }
1024
1025 static enum rules_token
1026 gettok(struct matcher *m)
1027 {
1028     return lex(&m->scanner, &m->val, &m->loc);
1029 }
1030
1031 static bool
1032 matcher_match(struct matcher *m, const char *string, size_t len,
1033               const char *file_name, struct xkb_component_names *out)
1034 {
1035     enum rules_token tok;
1036
1037     if (!m)
1038         return false;
1039
1040     scanner_init(&m->scanner, m->ctx, string, len, file_name);
1041
1042 initial:
1043     switch (tok = gettok(m)) {
1044     case TOK_BANG:
1045         goto bang;
1046     case TOK_END_OF_LINE:
1047         goto initial;
1048     case TOK_END_OF_FILE:
1049         goto finish;
1050     default:
1051         goto unexpected;
1052     }
1053
1054 bang:
1055     switch (tok = gettok(m)) {
1056     case TOK_GROUP_NAME:
1057         matcher_group_start_new(m, m->val.string);
1058         goto group_name;
1059     case TOK_IDENTIFIER:
1060         matcher_mapping_start_new(m);
1061         matcher_mapping_set_mlvo(m, m->val.string);
1062         goto mapping_mlvo;
1063     default:
1064         goto unexpected;
1065     }
1066
1067 group_name:
1068     switch (tok = gettok(m)) {
1069     case TOK_EQUALS:
1070         goto group_element;
1071     default:
1072         goto unexpected;
1073     }
1074
1075 group_element:
1076     switch (tok = gettok(m)) {
1077     case TOK_IDENTIFIER:
1078         matcher_group_add_element(m, m->val.string);
1079         goto group_element;
1080     case TOK_END_OF_LINE:
1081         goto initial;
1082     default:
1083         goto unexpected;
1084     }
1085
1086 mapping_mlvo:
1087     switch (tok = gettok(m)) {
1088     case TOK_IDENTIFIER:
1089         if (!m->mapping.skip)
1090             matcher_mapping_set_mlvo(m, m->val.string);
1091         goto mapping_mlvo;
1092     case TOK_EQUALS:
1093         goto mapping_kccgst;
1094     default:
1095         goto unexpected;
1096     }
1097
1098 mapping_kccgst:
1099     switch (tok = gettok(m)) {
1100     case TOK_IDENTIFIER:
1101         if (!m->mapping.skip)
1102             matcher_mapping_set_kccgst(m, m->val.string);
1103         goto mapping_kccgst;
1104     case TOK_END_OF_LINE:
1105         if (!m->mapping.skip)
1106             matcher_mapping_verify(m);
1107         goto rule_mlvo_first;
1108     default:
1109         goto unexpected;
1110     }
1111
1112 rule_mlvo_first:
1113     switch (tok = gettok(m)) {
1114     case TOK_BANG:
1115         goto bang;
1116     case TOK_END_OF_LINE:
1117         goto rule_mlvo_first;
1118     case TOK_END_OF_FILE:
1119         goto finish;
1120     default:
1121         matcher_rule_start_new(m);
1122         goto rule_mlvo_no_tok;
1123     }
1124
1125 rule_mlvo:
1126     tok = gettok(m);
1127 rule_mlvo_no_tok:
1128     switch (tok) {
1129     case TOK_IDENTIFIER:
1130         if (!m->rule.skip)
1131             matcher_rule_set_mlvo(m, m->val.string);
1132         goto rule_mlvo;
1133     case TOK_STAR:
1134         if (!m->rule.skip)
1135             matcher_rule_set_mlvo_wildcard(m);
1136         goto rule_mlvo;
1137     case TOK_GROUP_NAME:
1138         if (!m->rule.skip)
1139             matcher_rule_set_mlvo_group(m, m->val.string);
1140         goto rule_mlvo;
1141     case TOK_EQUALS:
1142         goto rule_kccgst;
1143     default:
1144         goto unexpected;
1145     }
1146
1147 rule_kccgst:
1148     switch (tok = gettok(m)) {
1149     case TOK_IDENTIFIER:
1150         if (!m->rule.skip)
1151             matcher_rule_set_kccgst(m, m->val.string);
1152         goto rule_kccgst;
1153     case TOK_END_OF_LINE:
1154         if (!m->rule.skip)
1155             matcher_rule_verify(m);
1156         if (!m->rule.skip)
1157             matcher_rule_apply_if_matches(m);
1158         goto rule_mlvo_first;
1159     default:
1160         goto unexpected;
1161     }
1162
1163 unexpected:
1164     switch (tok) {
1165     case TOK_ERROR:
1166         goto error;
1167     default:
1168         goto state_error;
1169     }
1170
1171 finish:
1172     if (darray_empty(m->kccgst[KCCGST_KEYCODES]) ||
1173         darray_empty(m->kccgst[KCCGST_TYPES]) ||
1174         darray_empty(m->kccgst[KCCGST_COMPAT]) ||
1175         /* darray_empty(m->kccgst[KCCGST_GEOMETRY]) || */
1176         darray_empty(m->kccgst[KCCGST_SYMBOLS]))
1177         goto error;
1178
1179     out->keycodes = darray_mem(m->kccgst[KCCGST_KEYCODES], 0);
1180     out->types = darray_mem(m->kccgst[KCCGST_TYPES], 0);
1181     out->compat = darray_mem(m->kccgst[KCCGST_COMPAT], 0);
1182     /* out->geometry = darray_mem(m->kccgst[KCCGST_GEOMETRY], 0); */
1183     darray_free(m->kccgst[KCCGST_GEOMETRY]);
1184     out->symbols = darray_mem(m->kccgst[KCCGST_SYMBOLS], 0);
1185
1186     return true;
1187
1188 state_error:
1189     matcher_error1(m, "unexpected token");
1190 error:
1191     return false;
1192 }
1193
1194 bool
1195 xkb_components_from_rules(struct xkb_context *ctx,
1196                           const struct xkb_rule_names *rmlvo,
1197                           struct xkb_component_names *out)
1198 {
1199     bool ret = false;
1200     FILE *file;
1201     char *path;
1202     int fd;
1203     struct stat stat_buf;
1204     char *string;
1205     struct matcher *matcher;
1206
1207     file = FindFileInXkbPath(ctx, rmlvo->rules, FILE_TYPE_RULES, &path);
1208     if (!file)
1209         goto err_out;
1210
1211     fd = fileno(file);
1212
1213     if (fstat(fd, &stat_buf) != 0) {
1214         log_err(ctx, "Couldn't stat rules file\n");
1215         goto err_file;
1216     }
1217
1218     string = mmap(NULL, stat_buf.st_size, PROT_READ, MAP_SHARED, fd, 0);
1219     if (string == MAP_FAILED) {
1220         log_err(ctx, "Couldn't mmap rules file (%lld bytes)\n",
1221                 (long long) stat_buf.st_size);
1222         goto err_file;
1223     }
1224
1225     matcher = matcher_new(ctx, rmlvo);
1226     ret = matcher_match(matcher, string, stat_buf.st_size, rmlvo->rules, out);
1227     if (!ret)
1228         log_err(ctx, "No components returned from XKB rules \"%s\"\n", path);
1229     matcher_free(matcher);
1230
1231     munmap(string, stat_buf.st_size);
1232 err_file:
1233     free(path);
1234     fclose(file);
1235 err_out:
1236     return ret;
1237 }