src/xkbcomp/symbols.c

   1 /************************************************************
   2  * Copyright (c) 1994 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 Intel Corporation
  29  * Copyright © 2012 Ran Benita <ran234@gmail.com>
  30  *
  31  * Permission is hereby granted, free of charge, to any person obtaining a
  32  * copy of this software and associated documentation files (the "Software"),
  33  * to deal in the Software without restriction, including without limitation
  34  * the rights to use, copy, modify, merge, publish, distribute, sublicense,
  35  * and/or sell copies of the Software, and to permit persons to whom the
  36  * Software is furnished to do so, subject to the following conditions:
  37  *
  38  * The above copyright notice and this permission notice (including the next
  39  * paragraph) shall be included in all copies or substantial portions of the
  40  * Software.
  41  *
  42  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  43  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  44  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.  IN NO EVENT SHALL
  45  * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  46  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  47  * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
  48  * DEALINGS IN THE SOFTWARE.
  49  *
  50  * Author: Daniel Stone <daniel@fooishbar.org>
  51  *         Ran Benita <ran234@gmail.com>
  52  */
  53
  54 #include "xkbcomp-priv.h"
  55 #include "text.h"
  56 #include "expr.h"
  57 #include "action.h"
  58 #include "vmod.h"
  59 #include "keycodes.h"
  60 #include "include.h"
  61 #include "keysym.h"
  62
  63 enum key_repeat {
  64     KEY_REPEAT_UNDEFINED = 0,
  65     KEY_REPEAT_YES = 1,
  66     KEY_REPEAT_NO = 2,
  67 };
  68
  69 enum group_field {
  70     GROUP_FIELD_SYMS = (1 << 0),
  71     GROUP_FIELD_ACTS = (1 << 1),
  72     GROUP_FIELD_TYPE = (1 << 2),
  73 };
  74
  75 enum key_field {
  76     KEY_FIELD_REPEAT    = (1 << 0),
  77     KEY_FIELD_TYPE_DFLT = (1 << 1),
  78     KEY_FIELD_GROUPINFO = (1 << 2),
  79     KEY_FIELD_VMODMAP   = (1 << 3),
  80 };
  81
  82 typedef struct {
  83     enum group_field defined;
  84     darray(struct xkb_level) levels;
  85     xkb_atom_t type;
  86 } GroupInfo;
  87
  88 typedef struct _KeyInfo {
  89     enum key_field defined;
  90     unsigned file_id;
  91     enum merge_mode merge;
  92
  93     unsigned long name; /* the 4 chars of the key name, as long */
  94
  95     darray(GroupInfo) groups;
  96
  97     enum key_repeat repeat;
  98     xkb_mod_mask_t vmodmap;
  99     xkb_atom_t dfltType;
 100
 101     enum xkb_range_exceed_type out_of_range_group_action;
 102     xkb_layout_index_t out_of_range_group_number;
 103 } KeyInfo;
 104
 105 static void
 106 ClearLevelInfo(struct xkb_level *leveli)
 107 {
 108     if (leveli->num_syms > 1)
 109         free(leveli->u.syms);
 110 }
 111
 112 static void
 113 InitGroupInfo(GroupInfo *groupi)
 114 {
 115     memset(groupi, 0, sizeof(*groupi));
 116 }
 117
 118 static void
 119 ClearGroupInfo(GroupInfo *groupi)
 120 {
 121     struct xkb_level *leveli;
 122     darray_foreach(leveli, groupi->levels)
 123         ClearLevelInfo(leveli);
 124     darray_free(groupi->levels);
 125 }
 126
 127 static void
 128 CopyGroupInfo(GroupInfo *to, const GroupInfo *from)
 129 {
 130     xkb_level_index_t j;
 131     to->defined = from->defined;
 132     to->type = from->type;
 133     darray_init(to->levels);
 134     darray_copy(to->levels, from->levels);
 135     for (j = 0; j < darray_size(to->levels); j++)
 136         if (darray_item(from->levels, j).num_syms > 1)
 137             darray_item(to->levels, j).u.syms =
 138                 memdup(darray_item(from->levels, j).u.syms,
 139                        darray_item(from->levels, j).num_syms,
 140                        sizeof(xkb_keysym_t));
 141 }
 142
 143 static void
 144 InitKeyInfo(KeyInfo *keyi, unsigned file_id)
 145 {
 146     static const char dflt_key_name[XKB_KEY_NAME_LENGTH] = "*";
 147
 148     memset(keyi, 0, sizeof(*keyi));
 149     keyi->file_id = file_id;
 150     keyi->merge = MERGE_OVERRIDE;
 151     keyi->name = KeyNameToLong(dflt_key_name);
 152     keyi->out_of_range_group_action = RANGE_WRAP;
 153 }
 154
 155 static void
 156 ClearKeyInfo(KeyInfo *keyi)
 157 {
 158     GroupInfo *groupi;
 159     darray_foreach(groupi, keyi->groups)
 160         ClearGroupInfo(groupi);
 161     darray_free(keyi->groups);
 162 }
 163
 164 /***====================================================================***/
 165
 166 typedef struct _ModMapEntry {
 167     enum merge_mode merge;
 168     bool haveSymbol;
 169     int modifier;
 170     union {
 171         unsigned long keyName;
 172         xkb_keysym_t keySym;
 173     } u;
 174 } ModMapEntry;
 175
 176 typedef struct _SymbolsInfo {
 177     char *name;         /* e.g. pc+us+inet(evdev) */
 178     int errorCount;
 179     unsigned file_id;
 180     enum merge_mode merge;
 181     xkb_layout_index_t explicit_group;
 182     darray(KeyInfo) keys;
 183     KeyInfo dflt;
 184     VModInfo vmods;
 185     ActionsInfo *actions;
 186     darray_xkb_atom_t group_names;
 187     darray(ModMapEntry) modMaps;
 188
 189     struct xkb_keymap *keymap;
 190 } SymbolsInfo;
 191
 192 static void
 193 InitSymbolsInfo(SymbolsInfo *info, struct xkb_keymap *keymap,
 194                 unsigned file_id, ActionsInfo *actions)
 195 {
 196     memset(info, 0, sizeof(*info));
 197     info->keymap = keymap;
 198     info->file_id = file_id;
 199     info->merge = MERGE_OVERRIDE;
 200     InitKeyInfo(&info->dflt, file_id);
 201     InitVModInfo(&info->vmods, keymap);
 202     info->actions = actions;
 203     info->explicit_group = XKB_LAYOUT_INVALID;
 204 }
 205
 206 static void
 207 ClearSymbolsInfo(SymbolsInfo * info)
 208 {
 209     KeyInfo *keyi;
 210     free(info->name);
 211     darray_foreach(keyi, info->keys)
 212         ClearKeyInfo(keyi);
 213     darray_free(info->keys);
 214     darray_free(info->group_names);
 215     darray_free(info->modMaps);
 216     ClearKeyInfo(&info->dflt);
 217 }
 218
 219 static bool
 220 MergeGroups(SymbolsInfo *info, GroupInfo *into, GroupInfo *from, bool clobber,
 221             bool report, xkb_layout_index_t group, unsigned long key_name)
 222 {
 223     xkb_level_index_t i, levels_in_both;
 224
 225     /* First find the type of the merged group. */
 226     if (into->type != from->type) {
 227         if (from->type == XKB_ATOM_NONE) {
 228         }
 229         else if (into->type == XKB_ATOM_NONE) {
 230             into->type = from->type;
 231         }
 232         else {
 233             xkb_atom_t use = (clobber ? from->type : into->type);
 234             xkb_atom_t ignore = (clobber ? into->type : from->type);
 235
 236             if (report)
 237                 log_warn(info->keymap->ctx,
 238                          "Multiple definitions for group %d type of key %s; "
 239                          "Using %s, ignoring %s\n",
 240                          group + 1, LongKeyNameText(key_name),
 241                          xkb_atom_text(info->keymap->ctx, use),
 242                          xkb_atom_text(info->keymap->ctx, ignore));
 243
 244             into->type = use;
 245         }
 246     }
 247     into->defined |= (from->defined & GROUP_FIELD_TYPE);
 248
 249     /* Now look at the levels. */
 250
 251     if (darray_empty(from->levels)) {
 252         InitGroupInfo(from);
 253         return true;
 254     }
 255
 256     if (darray_empty(into->levels)) {
 257         from->type = into->type;
 258         *into = *from;
 259         InitGroupInfo(from);
 260         return true;
 261     }
 262
 263     /* Merge the actions and syms. */
 264     levels_in_both = MIN(darray_size(into->levels), darray_size(from->levels));
 265     for (i = 0; i < levels_in_both; i++) {
 266         struct xkb_level *intoLevel = &darray_item(into->levels, i);
 267         struct xkb_level *fromLevel = &darray_item(from->levels, i);
 268
 269         if (fromLevel->action.type == ACTION_TYPE_NONE) {
 270         }
 271         else if (intoLevel->action.type == ACTION_TYPE_NONE) {
 272             intoLevel->action = fromLevel->action;
 273         }
 274         else {
 275             union xkb_action *use, *ignore;
 276             use = (clobber ? &fromLevel->action : &intoLevel->action);
 277             ignore = (clobber ? &intoLevel->action : &fromLevel->action);
 278
 279             if (report)
 280                 log_warn(info->keymap->ctx,
 281                          "Multiple actions for level %d/group %u on key %s; "
 282                          "Using %s, ignoring %s\n",
 283                          i + 1, group + 1, LongKeyNameText(key_name),
 284                          ActionTypeText(use->type),
 285                          ActionTypeText(ignore->type));
 286
 287             intoLevel->action = *use;
 288         }
 289
 290         if (fromLevel->num_syms == 0) {
 291         }
 292         else if (intoLevel->num_syms == 0) {
 293             intoLevel->num_syms = fromLevel->num_syms;
 294             if (fromLevel->num_syms > 1)
 295                 intoLevel->u.syms = fromLevel->u.syms;
 296             else
 297                 intoLevel->u.sym = fromLevel->u.sym;
 298             fromLevel->num_syms = 0;
 299         }
 300         else {
 301             if (report)
 302                 log_warn(info->keymap->ctx,
 303                          "Multiple symbols for level %d/group %u on key %s; "
 304                          "Using %s, ignoring %s\n",
 305                          i + 1, group + 1, LongKeyNameText(key_name),
 306                          (clobber ? "from" : "to"),
 307                          (clobber ? "to" : "from"));
 308
 309             if (clobber) {
 310                 ClearLevelInfo(intoLevel);
 311                 intoLevel->num_syms = fromLevel->num_syms;
 312                 if (fromLevel->num_syms > 1)
 313                     intoLevel->u.syms = fromLevel->u.syms;
 314                 else
 315                     intoLevel->u.sym = fromLevel->u.sym;
 316                 fromLevel->num_syms = 0;
 317             }
 318         }
 319     }
 320     /* If @from has extra levels, get them as well. */
 321     for (i = levels_in_both; i < darray_size(from->levels); i++) {
 322         darray_append(into->levels, darray_item(from->levels, i));
 323         darray_item(from->levels, i).num_syms = 0;
 324     }
 325     into->defined |= (from->defined & GROUP_FIELD_ACTS);
 326     into->defined |= (from->defined & GROUP_FIELD_SYMS);
 327
 328     return true;
 329 }
 330
 331 static bool
 332 UseNewKeyField(enum key_field field, enum key_field old, enum key_field new,
 333                bool clobber, bool report, enum key_field *collide)
 334 {
 335     if (!(old & field))
 336         return (new & field);
 337
 338     if (new & field) {
 339         if (report)
 340             *collide |= field;
 341
 342         if (clobber)
 343             return true;
 344     }
 345
 346     return false;
 347 }
 348
 349 static bool
 350 MergeKeys(SymbolsInfo *info, KeyInfo *into, KeyInfo *from)
 351 {
 352     xkb_layout_index_t i;
 353     xkb_layout_index_t groups_in_both;
 354     enum key_field collide = 0;
 355     bool clobber, report;
 356     int verbosity = xkb_context_get_log_verbosity(info->keymap->ctx);
 357
 358     if (from->merge == MERGE_REPLACE) {
 359         ClearKeyInfo(into);
 360         *into = *from;
 361         InitKeyInfo(from, info->file_id);
 362         return true;
 363     }
 364
 365     clobber = (from->merge != MERGE_AUGMENT);
 366     report = (verbosity > 9 ||
 367               (into->file_id == from->file_id && verbosity > 0));
 368
 369     groups_in_both = MIN(darray_size(into->groups),
 370                          darray_size(from->groups));
 371     for (i = 0; i < groups_in_both; i++)
 372         MergeGroups(info,
 373                     &darray_item(into->groups, i),
 374                     &darray_item(from->groups, i),
 375                     clobber, report, i, into->name);
 376     /* If @from has extra groups, just move them to @into. */
 377     for (i = groups_in_both; i < darray_size(from->groups); i++) {
 378         darray_append(into->groups, darray_item(from->groups, i));
 379         InitGroupInfo(&darray_item(from->groups, i));
 380     }
 381
 382     if (UseNewKeyField(KEY_FIELD_VMODMAP, into->defined, from->defined,
 383                        clobber, report, &collide)) {
 384         into->vmodmap = from->vmodmap;
 385         into->defined |= KEY_FIELD_VMODMAP;
 386     }
 387     if (UseNewKeyField(KEY_FIELD_REPEAT, into->defined, from->defined,
 388                        clobber, report, &collide)) {
 389         into->repeat = from->repeat;
 390         into->defined |= KEY_FIELD_REPEAT;
 391     }
 392     if (UseNewKeyField(KEY_FIELD_TYPE_DFLT, into->defined, from->defined,
 393                        clobber, report, &collide)) {
 394         into->dfltType = from->dfltType;
 395         into->defined |= KEY_FIELD_TYPE_DFLT;
 396     }
 397     if (UseNewKeyField(KEY_FIELD_GROUPINFO, into->defined, from->defined,
 398                        clobber, report, &collide)) {
 399         into->out_of_range_group_action = from->out_of_range_group_action;
 400         into->out_of_range_group_number = from->out_of_range_group_number;
 401         into->defined |= KEY_FIELD_GROUPINFO;
 402     }
 403
 404     if (collide)
 405         log_warn(info->keymap->ctx,
 406                  "Symbol map for key %s redefined; "
 407                  "Using %s definition for conflicting fields\n",
 408                  LongKeyNameText(into->name),
 409                  (clobber ? "first" : "last"));
 410
 411     ClearKeyInfo(from);
 412     InitKeyInfo(from, info->file_id);
 413     return true;
 414 }
 415
 416 static bool
 417 AddKeySymbols(SymbolsInfo *info, KeyInfo *keyi)
 418 {
 419     unsigned long real_name;
 420     KeyInfo *iter;
 421
 422     /*
 423      * Don't keep aliases in the keys array; this guarantees that
 424      * searching for keys to merge with by straight comparison (see the
 425      * following loop) is enough, and we won't get multiple KeyInfo's
 426      * for the same key because of aliases.
 427      */
 428     if (FindKeyNameForAlias(info->keymap, keyi->name, &real_name))
 429         keyi->name = real_name;
 430
 431     darray_foreach(iter, info->keys)
 432         if (iter->name == keyi->name)
 433             return MergeKeys(info, iter, keyi);
 434
 435     darray_append(info->keys, *keyi);
 436     InitKeyInfo(keyi, info->file_id);
 437     return true;
 438 }
 439
 440 static bool
 441 AddModMapEntry(SymbolsInfo * info, ModMapEntry * new)
 442 {
 443     ModMapEntry *mm;
 444     bool clobber;
 445
 446     clobber = (new->merge != MERGE_AUGMENT);
 447     darray_foreach(mm, info->modMaps) {
 448         if (new->haveSymbol && mm->haveSymbol
 449             && (new->u.keySym == mm->u.keySym)) {
 450             unsigned use, ignore;
 451             if (mm->modifier != new->modifier) {
 452                 if (clobber) {
 453                     use = new->modifier;
 454                     ignore = mm->modifier;
 455                 }
 456                 else {
 457                     use = mm->modifier;
 458                     ignore = new->modifier;
 459                 }
 460                 log_err(info->keymap->ctx,
 461                         "%s added to symbol map for multiple modifiers; "
 462                         "Using %s, ignoring %s.\n",
 463                         KeysymText(new->u.keySym), ModIndexText(use),
 464                         ModIndexText(ignore));
 465                 mm->modifier = use;
 466             }
 467             return true;
 468         }
 469         if ((!new->haveSymbol) && (!mm->haveSymbol) &&
 470             (new->u.keyName == mm->u.keyName)) {
 471             unsigned use, ignore;
 472             if (mm->modifier != new->modifier) {
 473                 if (clobber) {
 474                     use = new->modifier;
 475                     ignore = mm->modifier;
 476                 }
 477                 else {
 478                     use = mm->modifier;
 479                     ignore = new->modifier;
 480                 }
 481                 log_err(info->keymap->ctx,
 482                         "Key %s added to map for multiple modifiers; "
 483                         "Using %s, ignoring %s.\n",
 484                         LongKeyNameText(new->u.keyName), ModIndexText(use),
 485                         ModIndexText(ignore));
 486                 mm->modifier = use;
 487             }
 488             return true;
 489         }
 490     }
 491
 492     darray_append(info->modMaps, *new);
 493     return true;
 494 }
 495
 496 /***====================================================================***/
 497
 498 static void
 499 MergeIncludedSymbols(SymbolsInfo *into, SymbolsInfo *from,
 500                      enum merge_mode merge)
 501 {
 502     unsigned int i;
 503     KeyInfo *keyi;
 504     ModMapEntry *mm;
 505     xkb_atom_t *group_name;
 506     xkb_layout_index_t group_names_in_both;
 507
 508     if (from->errorCount > 0) {
 509         into->errorCount += from->errorCount;
 510         return;
 511     }
 512
 513     if (into->name == NULL) {
 514         into->name = from->name;
 515         from->name = NULL;
 516     }
 517
 518     group_names_in_both = MIN(darray_size(into->group_names),
 519                               darray_size(from->group_names));
 520     for (i = 0; i < group_names_in_both; i++) {
 521         if (!darray_item(from->group_names, i))
 522             continue;
 523
 524         if (merge == MERGE_AUGMENT && darray_item(into->group_names, i))
 525             continue;
 526
 527         darray_item(into->group_names, i) = darray_item(from->group_names, i);
 528     }
 529     /* If @from has more, get them as well. */
 530     darray_foreach_from(group_name, from->group_names, group_names_in_both)
 531         darray_append(into->group_names, *group_name);
 532
 533     darray_foreach(keyi, from->keys) {
 534         merge = (merge == MERGE_DEFAULT ? keyi->merge : merge);
 535         if (!AddKeySymbols(into, keyi))
 536             into->errorCount++;
 537     }
 538
 539     darray_foreach(mm, from->modMaps) {
 540         mm->merge = (merge == MERGE_DEFAULT ? mm->merge : merge);
 541         if (!AddModMapEntry(into, mm))
 542             into->errorCount++;
 543     }
 544 }
 545
 546 static void
 547 HandleSymbolsFile(SymbolsInfo *info, XkbFile *file, enum merge_mode merge);
 548
 549 static bool
 550 HandleIncludeSymbols(SymbolsInfo *info, IncludeStmt *stmt)
 551 {
 552     enum merge_mode merge = MERGE_DEFAULT;
 553     XkbFile *rtrn;
 554     SymbolsInfo included, next_incl;
 555
 556     InitSymbolsInfo(&included, info->keymap, info->file_id, info->actions);
 557     if (stmt->stmt) {
 558         free(included.name);
 559         included.name = stmt->stmt;
 560         stmt->stmt = NULL;
 561     }
 562
 563     for (; stmt; stmt = stmt->next_incl) {
 564         if (!ProcessIncludeFile(info->keymap->ctx, stmt, FILE_TYPE_SYMBOLS,
 565                                 &rtrn, &merge)) {
 566             info->errorCount += 10;
 567             ClearSymbolsInfo(&included);
 568             return false;
 569         }
 570
 571         InitSymbolsInfo(&next_incl, info->keymap, rtrn->id, info->actions);
 572         next_incl.merge = next_incl.dflt.merge = MERGE_OVERRIDE;
 573         if (stmt->modifier) {
 574             next_incl.explicit_group = atoi(stmt->modifier) - 1;
 575             if (next_incl.explicit_group >= XKB_NUM_GROUPS) {
 576                 log_err(info->keymap->ctx,
 577                         "Cannot set explicit group to %d - must be between 1..%d; "
 578                         "Ignoring group number\n",
 579                         next_incl.explicit_group + 1, XKB_NUM_GROUPS);
 580                 next_incl.explicit_group = info->explicit_group;
 581             }
 582         }
 583         else {
 584             next_incl.explicit_group = info->explicit_group;
 585         }
 586
 587         HandleSymbolsFile(&next_incl, rtrn, MERGE_OVERRIDE);
 588
 589         MergeIncludedSymbols(&included, &next_incl, merge);
 590
 591         ClearSymbolsInfo(&next_incl);
 592         FreeXkbFile(rtrn);
 593     }
 594
 595     MergeIncludedSymbols(info, &included, merge);
 596     ClearSymbolsInfo(&included);
 597
 598     return (info->errorCount == 0);
 599 }
 600
 601 #define SYMBOLS 1
 602 #define ACTIONS 2
 603
 604 static bool
 605 GetGroupIndex(SymbolsInfo *info, KeyInfo *keyi, ExprDef *arrayNdx,
 606               unsigned what, xkb_layout_index_t *ndx_rtrn)
 607 {
 608     const char *name = (what == SYMBOLS ? "symbols" : "actions");
 609
 610     if (arrayNdx == NULL) {
 611         xkb_layout_index_t i;
 612         GroupInfo *groupi;
 613         enum group_field field = (what == SYMBOLS ?
 614                                   GROUP_FIELD_SYMS : GROUP_FIELD_ACTS);
 615
 616         darray_enumerate(i, groupi, keyi->groups) {
 617             if (!(groupi->defined & field)) {
 618                 *ndx_rtrn = i;
 619                 return true;
 620             }
 621         }
 622
 623         if (i >= XKB_NUM_GROUPS) {
 624             log_err(info->keymap->ctx,
 625                     "Too many groups of %s for key %s (max %u); "
 626                     "Ignoring %s defined for extra groups\n",
 627                     name, LongKeyNameText(keyi->name), XKB_NUM_GROUPS + 1, name);
 628             return false;
 629         }
 630
 631         darray_resize0(keyi->groups, darray_size(keyi->groups) + 1);
 632         *ndx_rtrn = darray_size(keyi->groups) - 1;
 633         return true;
 634     }
 635
 636     if (!ExprResolveGroup(info->keymap->ctx, arrayNdx, ndx_rtrn)) {
 637         log_err(info->keymap->ctx,
 638                 "Illegal group index for %s of key %s\n"
 639                 "Definition with non-integer array index ignored\n",
 640                 name, LongKeyNameText(keyi->name));
 641         return false;
 642     }
 643
 644     (*ndx_rtrn)--;
 645     if (*ndx_rtrn >= darray_size(keyi->groups))
 646         darray_resize0(keyi->groups, *ndx_rtrn + 1);
 647
 648     return true;
 649 }
 650
 651 bool
 652 LookupKeysym(const char *str, xkb_keysym_t *sym_rtrn)
 653 {
 654     xkb_keysym_t sym;
 655
 656     if (!str || istreq(str, "any") || istreq(str, "nosymbol")) {
 657         *sym_rtrn = XKB_KEY_NoSymbol;
 658         return 1;
 659     }
 660
 661     if (istreq(str, "none") || istreq(str, "voidsymbol")) {
 662         *sym_rtrn = XKB_KEY_VoidSymbol;
 663         return 1;
 664     }
 665
 666     sym = xkb_keysym_from_name(str);
 667     if (sym != XKB_KEY_NoSymbol) {
 668         *sym_rtrn = sym;
 669         return 1;
 670     }
 671
 672     return 0;
 673 }
 674
 675 static bool
 676 AddSymbolsToKey(SymbolsInfo *info, KeyInfo *keyi, ExprDef *arrayNdx,
 677                 ExprDef *value)
 678 {
 679     xkb_layout_index_t ndx;
 680     GroupInfo *groupi;
 681     xkb_level_index_t nLevels;
 682     xkb_level_index_t i;
 683     int j;
 684
 685     if (!GetGroupIndex(info, keyi, arrayNdx, SYMBOLS, &ndx))
 686         return false;
 687
 688     groupi = &darray_item(keyi->groups, ndx);
 689
 690     if (value == NULL) {
 691         groupi->defined |= GROUP_FIELD_SYMS;
 692         return true;
 693     }
 694
 695     if (value->op != EXPR_KEYSYM_LIST) {
 696         log_err(info->keymap->ctx,
 697                 "Expected a list of symbols, found %s; "
 698                 "Ignoring symbols for group %u of %s\n",
 699                 expr_op_type_to_string(value->op), ndx + 1,
 700                 LongKeyNameText(keyi->name));
 701         return false;
 702     }
 703
 704     if (groupi->defined & GROUP_FIELD_SYMS) {
 705         log_err(info->keymap->ctx,
 706                 "Symbols for key %s, group %u already defined; "
 707                 "Ignoring duplicate definition\n",
 708                 LongKeyNameText(keyi->name), ndx + 1);
 709         return false;
 710     }
 711
 712     nLevels = darray_size(value->value.list.symsMapIndex);
 713     if (darray_size(groupi->levels) < nLevels)
 714         darray_resize0(groupi->levels, nLevels);
 715
 716     groupi->defined |= GROUP_FIELD_SYMS;
 717
 718     for (i = 0; i < nLevels; i++) {
 719         unsigned int sym_index;
 720         struct xkb_level *leveli = &darray_item(groupi->levels, i);
 721
 722         sym_index = darray_item(value->value.list.symsMapIndex, i);
 723         leveli->num_syms = darray_item(value->value.list.symsNumEntries, i);
 724         if (leveli->num_syms > 1)
 725             leveli->u.syms = calloc(leveli->num_syms, sizeof(*leveli->u.syms));
 726
 727         for (j = 0; j < leveli->num_syms; j++) {
 728             char *sym_name = darray_item(value->value.list.syms,
 729                                          sym_index + j);
 730             xkb_keysym_t keysym;
 731
 732             if (!LookupKeysym(sym_name, &keysym)) {
 733                 const char *group_name = "unnamed";
 734
 735                 if (ndx < darray_size(info->group_names) &&
 736                     darray_item(info->group_names, ndx))
 737                     group_name = xkb_atom_text(info->keymap->ctx,
 738                                                darray_item(info->group_names,
 739                                                            ndx));
 740
 741                 log_warn(info->keymap->ctx,
 742                          "Could not resolve keysym %s for key %s, group %u (%s), level %u\n",
 743                          sym_name, LongKeyNameText(keyi->name), ndx + 1,
 744                          group_name, i);
 745
 746                 ClearLevelInfo(leveli);
 747                 leveli->num_syms = 0;
 748                 break;
 749             }
 750
 751             if (leveli->num_syms == 1) {
 752                 if (keysym == XKB_KEY_NoSymbol)
 753                     leveli->num_syms = 0;
 754                 else
 755                     leveli->u.sym = keysym;
 756             }
 757             else if (leveli->num_syms > 1) {
 758                 leveli->u.syms[j] = keysym;
 759             }
 760         }
 761     }
 762
 763     return true;
 764 }
 765
 766 static bool
 767 AddActionsToKey(SymbolsInfo *info, KeyInfo *keyi, ExprDef *arrayNdx,
 768                 ExprDef *value)
 769 {
 770     unsigned int i;
 771     xkb_layout_index_t ndx;
 772     GroupInfo *groupi;
 773     unsigned int nActs;
 774     ExprDef *act;
 775     union xkb_action *toAct;
 776
 777     if (!GetGroupIndex(info, keyi, arrayNdx, ACTIONS, &ndx))
 778         return false;
 779
 780     groupi = &darray_item(keyi->groups, ndx);
 781
 782     if (value == NULL) {
 783         groupi->defined |= GROUP_FIELD_ACTS;
 784         return true;
 785     }
 786
 787     if (value->op != EXPR_ACTION_LIST) {
 788         log_wsgo(info->keymap->ctx,
 789                  "Bad expression type (%d) for action list value; "
 790                  "Ignoring actions for group %u of %s\n",
 791                  value->op, ndx, LongKeyNameText(keyi->name));
 792         return false;
 793     }
 794
 795     if (groupi->defined & GROUP_FIELD_ACTS) {
 796         log_wsgo(info->keymap->ctx,
 797                  "Actions for key %s, group %u already defined\n",
 798                  LongKeyNameText(keyi->name), ndx);
 799         return false;
 800     }
 801
 802     nActs = 0;
 803     for (act = value->value.child; act; act = (ExprDef *) act->common.next)
 804         nActs++;
 805
 806     if (darray_size(groupi->levels) < nActs)
 807         darray_resize0(groupi->levels, nActs);
 808
 809     groupi->defined |= GROUP_FIELD_ACTS;
 810
 811     act = value->value.child;
 812     for (i = 0; i < nActs; i++) {
 813         toAct = &darray_item(groupi->levels, i).action;
 814
 815         if (!HandleActionDef(act, info->keymap, toAct, info->actions))
 816             log_err(info->keymap->ctx,
 817                     "Illegal action definition for %s; "
 818                     "Action for group %u/level %u ignored\n",
 819                     LongKeyNameText(keyi->name), ndx + 1, i + 1);
 820
 821         act = (ExprDef *) act->common.next;
 822     }
 823
 824     return true;
 825 }
 826
 827 static const LookupEntry repeatEntries[] = {
 828     { "true", KEY_REPEAT_YES },
 829     { "yes", KEY_REPEAT_YES },
 830     { "on", KEY_REPEAT_YES },
 831     { "false", KEY_REPEAT_NO },
 832     { "no", KEY_REPEAT_NO },
 833     { "off", KEY_REPEAT_NO },
 834     { "default", KEY_REPEAT_UNDEFINED },
 835     { NULL, 0 }
 836 };
 837
 838 static bool
 839 SetSymbolsField(SymbolsInfo *info, KeyInfo *keyi, const char *field,
 840                 ExprDef *arrayNdx, ExprDef *value)
 841 {
 842     bool ok = true;
 843     struct xkb_context *ctx = info->keymap->ctx;
 844
 845     if (istreq(field, "type")) {
 846         xkb_layout_index_t ndx;
 847         xkb_atom_t val;
 848
 849         if (!ExprResolveString(ctx, value, &val))
 850             log_vrb(ctx, 1,
 851                     "The type field of a key symbol map must be a string; "
 852                     "Ignoring illegal type definition\n");
 853
 854         if (arrayNdx == NULL) {
 855             keyi->dfltType = val;
 856             keyi->defined |= KEY_FIELD_TYPE_DFLT;
 857         }
 858         else if (!ExprResolveGroup(ctx, arrayNdx, &ndx)) {
 859             log_err(ctx,
 860                     "Illegal group index for type of key %s; "
 861                     "Definition with non-integer array index ignored\n",
 862                     LongKeyNameText(keyi->name));
 863             return false;
 864         }
 865         else {
 866             ndx--;
 867             if (ndx >= darray_size(keyi->groups))
 868                 darray_resize0(keyi->groups, ndx + 1);
 869             darray_item(keyi->groups, ndx).type = val;
 870             darray_item(keyi->groups, ndx).defined |= GROUP_FIELD_TYPE;
 871         }
 872     }
 873     else if (istreq(field, "symbols"))
 874         return AddSymbolsToKey(info, keyi, arrayNdx, value);
 875     else if (istreq(field, "actions"))
 876         return AddActionsToKey(info, keyi, arrayNdx, value);
 877     else if (istreq(field, "vmods") ||
 878              istreq(field, "virtualmods") ||
 879              istreq(field, "virtualmodifiers")) {
 880         xkb_mod_mask_t mask;
 881
 882         ok = ExprResolveVModMask(info->keymap, value, &mask);
 883         if (ok) {
 884             keyi->vmodmap = (mask >> XKB_NUM_CORE_MODS) & 0xffff;
 885             keyi->defined |= KEY_FIELD_VMODMAP;
 886         }
 887         else {
 888             log_err(info->keymap->ctx,
 889                     "Expected a virtual modifier mask, found %s; "
 890                     "Ignoring virtual modifiers definition for key %s\n",
 891                     expr_op_type_to_string(value->op),
 892                     LongKeyNameText(keyi->name));
 893         }
 894     }
 895     else if (istreq(field, "locking") ||
 896              istreq(field, "lock") ||
 897              istreq(field, "locks")) {
 898         log_err(info->keymap->ctx,
 899                 "Key behaviors not supported; "
 900                 "Ignoring locking specification for key %s\n",
 901                 LongKeyNameText(keyi->name));
 902     }
 903     else if (istreq(field, "radiogroup") ||
 904              istreq(field, "permanentradiogroup") ||
 905              istreq(field, "allownone")) {
 906         log_err(info->keymap->ctx,
 907                 "Radio groups not supported; "
 908                 "Ignoring radio group specification for key %s\n",
 909                 LongKeyNameText(keyi->name));
 910     }
 911     else if (istreq_prefix("overlay", field) ||
 912              istreq_prefix("permanentoverlay", field)) {
 913         log_err(info->keymap->ctx,
 914                 "Overlays not supported; "
 915                 "Ignoring overlay specification for key %s\n",
 916                 LongKeyNameText(keyi->name));
 917     }
 918     else if (istreq(field, "repeating") ||
 919              istreq(field, "repeats") ||
 920              istreq(field, "repeat")) {
 921         unsigned int val;
 922
 923         ok = ExprResolveEnum(ctx, value, &val, repeatEntries);
 924         if (!ok) {
 925             log_err(info->keymap->ctx,
 926                     "Illegal repeat setting for %s; "
 927                     "Non-boolean repeat setting ignored\n",
 928                     LongKeyNameText(keyi->name));
 929             return false;
 930         }
 931         keyi->repeat = val;
 932         keyi->defined |= KEY_FIELD_REPEAT;
 933     }
 934     else if (istreq(field, "groupswrap") ||
 935              istreq(field, "wrapgroups")) {
 936         bool set;
 937
 938         if (!ExprResolveBoolean(ctx, value, &set)) {
 939             log_err(info->keymap->ctx,
 940                     "Illegal groupsWrap setting for %s; "
 941                     "Non-boolean value ignored\n",
 942                     LongKeyNameText(keyi->name));
 943             return false;
 944         }
 945
 946         if (set)
 947             keyi->out_of_range_group_action = RANGE_WRAP;
 948         else
 949             keyi->out_of_range_group_action = RANGE_SATURATE;
 950
 951         keyi->defined |= KEY_FIELD_GROUPINFO;
 952     }
 953     else if (istreq(field, "groupsclamp") ||
 954              istreq(field, "clampgroups")) {
 955         bool set;
 956
 957         if (!ExprResolveBoolean(ctx, value, &set)) {
 958             log_err(info->keymap->ctx,
 959                     "Illegal groupsClamp setting for %s; "
 960                     "Non-boolean value ignored\n",
 961                     LongKeyNameText(keyi->name));
 962             return false;
 963         }
 964
 965         if (set)
 966             keyi->out_of_range_group_action = RANGE_SATURATE;
 967         else
 968             keyi->out_of_range_group_action = RANGE_WRAP;
 969
 970         keyi->defined |= KEY_FIELD_GROUPINFO;
 971     }
 972     else if (istreq(field, "groupsredirect") ||
 973              istreq(field, "redirectgroups")) {
 974         xkb_layout_index_t grp;
 975
 976         if (!ExprResolveGroup(ctx, value, &grp)) {
 977             log_err(info->keymap->ctx,
 978                     "Illegal group index for redirect of key %s; "
 979                     "Definition with non-integer group ignored\n",
 980                     LongKeyNameText(keyi->name));
 981             return false;
 982         }
 983
 984         keyi->out_of_range_group_action = RANGE_REDIRECT;
 985         keyi->out_of_range_group_number = grp - 1;
 986         keyi->defined |= KEY_FIELD_GROUPINFO;
 987     }
 988     else {
 989         log_err(info->keymap->ctx,
 990                 "Unknown field %s in a symbol interpretation; "
 991                 "Definition ignored\n",
 992                 field);
 993         ok = false;
 994     }
 995
 996     return ok;
 997 }
 998
 999 static int
1000 SetGroupName(SymbolsInfo *info, ExprDef *arrayNdx, ExprDef *value)
1001 {
1002     xkb_layout_index_t grp, grp_to_use;
1003     xkb_atom_t name;
1004
1005     if (!arrayNdx) {
1006         log_vrb(info->keymap->ctx, 1,
1007                 "You must specify an index when specifying a group name; "
1008                 "Group name definition without array subscript ignored\n");
1009         return false;
1010     }
1011
1012     if (!ExprResolveGroup(info->keymap->ctx, arrayNdx, &grp)) {
1013         log_err(info->keymap->ctx,
1014                 "Illegal index in group name definition; "
1015                 "Definition with non-integer array index ignored\n");
1016         return false;
1017     }
1018
1019     if (!ExprResolveString(info->keymap->ctx, value, &name)) {
1020         log_err(info->keymap->ctx,
1021                 "Group name must be a string; "
1022                 "Illegal name for group %d ignored\n", grp);
1023         return false;
1024     }
1025
1026     grp_to_use = XKB_LAYOUT_INVALID;
1027     if (info->explicit_group == XKB_LAYOUT_INVALID) {
1028         grp_to_use = grp - 1;
1029     }
1030     else if (grp - 1 == 0) {
1031         grp_to_use = info->explicit_group;
1032     }
1033     else {
1034         log_warn(info->keymap->ctx,
1035                  "An explicit group was specified for the '%s' map, "
1036                  "but it provides a name for a group other than Group1 (%d); "
1037                  "Ignoring group name '%s'\n",
1038                  info->name, grp,
1039                  xkb_atom_text(info->keymap->ctx, name));
1040         return false;
1041     }
1042
1043     if (grp_to_use >= darray_size(info->group_names))
1044         darray_resize0(info->group_names, grp_to_use + 1);
1045     darray_item(info->group_names, grp_to_use) = name;
1046     return true;
1047 }
1048
1049 static int
1050 HandleGlobalVar(SymbolsInfo *info, VarDef *stmt)
1051 {
1052     const char *elem, *field;
1053     ExprDef *arrayNdx;
1054     bool ret;
1055
1056     if (ExprResolveLhs(info->keymap->ctx, stmt->name, &elem, &field,
1057                        &arrayNdx) == 0)
1058         return 0;               /* internal error, already reported */
1059     if (elem && istreq(elem, "key")) {
1060         ret = SetSymbolsField(info, &info->dflt, field, arrayNdx,
1061                               stmt->value);
1062     }
1063     else if (!elem && (istreq(field, "name") ||
1064                        istreq(field, "groupname"))) {
1065         ret = SetGroupName(info, arrayNdx, stmt->value);
1066     }
1067     else if (!elem && (istreq(field, "groupswrap") ||
1068                        istreq(field, "wrapgroups"))) {
1069         log_err(info->keymap->ctx,
1070                 "Global \"groupswrap\" not supported; Ignored\n");
1071         ret = true;
1072     }
1073     else if (!elem && (istreq(field, "groupsclamp") ||
1074                        istreq(field, "clampgroups"))) {
1075         log_err(info->keymap->ctx,
1076                 "Global \"groupsclamp\" not supported; Ignored\n");
1077         ret = true;
1078     }
1079     else if (!elem && (istreq(field, "groupsredirect") ||
1080                        istreq(field, "redirectgroups"))) {
1081         log_err(info->keymap->ctx,
1082                 "Global \"groupsredirect\" not supported; Ignored\n");
1083         ret = true;
1084     }
1085     else if (!elem && istreq(field, "allownone")) {
1086         log_err(info->keymap->ctx,
1087                 "Radio groups not supported; "
1088                 "Ignoring \"allownone\" specification\n");
1089         ret = true;
1090     }
1091     else {
1092         ret = SetActionField(info->keymap, elem, field, arrayNdx, stmt->value,
1093                              info->actions);
1094     }
1095
1096     return ret;
1097 }
1098
1099 static bool
1100 HandleSymbolsBody(SymbolsInfo *info, VarDef *def, KeyInfo *keyi)
1101 {
1102     bool ok = true;
1103     const char *elem, *field;
1104     ExprDef *arrayNdx;
1105
1106     for (; def; def = (VarDef *) def->common.next) {
1107         if (def->name && def->name->op == EXPR_FIELD_REF) {
1108             log_err(info->keymap->ctx,
1109                     "Cannot set a global default value from within a key statement; "
1110                     "Move statements to the global file scope\n");
1111             continue;
1112         }
1113
1114         if (!def->name) {
1115             if (!def->value || def->value->op == EXPR_KEYSYM_LIST)
1116                 field = "symbols";
1117             else
1118                 field = "actions";
1119             arrayNdx = NULL;
1120         }
1121         else {
1122             ok = ExprResolveLhs(info->keymap->ctx, def->name, &elem, &field,
1123                                 &arrayNdx);
1124         }
1125
1126         if (ok)
1127             ok = SetSymbolsField(info, keyi, field, arrayNdx, def->value);
1128     }
1129
1130     return ok;
1131 }
1132
1133 static bool
1134 SetExplicitGroup(SymbolsInfo *info, KeyInfo *keyi)
1135 {
1136     xkb_layout_index_t i;
1137     GroupInfo *groupi;
1138     bool warn = false;
1139
1140     if (info->explicit_group == XKB_LAYOUT_INVALID)
1141         return true;
1142
1143     darray_enumerate_from(i, groupi, keyi->groups, 1) {
1144         if (groupi->defined) {
1145             warn = true;
1146             ClearGroupInfo(groupi);
1147             InitGroupInfo(groupi);
1148         }
1149     }
1150
1151     if (warn)
1152         log_warn(info->keymap->ctx,
1153                  "For the map %s an explicit group specified, "
1154                  "but key %s has more than one group defined; "
1155                  "All groups except first one will be ignored\n",
1156                  info->name, LongKeyNameText(keyi->name));
1157
1158     darray_resize0(keyi->groups, info->explicit_group + 1);
1159     if (info->explicit_group > 0) {
1160         darray_item(keyi->groups, info->explicit_group) =
1161             darray_item(keyi->groups, 0);
1162         InitGroupInfo(&darray_item(keyi->groups, 0));
1163     }
1164
1165     return true;
1166 }
1167
1168 static int
1169 HandleSymbolsDef(SymbolsInfo *info, SymbolsDef *stmt)
1170 {
1171     KeyInfo keyi;
1172     xkb_layout_index_t i;
1173
1174     keyi = info->dflt;
1175     darray_init(keyi.groups);
1176     darray_copy(keyi.groups, info->dflt.groups);
1177     for (i = 0; i < darray_size(keyi.groups); i++)
1178         CopyGroupInfo(&darray_item(keyi.groups, i),
1179                       &darray_item(info->dflt.groups, i));
1180     keyi.merge = stmt->merge;
1181     keyi.name = KeyNameToLong(stmt->keyName);
1182
1183     if (!HandleSymbolsBody(info, (VarDef *) stmt->symbols, &keyi)) {
1184         info->errorCount++;
1185         return false;
1186     }
1187
1188     if (!SetExplicitGroup(info, &keyi)) {
1189         info->errorCount++;
1190         return false;
1191     }
1192
1193     if (!AddKeySymbols(info, &keyi)) {
1194         info->errorCount++;
1195         return false;
1196     }
1197
1198     return true;
1199 }
1200
1201 static bool
1202 HandleModMapDef(SymbolsInfo *info, ModMapDef *def)
1203 {
1204     ExprDef *key;
1205     ModMapEntry tmp;
1206     xkb_mod_index_t ndx;
1207     bool ok;
1208     struct xkb_context *ctx = info->keymap->ctx;
1209
1210     if (!LookupModIndex(ctx, NULL, def->modifier, EXPR_TYPE_INT, &ndx)) {
1211         log_err(info->keymap->ctx,
1212                 "Illegal modifier map definition; "
1213                 "Ignoring map for non-modifier \"%s\"\n",
1214                 xkb_atom_text(ctx, def->modifier));
1215         return false;
1216     }
1217
1218     ok = true;
1219     tmp.modifier = ndx;
1220
1221     for (key = def->keys; key != NULL; key = (ExprDef *) key->common.next) {
1222         xkb_keysym_t sym;
1223
1224         if (key->op == EXPR_VALUE && key->value_type == EXPR_TYPE_KEYNAME) {
1225             tmp.haveSymbol = false;
1226             tmp.u.keyName = KeyNameToLong(key->value.keyName);
1227         }
1228         else if (ExprResolveKeySym(ctx, key, &sym)) {
1229             tmp.haveSymbol = true;
1230             tmp.u.keySym = sym;
1231         }
1232         else {
1233             log_err(info->keymap->ctx,
1234                     "Modmap entries may contain only key names or keysyms; "
1235                     "Illegal definition for %s modifier ignored\n",
1236                     ModIndexText(tmp.modifier));
1237             continue;
1238         }
1239
1240         ok = AddModMapEntry(info, &tmp) && ok;
1241     }
1242     return ok;
1243 }
1244
1245 static void
1246 HandleSymbolsFile(SymbolsInfo *info, XkbFile *file, enum merge_mode merge)
1247 {
1248     bool ok;
1249     ParseCommon *stmt;
1250
1251     free(info->name);
1252     info->name = strdup_safe(file->name);
1253
1254     stmt = file->defs;
1255     for (stmt = file->defs; stmt; stmt = stmt->next) {
1256         switch (stmt->type) {
1257         case STMT_INCLUDE:
1258             ok = HandleIncludeSymbols(info, (IncludeStmt *) stmt);
1259             break;
1260         case STMT_SYMBOLS:
1261             ok = HandleSymbolsDef(info, (SymbolsDef *) stmt);
1262             break;
1263         case STMT_VAR:
1264             ok = HandleGlobalVar(info, (VarDef *) stmt);
1265             break;
1266         case STMT_VMOD:
1267             ok = HandleVModDef((VModDef *) stmt, info->keymap, merge,
1268                                &info->vmods);
1269             break;
1270         case STMT_MODMAP:
1271             ok = HandleModMapDef(info, (ModMapDef *) stmt);
1272             break;
1273         default:
1274             log_err(info->keymap->ctx,
1275                     "Interpretation files may not include other types; "
1276                     "Ignoring %s\n", stmt_type_to_string(stmt->type));
1277             ok = false;
1278             break;
1279         }
1280
1281         if (!ok)
1282             info->errorCount++;
1283
1284         if (info->errorCount > 10) {
1285             log_err(info->keymap->ctx, "Abandoning symbols file \"%s\"\n",
1286                     file->topName);
1287             break;
1288         }
1289     }
1290 }
1291
1292 /**
1293  * Given a keysym @sym, return a key which generates it, or NULL.
1294  * This is used for example in a modifier map definition, such as:
1295  *      modifier_map Lock           { Caps_Lock };
1296  * where we want to add the Lock modifier to the modmap of the key
1297  * which matches the keysym Caps_Lock.
1298  * Since there can be many keys which generates the keysym, the key
1299  * is chosen first by lowest group in which the keysym appears, than
1300  * by lowest level and than by lowest key code.
1301  */
1302 static struct xkb_key *
1303 FindKeyForSymbol(struct xkb_keymap *keymap, xkb_keysym_t sym)
1304 {
1305     struct xkb_key *key, *ret = NULL;
1306     xkb_layout_index_t group, min_group = UINT32_MAX;
1307     xkb_level_index_t level, min_level = UINT16_MAX;
1308
1309     xkb_foreach_key(key, keymap) {
1310         for (group = 0; group < key->num_groups; group++) {
1311             for (level = 0; level < XkbKeyGroupWidth(key, group); level++) {
1312                 if (key->groups[group].levels[level].num_syms != 1 ||
1313                     key->groups[group].levels[level].u.sym != sym)
1314                     continue;
1315
1316                 /*
1317                  * If the keysym was found in a group or level > 0, we must
1318                  * keep looking since we might find a key in which the keysym
1319                  * is in a lower group or level.
1320                  */
1321                 if (group < min_group ||
1322                     (group == min_group && level < min_level)) {
1323                     ret = key;
1324                     if (group == 0 && level == 0) {
1325                         return ret;
1326                     }
1327                     else {
1328                         min_group = group;
1329                         min_level = level;
1330                     }
1331                 }
1332             }
1333         }
1334     }
1335
1336     return ret;
1337 }
1338
1339 /*
1340  * Find an appropriate type for a group and return its name.
1341  *
1342  * Simple recipe:
1343  * - ONE_LEVEL for width 0/1
1344  * - ALPHABETIC for 2 shift levels, with lower/upercase keysyms
1345  * - KEYPAD for keypad keys.
1346  * - TWO_LEVEL for other 2 shift level keys.
1347  * and the same for four level keys.
1348  *
1349  * FIXME: Decide how to handle multiple-syms-per-level, and do it.
1350  */
1351 static bool
1352 FindAutomaticType(struct xkb_context *ctx, GroupInfo *groupi,
1353                   xkb_atom_t *typeNameRtrn, bool *autoType)
1354 {
1355     xkb_level_index_t width = darray_size(groupi->levels);
1356
1357     *autoType = false;
1358
1359 #define GET_SYM(level) \
1360     (darray_item(groupi->levels, level).num_syms == 0 ? \
1361         XKB_KEY_NoSymbol : \
1362      darray_item(groupi->levels, level).num_syms == 1 ? \
1363         darray_item(groupi->levels, level).u.sym : \
1364      /* num_syms > 1 */ \
1365         darray_item(groupi->levels, level).u.syms[0])
1366
1367     if (width == 1 || width == 0) {
1368         *typeNameRtrn = xkb_atom_intern(ctx, "ONE_LEVEL");
1369         *autoType = true;
1370     }
1371     else if (width == 2) {
1372         xkb_keysym_t sym0 = GET_SYM(0);
1373         xkb_keysym_t sym1 = GET_SYM(1);
1374
1375         if (xkb_keysym_is_lower(sym0) && xkb_keysym_is_upper(sym1)) {
1376             *typeNameRtrn = xkb_atom_intern(ctx, "ALPHABETIC");
1377         }
1378         else if (xkb_keysym_is_keypad(sym0) || xkb_keysym_is_keypad(sym1)) {
1379             *typeNameRtrn = xkb_atom_intern(ctx, "KEYPAD");
1380             *autoType = true;
1381         }
1382         else {
1383             *typeNameRtrn = xkb_atom_intern(ctx, "TWO_LEVEL");
1384             *autoType = true;
1385         }
1386     }
1387     else if (width <= 4) {
1388         xkb_keysym_t sym0 = GET_SYM(0);
1389         xkb_keysym_t sym1 = GET_SYM(1);
1390         xkb_keysym_t sym2 = GET_SYM(2);
1391         xkb_keysym_t sym3 = (width == 4 ? GET_SYM(3) : XKB_KEY_NoSymbol);
1392
1393         if (xkb_keysym_is_lower(sym0) && xkb_keysym_is_upper(sym1))
1394             if (xkb_keysym_is_lower(sym2) && xkb_keysym_is_upper(sym3))
1395                 *typeNameRtrn =
1396                     xkb_atom_intern(ctx, "FOUR_LEVEL_ALPHABETIC");
1397             else
1398                 *typeNameRtrn = xkb_atom_intern(ctx,
1399                                                 "FOUR_LEVEL_SEMIALPHABETIC");
1400
1401         else if (xkb_keysym_is_keypad(sym0) || xkb_keysym_is_keypad(sym1))
1402             *typeNameRtrn = xkb_atom_intern(ctx, "FOUR_LEVEL_KEYPAD");
1403         else
1404             *typeNameRtrn = xkb_atom_intern(ctx, "FOUR_LEVEL");
1405         /* XXX: why not set autoType here? */
1406     }
1407     return width <= 4;
1408 }
1409
1410 static const struct xkb_key_type *
1411 FindTypeForGroup(struct xkb_keymap *keymap, KeyInfo *keyi,
1412                  xkb_layout_index_t group, bool *explicit_type)
1413 {
1414     bool autoType = false;
1415     unsigned int i;
1416     GroupInfo *groupi = &darray_item(keyi->groups, group);
1417     xkb_atom_t type_name = groupi->type;
1418
1419     if (type_name == XKB_ATOM_NONE) {
1420         if (keyi->dfltType != XKB_ATOM_NONE)
1421             type_name  = keyi->dfltType;
1422         else
1423             FindAutomaticType(keymap->ctx, groupi, &type_name, &autoType);
1424     }
1425
1426     if (type_name == XKB_ATOM_NONE) {
1427         log_warn(keymap->ctx,
1428                  "Couldn't find an automatic type for key '%s' group %d with %d levels; "
1429                  "Using the default type\n",
1430                  LongKeyNameText(keyi->name), group + 1,
1431                  darray_size(groupi->levels));
1432         goto use_default;
1433     }
1434
1435     for (i = 0; i < keymap->num_types; i++)
1436         if (keymap->types[i].name == type_name)
1437             break;
1438
1439     if (i >= keymap->num_types) {
1440         log_warn(keymap->ctx,
1441                  "The type \"%s\" for key '%s' group %d was not previously defined; "
1442                  "Using the default type\n",
1443                  xkb_atom_text(keymap->ctx, type_name),
1444                  LongKeyNameText(keyi->name), group + 1);
1445         goto use_default;
1446     }
1447
1448     /* XXX: What's with the magic 2 here? */
1449     *explicit_type = !autoType || darray_size(groupi->levels) > 2;
1450     return &keymap->types[i];
1451
1452 use_default:
1453     /*
1454      * Index 0 is guaranteed to contain something, usually
1455      * ONE_LEVEL or at least some default one-level type.
1456      */
1457     *explicit_type = false;
1458     return &keymap->types[0];
1459 }
1460
1461 static bool
1462 CopySymbolsDef(SymbolsInfo *info, KeyInfo *keyi)
1463 {
1464     struct xkb_keymap *keymap = info->keymap;
1465     struct xkb_key *key;
1466     GroupInfo *groupi;
1467     const GroupInfo *group0;
1468     xkb_layout_index_t i;
1469
1470     /*
1471      * The name is guaranteed to be real and not an alias (see
1472      * AddKeySymbols), so 'false' is safe here.
1473      */
1474     key = FindNamedKey(keymap, keyi->name, false);
1475     if (!key) {
1476         log_vrb(info->keymap->ctx, 5,
1477                 "Key %s not found in keycodes; Symbols ignored\n",
1478                 LongKeyNameText(keyi->name));
1479         return false;
1480     }
1481
1482     /* Find the range of groups we need. */
1483     key->num_groups = 0;
1484     darray_enumerate(i, groupi, keyi->groups)
1485         if (groupi->defined)
1486             key->num_groups = i + 1;
1487
1488     if (key->num_groups <= 0)
1489         return false; /* WSGO */
1490
1491     darray_resize(keyi->groups, key->num_groups);
1492
1493     /*
1494      * If there are empty groups between non-empty ones, fill them with data
1495      * from the first group.
1496      * We can make a wrong assumption here. But leaving gaps is worse.
1497      */
1498     group0 = &darray_item(keyi->groups, 0);
1499     darray_foreach_from(groupi, keyi->groups, 1) {
1500         if (groupi->defined)
1501             continue;
1502
1503         CopyGroupInfo(groupi, group0);
1504     }
1505
1506     key->groups = calloc(key->num_groups, sizeof(*key->groups));
1507
1508     /* Find and assign the groups' types in the keymap. */
1509     darray_enumerate(i, groupi, keyi->groups) {
1510         const struct xkb_key_type *type;
1511         bool explicit_type;
1512
1513         type = FindTypeForGroup(keymap, keyi, i, &explicit_type);
1514
1515         /* Always have as many levels as the type specifies. */
1516         if (type->num_levels < darray_size(groupi->levels)) {
1517             struct xkb_level *leveli;
1518
1519             log_vrb(info->keymap->ctx, 1,
1520                     "Type \"%s\" has %d levels, but %s has %d levels; "
1521                     "Ignoring extra symbols\n",
1522                     xkb_atom_text(keymap->ctx, type->name), type->num_levels,
1523                     LongKeyNameText(keyi->name),
1524                     (int) darray_size(groupi->levels));
1525
1526             darray_foreach_from(leveli, groupi->levels, type->num_levels)
1527                 ClearLevelInfo(leveli);
1528         }
1529         darray_resize0(groupi->levels, type->num_levels);
1530
1531         key->groups[i].explicit_type = explicit_type;
1532         key->groups[i].type = type;
1533     }
1534
1535     /* Copy levels. */
1536     darray_enumerate(i, groupi, keyi->groups) {
1537         key->groups[i].levels = darray_mem(groupi->levels, 0);
1538         darray_init(groupi->levels);
1539     }
1540
1541     key->out_of_range_group_number = keyi->out_of_range_group_number;
1542     key->out_of_range_group_action = keyi->out_of_range_group_action;
1543
1544     if (keyi->defined & KEY_FIELD_VMODMAP) {
1545         key->vmodmap = keyi->vmodmap;
1546         key->explicit |= EXPLICIT_VMODMAP;
1547     }
1548
1549     if (keyi->repeat != KEY_REPEAT_UNDEFINED) {
1550         key->repeats = (keyi->repeat == KEY_REPEAT_YES);
1551         key->explicit |= EXPLICIT_REPEAT;
1552     }
1553
1554     darray_foreach(groupi, keyi->groups) {
1555         if (groupi->defined & GROUP_FIELD_ACTS) {
1556             key->explicit |= EXPLICIT_INTERP;
1557             break;
1558         }
1559     }
1560
1561     return true;
1562 }
1563
1564 static bool
1565 CopyModMapDef(SymbolsInfo *info, ModMapEntry *entry)
1566 {
1567     struct xkb_key *key;
1568     struct xkb_keymap *keymap = info->keymap;
1569
1570     if (!entry->haveSymbol) {
1571         key = FindNamedKey(keymap, entry->u.keyName, true);
1572         if (!key) {
1573             log_vrb(info->keymap->ctx, 5,
1574                     "Key %s not found in keycodes; "
1575                     "Modifier map entry for %s not updated\n",
1576                     LongKeyNameText(entry->u.keyName),
1577                     ModIndexText(entry->modifier));
1578             return false;
1579         }
1580     }
1581     else {
1582         key = FindKeyForSymbol(keymap, entry->u.keySym);
1583         if (!key) {
1584             log_vrb(info->keymap->ctx, 5,
1585                     "Key \"%s\" not found in symbol map; "
1586                     "Modifier map entry for %s not updated\n",
1587                     KeysymText(entry->u.keySym),
1588                     ModIndexText(entry->modifier));
1589             return false;
1590         }
1591     }
1592
1593     key->modmap |= (1 << entry->modifier);
1594     return true;
1595 }
1596
1597 static bool
1598 CopySymbolsToKeymap(struct xkb_keymap *keymap, SymbolsInfo *info)
1599 {
1600     KeyInfo *keyi;
1601     ModMapEntry *mm;
1602     struct xkb_key *key;
1603
1604     keymap->symbols_section_name = strdup_safe(info->name);
1605
1606     keymap->group_names = info->group_names;
1607     darray_init(info->group_names);
1608
1609     darray_foreach(keyi, info->keys)
1610         if (!CopySymbolsDef(info, keyi))
1611             info->errorCount++;
1612
1613     if (xkb_context_get_log_verbosity(keymap->ctx) > 3) {
1614         xkb_foreach_key(key, keymap) {
1615             if (key->name[0] == '\0')
1616                 continue;
1617
1618             if (key->num_groups < 1)
1619                 log_info(keymap->ctx,
1620                          "No symbols defined for %s\n",
1621                          KeyNameText(key->name));
1622         }
1623     }
1624
1625     darray_foreach(mm, info->modMaps)
1626         if (!CopyModMapDef(info, mm))
1627             info->errorCount++;
1628
1629     /* XXX: If we don't ignore errorCount, things break. */
1630     return true;
1631 }
1632
1633 bool
1634 CompileSymbols(XkbFile *file, struct xkb_keymap *keymap,
1635                enum merge_mode merge)
1636 {
1637     SymbolsInfo info;
1638     ActionsInfo *actions;
1639
1640     actions = NewActionsInfo();
1641     if (!actions)
1642         return false;
1643
1644     InitSymbolsInfo(&info, keymap, file->id, actions);
1645     info.dflt.merge = merge;
1646
1647     HandleSymbolsFile(&info, file, merge);
1648
1649     if (darray_empty(info.keys))
1650         goto err_info;
1651
1652     if (info.errorCount != 0)
1653         goto err_info;
1654
1655     if (!CopySymbolsToKeymap(keymap, &info))
1656         goto err_info;
1657
1658     ClearSymbolsInfo(&info);
1659     FreeActionsInfo(actions);
1660     return true;
1661
1662 err_info:
1663     FreeActionsInfo(actions);
1664     ClearSymbolsInfo(&info);
1665     return false;
1666 }