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