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