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