src/xkbcomp/rules.c

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