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