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