src/xkbcomp/rules.c

   1 /************************************************************
   2  Copyright (c) 1996 by Silicon Graphics Computer Systems, Inc.
   3
   4  Permission to use, copy, modify, and distribute this
   5  software and its documentation for any purpose and without
   6  fee is hereby granted, provided that the above copyright
   7  notice appear in all copies and that both that copyright
   8  notice and this permission notice appear in supporting
   9  documentation, and that the name of Silicon Graphics not be
  10  used in advertising or publicity pertaining to distribution
  11  of the software without specific prior written permission.
  12  Silicon Graphics makes no representation about the suitability
  13  of this software for any purpose. It is provided "as is"
  14  without any express or implied warranty.
  15
  16  SILICON GRAPHICS DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS
  17  SOFTWARE, INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY
  18  AND FITNESS FOR A PARTICULAR PURPOSE. IN NO EVENT SHALL SILICON
  19  GRAPHICS BE LIABLE FOR ANY SPECIAL, INDIRECT OR CONSEQUENTIAL
  20  DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
  21  DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE
  22  OR OTHER TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION  WITH
  23  THE USE OR PERFORMANCE OF THIS SOFTWARE.
  24
  25  ********************************************************/
  26
  27 #include <stdio.h>
  28 #include <ctype.h>
  29
  30 #include "rules.h"
  31 #include "path.h"
  32
  33 #define DFLT_LINE_SIZE 128
  34
  35 struct input_line {
  36     size_t size;
  37     size_t offset;
  38     char buf[DFLT_LINE_SIZE];
  39     char *line;
  40 };
  41
  42 static void
  43 input_line_init(struct input_line *line)
  44 {
  45     line->size = DFLT_LINE_SIZE;
  46     line->offset = 0;
  47     line->line = line->buf;
  48 }
  49
  50 static void
  51 input_line_deinit(struct input_line *line)
  52 {
  53     if (line->line != line->buf)
  54         free(line->line);
  55     line->offset = 0;
  56     line->size = DFLT_LINE_SIZE;
  57     line->line = line->buf;
  58 }
  59
  60 static int
  61 input_line_add_char(struct input_line *line, int ch)
  62 {
  63     if (line->offset >= line->size) {
  64         if (line->line == line->buf) {
  65             line->line = malloc(line->size * 2);
  66             memcpy(line->line, line->buf, line->size);
  67         }
  68         else {
  69             line->line = realloc(line->line, line->size * 2);
  70         }
  71
  72         line->size *= 2;
  73     }
  74
  75     line->line[line->offset++] = ch;
  76     return ch;
  77 }
  78
  79 static bool
  80 input_line_get(FILE *file, struct input_line *line)
  81 {
  82     int ch;
  83     bool end_of_file = false;
  84     bool space_pending;
  85     bool slash_pending;
  86     bool in_comment;
  87
  88     while (!end_of_file && line->offset == 0) {
  89         space_pending = slash_pending = in_comment = false;
  90
  91         while ((ch = getc(file)) != '\n' && ch != EOF) {
  92             if (ch == '\\') {
  93                 ch = getc(file);
  94
  95                 if (ch == EOF)
  96                     break;
  97
  98                 if (ch == '\n') {
  99                     in_comment = false;
 100                     ch = ' ';
 101                 }
 102             }
 103
 104             if (in_comment)
 105                 continue;
 106
 107             if (ch == '/') {
 108                 if (slash_pending) {
 109                     in_comment = true;
 110                     slash_pending = false;
 111                 }
 112                 else {
 113                     slash_pending = true;
 114                 }
 115
 116                 continue;
 117             }
 118
 119             if (slash_pending) {
 120                 if (space_pending) {
 121                     input_line_add_char(line, ' ');
 122                     space_pending = false;
 123                 }
 124
 125                 input_line_add_char(line, '/');
 126                 slash_pending = false;
 127             }
 128
 129             if (isspace(ch)) {
 130                 while (isspace(ch) && ch != '\n' && ch != EOF)
 131                     ch = getc(file);
 132
 133                 if (ch == EOF)
 134                     break;
 135
 136                 if (ch != '\n' && line->offset > 0)
 137                     space_pending = true;
 138
 139                 ungetc(ch, file);
 140             }
 141             else {
 142                 if (space_pending) {
 143                     input_line_add_char(line, ' ');
 144                     space_pending = false;
 145                 }
 146
 147                 if (ch == '!') {
 148                     if (line->offset != 0) {
 149                         WARN("The '!' is legal only at start of line\n");
 150                         ACTION("Line containing '!' ignored\n");
 151                         line->offset = 0;
 152                         break;
 153                     }
 154                 }
 155
 156                 input_line_add_char(line, ch);
 157             }
 158         }
 159
 160         if (ch == EOF)
 161             end_of_file = true;
 162     }
 163
 164     if (line->offset == 0 && end_of_file)
 165         return false;
 166
 167     input_line_add_char(line, '\0');
 168     return true;
 169 }
 170
 171 /***====================================================================***/
 172
 173 enum {
 174     /* "Parts" - the MLVO which rules file maps to components. */
 175     MODEL = 0,
 176     LAYOUT,
 177     VARIANT,
 178     OPTION,
 179
 180 #define PART_MASK \
 181     ((1 << MODEL) | (1 << LAYOUT) | (1 << VARIANT) | (1 << OPTION))
 182
 183     /* Components */
 184     KEYCODES,
 185     SYMBOLS,
 186     TYPES,
 187     COMPAT,
 188     GEOMETRY,
 189     KEYMAP,
 190
 191 #define COMPONENT_MASK \
 192     ((1 << KEYCODES) | (1 << SYMBOLS) | (1 << TYPES) | (1 << COMPAT) | \
 193      (1 << GEOMETRY) | (1 << KEYMAP))
 194
 195     MAX_WORDS
 196 };
 197
 198 static const char *cname[] = {
 199     [MODEL] = "model",
 200     [LAYOUT] = "layout",
 201     [VARIANT] = "variant",
 202     [OPTION] = "option",
 203
 204     [KEYCODES] = "keycodes",
 205     [SYMBOLS] = "symbols",
 206     [TYPES] = "types",
 207     [COMPAT] = "compat",
 208     [GEOMETRY] = "geometry",
 209     [KEYMAP] = "keymap",
 210 };
 211
 212 struct var_defs {
 213     const char *model;
 214     const char *layout;
 215     const char *variant;
 216     const char *options;
 217 };
 218
 219 struct multi_defs {
 220     const char *model;
 221     const char *layout[XkbNumKbdGroups + 1];
 222     const char *variant[XkbNumKbdGroups + 1];
 223     char *options;
 224 };
 225
 226 struct mapping {
 227     /* Sequential id for the mappings. */
 228     int number;
 229     size_t num_maps;
 230
 231     struct {
 232         int word;
 233         int index;
 234     } map[MAX_WORDS];
 235 };
 236
 237 struct var_desc {
 238     char *name;
 239     char *desc;
 240 };
 241
 242 struct group {
 243     int number;
 244     char *name;
 245     char *words;
 246 };
 247
 248 enum rule_flag {
 249     RULE_FLAG_PENDING_MATCH = (1L << 1),
 250     RULE_FLAG_OPTION        = (1L << 2),
 251     RULE_FLAG_APPEND        = (1L << 3),
 252     RULE_FLAG_NORMAL        = (1L << 4),
 253 };
 254
 255 struct rule {
 256     int number;
 257
 258     char *model;
 259     char *layout;
 260     int layout_num;
 261     char *variant;
 262     int variant_num;
 263     char *option;
 264
 265     /* yields */
 266
 267     char *keycodes;
 268     char *symbols;
 269     char *types;
 270     char *compat;
 271     char *keymap;
 272     unsigned flags;
 273 };
 274
 275 struct rules {
 276     size_t sz_rules;
 277     size_t num_rules;
 278     struct rule *rules;
 279
 280     size_t sz_groups;
 281     size_t num_groups;
 282     struct group *groups;
 283 };
 284
 285 /***====================================================================***/
 286
 287 /*
 288  * Resolve numeric index, such as "[4]" in layout[4]. Missing index
 289  * means zero.
 290  */
 291 static char *
 292 get_index(char *str, int *ndx)
 293 {
 294     int empty = 0, consumed = 0, num;
 295
 296     sscanf(str, "[%n%d]%n", &empty, &num, &consumed);
 297     if (consumed > 0) {
 298         *ndx = num;
 299         str += consumed;
 300     } else if (empty > 0) {
 301         *ndx = -1;
 302     } else {
 303         *ndx = 0;
 304     }
 305
 306     return str;
 307 }
 308
 309 /*
 310  * Match a mapping line which opens a rule, e.g:
 311  * ! model      layout[4]       variant[4]      =       symbols       geometry
 312  * Which will be followed by lines such as:
 313  *   *          ben             basic           =       +in(ben):4    nec(pc98)
 314  * So if the MLVO matches the LHS of some line, we'll get the components
 315  * on the RHS.
 316  * In this example, we will get for the second and fourth columns:
 317  * mapping->map[1] = {.word = LAYOUT, .index = 4}
 318  * mapping->map[3] = {.word = SYMBOLS, .index = 0}
 319  */
 320 static void
 321 match_mapping_line(struct input_line *line, struct mapping *mapping)
 322 {
 323     char *tok;
 324     char *str = &line->line[1];
 325     unsigned present = 0, layout_ndx_present = 0, variant_ndx_present = 0;
 326     int i, tmp;
 327     size_t len;
 328     int ndx;
 329     char *strtok_buf;
 330     bool found;
 331
 332     /*
 333      * Remember the last sequential mapping id (incremented if the match
 334      * is successful).
 335      */
 336     tmp = mapping->number;
 337     memset(mapping, 0, sizeof(*mapping));
 338     mapping->number = tmp;
 339
 340     while ((tok = strtok_r(str, " ", &strtok_buf)) != NULL) {
 341         found = false;
 342         str = NULL;
 343
 344         if (strcmp(tok, "=") == 0)
 345             continue;
 346
 347         for (i = 0; i < MAX_WORDS; i++) {
 348             len = strlen(cname[i]);
 349
 350             if (strncmp(cname[i], tok, len) == 0) {
 351                 if (strlen(tok) > len) {
 352                     char *end = get_index(tok + len, &ndx);
 353
 354                     if ((i != LAYOUT && i != VARIANT) ||
 355                         *end != '\0' || ndx == -1) {
 356                         WARN("Illegal %s index: %d\n", cname[i], ndx);
 357                         WARN("Can only index layout and variant\n");
 358                         break;
 359                     }
 360
 361                     if (ndx < 1 || ndx > XkbNumKbdGroups) {
 362                         WARN("Illegal %s index: %d\n", cname[i], ndx);
 363                         WARN("Index must be in range 1..%d\n", XkbNumKbdGroups);
 364                         break;
 365                     }
 366                 } else {
 367                     ndx = 0;
 368                 }
 369
 370                 found = true;
 371
 372                 if (present & (1 << i)) {
 373                     if ((i == LAYOUT && layout_ndx_present & (1 << ndx)) ||
 374                         (i == VARIANT && variant_ndx_present & (1 << ndx))) {
 375                         WARN("Component \"%s\" listed twice\n", tok);
 376                         ACTION("Second definition ignored\n");
 377                         break;
 378                     }
 379                 }
 380
 381                 present |= (1 << i);
 382                 if (i == LAYOUT)
 383                     layout_ndx_present |= 1 << ndx;
 384                 if (i == VARIANT)
 385                     variant_ndx_present |= 1 << ndx;
 386
 387                 mapping->map[mapping->num_maps].word = i;
 388                 mapping->map[mapping->num_maps].index = ndx;
 389                 mapping->num_maps++;
 390                 break;
 391             }
 392         }
 393
 394         if (!found) {
 395             WARN("Unknown component \"%s\"\n", tok);
 396             ACTION("ignored\n");
 397         }
 398     }
 399
 400     if ((present & PART_MASK) == 0) {
 401         WARN("Mapping needs at least one MLVO part\n");
 402         ACTION("Illegal mapping ignored\n");
 403         mapping->num_maps = 0;
 404         return;
 405     }
 406
 407     if ((present & COMPONENT_MASK) == 0) {
 408         WARN("Mapping needs at least one component\n");
 409         ACTION("Illegal mapping ignored\n");
 410         mapping->num_maps = 0;
 411         return;
 412     }
 413
 414     if (((present & COMPONENT_MASK) & (1 << KEYMAP)) &&
 415         ((present & COMPONENT_MASK) != (1 << KEYMAP))) {
 416         WARN("Keymap cannot appear with other components\n");
 417         ACTION("Illegal mapping ignored\n");
 418         mapping->num_maps = 0;
 419         return;
 420     }
 421
 422     mapping->number++;
 423 }
 424
 425 /*
 426  * Match a line such as:
 427  * ! $pcmodels = pc101 pc102 pc104 pc105
 428  */
 429 static bool
 430 match_group_line(struct input_line *line, struct group *group)
 431 {
 432     int i;
 433     char *name = strchr(line->line, '$');
 434     char *words = strchr(name, ' ');
 435
 436     if (!words)
 437         return false;
 438
 439     *words++ = '\0';
 440
 441     for (; *words; words++) {
 442         if (*words != '=' && *words != ' ')
 443             break;
 444     }
 445
 446     if (*words == '\0')
 447         return false;
 448
 449     group->name = strdup(name);
 450     group->words = strdup(words);
 451
 452     words = group->words;
 453     for (i = 1; *words; words++) {
 454         if (*words == ' ') {
 455             *words++ = '\0';
 456             i++;
 457         }
 458     }
 459     group->number = i;
 460
 461     return true;
 462
 463 }
 464
 465 /* Match lines following a mapping (see match_mapping_line comment). */
 466 static bool
 467 match_rule_line(struct input_line *line, struct mapping *mapping,
 468                 struct rule *rule)
 469 {
 470     char *str, *tok;
 471     int nread, i;
 472     char *strtok_buf;
 473     bool append = false;
 474     const char *names[MAX_WORDS] = { NULL };
 475
 476     if (mapping->num_maps == 0) {
 477         WARN("Must have a mapping before first line of data\n");
 478         ACTION("Illegal line of data ignored\n");
 479         return false;
 480     }
 481
 482     str = line->line;
 483
 484     for (nread = 0; (tok = strtok_r(str, " ", &strtok_buf)) != NULL; nread++) {
 485         str = NULL;
 486
 487         if (strcmp(tok, "=") == 0) {
 488             nread--;
 489             continue;
 490         }
 491
 492         if (nread > mapping->num_maps) {
 493             WARN("Too many words on a line\n");
 494             ACTION("Extra word \"%s\" ignored\n", tok);
 495             continue;
 496         }
 497
 498         names[mapping->map[nread].word] = tok;
 499         if (*tok == '+' || *tok == '|')
 500             append = true;
 501     }
 502
 503     if (nread < mapping->num_maps) {
 504         WARN("Too few words on a line: %s\n", line->line);
 505         ACTION("line ignored\n");
 506         return false;
 507     }
 508
 509     rule->flags = 0;
 510     rule->number = mapping->number;
 511
 512     if (names[OPTION])
 513         rule->flags |= RULE_FLAG_OPTION;
 514     else if (append)
 515         rule->flags |= RULE_FLAG_APPEND;
 516     else
 517         rule->flags |= RULE_FLAG_NORMAL;
 518
 519     rule->model = uDupString(names[MODEL]);
 520     rule->layout = uDupString(names[LAYOUT]);
 521     rule->variant = uDupString(names[VARIANT]);
 522     rule->option = uDupString(names[OPTION]);
 523
 524     rule->keycodes = uDupString(names[KEYCODES]);
 525     rule->symbols = uDupString(names[SYMBOLS]);
 526     rule->types = uDupString(names[TYPES]);
 527     rule->compat = uDupString(names[COMPAT]);
 528     rule->keymap = uDupString(names[KEYMAP]);
 529
 530     rule->layout_num = rule->variant_num = 0;
 531     for (i = 0; i < nread; i++) {
 532         if (mapping->map[i].index) {
 533             if (mapping->map[i].word == LAYOUT)
 534                 rule->layout_num = mapping->map[i].index;
 535             if (mapping->map[i].word == VARIANT)
 536                 rule->variant_num = mapping->map[i].index;
 537         }
 538     }
 539
 540     return true;
 541 }
 542
 543 static bool
 544 match_line(struct input_line *line, struct mapping *mapping,
 545            struct rule *rule, struct group *group)
 546 {
 547     if (line->line[0] != '!')
 548         return match_rule_line(line, mapping, rule);
 549
 550     if (line->line[1] == '$' || (line->line[1] == ' ' && line->line[2] == '$'))
 551         return match_group_line(line, group);
 552
 553     match_mapping_line(line, mapping);
 554     return false;
 555 }
 556
 557 static void
 558 squeeze_spaces(char *p1)
 559 {
 560    char *p2;
 561
 562    for (p2 = p1; *p2; p2++) {
 563        *p1 = *p2;
 564        if (*p1 != ' ')
 565            p1++;
 566    }
 567
 568    *p1 = '\0';
 569 }
 570
 571 /*
 572  * Expand the layout and variant of a var_defs and remove extraneous spaces.
 573  * If there's one layout/variant, it is kept in .layout[0]/.variant[0], else
 574  * is kept in [1], [2] and so on, and [0] remains empty.
 575  * For example, this var_defs:
 576  *      .model  = "pc105",
 577  *      .layout = "us,il,ru,ca"
 578  *      .variant = ",,,multix"
 579  *      .options = "grp:alts_toggle,   ctrl:nocaps,  compose:rwin"
 580  * Is expanded into this multi_defs:
 581  *      .model = "pc105"
 582  *      .layout = {NULL, "us", "il", "ru", "ca"},
 583  *      .variant = {NULL, "", "", "", "multix"},
 584  *      .options = "grp:alts_toggle,ctrl:nocaps,compose:rwin"
 585  */
 586 static bool
 587 make_multi_defs(struct multi_defs *mdefs, struct var_defs *defs)
 588 {
 589     char *p;
 590     int i;
 591
 592     memset(mdefs, 0, sizeof(*mdefs));
 593
 594     if (defs->model) {
 595         mdefs->model = defs->model;
 596     }
 597
 598     if (defs->options) {
 599         mdefs->options = strdup(defs->options);
 600         if (mdefs->options == NULL)
 601             return false;
 602
 603         squeeze_spaces(mdefs->options);
 604     }
 605
 606     if (defs->layout) {
 607         if (!strchr(defs->layout, ',')) {
 608             mdefs->layout[0] = defs->layout;
 609         }
 610         else {
 611             p = strdup(defs->layout);
 612             if (p == NULL)
 613                 return false;
 614
 615             squeeze_spaces(p);
 616             mdefs->layout[1] = p;
 617
 618             for (i = 2; i <= XkbNumKbdGroups; i++) {
 619                 if ((p = strchr(p, ','))) {
 620                     *p++ = '\0';
 621                     mdefs->layout[i] = p;
 622                 }
 623                 else {
 624                     break;
 625                 }
 626             }
 627
 628             if (p && (p = strchr(p, ',')))
 629                 *p = '\0';
 630         }
 631     }
 632
 633     if (defs->variant) {
 634         if (!strchr(defs->variant, ',')) {
 635             mdefs->variant[0] = defs->variant;
 636         }
 637         else {
 638             p = strdup(defs->variant);
 639             if (p == NULL)
 640                 return false;
 641
 642             squeeze_spaces(p);
 643             mdefs->variant[1] = p;
 644
 645             for (i = 2; i <= XkbNumKbdGroups; i++) {
 646                 if ((p = strchr(p, ','))) {
 647                     *p++ = '\0';
 648                     mdefs->variant[i] = p;
 649                 } else {
 650                     break;
 651                 }
 652             }
 653
 654             if (p && (p = strchr(p, ',')))
 655                 *p = '\0';
 656         }
 657     }
 658
 659     return true;
 660 }
 661
 662 static void
 663 free_multi_defs(struct multi_defs *defs)
 664 {
 665     free(defs->options);
 666     /*
 667      * See make_multi_defs comment for the hack; the same strdup'd
 668      * string is split among the indexes, but the one in [0] is const.
 669      */
 670     free(UNCONSTIFY(defs->layout[1]));
 671     free(UNCONSTIFY(defs->variant[1]));
 672 }
 673
 674 /* See apply_rule below. */
 675 static void
 676 apply(const char *src, char **dst)
 677 {
 678     int ret;
 679     char *tmp;
 680
 681     if (!src)
 682         return;
 683
 684     if (*src == '+' || *src == '!') {
 685         tmp = *dst;
 686         ret = asprintf(dst, "%s%s", *dst, src);
 687         if (ret < 0)
 688             *dst = NULL;
 689         free(tmp);
 690     }
 691     else if (*dst == NULL) {
 692         *dst = strdup(src);
 693     }
 694 }
 695
 696 /*
 697  * Add the info from the matching rule to the resulting
 698  * xkb_component_names. If we already had a match for something
 699  * (e.g. keycodes), and the rule is not an appending one (e.g.
 700  * +whatever), than we don't override but drop the new one.
 701  */
 702 static void
 703 apply_rule(struct rule *rule, struct xkb_component_names *kccgst)
 704 {
 705     /* Clear the flag because it's applied. */
 706     rule->flags &= ~RULE_FLAG_PENDING_MATCH;
 707
 708     apply(rule->keycodes, &kccgst->keycodes);
 709     apply(rule->symbols, &kccgst->symbols);
 710     apply(rule->types, &kccgst->types);
 711     apply(rule->compat, &kccgst->compat);
 712     apply(rule->keymap, &kccgst->keymap);
 713 }
 714
 715 /*
 716  * Match if name is part of the group, e.g. if the following
 717  * group is defined:
 718  *      ! $qwertz = al cz de hr hu ro si sk
 719  * then
 720  *      match_group_member(rules, "qwertz", "hr")
 721  * will return true.
 722  */
 723 static bool
 724 match_group_member(struct rules *rules, const char *group_name,
 725                    const char *name)
 726 {
 727    int i;
 728    const char *word;
 729    struct group *group;
 730
 731    for (i = 0; i < rules->num_groups; i++)
 732        if (strcmp(rules->groups[i].name, group_name) == 0)
 733            break;
 734
 735    if (i == rules->num_groups)
 736        return false;
 737    group = &rules->groups[i];
 738
 739    word = group->words;
 740    for (i = 0; i < group->number; i++, word += strlen(word) + 1)
 741        if (strcmp(word, name) == 0)
 742            return true;
 743
 744    return false;
 745 }
 746
 747 /* Match @needle out of @sep-seperated @haystack. */
 748 static bool
 749 match_one_of(const char *haystack, const char *needle, char sep)
 750 {
 751     const char *s = strstr(haystack, needle);
 752
 753     if (s == NULL)
 754         return false;
 755
 756     if (s != haystack && *s != sep)
 757         return false;
 758
 759     s += strlen(needle);
 760     if (*s != '\0' && *s != sep)
 761         return false;
 762
 763     return true;
 764 }
 765
 766 static int
 767 apply_rule_if_matches(struct rules *rules, struct rule *rule,
 768                       struct multi_defs *mdefs,
 769                       struct xkb_component_names *kccgst)
 770 {
 771     bool pending = false;
 772
 773     if (rule->model) {
 774         if (mdefs->model == NULL)
 775             return 0;
 776
 777         if (strcmp(rule->model, "*") == 0) {
 778             pending = true;
 779         }
 780         else if (rule->model[0] == '$') {
 781             if (!match_group_member(rules, rule->model, mdefs->model))
 782                 return 0;
 783         }
 784         else if (strcmp(rule->model, mdefs->model) != 0) {
 785             return 0;
 786         }
 787     }
 788
 789     if (rule->option) {
 790         if (mdefs->options == NULL)
 791             return 0;
 792
 793         if (!match_one_of(mdefs->options, rule->option, ','))
 794             return 0;
 795     }
 796
 797     if (rule->layout) {
 798         if (mdefs->layout[rule->layout_num] == NULL ||
 799             *mdefs->layout[rule->layout_num] == '\0')
 800             return 0;
 801
 802         if (strcmp(rule->layout, "*") == 0) {
 803             pending = true;
 804         }
 805         else if (rule->layout[0] == '$') {
 806             if (!match_group_member(rules, rule->layout,
 807                                     mdefs->layout[rule->layout_num]))
 808                   return 0;
 809         }
 810         else if (strcmp(rule->layout,
 811                         mdefs->layout[rule->layout_num]) != 0) {
 812             return 0;
 813         }
 814     }
 815
 816     if (rule->variant) {
 817         if (mdefs->variant[rule->variant_num] == NULL ||
 818             *mdefs->variant[rule->variant_num] == '\0')
 819             return 0;
 820
 821         if (strcmp(rule->variant, "*") == 0) {
 822             pending = true;
 823         } else if (rule->variant[0] == '$') {
 824             if (!match_group_member(rules, rule->variant,
 825                                     mdefs->variant[rule->variant_num]))
 826                 return 0;
 827         }
 828         else if (strcmp(rule->variant,
 829                         mdefs->variant[rule->variant_num]) != 0) {
 830             return 0;
 831         }
 832     }
 833
 834     if (pending) {
 835         rule->flags |= RULE_FLAG_PENDING_MATCH;
 836     } else {
 837         /* Exact match, apply it now. */
 838         apply_rule(rule, kccgst);
 839     }
 840
 841     return rule->number;
 842 }
 843
 844 static void
 845 clear_partial_matches(struct rules *rules)
 846 {
 847     int i;
 848
 849     for (i = 0; i < rules->num_rules; i++)
 850         rules->rules[i].flags &= ~RULE_FLAG_PENDING_MATCH;
 851 }
 852
 853 static void
 854 apply_partial_matches(struct rules *rules, struct xkb_component_names *kccgst)
 855 {
 856     int i;
 857
 858     for (i = 0; i < rules->num_rules; i++)
 859         if (rules->rules[i].flags & RULE_FLAG_PENDING_MATCH)
 860             apply_rule(&rules->rules[i], kccgst);
 861 }
 862
 863 static void
 864 apply_matching_rules(struct rules *rules, struct multi_defs *mdefs,
 865                      struct xkb_component_names *kccgst, unsigned int flags)
 866 {
 867     int i;
 868     int skip = -1;
 869     struct rule *rule;
 870
 871     for (i = 0; i < rules->num_rules; i++) {
 872         rule = &rules->rules[i];
 873
 874         if ((rule->flags & flags) != flags)
 875             continue;
 876
 877         if ((flags & RULE_FLAG_OPTION) == 0 && rule->number == skip)
 878             continue;
 879
 880         skip = apply_rule_if_matches(rules, rule, mdefs, kccgst);
 881     }
 882 }
 883
 884 /***====================================================================***/
 885
 886 static char *
 887 substitute_vars(char *name, struct multi_defs *mdefs)
 888 {
 889     char *str, *outstr, *var;
 890     char *orig = name;
 891     size_t len, extra_len;
 892     char pfx, sfx;
 893     int ndx;
 894
 895     if (!name)
 896         return NULL;
 897
 898     str = strchr(name, '%');
 899     if (str == NULL)
 900         return name;
 901
 902     len = strlen(name);
 903
 904     while (str != NULL) {
 905         pfx = str[1];
 906         extra_len = 0;
 907
 908         if (pfx == '+' || pfx == '|' || pfx == '_' || pfx == '-') {
 909             extra_len = 1;
 910             str++;
 911         }
 912         else if (pfx == '(') {
 913             extra_len = 2;
 914             str++;
 915         }
 916
 917         var = str + 1;
 918         str = get_index(var + 1, &ndx);
 919         if (ndx == -1) {
 920             str = strchr(str, '%');
 921             continue;
 922         }
 923
 924         if (*var == 'l' && mdefs->layout[ndx] && *mdefs->layout[ndx])
 925             len += strlen(mdefs->layout[ndx]) + extra_len;
 926         else if (*var == 'm' && mdefs->model)
 927             len += strlen(mdefs->model) + extra_len;
 928         else if (*var == 'v' && mdefs->variant[ndx] && *mdefs->variant[ndx])
 929             len += strlen(mdefs->variant[ndx]) + extra_len;
 930
 931         if (pfx == '(' && *str == ')')
 932             str++;
 933
 934         str = strchr(&str[0], '%');
 935     }
 936
 937     name = malloc(len + 1);
 938     str = orig;
 939     outstr = name;
 940
 941     while (*str != '\0') {
 942         if (str[0] == '%') {
 943             str++;
 944             pfx = str[0];
 945             sfx = '\0';
 946
 947             if (pfx == '+' || pfx == '|' || pfx == '_' || pfx == '-') {
 948                 str++;
 949             }
 950             else if (pfx == '(') {
 951                 sfx = ')';
 952                 str++;
 953             }
 954             else {
 955                 pfx = '\0';
 956             }
 957
 958             var = str;
 959             str = get_index(var + 1, &ndx);
 960             if (ndx == -1)
 961                 continue;
 962
 963             if (*var == 'l' && mdefs->layout[ndx] && *mdefs->layout[ndx]) {
 964                 if (pfx)
 965                     *outstr++ = pfx;
 966
 967                 strcpy(outstr, mdefs->layout[ndx]);
 968                 outstr += strlen(mdefs->layout[ndx]);
 969
 970                 if (sfx)
 971                     *outstr++ = sfx;
 972             }
 973             else if (*var == 'm' && mdefs->model) {
 974                 if (pfx)
 975                     *outstr++ = pfx;
 976
 977                 strcpy(outstr, mdefs->model);
 978                 outstr += strlen(mdefs->model);
 979
 980                 if (sfx)
 981                     *outstr++ = sfx;
 982             }
 983             else if (*var == 'v' && mdefs->variant[ndx] && *mdefs->variant[ndx]) {
 984                 if (pfx)
 985                     *outstr++ = pfx;
 986
 987                 strcpy(outstr, mdefs->variant[ndx]);
 988                 outstr += strlen(mdefs->variant[ndx]);
 989
 990                 if (sfx)
 991                     *outstr++ = sfx;
 992             }
 993
 994             if (pfx == '(' && *str == ')')
 995                 str++;
 996         }
 997         else {
 998             *outstr++= *str++;
 999         }
1000     }
1001
1002     *outstr++= '\0';
1003
1004     if (orig != name)
1005         free(orig);
1006
1007     return name;
1008 }
1009
1010 /***====================================================================***/
1011
1012 static bool
1013 get_components(struct rules *rules, struct var_defs *defs,
1014                struct xkb_component_names *kccgst)
1015 {
1016     struct multi_defs mdefs;
1017
1018     make_multi_defs(&mdefs, defs);
1019
1020     clear_partial_matches(rules);
1021
1022     apply_matching_rules(rules, &mdefs, kccgst, RULE_FLAG_NORMAL);
1023     apply_partial_matches(rules, kccgst);
1024
1025     apply_matching_rules(rules, &mdefs, kccgst, RULE_FLAG_APPEND);
1026     apply_partial_matches(rules, kccgst);
1027
1028     apply_matching_rules(rules, &mdefs, kccgst, RULE_FLAG_OPTION);
1029     apply_partial_matches(rules, kccgst);
1030
1031     kccgst->keycodes = substitute_vars(kccgst->keycodes, &mdefs);
1032     kccgst->symbols = substitute_vars(kccgst->symbols, &mdefs);
1033     kccgst->types = substitute_vars(kccgst->types, &mdefs);
1034     kccgst->compat = substitute_vars(kccgst->compat, &mdefs);
1035     kccgst->keymap = substitute_vars(kccgst->keymap, &mdefs);
1036
1037     free_multi_defs(&mdefs);
1038
1039     return (kccgst->keycodes && kccgst->symbols && kccgst->types &&
1040             kccgst->compat) || kccgst->keymap;
1041 }
1042
1043 static struct rule *
1044 add_rule(struct rules *rules)
1045 {
1046     if (rules->sz_rules < 1) {
1047         rules->sz_rules = 16;
1048         rules->num_rules = 0;
1049         rules->rules = calloc(rules->sz_rules, sizeof(*rules->rules));
1050     }
1051     else if (rules->num_rules >= rules->sz_rules) {
1052         rules->sz_rules *= 2;
1053         rules->rules = realloc(rules->rules,
1054                                rules->sz_rules * sizeof(*rules->rules));
1055     }
1056
1057     if (!rules->rules) {
1058         rules->sz_rules = rules->num_rules = 0;
1059         return NULL;
1060     }
1061
1062     memset(&rules->rules[rules->num_rules], 0, sizeof(*rules->rules));
1063     return &rules->rules[rules->num_rules++];
1064 }
1065
1066 static struct group *
1067 add_group(struct rules *rules)
1068 {
1069     if (rules->sz_groups < 1) {
1070         rules->sz_groups = 16;
1071         rules->num_groups = 0;
1072         rules->groups = calloc(rules->sz_groups, sizeof(*rules->groups));
1073     }
1074     else if (rules->num_groups >= rules->sz_groups) {
1075         rules->sz_groups *= 2;
1076         rules->groups = realloc(rules->groups,
1077                                 rules->sz_groups * sizeof(*rules->groups));
1078     }
1079
1080     if (!rules->groups) {
1081         rules->sz_groups = rules->num_groups = 0;
1082         return NULL;
1083     }
1084
1085     memset(&rules->groups[rules->num_groups], 0, sizeof(*rules->groups));
1086     return &rules->groups[rules->num_groups++];
1087 }
1088
1089 static struct rules *
1090 load_rules(FILE *file)
1091 {
1092     struct input_line line;
1093     struct mapping mapping;
1094     struct rule trule, *rule;
1095     struct group tgroup, *group;
1096     struct rules *rules;
1097
1098     rules = calloc(1, sizeof(*rules));
1099     if (!rules)
1100         return NULL;
1101
1102     memset(&mapping, 0, sizeof(mapping));
1103     memset(&tgroup, 0, sizeof(tgroup));
1104     input_line_init(&line);
1105
1106     while (input_line_get(file, &line)) {
1107         if (match_line(&line, &mapping, &trule, &tgroup)) {
1108             if (tgroup.number) {
1109                 group = add_group(rules);
1110                 if (group) {
1111                     *group = tgroup;
1112                     memset(&tgroup, 0, sizeof(tgroup));
1113                 }
1114             } else {
1115                 rule = add_rule(rules);
1116                 if (rule) {
1117                     *rule = trule;
1118                     memset(&trule, 0, sizeof(trule));
1119                 }
1120             }
1121         }
1122
1123         line.offset = 0;
1124     }
1125
1126     input_line_deinit(&line);
1127     return rules;
1128 }
1129
1130 static void
1131 free_rules(struct rules *rules)
1132 {
1133     int i;
1134     struct rule *rule;
1135     struct group *group;
1136
1137     if (!rules)
1138         return;
1139
1140     for (i = 0; i < rules->num_rules; i++) {
1141         rule = &rules->rules[i];
1142
1143         free(rule->model);
1144         free(rule->layout);
1145         free(rule->variant);
1146         free(rule->option);
1147         free(rule->keycodes);
1148         free(rule->symbols);
1149         free(rule->types);
1150         free(rule->compat);
1151         free(rule->keymap);
1152     }
1153     free(rules->rules);
1154
1155     for (i = 0; i < rules->num_groups; i++) {
1156         group = &rules->groups[i];
1157
1158         free(group->name);
1159         free(group->words);
1160     }
1161     free(rules->groups);
1162
1163     free(rules);
1164 }
1165
1166 struct xkb_component_names *
1167 xkb_components_from_rules(struct xkb_context *ctx,
1168                           const struct xkb_rule_names *rmlvo)
1169 {
1170     int i;
1171     FILE *rulesFile;
1172     char *rulesPath;
1173     struct rules *loaded;
1174     struct xkb_component_names *names = NULL;
1175     struct var_defs defs = {
1176         .model = rmlvo->model,
1177         .layout = rmlvo->layout,
1178         .variant = rmlvo->variant,
1179         .options = rmlvo->options,
1180     };
1181
1182     rulesFile = XkbFindFileInPath(ctx, rmlvo->rules, XkmRulesFile,
1183                                   &rulesPath);
1184     if (!rulesFile) {
1185         ERROR("could not find \"%s\" rules in XKB path\n", rmlvo->rules);
1186         ERROR("%d include paths searched:\n",
1187               xkb_context_num_include_paths(ctx));
1188         for (i = 0; i < xkb_context_num_include_paths(ctx); i++)
1189             ERROR("\t%s\n", xkb_context_include_path_get(ctx, i));
1190         return NULL;
1191     }
1192
1193     loaded = load_rules(rulesFile);
1194     if (!loaded) {
1195         ERROR("failed to load XKB rules \"%s\"\n", rulesPath);
1196         goto unwind_file;
1197     }
1198
1199     names = calloc(1, sizeof(*names));
1200     if (!names) {
1201         ERROR("failed to allocate XKB components\n");
1202         goto unwind_file;
1203     }
1204
1205     if (!get_components(loaded, &defs, names)) {
1206         free(names->keymap);
1207         free(names->keycodes);
1208         free(names->types);
1209         free(names->compat);
1210         free(names->symbols);
1211         free(names);
1212         names = NULL;
1213         ERROR("no components returned from XKB rules \"%s\"\n", rulesPath);
1214     }
1215
1216 unwind_file:
1217     free_rules(loaded);
1218     if (rulesFile)
1219         fclose(rulesFile);
1220     free(rulesPath);
1221     return names;
1222 }