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

6 files changed, 427 insertions, 43 deletions

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 @@ private:
         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 @@ private:
             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 KeyCharacterMap* load(int id);
-
-    enum {
-        NUMERIC = 1,
-        Q14 = 2,
-        QWERTY = 3 // or AZERTY or whatever
-    };
+    static status_t load(const String8& filename, KeyCharacterMap** outMap);
+    static status_t loadByDeviceId(int32_t deviceId, KeyCharacterMap** outMap);
+
+    /* Gets the keyboard type. */
+    int32_t getKeyboardType() const;
+
+    /* 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;
+
+    /* 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;
 
-#define META_MASK 3
+    /* 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;
+    };
+
+    struct Key {
+        Key();
+        ~Key();
+
+        /* 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();
-    static KeyCharacterMap* try_file(const char* filename);
-    Key* find_key(int keycode);
-    bool find_char(uint16_t c, uint32_t* key, uint32_t* mods);
 
-    unsigned int m_type;
-    unsigned int m_keyCount;
-    Key* m_keys;
+    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 @@ public:
 
             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