1/*
2 * Copyright (C) 2008 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17#define LOG_TAG "KeyCharacterMap"
18
19#include <stdlib.h>
20#include <string.h>
21
22#if HAVE_ANDROID_OS
23#include <binder/Parcel.h>
24#endif
25
26#include <android/keycodes.h>
27#include <input/Keyboard.h>
28#include <input/KeyCharacterMap.h>
29
30#include <utils/Log.h>
31#include <utils/Errors.h>
32#include <utils/Tokenizer.h>
33#include <utils/Timers.h>
34
35// Enables debug output for the parser.
36#define DEBUG_PARSER 0
37
38// Enables debug output for parser performance.
39#define DEBUG_PARSER_PERFORMANCE 0
40
41// Enables debug output for mapping.
42#define DEBUG_MAPPING 0
43
44
45namespace android {
46
47static const char* WHITESPACE = " \t\r";
48static const char* WHITESPACE_OR_PROPERTY_DELIMITER = " \t\r,:";
49
50struct Modifier {
51    const char* label;
52    int32_t metaState;
53};
54static const Modifier modifiers[] = {
55        { "shift", AMETA_SHIFT_ON },
56        { "lshift", AMETA_SHIFT_LEFT_ON },
57        { "rshift", AMETA_SHIFT_RIGHT_ON },
58        { "alt", AMETA_ALT_ON },
59        { "lalt", AMETA_ALT_LEFT_ON },
60        { "ralt", AMETA_ALT_RIGHT_ON },
61        { "ctrl", AMETA_CTRL_ON },
62        { "lctrl", AMETA_CTRL_LEFT_ON },
63        { "rctrl", AMETA_CTRL_RIGHT_ON },
64        { "meta", AMETA_META_ON },
65        { "lmeta", AMETA_META_LEFT_ON },
66        { "rmeta", AMETA_META_RIGHT_ON },
67        { "sym", AMETA_SYM_ON },
68        { "fn", AMETA_FUNCTION_ON },
69        { "capslock", AMETA_CAPS_LOCK_ON },
70        { "numlock", AMETA_NUM_LOCK_ON },
71        { "scrolllock", AMETA_SCROLL_LOCK_ON },
72};
73
74#if DEBUG_MAPPING
75static String8 toString(const char16_t* chars, size_t numChars) {
76    String8 result;
77    for (size_t i = 0; i < numChars; i++) {
78        result.appendFormat(i == 0 ? "%d" : ", %d", chars[i]);
79    }
80    return result;
81}
82#endif
83
84
85// --- KeyCharacterMap ---
86
87sp<KeyCharacterMap> KeyCharacterMap::sEmpty = new KeyCharacterMap();
88
89KeyCharacterMap::KeyCharacterMap() :
90    mType(KEYBOARD_TYPE_UNKNOWN) {
91}
92
93KeyCharacterMap::KeyCharacterMap(const KeyCharacterMap& other) :
94    RefBase(), mType(other.mType), mKeysByScanCode(other.mKeysByScanCode),
95    mKeysByUsageCode(other.mKeysByUsageCode) {
96    for (size_t i = 0; i < other.mKeys.size(); i++) {
97        mKeys.add(other.mKeys.keyAt(i), new Key(*other.mKeys.valueAt(i)));
98    }
99}
100
101KeyCharacterMap::~KeyCharacterMap() {
102    for (size_t i = 0; i < mKeys.size(); i++) {
103        Key* key = mKeys.editValueAt(i);
104        delete key;
105    }
106}
107
108status_t KeyCharacterMap::load(const String8& filename,
109        Format format, sp<KeyCharacterMap>* outMap) {
110    outMap->clear();
111
112    Tokenizer* tokenizer;
113    status_t status = Tokenizer::open(filename, &tokenizer);
114    if (status) {
115        ALOGE("Error %d opening key character map file %s.", status, filename.string());
116    } else {
117        status = load(tokenizer, format, outMap);
118        delete tokenizer;
119    }
120    return status;
121}
122
123status_t KeyCharacterMap::loadContents(const String8& filename, const char* contents,
124        Format format, sp<KeyCharacterMap>* outMap) {
125    outMap->clear();
126
127    Tokenizer* tokenizer;
128    status_t status = Tokenizer::fromContents(filename, contents, &tokenizer);
129    if (status) {
130        ALOGE("Error %d opening key character map.", status);
131    } else {
132        status = load(tokenizer, format, outMap);
133        delete tokenizer;
134    }
135    return status;
136}
137
138status_t KeyCharacterMap::load(Tokenizer* tokenizer,
139        Format format, sp<KeyCharacterMap>* outMap) {
140    status_t status = OK;
141    sp<KeyCharacterMap> map = new KeyCharacterMap();
142    if (!map.get()) {
143        ALOGE("Error allocating key character map.");
144        status = NO_MEMORY;
145    } else {
146#if DEBUG_PARSER_PERFORMANCE
147        nsecs_t startTime = systemTime(SYSTEM_TIME_MONOTONIC);
148#endif
149        Parser parser(map.get(), tokenizer, format);
150        status = parser.parse();
151#if DEBUG_PARSER_PERFORMANCE
152        nsecs_t elapsedTime = systemTime(SYSTEM_TIME_MONOTONIC) - startTime;
153        ALOGD("Parsed key character map file '%s' %d lines in %0.3fms.",
154                tokenizer->getFilename().string(), tokenizer->getLineNumber(),
155                elapsedTime / 1000000.0);
156#endif
157        if (!status) {
158            *outMap = map;
159        }
160    }
161    return status;
162}
163
164sp<KeyCharacterMap> KeyCharacterMap::combine(const sp<KeyCharacterMap>& base,
165        const sp<KeyCharacterMap>& overlay) {
166    if (overlay == NULL) {
167        return base;
168    }
169    if (base == NULL) {
170        return overlay;
171    }
172
173    sp<KeyCharacterMap> map = new KeyCharacterMap(*base.get());
174    for (size_t i = 0; i < overlay->mKeys.size(); i++) {
175        int32_t keyCode = overlay->mKeys.keyAt(i);
176        Key* key = overlay->mKeys.valueAt(i);
177        ssize_t oldIndex = map->mKeys.indexOfKey(keyCode);
178        if (oldIndex >= 0) {
179            delete map->mKeys.valueAt(oldIndex);
180            map->mKeys.editValueAt(oldIndex) = new Key(*key);
181        } else {
182            map->mKeys.add(keyCode, new Key(*key));
183        }
184    }
185
186    for (size_t i = 0; i < overlay->mKeysByScanCode.size(); i++) {
187        map->mKeysByScanCode.replaceValueFor(overlay->mKeysByScanCode.keyAt(i),
188                overlay->mKeysByScanCode.valueAt(i));
189    }
190
191    for (size_t i = 0; i < overlay->mKeysByUsageCode.size(); i++) {
192        map->mKeysByUsageCode.replaceValueFor(overlay->mKeysByUsageCode.keyAt(i),
193                overlay->mKeysByUsageCode.valueAt(i));
194    }
195    return map;
196}
197
198sp<KeyCharacterMap> KeyCharacterMap::empty() {
199    return sEmpty;
200}
201
202int32_t KeyCharacterMap::getKeyboardType() const {
203    return mType;
204}
205
206char16_t KeyCharacterMap::getDisplayLabel(int32_t keyCode) const {
207    char16_t result = 0;
208    const Key* key;
209    if (getKey(keyCode, &key)) {
210        result = key->label;
211    }
212#if DEBUG_MAPPING
213    ALOGD("getDisplayLabel: keyCode=%d ~ Result %d.", keyCode, result);
214#endif
215    return result;
216}
217
218char16_t KeyCharacterMap::getNumber(int32_t keyCode) const {
219    char16_t result = 0;
220    const Key* key;
221    if (getKey(keyCode, &key)) {
222        result = key->number;
223    }
224#if DEBUG_MAPPING
225    ALOGD("getNumber: keyCode=%d ~ Result %d.", keyCode, result);
226#endif
227    return result;
228}
229
230char16_t KeyCharacterMap::getCharacter(int32_t keyCode, int32_t metaState) const {
231    char16_t result = 0;
232    const Key* key;
233    const Behavior* behavior;
234    if (getKeyBehavior(keyCode, metaState, &key, &behavior)) {
235        result = behavior->character;
236    }
237#if DEBUG_MAPPING
238    ALOGD("getCharacter: keyCode=%d, metaState=0x%08x ~ Result %d.", keyCode, metaState, result);
239#endif
240    return result;
241}
242
243bool KeyCharacterMap::getFallbackAction(int32_t keyCode, int32_t metaState,
244        FallbackAction* outFallbackAction) const {
245    outFallbackAction->keyCode = 0;
246    outFallbackAction->metaState = 0;
247
248    bool result = false;
249    const Key* key;
250    const Behavior* behavior;
251    if (getKeyBehavior(keyCode, metaState, &key, &behavior)) {
252        if (behavior->fallbackKeyCode) {
253            outFallbackAction->keyCode = behavior->fallbackKeyCode;
254            outFallbackAction->metaState = metaState & ~behavior->metaState;
255            result = true;
256        }
257    }
258#if DEBUG_MAPPING
259    ALOGD("getFallbackKeyCode: keyCode=%d, metaState=0x%08x ~ Result %s, "
260            "fallback keyCode=%d, fallback metaState=0x%08x.",
261            keyCode, metaState, result ? "true" : "false",
262            outFallbackAction->keyCode, outFallbackAction->metaState);
263#endif
264    return result;
265}
266
267char16_t KeyCharacterMap::getMatch(int32_t keyCode, const char16_t* chars, size_t numChars,
268        int32_t metaState) const {
269    char16_t result = 0;
270    const Key* key;
271    if (getKey(keyCode, &key)) {
272        // Try to find the most general behavior that maps to this character.
273        // For example, the base key behavior will usually be last in the list.
274        // However, if we find a perfect meta state match for one behavior then use that one.
275        for (const Behavior* behavior = key->firstBehavior; behavior; behavior = behavior->next) {
276            if (behavior->character) {
277                for (size_t i = 0; i < numChars; i++) {
278                    if (behavior->character == chars[i]) {
279                        result = behavior->character;
280                        if ((behavior->metaState & metaState) == behavior->metaState) {
281                            goto ExactMatch;
282                        }
283                        break;
284                    }
285                }
286            }
287        }
288    ExactMatch: ;
289    }
290#if DEBUG_MAPPING
291    ALOGD("getMatch: keyCode=%d, chars=[%s], metaState=0x%08x ~ Result %d.",
292            keyCode, toString(chars, numChars).string(), metaState, result);
293#endif
294    return result;
295}
296
297bool KeyCharacterMap::getEvents(int32_t deviceId, const char16_t* chars, size_t numChars,
298        Vector<KeyEvent>& outEvents) const {
299    nsecs_t now = systemTime(SYSTEM_TIME_MONOTONIC);
300
301    for (size_t i = 0; i < numChars; i++) {
302        int32_t keyCode, metaState;
303        char16_t ch = chars[i];
304        if (!findKey(ch, &keyCode, &metaState)) {
305#if DEBUG_MAPPING
306            ALOGD("getEvents: deviceId=%d, chars=[%s] ~ Failed to find mapping for character %d.",
307                    deviceId, toString(chars, numChars).string(), ch);
308#endif
309            return false;
310        }
311
312        int32_t currentMetaState = 0;
313        addMetaKeys(outEvents, deviceId, metaState, true, now, &currentMetaState);
314        addKey(outEvents, deviceId, keyCode, currentMetaState, true, now);
315        addKey(outEvents, deviceId, keyCode, currentMetaState, false, now);
316        addMetaKeys(outEvents, deviceId, metaState, false, now, &currentMetaState);
317    }
318#if DEBUG_MAPPING
319    ALOGD("getEvents: deviceId=%d, chars=[%s] ~ Generated %d events.",
320            deviceId, toString(chars, numChars).string(), int32_t(outEvents.size()));
321    for (size_t i = 0; i < outEvents.size(); i++) {
322        ALOGD("  Key: keyCode=%d, metaState=0x%08x, %s.",
323                outEvents[i].getKeyCode(), outEvents[i].getMetaState(),
324                outEvents[i].getAction() == AKEY_EVENT_ACTION_DOWN ? "down" : "up");
325    }
326#endif
327    return true;
328}
329
330status_t KeyCharacterMap::mapKey(int32_t scanCode, int32_t usageCode, int32_t* outKeyCode) const {
331    if (usageCode) {
332        ssize_t index = mKeysByUsageCode.indexOfKey(usageCode);
333        if (index >= 0) {
334#if DEBUG_MAPPING
335    ALOGD("mapKey: scanCode=%d, usageCode=0x%08x ~ Result keyCode=%d.",
336            scanCode, usageCode, *outKeyCode);
337#endif
338            *outKeyCode = mKeysByUsageCode.valueAt(index);
339            return OK;
340        }
341    }
342    if (scanCode) {
343        ssize_t index = mKeysByScanCode.indexOfKey(scanCode);
344        if (index >= 0) {
345#if DEBUG_MAPPING
346    ALOGD("mapKey: scanCode=%d, usageCode=0x%08x ~ Result keyCode=%d.",
347            scanCode, usageCode, *outKeyCode);
348#endif
349            *outKeyCode = mKeysByScanCode.valueAt(index);
350            return OK;
351        }
352    }
353
354#if DEBUG_MAPPING
355        ALOGD("mapKey: scanCode=%d, usageCode=0x%08x ~ Failed.", scanCode, usageCode);
356#endif
357    *outKeyCode = AKEYCODE_UNKNOWN;
358    return NAME_NOT_FOUND;
359}
360
361bool KeyCharacterMap::getKey(int32_t keyCode, const Key** outKey) const {
362    ssize_t index = mKeys.indexOfKey(keyCode);
363    if (index >= 0) {
364        *outKey = mKeys.valueAt(index);
365        return true;
366    }
367    return false;
368}
369
370bool KeyCharacterMap::getKeyBehavior(int32_t keyCode, int32_t metaState,
371        const Key** outKey, const Behavior** outBehavior) const {
372    const Key* key;
373    if (getKey(keyCode, &key)) {
374        const Behavior* behavior = key->firstBehavior;
375        while (behavior) {
376            if (matchesMetaState(metaState, behavior->metaState)) {
377                *outKey = key;
378                *outBehavior = behavior;
379                return true;
380            }
381            behavior = behavior->next;
382        }
383    }
384    return false;
385}
386
387bool KeyCharacterMap::matchesMetaState(int32_t eventMetaState, int32_t behaviorMetaState) {
388    // Behavior must have at least the set of meta states specified.
389    // And if the key event has CTRL, ALT or META then the behavior must exactly
390    // match those, taking into account that a behavior can specify that it handles
391    // one, both or either of a left/right modifier pair.
392    if ((eventMetaState & behaviorMetaState) == behaviorMetaState) {
393        const int32_t EXACT_META_STATES =
394                AMETA_CTRL_ON | AMETA_CTRL_LEFT_ON | AMETA_CTRL_RIGHT_ON
395                | AMETA_ALT_ON | AMETA_ALT_LEFT_ON | AMETA_ALT_RIGHT_ON
396                | AMETA_META_ON | AMETA_META_LEFT_ON | AMETA_META_RIGHT_ON;
397        int32_t unmatchedMetaState = eventMetaState & ~behaviorMetaState & EXACT_META_STATES;
398        if (behaviorMetaState & AMETA_CTRL_ON) {
399            unmatchedMetaState &= ~(AMETA_CTRL_LEFT_ON | AMETA_CTRL_RIGHT_ON);
400        } else if (behaviorMetaState & (AMETA_CTRL_LEFT_ON | AMETA_CTRL_RIGHT_ON)) {
401            unmatchedMetaState &= ~AMETA_CTRL_ON;
402        }
403        if (behaviorMetaState & AMETA_ALT_ON) {
404            unmatchedMetaState &= ~(AMETA_ALT_LEFT_ON | AMETA_ALT_RIGHT_ON);
405        } else if (behaviorMetaState & (AMETA_ALT_LEFT_ON | AMETA_ALT_RIGHT_ON)) {
406            unmatchedMetaState &= ~AMETA_ALT_ON;
407        }
408        if (behaviorMetaState & AMETA_META_ON) {
409            unmatchedMetaState &= ~(AMETA_META_LEFT_ON | AMETA_META_RIGHT_ON);
410        } else if (behaviorMetaState & (AMETA_META_LEFT_ON | AMETA_META_RIGHT_ON)) {
411            unmatchedMetaState &= ~AMETA_META_ON;
412        }
413        return !unmatchedMetaState;
414    }
415    return false;
416}
417
418bool KeyCharacterMap::findKey(char16_t ch, int32_t* outKeyCode, int32_t* outMetaState) const {
419    if (!ch) {
420        return false;
421    }
422
423    for (size_t i = 0; i < mKeys.size(); i++) {
424        const Key* key = mKeys.valueAt(i);
425
426        // Try to find the most general behavior that maps to this character.
427        // For example, the base key behavior will usually be last in the list.
428        const Behavior* found = NULL;
429        for (const Behavior* behavior = key->firstBehavior; behavior; behavior = behavior->next) {
430            if (behavior->character == ch) {
431                found = behavior;
432            }
433        }
434        if (found) {
435            *outKeyCode = mKeys.keyAt(i);
436            *outMetaState = found->metaState;
437            return true;
438        }
439    }
440    return false;
441}
442
443void KeyCharacterMap::addKey(Vector<KeyEvent>& outEvents,
444        int32_t deviceId, int32_t keyCode, int32_t metaState, bool down, nsecs_t time) {
445    outEvents.push();
446    KeyEvent& event = outEvents.editTop();
447    event.initialize(deviceId, AINPUT_SOURCE_KEYBOARD,
448            down ? AKEY_EVENT_ACTION_DOWN : AKEY_EVENT_ACTION_UP,
449            0, keyCode, 0, metaState, 0, time, time);
450}
451
452void KeyCharacterMap::addMetaKeys(Vector<KeyEvent>& outEvents,
453        int32_t deviceId, int32_t metaState, bool down, nsecs_t time,
454        int32_t* currentMetaState) {
455    // Add and remove meta keys symmetrically.
456    if (down) {
457        addLockedMetaKey(outEvents, deviceId, metaState, time,
458                AKEYCODE_CAPS_LOCK, AMETA_CAPS_LOCK_ON, currentMetaState);
459        addLockedMetaKey(outEvents, deviceId, metaState, time,
460                AKEYCODE_NUM_LOCK, AMETA_NUM_LOCK_ON, currentMetaState);
461        addLockedMetaKey(outEvents, deviceId, metaState, time,
462                AKEYCODE_SCROLL_LOCK, AMETA_SCROLL_LOCK_ON, currentMetaState);
463
464        addDoubleEphemeralMetaKey(outEvents, deviceId, metaState, true, time,
465                AKEYCODE_SHIFT_LEFT, AMETA_SHIFT_LEFT_ON,
466                AKEYCODE_SHIFT_RIGHT, AMETA_SHIFT_RIGHT_ON,
467                AMETA_SHIFT_ON, currentMetaState);
468        addDoubleEphemeralMetaKey(outEvents, deviceId, metaState, true, time,
469                AKEYCODE_ALT_LEFT, AMETA_ALT_LEFT_ON,
470                AKEYCODE_ALT_RIGHT, AMETA_ALT_RIGHT_ON,
471                AMETA_ALT_ON, currentMetaState);
472        addDoubleEphemeralMetaKey(outEvents, deviceId, metaState, true, time,
473                AKEYCODE_CTRL_LEFT, AMETA_CTRL_LEFT_ON,
474                AKEYCODE_CTRL_RIGHT, AMETA_CTRL_RIGHT_ON,
475                AMETA_CTRL_ON, currentMetaState);
476        addDoubleEphemeralMetaKey(outEvents, deviceId, metaState, true, time,
477                AKEYCODE_META_LEFT, AMETA_META_LEFT_ON,
478                AKEYCODE_META_RIGHT, AMETA_META_RIGHT_ON,
479                AMETA_META_ON, currentMetaState);
480
481        addSingleEphemeralMetaKey(outEvents, deviceId, metaState, true, time,
482                AKEYCODE_SYM, AMETA_SYM_ON, currentMetaState);
483        addSingleEphemeralMetaKey(outEvents, deviceId, metaState, true, time,
484                AKEYCODE_FUNCTION, AMETA_FUNCTION_ON, currentMetaState);
485    } else {
486        addSingleEphemeralMetaKey(outEvents, deviceId, metaState, false, time,
487                AKEYCODE_FUNCTION, AMETA_FUNCTION_ON, currentMetaState);
488        addSingleEphemeralMetaKey(outEvents, deviceId, metaState, false, time,
489                AKEYCODE_SYM, AMETA_SYM_ON, currentMetaState);
490
491        addDoubleEphemeralMetaKey(outEvents, deviceId, metaState, false, time,
492                AKEYCODE_META_LEFT, AMETA_META_LEFT_ON,
493                AKEYCODE_META_RIGHT, AMETA_META_RIGHT_ON,
494                AMETA_META_ON, currentMetaState);
495        addDoubleEphemeralMetaKey(outEvents, deviceId, metaState, false, time,
496                AKEYCODE_CTRL_LEFT, AMETA_CTRL_LEFT_ON,
497                AKEYCODE_CTRL_RIGHT, AMETA_CTRL_RIGHT_ON,
498                AMETA_CTRL_ON, currentMetaState);
499        addDoubleEphemeralMetaKey(outEvents, deviceId, metaState, false, time,
500                AKEYCODE_ALT_LEFT, AMETA_ALT_LEFT_ON,
501                AKEYCODE_ALT_RIGHT, AMETA_ALT_RIGHT_ON,
502                AMETA_ALT_ON, currentMetaState);
503        addDoubleEphemeralMetaKey(outEvents, deviceId, metaState, false, time,
504                AKEYCODE_SHIFT_LEFT, AMETA_SHIFT_LEFT_ON,
505                AKEYCODE_SHIFT_RIGHT, AMETA_SHIFT_RIGHT_ON,
506                AMETA_SHIFT_ON, currentMetaState);
507
508        addLockedMetaKey(outEvents, deviceId, metaState, time,
509                AKEYCODE_SCROLL_LOCK, AMETA_SCROLL_LOCK_ON, currentMetaState);
510        addLockedMetaKey(outEvents, deviceId, metaState, time,
511                AKEYCODE_NUM_LOCK, AMETA_NUM_LOCK_ON, currentMetaState);
512        addLockedMetaKey(outEvents, deviceId, metaState, time,
513                AKEYCODE_CAPS_LOCK, AMETA_CAPS_LOCK_ON, currentMetaState);
514    }
515}
516
517bool KeyCharacterMap::addSingleEphemeralMetaKey(Vector<KeyEvent>& outEvents,
518        int32_t deviceId, int32_t metaState, bool down, nsecs_t time,
519        int32_t keyCode, int32_t keyMetaState,
520        int32_t* currentMetaState) {
521    if ((metaState & keyMetaState) == keyMetaState) {
522        *currentMetaState = updateMetaState(keyCode, down, *currentMetaState);
523        addKey(outEvents, deviceId, keyCode, *currentMetaState, down, time);
524        return true;
525    }
526    return false;
527}
528
529void KeyCharacterMap::addDoubleEphemeralMetaKey(Vector<KeyEvent>& outEvents,
530        int32_t deviceId, int32_t metaState, bool down, nsecs_t time,
531        int32_t leftKeyCode, int32_t leftKeyMetaState,
532        int32_t rightKeyCode, int32_t rightKeyMetaState,
533        int32_t eitherKeyMetaState,
534        int32_t* currentMetaState) {
535    bool specific = false;
536    specific |= addSingleEphemeralMetaKey(outEvents, deviceId, metaState, down, time,
537            leftKeyCode, leftKeyMetaState, currentMetaState);
538    specific |= addSingleEphemeralMetaKey(outEvents, deviceId, metaState, down, time,
539            rightKeyCode, rightKeyMetaState, currentMetaState);
540
541    if (!specific) {
542        addSingleEphemeralMetaKey(outEvents, deviceId, metaState, down, time,
543                leftKeyCode, eitherKeyMetaState, currentMetaState);
544    }
545}
546
547void KeyCharacterMap::addLockedMetaKey(Vector<KeyEvent>& outEvents,
548        int32_t deviceId, int32_t metaState, nsecs_t time,
549        int32_t keyCode, int32_t keyMetaState,
550        int32_t* currentMetaState) {
551    if ((metaState & keyMetaState) == keyMetaState) {
552        *currentMetaState = updateMetaState(keyCode, true, *currentMetaState);
553        addKey(outEvents, deviceId, keyCode, *currentMetaState, true, time);
554        *currentMetaState = updateMetaState(keyCode, false, *currentMetaState);
555        addKey(outEvents, deviceId, keyCode, *currentMetaState, false, time);
556    }
557}
558
559#if HAVE_ANDROID_OS
560sp<KeyCharacterMap> KeyCharacterMap::readFromParcel(Parcel* parcel) {
561    sp<KeyCharacterMap> map = new KeyCharacterMap();
562    map->mType = parcel->readInt32();
563    size_t numKeys = parcel->readInt32();
564    if (parcel->errorCheck()) {
565        return NULL;
566    }
567
568    for (size_t i = 0; i < numKeys; i++) {
569        int32_t keyCode = parcel->readInt32();
570        char16_t label = parcel->readInt32();
571        char16_t number = parcel->readInt32();
572        if (parcel->errorCheck()) {
573            return NULL;
574        }
575
576        Key* key = new Key();
577        key->label = label;
578        key->number = number;
579        map->mKeys.add(keyCode, key);
580
581        Behavior* lastBehavior = NULL;
582        while (parcel->readInt32()) {
583            int32_t metaState = parcel->readInt32();
584            char16_t character = parcel->readInt32();
585            int32_t fallbackKeyCode = parcel->readInt32();
586            if (parcel->errorCheck()) {
587                return NULL;
588            }
589
590            Behavior* behavior = new Behavior();
591            behavior->metaState = metaState;
592            behavior->character = character;
593            behavior->fallbackKeyCode = fallbackKeyCode;
594            if (lastBehavior) {
595                lastBehavior->next = behavior;
596            } else {
597                key->firstBehavior = behavior;
598            }
599            lastBehavior = behavior;
600        }
601
602        if (parcel->errorCheck()) {
603            return NULL;
604        }
605    }
606    return map;
607}
608
609void KeyCharacterMap::writeToParcel(Parcel* parcel) const {
610    parcel->writeInt32(mType);
611
612    size_t numKeys = mKeys.size();
613    parcel->writeInt32(numKeys);
614    for (size_t i = 0; i < numKeys; i++) {
615        int32_t keyCode = mKeys.keyAt(i);
616        const Key* key = mKeys.valueAt(i);
617        parcel->writeInt32(keyCode);
618        parcel->writeInt32(key->label);
619        parcel->writeInt32(key->number);
620        for (const Behavior* behavior = key->firstBehavior; behavior != NULL;
621                behavior = behavior->next) {
622            parcel->writeInt32(1);
623            parcel->writeInt32(behavior->metaState);
624            parcel->writeInt32(behavior->character);
625            parcel->writeInt32(behavior->fallbackKeyCode);
626        }
627        parcel->writeInt32(0);
628    }
629}
630#endif
631
632
633// --- KeyCharacterMap::Key ---
634
635KeyCharacterMap::Key::Key() :
636        label(0), number(0), firstBehavior(NULL) {
637}
638
639KeyCharacterMap::Key::Key(const Key& other) :
640        label(other.label), number(other.number),
641        firstBehavior(other.firstBehavior ? new Behavior(*other.firstBehavior) : NULL) {
642}
643
644KeyCharacterMap::Key::~Key() {
645    Behavior* behavior = firstBehavior;
646    while (behavior) {
647        Behavior* next = behavior->next;
648        delete behavior;
649        behavior = next;
650    }
651}
652
653
654// --- KeyCharacterMap::Behavior ---
655
656KeyCharacterMap::Behavior::Behavior() :
657        next(NULL), metaState(0), character(0), fallbackKeyCode(0) {
658}
659
660KeyCharacterMap::Behavior::Behavior(const Behavior& other) :
661        next(other.next ? new Behavior(*other.next) : NULL),
662        metaState(other.metaState), character(other.character),
663        fallbackKeyCode(other.fallbackKeyCode) {
664}
665
666
667// --- KeyCharacterMap::Parser ---
668
669KeyCharacterMap::Parser::Parser(KeyCharacterMap* map, Tokenizer* tokenizer, Format format) :
670        mMap(map), mTokenizer(tokenizer), mFormat(format), mState(STATE_TOP) {
671}
672
673KeyCharacterMap::Parser::~Parser() {
674}
675
676status_t KeyCharacterMap::Parser::parse() {
677    while (!mTokenizer->isEof()) {
678#if DEBUG_PARSER
679        ALOGD("Parsing %s: '%s'.", mTokenizer->getLocation().string(),
680                mTokenizer->peekRemainderOfLine().string());
681#endif
682
683        mTokenizer->skipDelimiters(WHITESPACE);
684
685        if (!mTokenizer->isEol() && mTokenizer->peekChar() != '#') {
686            switch (mState) {
687            case STATE_TOP: {
688                String8 keywordToken = mTokenizer->nextToken(WHITESPACE);
689                if (keywordToken == "type") {
690                    mTokenizer->skipDelimiters(WHITESPACE);
691                    status_t status = parseType();
692                    if (status) return status;
693                } else if (keywordToken == "map") {
694                    mTokenizer->skipDelimiters(WHITESPACE);
695                    status_t status = parseMap();
696                    if (status) return status;
697                } else if (keywordToken == "key") {
698                    mTokenizer->skipDelimiters(WHITESPACE);
699                    status_t status = parseKey();
700                    if (status) return status;
701                } else {
702                    ALOGE("%s: Expected keyword, got '%s'.", mTokenizer->getLocation().string(),
703                            keywordToken.string());
704                    return BAD_VALUE;
705                }
706                break;
707            }
708
709            case STATE_KEY: {
710                status_t status = parseKeyProperty();
711                if (status) return status;
712                break;
713            }
714            }
715
716            mTokenizer->skipDelimiters(WHITESPACE);
717            if (!mTokenizer->isEol() && mTokenizer->peekChar() != '#') {
718                ALOGE("%s: Expected end of line or trailing comment, got '%s'.",
719                        mTokenizer->getLocation().string(),
720                        mTokenizer->peekRemainderOfLine().string());
721                return BAD_VALUE;
722            }
723        }
724
725        mTokenizer->nextLine();
726    }
727
728    if (mState != STATE_TOP) {
729        ALOGE("%s: Unterminated key description at end of file.",
730                mTokenizer->getLocation().string());
731        return BAD_VALUE;
732    }
733
734    if (mMap->mType == KEYBOARD_TYPE_UNKNOWN) {
735        ALOGE("%s: Keyboard layout missing required keyboard 'type' declaration.",
736                mTokenizer->getLocation().string());
737        return BAD_VALUE;
738    }
739
740    if (mFormat == FORMAT_BASE) {
741        if (mMap->mType == KEYBOARD_TYPE_OVERLAY) {
742            ALOGE("%s: Base keyboard layout must specify a keyboard 'type' other than 'OVERLAY'.",
743                    mTokenizer->getLocation().string());
744            return BAD_VALUE;
745        }
746    } else if (mFormat == FORMAT_OVERLAY) {
747        if (mMap->mType != KEYBOARD_TYPE_OVERLAY) {
748            ALOGE("%s: Overlay keyboard layout missing required keyboard "
749                    "'type OVERLAY' declaration.",
750                    mTokenizer->getLocation().string());
751            return BAD_VALUE;
752        }
753    }
754
755    return NO_ERROR;
756}
757
758status_t KeyCharacterMap::Parser::parseType() {
759    if (mMap->mType != KEYBOARD_TYPE_UNKNOWN) {
760        ALOGE("%s: Duplicate keyboard 'type' declaration.",
761                mTokenizer->getLocation().string());
762        return BAD_VALUE;
763    }
764
765    KeyboardType type;
766    String8 typeToken = mTokenizer->nextToken(WHITESPACE);
767    if (typeToken == "NUMERIC") {
768        type = KEYBOARD_TYPE_NUMERIC;
769    } else if (typeToken == "PREDICTIVE") {
770        type = KEYBOARD_TYPE_PREDICTIVE;
771    } else if (typeToken == "ALPHA") {
772        type = KEYBOARD_TYPE_ALPHA;
773    } else if (typeToken == "FULL") {
774        type = KEYBOARD_TYPE_FULL;
775    } else if (typeToken == "SPECIAL_FUNCTION") {
776        type = KEYBOARD_TYPE_SPECIAL_FUNCTION;
777    } else if (typeToken == "OVERLAY") {
778        type = KEYBOARD_TYPE_OVERLAY;
779    } else {
780        ALOGE("%s: Expected keyboard type label, got '%s'.", mTokenizer->getLocation().string(),
781                typeToken.string());
782        return BAD_VALUE;
783    }
784
785#if DEBUG_PARSER
786    ALOGD("Parsed type: type=%d.", type);
787#endif
788    mMap->mType = type;
789    return NO_ERROR;
790}
791
792status_t KeyCharacterMap::Parser::parseMap() {
793    String8 keywordToken = mTokenizer->nextToken(WHITESPACE);
794    if (keywordToken == "key") {
795        mTokenizer->skipDelimiters(WHITESPACE);
796        return parseMapKey();
797    }
798    ALOGE("%s: Expected keyword after 'map', got '%s'.", mTokenizer->getLocation().string(),
799            keywordToken.string());
800    return BAD_VALUE;
801}
802
803status_t KeyCharacterMap::Parser::parseMapKey() {
804    String8 codeToken = mTokenizer->nextToken(WHITESPACE);
805    bool mapUsage = false;
806    if (codeToken == "usage") {
807        mapUsage = true;
808        mTokenizer->skipDelimiters(WHITESPACE);
809        codeToken = mTokenizer->nextToken(WHITESPACE);
810    }
811
812    char* end;
813    int32_t code = int32_t(strtol(codeToken.string(), &end, 0));
814    if (*end) {
815        ALOGE("%s: Expected key %s number, got '%s'.", mTokenizer->getLocation().string(),
816                mapUsage ? "usage" : "scan code", codeToken.string());
817        return BAD_VALUE;
818    }
819    KeyedVector<int32_t, int32_t>& map =
820            mapUsage ? mMap->mKeysByUsageCode : mMap->mKeysByScanCode;
821    if (map.indexOfKey(code) >= 0) {
822        ALOGE("%s: Duplicate entry for key %s '%s'.", mTokenizer->getLocation().string(),
823                mapUsage ? "usage" : "scan code", codeToken.string());
824        return BAD_VALUE;
825    }
826
827    mTokenizer->skipDelimiters(WHITESPACE);
828    String8 keyCodeToken = mTokenizer->nextToken(WHITESPACE);
829    int32_t keyCode = getKeyCodeByLabel(keyCodeToken.string());
830    if (!keyCode) {
831        ALOGE("%s: Expected key code label, got '%s'.", mTokenizer->getLocation().string(),
832                keyCodeToken.string());
833        return BAD_VALUE;
834    }
835
836#if DEBUG_PARSER
837    ALOGD("Parsed map key %s: code=%d, keyCode=%d.",
838            mapUsage ? "usage" : "scan code", code, keyCode);
839#endif
840    map.add(code, keyCode);
841    return NO_ERROR;
842}
843
844status_t KeyCharacterMap::Parser::parseKey() {
845    String8 keyCodeToken = mTokenizer->nextToken(WHITESPACE);
846    int32_t keyCode = getKeyCodeByLabel(keyCodeToken.string());
847    if (!keyCode) {
848        ALOGE("%s: Expected key code label, got '%s'.", mTokenizer->getLocation().string(),
849                keyCodeToken.string());
850        return BAD_VALUE;
851    }
852    if (mMap->mKeys.indexOfKey(keyCode) >= 0) {
853        ALOGE("%s: Duplicate entry for key code '%s'.", mTokenizer->getLocation().string(),
854                keyCodeToken.string());
855        return BAD_VALUE;
856    }
857
858    mTokenizer->skipDelimiters(WHITESPACE);
859    String8 openBraceToken = mTokenizer->nextToken(WHITESPACE);
860    if (openBraceToken != "{") {
861        ALOGE("%s: Expected '{' after key code label, got '%s'.",
862                mTokenizer->getLocation().string(), openBraceToken.string());
863        return BAD_VALUE;
864    }
865
866#if DEBUG_PARSER
867    ALOGD("Parsed beginning of key: keyCode=%d.", keyCode);
868#endif
869    mKeyCode = keyCode;
870    mMap->mKeys.add(keyCode, new Key());
871    mState = STATE_KEY;
872    return NO_ERROR;
873}
874
875status_t KeyCharacterMap::Parser::parseKeyProperty() {
876    Key* key = mMap->mKeys.valueFor(mKeyCode);
877    String8 token = mTokenizer->nextToken(WHITESPACE_OR_PROPERTY_DELIMITER);
878    if (token == "}") {
879        mState = STATE_TOP;
880        return finishKey(key);
881    }
882
883    Vector<Property> properties;
884
885    // Parse all comma-delimited property names up to the first colon.
886    for (;;) {
887        if (token == "label") {
888            properties.add(Property(PROPERTY_LABEL));
889        } else if (token == "number") {
890            properties.add(Property(PROPERTY_NUMBER));
891        } else {
892            int32_t metaState;
893            status_t status = parseModifier(token, &metaState);
894            if (status) {
895                ALOGE("%s: Expected a property name or modifier, got '%s'.",
896                        mTokenizer->getLocation().string(), token.string());
897                return status;
898            }
899            properties.add(Property(PROPERTY_META, metaState));
900        }
901
902        mTokenizer->skipDelimiters(WHITESPACE);
903        if (!mTokenizer->isEol()) {
904            char ch = mTokenizer->nextChar();
905            if (ch == ':') {
906                break;
907            } else if (ch == ',') {
908                mTokenizer->skipDelimiters(WHITESPACE);
909                token = mTokenizer->nextToken(WHITESPACE_OR_PROPERTY_DELIMITER);
910                continue;
911            }
912        }
913
914        ALOGE("%s: Expected ',' or ':' after property name.",
915                mTokenizer->getLocation().string());
916        return BAD_VALUE;
917    }
918
919    // Parse behavior after the colon.
920    mTokenizer->skipDelimiters(WHITESPACE);
921
922    Behavior behavior;
923    bool haveCharacter = false;
924    bool haveFallback = false;
925
926    do {
927        char ch = mTokenizer->peekChar();
928        if (ch == '\'') {
929            char16_t character;
930            status_t status = parseCharacterLiteral(&character);
931            if (status || !character) {
932                ALOGE("%s: Invalid character literal for key.",
933                        mTokenizer->getLocation().string());
934                return BAD_VALUE;
935            }
936            if (haveCharacter) {
937                ALOGE("%s: Cannot combine multiple character literals or 'none'.",
938                        mTokenizer->getLocation().string());
939                return BAD_VALUE;
940            }
941            behavior.character = character;
942            haveCharacter = true;
943        } else {
944            token = mTokenizer->nextToken(WHITESPACE);
945            if (token == "none") {
946                if (haveCharacter) {
947                    ALOGE("%s: Cannot combine multiple character literals or 'none'.",
948                            mTokenizer->getLocation().string());
949                    return BAD_VALUE;
950                }
951                haveCharacter = true;
952            } else if (token == "fallback") {
953                mTokenizer->skipDelimiters(WHITESPACE);
954                token = mTokenizer->nextToken(WHITESPACE);
955                int32_t keyCode = getKeyCodeByLabel(token.string());
956                if (!keyCode) {
957                    ALOGE("%s: Invalid key code label for fallback behavior, got '%s'.",
958                            mTokenizer->getLocation().string(),
959                            token.string());
960                    return BAD_VALUE;
961                }
962                if (haveFallback) {
963                    ALOGE("%s: Cannot combine multiple fallback key codes.",
964                            mTokenizer->getLocation().string());
965                    return BAD_VALUE;
966                }
967                behavior.fallbackKeyCode = keyCode;
968                haveFallback = true;
969            } else {
970                ALOGE("%s: Expected a key behavior after ':'.",
971                        mTokenizer->getLocation().string());
972                return BAD_VALUE;
973            }
974        }
975
976        mTokenizer->skipDelimiters(WHITESPACE);
977    } while (!mTokenizer->isEol() && mTokenizer->peekChar() != '#');
978
979    // Add the behavior.
980    for (size_t i = 0; i < properties.size(); i++) {
981        const Property& property = properties.itemAt(i);
982        switch (property.property) {
983        case PROPERTY_LABEL:
984            if (key->label) {
985                ALOGE("%s: Duplicate label for key.",
986                        mTokenizer->getLocation().string());
987                return BAD_VALUE;
988            }
989            key->label = behavior.character;
990#if DEBUG_PARSER
991            ALOGD("Parsed key label: keyCode=%d, label=%d.", mKeyCode, key->label);
992#endif
993            break;
994        case PROPERTY_NUMBER:
995            if (key->number) {
996                ALOGE("%s: Duplicate number for key.",
997                        mTokenizer->getLocation().string());
998                return BAD_VALUE;
999            }
1000            key->number = behavior.character;
1001#if DEBUG_PARSER
1002            ALOGD("Parsed key number: keyCode=%d, number=%d.", mKeyCode, key->number);
1003#endif
1004            break;
1005        case PROPERTY_META: {
1006            for (Behavior* b = key->firstBehavior; b; b = b->next) {
1007                if (b->metaState == property.metaState) {
1008                    ALOGE("%s: Duplicate key behavior for modifier.",
1009                            mTokenizer->getLocation().string());
1010                    return BAD_VALUE;
1011                }
1012            }
1013            Behavior* newBehavior = new Behavior(behavior);
1014            newBehavior->metaState = property.metaState;
1015            newBehavior->next = key->firstBehavior;
1016            key->firstBehavior = newBehavior;
1017#if DEBUG_PARSER
1018            ALOGD("Parsed key meta: keyCode=%d, meta=0x%x, char=%d, fallback=%d.", mKeyCode,
1019                    newBehavior->metaState, newBehavior->character, newBehavior->fallbackKeyCode);
1020#endif
1021            break;
1022        }
1023        }
1024    }
1025    return NO_ERROR;
1026}
1027
1028status_t KeyCharacterMap::Parser::finishKey(Key* key) {
1029    // Fill in default number property.
1030    if (!key->number) {
1031        char16_t digit = 0;
1032        char16_t symbol = 0;
1033        for (Behavior* b = key->firstBehavior; b; b = b->next) {
1034            char16_t ch = b->character;
1035            if (ch) {
1036                if (ch >= '0' && ch <= '9') {
1037                    digit = ch;
1038                } else if (ch == '(' || ch == ')' || ch == '#' || ch == '*'
1039                        || ch == '-' || ch == '+' || ch == ',' || ch == '.'
1040                        || ch == '\'' || ch == ':' || ch == ';' || ch == '/') {
1041                    symbol = ch;
1042                }
1043            }
1044        }
1045        key->number = digit ? digit : symbol;
1046    }
1047    return NO_ERROR;
1048}
1049
1050status_t KeyCharacterMap::Parser::parseModifier(const String8& token, int32_t* outMetaState) {
1051    if (token == "base") {
1052        *outMetaState = 0;
1053        return NO_ERROR;
1054    }
1055
1056    int32_t combinedMeta = 0;
1057
1058    const char* str = token.string();
1059    const char* start = str;
1060    for (const char* cur = str; ; cur++) {
1061        char ch = *cur;
1062        if (ch == '+' || ch == '\0') {
1063            size_t len = cur - start;
1064            int32_t metaState = 0;
1065            for (size_t i = 0; i < sizeof(modifiers) / sizeof(Modifier); i++) {
1066                if (strlen(modifiers[i].label) == len
1067                        && strncmp(modifiers[i].label, start, len) == 0) {
1068                    metaState = modifiers[i].metaState;
1069                    break;
1070                }
1071            }
1072            if (!metaState) {
1073                return BAD_VALUE;
1074            }
1075            if (combinedMeta & metaState) {
1076                ALOGE("%s: Duplicate modifier combination '%s'.",
1077                        mTokenizer->getLocation().string(), token.string());
1078                return BAD_VALUE;
1079            }
1080
1081            combinedMeta |= metaState;
1082            start = cur + 1;
1083
1084            if (ch == '\0') {
1085                break;
1086            }
1087        }
1088    }
1089    *outMetaState = combinedMeta;
1090    return NO_ERROR;
1091}
1092
1093status_t KeyCharacterMap::Parser::parseCharacterLiteral(char16_t* outCharacter) {
1094    char ch = mTokenizer->nextChar();
1095    if (ch != '\'') {
1096        goto Error;
1097    }
1098
1099    ch = mTokenizer->nextChar();
1100    if (ch == '\\') {
1101        // Escape sequence.
1102        ch = mTokenizer->nextChar();
1103        if (ch == 'n') {
1104            *outCharacter = '\n';
1105        } else if (ch == 't') {
1106            *outCharacter = '\t';
1107        } else if (ch == '\\') {
1108            *outCharacter = '\\';
1109        } else if (ch == '\'') {
1110            *outCharacter = '\'';
1111        } else if (ch == '"') {
1112            *outCharacter = '"';
1113        } else if (ch == 'u') {
1114            *outCharacter = 0;
1115            for (int i = 0; i < 4; i++) {
1116                ch = mTokenizer->nextChar();
1117                int digit;
1118                if (ch >= '0' && ch <= '9') {
1119                    digit = ch - '0';
1120                } else if (ch >= 'A' && ch <= 'F') {
1121                    digit = ch - 'A' + 10;
1122                } else if (ch >= 'a' && ch <= 'f') {
1123                    digit = ch - 'a' + 10;
1124                } else {
1125                    goto Error;
1126                }
1127                *outCharacter = (*outCharacter << 4) | digit;
1128            }
1129        } else {
1130            goto Error;
1131        }
1132    } else if (ch >= 32 && ch <= 126 && ch != '\'') {
1133        // ASCII literal character.
1134        *outCharacter = ch;
1135    } else {
1136        goto Error;
1137    }
1138
1139    ch = mTokenizer->nextChar();
1140    if (ch != '\'') {
1141        goto Error;
1142    }
1143
1144    // Ensure that we consumed the entire token.
1145    if (mTokenizer->nextToken(WHITESPACE).isEmpty()) {
1146        return NO_ERROR;
1147    }
1148
1149Error:
1150    ALOGE("%s: Malformed character literal.", mTokenizer->getLocation().string());
1151    return BAD_VALUE;
1152}
1153
1154} // namespace android
1155