node_modules/node-pty/deps/winpty/src/agent/InputMap.cc

   1 // Copyright (c) 2011-2015 Ryan Prichard
   2 //
   3 // Permission is hereby granted, free of charge, to any person obtaining a copy
   4 // of this software and associated documentation files (the "Software"), to
   5 // deal in the Software without restriction, including without limitation the
   6 // rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
   7 // sell copies of the Software, and to permit persons to whom the Software is
   8 // furnished to do so, subject to the following conditions:
   9 //
  10 // The above copyright notice and this permission notice shall be included in
  11 // all copies or substantial portions of the Software.
  12 //
  13 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  14 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  15 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  16 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  17 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
  18 // FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
  19 // IN THE SOFTWARE.
  20
  21 #include "InputMap.h"
  22
  23 #include <windows.h>
  24 #include <stdio.h>
  25 #include <stdlib.h>
  26 #include <string.h>
  27
  28 #include "DebugShowInput.h"
  29 #include "SimplePool.h"
  30 #include "../shared/DebugClient.h"
  31 #include "../shared/UnixCtrlChars.h"
  32 #include "../shared/WinptyAssert.h"
  33 #include "../shared/winpty_snprintf.h"
  34
  35 namespace {
  36
  37 static const char *getVirtualKeyString(int virtualKey)
  38 {
  39     switch (virtualKey) {
  40 #define WINPTY_GVKS_KEY(x) case VK_##x: return #x;
  41         WINPTY_GVKS_KEY(RBUTTON)    WINPTY_GVKS_KEY(F9)
  42         WINPTY_GVKS_KEY(CANCEL)     WINPTY_GVKS_KEY(F10)
  43         WINPTY_GVKS_KEY(MBUTTON)    WINPTY_GVKS_KEY(F11)
  44         WINPTY_GVKS_KEY(XBUTTON1)   WINPTY_GVKS_KEY(F12)
  45         WINPTY_GVKS_KEY(XBUTTON2)   WINPTY_GVKS_KEY(F13)
  46         WINPTY_GVKS_KEY(BACK)       WINPTY_GVKS_KEY(F14)
  47         WINPTY_GVKS_KEY(TAB)        WINPTY_GVKS_KEY(F15)
  48         WINPTY_GVKS_KEY(CLEAR)      WINPTY_GVKS_KEY(F16)
  49         WINPTY_GVKS_KEY(RETURN)     WINPTY_GVKS_KEY(F17)
  50         WINPTY_GVKS_KEY(SHIFT)      WINPTY_GVKS_KEY(F18)
  51         WINPTY_GVKS_KEY(CONTROL)    WINPTY_GVKS_KEY(F19)
  52         WINPTY_GVKS_KEY(MENU)       WINPTY_GVKS_KEY(F20)
  53         WINPTY_GVKS_KEY(PAUSE)      WINPTY_GVKS_KEY(F21)
  54         WINPTY_GVKS_KEY(CAPITAL)    WINPTY_GVKS_KEY(F22)
  55         WINPTY_GVKS_KEY(HANGUL)     WINPTY_GVKS_KEY(F23)
  56         WINPTY_GVKS_KEY(JUNJA)      WINPTY_GVKS_KEY(F24)
  57         WINPTY_GVKS_KEY(FINAL)      WINPTY_GVKS_KEY(NUMLOCK)
  58         WINPTY_GVKS_KEY(KANJI)      WINPTY_GVKS_KEY(SCROLL)
  59         WINPTY_GVKS_KEY(ESCAPE)     WINPTY_GVKS_KEY(LSHIFT)
  60         WINPTY_GVKS_KEY(CONVERT)    WINPTY_GVKS_KEY(RSHIFT)
  61         WINPTY_GVKS_KEY(NONCONVERT) WINPTY_GVKS_KEY(LCONTROL)
  62         WINPTY_GVKS_KEY(ACCEPT)     WINPTY_GVKS_KEY(RCONTROL)
  63         WINPTY_GVKS_KEY(MODECHANGE) WINPTY_GVKS_KEY(LMENU)
  64         WINPTY_GVKS_KEY(SPACE)      WINPTY_GVKS_KEY(RMENU)
  65         WINPTY_GVKS_KEY(PRIOR)      WINPTY_GVKS_KEY(BROWSER_BACK)
  66         WINPTY_GVKS_KEY(NEXT)       WINPTY_GVKS_KEY(BROWSER_FORWARD)
  67         WINPTY_GVKS_KEY(END)        WINPTY_GVKS_KEY(BROWSER_REFRESH)
  68         WINPTY_GVKS_KEY(HOME)       WINPTY_GVKS_KEY(BROWSER_STOP)
  69         WINPTY_GVKS_KEY(LEFT)       WINPTY_GVKS_KEY(BROWSER_SEARCH)
  70         WINPTY_GVKS_KEY(UP)         WINPTY_GVKS_KEY(BROWSER_FAVORITES)
  71         WINPTY_GVKS_KEY(RIGHT)      WINPTY_GVKS_KEY(BROWSER_HOME)
  72         WINPTY_GVKS_KEY(DOWN)       WINPTY_GVKS_KEY(VOLUME_MUTE)
  73         WINPTY_GVKS_KEY(SELECT)     WINPTY_GVKS_KEY(VOLUME_DOWN)
  74         WINPTY_GVKS_KEY(PRINT)      WINPTY_GVKS_KEY(VOLUME_UP)
  75         WINPTY_GVKS_KEY(EXECUTE)    WINPTY_GVKS_KEY(MEDIA_NEXT_TRACK)
  76         WINPTY_GVKS_KEY(SNAPSHOT)   WINPTY_GVKS_KEY(MEDIA_PREV_TRACK)
  77         WINPTY_GVKS_KEY(INSERT)     WINPTY_GVKS_KEY(MEDIA_STOP)
  78         WINPTY_GVKS_KEY(DELETE)     WINPTY_GVKS_KEY(MEDIA_PLAY_PAUSE)
  79         WINPTY_GVKS_KEY(HELP)       WINPTY_GVKS_KEY(LAUNCH_MAIL)
  80         WINPTY_GVKS_KEY(LWIN)       WINPTY_GVKS_KEY(LAUNCH_MEDIA_SELECT)
  81         WINPTY_GVKS_KEY(RWIN)       WINPTY_GVKS_KEY(LAUNCH_APP1)
  82         WINPTY_GVKS_KEY(APPS)       WINPTY_GVKS_KEY(LAUNCH_APP2)
  83         WINPTY_GVKS_KEY(SLEEP)      WINPTY_GVKS_KEY(OEM_1)
  84         WINPTY_GVKS_KEY(NUMPAD0)    WINPTY_GVKS_KEY(OEM_PLUS)
  85         WINPTY_GVKS_KEY(NUMPAD1)    WINPTY_GVKS_KEY(OEM_COMMA)
  86         WINPTY_GVKS_KEY(NUMPAD2)    WINPTY_GVKS_KEY(OEM_MINUS)
  87         WINPTY_GVKS_KEY(NUMPAD3)    WINPTY_GVKS_KEY(OEM_PERIOD)
  88         WINPTY_GVKS_KEY(NUMPAD4)    WINPTY_GVKS_KEY(OEM_2)
  89         WINPTY_GVKS_KEY(NUMPAD5)    WINPTY_GVKS_KEY(OEM_3)
  90         WINPTY_GVKS_KEY(NUMPAD6)    WINPTY_GVKS_KEY(OEM_4)
  91         WINPTY_GVKS_KEY(NUMPAD7)    WINPTY_GVKS_KEY(OEM_5)
  92         WINPTY_GVKS_KEY(NUMPAD8)    WINPTY_GVKS_KEY(OEM_6)
  93         WINPTY_GVKS_KEY(NUMPAD9)    WINPTY_GVKS_KEY(OEM_7)
  94         WINPTY_GVKS_KEY(MULTIPLY)   WINPTY_GVKS_KEY(OEM_8)
  95         WINPTY_GVKS_KEY(ADD)        WINPTY_GVKS_KEY(OEM_102)
  96         WINPTY_GVKS_KEY(SEPARATOR)  WINPTY_GVKS_KEY(PROCESSKEY)
  97         WINPTY_GVKS_KEY(SUBTRACT)   WINPTY_GVKS_KEY(PACKET)
  98         WINPTY_GVKS_KEY(DECIMAL)    WINPTY_GVKS_KEY(ATTN)
  99         WINPTY_GVKS_KEY(DIVIDE)     WINPTY_GVKS_KEY(CRSEL)
 100         WINPTY_GVKS_KEY(F1)         WINPTY_GVKS_KEY(EXSEL)
 101         WINPTY_GVKS_KEY(F2)         WINPTY_GVKS_KEY(EREOF)
 102         WINPTY_GVKS_KEY(F3)         WINPTY_GVKS_KEY(PLAY)
 103         WINPTY_GVKS_KEY(F4)         WINPTY_GVKS_KEY(ZOOM)
 104         WINPTY_GVKS_KEY(F5)         WINPTY_GVKS_KEY(NONAME)
 105         WINPTY_GVKS_KEY(F6)         WINPTY_GVKS_KEY(PA1)
 106         WINPTY_GVKS_KEY(F7)         WINPTY_GVKS_KEY(OEM_CLEAR)
 107         WINPTY_GVKS_KEY(F8)
 108 #undef WINPTY_GVKS_KEY
 109         default:                        return NULL;
 110     }
 111 }
 112
 113 } // anonymous namespace
 114
 115 std::string InputMap::Key::toString() const {
 116     std::string ret;
 117     ret += controlKeyStatePrefix(keyState);
 118     char buf[256];
 119     const char *vkString = getVirtualKeyString(virtualKey);
 120     if (vkString != NULL) {
 121         ret += vkString;
 122     } else if ((virtualKey >= 'A' && virtualKey <= 'Z') ||
 123                (virtualKey >= '0' && virtualKey <= '9')) {
 124         ret += static_cast<char>(virtualKey);
 125     } else {
 126         winpty_snprintf(buf, "%#x", virtualKey);
 127         ret += buf;
 128     }
 129     if (unicodeChar >= 32 && unicodeChar <= 126) {
 130         winpty_snprintf(buf, " ch='%c'",
 131                         static_cast<char>(unicodeChar));
 132     } else {
 133         winpty_snprintf(buf, " ch=%#x",
 134                         static_cast<unsigned int>(unicodeChar));
 135     }
 136     ret += buf;
 137     return ret;
 138 }
 139
 140 void InputMap::set(const char *encoding, int encodingLen, const Key &key) {
 141     ASSERT(encodingLen > 0);
 142     setHelper(m_root, encoding, encodingLen, key);
 143 }
 144
 145 void InputMap::setHelper(Node &node, const char *encoding, int encodingLen, const Key &key) {
 146     if (encodingLen == 0) {
 147         node.key = key;
 148     } else {
 149         setHelper(getOrCreateChild(node, encoding[0]), encoding + 1, encodingLen - 1, key);
 150     }
 151 }
 152
 153 InputMap::Node &InputMap::getOrCreateChild(Node &node, unsigned char ch) {
 154     Node *ret = getChild(node, ch);
 155     if (ret != NULL) {
 156         return *ret;
 157     }
 158     if (node.childCount < Node::kTinyCount) {
 159         // Maintain sorted order for the sake of the InputMap dumping.
 160         int insertIndex = node.childCount;
 161         for (int i = 0; i < node.childCount; ++i) {
 162             if (ch < node.u.tiny.values[i]) {
 163                 insertIndex = i;
 164                 break;
 165             }
 166         }
 167         for (int j = node.childCount; j > insertIndex; --j) {
 168             node.u.tiny.values[j] = node.u.tiny.values[j - 1];
 169             node.u.tiny.children[j] = node.u.tiny.children[j - 1];
 170         }
 171         node.u.tiny.values[insertIndex] = ch;
 172         node.u.tiny.children[insertIndex] = ret = m_nodePool.alloc();
 173         ++node.childCount;
 174         return *ret;
 175     }
 176     if (node.childCount == Node::kTinyCount) {
 177         Branch *branch = m_branchPool.alloc();
 178         for (int i = 0; i < node.childCount; ++i) {
 179             branch->children[node.u.tiny.values[i]] = node.u.tiny.children[i];
 180         }
 181         node.u.branch = branch;
 182     }
 183     node.u.branch->children[ch] = ret = m_nodePool.alloc();
 184     ++node.childCount;
 185     return *ret;
 186 }
 187
 188 // Find the longest matching key and node.
 189 int InputMap::lookupKey(const char *input, int inputSize,
 190                         Key &keyOut, bool &incompleteOut) const {
 191     keyOut = kKeyZero;
 192     incompleteOut = false;
 193
 194     const Node *node = &m_root;
 195     InputMap::Key longestMatch = kKeyZero;
 196     int longestMatchLen = 0;
 197
 198     for (int i = 0; i < inputSize; ++i) {
 199         unsigned char ch = input[i];
 200         node = getChild(*node, ch);
 201         if (node == NULL) {
 202             keyOut = longestMatch;
 203             return longestMatchLen;
 204         } else if (node->hasKey()) {
 205             longestMatchLen = i + 1;
 206             longestMatch = node->key;
 207         }
 208     }
 209     keyOut = longestMatch;
 210     incompleteOut = node->childCount > 0;
 211     return longestMatchLen;
 212 }
 213
 214 void InputMap::dumpInputMap() const {
 215     std::string encoding;
 216     dumpInputMapHelper(m_root, encoding);
 217 }
 218
 219 void InputMap::dumpInputMapHelper(
 220         const Node &node, std::string &encoding) const {
 221     if (node.hasKey()) {
 222         trace("%s -> %s",
 223             encoding.c_str(),
 224             node.key.toString().c_str());
 225     }
 226     for (int i = 0; i < 256; ++i) {
 227         const Node *child = getChild(node, i);
 228         if (child != NULL) {
 229             size_t oldSize = encoding.size();
 230             if (!encoding.empty()) {
 231                 encoding.push_back(' ');
 232             }
 233             char ctrlChar = decodeUnixCtrlChar(i);
 234             if (ctrlChar != '\0') {
 235                 encoding.push_back('^');
 236                 encoding.push_back(static_cast<char>(ctrlChar));
 237             } else if (i == ' ') {
 238                 encoding.append("' '");
 239             } else {
 240                 encoding.push_back(static_cast<char>(i));
 241             }
 242             dumpInputMapHelper(*child, encoding);
 243             encoding.resize(oldSize);
 244         }
 245     }
 246 }