Pileus Git - ~andy/gtk/blob - gtk/gtkkeyhash.c

   1 /* gtkkeyhash.c: Keymap aware matching of key bindings
   2  *
   3  * GTK - The GIMP Toolkit
   4  * Copyright (C) 2002, Red Hat Inc.
   5  *
   6  * This library is free software; you can redistribute it and/or
   7  * modify it under the terms of the GNU Lesser General Public
   8  * License as published by the Free Software Foundation; either
   9  * version 2 of the License, or (at your option) any later version.
  10  *
  11  * This library is distributed in the hope that it will be useful,
  12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14  * Lesser General Public License for more details.
  15  *
  16  * You should have received a copy of the GNU Lesser General Public
  17  * License along with this library. If not, see <http://www.gnu.org/licenses/>.
  18  */
  19
  20 #include "config.h"
  21
  22 #include "gtkdebug.h"
  23 #include "gtkkeyhash.h"
  24 #include "gtkprivate.h"
  25
  26 typedef struct _GtkKeyHashEntry GtkKeyHashEntry;
  27
  28 struct _GtkKeyHashEntry
  29 {
  30   guint keyval;
  31   GdkModifierType modifiers;
  32   gpointer value;
  33
  34   /* Set as a side effect of generating key_hash->keycode_hash
  35    */
  36   GdkKeymapKey *keys;
  37   gint n_keys;
  38 };
  39
  40 struct _GtkKeyHash
  41 {
  42   GdkKeymap *keymap;
  43   GHashTable *keycode_hash;
  44   GHashTable *reverse_hash;
  45   GList *entries_list;
  46   GDestroyNotify destroy_notify;
  47 };
  48
  49 static void
  50 key_hash_clear_keycode (gpointer key,
  51                         gpointer value,
  52                         gpointer data)
  53 {
  54   GSList *keys = value;
  55   g_slist_free (keys);
  56 }
  57
  58 static void
  59 key_hash_insert_entry (GtkKeyHash      *key_hash,
  60                        GtkKeyHashEntry *entry)
  61 {
  62   gint i;
  63
  64   g_free (entry->keys);
  65   gdk_keymap_get_entries_for_keyval (key_hash->keymap,
  66                                      entry->keyval,
  67                                      &entry->keys, &entry->n_keys);
  68
  69   for (i = 0; i < entry->n_keys; i++)
  70     {
  71       GSList *old_keys = g_hash_table_lookup (key_hash->keycode_hash,
  72                                               GUINT_TO_POINTER (entry->keys[i].keycode));
  73       old_keys = g_slist_prepend (old_keys, entry);
  74       g_hash_table_insert (key_hash->keycode_hash,
  75                            GUINT_TO_POINTER (entry->keys[i].keycode),
  76                            old_keys);
  77     }
  78 }
  79
  80 static GHashTable *
  81 key_hash_get_keycode_hash (GtkKeyHash *key_hash)
  82 {
  83   if (!key_hash->keycode_hash)
  84     {
  85       GList *tmp_list;
  86
  87       key_hash->keycode_hash = g_hash_table_new (g_direct_hash, NULL);
  88
  89       /* Preserve the original insertion order
  90        */
  91       for (tmp_list = g_list_last (key_hash->entries_list);
  92            tmp_list;
  93            tmp_list = tmp_list->prev)
  94         key_hash_insert_entry (key_hash, tmp_list->data);
  95     }
  96
  97   return key_hash->keycode_hash;
  98 }
  99
 100 static void
 101 key_hash_keys_changed (GdkKeymap  *keymap,
 102                        GtkKeyHash *key_hash)
 103 {
 104   /* The keymap changed, so we have to regenerate the keycode hash
 105    */
 106   if (key_hash->keycode_hash)
 107     {
 108       g_hash_table_foreach (key_hash->keycode_hash, key_hash_clear_keycode, NULL);
 109       g_hash_table_destroy (key_hash->keycode_hash);
 110       key_hash->keycode_hash = NULL;
 111     }
 112 }
 113
 114 /**
 115  * _gtk_key_hash_new:
 116  * @keymap: a #GdkKeymap
 117  * @item_destroy_notify: function to be called when items are removed
 118  *   from the hash or %NULL.
 119  *
 120  * Create a new key hash object for doing binding resolution.
 121  *
 122  * Return value: the newly created object. Free with _gtk_key_hash_free().
 123  **/
 124 GtkKeyHash *
 125 _gtk_key_hash_new (GdkKeymap      *keymap,
 126                    GDestroyNotify  item_destroy_notify)
 127 {
 128   GtkKeyHash *key_hash = g_new (GtkKeyHash, 1);
 129
 130   key_hash->keymap = keymap;
 131   g_signal_connect (keymap, "keys-changed",
 132                     G_CALLBACK (key_hash_keys_changed), key_hash);
 133
 134   key_hash->entries_list = NULL;
 135   key_hash->keycode_hash = NULL;
 136   key_hash->reverse_hash = g_hash_table_new (g_direct_hash, NULL);
 137   key_hash->destroy_notify = item_destroy_notify;
 138
 139   return key_hash;
 140 }
 141
 142 static void
 143 key_hash_free_entry (GtkKeyHash      *key_hash,
 144                      GtkKeyHashEntry *entry)
 145 {
 146   if (key_hash->destroy_notify)
 147     (*key_hash->destroy_notify) (entry->value);
 148
 149   g_free (entry->keys);
 150   g_slice_free (GtkKeyHashEntry, entry);
 151 }
 152
 153 static void
 154 key_hash_free_entry_foreach (gpointer value,
 155                              gpointer data)
 156 {
 157   GtkKeyHashEntry *entry = value;
 158   GtkKeyHash *key_hash = data;
 159
 160   key_hash_free_entry (key_hash, entry);
 161 }
 162
 163 /**
 164  * gtk_key_hash_free:
 165  * @key_hash: a #GtkKeyHash
 166  *
 167  * Destroys a key hash created with gtk_key_hash_new()
 168  **/
 169 void
 170 _gtk_key_hash_free (GtkKeyHash *key_hash)
 171 {
 172   g_signal_handlers_disconnect_by_func (key_hash->keymap,
 173                                         key_hash_keys_changed,
 174                                         key_hash);
 175
 176   if (key_hash->keycode_hash)
 177     {
 178       g_hash_table_foreach (key_hash->keycode_hash, key_hash_clear_keycode, NULL);
 179       g_hash_table_destroy (key_hash->keycode_hash);
 180     }
 181
 182   g_hash_table_destroy (key_hash->reverse_hash);
 183
 184   g_list_foreach (key_hash->entries_list, key_hash_free_entry_foreach, key_hash);
 185   g_list_free (key_hash->entries_list);
 186
 187   g_free (key_hash);
 188 }
 189
 190 /**
 191  * _gtk_key_hash_add_entry:
 192  * @key_hash: a #GtkKeyHash
 193  * @keyval: key symbol for this binding
 194  * @modifiers: modifiers for this binding
 195  * @value: value to insert in the key hash
 196  *
 197  * Inserts a pair of key symbol and modifier mask into the key hash.
 198  **/
 199 void
 200 _gtk_key_hash_add_entry (GtkKeyHash      *key_hash,
 201                          guint            keyval,
 202                          GdkModifierType  modifiers,
 203                          gpointer         value)
 204 {
 205   GtkKeyHashEntry *entry = g_slice_new (GtkKeyHashEntry);
 206
 207   entry->value = value;
 208   entry->keyval = keyval;
 209   entry->modifiers = modifiers;
 210   entry->keys = NULL;
 211
 212   key_hash->entries_list = g_list_prepend (key_hash->entries_list, entry);
 213   g_hash_table_insert (key_hash->reverse_hash, value, key_hash->entries_list);
 214
 215   if (key_hash->keycode_hash)
 216     key_hash_insert_entry (key_hash, entry);
 217 }
 218
 219 /**
 220  * _gtk_key_hash_remove_entry:
 221  * @key_hash: a #GtkKeyHash
 222  * @value: value previously added with _gtk_key_hash_add_entry()
 223  *
 224  * Removes a value previously added to the key hash with
 225  * _gtk_key_hash_add_entry().
 226  **/
 227 void
 228 _gtk_key_hash_remove_entry (GtkKeyHash *key_hash,
 229                             gpointer    value)
 230 {
 231   GList *entry_node = g_hash_table_lookup (key_hash->reverse_hash, value);
 232
 233   if (entry_node)
 234     {
 235       GtkKeyHashEntry *entry = entry_node->data;
 236
 237       if (key_hash->keycode_hash)
 238         {
 239           gint i;
 240
 241           for (i = 0; i < entry->n_keys; i++)
 242             {
 243               GSList *old_keys = g_hash_table_lookup (key_hash->keycode_hash,
 244                                                       GUINT_TO_POINTER (entry->keys[i].keycode));
 245
 246               GSList *new_keys = g_slist_remove (old_keys, entry);
 247               if (new_keys != old_keys)
 248                 {
 249                   if (new_keys)
 250                     g_hash_table_insert (key_hash->keycode_hash,
 251                                          GUINT_TO_POINTER (entry->keys[i].keycode),
 252                                          new_keys);
 253                   else
 254                     g_hash_table_remove (key_hash->keycode_hash,
 255                                          GUINT_TO_POINTER (entry->keys[i].keycode));
 256                 }
 257             }
 258         }
 259
 260       g_hash_table_remove (key_hash->reverse_hash, entry_node);
 261       key_hash->entries_list = g_list_delete_link (key_hash->entries_list, entry_node);
 262
 263       key_hash_free_entry (key_hash, entry);
 264     }
 265 }
 266
 267 static gint
 268 lookup_result_compare (gconstpointer a,
 269                        gconstpointer b)
 270 {
 271   const GtkKeyHashEntry *entry_a = a;
 272   const GtkKeyHashEntry *entry_b = b;
 273   guint modifiers;
 274
 275   gint n_bits_a = 0;
 276   gint n_bits_b = 0;
 277
 278   modifiers = entry_a->modifiers;
 279   while (modifiers)
 280     {
 281       if (modifiers & 1)
 282         n_bits_a++;
 283       modifiers >>= 1;
 284     }
 285
 286   modifiers = entry_b->modifiers;
 287   while (modifiers)
 288     {
 289       if (modifiers & 1)
 290         n_bits_b++;
 291       modifiers >>= 1;
 292     }
 293
 294   return n_bits_a < n_bits_b ? -1 : (n_bits_a == n_bits_b ? 0 : 1);
 295
 296 }
 297
 298 /* Sort a list of results so that matches with less modifiers come
 299  * before matches with more modifiers
 300  */
 301 static GSList *
 302 sort_lookup_results (GSList *slist)
 303 {
 304   return g_slist_sort (slist, lookup_result_compare);
 305 }
 306
 307 static gint
 308 lookup_result_compare_by_keyval (gconstpointer a,
 309                                  gconstpointer b)
 310 {
 311   const GtkKeyHashEntry *entry_a = a;
 312   const GtkKeyHashEntry *entry_b = b;
 313
 314   if (entry_a->keyval < entry_b->keyval)
 315         return -1;
 316   else if (entry_a->keyval > entry_b->keyval)
 317         return 1;
 318   else
 319         return 0;
 320 }
 321
 322 static GSList *
 323 sort_lookup_results_by_keyval (GSList *slist)
 324 {
 325   return g_slist_sort (slist, lookup_result_compare_by_keyval);
 326 }
 327
 328 /* Return true if keyval is defined in keyboard group
 329  */
 330 static gboolean
 331 keyval_in_group (GdkKeymap  *keymap,
 332                  guint      keyval,
 333                  gint       group)
 334 {
 335   GtkKeyHashEntry entry;
 336   gint i;
 337
 338   gdk_keymap_get_entries_for_keyval (keymap,
 339                                      keyval,
 340                                      &entry.keys, &entry.n_keys);
 341
 342   for (i = 0; i < entry.n_keys; i++)
 343     {
 344       if (entry.keys[i].group == group)
 345         {
 346           g_free (entry.keys);
 347           return TRUE;
 348         }
 349     }
 350
 351   g_free (entry.keys);
 352   return FALSE;
 353 }
 354
 355 /**
 356  * _gtk_key_hash_lookup:
 357  * @key_hash: a #GtkKeyHash
 358  * @hardware_keycode: hardware keycode field from a #GdkEventKey
 359  * @state: state field from a #GdkEventKey
 360  * @mask: mask of modifiers to consider when matching against the
 361  *        modifiers in entries.
 362  * @group: group field from a #GdkEventKey
 363  *
 364  * Looks up the best matching entry or entries in the hash table for
 365  * a given event. The results are sorted so that entries with less
 366  * modifiers come before entries with more modifiers.
 367  *
 368  * The matches returned by this function can be exact (i.e. keycode, level
 369  * and group all match) or fuzzy (i.e. keycode and level match, but group
 370  * does not). As long there are any exact matches, only exact matches
 371  * are returned. If there are no exact matches, fuzzy matches will be
 372  * returned, as long as they are not shadowing a possible exact match.
 373  * This means that fuzzy matches won't be considered if their keyval is
 374  * present in the current group.
 375  *
 376  * Return value: A newly-allocated #GSList of matching entries.
 377  *     Free with g_slist_free() when no longer needed.
 378  */
 379 GSList *
 380 _gtk_key_hash_lookup (GtkKeyHash      *key_hash,
 381                       guint16          hardware_keycode,
 382                       GdkModifierType  state,
 383                       GdkModifierType  mask,
 384                       gint             group)
 385 {
 386   GHashTable *keycode_hash = key_hash_get_keycode_hash (key_hash);
 387   GSList *keys = g_hash_table_lookup (keycode_hash, GUINT_TO_POINTER ((guint)hardware_keycode));
 388   GSList *results = NULL;
 389   GSList *l;
 390   gboolean have_exact = FALSE;
 391   guint keyval;
 392   gint effective_group;
 393   gint level;
 394   GdkModifierType modifiers;
 395   GdkModifierType consumed_modifiers;
 396   GdkModifierType shift_group_mask;
 397   gboolean group_mod_is_accel_mod = FALSE;
 398   const GdkModifierType xmods = GDK_MOD2_MASK|GDK_MOD3_MASK|GDK_MOD4_MASK|GDK_MOD5_MASK;
 399   const GdkModifierType vmods = GDK_SUPER_MASK|GDK_HYPER_MASK|GDK_META_MASK;
 400
 401   /* We don't want Caps_Lock to affect keybinding lookups.
 402    */
 403   state &= ~GDK_LOCK_MASK;
 404
 405   _gtk_translate_keyboard_accel_state (key_hash->keymap,
 406                                        hardware_keycode, state, mask, group,
 407                                        &keyval,
 408                                        &effective_group, &level, &consumed_modifiers);
 409
 410   /* if the group-toggling modifier is part of the default accel mod
 411    * mask, and it is active, disable it for matching
 412    */
 413   shift_group_mask = gdk_keymap_get_modifier_mask (key_hash->keymap,
 414                                                    GDK_MODIFIER_INTENT_SHIFT_GROUP);
 415   if (mask & shift_group_mask)
 416     group_mod_is_accel_mod = TRUE;
 417
 418   gdk_keymap_map_virtual_modifiers (key_hash->keymap, &mask);
 419   gdk_keymap_add_virtual_modifiers (key_hash->keymap, &state);
 420
 421   GTK_NOTE (KEYBINDINGS,
 422             g_message ("Looking up keycode = %u, modifiers = 0x%04x,\n"
 423                        "    keyval = %u, group = %d, level = %d, consumed_modifiers = 0x%04x",
 424                        hardware_keycode, state, keyval, effective_group, level, consumed_modifiers));
 425
 426   if (keys)
 427     {
 428       GSList *tmp_list = keys;
 429       while (tmp_list)
 430         {
 431           GtkKeyHashEntry *entry = tmp_list->data;
 432
 433           /* If the virtual Super, Hyper or Meta modifiers are present,
 434            * they will also be mapped to some of the Mod2 - Mod5 modifiers,
 435            * so we compare them twice, ignoring either set.
 436            * We accept combinations involving virtual modifiers only if they
 437            * are mapped to separate modifiers; i.e. if Super and Hyper are
 438            * both mapped to Mod4, then pressing a key that is mapped to Mod4
 439            * will not match a Super+Hyper entry.
 440            */
 441           modifiers = entry->modifiers;
 442           if (gdk_keymap_map_virtual_modifiers (key_hash->keymap, &modifiers) &&
 443               ((modifiers & ~consumed_modifiers & mask & ~vmods) == (state & ~consumed_modifiers & mask & ~vmods) ||
 444                (modifiers & ~consumed_modifiers & mask & ~xmods) == (state & ~consumed_modifiers & mask & ~xmods)))
 445             {
 446               gint i;
 447
 448               if (keyval == entry->keyval && /* Exact match */
 449                   /* but also match for group if it is an accel mod, because
 450                    * otherwise we can get multiple exact matches, some being
 451                    * bogus */
 452                   (!group_mod_is_accel_mod ||
 453                    (state & shift_group_mask) == (entry->modifiers & shift_group_mask)))
 454
 455                 {
 456                   GTK_NOTE (KEYBINDINGS,
 457                             g_message ("  found exact match, keyval = %u, modifiers = 0x%04x",
 458                                        entry->keyval, entry->modifiers));
 459
 460                   if (!have_exact)
 461                     {
 462                       g_slist_free (results);
 463                       results = NULL;
 464                     }
 465
 466                   have_exact = TRUE;
 467                   results = g_slist_prepend (results, entry);
 468                 }
 469
 470               if (!have_exact)
 471                 {
 472                   for (i = 0; i < entry->n_keys; i++)
 473                     {
 474                       if (entry->keys[i].keycode == hardware_keycode &&
 475                           entry->keys[i].level == level &&
 476                            /* Only match for group if it's an accel mod */
 477                           (!group_mod_is_accel_mod ||
 478                            entry->keys[i].group == effective_group))
 479                         {
 480                           GTK_NOTE (KEYBINDINGS,
 481                                     g_message ("  found group = %d, level = %d",
 482                                                entry->keys[i].group, entry->keys[i].level));
 483                           results = g_slist_prepend (results, entry);
 484                           break;
 485                         }
 486                     }
 487                 }
 488             }
 489
 490           tmp_list = tmp_list->next;
 491         }
 492     }
 493
 494   if (!have_exact && results)
 495     {
 496       /* If there are fuzzy matches, check that the current group doesn't also
 497        * define these keyvals; if yes, discard results because a widget up in
 498        * the stack may have an exact match and we don't want to 'steal' it.
 499        */
 500       guint oldkeyval = 0;
 501       GtkKeyHashEntry *keyhashentry;
 502
 503       results = sort_lookup_results_by_keyval (results);
 504       for (l = results; l; l = l->next)
 505         {
 506           keyhashentry = l->data;
 507           if (l == results || oldkeyval != keyhashentry->keyval)
 508             {
 509               oldkeyval = keyhashentry->keyval;
 510               if (keyval_in_group (key_hash->keymap, oldkeyval, group))
 511                 {
 512                   g_slist_free (results);
 513                   return NULL;
 514                 }
 515             }
 516         }
 517     }
 518
 519   results = sort_lookup_results (results);
 520   for (l = results; l; l = l->next)
 521     l->data = ((GtkKeyHashEntry *)l->data)->value;
 522
 523   return results;
 524 }
 525
 526 /**
 527  * _gtk_key_hash_lookup_keyval:
 528  * @key_hash: a #GtkKeyHash
 529  * @event: a #GtkEvent
 530  *
 531  * Looks up the best matching entry or entries in the hash table for a
 532  * given keyval/modifiers pair. It's better to use
 533  * _gtk_key_hash_lookup() if you have the original #GdkEventKey
 534  * available.  The results are sorted so that entries with less
 535  * modifiers come before entries with more modifiers.
 536  *
 537  * Return value: A #GSList of all matching entries.
 538  **/
 539 GSList *
 540 _gtk_key_hash_lookup_keyval (GtkKeyHash     *key_hash,
 541                              guint           keyval,
 542                              GdkModifierType modifiers)
 543 {
 544   GdkKeymapKey *keys;
 545   gint n_keys;
 546   GSList *results = NULL;
 547   GSList *l;
 548
 549   if (!keyval)                  /* Key without symbol */
 550     return NULL;
 551
 552   /* Find some random keycode for this keyval
 553    */
 554   gdk_keymap_get_entries_for_keyval (key_hash->keymap, keyval,
 555                                      &keys, &n_keys);
 556
 557   if (n_keys)
 558     {
 559       GHashTable *keycode_hash = key_hash_get_keycode_hash (key_hash);
 560       GSList *entries = g_hash_table_lookup (keycode_hash, GUINT_TO_POINTER (keys[0].keycode));
 561
 562       while (entries)
 563         {
 564           GtkKeyHashEntry *entry = entries->data;
 565
 566           if (entry->keyval == keyval && entry->modifiers == modifiers)
 567             results = g_slist_prepend (results, entry);
 568
 569           entries = entries->next;
 570         }
 571     }
 572
 573   g_free (keys);
 574
 575   results = sort_lookup_results (results);
 576   for (l = results; l; l = l->next)
 577     l->data = ((GtkKeyHashEntry *)l->data)->value;
 578
 579   return results;
 580 }