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
key_hash_clear_keycode(gpointer key,gpointer value,gpointer data)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
key_hash_insert_entry(GtkKeyHash * key_hash,GtkKeyHashEntry * entry)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 *
key_hash_get_keycode_hash(GtkKeyHash * key_hash)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
key_hash_keys_changed(GdkKeymap * keymap,GtkKeyHash * key_hash)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 * Returns: the newly created object. Free with _gtk_key_hash_free().
123 **/
124 GtkKeyHash *
_gtk_key_hash_new(GdkKeymap * keymap,GDestroyNotify item_destroy_notify)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
key_hash_free_entry(GtkKeyHash * key_hash,GtkKeyHashEntry * entry)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
key_hash_free_entry_foreach(gpointer value,gpointer data)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
_gtk_key_hash_free(GtkKeyHash * key_hash)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
_gtk_key_hash_add_entry(GtkKeyHash * key_hash,guint keyval,GdkModifierType modifiers,gpointer value)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
_gtk_key_hash_remove_entry(GtkKeyHash * key_hash,gpointer value)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
lookup_result_compare(gconstpointer a,gconstpointer b)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 *
sort_lookup_results(GSList * slist)302 sort_lookup_results (GSList *slist)
303 {
304 return g_slist_sort (slist, lookup_result_compare);
305 }
306
307 static gint
lookup_result_compare_by_keyval(gconstpointer a,gconstpointer b)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 *
sort_lookup_results_by_keyval(GSList * slist)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
keyval_in_group(GdkKeymap * keymap,guint keyval,gint group)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 * Returns: A newly-allocated #GSList of matching entries.
377 * Free with g_slist_free() when no longer needed.
378 */
379 GSList *
_gtk_key_hash_lookup(GtkKeyHash * key_hash,guint16 hardware_keycode,GdkModifierType state,GdkModifierType mask,gint group)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 * Returns: A #GSList of all matching entries.
538 **/
539 GSList *
_gtk_key_hash_lookup_keyval(GtkKeyHash * key_hash,guint keyval,GdkModifierType modifiers)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 }
581