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