CKeyMap.cpp

/*
 * synergy -- mouse and keyboard sharing utility
 * Copyright (C) 2012 Bolton Software Ltd.
 * Copyright (C) 2005 Chris Schoeneman
 * 
 * This package is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License
 * found in the file COPYING that should have accompanied this file.
 * 
 * This package is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#include "CKeyMap.h"
#include "KeyTypes.h"
#include "CLog.h"
#include <assert.h>
#include <cctype>
#include <cstdlib>

CKeyMap::CNameToKeyMap*         CKeyMap::s_nameToKeyMap      = NULL;
CKeyMap::CNameToModifierMap*    CKeyMap::s_nameToModifierMap = NULL;
CKeyMap::CKeyToNameMap*         CKeyMap::s_keyToNameMap      = NULL;
CKeyMap::CModifierToNameMap*    CKeyMap::s_modifierToNameMap = NULL;

CKeyMap::CKeyMap() :
    m_numGroups(0),
    m_composeAcrossGroups(false)
{
    m_modifierKeyItem.m_id        = kKeyNone;
    m_modifierKeyItem.m_group     = 0;
    m_modifierKeyItem.m_button    = 0;
    m_modifierKeyItem.m_required  = 0;
    m_modifierKeyItem.m_sensitive = 0;
    m_modifierKeyItem.m_generates = 0;
    m_modifierKeyItem.m_dead      = false;
    m_modifierKeyItem.m_lock      = false;
    m_modifierKeyItem.m_client    = 0;
}

CKeyMap::~CKeyMap()
{
    // do nothing
}

void
CKeyMap::swap(CKeyMap& x)
{
    m_keyIDMap.swap(x.m_keyIDMap);
    m_modifierKeys.swap(x.m_modifierKeys);
    m_halfDuplex.swap(x.m_halfDuplex);
    m_halfDuplexMods.swap(x.m_halfDuplexMods);
    SInt32 tmp1   = m_numGroups;
    m_numGroups   = x.m_numGroups;
    x.m_numGroups = tmp1;
    bool tmp2               = m_composeAcrossGroups;
    m_composeAcrossGroups   = x.m_composeAcrossGroups;
    x.m_composeAcrossGroups = tmp2;
}

void
CKeyMap::addKeyEntry(const KeyItem& item)
{
    // ignore kKeyNone
    if (item.m_id == kKeyNone) {
        return;
    }

    // resize number of groups for key
    SInt32 numGroups = item.m_group + 1;
    if (getNumGroups() > numGroups) {
        numGroups = getNumGroups();
    }
    KeyGroupTable& groupTable = m_keyIDMap[item.m_id];
    if (groupTable.size() < static_cast<size_t>(numGroups)) {
        groupTable.resize(numGroups);
    }

    // make a list from the item
    KeyItemList items;
    items.push_back(item);

    // set group and dead key flag on the item
    KeyItem& newItem = items.back();
    newItem.m_dead   = isDeadKey(item.m_id);

    // mask the required bits with the sensitive bits
    newItem.m_required &= newItem.m_sensitive;

    // see if we already have this item;  just return if so
    KeyEntryList& entries = groupTable[item.m_group];
    for (size_t i = 0, n = entries.size(); i < n; ++i) {
        if (entries[i].size() == 1 && newItem == entries[i][0]) {
            return;
        }
    }

    // add item list
    entries.push_back(items);
    LOG((CLOG_DEBUG5 "add key: %04x %d %03x %04x (%04x %04x %04x)%s", newItem.m_id, newItem.m_group, newItem.m_button, newItem.m_client, newItem.m_required, newItem.m_sensitive, newItem.m_generates, newItem.m_dead ? " dead" : ""));
}

void
CKeyMap::addKeyAliasEntry(KeyID targetID, SInt32 group,
                KeyModifierMask targetRequired,
                KeyModifierMask targetSensitive,
                KeyID sourceID,
                KeyModifierMask sourceRequired,
                KeyModifierMask sourceSensitive)
{
    // if we can already generate the target as desired then we're done.
    if (findCompatibleKey(targetID, group, targetRequired,
                                targetSensitive) != NULL) {
        return;
    }

    // find a compatible source, preferably in the same group
    for (SInt32 gd = 0, n = getNumGroups(); gd < n; ++gd) {
        SInt32 eg = getEffectiveGroup(group, gd);
        const KeyItemList* sourceEntry =
            findCompatibleKey(sourceID, eg,
                                sourceRequired, sourceSensitive);
        if (sourceEntry != NULL && sourceEntry->size() == 1) {
            CKeyMap::KeyItem targetItem = sourceEntry->back();
            targetItem.m_id    = targetID;
            targetItem.m_group = eg;
            addKeyEntry(targetItem);
            break;
        }
    }
}

bool
CKeyMap::addKeyCombinationEntry(KeyID id, SInt32 group,
                const KeyID* keys, UInt32 numKeys)
{
    // disallow kKeyNone
    if (id == kKeyNone) {
        return false;
    }

    SInt32 numGroups = group + 1;
    if (getNumGroups() > numGroups) {
        numGroups = getNumGroups();
    }
    KeyGroupTable& groupTable = m_keyIDMap[id];
    if (groupTable.size() < static_cast<size_t>(numGroups)) {
        groupTable.resize(numGroups);
    }
    if (!groupTable[group].empty()) {
        // key is already in the table
        return false;
    }

    // convert to buttons
    KeyItemList items;
    for (UInt32 i = 0; i < numKeys; ++i) {
        KeyIDMap::const_iterator gtIndex = m_keyIDMap.find(keys[i]);
        if (gtIndex == m_keyIDMap.end()) {
            return false;
        }
        const KeyGroupTable& groupTable = gtIndex->second;

        // if we allow group switching during composition then search all
        // groups for keys, otherwise search just the given group.
        SInt32 n = 1;
        if (m_composeAcrossGroups) {
            n = (SInt32)groupTable.size();
        }

        bool found = false;
        for (SInt32 gd = 0; gd < n && !found; ++gd) {
            SInt32 eg = (group + gd) % getNumGroups();
            const KeyEntryList& entries = groupTable[eg];
            for (size_t j = 0; j < entries.size(); ++j) {
                if (entries[j].size() == 1) {
                    found = true;
                    items.push_back(entries[j][0]);
                    break;
                }
            }
        }
        if (!found) {
            // required key is not in keyboard group
            return false;
        }
    }

    // add key
    groupTable[group].push_back(items);
    return true;
}

void
CKeyMap::allowGroupSwitchDuringCompose()
{
    m_composeAcrossGroups = true;
}

void
CKeyMap::addHalfDuplexButton(KeyButton button)
{
    m_halfDuplex.insert(button);
}

void
CKeyMap::clearHalfDuplexModifiers()
{
    m_halfDuplexMods.clear();
}

void
CKeyMap::addHalfDuplexModifier(KeyID key)
{
    m_halfDuplexMods.insert(key);
}

void
CKeyMap::finish()
{
    m_numGroups = findNumGroups();

    // make sure every key has the same number of groups
    for (KeyIDMap::iterator i = m_keyIDMap.begin();
                                i != m_keyIDMap.end(); ++i) {
        i->second.resize(m_numGroups);
    }

    // compute keys that generate each modifier
    setModifierKeys();
}

void
CKeyMap::foreachKey(ForeachKeyCallback cb, void* userData)
{
    for (KeyIDMap::iterator i = m_keyIDMap.begin();
                                i != m_keyIDMap.end(); ++i) {
        KeyGroupTable& groupTable = i->second;
        for (size_t group = 0; group < groupTable.size(); ++group) {
            KeyEntryList& entryList = groupTable[group];
            for (size_t j = 0; j < entryList.size(); ++j) {
                KeyItemList& itemList = entryList[j];
                for (size_t k = 0; k < itemList.size(); ++k) {
                    (*cb)(i->first, static_cast<SInt32>(group),
                                itemList[k], userData);
                }
            }
        }
    }
}

const CKeyMap::KeyItem*
CKeyMap::mapKey(Keystrokes& keys, KeyID id, SInt32 group,
                ModifierToKeys& activeModifiers,
                KeyModifierMask& currentState,
                KeyModifierMask desiredMask,
                bool isAutoRepeat) const
{
    LOG((CLOG_DEBUG1 "mapKey %04x (%d) with mask %04x, start state: %04x", id, id, desiredMask, currentState));

    // handle group change
    if (id == kKeyNextGroup) {
        keys.push_back(Keystroke(1, false, false));
        return NULL;
    }
    else if (id == kKeyPrevGroup) {
        keys.push_back(Keystroke(-1, false, false));
        return NULL;
    }

    const KeyItem* item;
    switch (id) {
    case kKeyShift_L:
    case kKeyShift_R:
    case kKeyControl_L:
    case kKeyControl_R:
    case kKeyAlt_L:
    case kKeyAlt_R:
    case kKeyMeta_L:
    case kKeyMeta_R:
    case kKeySuper_L:
    case kKeySuper_R:
    case kKeyAltGr:
    case kKeyCapsLock:
    case kKeyNumLock:
    case kKeyScrollLock:
        item = mapModifierKey(keys, id, group, activeModifiers,
                                currentState, desiredMask, isAutoRepeat);
        break;

    case kKeySetModifiers:
        if (!keysForModifierState(0, group, activeModifiers, currentState,
                                desiredMask, desiredMask, 0, keys)) {
            LOG((CLOG_DEBUG1 "unable to set modifiers %04x", desiredMask));
            return NULL;
        }
        return &m_modifierKeyItem;

    case kKeyClearModifiers:
        if (!keysForModifierState(0, group, activeModifiers, currentState,
                                currentState & ~desiredMask,
                                desiredMask, 0, keys)) {
            LOG((CLOG_DEBUG1 "unable to clear modifiers %04x", desiredMask));
            return NULL;
        }
        return &m_modifierKeyItem;

    default:
        if (isCommand(desiredMask)) {
            item = mapCommandKey(keys, id, group, activeModifiers,
                                currentState, desiredMask, isAutoRepeat);
        }
        else {
            item = mapCharacterKey(keys, id, group, activeModifiers,
                                currentState, desiredMask, isAutoRepeat);
        }
        break;
    }

    if (item != NULL) {
        LOG((CLOG_DEBUG1 "mapped to %03x, new state %04x", item->m_button, currentState));
    }
    return item;
}

SInt32
CKeyMap::getNumGroups() const
{
    return m_numGroups;
}

SInt32
CKeyMap::getEffectiveGroup(SInt32 group, SInt32 offset) const
{
    return (group + offset + getNumGroups()) % getNumGroups();
}

const CKeyMap::KeyItemList*
CKeyMap::findCompatibleKey(KeyID id, SInt32 group,
                KeyModifierMask required, KeyModifierMask sensitive) const
{
    assert(group >= 0 && group < getNumGroups());

    KeyIDMap::const_iterator i = m_keyIDMap.find(id);
    if (i == m_keyIDMap.end()) {
        return NULL;
    }

    const KeyEntryList& entries = i->second[group];
    for (size_t j = 0; j < entries.size(); ++j) {
        if ((entries[j].back().m_sensitive & sensitive) == 0 ||
            (entries[j].back().m_required & sensitive) ==
                (required & sensitive)) {
            return &entries[j];
        }
    }

    return NULL;
}

bool
CKeyMap::isHalfDuplex(KeyID key, KeyButton button) const
{
    return (m_halfDuplex.count(button) + m_halfDuplexMods.count(key) > 0);
}

bool
CKeyMap::isCommand(KeyModifierMask mask) const
{
    return ((mask & getCommandModifiers()) != 0);
}

KeyModifierMask
CKeyMap::getCommandModifiers() const
{
    // we currently treat ctrl, alt, meta and super as command modifiers.
    // some platforms may have a more limited set (OS X only needs Alt)
    // but this works anyway.
    return KeyModifierControl |
            KeyModifierAlt    |
            KeyModifierAltGr  |
            KeyModifierMeta   |
            KeyModifierSuper;
}

void
CKeyMap::collectButtons(const ModifierToKeys& mods, ButtonToKeyMap& keys)
{
    keys.clear();
    for (ModifierToKeys::const_iterator i = mods.begin();
                                i != mods.end(); ++i) {
        keys.insert(std::make_pair(i->second.m_button, &i->second));
    }
}

void
CKeyMap::initModifierKey(KeyItem& item)
{
    item.m_generates = 0;
    item.m_lock      = false;
    switch (item.m_id) {
    case kKeyShift_L:
    case kKeyShift_R:
        item.m_generates = KeyModifierShift;
        break;

    case kKeyControl_L:
    case kKeyControl_R:
        item.m_generates = KeyModifierControl;
        break;

    case kKeyAlt_L:
    case kKeyAlt_R:
        item.m_generates = KeyModifierAlt;
        break;

    case kKeyMeta_L:
    case kKeyMeta_R:
        item.m_generates = KeyModifierMeta;
        break;

    case kKeySuper_L:
    case kKeySuper_R:
        item.m_generates = KeyModifierSuper;
        break;

    case kKeyAltGr:
        item.m_generates = KeyModifierAltGr;
        break;

    case kKeyCapsLock:
        item.m_generates = KeyModifierCapsLock;
        item.m_lock      = true;
        break;

    case kKeyNumLock:
        item.m_generates = KeyModifierNumLock;
        item.m_lock      = true;
        break;

    case kKeyScrollLock:
        item.m_generates = KeyModifierScrollLock;
        item.m_lock      = true;
        break;

    default:
        // not a modifier
        break;
    }
}

SInt32
CKeyMap::findNumGroups() const
{
    size_t max = 0;
    for (KeyIDMap::const_iterator i = m_keyIDMap.begin();
                                i != m_keyIDMap.end(); ++i) {
        if (i->second.size() > max) {
            max = i->second.size();
        }
    }
    return static_cast<SInt32>(max);
}

void
CKeyMap::setModifierKeys()
{
    m_modifierKeys.clear();
    m_modifierKeys.resize(kKeyModifierNumBits * getNumGroups());
    for (KeyIDMap::const_iterator i = m_keyIDMap.begin();
                                i != m_keyIDMap.end(); ++i) {
        const KeyGroupTable& groupTable = i->second;
        for (size_t g = 0; g < groupTable.size(); ++g) {
            const KeyEntryList& entries = groupTable[g];
            for (size_t j = 0; j < entries.size(); ++j) {
                // skip multi-key sequences
                if (entries[j].size() != 1) {
                    continue;
                }

                // skip keys that don't generate a modifier
                const KeyItem& item = entries[j].back();
                if (item.m_generates == 0) {
                    continue;
                }

                // add key to each indicated modifier in this group
                for (SInt32 b = 0; b < kKeyModifierNumBits; ++b) {
                    // skip if item doesn't generate bit b
                    if (((1u << b) & item.m_generates) != 0) {
                        SInt32 mIndex = (SInt32)g * kKeyModifierNumBits + b;
                        m_modifierKeys[mIndex].push_back(&item);
                    }
                }
            }
        }
    }
}

const CKeyMap::KeyItem*
CKeyMap::mapCommandKey(Keystrokes& keys, KeyID id, SInt32 group,
                ModifierToKeys& activeModifiers,
                KeyModifierMask& currentState,
                KeyModifierMask desiredMask,
                bool isAutoRepeat) const
{
    static const KeyModifierMask s_overrideModifiers = 0xffffu;

    // find KeySym in table
    KeyIDMap::const_iterator i = m_keyIDMap.find(id);
    if (i == m_keyIDMap.end()) {
        // unknown key
        LOG((CLOG_DEBUG1 "key %04x is not on keyboard", id));
        return NULL;
    }
    const KeyGroupTable& keyGroupTable = i->second;

    // find the first key that generates this KeyID
    const KeyItem* keyItem = NULL;
    SInt32 numGroups       = getNumGroups();
    for (SInt32 groupOffset = 0; groupOffset < numGroups; ++groupOffset) {
        SInt32 effectiveGroup = getEffectiveGroup(group, groupOffset);
        const KeyEntryList& entryList = keyGroupTable[effectiveGroup];
        for (size_t i = 0; i < entryList.size(); ++i) {
            if (entryList[i].size() != 1) {
                // ignore multikey entries
                continue;
            }

            // only match based on shift;  we're after the right button
            // not the right character.  we'll use desiredMask as-is,
            // overriding the key's required modifiers, when synthesizing
            // this button.
            const KeyItem& item = entryList[i].back();
            if ((item.m_required & KeyModifierShift & desiredMask) ==
                (item.m_sensitive & KeyModifierShift & desiredMask)) {
                LOG((CLOG_DEBUG1 "found key in group %d", effectiveGroup));
                keyItem = &item;
                break;
            }
        }
        if (keyItem != NULL) {
            break;
        }
    }
    if (keyItem == NULL) {
        // no mapping for this keysym
        LOG((CLOG_DEBUG1 "no mapping for key %04x", id));
        return NULL;
    }

    // make working copy of modifiers
    ModifierToKeys newModifiers = activeModifiers;
    KeyModifierMask newState    = currentState;
    SInt32 newGroup             = group;

    // don't try to change CapsLock
    desiredMask = (desiredMask & ~KeyModifierCapsLock) |
                    (currentState & KeyModifierCapsLock);

    // add the key
    if (!keysForKeyItem(*keyItem, newGroup, newModifiers,
                            newState, desiredMask,
                            s_overrideModifiers, isAutoRepeat, keys)) {
        LOG((CLOG_DEBUG1 "can't map key"));
        keys.clear();
        return NULL;
    }

    // add keystrokes to restore modifier keys
    if (!keysToRestoreModifiers(*keyItem, group, newModifiers, newState,
                                activeModifiers, keys)) {
        LOG((CLOG_DEBUG1 "failed to restore modifiers"));
        keys.clear();
        return NULL;
    }

    // add keystrokes to restore group
    if (newGroup != group) {
        keys.push_back(Keystroke(group, true, true));
    }

    // save new modifiers
    activeModifiers = newModifiers;
    currentState    = newState;

    return keyItem;
}

const CKeyMap::KeyItem*
CKeyMap::mapCharacterKey(Keystrokes& keys, KeyID id, SInt32 group,
                ModifierToKeys& activeModifiers,
                KeyModifierMask& currentState,
                KeyModifierMask desiredMask,
                bool isAutoRepeat) const
{
    // find KeySym in table
    KeyIDMap::const_iterator i = m_keyIDMap.find(id);
    if (i == m_keyIDMap.end()) {
        // unknown key
        LOG((CLOG_DEBUG1 "key %04x is not on keyboard", id));
        return NULL;
    }
    const KeyGroupTable& keyGroupTable = i->second;

    // find best key in any group, starting with the active group
    SInt32 keyIndex  = -1;
    SInt32 numGroups = getNumGroups();
    SInt32 groupOffset;
    LOG((CLOG_DEBUG1 "find best:  %04x %04x", currentState, desiredMask));
    for (groupOffset = 0; groupOffset < numGroups; ++groupOffset) {
        SInt32 effectiveGroup = getEffectiveGroup(group, groupOffset);
        keyIndex = findBestKey(keyGroupTable[effectiveGroup],
                                currentState, desiredMask);
        if (keyIndex != -1) {
            LOG((CLOG_DEBUG1 "found key in group %d", effectiveGroup));
            break;
        }
    }
    if (keyIndex == -1) {
        // no mapping for this keysym
        LOG((CLOG_DEBUG1 "no mapping for key %04x", id));
        return NULL;
    }

    // get keys to press for key
    SInt32 effectiveGroup = getEffectiveGroup(group, groupOffset);
    const KeyItemList& itemList = keyGroupTable[effectiveGroup][keyIndex];
    if (itemList.empty()) {
        return NULL;
    }
    const KeyItem& keyItem = itemList.back();

    // make working copy of modifiers
    ModifierToKeys newModifiers = activeModifiers;
    KeyModifierMask newState    = currentState;
    SInt32 newGroup             = group;

    // add each key
    for (size_t j = 0; j < itemList.size(); ++j) {
        if (!keysForKeyItem(itemList[j], newGroup, newModifiers,
                            newState, desiredMask,
                            0, isAutoRepeat, keys)) {
            LOG((CLOG_DEBUG1 "can't map key"));
            keys.clear();
            return NULL;
        }
    }

    // add keystrokes to restore modifier keys
    if (!keysToRestoreModifiers(keyItem, group, newModifiers, newState,
                                activeModifiers, keys)) {
        LOG((CLOG_DEBUG1 "failed to restore modifiers"));
        keys.clear();
        return NULL;
    }

    // add keystrokes to restore group
    if (newGroup != group) {
        keys.push_back(Keystroke(group, true, true));
    }

    // save new modifiers
    activeModifiers = newModifiers;
    currentState    = newState;

    return &keyItem;
}

const CKeyMap::KeyItem*
CKeyMap::mapModifierKey(Keystrokes& keys, KeyID id, SInt32 group,
                ModifierToKeys& activeModifiers,
                KeyModifierMask& currentState,
                KeyModifierMask desiredMask,
                bool isAutoRepeat) const
{
    return mapCharacterKey(keys, id, group, activeModifiers,
                                currentState, desiredMask, isAutoRepeat);
}

SInt32
CKeyMap::findBestKey(const KeyEntryList& entryList,
                KeyModifierMask /*currentState*/,
                KeyModifierMask desiredState) const
{
    // check for an item that can accommodate the desiredState exactly
    for (SInt32 i = 0; i < (SInt32)entryList.size(); ++i) {
        const KeyItem& item = entryList[i].back();
        if ((item.m_required & desiredState) ==
            (item.m_sensitive & desiredState)) {
            LOG((CLOG_DEBUG1 "best key index %d of %d (exact)", i, entryList.size()));
            return i;
        }
    }

    // choose the item that requires the fewest modifier changes
    SInt32 bestCount = 32;
    SInt32 bestIndex = -1;
    for (SInt32 i = 0; i < (SInt32)entryList.size(); ++i) {
        const KeyItem& item = entryList[i].back();
        KeyModifierMask change =
            ((item.m_required ^ desiredState) & item.m_sensitive);
        SInt32 n = getNumModifiers(change);
        if (n < bestCount) {
            bestCount = n;
            bestIndex = i;
        }
    }
    if (bestIndex != -1) {
        LOG((CLOG_DEBUG1 "best key index %d of %d (%d modifiers)", bestIndex, entryList.size(), bestCount));
    }

    return bestIndex;
}


const CKeyMap::KeyItem*
CKeyMap::keyForModifier(KeyButton button, SInt32 group,
                SInt32 modifierBit) const
{
    assert(modifierBit >= 0 && modifierBit < kKeyModifierNumBits);
    assert(group >= 0 && group < getNumGroups());

    // find a key that generates the given modifier in the given group 
    // but doesn't use the given button, presumably because we're trying
    // to generate a KeyID that's only bound the the given button.
    // this is important when a shift button is modified by shift;  we
    // must use the other shift button to do the shifting.
    const ModifierKeyItemList& items =
        m_modifierKeys[group * kKeyModifierNumBits + modifierBit];
    for (ModifierKeyItemList::const_iterator i = items.begin();
                                i != items.end(); ++i) {
        if ((*i)->m_button != button) {
            return (*i);
        }
    }
    return NULL;
}

bool
CKeyMap::keysForKeyItem(const KeyItem& keyItem, SInt32& group,
                ModifierToKeys& activeModifiers,
                KeyModifierMask& currentState, KeyModifierMask desiredState,
                KeyModifierMask overrideModifiers,
                bool isAutoRepeat,
                Keystrokes& keystrokes) const
{
    static const KeyModifierMask s_notRequiredMask =
        KeyModifierAltGr | KeyModifierNumLock | KeyModifierScrollLock;

    // add keystrokes to adjust the group
    if (group != keyItem.m_group) {
        group = keyItem.m_group;
        keystrokes.push_back(Keystroke(group, true, false));
    }

    EKeystroke type;
    if (keyItem.m_dead) {
        // adjust modifiers for dead key
        if (!keysForModifierState(keyItem.m_button, group,
                                activeModifiers, currentState,
                                keyItem.m_required, keyItem.m_sensitive,
                                0, keystrokes)) {
            LOG((CLOG_DEBUG1 "unable to match modifier state for dead key %d", keyItem.m_button));
            return false;
        }

        // press and release the dead key
        type = kKeystrokeClick;
    }
    else {
        // if this a command key then we don't have to match some of the
        // key's required modifiers.
        KeyModifierMask sensitive = keyItem.m_sensitive & ~overrideModifiers;

        // XXX -- must handle pressing a modifier.  in particular, if we want
        // to synthesize a KeyID on level 1 of a KeyButton that has Shift_L
        // mapped to level 0 then we must release that button if it's down
        // (in order to satisfy a shift modifier) then press a different
        // button (any other button) mapped to the shift modifier and then
        // the Shift_L button.
        // match key's required state
        LOG((CLOG_DEBUG1 "state: %04x,%04x,%04x", currentState, keyItem.m_required, sensitive));
        if (!keysForModifierState(keyItem.m_button, group,
                                activeModifiers, currentState,
                                keyItem.m_required, sensitive,
                                0, keystrokes)) {
            LOG((CLOG_DEBUG1 "unable to match modifier state (%04x,%04x) for key %d", keyItem.m_required, keyItem.m_sensitive, keyItem.m_button));
            return false;
        }

        // match desiredState as closely as possible.  we must not
        // change any modifiers in keyItem.m_sensitive.  and if the key
        // is a modifier, we don't want to change that modifier.
        LOG((CLOG_DEBUG1 "desired state: %04x %04x,%04x,%04x", desiredState, currentState, keyItem.m_required, keyItem.m_sensitive));
        if (!keysForModifierState(keyItem.m_button, group,
                                activeModifiers, currentState,
                                desiredState,
                                ~(sensitive | keyItem.m_generates),
                                s_notRequiredMask, keystrokes)) {
            LOG((CLOG_DEBUG1 "unable to match desired modifier state (%04x,%04x) for key %d", desiredState, ~keyItem.m_sensitive & 0xffffu, keyItem.m_button));
            return false;
        }

        // repeat or press of key
        type = isAutoRepeat ? kKeystrokeRepeat : kKeystrokePress;
    }
    addKeystrokes(type, keyItem, activeModifiers, currentState, keystrokes);

    return true;
}

bool
CKeyMap::keysToRestoreModifiers(const KeyItem& keyItem, SInt32,
                ModifierToKeys& activeModifiers,
                KeyModifierMask& currentState,
                const ModifierToKeys& desiredModifiers,
                Keystrokes& keystrokes) const
{
    // XXX -- we're not considering modified modifiers here

    ModifierToKeys oldModifiers = activeModifiers;

    // get the pressed modifier buttons before and after
    ButtonToKeyMap oldKeys, newKeys;
    collectButtons(oldModifiers, oldKeys);
    collectButtons(desiredModifiers, newKeys);

    // release unwanted keys
    for (ModifierToKeys::const_iterator i = oldModifiers.begin();
                                i != oldModifiers.end(); ++i) {
        KeyButton button = i->second.m_button;
        if (button != keyItem.m_button && newKeys.count(button) == 0) {
            EKeystroke type = kKeystrokeRelease;
            if (i->second.m_lock) {
                type = kKeystrokeUnmodify;
            }
            addKeystrokes(type, i->second,
                                activeModifiers, currentState, keystrokes);
        }
    }

    // press wanted keys
    for (ModifierToKeys::const_iterator i = desiredModifiers.begin();
                                i != desiredModifiers.end(); ++i) {
        KeyButton button = i->second.m_button;
        if (button != keyItem.m_button && oldKeys.count(button) == 0) {
            EKeystroke type = kKeystrokePress;
            if (i->second.m_lock) {
                type = kKeystrokeModify;
            }
            addKeystrokes(type, i->second,
                                activeModifiers, currentState, keystrokes);
        }
    }

    return true;
}

bool
CKeyMap::keysForModifierState(KeyButton button, SInt32 group,
                ModifierToKeys& activeModifiers,
                KeyModifierMask& currentState,
                KeyModifierMask requiredState, KeyModifierMask sensitiveMask,
                KeyModifierMask notRequiredMask,
                Keystrokes& keystrokes) const
{
    // compute which modifiers need changing
    KeyModifierMask flipMask = ((currentState ^ requiredState) & sensitiveMask);
    // if a modifier is not required then don't even try to match it.  if
    // we don't mask out notRequiredMask then we'll try to match those
    // modifiers but succeed if we can't.  however, this is known not
    // to work if the key itself is a modifier (the numlock toggle can
    // interfere) so we don't try to match at all.
    flipMask &= ~notRequiredMask;
    LOG((CLOG_DEBUG1 "flip: %04x (%04x vs %04x in %04x - %04x)", flipMask, currentState, requiredState, sensitiveMask & 0xffffu, notRequiredMask & 0xffffu));
    if (flipMask == 0) {
        return true;
    }

    // fix modifiers.  this is complicated by the fact that a modifier may
    // be sensitive to other modifiers!  (who thought that up?)
    //
    // we'll assume that modifiers with higher bits are affected by modifiers
    // with lower bits.  there's not much basis for that assumption except
    // that we're pretty sure shift isn't changed by other modifiers.
    for (SInt32 bit = kKeyModifierNumBits; bit-- > 0; ) {
        KeyModifierMask mask = (1u << bit);
        if ((flipMask & mask) == 0) {
            // modifier is already correct
            continue;
        }

        // do we want the modifier active or inactive?
        bool active = ((requiredState & mask) != 0);

        // get the KeyItem for the modifier in the group
        const KeyItem* keyItem = keyForModifier(button, group, bit);
        if (keyItem == NULL) {
            if ((mask & notRequiredMask) == 0) {
                LOG((CLOG_DEBUG1 "no key for modifier %04x", mask));
                return false;
            }
            else {
                continue;
            }
        }

        // if this modifier is sensitive to modifiers then adjust those
        // modifiers.  also check if our assumption was correct.  note
        // that we only need to adjust the modifiers on key down.
        KeyModifierMask sensitive = keyItem->m_sensitive;
        if ((sensitive & mask) != 0) {
            // modifier is sensitive to itself.  that makes no sense
            // so ignore it.
            LOG((CLOG_DEBUG1 "modifier %04x modified by itself", mask));
            sensitive &= ~mask;
        }
        if (sensitive != 0) {
            if (sensitive > mask) {
                // our assumption is incorrect
                LOG((CLOG_DEBUG1 "modifier %04x modified by %04x", mask, sensitive));
                return false;
            }
            if (active && !keysForModifierState(button, group,
                                activeModifiers, currentState,
                                keyItem->m_required, sensitive,
                                notRequiredMask, keystrokes)) {
                return false;
            }
            else if (!active) {
                // release the modifier
                // XXX -- this doesn't work!  if Alt and Meta are mapped
                // to one key and we want to release Meta we can't do
                // that without also releasing Alt.
                // need to think about support for modified modifiers.
            }
        }

        // current state should match required state
        if ((currentState & sensitive) != (keyItem->m_required & sensitive)) {
            LOG((CLOG_DEBUG1 "unable to match modifier state for modifier %04x (%04x vs %04x in %04x)", mask, currentState, keyItem->m_required, sensitive));
            return false;
        }

        // add keystrokes
        EKeystroke type = active ? kKeystrokeModify : kKeystrokeUnmodify;
        addKeystrokes(type, *keyItem, activeModifiers, currentState,
                                keystrokes);
    }

    return true;
}

void
CKeyMap::addKeystrokes(EKeystroke type, const KeyItem& keyItem,
                ModifierToKeys& activeModifiers,
                KeyModifierMask& currentState,
                Keystrokes& keystrokes) const
{
    KeyButton button = keyItem.m_button;
    UInt32 data      = keyItem.m_client;
    switch (type) {
    case kKeystrokePress:
        keystrokes.push_back(Keystroke(button, true, false, data));
        if (keyItem.m_generates != 0) {
            if (!keyItem.m_lock || (currentState & keyItem.m_generates) == 0) {
                // add modifier key and activate modifier
                activeModifiers.insert(std::make_pair(
                                    keyItem.m_generates, keyItem));
                currentState |= keyItem.m_generates;
            }
            else {
                // deactivate locking modifier
                activeModifiers.erase(keyItem.m_generates);
                currentState &= ~keyItem.m_generates;
            }
        }
        break;
        
    case kKeystrokeRelease:
        keystrokes.push_back(Keystroke(button, false, false, data));
        if (keyItem.m_generates != 0 && !keyItem.m_lock) {
            // remove key from active modifiers
            std::pair<ModifierToKeys::iterator,
                        ModifierToKeys::iterator> range =
                activeModifiers.equal_range(keyItem.m_generates);
            for (ModifierToKeys::iterator i = range.first;
                                i != range.second; ++i) {
                if (i->second.m_button == button) {
                    activeModifiers.erase(i);
                    break;
                }
            }

            // if no more keys for this modifier then deactivate modifier
            if (activeModifiers.count(keyItem.m_generates) == 0) {
                currentState &= ~keyItem.m_generates;
            }
        }
        break;
        
    case kKeystrokeRepeat:
        keystrokes.push_back(Keystroke(button, false, true, data));
        keystrokes.push_back(Keystroke(button,  true, true, data));
        // no modifier changes on key repeat
        break;
        
    case kKeystrokeClick:
        keystrokes.push_back(Keystroke(button,  true, false, data));
        keystrokes.push_back(Keystroke(button, false, false, data));
        // no modifier changes on key click
        break;
        
    case kKeystrokeModify:
    case kKeystrokeUnmodify:
        if (keyItem.m_lock) {
            // we assume there's just one button for this modifier
            if (m_halfDuplex.count(button) > 0) {
                if (type == kKeystrokeModify) {
                    // turn half-duplex toggle on (press)
                    keystrokes.push_back(Keystroke(button,  true, false, data));
                }
                else {
                    // turn half-duplex toggle off (release)
                    keystrokes.push_back(Keystroke(button, false, false, data));
                }
            }
            else {
                // toggle (click)
                keystrokes.push_back(Keystroke(button,  true, false, data));
                keystrokes.push_back(Keystroke(button, false, false, data));
            }
        }
        else if (type == kKeystrokeModify) {
            // press modifier
            keystrokes.push_back(Keystroke(button, true, false, data));
        }
        else {
            // release all the keys that generate the modifier that are
            // currently down
            std::pair<ModifierToKeys::const_iterator,
                        ModifierToKeys::const_iterator> range =
                activeModifiers.equal_range(keyItem.m_generates);
            for (ModifierToKeys::const_iterator i = range.first;
                                i != range.second; ++i) {
                keystrokes.push_back(Keystroke(i->second.m_button,
                                false, false, i->second.m_client));
            }
        }

        if (type == kKeystrokeModify) {
            activeModifiers.insert(std::make_pair(
                                keyItem.m_generates, keyItem));
            currentState |= keyItem.m_generates;
        }
        else {
            activeModifiers.erase(keyItem.m_generates);
            currentState &= ~keyItem.m_generates;
        }
        break;
    }
}

SInt32
CKeyMap::getNumModifiers(KeyModifierMask state)
{
    SInt32 n = 0;
    for (; state != 0; state >>= 1) {
        if ((state & 1) != 0) {
            ++n;
        }
    }
    return n;
}

bool
CKeyMap::isDeadKey(KeyID key)
{
    return (key == kKeyCompose || (key >= 0x0300 && key <= 0x036f));
}

KeyID
CKeyMap::getDeadKey(KeyID key)
{
    if (isDeadKey(key)) {
        // already dead
        return key;
    }

    switch (key) {
    case '`':
        return kKeyDeadGrave;

    case 0xb4u:
        return kKeyDeadAcute;

    case '^':
    case 0x2c6:
        return kKeyDeadCircumflex;

    case '~':
    case 0x2dcu:
        return kKeyDeadTilde;

    case 0xafu:
        return kKeyDeadMacron;

    case 0x2d8u:
        return kKeyDeadBreve;

    case 0x2d9u:
        return kKeyDeadAbovedot;

    case 0xa8u:
        return kKeyDeadDiaeresis;

    case 0xb0u:
    case 0x2dau:
        return kKeyDeadAbovering;

    case '\"':
    case 0x2ddu:
        return kKeyDeadDoubleacute;

    case 0x2c7u:
        return kKeyDeadCaron;

    case 0xb8u:
        return kKeyDeadCedilla;

    case 0x2dbu:
        return kKeyDeadOgonek;

    default:
        // unknown
        return kKeyNone;
    }
}

CString
CKeyMap::formatKey(KeyID key, KeyModifierMask mask)
{
    // initialize tables
    initKeyNameMaps();

    CString x;
    for (SInt32 i = 0; i < kKeyModifierNumBits; ++i) {
        KeyModifierMask mod = (1u << i);
        if ((mask & mod) != 0 && s_modifierToNameMap->count(mod) > 0) {
            x += s_modifierToNameMap->find(mod)->second;
            x += "+";
        }
    }
    if (key != kKeyNone) {
        if (s_keyToNameMap->count(key) > 0) {
            x += s_keyToNameMap->find(key)->second;
        }
        // XXX -- we're assuming ASCII here
        else if (key >= 33 && key < 127) {
            x += (char)key;
        }
        else {
            x += CStringUtil::print("\\u%04x", key);
        }
    }
    else if (!x.empty()) {
        // remove trailing '+'
        x.erase(x.size() - 1);
    }
    return x;
}

bool
CKeyMap::parseKey(const CString& x, KeyID& key)
{
    // initialize tables
    initKeyNameMaps();

    // parse the key
    key = kKeyNone;
    if (s_nameToKeyMap->count(x) > 0) {
        key = s_nameToKeyMap->find(x)->second;
    }
    // XXX -- we're assuming ASCII encoding here
    else if (x.size() == 1) {
        if (!isgraph(x[0])) {
            // unknown key
            return false;
        }
        key = (KeyID)x[0];
    }
    else if (x.size() == 6 && x[0] == '\\' && x[1] == 'u') {
        // escaped unicode (\uXXXX where XXXX is a hex number)
        char* end;
        key = (KeyID)strtol(x.c_str() + 2, &end, 16);
        if (*end != '\0') {
            return false;
        }
    }
    else if (!x.empty()) {
        // unknown key
        return false;
    }

    return true;
}

bool
CKeyMap::parseModifiers(CString& x, KeyModifierMask& mask)
{
    // initialize tables
    initKeyNameMaps();

    mask = 0;
    CString::size_type tb = x.find_first_not_of(" \t", 0);
    while (tb != CString::npos) {
        // get next component
        CString::size_type te = x.find_first_of(" \t+)", tb);
        if (te == CString::npos) {
            te = x.size();
        }
        CString c = x.substr(tb, te - tb);
        if (c.empty()) {
            // missing component
            return false;
        }

        if (s_nameToModifierMap->count(c) > 0) {
            KeyModifierMask mod = s_nameToModifierMap->find(c)->second;
            if ((mask & mod) != 0) {
                // modifier appears twice
                return false;
            }
            mask |= mod;
        }
        else {
            // unknown string
            x.erase(0, tb);
            CString::size_type tb = x.find_first_not_of(" \t");
            CString::size_type te = x.find_last_not_of(" \t");
            if (tb == CString::npos) {
                x = "";
            }
            else {
                x = x.substr(tb, te - tb + 1);
            }
            return true;
        }

        // check for '+' or end of string
        tb = x.find_first_not_of(" \t", te);
        if (tb != CString::npos) {
            if (x[tb] != '+') {
                // expected '+'
                return false;
            }
            tb = x.find_first_not_of(" \t", tb + 1);
        }
    }

    // parsed the whole thing
    x = "";
    return true;
}

void
CKeyMap::initKeyNameMaps()
{
    // initialize tables
    if (s_nameToKeyMap == NULL) {
        s_nameToKeyMap = new CNameToKeyMap;
        s_keyToNameMap = new CKeyToNameMap;
        for (const KeyNameMapEntry* i = kKeyNameMap; i->m_name != NULL; ++i) {
            (*s_nameToKeyMap)[i->m_name] = i->m_id;
            (*s_keyToNameMap)[i->m_id]   = i->m_name;
        }
    }
    if (s_nameToModifierMap == NULL) {
        s_nameToModifierMap = new CNameToModifierMap;
        s_modifierToNameMap = new CModifierToNameMap;
        for (const KeyModifierNameMapEntry* i = kModifierNameMap;
                                i->m_name != NULL; ++i) {
            (*s_nameToModifierMap)[i->m_name] = i->m_mask;
            (*s_modifierToNameMap)[i->m_mask] = i->m_name;
        }
    }
}


//
// CKeyMap::KeyItem
//

bool
CKeyMap::KeyItem::operator==(const KeyItem& x) const
{
    return (m_id        == x.m_id        &&
            m_group     == x.m_group     &&
            m_button    == x.m_button    &&
            m_required  == x.m_required  &&
            m_sensitive == x.m_sensitive &&
            m_generates == x.m_generates &&
            m_dead      == x.m_dead      &&
            m_lock      == x.m_lock      &&
            m_client    == x.m_client);
}


//
// CKeyMap::Keystroke
//

CKeyMap::Keystroke::Keystroke(KeyButton button,
                bool press, bool repeat, UInt32 data) :
    m_type(kButton)
{
    m_data.m_button.m_button = button;
    m_data.m_button.m_press  = press;
    m_data.m_button.m_repeat = repeat;
    m_data.m_button.m_client = data;
}

CKeyMap::Keystroke::Keystroke(SInt32 group, bool absolute, bool restore) :
    m_type(kGroup)
{
    m_data.m_group.m_group    = group;
    m_data.m_group.m_absolute = absolute;
    m_data.m_group.m_restore  = restore;
}