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