Added support for full PC-style keyboards.

BREAKING CHANGE: Redesigned the key character map format to
accomodate full keyboards with more comprehensive suite of modifiers.
Old key character maps will not work anymore and must be updated.
The new format is plain text only and it not compiled to a binary
file (so the "kcm" tool will be removed in a subsequent check-in).

Added FULL keyboard type to support full PC-style keyboards.

Added SPECIAL_FUNCTION keyboard type to support special function
keypads that do not have any printable keys suitable for typing
and only have keys like HOME and POWER

Added a special VIRTUAL_KEYBOARD device id convention that maps
to a virtual keyboard with a fixed known layout.  This is designed
to work around issues injecting input events on devices whose
built-in keyboard does not have a useful key character map (ie.
when the built-in keyboard is a special function keyboard only.)

Modified several places where events were being synthesized
to use the virtual keyboard.

Removed support for the "qwerty" default layout.
The new default layout is "Generic".  For the most part "qwerty"
was being used as a backstop in case the built-in keyboard did
not have a key character map (probably because it was a special
function keypad) and the framework needed to be able to inject
key events anyways.  The latter issue is resolved by using the
special VIRTUAL_KEYBOARD device instead of BUILT_IN_KEYBOARD.

Added the concept of a key modifier behavior so that
MetaKeyKeyListener can distinguish between keyboards that use
chorded vs. toggled modifiers.

Wrote more robust key layout and key character map parsers
to enable support for new keyboard features and user installable
key maps.

Fixed a bug in InputReader generating key ups when keys
are released out of sequence.

Updated tons of documentation.

Currently QwertyKeyListener is being used for full keyboards
with autotext and capitalization disabled.  This mostly works
but causes some problems with character pickers, etc.
These issues will be resolved in subsequent changes.

Change-Id: Ica48f6097a551141c215bc0d2c6f7b3fb634d354

10 files changed, 1363 insertions, 629 deletions

diff --git a/libs/ui/Android.mk b/libs/ui/Android.mk
index c4a09d6..61d8abd 100644
--- a/libs/ui/Android.mk
+++ b/libs/ui/Android.mk
@@ -10,6 +10,7 @@ LOCAL_SRC_FILES:= \
 	GraphicBufferAllocator.cpp \
 	GraphicBufferMapper.cpp \
 	GraphicLog.cpp \
+	Keyboard.cpp \
 	KeyLayoutMap.cpp \
 	KeyCharacterMap.cpp \
 	Input.cpp \
diff --git a/libs/ui/EventHub.cpp b/libs/ui/EventHub.cpp
index 9c7e7f4..f468217 100644
--- a/libs/ui/EventHub.cpp
+++ b/libs/ui/EventHub.cpp
@@ -16,7 +16,6 @@
 //#define LOG_NDEBUG 0
 
 #include <ui/EventHub.h>
-#include <ui/KeycodeLabels.h>
 #include <hardware_legacy/power.h>
 
 #include <cutils/properties.h>
@@ -33,7 +32,7 @@
 #include <errno.h>
 #include <assert.h>
 
-#include "KeyLayoutMap.h"
+#include <ui/KeyLayoutMap.h>
 
 #include <string.h>
 #include <stdint.h>
@@ -94,7 +93,7 @@ static inline const char* toString(bool value) {
 
 EventHub::device_t::device_t(int32_t _id, const char* _path, const char* name)
     : id(_id), path(_path), name(name), classes(0)
-    , keyBitmask(NULL), layoutMap(new KeyLayoutMap()), defaultKeyMap(false), fd(-1), next(NULL) {
+    , keyBitmask(NULL), layoutMap(NULL), fd(-1), next(NULL) {
 }
 
 EventHub::device_t::~device_t() {
@@ -204,8 +203,12 @@ int32_t EventHub::getKeyCodeState(int32_t deviceId, int32_t keyCode) const {
 }
 
 int32_t EventHub::getKeyCodeStateLocked(device_t* device, int32_t keyCode) const {
+    if (!device->layoutMap) {
+        return AKEY_STATE_UNKNOWN;
+    }
+
     Vector<int32_t> scanCodes;
-    device->layoutMap->findScancodes(keyCode, &scanCodes);
+    device->layoutMap->findScanCodes(keyCode, &scanCodes);
 
     uint8_t key_bitmask[sizeof_bit_array(KEY_MAX + 1)];
     memset(key_bitmask, 0, sizeof(key_bitmask));
@@ -273,7 +276,7 @@ bool EventHub::markSupportedKeyCodesLocked(device_t* device, size_t numCodes,
     for (size_t codeIndex = 0; codeIndex < numCodes; codeIndex++) {
         scanCodes.clear();
 
-        status_t err = device->layoutMap->findScancodes(keyCodes[codeIndex], &scanCodes);
+        status_t err = device->layoutMap->findScanCodes(keyCodes[codeIndex], &scanCodes);
         if (! err) {
             // check the possible scan codes identified by the layout map against the
             // map of codes actually emitted by the driver
@@ -448,14 +451,14 @@ bool EventHub::getEvent(RawEvent* outEvent)
                 }
                 outEvent->type = iev.type;
                 outEvent->scanCode = iev.code;
+                outEvent->flags = 0;
                 if (iev.type == EV_KEY) {
-                    status_t err = device->layoutMap->map(iev.code,
-                            & outEvent->keyCode, & outEvent->flags);
-                    LOGV("iev.code=%d keyCode=%d flags=0x%08x err=%d\n",
-                        iev.code, outEvent->keyCode, outEvent->flags, err);
-                    if (err != 0) {
-                        outEvent->keyCode = AKEYCODE_UNKNOWN;
-                        outEvent->flags = 0;
+                    outEvent->keyCode = AKEYCODE_UNKNOWN;
+                    if (device->layoutMap) {
+                        status_t err = device->layoutMap->map(iev.code,
+                                &outEvent->keyCode, &outEvent->flags);
+                        LOGV("iev.code=%d keyCode=%d flags=0x%08x err=%d\n",
+                                iev.code, outEvent->keyCode, outEvent->flags, err);
                     }
                 } else {
                     outEvent->keyCode = iev.code;
@@ -800,10 +803,11 @@ int EventHub::openDevice(const char *deviceName) {
         device->name = name;
 
         // Configure the keymap for the device.
+
         configureKeyMap(device);
 
         // Tell the world about the devname (the descriptive name)
-        if (!mHaveFirstKeyboard && !device->defaultKeyMap && strstr(name, "-keypad")) {
+        if (!mHaveFirstKeyboard && !device->keyMapInfo.isDefaultKeyMap && strstr(name, "-keypad")) {
             // the built-in keyboard has a well-known device ID of 0,
             // this device better not go away.
             mHaveFirstKeyboard = true;
@@ -819,11 +823,12 @@ int EventHub::openDevice(const char *deviceName) {
         setKeyboardProperties(device, false);
 
         // Load the keylayout.
-        if (!device->keyLayoutFilename.isEmpty()) {
-            status_t status = device->layoutMap->load(device->keyLayoutFilename);
+        if (!device->keyMapInfo.keyLayoutFile.isEmpty()) {
+            status_t status = KeyLayoutMap::load(device->keyMapInfo.keyLayoutFile,
+                    &device->layoutMap);
             if (status) {
                 LOGE("Error %d loading key layout file '%s'.", status,
-                        device->keyLayoutFilename.string());
+                        device->keyMapInfo.keyLayoutFile.string());
             }
         }
 
@@ -851,7 +856,8 @@ int EventHub::openDevice(const char *deviceName) {
 
         LOGI("New keyboard: device->id=0x%x devname='%s' keylayout='%s' keycharactermap='%s'\n",
                 device->id, name,
-                device->keyLayoutFilename.string(), device->keyCharacterMapFilename.string());
+                device->keyMapInfo.keyLayoutFile.string(),
+                device->keyMapInfo.keyCharacterMapFile.string());
     }
 
     // If the device isn't recognized as something we handle, don't monitor it.
@@ -878,106 +884,17 @@ int EventHub::openDevice(const char *deviceName) {
 }
 
 void EventHub::configureKeyMap(device_t* device) {
-    // As an initial key map name, try using the device name.
-    String8 keyMapName(device->name);
-    char* p = keyMapName.lockBuffer(keyMapName.size());
-    while (*p) {
-        if (*p == ' ') *p = '_';
-        p++;
-    }
-    keyMapName.unlockBuffer();
-
-    if (probeKeyMap(device, keyMapName, false)) return;
-
-    // TODO Consider allowing the user to configure a specific key map somehow.
-
-    // Try the Generic key map.
-    // TODO Apply some additional heuristics here to figure out what kind of
-    //      generic key map to use (US English, etc.).
-    keyMapName.setTo("Generic");
-    if (probeKeyMap(device, keyMapName, true)) return;
-
-    // Fall back on the old style catchall qwerty key map.
-    keyMapName.setTo("qwerty");
-    if (probeKeyMap(device, keyMapName, true)) return;
-
-    // Give up!
-    keyMapName.setTo("unknown");
-    selectKeyMap(device, keyMapName, true);
-    LOGE("Could not determine key map for device '%s'.", device->name.string());
-}
-
-bool EventHub::probeKeyMap(device_t* device, const String8& keyMapName, bool defaultKeyMap) {
-    const char* root = getenv("ANDROID_ROOT");
-
-    // TODO Consider also looking somewhere in a writeable partition like /data for a
-    //      custom keymap supplied by the user for this device.
-    bool haveKeyLayout = !device->keyLayoutFilename.isEmpty();
-    if (!haveKeyLayout) {
-        device->keyLayoutFilename.setTo(root);
-        device->keyLayoutFilename.append("/usr/keylayout/");
-        device->keyLayoutFilename.append(keyMapName);
-        device->keyLayoutFilename.append(".kl");
-        if (access(device->keyLayoutFilename.string(), R_OK)) {
-            device->keyLayoutFilename.clear();
-        } else {
-            haveKeyLayout = true;
-        }
-    }
-
-    bool haveKeyCharacterMap = !device->keyCharacterMapFilename.isEmpty();
-    if (!haveKeyCharacterMap) {
-        device->keyCharacterMapFilename.setTo(root);
-        device->keyCharacterMapFilename.append("/usr/keychars/");
-        device->keyCharacterMapFilename.append(keyMapName);
-        device->keyCharacterMapFilename.append(".kcm.bin");
-        if (access(device->keyCharacterMapFilename.string(), R_OK)) {
-            device->keyCharacterMapFilename.clear();
-        } else {
-            haveKeyCharacterMap = true;
-        }
-    }
-
-    if (haveKeyLayout || haveKeyCharacterMap) {
-        selectKeyMap(device, keyMapName, defaultKeyMap);
-    }
-    return haveKeyLayout && haveKeyCharacterMap;
-}
-
-void EventHub::selectKeyMap(device_t* device,
-        const String8& keyMapName, bool defaultKeyMap) {
-    if (device->keyMapName.isEmpty()) {
-        device->keyMapName.setTo(keyMapName);
-        device->defaultKeyMap = defaultKeyMap;
-    }
+    android::resolveKeyMap(device->name, device->keyMapInfo);
 }
 
 void EventHub::setKeyboardProperties(device_t* device, bool firstKeyboard) {
     int32_t id = firstKeyboard ? 0 : device->id;
-
-    char propName[100];
-    sprintf(propName, "hw.keyboards.%u.devname", id);
-    property_set(propName, device->name.string());
-    sprintf(propName, "hw.keyboards.%u.keymap", id);
-    property_set(propName, device->keyMapName.string());
-    sprintf(propName, "hw.keyboards.%u.klfile", id);
-    property_set(propName, device->keyLayoutFilename.string());
-    sprintf(propName, "hw.keyboards.%u.kcmfile", id);
-    property_set(propName, device->keyCharacterMapFilename.string());
+    android::setKeyboardProperties(id, device->name, device->keyMapInfo);
 }
 
 void EventHub::clearKeyboardProperties(device_t* device, bool firstKeyboard) {
     int32_t id = firstKeyboard ? 0 : device->id;
-
-    char propName[100];
-    sprintf(propName, "hw.keyboards.%u.devname", id);
-    property_set(propName, "");
-    sprintf(propName, "hw.keyboards.%u.keymap", id);
-    property_set(propName, "");
-    sprintf(propName, "hw.keyboards.%u.klfile", id);
-    property_set(propName, "");
-    sprintf(propName, "hw.keyboards.%u.kcmfile", id);
-    property_set(propName, "");
+    android::clearKeyboardProperties(id);
 }
 
 bool EventHub::hasKeycodeLocked(device_t* device, int keycode) const
@@ -987,7 +904,7 @@ bool EventHub::hasKeycodeLocked(device_t* device, int keycode) const
     }
     
     Vector<int32_t> scanCodes;
-    device->layoutMap->findScancodes(keycode, &scanCodes);
+    device->layoutMap->findScanCodes(keycode, &scanCodes);
     const size_t N = scanCodes.size();
     for (size_t i=0; i<N && i<=KEY_MAX; i++) {
         int32_t sc = scanCodes.itemAt(i);
@@ -1139,11 +1056,14 @@ void EventHub::dump(String8& dump) {
                 }
                 dump.appendFormat(INDENT3 "Classes: 0x%08x\n", device->classes);
                 dump.appendFormat(INDENT3 "Path: %s\n", device->path.string());
-                dump.appendFormat(INDENT3 "KeyMapName: %s\n", device->keyMapName.string());
-                dump.appendFormat(INDENT3 "KeyLayoutFilename: %s\n",
-                        device->keyLayoutFilename.string());
-                dump.appendFormat(INDENT3 "KeyCharacterMapFilename: %s\n",
-                        device->keyCharacterMapFilename.string());
+                dump.appendFormat(INDENT3 "IsDefaultKeyMap: %s\n",
+                        toString(device->keyMapInfo.isDefaultKeyMap));
+                dump.appendFormat(INDENT3 "KeyMapName: %s\n",
+                        device->keyMapInfo.keyMapName.string());
+                dump.appendFormat(INDENT3 "KeyLayoutFile: %s\n",
+                        device->keyMapInfo.keyLayoutFile.string());
+                dump.appendFormat(INDENT3 "KeyCharacterMapFile: %s\n",
+                        device->keyMapInfo.keyCharacterMapFile.string());
             }
         }
     } // release lock
diff --git a/libs/ui/InputReader.cpp b/libs/ui/InputReader.cpp
index b91e93a..daff2d0 100644
--- a/libs/ui/InputReader.cpp
+++ b/libs/ui/InputReader.cpp
@@ -24,6 +24,7 @@
 
 #include <cutils/log.h>
 #include <ui/InputReader.h>
+#include <ui/Keyboard.h>
 
 #include <stddef.h>
 #include <stdlib.h>
@@ -70,75 +71,6 @@ static inline const char* toString(bool value) {
     return value ? "true" : "false";
 }
 
-int32_t setEphemeralMetaState(int32_t mask, bool down, int32_t oldMetaState) {
-    int32_t newMetaState;
-    if (down) {
-        newMetaState = oldMetaState | mask;
-    } else {
-        newMetaState = oldMetaState &
-                ~(mask | AMETA_ALT_ON | AMETA_SHIFT_ON | AMETA_CTRL_ON | AMETA_META_ON);
-    }
-
-    if (newMetaState & (AMETA_ALT_LEFT_ON | AMETA_ALT_RIGHT_ON)) {
-        newMetaState |= AMETA_ALT_ON;
-    }
-
-    if (newMetaState & (AMETA_SHIFT_LEFT_ON | AMETA_SHIFT_RIGHT_ON)) {
-        newMetaState |= AMETA_SHIFT_ON;
-    }
-
-    if (newMetaState & (AMETA_CTRL_LEFT_ON | AMETA_CTRL_RIGHT_ON)) {
-        newMetaState |= AMETA_CTRL_ON;
-    }
-
-    if (newMetaState & (AMETA_META_LEFT_ON | AMETA_META_RIGHT_ON)) {
-        newMetaState |= AMETA_META_ON;
-    }
-    return newMetaState;
-}
-
-int32_t toggleLockedMetaState(int32_t mask, bool down, int32_t oldMetaState) {
-    if (down) {
-        return oldMetaState;
-    } else {
-        return oldMetaState ^ mask;
-    }
-}
-
-int32_t updateMetaState(int32_t keyCode, bool down, int32_t oldMetaState) {
-    int32_t mask;
-    switch (keyCode) {
-    case AKEYCODE_ALT_LEFT:
-        return setEphemeralMetaState(AMETA_ALT_LEFT_ON, down, oldMetaState);
-    case AKEYCODE_ALT_RIGHT:
-        return setEphemeralMetaState(AMETA_ALT_RIGHT_ON, down, oldMetaState);
-    case AKEYCODE_SHIFT_LEFT:
-        return setEphemeralMetaState(AMETA_SHIFT_LEFT_ON, down, oldMetaState);
-    case AKEYCODE_SHIFT_RIGHT:
-        return setEphemeralMetaState(AMETA_SHIFT_RIGHT_ON, down, oldMetaState);
-    case AKEYCODE_SYM:
-        return setEphemeralMetaState(AMETA_SYM_ON, down, oldMetaState);
-    case AKEYCODE_FUNCTION:
-        return setEphemeralMetaState(AMETA_FUNCTION_ON, down, oldMetaState);
-    case AKEYCODE_CTRL_LEFT:
-        return setEphemeralMetaState(AMETA_CTRL_LEFT_ON, down, oldMetaState);
-    case AKEYCODE_CTRL_RIGHT:
-        return setEphemeralMetaState(AMETA_CTRL_RIGHT_ON, down, oldMetaState);
-    case AKEYCODE_META_LEFT:
-        return setEphemeralMetaState(AMETA_META_LEFT_ON, down, oldMetaState);
-    case AKEYCODE_META_RIGHT:
-        return setEphemeralMetaState(AMETA_META_RIGHT_ON, down, oldMetaState);
-    case AKEYCODE_CAPS_LOCK:
-        return toggleLockedMetaState(AMETA_CAPS_LOCK_ON, down, oldMetaState);
-    case AKEYCODE_NUM_LOCK:
-        return toggleLockedMetaState(AMETA_NUM_LOCK_ON, down, oldMetaState);
-    case AKEYCODE_SCROLL_LOCK:
-        return toggleLockedMetaState(AMETA_SCROLL_LOCK_ON, down, oldMetaState);
-    default:
-        return oldMetaState;
-    }
-}
-
 static const int32_t keyCodeRotationMap[][4] = {
         // key codes enumerated counter-clockwise with the original (unrotated) key first
         // no rotation,        90 degree rotation,  180 degree rotation, 270 degree rotation
@@ -977,7 +909,7 @@ void KeyboardInputMapper::processKey(nsecs_t when, bool down, int32_t keyCode,
             ssize_t keyDownIndex = findKeyDownLocked(scanCode);
             if (keyDownIndex >= 0) {
                 // key repeat, be sure to use same keycode as before in case of rotation
-                keyCode = mLocked.keyDowns.top().keyCode;
+                keyCode = mLocked.keyDowns.itemAt(keyDownIndex).keyCode;
             } else {
                 // key down
                 mLocked.keyDowns.push();
@@ -992,7 +924,7 @@ void KeyboardInputMapper::processKey(nsecs_t when, bool down, int32_t keyCode,
             ssize_t keyDownIndex = findKeyDownLocked(scanCode);
             if (keyDownIndex >= 0) {
                 // key up, be sure to use same keycode as before in case of rotation
-                keyCode = mLocked.keyDowns.top().keyCode;
+                keyCode = mLocked.keyDowns.itemAt(keyDownIndex).keyCode;
                 mLocked.keyDowns.removeAt(size_t(keyDownIndex));
             } else {
                 // key was not actually down
diff --git a/libs/ui/KeyCharacterMap.cpp b/libs/ui/KeyCharacterMap.cpp
index 870a45c..890cc3f 100644
--- a/libs/ui/KeyCharacterMap.cpp
+++ b/libs/ui/KeyCharacterMap.cpp
@@ -1,275 +1,807 @@
-#define LOG_TAG "KeyCharacterMap"
+/*
+ * Copyright (C) 2008 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
 
-#include <ui/KeyCharacterMap.h>
-#include <cutils/properties.h>
+#define LOG_TAG "KeyCharacterMap"
 
-#include <utils/Log.h>
-#include <sys/types.h>
-#include <unistd.h>
 #include <stdlib.h>
-#include <fcntl.h>
-#include <limits.h>
 #include <string.h>
+#include <android/keycodes.h>
+#include <ui/Keyboard.h>
+#include <ui/KeyCharacterMap.h>
+#include <utils/Log.h>
+#include <utils/Errors.h>
+#include <utils/Tokenizer.h>
+#include <utils/Timers.h>
+
+// Enables debug output for the parser.
+#define DEBUG_PARSER 0
+
+// Enables debug output for parser performance.
+#define DEBUG_PARSER_PERFORMANCE 0
+
+// Enables debug output for mapping.
+#define DEBUG_MAPPING 0
+
+
+namespace android {
 
-struct Header
-{
-    char magic[8];
-    unsigned int endian;
-    unsigned int version;
-    unsigned int keycount;
-    unsigned char kbdtype;
-    char padding[11];
+static const char* WHITESPACE = " \t\r";
+static const char* WHITESPACE_OR_PROPERTY_DELIMITER = " \t\r,:";
+
+struct Modifier {
+    const char* label;
+    int32_t metaState;
+};
+static const Modifier modifiers[] = {
+        { "shift", AMETA_SHIFT_ON },
+        { "lshift", AMETA_SHIFT_LEFT_ON },
+        { "rshift", AMETA_SHIFT_RIGHT_ON },
+        { "alt", AMETA_ALT_ON },
+        { "lalt", AMETA_ALT_LEFT_ON },
+        { "ralt", AMETA_ALT_RIGHT_ON },
+        { "ctrl", AMETA_CTRL_ON },
+        { "lctrl", AMETA_CTRL_LEFT_ON },
+        { "rctrl", AMETA_CTRL_RIGHT_ON },
+        { "meta", AMETA_META_ON },
+        { "lmeta", AMETA_META_LEFT_ON },
+        { "rmeta", AMETA_META_RIGHT_ON },
+        { "sym", AMETA_SYM_ON },
+        { "fn", AMETA_FUNCTION_ON },
+        { "capslock", AMETA_CAPS_LOCK_ON },
+        { "numlock", AMETA_NUM_LOCK_ON },
+        { "scrolllock", AMETA_SCROLL_LOCK_ON },
 };
 
-KeyCharacterMap::KeyCharacterMap()
-{
+#if DEBUG_MAPPING
+static String8 toString(const char16_t* chars, size_t numChars) {
+    String8 result;
+    for (size_t i = 0; i < numChars; i++) {
+        result.appendFormat(i == 0 ? "%d" : ", %d", chars[i]);
+    }
+    return result;
 }
+#endif
+
+
+// --- KeyCharacterMap ---
 
-KeyCharacterMap::~KeyCharacterMap()
-{
-    free(m_keys);
+KeyCharacterMap::KeyCharacterMap() :
+    mType(KEYBOARD_TYPE_UNKNOWN) {
 }
 
-unsigned short
-KeyCharacterMap::get(int keycode, int meta)
-{
-    Key* k = find_key(keycode);
-    if (k != NULL) {
-        return k->data[meta & META_MASK];
+KeyCharacterMap::~KeyCharacterMap() {
+    for (size_t i = 0; i < mKeys.size(); i++) {
+        Key* key = mKeys.editValueAt(i);
+        delete key;
     }
-    return 0;
 }
 
-unsigned short
-KeyCharacterMap::getNumber(int keycode)
-{
-    Key* k = find_key(keycode);
-    if (k != NULL) {
-        return k->number;
+status_t KeyCharacterMap::load(const String8& filename, KeyCharacterMap** outMap) {
+    *outMap = NULL;
+
+    Tokenizer* tokenizer;
+    status_t status = Tokenizer::open(filename, &tokenizer);
+    if (status) {
+        LOGE("Error %d opening key character map file %s.", status, filename.string());
+    } else {
+        KeyCharacterMap* map = new KeyCharacterMap();
+        if (!map) {
+            LOGE("Error allocating key character map.");
+            status = NO_MEMORY;
+        } else {
+#if DEBUG_PARSER_PERFORMANCE
+            nsecs_t startTime = systemTime(SYSTEM_TIME_MONOTONIC);
+#endif
+            Parser parser(map, tokenizer);
+            status = parser.parse();
+#if DEBUG_PARSER_PERFORMANCE
+            nsecs_t elapsedTime = systemTime(SYSTEM_TIME_MONOTONIC) - startTime;
+            LOGD("Parsed key character map file '%s' %d lines in %0.3fms.",
+                    tokenizer->getFilename().string(), tokenizer->getLineNumber(),
+                    elapsedTime / 1000000.0);
+#endif
+            if (status) {
+                delete map;
+            } else {
+                *outMap = map;
+            }
+        }
+        delete tokenizer;
     }
-    return 0;
+    return status;
 }
 
-unsigned short
-KeyCharacterMap::getMatch(int keycode, const unsigned short* chars,
-                          int charsize, uint32_t modifiers)
-{
-    Key* k = find_key(keycode);
-    modifiers &= 3; // ignore the SYM key because we don't have keymap entries for it
-    if (k != NULL) {
-        const uint16_t* data = k->data;
-        for (int j=0; j<charsize; j++) {
-            uint16_t c = chars[j];
-            for (int i=0; i<(META_MASK + 1); i++) {
-                if ((modifiers == 0) || ((modifiers & i) != 0)) {
-                    if (c == data[i]) {
-                        return c;
+status_t KeyCharacterMap::loadByDeviceId(int32_t deviceId, KeyCharacterMap** outMap) {
+    *outMap = NULL;
+
+    String8 filename;
+    status_t result = getKeyCharacterMapFile(deviceId, filename);
+    if (!result) {
+        result = load(filename, outMap);
+    }
+    return result;
+}
+
+int32_t KeyCharacterMap::getKeyboardType() const {
+    return mType;
+}
+
+char16_t KeyCharacterMap::getDisplayLabel(int32_t keyCode) const {
+    char16_t result = 0;
+    ssize_t index = mKeys.indexOfKey(keyCode);
+    if (index >= 0) {
+        const Key* key = mKeys.valueAt(index);
+        result = key->label;
+    }
+#if DEBUG_MAPPING
+    LOGD("getDisplayLabel: keyCode=%d ~ Result %d.", keyCode, result);
+#endif
+    return result;
+}
+
+char16_t KeyCharacterMap::getNumber(int32_t keyCode) const {
+    char16_t result = 0;
+    ssize_t index = mKeys.indexOfKey(keyCode);
+    if (index >= 0) {
+        const Key* key = mKeys.valueAt(index);
+        result = key->number;
+    }
+#if DEBUG_MAPPING
+    LOGD("getNumber: keyCode=%d ~ Result %d.", keyCode, result);
+#endif
+    return result;
+}
+
+char16_t KeyCharacterMap::getCharacter(int32_t keyCode, int32_t metaState) const {
+    char16_t result = 0;
+    ssize_t index = mKeys.indexOfKey(keyCode);
+    if (index >= 0) {
+        const Key* key = mKeys.valueAt(index);
+        for (const Behavior* behavior = key->firstBehavior; behavior; behavior = behavior->next) {
+            if ((behavior->metaState & metaState) == behavior->metaState) {
+                result = behavior->character;
+                break;
+            }
+        }
+    }
+#if DEBUG_MAPPING
+    LOGD("getCharacter: keyCode=%d, metaState=0x%08x ~ Result %d.", keyCode, metaState, result);
+#endif
+    return result;
+}
+
+char16_t KeyCharacterMap::getMatch(int32_t keyCode, const char16_t* chars, size_t numChars,
+        int32_t metaState) const {
+    char16_t result = 0;
+    ssize_t index = mKeys.indexOfKey(keyCode);
+    if (index >= 0) {
+        const Key* key = mKeys.valueAt(index);
+
+        // Try to find the most general behavior that maps to this character.
+        // For example, the base key behavior will usually be last in the list.
+        // However, if we find a perfect meta state match for one behavior then use that one.
+        for (const Behavior* behavior = key->firstBehavior; behavior; behavior = behavior->next) {
+            if (behavior->character) {
+                for (size_t i = 0; i < numChars; i++) {
+                    if (behavior->character == chars[i]) {
+                        result = behavior->character;
+                        if ((behavior->metaState & metaState) == behavior->metaState) {
+                            goto ExactMatch;
+                        }
+                        break;
                     }
                 }
             }
         }
+    ExactMatch: ;
     }
-    return 0;
+#if DEBUG_MAPPING
+    LOGD("getMatch: keyCode=%d, chars=[%s], metaState=0x%08x ~ Result %d.",
+            keyCode, toString(chars, numChars).string(), metaState, result);
+#endif
+    return result;
 }
 
-unsigned short
-KeyCharacterMap::getDisplayLabel(int keycode)
-{
-    Key* k = find_key(keycode);
-    if (k != NULL) {
-        return k->display_label;
+bool KeyCharacterMap::getEvents(int32_t deviceId, const char16_t* chars, size_t numChars,
+        Vector<KeyEvent>& outEvents) const {
+    nsecs_t now = systemTime(SYSTEM_TIME_MONOTONIC);
+
+    for (size_t i = 0; i < numChars; i++) {
+        int32_t keyCode, metaState;
+        char16_t ch = chars[i];
+        if (!findKey(ch, &keyCode, &metaState)) {
+#if DEBUG_MAPPING
+            LOGD("getEvents: deviceId=%d, chars=[%s] ~ Failed to find mapping for character %d.",
+                    deviceId, toString(chars, numChars).string(), ch);
+#endif
+            return false;
+        }
+
+        int32_t currentMetaState = 0;
+        addMetaKeys(outEvents, deviceId, metaState, true, now, &currentMetaState);
+        addKey(outEvents, deviceId, keyCode, currentMetaState, true, now);
+        addKey(outEvents, deviceId, keyCode, currentMetaState, false, now);
+        addMetaKeys(outEvents, deviceId, metaState, false, now, &currentMetaState);
+    }
+#if DEBUG_MAPPING
+    LOGD("getEvents: deviceId=%d, chars=[%s] ~ Generated %d events.",
+            deviceId, toString(chars, numChars).string(), outEvents.size());
+    for (size_t i = 0; i < outEvents.size(); i++) {
+        LOGD("  Key: keyCode=%d, metaState=0x%08x, %s.",
+                outEvents[i].getKeyCode(), outEvents[i].getMetaState(),
+                outEvents[i].getAction() == AKEY_EVENT_ACTION_DOWN ? "down" : "up");
     }
-    return 0;
+#endif
+    return true;
 }
 
-bool
-KeyCharacterMap::getKeyData(int keycode, unsigned short *displayLabel,
-                            unsigned short *number, unsigned short* results)
-{
-    Key* k = find_key(keycode);
-    if (k != NULL) {
-        memcpy(results, k->data, sizeof(short)*(META_MASK + 1));
-        *number = k->number;
-        *displayLabel = k->display_label;
-        return true;
-    } else {
+bool KeyCharacterMap::findKey(char16_t ch, int32_t* outKeyCode, int32_t* outMetaState) const {
+    if (!ch) {
         return false;
     }
-}
 
-bool
-KeyCharacterMap::find_char(uint16_t c, uint32_t* key, uint32_t* mods)
-{
-    uint32_t N = m_keyCount;
-    for (int j=0; j<(META_MASK + 1); j++) {
-        Key const* keys = m_keys;
-        for (uint32_t i=0; i<N; i++) {
-            if (keys->data[j] == c) {
-                *key = keys->keycode;
-                *mods = j;
-                return true;
+    for (size_t i = 0; i < mKeys.size(); i++) {
+        const Key* key = mKeys.valueAt(i);
+
+        // Try to find the most general behavior that maps to this character.
+        // For example, the base key behavior will usually be last in the list.
+        const Behavior* found = NULL;
+        for (const Behavior* behavior = key->firstBehavior; behavior; behavior = behavior->next) {
+            if (behavior->character == ch) {
+                found = behavior;
             }
-            keys++;
+        }
+        if (found) {
+            *outKeyCode = mKeys.keyAt(i);
+            *outMetaState = found->metaState;
+            return true;
         }
     }
     return false;
 }
 
-bool
-KeyCharacterMap::getEvents(uint16_t* chars, size_t len,
-                           Vector<int32_t>* keys, Vector<uint32_t>* modifiers)
-{
-    for (size_t i=0; i<len; i++) {
-        uint32_t k, mods;
-        if (find_char(chars[i], &k, &mods)) {
-            keys->add(k);
-            modifiers->add(mods);
-        } else {
-            return false;
-        }
+void KeyCharacterMap::addKey(Vector<KeyEvent>& outEvents,
+        int32_t deviceId, int32_t keyCode, int32_t metaState, bool down, nsecs_t time) {
+    outEvents.push();
+    KeyEvent& event = outEvents.editTop();
+    event.initialize(deviceId, AINPUT_SOURCE_KEYBOARD,
+            down ? AKEY_EVENT_ACTION_DOWN : AKEY_EVENT_ACTION_UP,
+            0, keyCode, 0, metaState, 0, time, time);
+}
+
+void KeyCharacterMap::addMetaKeys(Vector<KeyEvent>& outEvents,
+        int32_t deviceId, int32_t metaState, bool down, nsecs_t time,
+        int32_t* currentMetaState) {
+    // Add and remove meta keys symmetrically.
+    if (down) {
+        addLockedMetaKey(outEvents, deviceId, metaState, time,
+                AKEYCODE_CAPS_LOCK, AMETA_CAPS_LOCK_ON, currentMetaState);
+        addLockedMetaKey(outEvents, deviceId, metaState, time,
+                AKEYCODE_NUM_LOCK, AMETA_NUM_LOCK_ON, currentMetaState);
+        addLockedMetaKey(outEvents, deviceId, metaState, time,
+                AKEYCODE_SCROLL_LOCK, AMETA_SCROLL_LOCK_ON, currentMetaState);
+
+        addDoubleEphemeralMetaKey(outEvents, deviceId, metaState, true, time,
+                AKEYCODE_SHIFT_LEFT, AMETA_SHIFT_LEFT_ON,
+                AKEYCODE_SHIFT_RIGHT, AMETA_SHIFT_RIGHT_ON,
+                AMETA_SHIFT_ON, currentMetaState);
+        addDoubleEphemeralMetaKey(outEvents, deviceId, metaState, true, time,
+                AKEYCODE_ALT_LEFT, AMETA_ALT_LEFT_ON,
+                AKEYCODE_ALT_RIGHT, AMETA_ALT_RIGHT_ON,
+                AMETA_ALT_ON, currentMetaState);
+        addDoubleEphemeralMetaKey(outEvents, deviceId, metaState, true, time,
+                AKEYCODE_CTRL_LEFT, AMETA_CTRL_LEFT_ON,
+                AKEYCODE_CTRL_RIGHT, AMETA_CTRL_RIGHT_ON,
+                AMETA_CTRL_ON, currentMetaState);
+        addDoubleEphemeralMetaKey(outEvents, deviceId, metaState, true, time,
+                AKEYCODE_META_LEFT, AMETA_META_LEFT_ON,
+                AKEYCODE_META_RIGHT, AMETA_META_RIGHT_ON,
+                AMETA_META_ON, currentMetaState);
+
+        addSingleEphemeralMetaKey(outEvents, deviceId, metaState, true, time,
+                AKEYCODE_SYM, AMETA_SYM_ON, currentMetaState);
+        addSingleEphemeralMetaKey(outEvents, deviceId, metaState, true, time,
+                AKEYCODE_FUNCTION, AMETA_FUNCTION_ON, currentMetaState);
+    } else {
+        addSingleEphemeralMetaKey(outEvents, deviceId, metaState, false, time,
+                AKEYCODE_FUNCTION, AMETA_FUNCTION_ON, currentMetaState);
+        addSingleEphemeralMetaKey(outEvents, deviceId, metaState, false, time,
+                AKEYCODE_SYM, AMETA_SYM_ON, currentMetaState);
+
+        addDoubleEphemeralMetaKey(outEvents, deviceId, metaState, false, time,
+                AKEYCODE_META_LEFT, AMETA_META_LEFT_ON,
+                AKEYCODE_META_RIGHT, AMETA_META_RIGHT_ON,
+                AMETA_META_ON, currentMetaState);
+        addDoubleEphemeralMetaKey(outEvents, deviceId, metaState, false, time,
+                AKEYCODE_CTRL_LEFT, AMETA_CTRL_LEFT_ON,
+                AKEYCODE_CTRL_RIGHT, AMETA_CTRL_RIGHT_ON,
+                AMETA_CTRL_ON, currentMetaState);
+        addDoubleEphemeralMetaKey(outEvents, deviceId, metaState, false, time,
+                AKEYCODE_ALT_LEFT, AMETA_ALT_LEFT_ON,
+                AKEYCODE_ALT_RIGHT, AMETA_ALT_RIGHT_ON,
+                AMETA_ALT_ON, currentMetaState);
+        addDoubleEphemeralMetaKey(outEvents, deviceId, metaState, false, time,
+                AKEYCODE_SHIFT_LEFT, AMETA_SHIFT_LEFT_ON,
+                AKEYCODE_SHIFT_RIGHT, AMETA_SHIFT_RIGHT_ON,
+                AMETA_SHIFT_ON, currentMetaState);
+
+        addLockedMetaKey(outEvents, deviceId, metaState, time,
+                AKEYCODE_SCROLL_LOCK, AMETA_SCROLL_LOCK_ON, currentMetaState);
+        addLockedMetaKey(outEvents, deviceId, metaState, time,
+                AKEYCODE_NUM_LOCK, AMETA_NUM_LOCK_ON, currentMetaState);
+        addLockedMetaKey(outEvents, deviceId, metaState, time,
+                AKEYCODE_CAPS_LOCK, AMETA_CAPS_LOCK_ON, currentMetaState);
     }
-    return true;
 }
 
-KeyCharacterMap::Key*
-KeyCharacterMap::find_key(int keycode)
-{
-    Key* keys = m_keys;
-    int low = 0;
-    int high = m_keyCount - 1;
-    int mid;
-    int n;
-    while (low <= high) {
-        mid = (low + high) / 2;
-        n = keys[mid].keycode;
-        if (keycode < n) {
-            high = mid - 1;
-        } else if (keycode > n) {
-            low = mid + 1;
-        } else {
-            return keys + mid;
-        }
+bool KeyCharacterMap::addSingleEphemeralMetaKey(Vector<KeyEvent>& outEvents,
+        int32_t deviceId, int32_t metaState, bool down, nsecs_t time,
+        int32_t keyCode, int32_t keyMetaState,
+        int32_t* currentMetaState) {
+    if ((metaState & keyMetaState) == keyMetaState) {
+        *currentMetaState = updateMetaState(keyCode, down, *currentMetaState);
+        addKey(outEvents, deviceId, keyCode, *currentMetaState, down, time);
+        return true;
     }
-    return NULL;
+    return false;
 }
 
-KeyCharacterMap*
-KeyCharacterMap::load(int id)
-{
-    KeyCharacterMap* map;
-    char path[PATH_MAX];
-    char propName[100];
-    char dev[PROPERTY_VALUE_MAX];
-    char fn[PROPERTY_VALUE_MAX];
-    int err;
-
-    // Check whether the EventHub has set a key character map filename for us already.
-    sprintf(propName, "hw.keyboards.%u.kcmfile", id);
-    err = property_get(propName, fn, "");
-    if (err > 0) {
-        map = try_file(fn);
-        if (map) {
-            return map;
-        }
-        LOGW("Error loading keycharmap file '%s'. %s='%s'", path, propName, fn);
-    }
-
-    // Try using the device name.
-    const char* root = getenv("ANDROID_ROOT");
-
-    sprintf(propName, "hw.keyboards.%u.devname", id);
-    err = property_get(propName, dev, "");
-    if (err > 0) {
-        // replace all the spaces with underscores
-        strcpy(fn, dev);
-        for (char *p = strchr(fn, ' '); p && *p; p = strchr(p + 1, ' '))
-            *p = '_';
-        snprintf(path, sizeof(path), "%s/usr/keychars/%s.kcm.bin", root, fn);
-        map = try_file(path);
-        if (map) {
-            return map;
+void KeyCharacterMap::addDoubleEphemeralMetaKey(Vector<KeyEvent>& outEvents,
+        int32_t deviceId, int32_t metaState, bool down, nsecs_t time,
+        int32_t leftKeyCode, int32_t leftKeyMetaState,
+        int32_t rightKeyCode, int32_t rightKeyMetaState,
+        int32_t eitherKeyMetaState,
+        int32_t* currentMetaState) {
+    bool specific = false;
+    specific |= addSingleEphemeralMetaKey(outEvents, deviceId, metaState, down, time,
+            leftKeyCode, leftKeyMetaState, currentMetaState);
+    specific |= addSingleEphemeralMetaKey(outEvents, deviceId, metaState, down, time,
+            rightKeyCode, rightKeyMetaState, currentMetaState);
+
+    if (!specific) {
+        addSingleEphemeralMetaKey(outEvents, deviceId, metaState, down, time,
+                leftKeyCode, eitherKeyMetaState, currentMetaState);
+    }
+}
+
+void KeyCharacterMap::addLockedMetaKey(Vector<KeyEvent>& outEvents,
+        int32_t deviceId, int32_t metaState, nsecs_t time,
+        int32_t keyCode, int32_t keyMetaState,
+        int32_t* currentMetaState) {
+    if ((metaState & keyMetaState) == keyMetaState) {
+        *currentMetaState = updateMetaState(keyCode, true, *currentMetaState);
+        addKey(outEvents, deviceId, keyCode, *currentMetaState, true, time);
+        *currentMetaState = updateMetaState(keyCode, false, *currentMetaState);
+        addKey(outEvents, deviceId, keyCode, *currentMetaState, false, time);
+    }
+}
+
+
+// --- KeyCharacterMap::Key ---
+
+KeyCharacterMap::Key::Key() :
+        label(0), number(0), firstBehavior(NULL) {
+}
+
+KeyCharacterMap::Key::~Key() {
+    Behavior* behavior = firstBehavior;
+    while (behavior) {
+        Behavior* next = behavior->next;
+        delete behavior;
+        behavior = next;
+    }
+}
+
+
+// --- KeyCharacterMap::Behavior ---
+
+KeyCharacterMap::Behavior::Behavior() :
+        next(NULL), metaState(0), character(0), fallbackKeyCode(0) {
+}
+
+
+// --- KeyCharacterMap::Parser ---
+
+KeyCharacterMap::Parser::Parser(KeyCharacterMap* map, Tokenizer* tokenizer) :
+        mMap(map), mTokenizer(tokenizer), mState(STATE_TOP) {
+}
+
+KeyCharacterMap::Parser::~Parser() {
+}
+
+status_t KeyCharacterMap::Parser::parse() {
+    while (!mTokenizer->isEof()) {
+#if DEBUG_PARSER
+        LOGD("Parsing %s: '%s'.", mTokenizer->getLocation().string(),
+                mTokenizer->peekRemainderOfLine().string());
+#endif
+
+        mTokenizer->skipDelimiters(WHITESPACE);
+
+        if (!mTokenizer->isEol() && mTokenizer->peekChar() != '#') {
+            switch (mState) {
+            case STATE_TOP: {
+                String8 keywordToken = mTokenizer->nextToken(WHITESPACE);
+                if (keywordToken == "type") {
+                    mTokenizer->skipDelimiters(WHITESPACE);
+                    status_t status = parseType();
+                    if (status) return status;
+                } else if (keywordToken == "key") {
+                    mTokenizer->skipDelimiters(WHITESPACE);
+                    status_t status = parseKey();
+                    if (status) return status;
+                } else {
+                    LOGE("%s: Expected keyword, got '%s'.", mTokenizer->getLocation().string(),
+                            keywordToken.string());
+                    return BAD_VALUE;
+                }
+                break;
+            }
+
+            case STATE_KEY: {
+                status_t status = parseKeyProperty();
+                if (status) return status;
+                break;
+            }
+            }
+
+            mTokenizer->skipDelimiters(WHITESPACE);
+            if (!mTokenizer->isEol()) {
+                LOGE("%s: Expected end of line, got '%s'.",
+                        mTokenizer->getLocation().string(),
+                        mTokenizer->peekRemainderOfLine().string());
+                return BAD_VALUE;
+            }
         }
-        LOGW("Error loading keycharmap file '%s'. %s='%s'", path, propName, dev);
-    } else {
-        LOGW("No keyboard for id %d", id);
+
+        mTokenizer->nextLine();
     }
 
-    snprintf(path, sizeof(path), "%s/usr/keychars/qwerty.kcm.bin", root);
-    map = try_file(path);
-    if (map) {
-        LOGW("Using default keymap: %s", path);
-        return map;
+    if (mState != STATE_TOP) {
+        LOGE("%s: Unterminated key description at end of file.",
+                mTokenizer->getLocation().string());
+        return BAD_VALUE;
     }
 
-    LOGE("Can't find any keycharmaps (also tried %s)", path);
-    return NULL;
+    if (mMap->mType == KEYBOARD_TYPE_UNKNOWN) {
+        LOGE("%s: Missing required keyboard 'type' declaration.",
+                mTokenizer->getLocation().string());
+        return BAD_VALUE;
+    }
+
+    return NO_ERROR;
 }
 
-KeyCharacterMap*
-KeyCharacterMap::try_file(const char* filename)
-{
-    KeyCharacterMap* rv = NULL;
-    Key* keys;
-    int fd;
-    off_t filesize;
-    Header header;
-    int err;
-    
-    fd = open(filename, O_RDONLY);
-    if (fd == -1) {
-        LOGW("Can't open keycharmap file");
-        return NULL;
+status_t KeyCharacterMap::Parser::parseType() {
+    if (mMap->mType != KEYBOARD_TYPE_UNKNOWN) {
+        LOGE("%s: Duplicate keyboard 'type' declaration.",
+                mTokenizer->getLocation().string());
+        return BAD_VALUE;
     }
 
-    filesize = lseek(fd, 0, SEEK_END);
-    lseek(fd, 0, SEEK_SET);
+    KeyboardType type;
+    String8 typeToken = mTokenizer->nextToken(WHITESPACE);
+    if (typeToken == "NUMERIC") {
+        type = KEYBOARD_TYPE_NUMERIC;
+    } else if (typeToken == "PREDICTIVE") {
+        type = KEYBOARD_TYPE_PREDICTIVE;
+    } else if (typeToken == "ALPHA") {
+        type = KEYBOARD_TYPE_ALPHA;
+    } else if (typeToken == "FULL") {
+        type = KEYBOARD_TYPE_FULL;
+    } else if (typeToken == "SPECIAL_FUNCTION") {
+        type = KEYBOARD_TYPE_SPECIAL_FUNCTION;
+    } else {
+        LOGE("%s: Expected keyboard type label, got '%s'.", mTokenizer->getLocation().string(),
+                typeToken.string());
+        return BAD_VALUE;
+    }
+
+#if DEBUG_PARSER
+    LOGD("Parsed type: type=%d.", type);
+#endif
+    mMap->mType = type;
+    return NO_ERROR;
+}
 
-    // validate the header
-    if (filesize <= (off_t)sizeof(header)) {
-        LOGW("Bad keycharmap - filesize=%d\n", (int)filesize);
-        goto cleanup1;
+status_t KeyCharacterMap::Parser::parseKey() {
+    String8 keyCodeToken = mTokenizer->nextToken(WHITESPACE);
+    int32_t keyCode = getKeyCodeByLabel(keyCodeToken.string());
+    if (!keyCode) {
+        LOGE("%s: Expected key code label, got '%s'.", mTokenizer->getLocation().string(),
+                keyCodeToken.string());
+        return BAD_VALUE;
+    }
+    if (mMap->mKeys.indexOfKey(keyCode) >= 0) {
+        LOGE("%s: Duplicate entry for key code '%s'.", mTokenizer->getLocation().string(),
+                keyCodeToken.string());
+        return BAD_VALUE;
     }
 
-    err = read(fd, &header, sizeof(header));
-    if (err == -1) {
-        LOGW("Error reading keycharmap file");
-        goto cleanup1;
+    mTokenizer->skipDelimiters(WHITESPACE);
+    String8 openBraceToken = mTokenizer->nextToken(WHITESPACE);
+    if (openBraceToken != "{") {
+        LOGE("%s: Expected '{' after key code label, got '%s'.",
+                mTokenizer->getLocation().string(), openBraceToken.string());
+        return BAD_VALUE;
     }
 
-    if (0 != memcmp(header.magic, "keychar", 8)) {
-        LOGW("Bad keycharmap magic token");
-        goto cleanup1;
+#if DEBUG_PARSER
+    LOGD("Parsed beginning of key: keyCode=%d.", keyCode);
+#endif
+    mKeyCode = keyCode;
+    mMap->mKeys.add(keyCode, new Key());
+    mState = STATE_KEY;
+    return NO_ERROR;
+}
+
+status_t KeyCharacterMap::Parser::parseKeyProperty() {
+    String8 token = mTokenizer->nextToken(WHITESPACE_OR_PROPERTY_DELIMITER);
+    if (token == "}") {
+        mState = STATE_TOP;
+        return NO_ERROR;
     }
-    if (header.endian != 0x12345678) {
-        LOGW("Bad keycharmap endians");
-        goto cleanup1;
+
+    Vector<Property> properties;
+
+    // Parse all comma-delimited property names up to the first colon.
+    for (;;) {
+        if (token == "label") {
+            properties.add(Property(PROPERTY_LABEL));
+        } else if (token == "number") {
+            properties.add(Property(PROPERTY_NUMBER));
+        } else {
+            int32_t metaState;
+            status_t status = parseModifier(token, &metaState);
+            if (status) {
+                LOGE("%s: Expected a property name or modifier, got '%s'.",
+                        mTokenizer->getLocation().string(), token.string());
+                return status;
+            }
+            properties.add(Property(PROPERTY_META, metaState));
+        }
+
+        mTokenizer->skipDelimiters(WHITESPACE);
+        if (!mTokenizer->isEol()) {
+            char ch = mTokenizer->nextChar();
+            if (ch == ':') {
+                break;
+            } else if (ch == ',') {
+                mTokenizer->skipDelimiters(WHITESPACE);
+                token = mTokenizer->nextToken(WHITESPACE_OR_PROPERTY_DELIMITER);
+                continue;
+            }
+        }
+
+        LOGE("%s: Expected ',' or ':' after property name.",
+                mTokenizer->getLocation().string());
+        return BAD_VALUE;
     }
-    if ((header.version & 0xff) != 2) {
-        LOGW("Only support keycharmap version 2 (got 0x%08x)", header.version);
-        goto cleanup1;
+
+    // Parse behavior after the colon.
+    mTokenizer->skipDelimiters(WHITESPACE);
+
+    Behavior behavior;
+    bool haveCharacter = false;
+    bool haveFallback = false;
+
+    do {
+        char ch = mTokenizer->peekChar();
+        if (ch == '\'') {
+            char16_t character;
+            status_t status = parseCharacterLiteral(&character);
+            if (status || !character) {
+                LOGE("%s: Invalid character literal for key.",
+                        mTokenizer->getLocation().string());
+                return BAD_VALUE;
+            }
+            if (haveCharacter) {
+                LOGE("%s: Cannot combine multiple character literals or 'none'.",
+                        mTokenizer->getLocation().string());
+                return BAD_VALUE;
+            }
+            behavior.character = character;
+            haveCharacter = true;
+        } else {
+            token = mTokenizer->nextToken(WHITESPACE);
+            if (token == "none") {
+                if (haveCharacter) {
+                    LOGE("%s: Cannot combine multiple character literals or 'none'.",
+                            mTokenizer->getLocation().string());
+                    return BAD_VALUE;
+                }
+                haveCharacter = true;
+            } else if (token == "fallback") {
+                mTokenizer->skipDelimiters(WHITESPACE);
+                token = mTokenizer->nextToken(WHITESPACE);
+                int32_t keyCode = getKeyCodeByLabel(token.string());
+                if (!keyCode) {
+                    LOGE("%s: Invalid key code label for fallback behavior, got '%s'.",
+                            mTokenizer->getLocation().string(),
+                            token.string());
+                    return BAD_VALUE;
+                }
+                if (haveFallback) {
+                    LOGE("%s: Cannot combine multiple fallback key codes.",
+                            mTokenizer->getLocation().string());
+                    return BAD_VALUE;
+                }
+                behavior.fallbackKeyCode = keyCode;
+                haveFallback = true;
+            } else {
+                LOGE("%s: Expected a key behavior after ':'.",
+                        mTokenizer->getLocation().string());
+                return BAD_VALUE;
+            }
+        }
+
+        mTokenizer->skipDelimiters(WHITESPACE);
+    } while (!mTokenizer->isEol());
+
+    // Add the behavior.
+    Key* key = mMap->mKeys.valueFor(mKeyCode);
+    for (size_t i = 0; i < properties.size(); i++) {
+        const Property& property = properties.itemAt(i);
+        switch (property.property) {
+        case PROPERTY_LABEL:
+            if (key->label) {
+                LOGE("%s: Duplicate label for key.",
+                        mTokenizer->getLocation().string());
+                return BAD_VALUE;
+            }
+            key->label = behavior.character;
+#if DEBUG_PARSER
+            LOGD("Parsed key label: keyCode=%d, label=%d.", mKeyCode, key->label);
+#endif
+            break;
+        case PROPERTY_NUMBER:
+            if (key->number) {
+                LOGE("%s: Duplicate number for key.",
+                        mTokenizer->getLocation().string());
+                return BAD_VALUE;
+            }
+            key->number = behavior.character;
+#if DEBUG_PARSER
+            LOGD("Parsed key number: keyCode=%d, number=%d.", mKeyCode, key->number);
+#endif
+            break;
+        case PROPERTY_META: {
+            for (Behavior* b = key->firstBehavior; b; b = b->next) {
+                if (b->metaState == property.metaState) {
+                    LOGE("%s: Duplicate key behavior for modifier.",
+                            mTokenizer->getLocation().string());
+                    return BAD_VALUE;
+                }
+            }
+            Behavior* newBehavior = new Behavior(behavior);
+            newBehavior->metaState = property.metaState;
+            newBehavior->next = key->firstBehavior;
+            key->firstBehavior = newBehavior;
+#if DEBUG_PARSER
+            LOGD("Parsed key meta: keyCode=%d, meta=0x%x, char=%d, fallback=%d.", mKeyCode,
+                    newBehavior->metaState, newBehavior->character, newBehavior->fallbackKeyCode);
+#endif
+            break;
+        }
+        }
+    }
+    return NO_ERROR;
+}
+
+status_t KeyCharacterMap::Parser::parseModifier(const String8& token, int32_t* outMetaState) {
+    if (token == "base") {
+        *outMetaState = 0;
+        return NO_ERROR;
+    }
+
+    int32_t combinedMeta = 0;
+
+    const char* str = token.string();
+    const char* start = str;
+    for (const char* cur = str; ; cur++) {
+        char ch = *cur;
+        if (ch == '+' || ch == '\0') {
+            size_t len = cur - start;
+            int32_t metaState = 0;
+            for (size_t i = 0; i < sizeof(modifiers) / sizeof(Modifier); i++) {
+                if (strlen(modifiers[i].label) == len
+                        && strncmp(modifiers[i].label, start, len) == 0) {
+                    metaState = modifiers[i].metaState;
+                    break;
+                }
+            }
+            if (!metaState) {
+                return BAD_VALUE;
+            }
+            if (combinedMeta & metaState) {
+                LOGE("%s: Duplicate modifier combination '%s'.",
+                        mTokenizer->getLocation().string(), token.string());
+                return BAD_VALUE;
+            }
+
+            combinedMeta |= metaState;
+
+            if (ch == '\0') {
+                break;
+            }
+        }
     }
-    if (filesize < (off_t)(sizeof(Header)+(sizeof(Key)*header.keycount))) {
-        LOGW("Bad keycharmap file size\n");
-        goto cleanup1;
+    *outMetaState = combinedMeta;
+    return NO_ERROR;
+}
+
+status_t KeyCharacterMap::Parser::parseCharacterLiteral(char16_t* outCharacter) {
+    char ch = mTokenizer->nextChar();
+    if (ch != '\'') {
+        goto Error;
     }
 
-    // read the key data
-    keys = (Key*)malloc(sizeof(Key)*header.keycount);
-    err = read(fd, keys, sizeof(Key)*header.keycount);
-    if (err == -1) {
-        LOGW("Error reading keycharmap file");
-        free(keys);
-        goto cleanup1;
+    ch = mTokenizer->nextChar();
+    if (ch == '\\') {
+        // Escape sequence.
+        ch = mTokenizer->nextChar();
+        if (ch == 'n') {
+            *outCharacter = '\n';
+        } else if (ch == 't') {
+            *outCharacter = '\t';
+        } else if (ch == '\\') {
+            *outCharacter = '\\';
+        } else if (ch == '\'') {
+            *outCharacter = '\'';
+        } else if (ch == '"') {
+            *outCharacter = '"';
+        } else if (ch == 'u') {
+            *outCharacter = 0;
+            for (int i = 0; i < 4; i++) {
+                ch = mTokenizer->nextChar();
+                int digit;
+                if (ch >= '0' && ch <= '9') {
+                    digit = ch - '0';
+                } else if (ch >= 'A' && ch <= 'F') {
+                    digit = ch - 'A' + 10;
+                } else if (ch >= 'a' && ch <= 'f') {
+                    digit = ch - 'a' + 10;
+                } else {
+                    goto Error;
+                }
+                *outCharacter = (*outCharacter << 4) | digit;
+            }
+        } else {
+            goto Error;
+        }
+    } else if (ch >= 32 && ch <= 126 && ch != '\'') {
+        // ASCII literal character.
+        *outCharacter = ch;
+    } else {
+        goto Error;
     }
 
-    // return the object
-    rv = new KeyCharacterMap;
-    rv->m_keyCount = header.keycount;
-    rv->m_keys = keys;
-    rv->m_type = header.kbdtype;
+    ch = mTokenizer->nextChar();
+    if (ch != '\'') {
+        goto Error;
+    }
 
-cleanup1:
-    close(fd);
+    // Ensure that we consumed the entire token.
+    if (mTokenizer->nextToken(WHITESPACE).isEmpty()) {
+        return NO_ERROR;
+    }
 
-    return rv;
+Error:
+    LOGE("%s: Malformed character literal.", mTokenizer->getLocation().string());
+    return BAD_VALUE;
 }
+
+} // namespace android
diff --git a/libs/ui/KeyLayoutMap.cpp b/libs/ui/KeyLayoutMap.cpp
index 15ae54c..56bc26f 100644
--- a/libs/ui/KeyLayoutMap.cpp
+++ b/libs/ui/KeyLayoutMap.cpp
@@ -1,234 +1,213 @@
+/*
+ * Copyright (C) 2008 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
 #define LOG_TAG "KeyLayoutMap"
 
-#include "KeyLayoutMap.h"
-#include <sys/types.h>
-#include <sys/stat.h>
-#include <fcntl.h>
-#include <unistd.h>
-#include <errno.h>
-#include <utils/String8.h>
 #include <stdlib.h>
-#include <ui/KeycodeLabels.h>
+#include <android/keycodes.h>
+#include <ui/Keyboard.h>
+#include <ui/KeyLayoutMap.h>
 #include <utils/Log.h>
+#include <utils/Errors.h>
+#include <utils/Tokenizer.h>
+#include <utils/Timers.h>
+
+// Enables debug output for the parser.
+#define DEBUG_PARSER 0
+
+// Enables debug output for parser performance.
+#define DEBUG_PARSER_PERFORMANCE 0
+
+// Enables debug output for mapping.
+#define DEBUG_MAPPING 0
+
 
 namespace android {
 
-KeyLayoutMap::KeyLayoutMap()
-    :m_status(NO_INIT),
-     m_keys()
-{
-}
+static const char* WHITESPACE = " \t\r";
 
-KeyLayoutMap::~KeyLayoutMap()
-{
+// --- KeyLayoutMap ---
+
+KeyLayoutMap::KeyLayoutMap() {
 }
 
-static String8
-next_token(char const** p, int *line)
-{
-    bool begun = false;
-    const char* begin = *p;
-    const char* end = *p;
-    while (true) {
-        if (*end == '\n') {
-            (*line)++;
-        }
-        switch (*end)
-        {
-            case '#':
-                if (begun) {
-                    *p = end;
-                    return String8(begin, end-begin);
-                } else {
-                    do {
-                        begin++;
-                        end++;
-                    } while (*begin != '\0' && *begin != '\n');
-                }
-            case '\0':
-            case ' ':
-            case '\n':
-            case '\r':
-            case '\t':
-                if (begun || (*end == '\0')) {
-                    *p = end;
-                    return String8(begin, end-begin);
-                } else {
-                    begin++;
-                    end++;
-                    break;
-                }
-            default:
-                end++;
-                begun = true;
-        }
-    }
+KeyLayoutMap::~KeyLayoutMap() {
 }
 
-static int32_t
-token_to_value(const char *literal, const KeycodeLabel *list)
-{
-    while (list->literal) {
-        if (0 == strcmp(literal, list->literal)) {
-            return list->value;
+status_t KeyLayoutMap::load(const String8& filename, KeyLayoutMap** outMap) {
+    *outMap = NULL;
+
+    Tokenizer* tokenizer;
+    status_t status = Tokenizer::open(filename, &tokenizer);
+    if (status) {
+        LOGE("Error %d opening key layout map file %s.", status, filename.string());
+    } else {
+        KeyLayoutMap* map = new KeyLayoutMap();
+        if (!map) {
+            LOGE("Error allocating key layout map.");
+            status = NO_MEMORY;
+        } else {
+#if DEBUG_PARSER_PERFORMANCE
+            nsecs_t startTime = systemTime(SYSTEM_TIME_MONOTONIC);
+#endif
+            Parser parser(map, tokenizer);
+            status = parser.parse();
+#if DEBUG_PARSER_PERFORMANCE
+            nsecs_t elapsedTime = systemTime(SYSTEM_TIME_MONOTONIC) - startTime;
+            LOGD("Parsed key layout map file '%s' %d lines in %0.3fms.",
+                    tokenizer->getFilename().string(), tokenizer->getLineNumber(),
+                    elapsedTime / 1000000.0);
+#endif
+            if (status) {
+                delete map;
+            } else {
+                *outMap = map;
+            }
         }
-        list++;
+        delete tokenizer;
     }
-    return list->value;
+    return status;
 }
 
-status_t
-KeyLayoutMap::load(const char* filename)
-{
-    int fd = open(filename, O_RDONLY);
-    if (fd < 0) {
-        LOGE("error opening file=%s err=%s\n", filename, strerror(errno));
-        m_status = errno;
-        return errno;
+status_t KeyLayoutMap::map(int32_t scanCode, int32_t* keyCode, uint32_t* flags) const {
+    ssize_t index = mKeys.indexOfKey(scanCode);
+    if (index < 0) {
+#if DEBUG_MAPPING
+        LOGD("map: scanCode=%d ~ Failed.", scanCode);
+#endif
+        *keyCode = AKEYCODE_UNKNOWN;
+        *flags = 0;
+        return NAME_NOT_FOUND;
     }
 
-    off_t len = lseek(fd, 0, SEEK_END);
-    off_t errlen = lseek(fd, 0, SEEK_SET);
-    if (len < 0 || errlen < 0) {
-        close(fd);
-        LOGE("error seeking file=%s err=%s\n", filename, strerror(errno));
-        m_status = errno;
-        return errno;
-    }
+    const Key& k = mKeys.valueAt(index);
+    *keyCode = k.keyCode;
+    *flags = k.flags;
 
-    char* buf = (char*)malloc(len+1);
-    if (read(fd, buf, len) != len) {
-        LOGE("error reading file=%s err=%s\n", filename, strerror(errno));
-        m_status = errno != 0 ? errno : ((int)NOT_ENOUGH_DATA);
-        return errno != 0 ? errno : ((int)NOT_ENOUGH_DATA);
-    }
-    errno = 0;
-    buf[len] = '\0';
+#if DEBUG_MAPPING
+    LOGD("map: scanCode=%d ~ Result keyCode=%d, flags=0x%08x.", scanCode, *keyCode, *flags);
+#endif
+    return NO_ERROR;
+}
 
-    int32_t scancode = -1;
-    int32_t keycode = -1;
-    uint32_t flags = 0;
-    uint32_t tmp;
-    char* end;
-    status_t err = NO_ERROR;
-    int line = 1;
-    char const* p = buf;
-    enum { BEGIN, SCANCODE, KEYCODE, FLAG } state = BEGIN;
-    while (true) {
-        String8 token = next_token(&p, &line);
-        if (*p == '\0') {
-            break;
-        }
-        switch (state)
-        {
-            case BEGIN:
-                if (token == "key") {
-                    state = SCANCODE;
-                } else {
-                    LOGE("%s:%d: expected key, got '%s'\n", filename, line,
-                            token.string());
-                    err = BAD_VALUE;
-                    goto done;
-                }
-                break;
-            case SCANCODE:
-                scancode = strtol(token.string(), &end, 0);
-                if (*end != '\0') {
-                    LOGE("%s:%d: expected scancode (a number), got '%s'\n",
-                            filename, line, token.string());
-                    goto done;
-                }
-                //LOGI("%s:%d: got scancode %d\n", filename, line, scancode );
-                state = KEYCODE;
-                break;
-            case KEYCODE:
-                keycode = token_to_value(token.string(), KEYCODES);
-                //LOGI("%s:%d: got keycode %d for %s\n", filename, line, keycode, token.string() );
-                if (keycode == 0) {
-                    LOGE("%s:%d: expected keycode, got '%s'\n",
-                            filename, line, token.string());
-                    goto done;
-                }
-                state = FLAG;
-                break;
-            case FLAG:
-                if (token == "key") {
-                    if (scancode != -1) {
-                        //LOGI("got key decl scancode=%d keycode=%d"
-                        //       " flags=0x%08x\n", scancode, keycode, flags);
-                        Key k = { keycode, flags };
-                        m_keys.add(scancode, k);
-                        state = SCANCODE;
-                        scancode = -1;
-                        keycode = -1;
-                        flags = 0;
-                        break;
-                    }
-                }
-                tmp = token_to_value(token.string(), FLAGS);
-                //LOGI("%s:%d: got flags %x for %s\n", filename, line, tmp, token.string() );
-                if (tmp == 0) {
-                    LOGE("%s:%d: expected flag, got '%s'\n",
-                            filename, line, token.string());
-                    goto done;
-                }
-                flags |= tmp;
-                break;
+status_t KeyLayoutMap::findScanCodes(int32_t keyCode, Vector<int32_t>* outScanCodes) const {
+    const size_t N = mKeys.size();
+    for (size_t i=0; i<N; i++) {
+        if (mKeys.valueAt(i).keyCode == keyCode) {
+            outScanCodes->add(mKeys.keyAt(i));
         }
     }
-    if (state == FLAG && scancode != -1 ) {
-        //LOGI("got key decl scancode=%d keycode=%d"
-        //       " flags=0x%08x\n", scancode, keycode, flags);
-        Key k = { keycode, flags };
-        m_keys.add(scancode, k);
-    }
-
-done:
-    free(buf);
-    close(fd);
-
-    m_status = err;
-    return err;
+    return NO_ERROR;
 }
 
-status_t
-KeyLayoutMap::map(int32_t scancode, int32_t *keycode, uint32_t *flags) const
-{
-    if (m_status != NO_ERROR) {
-        return m_status;
-    }
+// --- KeyLayoutMap::Parser ---
 
-    ssize_t index = m_keys.indexOfKey(scancode);
-    if (index < 0) {
-        //LOGW("couldn't map scancode=%d\n", scancode);
-        return NAME_NOT_FOUND;
-    }
-
-    const Key& k = m_keys.valueAt(index);
+KeyLayoutMap::Parser::Parser(KeyLayoutMap* map, Tokenizer* tokenizer) :
+        mMap(map), mTokenizer(tokenizer) {
+}
 
-    *keycode = k.keycode;
-    *flags = k.flags;
+KeyLayoutMap::Parser::~Parser() {
+}
 
-    //LOGD("mapped scancode=%d to keycode=%d flags=0x%08x\n", scancode,
-    //        keycode, flags);
+status_t KeyLayoutMap::Parser::parse() {
+    while (!mTokenizer->isEof()) {
+#if DEBUG_PARSER
+        LOGD("Parsing %s: '%s'.", mTokenizer->getLocation().string(),
+                mTokenizer->peekRemainderOfLine().string());
+#endif
+
+        mTokenizer->skipDelimiters(WHITESPACE);
+
+        if (!mTokenizer->isEol() && mTokenizer->peekChar() != '#') {
+            String8 keywordToken = mTokenizer->nextToken(WHITESPACE);
+            if (keywordToken == "key") {
+                mTokenizer->skipDelimiters(WHITESPACE);
+                status_t status = parseKey();
+                if (status) return status;
+            } else {
+                LOGE("%s: Expected keyword, got '%s'.", mTokenizer->getLocation().string(),
+                        keywordToken.string());
+                return BAD_VALUE;
+            }
+
+            mTokenizer->skipDelimiters(WHITESPACE);
+            if (!mTokenizer->isEol()) {
+                LOGE("%s: Expected end of line, got '%s'.",
+                        mTokenizer->getLocation().string(),
+                        mTokenizer->peekRemainderOfLine().string());
+                return BAD_VALUE;
+            }
+        }
 
+        mTokenizer->nextLine();
+    }
     return NO_ERROR;
 }
 
-status_t
-KeyLayoutMap::findScancodes(int32_t keycode, Vector<int32_t>* outScancodes) const
-{
-    if (m_status != NO_ERROR) {
-        return m_status;
+status_t KeyLayoutMap::Parser::parseKey() {
+    String8 scanCodeToken = mTokenizer->nextToken(WHITESPACE);
+    char* end;
+    int32_t scanCode = int32_t(strtol(scanCodeToken.string(), &end, 0));
+    if (*end) {
+        LOGE("%s: Expected scan code number, got '%s'.", mTokenizer->getLocation().string(),
+                scanCodeToken.string());
+        return BAD_VALUE;
     }
-    
-    const size_t N = m_keys.size();
-    for (size_t i=0; i<N; i++) {
-        if (m_keys.valueAt(i).keycode == keycode) {
-            outScancodes->add(m_keys.keyAt(i));
+    if (mMap->mKeys.indexOfKey(scanCode) >= 0) {
+        LOGE("%s: Duplicate entry for scan code '%s'.", mTokenizer->getLocation().string(),
+                scanCodeToken.string());
+        return BAD_VALUE;
+    }
+
+    mTokenizer->skipDelimiters(WHITESPACE);
+    String8 keyCodeToken = mTokenizer->nextToken(WHITESPACE);
+    int32_t keyCode = getKeyCodeByLabel(keyCodeToken.string());
+    if (!keyCode) {
+        LOGE("%s: Expected key code label, got '%s'.", mTokenizer->getLocation().string(),
+                keyCodeToken.string());
+        return BAD_VALUE;
+    }
+
+    uint32_t flags = 0;
+    for (;;) {
+        mTokenizer->skipDelimiters(WHITESPACE);
+        if (mTokenizer->isEol()) break;
+
+        String8 flagToken = mTokenizer->nextToken(WHITESPACE);
+        uint32_t flag = getKeyFlagByLabel(flagToken.string());
+        if (!flag) {
+            LOGE("%s: Expected flag label, got '%s'.", mTokenizer->getLocation().string(),
+                    flagToken.string());
+            return BAD_VALUE;
         }
+        if (flags & flag) {
+            LOGE("%s: Duplicate flag '%s'.", mTokenizer->getLocation().string(),
+                    flagToken.string());
+            return BAD_VALUE;
+        }
+        flags |= flag;
     }
-    
+
+#if DEBUG_PARSER
+    LOGD("Parsed key: scanCode=%d, keyCode=%d, flags=0x%08x.", scanCode, keyCode, flags);
+#endif
+    Key key;
+    key.keyCode = keyCode;
+    key.flags = flags;
+    mMap->mKeys.add(scanCode, key);
     return NO_ERROR;
 }
 
diff --git a/libs/ui/KeyLayoutMap.h b/libs/ui/KeyLayoutMap.h
deleted file mode 100644
index 43f84ce..0000000
--- a/libs/ui/KeyLayoutMap.h
+++ /dev/null
@@ -1,31 +0,0 @@
-#ifndef KEYLAYOUTMAP_H
-#define KEYLAYOUTMAP_H
-
-#include <utils/KeyedVector.h>
-
-namespace android {
-
-class KeyLayoutMap
-{
-public:
-    KeyLayoutMap();
-    ~KeyLayoutMap();
-
-    status_t load(const char* filename);
-
-    status_t map(int32_t scancode, int32_t *keycode, uint32_t *flags) const;
-    status_t findScancodes(int32_t keycode, Vector<int32_t>* outScancodes) const;
-
-private:
-    struct Key {
-        int32_t keycode;
-        uint32_t flags;
-    };
-
-    status_t m_status;
-    KeyedVector<int32_t,Key> m_keys;
-};
-
-};
-
-#endif // KEYLAYOUTMAP_H
diff --git a/libs/ui/Keyboard.cpp b/libs/ui/Keyboard.cpp
new file mode 100644
index 0000000..de76e25
--- /dev/null
+++ b/libs/ui/Keyboard.cpp
@@ -0,0 +1,244 @@
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#define LOG_TAG "Keyboard"
+
+#include <stdlib.h>
+#include <unistd.h>
+#include <limits.h>
+
+#include <ui/Keyboard.h>
+#include <ui/KeycodeLabels.h>
+#include <utils/Errors.h>
+#include <utils/Log.h>
+#include <cutils/properties.h>
+
+namespace android {
+
+static void selectKeyMap(KeyMapInfo& keyMapInfo, const String8& keyMapName, bool defaultKeyMap) {
+    if (keyMapInfo.keyMapName.isEmpty()) {
+        keyMapInfo.keyMapName.setTo(keyMapName);
+        keyMapInfo.isDefaultKeyMap = defaultKeyMap;
+    }
+}
+
+static bool probeKeyMap(KeyMapInfo& keyMapInfo, const String8& keyMapName, bool defaultKeyMap) {
+    const char* root = getenv("ANDROID_ROOT");
+
+    // TODO Consider also looking somewhere in a writeable partition like /data for a
+    //      custom keymap supplied by the user for this device.
+    bool haveKeyLayout = !keyMapInfo.keyLayoutFile.isEmpty();
+    if (!haveKeyLayout) {
+        keyMapInfo.keyLayoutFile.setTo(root);
+        keyMapInfo.keyLayoutFile.append("/usr/keylayout/");
+        keyMapInfo.keyLayoutFile.append(keyMapName);
+        keyMapInfo.keyLayoutFile.append(".kl");
+        if (access(keyMapInfo.keyLayoutFile.string(), R_OK)) {
+            keyMapInfo.keyLayoutFile.clear();
+        } else {
+            haveKeyLayout = true;
+        }
+    }
+
+    bool haveKeyCharacterMap = !keyMapInfo.keyCharacterMapFile.isEmpty();
+    if (!haveKeyCharacterMap) {
+        keyMapInfo.keyCharacterMapFile.setTo(root);
+        keyMapInfo.keyCharacterMapFile.append("/usr/keychars/");
+        keyMapInfo.keyCharacterMapFile.append(keyMapName);
+        keyMapInfo.keyCharacterMapFile.append(".kcm");
+        if (access(keyMapInfo.keyCharacterMapFile.string(), R_OK)) {
+            keyMapInfo.keyCharacterMapFile.clear();
+        } else {
+            haveKeyCharacterMap = true;
+        }
+    }
+
+    if (haveKeyLayout || haveKeyCharacterMap) {
+        selectKeyMap(keyMapInfo, keyMapName, defaultKeyMap);
+    }
+    return haveKeyLayout && haveKeyCharacterMap;
+}
+
+status_t resolveKeyMap(const String8& deviceName, KeyMapInfo& outKeyMapInfo) {
+    // As an initial key map name, try using the device name.
+    String8 keyMapName(deviceName);
+    char* p = keyMapName.lockBuffer(keyMapName.size());
+    while (*p) {
+        if (*p == ' ') *p = '_';
+        p++;
+    }
+    keyMapName.unlockBuffer();
+
+    if (probeKeyMap(outKeyMapInfo, keyMapName, false)) return OK;
+
+    // TODO Consider allowing the user to configure a specific key map somehow.
+
+    // Try the Generic key map.
+    // TODO Apply some additional heuristics here to figure out what kind of
+    //      generic key map to use (US English, etc.).
+    keyMapName.setTo("Generic");
+    if (probeKeyMap(outKeyMapInfo, keyMapName, true)) return OK;
+
+    // Give up!
+    keyMapName.setTo("unknown");
+    selectKeyMap(outKeyMapInfo, keyMapName, true);
+    LOGE("Could not determine key map for device '%s'.", deviceName.string());
+    return NAME_NOT_FOUND;
+}
+
+void setKeyboardProperties(int32_t deviceId, const String8& deviceName,
+        const KeyMapInfo& keyMapInfo) {
+    char propName[PROPERTY_KEY_MAX];
+    snprintf(propName, sizeof(propName), "hw.keyboards.%u.devname", deviceId);
+    property_set(propName, deviceName.string());
+    snprintf(propName, sizeof(propName), "hw.keyboards.%u.keymap", deviceId);
+    property_set(propName, keyMapInfo.keyMapName.string());
+    snprintf(propName, sizeof(propName), "hw.keyboards.%u.klfile", deviceId);
+    property_set(propName, keyMapInfo.keyLayoutFile.string());
+    snprintf(propName, sizeof(propName), "hw.keyboards.%u.kcmfile", deviceId);
+    property_set(propName, keyMapInfo.keyCharacterMapFile.string());
+}
+
+void clearKeyboardProperties(int32_t deviceId) {
+    char propName[PROPERTY_KEY_MAX];
+    snprintf(propName, sizeof(propName), "hw.keyboards.%u.devname", deviceId);
+    property_set(propName, "");
+    snprintf(propName, sizeof(propName), "hw.keyboards.%u.keymap", deviceId);
+    property_set(propName, "");
+    snprintf(propName, sizeof(propName), "hw.keyboards.%u.klfile", deviceId);
+    property_set(propName, "");
+    snprintf(propName, sizeof(propName), "hw.keyboards.%u.kcmfile", deviceId);
+    property_set(propName, "");
+}
+
+status_t getKeyCharacterMapFile(int32_t deviceId, String8& outKeyCharacterMapFile) {
+    char propName[PROPERTY_KEY_MAX];
+    char fn[PROPERTY_VALUE_MAX];
+    snprintf(propName, sizeof(propName), "hw.keyboards.%u.kcmfile", deviceId);
+    if (property_get(propName, fn, "") > 0) {
+        outKeyCharacterMapFile.setTo(fn);
+        return OK;
+    }
+
+    const char* root = getenv("ANDROID_ROOT");
+    char path[PATH_MAX];
+    if (deviceId == DEVICE_ID_VIRTUAL_KEYBOARD) {
+        snprintf(path, sizeof(path), "%s/usr/keychars/Virtual.kcm", root);
+        if (!access(path, R_OK)) {
+            outKeyCharacterMapFile.setTo(path);
+            return OK;
+        }
+    }
+
+    snprintf(path, sizeof(path), "%s/usr/keychars/Generic.kcm", root);
+    if (!access(path, R_OK)) {
+        outKeyCharacterMapFile.setTo(path);
+        return OK;
+    }
+
+    LOGE("Can't find any key character map files (also tried %s)", path);
+    return NAME_NOT_FOUND;
+}
+
+static int lookupLabel(const char* literal, const KeycodeLabel *list) {
+    while (list->literal) {
+        if (strcmp(literal, list->literal) == 0) {
+            return list->value;
+        }
+        list++;
+    }
+    return list->value;
+}
+
+int32_t getKeyCodeByLabel(const char* label) {
+    return int32_t(lookupLabel(label, KEYCODES));
+}
+
+uint32_t getKeyFlagByLabel(const char* label) {
+    return uint32_t(lookupLabel(label, FLAGS));
+}
+
+static int32_t setEphemeralMetaState(int32_t mask, bool down, int32_t oldMetaState) {
+    int32_t newMetaState;
+    if (down) {
+        newMetaState = oldMetaState | mask;
+    } else {
+        newMetaState = oldMetaState &
+                ~(mask | AMETA_ALT_ON | AMETA_SHIFT_ON | AMETA_CTRL_ON | AMETA_META_ON);
+    }
+
+    if (newMetaState & (AMETA_ALT_LEFT_ON | AMETA_ALT_RIGHT_ON)) {
+        newMetaState |= AMETA_ALT_ON;
+    }
+
+    if (newMetaState & (AMETA_SHIFT_LEFT_ON | AMETA_SHIFT_RIGHT_ON)) {
+        newMetaState |= AMETA_SHIFT_ON;
+    }
+
+    if (newMetaState & (AMETA_CTRL_LEFT_ON | AMETA_CTRL_RIGHT_ON)) {
+        newMetaState |= AMETA_CTRL_ON;
+    }
+
+    if (newMetaState & (AMETA_META_LEFT_ON | AMETA_META_RIGHT_ON)) {
+        newMetaState |= AMETA_META_ON;
+    }
+    return newMetaState;
+}
+
+static int32_t toggleLockedMetaState(int32_t mask, bool down, int32_t oldMetaState) {
+    if (down) {
+        return oldMetaState;
+    } else {
+        return oldMetaState ^ mask;
+    }
+}
+
+int32_t updateMetaState(int32_t keyCode, bool down, int32_t oldMetaState) {
+    int32_t mask;
+    switch (keyCode) {
+    case AKEYCODE_ALT_LEFT:
+        return setEphemeralMetaState(AMETA_ALT_LEFT_ON, down, oldMetaState);
+    case AKEYCODE_ALT_RIGHT:
+        return setEphemeralMetaState(AMETA_ALT_RIGHT_ON, down, oldMetaState);
+    case AKEYCODE_SHIFT_LEFT:
+        return setEphemeralMetaState(AMETA_SHIFT_LEFT_ON, down, oldMetaState);
+    case AKEYCODE_SHIFT_RIGHT:
+        return setEphemeralMetaState(AMETA_SHIFT_RIGHT_ON, down, oldMetaState);
+    case AKEYCODE_SYM:
+        return setEphemeralMetaState(AMETA_SYM_ON, down, oldMetaState);
+    case AKEYCODE_FUNCTION:
+        return setEphemeralMetaState(AMETA_FUNCTION_ON, down, oldMetaState);
+    case AKEYCODE_CTRL_LEFT:
+        return setEphemeralMetaState(AMETA_CTRL_LEFT_ON, down, oldMetaState);
+    case AKEYCODE_CTRL_RIGHT:
+        return setEphemeralMetaState(AMETA_CTRL_RIGHT_ON, down, oldMetaState);
+    case AKEYCODE_META_LEFT:
+        return setEphemeralMetaState(AMETA_META_LEFT_ON, down, oldMetaState);
+    case AKEYCODE_META_RIGHT:
+        return setEphemeralMetaState(AMETA_META_RIGHT_ON, down, oldMetaState);
+    case AKEYCODE_CAPS_LOCK:
+        return toggleLockedMetaState(AMETA_CAPS_LOCK_ON, down, oldMetaState);
+    case AKEYCODE_NUM_LOCK:
+        return toggleLockedMetaState(AMETA_NUM_LOCK_ON, down, oldMetaState);
+    case AKEYCODE_SCROLL_LOCK:
+        return toggleLockedMetaState(AMETA_SCROLL_LOCK_ON, down, oldMetaState);
+    default:
+        return oldMetaState;
+    }
+}
+
+
+} // namespace android
diff --git a/libs/utils/Android.mk b/libs/utils/Android.mk
index 05a9674..9c01aea 100644
--- a/libs/utils/Android.mk
+++ b/libs/utils/Android.mk
@@ -41,6 +41,7 @@ commonSources:= \
 	TextOutput.cpp \
 	Threads.cpp \
 	Timers.cpp \
+	Tokenizer.cpp \
 	Unicode.cpp \
 	VectorImpl.cpp \
 	ZipFileCRO.cpp \
diff --git a/libs/utils/String8.cpp b/libs/utils/String8.cpp
index c8dc083..e531a2a 100644
--- a/libs/utils/String8.cpp
+++ b/libs/utils/String8.cpp
@@ -282,22 +282,28 @@ status_t String8::append(const char* other, size_t otherLen)
 
 status_t String8::appendFormat(const char* fmt, ...)
 {
-    va_list ap;
-    va_start(ap, fmt);
+    va_list args;
+    va_start(args, fmt);
 
+    status_t result = appendFormatV(fmt, args);
+
+    va_end(args);
+    return result;
+}
+
+status_t String8::appendFormatV(const char* fmt, va_list args)
+{
     int result = NO_ERROR;
-    int n = vsnprintf(NULL, 0, fmt, ap);
+    int n = vsnprintf(NULL, 0, fmt, args);
     if (n != 0) {
         size_t oldLength = length();
         char* buf = lockBuffer(oldLength + n);
         if (buf) {
-            vsnprintf(buf + oldLength, n + 1, fmt, ap);
+            vsnprintf(buf + oldLength, n + 1, fmt, args);
         } else {
             result = NO_MEMORY;
         }
     }
-
-    va_end(ap);
     return result;
 }
 
diff --git a/libs/utils/Tokenizer.cpp b/libs/utils/Tokenizer.cpp
new file mode 100644
index 0000000..19dadf0
--- /dev/null
+++ b/libs/utils/Tokenizer.cpp
@@ -0,0 +1,150 @@
+/*
+ * Copyright (C) 2010 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+#define LOG_TAG "Tokenizer"
+
+#include <stdlib.h>
+#include <unistd.h>
+#include <fcntl.h>
+#include <errno.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <sys/mman.h>
+#include <utils/Log.h>
+#include <utils/Tokenizer.h>
+
+// Enables debug output for the tokenizer.
+#define DEBUG_TOKENIZER 0
+
+
+namespace android {
+
+static inline bool isDelimiter(char ch, const char* delimiters) {
+    return strchr(delimiters, ch) != NULL;
+}
+
+
+Tokenizer::Tokenizer(const String8& filename, const char* buffer, size_t length) :
+        mFilename(filename), mBuffer(buffer), mLength(length),
+        mCurrent(buffer), mLineNumber(1) {
+}
+
+Tokenizer::~Tokenizer() {
+    munmap((void*)mBuffer, mLength);
+}
+
+status_t Tokenizer::open(const String8& filename, Tokenizer** outTokenizer) {
+    *outTokenizer = NULL;
+
+    int result = NO_ERROR;
+    int fd = ::open(filename.string(), O_RDONLY);
+    if (fd < 0) {
+        result = -errno;
+        LOGE("Error opening file '%s', %s.", filename.string(), strerror(errno));
+    } else {
+        struct stat64 stat;
+        if (fstat64(fd, &stat)) {
+            result = -errno;
+            LOGE("Error getting size of file '%s', %s.", filename.string(), strerror(errno));
+        } else {
+            size_t length = size_t(stat.st_size);
+            void* buffer = mmap(NULL, length, PROT_READ, MAP_FILE | MAP_PRIVATE, fd, 0);
+            if (buffer == MAP_FAILED) {
+                result = -errno;
+                LOGE("Error mapping file '%s', %s.", filename.string(), strerror(errno));
+            } else {
+                if (madvise(buffer, length, MADV_SEQUENTIAL)) {
+                    LOGW("Error calling madvise for mmapped file '%s', %s.", filename.string(),
+                            strerror(errno));
+                }
+
+                *outTokenizer = new Tokenizer(filename, static_cast<const char*>(buffer), length);
+                if (!*outTokenizer) {
+                    result = NO_MEMORY;
+                    LOGE("Error allocating tokenizer for file=%s.", filename.string());
+                    munmap(buffer, length);
+                }
+            }
+        }
+        close(fd);
+    }
+    return result;
+}
+
+String8 Tokenizer::getLocation() const {
+    String8 result;
+    result.appendFormat("%s:%d", mFilename.string(), mLineNumber);
+    return result;
+}
+
+String8 Tokenizer::peekRemainderOfLine() const {
+    const char* end = getEnd();
+    const char* eol = mCurrent;
+    while (eol != end) {
+        char ch = *eol;
+        if (ch == '\n') {
+            break;
+        }
+        eol += 1;
+    }
+    return String8(mCurrent, eol - mCurrent);
+}
+
+String8 Tokenizer::nextToken(const char* delimiters) {
+#if DEBUG_TOKENIZER
+    LOGD("nextToken");
+#endif
+    const char* end = getEnd();
+    const char* tokenStart = mCurrent;
+    while (mCurrent != end) {
+        char ch = *mCurrent;
+        if (ch == '\n' || isDelimiter(ch, delimiters)) {
+            break;
+        }
+        mCurrent += 1;
+    }
+    return String8(tokenStart, mCurrent - tokenStart);
+}
+
+void Tokenizer::nextLine() {
+#if DEBUG_TOKENIZER
+    LOGD("nextLine");
+#endif
+    const char* end = getEnd();
+    while (mCurrent != end) {
+        char ch = *(mCurrent++);
+        if (ch == '\n') {
+            mLineNumber += 1;
+            break;
+        }
+    }
+}
+
+void Tokenizer::skipDelimiters(const char* delimiters) {
+#if DEBUG_TOKENIZER
+    LOGD("skipDelimiters");
+#endif
+    const char* end = getEnd();
+    while (mCurrent != end) {
+        char ch = *mCurrent;
+        if (ch == '\n' || !isDelimiter(ch, delimiters)) {
+            break;
+        }
+        mCurrent += 1;
+    }
+}
+
+} // namespace android