src/keyboard.C

   1 /*----------------------------------------------------------------------*
   2  * File:        keyboard.C
   3  *----------------------------------------------------------------------*
   4  *
   5  * All portions of code are copyright by their respective author/s.
   6  * Copyright (c) 2005      WU Fengguang
   7  * Copyright (c) 2005-2006 Marc Lehmann <pcg@goof.com>
   8  *
   9  * This program is free software; you can redistribute it and/or modify
  10  * it under the terms of the GNU General Public License as published by
  11  * the Free Software Foundation; either version 2 of the License, or
  12  * (at your option) any later version.
  13  *
  14  * This program is distributed in the hope that it will be useful,
  15  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  16  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  17  * GNU General Public License for more details.
  18  *
  19  * You should have received a copy of the GNU General Public License
  20  * along with this program; if not, write to the Free Software
  21  * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  22  *----------------------------------------------------------------------*/
  23
  24 #include "../config.h"
  25 #include "rxvt.h"
  26
  27 #ifdef KEYSYM_RESOURCE
  28
  29 #include <cstring>
  30
  31 #include "rxvtperl.h"
  32 #include "keyboard.h"
  33 #include "command.h"
  34
  35 /* an intro to the data structure:
  36  *
  37  * vector keymap[] is grouped.
  38  *
  39  * inside each group, elements are sorted by the criteria given by compare_priority().
  40  * the lookup of keysym is done in two steps:
  41  * 1) locate the group corresponds to the keysym;
  42  * 2) do a linear search inside the group.
  43  *
  44  * array hash[] effectively defines a map from a keysym to a group in keymap[].
  45  *
  46  * each group has its address(the index of first group element in keymap[]),
  47  * which is computed and stored in hash[].
  48  * hash[] stores the addresses in the form of:
  49  * index: 0      I1       I2       I3            In
  50  * value: 0...0, A1...A1, A2...A2, A3...A3, ..., An...An
  51  * where
  52  * A1 = 0;
  53  * Ai+1 = N1 + N2 + ... + Ni.
  54  * it is computed from hash_budget_size[]:
  55  * index: 0      I1         I2         I3             In
  56  * value: 0...0, N1, 0...0, N2, 0...0, N3,    ...,    Nn, 0...0
  57  *        0...0, 0.......0, N1.....N1, N1+N2...N1+N2, ... (the compution of hash[])
  58  * or we can say
  59  * hash_budget_size[Ii] = Ni; hash_budget_size[elsewhere] = 0,
  60  * where
  61  * set {I1, I2, ..., In} = { hashkey of keymap[0]->keysym, ..., keymap[keymap.size-1]->keysym }
  62  * where hashkey of keymap[i]->keysym = keymap[i]->keysym & KEYSYM_HASH_MASK
  63  *       n(the number of groups) = the number of non-zero member of hash_budget_size[];
  64  *       Ni(the size of group i) = hash_budget_size[Ii].
  65  */
  66
  67 #if STOCK_KEYMAP
  68 ////////////////////////////////////////////////////////////////////////////////
  69 // default keycode translation map and keyevent handlers
  70
  71 keysym_t keyboard_manager::stock_keymap[] = {
  72   /* examples */
  73   /*        keysym,                state, range,                  type,              str */
  74 //{XK_ISO_Left_Tab,                    0,     1,      keysym_t::STRING,           "\033[Z"},
  75 //{            'a',                    0,    26, keysym_t::RANGE_META8,           "a" "%c"},
  76 //{            'a',          ControlMask,    26, keysym_t::RANGE_META8,          "\ 1" "%c"},
  77 //{        XK_Left,                    0,     4,        keysym_t::LIST,     ".\033[.DACB."},
  78 //{        XK_Left,            ShiftMask,     4,        keysym_t::LIST,     ".\033[.dacb."},
  79 //{        XK_Left,          ControlMask,     4,        keysym_t::LIST,     ".\033O.dacb."},
  80 //{         XK_Tab,          ControlMask,     1,      keysym_t::STRING,      "\033<C-Tab>"},
  81 //{  XK_apostrophe,          ControlMask,     1,      keysym_t::STRING,        "\033<C-'>"},
  82 //{       XK_slash,          ControlMask,     1,      keysym_t::STRING,        "\033<C-/>"},
  83 //{   XK_semicolon,          ControlMask,     1,      keysym_t::STRING,        "\033<C-;>"},
  84 //{       XK_grave,          ControlMask,     1,      keysym_t::STRING,        "\033<C-`>"},
  85 //{       XK_comma,          ControlMask,     1,      keysym_t::STRING,     "\033<C-\054>"},
  86 //{      XK_Return,          ControlMask,     1,      keysym_t::STRING,   "\033<C-Return>"},
  87 //{      XK_Return,            ShiftMask,     1,      keysym_t::STRING,   "\033<S-Return>"},
  88 //{            ' ',            ShiftMask,     1,      keysym_t::STRING,    "\033<S-Space>"},
  89 //{            '.',          ControlMask,     1,      keysym_t::STRING,        "\033<C-.>"},
  90 //{            '0',          ControlMask,    10,       keysym_t::RANGE,   "0" "\033<C-%c>"},
  91 //{            '0', MetaMask|ControlMask,    10,       keysym_t::RANGE, "0" "\033<M-C-%c>"},
  92 //{            'a', MetaMask|ControlMask,    26,       keysym_t::RANGE, "a" "\033<M-C-%c>"},
  93 };
  94 #endif
  95
  96 static void
  97 output_string (rxvt_term *rt, const char *str)
  98 {
  99   if (strncmp (str, "command:", 8) == 0)
 100     rt->cmd_write (str + 8, strlen (str) - 8);
 101   else if (strncmp (str, "perl:", 5) == 0)
 102     HOOK_INVOKE((rt, HOOK_USER_COMMAND, DT_STR, str + 5, DT_END));
 103   else
 104     rt->tt_write (str, strlen (str));
 105 }
 106
 107 static void
 108 output_string_meta8 (rxvt_term *rt, unsigned int state, char *buf, int buflen)
 109 {
 110   if (state & rt->ModMetaMask)
 111     {
 112 #ifdef META8_OPTION
 113       if (rt->meta_char == 0x80)        /* set 8-bit on */
 114         {
 115           for (char *ch = buf; ch < buf + buflen; ch++)
 116             *ch |= 0x80;
 117         }
 118       else if (rt->meta_char == C0_ESC) /* escape prefix */
 119 #endif
 120         {
 121           const char ch = C0_ESC;
 122           rt->tt_write (&ch, 1);
 123         }
 124     }
 125
 126   rt->tt_write (buf, buflen);
 127 }
 128
 129 static int
 130 format_keyrange_string (const char *str, int keysym_offset, char *buf, int bufsize)
 131 {
 132   size_t len = snprintf (buf, bufsize, str + 1, keysym_offset + str [0]);
 133
 134   if (len >= (size_t)bufsize)
 135     {
 136       rxvt_warn ("format_keyrange_string: formatting failed, ignoring key.\n");
 137       *buf = 0;
 138     }
 139
 140   return len;
 141 }
 142
 143 // return: priority_of_a - priority_of_b
 144 static int
 145 compare_priority (keysym_t *a, keysym_t *b)
 146 {
 147   // (the more '1's in state; the less range): the greater priority
 148   int ca = rxvt_popcount (a->state /* & OtherModMask */);
 149   int cb = rxvt_popcount (b->state /* & OtherModMask */);
 150
 151   if (ca != cb)
 152     return ca - cb;
 153 //else if (a->state != b->state) // this behavior is to be disscussed
 154 //  return b->state - a->state;
 155   else
 156     return b->range - a->range;
 157 }
 158
 159 ////////////////////////////////////////////////////////////////////////////////
 160 keyboard_manager::keyboard_manager ()
 161 {
 162   keymap.reserve (256);
 163   hash [0] = 1;                 // hash[0] != 0 indicates uninitialized data
 164 }
 165
 166 keyboard_manager::~keyboard_manager ()
 167 {
 168   clear ();
 169 }
 170
 171 void
 172 keyboard_manager::clear ()
 173 {
 174   keymap.clear ();
 175   hash [0] = 2;
 176
 177   for (unsigned int i = 0; i < user_translations.size (); ++i)
 178     {
 179       free ((void *)user_translations [i]);
 180       user_translations [i] = 0;
 181     }
 182
 183   for (unsigned int i = 0; i < user_keymap.size (); ++i)
 184     {
 185       delete user_keymap [i];
 186       user_keymap [i] = 0;
 187     }
 188
 189   user_keymap.clear ();
 190   user_translations.clear ();
 191 }
 192
 193 // a wrapper for register_keymap,
 194 // so that outside codes don't have to know so much details.
 195 //
 196 // the string 'trans' is copied to an internal managed buffer,
 197 // so the caller can free memory of 'trans' at any time.
 198 void
 199 keyboard_manager::register_user_translation (KeySym keysym, unsigned int state, const char *trans)
 200 {
 201   keysym_t *key = new keysym_t;
 202   wchar_t *wc = rxvt_mbstowcs (trans);
 203   char *translation = rxvt_wcstoutf8 (wc);
 204   free (wc);
 205
 206   if (key && translation)
 207     {
 208       key->keysym = keysym;
 209       key->state  = state;
 210       key->range  = 1;
 211       key->str    = translation;
 212       key->type   = keysym_t::STRING;
 213
 214       if (strncmp (translation, "list", 4) == 0 && translation [4])
 215         {
 216           char *middle = strchr  (translation + 5, translation [4]);
 217           char *suffix = strrchr (translation + 5, translation [4]);
 218
 219           if (suffix && middle && suffix > middle + 1)
 220             {
 221               key->type  = keysym_t::LIST;
 222               key->range = suffix - middle - 1;
 223
 224               memmove (translation, translation + 4, strlen (translation + 4) + 1);
 225             }
 226           else
 227             rxvt_warn ("cannot parse list-type keysym '%s', treating as normal keysym.\n", translation);
 228         }
 229       else if (strncmp (translation, "builtin:", 8) == 0)
 230         key->type = keysym_t::BUILTIN;
 231
 232       user_keymap.push_back (key);
 233       user_translations.push_back (translation);
 234       register_keymap (key);
 235     }
 236   else
 237     {
 238       delete key;
 239       free ((void *)translation);
 240       rxvt_fatal ("out of memory, aborting.\n");
 241     }
 242 }
 243
 244 void
 245 keyboard_manager::register_keymap (keysym_t *key)
 246 {
 247   if (keymap.size () == keymap.capacity ())
 248     keymap.reserve (keymap.size () * 2);
 249
 250   keymap.push_back (key);
 251   hash[0] = 3;
 252 }
 253
 254 void
 255 keyboard_manager::register_done ()
 256 {
 257 #if STOCK_KEYMAP
 258   int n = sizeof (stock_keymap) / sizeof (keysym_t);
 259
 260   //TODO: shield against repeated calls and empty keymap
 261   //if (keymap.back () != &stock_keymap[n - 1])
 262     for (int i = 0; i < n; ++i)
 263       register_keymap (&stock_keymap[i]);
 264 #endif
 265
 266   purge_duplicate_keymap ();
 267
 268   setup_hash ();
 269 }
 270
 271 bool
 272 keyboard_manager::dispatch (rxvt_term *term, KeySym keysym, unsigned int state)
 273 {
 274   assert (hash[0] == 0 && "register_done() need to be called");
 275
 276   state &= OtherModMask; // mask out uninteresting modifiers
 277
 278   if (state & term->ModMetaMask)    state |= MetaMask;
 279   if (state & term->ModNumLockMask) state |= NumLockMask;
 280   if (state & term->ModLevel3Mask)  state |= Level3Mask;
 281
 282   if (!!(term->priv_modes & PrivMode_aplKP) != !!(state & ShiftMask))
 283     state |= AppKeypadMask;
 284
 285   int index = find_keysym (keysym, state);
 286
 287   if (index >= 0)
 288     {
 289       const keysym_t &key = *keymap [index];
 290
 291       if (key.type != keysym_t::BUILTIN)
 292         {
 293           int keysym_offset = keysym - key.keysym;
 294
 295           wchar_t *wc = rxvt_utf8towcs (key.str);
 296           char *str = rxvt_wcstombs (wc);
 297           // TODO: do (some) translations, unescaping etc, here (allow \u escape etc.)
 298           free (wc);
 299
 300           switch (key.type)
 301             {
 302               case keysym_t::STRING:
 303                 output_string (term, str);
 304                 break;
 305
 306               case keysym_t::RANGE:
 307                 {
 308                   char buf[STRING_MAX];
 309
 310                   if (format_keyrange_string (str, keysym_offset, buf, sizeof (buf)) > 0)
 311                     output_string (term, buf);
 312                 }
 313                 break;
 314
 315               case keysym_t::RANGE_META8:
 316                 {
 317                   int len;
 318                   char buf[STRING_MAX];
 319
 320                   len = format_keyrange_string (str, keysym_offset, buf, sizeof (buf));
 321                   if (len > 0)
 322                     output_string_meta8 (term, state, buf, len);
 323                 }
 324                 break;
 325
 326               case keysym_t::LIST:
 327                 {
 328                   char buf[STRING_MAX];
 329
 330                   char *prefix, *middle, *suffix;
 331
 332                   prefix = str;
 333                   middle = strchr  (prefix + 1, *prefix);
 334                   suffix = strrchr (middle + 1, *prefix);
 335
 336                   memcpy (buf, prefix + 1, middle - prefix - 1);
 337                   buf [middle - prefix - 1] = middle [keysym_offset + 1];
 338                   strcpy (buf + (middle - prefix), suffix + 1);
 339
 340                   output_string (term, buf);
 341                 }
 342                 break;
 343             }
 344
 345           free (str);
 346
 347           return true;
 348         }
 349     }
 350
 351   return false;
 352 }
 353
 354 // purge duplicate keymap entries
 355 void keyboard_manager::purge_duplicate_keymap ()
 356 {
 357   for (unsigned int i = 0; i < keymap.size (); ++i)
 358     {
 359       for (unsigned int j = 0; j < i; ++j)
 360         {
 361           if (keymap [i] == keymap [j])
 362             {
 363               while (keymap [i] == keymap.back ())
 364                 keymap.pop_back ();
 365
 366               if (i < keymap.size ())
 367                 {
 368                   keymap[i] = keymap.back ();
 369                   keymap.pop_back ();
 370                 }
 371
 372               break;
 373             }
 374         }
 375     }
 376 }
 377
 378 void
 379 keyboard_manager::setup_hash ()
 380 {
 381   unsigned int i, index, hashkey;
 382   vector <keysym_t *> sorted_keymap;
 383   uint16_t hash_budget_size[KEYSYM_HASH_BUDGETS];       // size of each budget
 384   uint16_t hash_budget_counter[KEYSYM_HASH_BUDGETS];    // #elements in each budget
 385
 386   memset (hash_budget_size, 0, sizeof (hash_budget_size));
 387   memset (hash_budget_counter, 0, sizeof (hash_budget_counter));
 388
 389   // determine hash bucket size
 390   for (i = 0; i < keymap.size (); ++i)
 391     for (int j = min (keymap [i]->range, KEYSYM_HASH_BUDGETS) - 1; j >= 0; --j)
 392       {
 393         hashkey = (keymap [i]->keysym + j) & KEYSYM_HASH_MASK;
 394         ++hash_budget_size [hashkey];
 395       }
 396
 397   // now we know the size of each budget
 398   // compute the index of each budget
 399   hash [0] = 0;
 400   for (index = 0, i = 1; i < KEYSYM_HASH_BUDGETS; ++i)
 401     {
 402       index += hash_budget_size [i - 1];
 403       hash [i] = index;
 404     }
 405
 406   // and allocate just enough space
 407   sorted_keymap.insert (sorted_keymap.begin (), index + hash_budget_size [i - 1], 0);
 408
 409   // fill in sorted_keymap
 410   // it is sorted in each budget
 411   for (i = 0; i < keymap.size (); ++i)
 412     for (int j = min (keymap [i]->range, KEYSYM_HASH_BUDGETS) - 1; j >= 0; --j)
 413       {
 414         hashkey = (keymap [i]->keysym + j) & KEYSYM_HASH_MASK;
 415
 416         index = hash [hashkey] + hash_budget_counter [hashkey];
 417
 418         while (index > hash [hashkey]
 419                && compare_priority (keymap [i], sorted_keymap [index - 1]) > 0)
 420           {
 421             sorted_keymap [index] = sorted_keymap [index - 1];
 422             --index;
 423           }
 424
 425         sorted_keymap [index] = keymap [i];
 426         ++hash_budget_counter [hashkey];
 427       }
 428
 429   keymap.swap (sorted_keymap);
 430
 431 #ifdef DEBUG_STRICT
 432   // check for invariants
 433   for (i = 0; i < KEYSYM_HASH_BUDGETS; ++i)
 434     {
 435       index = hash[i];
 436       for (int j = 0; j < hash_budget_size [i]; ++j)
 437         {
 438           if (keymap [index + j]->range == 1)
 439             assert (i == (keymap [index + j]->keysym & KEYSYM_HASH_MASK));
 440
 441           if (j)
 442             assert (compare_priority (keymap [index + j - 1],
 443                     keymap [index + j]) >= 0);
 444         }
 445     }
 446
 447   // this should be able to detect most possible bugs
 448   for (i = 0; i < sorted_keymap.size (); ++i)
 449     {
 450       keysym_t *a = sorted_keymap[i];
 451       for (int j = 0; j < a->range; ++j)
 452         {
 453           int index = find_keysym (a->keysym + j, a->state);
 454
 455           assert (index >= 0);
 456           keysym_t *b = keymap [index];
 457           assert (i == index    // the normally expected result
 458                   || IN_RANGE_INC (a->keysym + j, b->keysym, b->keysym + b->range)
 459                   && compare_priority (a, b) <= 0);     // is effectively the same or a closer match
 460         }
 461     }
 462 #endif
 463 }
 464
 465 int
 466 keyboard_manager::find_keysym (KeySym keysym, unsigned int state)
 467 {
 468   int hashkey = keysym & KEYSYM_HASH_MASK;
 469   unsigned int index = hash [hashkey];
 470   unsigned int end = hashkey < KEYSYM_HASH_BUDGETS - 1
 471                      ? hash [hashkey + 1]
 472                      : keymap.size ();
 473
 474   for (; index < end; ++index)
 475     {
 476       keysym_t *key = keymap [index];
 477
 478       if (key->keysym <= keysym && keysym < key->keysym + key->range
 479           // match only the specified bits in state and ignore others
 480           && (key->state & state) == key->state)
 481         return index;
 482     }
 483
 484   return -1;
 485 }
 486
 487 #endif /* KEYSYM_RESOURCE */
 488 // vim:et:ts=2:sw=2