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