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
diff --git a/include/ui/EventHub.h b/include/ui/EventHub.h
index 1431964..f4dc536 100644
--- a/include/ui/EventHub.h
+++ b/include/ui/EventHub.h
@@ -19,6 +19,7 @@
 #define _RUNTIME_EVENT_HUB_H
 
 #include <android/input.h>
+#include <ui/Keyboard.h>
 #include <utils/String8.h>
 #include <utils/threads.h>
 #include <utils/Log.h>
@@ -246,10 +247,7 @@
         uint32_t        classes;
         uint8_t*        keyBitmask;
         KeyLayoutMap*   layoutMap;
-        String8         keyMapName;
-        bool            defaultKeyMap;
-        String8         keyLayoutFilename;
-        String8         keyCharacterMapFilename;
+        KeyMapInfo      keyMapInfo;
         int             fd;
         device_t*       next;
         
@@ -267,8 +265,6 @@
             const int32_t* keyCodes, uint8_t* outFlags) const;
 
     void configureKeyMap(device_t* device);
-    bool probeKeyMap(device_t* device, const String8& keyMapName, bool defaultKeyMap);
-    void selectKeyMap(device_t* device, const String8& keyMapName, bool defaultKeyMap);
     void setKeyboardProperties(device_t* device, bool firstKeyboard);
     void clearKeyboardProperties(device_t* device, bool firstKeyboard);
 
diff --git a/include/ui/KeyCharacterMap.h b/include/ui/KeyCharacterMap.h
index bad2cf8..a1ccb37 100644
--- a/include/ui/KeyCharacterMap.h
+++ b/include/ui/KeyCharacterMap.h
@@ -18,55 +18,166 @@
 #define _UI_KEY_CHARACTER_MAP_H
 
 #include <stdint.h>
-#include <utils/Vector.h>
 
-using namespace android;
+#include <ui/Input.h>
+#include <utils/Errors.h>
+#include <utils/KeyedVector.h>
+#include <utils/Tokenizer.h>
+#include <utils/String8.h>
+#include <utils/Unicode.h>
 
-class KeyCharacterMap
-{
+namespace android {
+
+/**
+ * Describes a mapping from Android key codes to characters.
+ * Also specifies other functions of the keyboard such as the keyboard type
+ * and key modifier semantics.
+ */
+class KeyCharacterMap {
 public:
+    enum KeyboardType {
+        KEYBOARD_TYPE_UNKNOWN = 0,
+        KEYBOARD_TYPE_NUMERIC = 1,
+        KEYBOARD_TYPE_PREDICTIVE = 2,
+        KEYBOARD_TYPE_ALPHA = 3,
+        KEYBOARD_TYPE_FULL = 4,
+        KEYBOARD_TYPE_SPECIAL_FUNCTION = 5,
+    };
+
     ~KeyCharacterMap();
 
-    // see the javadoc for android.text.method.KeyCharacterMap for what
-    // these do
-    unsigned short get(int keycode, int meta);
-    unsigned short getNumber(int keycode);
-    unsigned short getMatch(int keycode, const unsigned short* chars,
-                            int charsize, uint32_t modifiers);
-    unsigned short getDisplayLabel(int keycode);
-    bool getKeyData(int keycode, unsigned short *displayLabel,
-                    unsigned short *number, unsigned short* results);
-    inline unsigned int getKeyboardType() { return m_type; }
-    bool getEvents(uint16_t* chars, size_t len,
-                   Vector<int32_t>* keys, Vector<uint32_t>* modifiers);
+    static status_t load(const String8& filename, KeyCharacterMap** outMap);
+    static status_t loadByDeviceId(int32_t deviceId, KeyCharacterMap** outMap);
 
-    static KeyCharacterMap* load(int id);
+    /* Gets the keyboard type. */
+    int32_t getKeyboardType() const;
 
-    enum {
-        NUMERIC = 1,
-        Q14 = 2,
-        QWERTY = 3 // or AZERTY or whatever
-    };
+    /* Gets the primary character for this key as in the label physically printed on it.
+     * Returns 0 if none (eg. for non-printing keys). */
+    char16_t getDisplayLabel(int32_t keyCode) const;
 
-#define META_MASK 3
+    /* Gets the Unicode character for the number or symbol generated by the key
+     * when the keyboard is used as a dialing pad.
+     * Returns 0 if no number or symbol is generated.
+     */
+    char16_t getNumber(int32_t keyCode) const;
+
+    /* Gets the Unicode character generated by the key and meta key modifiers.
+     * Returns 0 if no character is generated.
+     */
+    char16_t getCharacter(int32_t keyCode, int32_t metaState) const;
+
+    /* Gets the first matching Unicode character that can be generated by the key,
+     * preferring the one with the specified meta key modifiers.
+     * Returns 0 if no matching character is generated.
+     */
+    char16_t getMatch(int32_t keyCode, const char16_t* chars,
+            size_t numChars, int32_t metaState) const;
+
+    /* Gets a sequence of key events that could plausibly generate the specified
+     * character sequence.  Returns false if some of the characters cannot be generated.
+     */
+    bool getEvents(int32_t deviceId, const char16_t* chars, size_t numChars,
+            Vector<KeyEvent>& outEvents) const;
 
 private:
-    struct Key
-    {
-        int32_t keycode;
-        uint16_t display_label;
-        uint16_t number;
-        uint16_t data[META_MASK + 1];
+    struct Behavior {
+        Behavior();
+
+        /* The next behavior in the list, or NULL if none. */
+        Behavior* next;
+
+        /* The meta key modifiers for this behavior. */
+        int32_t metaState;
+
+        /* The character to insert. */
+        char16_t character;
+
+        /* The fallback keycode if the key is not handled. */
+        int32_t fallbackKeyCode;
     };
 
-    KeyCharacterMap();
-    static KeyCharacterMap* try_file(const char* filename);
-    Key* find_key(int keycode);
-    bool find_char(uint16_t c, uint32_t* key, uint32_t* mods);
+    struct Key {
+        Key();
+        ~Key();
 
-    unsigned int m_type;
-    unsigned int m_keyCount;
-    Key* m_keys;
+        /* The single character label printed on the key, or 0 if none. */
+        char16_t label;
+
+        /* The number or symbol character generated by the key, or 0 if none. */
+        char16_t number;
+
+        /* The list of key behaviors sorted from most specific to least specific
+         * meta key binding. */
+        Behavior* firstBehavior;
+    };
+
+    class Parser {
+        enum State {
+            STATE_TOP = 0,
+            STATE_KEY = 1,
+        };
+
+        enum {
+            PROPERTY_LABEL = 1,
+            PROPERTY_NUMBER = 2,
+            PROPERTY_META = 3,
+        };
+
+        struct Property {
+            inline Property(int32_t property = 0, int32_t metaState = 0) :
+                    property(property), metaState(metaState) { }
+
+            int32_t property;
+            int32_t metaState;
+        };
+
+        KeyCharacterMap* mMap;
+        Tokenizer* mTokenizer;
+        State mState;
+        int32_t mKeyCode;
+
+    public:
+        Parser(KeyCharacterMap* map, Tokenizer* tokenizer);
+        ~Parser();
+        status_t parse();
+
+    private:
+        status_t parseType();
+        status_t parseKey();
+        status_t parseKeyProperty();
+        status_t parseModifier(const String8& token, int32_t* outMetaState);
+        status_t parseCharacterLiteral(char16_t* outCharacter);
+    };
+
+    KeyedVector<int32_t, Key*> mKeys;
+    int mType;
+
+    KeyCharacterMap();
+
+    bool findKey(char16_t ch, int32_t* outKeyCode, int32_t* outMetaState) const;
+
+    static void addKey(Vector<KeyEvent>& outEvents,
+            int32_t deviceId, int32_t keyCode, int32_t metaState, bool down, nsecs_t time);
+    static void addMetaKeys(Vector<KeyEvent>& outEvents,
+            int32_t deviceId, int32_t metaState, bool down, nsecs_t time,
+            int32_t* currentMetaState);
+    static bool addSingleEphemeralMetaKey(Vector<KeyEvent>& outEvents,
+            int32_t deviceId, int32_t metaState, bool down, nsecs_t time,
+            int32_t keyCode, int32_t keyMetaState,
+            int32_t* currentMetaState);
+    static void 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);
+    static void addLockedMetaKey(Vector<KeyEvent>& outEvents,
+            int32_t deviceId, int32_t metaState, nsecs_t time,
+            int32_t keyCode, int32_t keyMetaState,
+            int32_t* currentMetaState);
 };
 
+} // namespace android
+
 #endif // _UI_KEY_CHARACTER_MAP_H
diff --git a/include/ui/KeyLayoutMap.h b/include/ui/KeyLayoutMap.h
new file mode 100644
index 0000000..f0a6d00
--- /dev/null
+++ b/include/ui/KeyLayoutMap.h
@@ -0,0 +1,65 @@
+/*
+ * 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.
+ */
+
+#ifndef _UI_KEY_LAYOUT_MAP_H
+#define _UI_KEY_LAYOUT_MAP_H
+
+#include <stdint.h>
+#include <utils/Errors.h>
+#include <utils/KeyedVector.h>
+#include <utils/Tokenizer.h>
+
+namespace android {
+
+/**
+ * Describes a mapping from keyboard scan codes to Android key codes.
+ */
+class KeyLayoutMap {
+public:
+    ~KeyLayoutMap();
+
+    static status_t load(const String8& filename, KeyLayoutMap** outMap);
+
+    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;
+    };
+
+    KeyedVector<int32_t,Key> mKeys;
+
+    KeyLayoutMap();
+
+    class Parser {
+        KeyLayoutMap* mMap;
+        Tokenizer* mTokenizer;
+
+    public:
+        Parser(KeyLayoutMap* map, Tokenizer* tokenizer);
+        ~Parser();
+        status_t parse();
+
+    private:
+        status_t parseKey();
+    };
+};
+
+} // namespace android
+
+#endif // _UI_KEY_LAYOUT_MAP_H
diff --git a/include/ui/Keyboard.h b/include/ui/Keyboard.h
new file mode 100644
index 0000000..3b477c7
--- /dev/null
+++ b/include/ui/Keyboard.h
@@ -0,0 +1,87 @@
+/*
+ * 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.
+ */
+
+#ifndef _UI_KEYBOARD_H
+#define _UI_KEYBOARD_H
+
+#include <ui/Input.h>
+#include <utils/Errors.h>
+#include <utils/String8.h>
+
+namespace android {
+
+enum {
+    /* Device id of the built in keyboard. */
+    DEVICE_ID_BUILT_IN_KEYBOARD = 0,
+
+    /* Device id of a generic virtual keyboard with a full layout that can be used
+     * to synthesize key events. */
+    DEVICE_ID_VIRTUAL_KEYBOARD = -1,
+};
+
+struct KeyMapInfo {
+    String8 keyMapName;
+    String8 keyLayoutFile;
+    String8 keyCharacterMapFile;
+    bool isDefaultKeyMap;
+
+    KeyMapInfo() : isDefaultKeyMap(false) {
+    }
+};
+
+/**
+ * Resolves the key map to use for a particular keyboard device.
+ */
+extern status_t resolveKeyMap(const String8& deviceName, KeyMapInfo& outKeyMapInfo);
+
+/**
+ * Sets keyboard system properties.
+ */
+extern void setKeyboardProperties(int32_t deviceId, const String8& deviceName,
+        const KeyMapInfo& keyMapInfo);
+
+/**
+ * Clears keyboard system properties.
+ */
+extern void clearKeyboardProperties(int32_t deviceId);
+
+/**
+ * Gets the key character map filename for a device using inspecting system properties
+ * and then falling back on a default key character map if necessary.
+ * Returns a NAME_NOT_FOUND if none found.
+ */
+extern status_t getKeyCharacterMapFile(int32_t deviceId, String8& outKeyCharacterMapFile);
+
+/**
+ * Gets a key code by its short form label, eg. "HOME".
+ * Returns 0 if unknown.
+ */
+extern int32_t getKeyCodeByLabel(const char* label);
+
+/**
+ * Gets a key flag by its short form label, eg. "WAKE".
+ * Returns 0 if unknown.
+ */
+extern uint32_t getKeyFlagByLabel(const char* label);
+
+/**
+ * Updates a meta state field when a key is pressed or released.
+ */
+extern int32_t updateMetaState(int32_t keyCode, bool down, int32_t oldMetaState);
+
+} // namespace android
+
+#endif // _UI_KEYBOARD_H
diff --git a/include/utils/String8.h b/include/utils/String8.h
index b36f128..6abfb06 100644
--- a/include/utils/String8.h
+++ b/include/utils/String8.h
@@ -22,6 +22,7 @@
 #include <utils/Unicode.h>
 
 #include <string.h> // for strcmp
+#include <stdarg.h>
 
 // ---------------------------------------------------------------------------
 
@@ -70,6 +71,7 @@
 
             status_t            appendFormat(const char* fmt, ...)
                     __attribute__((format (printf, 2, 3)));
+            status_t            appendFormatV(const char* fmt, va_list args);
 
             // Note that this function takes O(N) time to calculate the value.
             // No cache value is stored.
diff --git a/include/utils/Tokenizer.h b/include/utils/Tokenizer.h
new file mode 100644
index 0000000..bfe8923
--- /dev/null
+++ b/include/utils/Tokenizer.h
@@ -0,0 +1,123 @@
+/*
+ * 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.
+ */
+
+#ifndef _UTILS_TOKENIZER_H
+#define _UTILS_TOKENIZER_H
+
+#include <assert.h>
+#include <utils/Errors.h>
+#include <utils/String8.h>
+
+namespace android {
+
+/**
+ * A simple tokenizer for loading and parsing ASCII text files line by line.
+ */
+class Tokenizer {
+    Tokenizer(const String8& filename, const char* buffer, size_t length);
+
+public:
+    ~Tokenizer();
+
+    /**
+     * Opens a file and maps it into memory.
+     *
+     * Returns NO_ERROR and a tokenizer for the file, if successful.
+     * Otherwise returns an error and sets outTokenizer to NULL.
+     */
+    static status_t open(const String8& filename, Tokenizer** outTokenizer);
+
+    /**
+     * Returns true if at the end of the file.
+     */
+    inline bool isEof() const { return mCurrent == getEnd(); }
+
+    /**
+     * Returns true if at the end of the line or end of the file.
+     */
+    inline bool isEol() const { return isEof() || *mCurrent == '\n'; }
+
+    /**
+     * Gets the name of the file.
+     */
+    inline String8 getFilename() const { return mFilename; }
+
+    /**
+     * Gets a 1-based line number index for the current position.
+     */
+    inline int32_t getLineNumber() const { return mLineNumber; }
+
+    /**
+     * Formats a location string consisting of the filename and current line number.
+     * Returns a string like "MyFile.txt:33".
+     */
+    String8 getLocation() const;
+
+    /**
+     * Gets the character at the current position.
+     * Returns null at end of file.
+     */
+    inline char peekChar() const { return isEof() ? '\0' : *mCurrent; }
+
+    /**
+     * Gets the remainder of the current line as a string, excluding the newline character.
+     */
+    String8 peekRemainderOfLine() const;
+
+    /**
+     * Gets the character at the current position and advances past it.
+     * Returns null at end of file.
+     */
+    inline char nextChar() { return isEof() ? '\0' : *(mCurrent++); }
+
+    /**
+     * Gets the next token on this line stopping at the specified delimiters
+     * or the end of the line whichever comes first and advances past it.
+     * Also stops at embedded nulls.
+     * Returns the token or an empty string if the current character is a delimiter
+     * or is at the end of the line.
+     */
+    String8 nextToken(const char* delimiters);
+
+    /**
+     * Advances to the next line.
+     * Does nothing if already at the end of the file.
+     */
+    void nextLine();
+
+    /**
+     * Skips over the specified delimiters in the line.
+     * Also skips embedded nulls.
+     */
+    void skipDelimiters(const char* delimiters);
+
+private:
+    Tokenizer(const Tokenizer& other); // not copyable
+
+    String8 mFilename;
+    const char* mBuffer;
+    size_t mLength;
+
+    const char* mCurrent;
+    int32_t mLineNumber;
+
+    inline const char* getEnd() const { return mBuffer + mLength; }
+
+};
+
+} // namespace android
+
+#endif // _UTILS_TOKENIZER_H
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 @@
 	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 @@
 
 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::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 @@
     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 @@
                 }
                 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 @@
         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 @@
         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 @@
 
         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 @@
 }
 
 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 @@
     }
     
     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 @@
                 }
                 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 @@
     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 @@
             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 @@
             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 @@
+/*
+ * 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 "KeyCharacterMap"
 
-#include <ui/KeyCharacterMap.h>
-#include <cutils/properties.h>
-
-#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>
 
-struct Header
-{
-    char magic[8];
-    unsigned int endian;
-    unsigned int version;
-    unsigned int keycount;
-    unsigned char kbdtype;
-    char padding[11];
+// 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 {
+
+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()
-{
-}
-
-KeyCharacterMap::~KeyCharacterMap()
-{
-    free(m_keys);
-}
-
-unsigned short
-KeyCharacterMap::get(int keycode, int meta)
-{
-    Key* k = find_key(keycode);
-    if (k != NULL) {
-        return k->data[meta & META_MASK];
+#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 0;
+    return result;
+}
+#endif
+
+
+// --- KeyCharacterMap ---
+
+KeyCharacterMap::KeyCharacterMap() :
+    mType(KEYBOARD_TYPE_UNKNOWN) {
 }
 
-unsigned short
-KeyCharacterMap::getNumber(int keycode)
-{
-    Key* k = find_key(keycode);
-    if (k != NULL) {
-        return k->number;
+KeyCharacterMap::~KeyCharacterMap() {
+    for (size_t i = 0; i < mKeys.size(); i++) {
+        Key* key = mKeys.editValueAt(i);
+        delete key;
     }
-    return 0;
 }
 
-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::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 status;
+}
+
+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);
     }
-    return 0;
+#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");
+    }
+#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;
-        }
-    }
-    return true;
+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);
 }
 
-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;
-        }
-    }
-    return NULL;
-}
+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);
 
-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;
+        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);
 
-    // 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;
-        }
-        LOGW("Error loading keycharmap file '%s'. %s='%s'", path, propName, dev);
+        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 {
-        LOGW("No keyboard for id %d", id);
-    }
+        addSingleEphemeralMetaKey(outEvents, deviceId, metaState, false, time,
+                AKEYCODE_FUNCTION, AMETA_FUNCTION_ON, currentMetaState);
+        addSingleEphemeralMetaKey(outEvents, deviceId, metaState, false, time,
+                AKEYCODE_SYM, AMETA_SYM_ON, currentMetaState);
 
-    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;
-    }
+        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);
 
-    LOGE("Can't find any keycharmaps (also tried %s)", path);
-    return NULL;
+        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);
+    }
 }
 
-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;
+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;
     }
-
-    filesize = lseek(fd, 0, SEEK_END);
-    lseek(fd, 0, SEEK_SET);
-
-    // validate the header
-    if (filesize <= (off_t)sizeof(header)) {
-        LOGW("Bad keycharmap - filesize=%d\n", (int)filesize);
-        goto cleanup1;
-    }
-
-    err = read(fd, &header, sizeof(header));
-    if (err == -1) {
-        LOGW("Error reading keycharmap file");
-        goto cleanup1;
-    }
-
-    if (0 != memcmp(header.magic, "keychar", 8)) {
-        LOGW("Bad keycharmap magic token");
-        goto cleanup1;
-    }
-    if (header.endian != 0x12345678) {
-        LOGW("Bad keycharmap endians");
-        goto cleanup1;
-    }
-    if ((header.version & 0xff) != 2) {
-        LOGW("Only support keycharmap version 2 (got 0x%08x)", header.version);
-        goto cleanup1;
-    }
-    if (filesize < (off_t)(sizeof(Header)+(sizeof(Key)*header.keycount))) {
-        LOGW("Bad keycharmap file size\n");
-        goto cleanup1;
-    }
-
-    // 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;
-    }
-
-    // return the object
-    rv = new KeyCharacterMap;
-    rv->m_keyCount = header.keycount;
-    rv->m_keys = keys;
-    rv->m_type = header.kbdtype;
-
-cleanup1:
-    close(fd);
-
-    return rv;
+    return false;
 }
+
+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;
+            }
+        }
+
+        mTokenizer->nextLine();
+    }
+
+    if (mState != STATE_TOP) {
+        LOGE("%s: Unterminated key description at end of file.",
+                mTokenizer->getLocation().string());
+        return BAD_VALUE;
+    }
+
+    if (mMap->mType == KEYBOARD_TYPE_UNKNOWN) {
+        LOGE("%s: Missing required keyboard 'type' declaration.",
+                mTokenizer->getLocation().string());
+        return BAD_VALUE;
+    }
+
+    return NO_ERROR;
+}
+
+status_t KeyCharacterMap::Parser::parseType() {
+    if (mMap->mType != KEYBOARD_TYPE_UNKNOWN) {
+        LOGE("%s: Duplicate keyboard 'type' declaration.",
+                mTokenizer->getLocation().string());
+        return BAD_VALUE;
+    }
+
+    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;
+}
+
+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;
+    }
+
+    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 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;
+    }
+
+    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;
+    }
+
+    // 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;
+            }
+        }
+    }
+    *outMetaState = combinedMeta;
+    return NO_ERROR;
+}
+
+status_t KeyCharacterMap::Parser::parseCharacterLiteral(char16_t* outCharacter) {
+    char ch = mTokenizer->nextChar();
+    if (ch != '\'') {
+        goto Error;
+    }
+
+    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;
+    }
+
+    ch = mTokenizer->nextChar();
+    if (ch != '\'') {
+        goto Error;
+    }
+
+    // Ensure that we consumed the entire token.
+    if (mTokenizer->nextToken(WHITESPACE).isEmpty()) {
+        return NO_ERROR;
+    }
+
+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()
-{
+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)++;
+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;
+            }
         }
-        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;
-        }
+        delete tokenizer;
     }
+    return status;
 }
 
-static int32_t
-token_to_value(const char *literal, const KeycodeLabel *list)
-{
-    while (list->literal) {
-        if (0 == strcmp(literal, list->literal)) {
-            return list->value;
-        }
-        list++;
-    }
-    return list->value;
-}
-
-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;
-    }
-
-    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;
-    }
-
-    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';
-
-    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;
-        }
-    }
-    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;
-}
-
-status_t
-KeyLayoutMap::map(int32_t scancode, int32_t *keycode, uint32_t *flags) const
-{
-    if (m_status != NO_ERROR) {
-        return m_status;
-    }
-
-    ssize_t index = m_keys.indexOfKey(scancode);
+status_t KeyLayoutMap::map(int32_t scanCode, int32_t* keyCode, uint32_t* flags) const {
+    ssize_t index = mKeys.indexOfKey(scanCode);
     if (index < 0) {
-        //LOGW("couldn't map scancode=%d\n", scancode);
+#if DEBUG_MAPPING
+        LOGD("map: scanCode=%d ~ Failed.", scanCode);
+#endif
+        *keyCode = AKEYCODE_UNKNOWN;
+        *flags = 0;
         return NAME_NOT_FOUND;
     }
 
-    const Key& k = m_keys.valueAt(index);
-
-    *keycode = k.keycode;
+    const Key& k = mKeys.valueAt(index);
+    *keyCode = k.keyCode;
     *flags = k.flags;
 
-    //LOGD("mapped scancode=%d to keycode=%d flags=0x%08x\n", scancode,
-    //        keycode, flags);
-
+#if DEBUG_MAPPING
+    LOGD("map: scanCode=%d ~ Result keyCode=%d, flags=0x%08x.", scanCode, *keyCode, *flags);
+#endif
     return NO_ERROR;
 }
 
-status_t
-KeyLayoutMap::findScancodes(int32_t keycode, Vector<int32_t>* outScancodes) const
-{
-    if (m_status != NO_ERROR) {
-        return m_status;
-    }
-    
-    const size_t N = m_keys.size();
+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 (m_keys.valueAt(i).keycode == keycode) {
-            outScancodes->add(m_keys.keyAt(i));
+        if (mKeys.valueAt(i).keyCode == keyCode) {
+            outScanCodes->add(mKeys.keyAt(i));
         }
     }
-    
+    return NO_ERROR;
+}
+
+// --- KeyLayoutMap::Parser ---
+
+KeyLayoutMap::Parser::Parser(KeyLayoutMap* map, Tokenizer* tokenizer) :
+        mMap(map), mTokenizer(tokenizer) {
+}
+
+KeyLayoutMap::Parser::~Parser() {
+}
+
+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::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;
+    }
+    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 @@
 	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::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