1/*
2 * Copyright (C) 2010 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
17package android.view;
18
19import android.os.Build;
20import android.util.Log;
21
22/**
23 * Checks whether a sequence of input events is self-consistent.
24 * Logs a description of each problem detected.
25 * <p>
26 * When a problem is detected, the event is tainted.  This mechanism prevents the same
27 * error from being reported multiple times.
28 * </p>
29 *
30 * @hide
31 */
32public final class InputEventConsistencyVerifier {
33    private static final boolean IS_ENG_BUILD = "eng".equals(Build.TYPE);
34
35    private static final String EVENT_TYPE_KEY = "KeyEvent";
36    private static final String EVENT_TYPE_TRACKBALL = "TrackballEvent";
37    private static final String EVENT_TYPE_TOUCH = "TouchEvent";
38    private static final String EVENT_TYPE_GENERIC_MOTION = "GenericMotionEvent";
39
40    // The number of recent events to log when a problem is detected.
41    // Can be set to 0 to disable logging recent events but the runtime overhead of
42    // this feature is negligible on current hardware.
43    private static final int RECENT_EVENTS_TO_LOG = 5;
44
45    // The object to which the verifier is attached.
46    private final Object mCaller;
47
48    // Consistency verifier flags.
49    private final int mFlags;
50
51    // Tag for logging which a client can set to help distinguish the output
52    // from different verifiers since several can be active at the same time.
53    // If not provided defaults to the simple class name.
54    private final String mLogTag;
55
56    // The most recently checked event and the nesting level at which it was checked.
57    // This is only set when the verifier is called from a nesting level greater than 0
58    // so that the verifier can detect when it has been asked to verify the same event twice.
59    // It does not make sense to examine the contents of the last event since it may have
60    // been recycled.
61    private int mLastEventSeq;
62    private String mLastEventType;
63    private int mLastNestingLevel;
64
65    // Copy of the most recent events.
66    private InputEvent[] mRecentEvents;
67    private boolean[] mRecentEventsUnhandled;
68    private int mMostRecentEventIndex;
69
70    // Current event and its type.
71    private InputEvent mCurrentEvent;
72    private String mCurrentEventType;
73
74    // Linked list of key state objects.
75    private KeyState mKeyStateList;
76
77    // Current state of the trackball.
78    private boolean mTrackballDown;
79    private boolean mTrackballUnhandled;
80
81    // Bitfield of pointer ids that are currently down.
82    // Assumes that the largest possible pointer id is 31, which is potentially subject to change.
83    // (See MAX_POINTER_ID in frameworks/base/include/ui/Input.h)
84    private int mTouchEventStreamPointers;
85
86    // The device id and source of the current stream of touch events.
87    private int mTouchEventStreamDeviceId = -1;
88    private int mTouchEventStreamSource;
89
90    // Set to true when we discover that the touch event stream is inconsistent.
91    // Reset on down or cancel.
92    private boolean mTouchEventStreamIsTainted;
93
94    // Set to true if the touch event stream is partially unhandled.
95    private boolean mTouchEventStreamUnhandled;
96
97    // Set to true if we received hover enter.
98    private boolean mHoverEntered;
99
100    // The current violation message.
101    private StringBuilder mViolationMessage;
102
103    /**
104     * Indicates that the verifier is intended to act on raw device input event streams.
105     * Disables certain checks for invariants that are established by the input dispatcher
106     * itself as it delivers input events, such as key repeating behavior.
107     */
108    public static final int FLAG_RAW_DEVICE_INPUT = 1 << 0;
109
110    /**
111     * Creates an input consistency verifier.
112     * @param caller The object to which the verifier is attached.
113     * @param flags Flags to the verifier, or 0 if none.
114     */
115    public InputEventConsistencyVerifier(Object caller, int flags) {
116        this(caller, flags, InputEventConsistencyVerifier.class.getSimpleName());
117    }
118
119    /**
120     * Creates an input consistency verifier.
121     * @param caller The object to which the verifier is attached.
122     * @param flags Flags to the verifier, or 0 if none.
123     * @param logTag Tag for logging. If null defaults to the short class name.
124     */
125    public InputEventConsistencyVerifier(Object caller, int flags, String logTag) {
126        this.mCaller = caller;
127        this.mFlags = flags;
128        this.mLogTag = (logTag != null) ? logTag : "InputEventConsistencyVerifier";
129    }
130
131    /**
132     * Determines whether the instrumentation should be enabled.
133     * @return True if it should be enabled.
134     */
135    public static boolean isInstrumentationEnabled() {
136        return IS_ENG_BUILD;
137    }
138
139    /**
140     * Resets the state of the input event consistency verifier.
141     */
142    public void reset() {
143        mLastEventSeq = -1;
144        mLastNestingLevel = 0;
145        mTrackballDown = false;
146        mTrackballUnhandled = false;
147        mTouchEventStreamPointers = 0;
148        mTouchEventStreamIsTainted = false;
149        mTouchEventStreamUnhandled = false;
150        mHoverEntered = false;
151
152        while (mKeyStateList != null) {
153            final KeyState state = mKeyStateList;
154            mKeyStateList = state.next;
155            state.recycle();
156        }
157    }
158
159    /**
160     * Checks an arbitrary input event.
161     * @param event The event.
162     * @param nestingLevel The nesting level: 0 if called from the base class,
163     * or 1 from a subclass.  If the event was already checked by this consistency verifier
164     * at a higher nesting level, it will not be checked again.  Used to handle the situation
165     * where a subclass dispatching method delegates to its superclass's dispatching method
166     * and both dispatching methods call into the consistency verifier.
167     */
168    public void onInputEvent(InputEvent event, int nestingLevel) {
169        if (event instanceof KeyEvent) {
170            final KeyEvent keyEvent = (KeyEvent)event;
171            onKeyEvent(keyEvent, nestingLevel);
172        } else {
173            final MotionEvent motionEvent = (MotionEvent)event;
174            if (motionEvent.isTouchEvent()) {
175                onTouchEvent(motionEvent, nestingLevel);
176            } else if ((motionEvent.getSource() & InputDevice.SOURCE_CLASS_TRACKBALL) != 0) {
177                onTrackballEvent(motionEvent, nestingLevel);
178            } else {
179                onGenericMotionEvent(motionEvent, nestingLevel);
180            }
181        }
182    }
183
184    /**
185     * Checks a key event.
186     * @param event The event.
187     * @param nestingLevel The nesting level: 0 if called from the base class,
188     * or 1 from a subclass.  If the event was already checked by this consistency verifier
189     * at a higher nesting level, it will not be checked again.  Used to handle the situation
190     * where a subclass dispatching method delegates to its superclass's dispatching method
191     * and both dispatching methods call into the consistency verifier.
192     */
193    public void onKeyEvent(KeyEvent event, int nestingLevel) {
194        if (!startEvent(event, nestingLevel, EVENT_TYPE_KEY)) {
195            return;
196        }
197
198        try {
199            ensureMetaStateIsNormalized(event.getMetaState());
200
201            final int action = event.getAction();
202            final int deviceId = event.getDeviceId();
203            final int source = event.getSource();
204            final int keyCode = event.getKeyCode();
205            switch (action) {
206                case KeyEvent.ACTION_DOWN: {
207                    KeyState state = findKeyState(deviceId, source, keyCode, /*remove*/ false);
208                    if (state != null) {
209                        // If the key is already down, ensure it is a repeat.
210                        // We don't perform this check when processing raw device input
211                        // because the input dispatcher itself is responsible for setting
212                        // the key repeat count before it delivers input events.
213                        if (state.unhandled) {
214                            state.unhandled = false;
215                        } else if ((mFlags & FLAG_RAW_DEVICE_INPUT) == 0
216                                && event.getRepeatCount() == 0) {
217                            problem("ACTION_DOWN but key is already down and this event "
218                                    + "is not a key repeat.");
219                        }
220                    } else {
221                        addKeyState(deviceId, source, keyCode);
222                    }
223                    break;
224                }
225                case KeyEvent.ACTION_UP: {
226                    KeyState state = findKeyState(deviceId, source, keyCode, /*remove*/ true);
227                    if (state == null) {
228                        problem("ACTION_UP but key was not down.");
229                    } else {
230                        state.recycle();
231                    }
232                    break;
233                }
234                case KeyEvent.ACTION_MULTIPLE:
235                    break;
236                default:
237                    problem("Invalid action " + KeyEvent.actionToString(action)
238                            + " for key event.");
239                    break;
240            }
241        } finally {
242            finishEvent();
243        }
244    }
245
246    /**
247     * Checks a trackball event.
248     * @param event The event.
249     * @param nestingLevel The nesting level: 0 if called from the base class,
250     * or 1 from a subclass.  If the event was already checked by this consistency verifier
251     * at a higher nesting level, it will not be checked again.  Used to handle the situation
252     * where a subclass dispatching method delegates to its superclass's dispatching method
253     * and both dispatching methods call into the consistency verifier.
254     */
255    public void onTrackballEvent(MotionEvent event, int nestingLevel) {
256        if (!startEvent(event, nestingLevel, EVENT_TYPE_TRACKBALL)) {
257            return;
258        }
259
260        try {
261            ensureMetaStateIsNormalized(event.getMetaState());
262
263            final int action = event.getAction();
264            final int source = event.getSource();
265            if ((source & InputDevice.SOURCE_CLASS_TRACKBALL) != 0) {
266                switch (action) {
267                    case MotionEvent.ACTION_DOWN:
268                        if (mTrackballDown && !mTrackballUnhandled) {
269                            problem("ACTION_DOWN but trackball is already down.");
270                        } else {
271                            mTrackballDown = true;
272                            mTrackballUnhandled = false;
273                        }
274                        ensureHistorySizeIsZeroForThisAction(event);
275                        ensurePointerCountIsOneForThisAction(event);
276                        break;
277                    case MotionEvent.ACTION_UP:
278                        if (!mTrackballDown) {
279                            problem("ACTION_UP but trackball is not down.");
280                        } else {
281                            mTrackballDown = false;
282                            mTrackballUnhandled = false;
283                        }
284                        ensureHistorySizeIsZeroForThisAction(event);
285                        ensurePointerCountIsOneForThisAction(event);
286                        break;
287                    case MotionEvent.ACTION_MOVE:
288                        ensurePointerCountIsOneForThisAction(event);
289                        break;
290                    default:
291                        problem("Invalid action " + MotionEvent.actionToString(action)
292                                + " for trackball event.");
293                        break;
294                }
295
296                if (mTrackballDown && event.getPressure() <= 0) {
297                    problem("Trackball is down but pressure is not greater than 0.");
298                } else if (!mTrackballDown && event.getPressure() != 0) {
299                    problem("Trackball is up but pressure is not equal to 0.");
300                }
301            } else {
302                problem("Source was not SOURCE_CLASS_TRACKBALL.");
303            }
304        } finally {
305            finishEvent();
306        }
307    }
308
309    /**
310     * Checks a touch event.
311     * @param event The event.
312     * @param nestingLevel The nesting level: 0 if called from the base class,
313     * or 1 from a subclass.  If the event was already checked by this consistency verifier
314     * at a higher nesting level, it will not be checked again.  Used to handle the situation
315     * where a subclass dispatching method delegates to its superclass's dispatching method
316     * and both dispatching methods call into the consistency verifier.
317     */
318    public void onTouchEvent(MotionEvent event, int nestingLevel) {
319        if (!startEvent(event, nestingLevel, EVENT_TYPE_TOUCH)) {
320            return;
321        }
322
323        final int action = event.getAction();
324        final boolean newStream = action == MotionEvent.ACTION_DOWN
325                || action == MotionEvent.ACTION_CANCEL || action == MotionEvent.ACTION_OUTSIDE;
326        if (newStream && (mTouchEventStreamIsTainted || mTouchEventStreamUnhandled)) {
327            mTouchEventStreamIsTainted = false;
328            mTouchEventStreamUnhandled = false;
329            mTouchEventStreamPointers = 0;
330        }
331        if (mTouchEventStreamIsTainted) {
332            event.setTainted(true);
333        }
334
335        try {
336            ensureMetaStateIsNormalized(event.getMetaState());
337
338            final int deviceId = event.getDeviceId();
339            final int source = event.getSource();
340
341            if (!newStream && mTouchEventStreamDeviceId != -1
342                    && (mTouchEventStreamDeviceId != deviceId
343                            || mTouchEventStreamSource != source)) {
344                problem("Touch event stream contains events from multiple sources: "
345                        + "previous device id " + mTouchEventStreamDeviceId
346                        + ", previous source " + Integer.toHexString(mTouchEventStreamSource)
347                        + ", new device id " + deviceId
348                        + ", new source " + Integer.toHexString(source));
349            }
350            mTouchEventStreamDeviceId = deviceId;
351            mTouchEventStreamSource = source;
352
353            final int pointerCount = event.getPointerCount();
354            if ((source & InputDevice.SOURCE_CLASS_POINTER) != 0) {
355                switch (action) {
356                    case MotionEvent.ACTION_DOWN:
357                        if (mTouchEventStreamPointers != 0) {
358                            problem("ACTION_DOWN but pointers are already down.  "
359                                    + "Probably missing ACTION_UP from previous gesture.");
360                        }
361                        ensureHistorySizeIsZeroForThisAction(event);
362                        ensurePointerCountIsOneForThisAction(event);
363                        mTouchEventStreamPointers = 1 << event.getPointerId(0);
364                        break;
365                    case MotionEvent.ACTION_UP:
366                        ensureHistorySizeIsZeroForThisAction(event);
367                        ensurePointerCountIsOneForThisAction(event);
368                        mTouchEventStreamPointers = 0;
369                        mTouchEventStreamIsTainted = false;
370                        break;
371                    case MotionEvent.ACTION_MOVE: {
372                        final int expectedPointerCount =
373                                Integer.bitCount(mTouchEventStreamPointers);
374                        if (pointerCount != expectedPointerCount) {
375                            problem("ACTION_MOVE contained " + pointerCount
376                                    + " pointers but there are currently "
377                                    + expectedPointerCount + " pointers down.");
378                            mTouchEventStreamIsTainted = true;
379                        }
380                        break;
381                    }
382                    case MotionEvent.ACTION_CANCEL:
383                        mTouchEventStreamPointers = 0;
384                        mTouchEventStreamIsTainted = false;
385                        break;
386                    case MotionEvent.ACTION_OUTSIDE:
387                        if (mTouchEventStreamPointers != 0) {
388                            problem("ACTION_OUTSIDE but pointers are still down.");
389                        }
390                        ensureHistorySizeIsZeroForThisAction(event);
391                        ensurePointerCountIsOneForThisAction(event);
392                        mTouchEventStreamIsTainted = false;
393                        break;
394                    default: {
395                        final int actionMasked = event.getActionMasked();
396                        final int actionIndex = event.getActionIndex();
397                        if (actionMasked == MotionEvent.ACTION_POINTER_DOWN) {
398                            if (mTouchEventStreamPointers == 0) {
399                                problem("ACTION_POINTER_DOWN but no other pointers were down.");
400                                mTouchEventStreamIsTainted = true;
401                            }
402                            if (actionIndex < 0 || actionIndex >= pointerCount) {
403                                problem("ACTION_POINTER_DOWN index is " + actionIndex
404                                        + " but the pointer count is " + pointerCount + ".");
405                                mTouchEventStreamIsTainted = true;
406                            } else {
407                                final int id = event.getPointerId(actionIndex);
408                                final int idBit = 1 << id;
409                                if ((mTouchEventStreamPointers & idBit) != 0) {
410                                    problem("ACTION_POINTER_DOWN specified pointer id " + id
411                                            + " which is already down.");
412                                    mTouchEventStreamIsTainted = true;
413                                } else {
414                                    mTouchEventStreamPointers |= idBit;
415                                }
416                            }
417                            ensureHistorySizeIsZeroForThisAction(event);
418                        } else if (actionMasked == MotionEvent.ACTION_POINTER_UP) {
419                            if (actionIndex < 0 || actionIndex >= pointerCount) {
420                                problem("ACTION_POINTER_UP index is " + actionIndex
421                                        + " but the pointer count is " + pointerCount + ".");
422                                mTouchEventStreamIsTainted = true;
423                            } else {
424                                final int id = event.getPointerId(actionIndex);
425                                final int idBit = 1 << id;
426                                if ((mTouchEventStreamPointers & idBit) == 0) {
427                                    problem("ACTION_POINTER_UP specified pointer id " + id
428                                            + " which is not currently down.");
429                                    mTouchEventStreamIsTainted = true;
430                                } else {
431                                    mTouchEventStreamPointers &= ~idBit;
432                                }
433                            }
434                            ensureHistorySizeIsZeroForThisAction(event);
435                        } else {
436                            problem("Invalid action " + MotionEvent.actionToString(action)
437                                    + " for touch event.");
438                        }
439                        break;
440                    }
441                }
442            } else {
443                problem("Source was not SOURCE_CLASS_POINTER.");
444            }
445        } finally {
446            finishEvent();
447        }
448    }
449
450    /**
451     * Checks a generic motion event.
452     * @param event The event.
453     * @param nestingLevel The nesting level: 0 if called from the base class,
454     * or 1 from a subclass.  If the event was already checked by this consistency verifier
455     * at a higher nesting level, it will not be checked again.  Used to handle the situation
456     * where a subclass dispatching method delegates to its superclass's dispatching method
457     * and both dispatching methods call into the consistency verifier.
458     */
459    public void onGenericMotionEvent(MotionEvent event, int nestingLevel) {
460        if (!startEvent(event, nestingLevel, EVENT_TYPE_GENERIC_MOTION)) {
461            return;
462        }
463
464        try {
465            ensureMetaStateIsNormalized(event.getMetaState());
466
467            final int action = event.getAction();
468            final int source = event.getSource();
469            if ((source & InputDevice.SOURCE_CLASS_POINTER) != 0) {
470                switch (action) {
471                    case MotionEvent.ACTION_HOVER_ENTER:
472                        ensurePointerCountIsOneForThisAction(event);
473                        mHoverEntered = true;
474                        break;
475                    case MotionEvent.ACTION_HOVER_MOVE:
476                        ensurePointerCountIsOneForThisAction(event);
477                        break;
478                    case MotionEvent.ACTION_HOVER_EXIT:
479                        ensurePointerCountIsOneForThisAction(event);
480                        if (!mHoverEntered) {
481                            problem("ACTION_HOVER_EXIT without prior ACTION_HOVER_ENTER");
482                        }
483                        mHoverEntered = false;
484                        break;
485                    case MotionEvent.ACTION_SCROLL:
486                        ensureHistorySizeIsZeroForThisAction(event);
487                        ensurePointerCountIsOneForThisAction(event);
488                        break;
489                    default:
490                        problem("Invalid action for generic pointer event.");
491                        break;
492                }
493            } else if ((source & InputDevice.SOURCE_CLASS_JOYSTICK) != 0) {
494                switch (action) {
495                    case MotionEvent.ACTION_MOVE:
496                        ensurePointerCountIsOneForThisAction(event);
497                        break;
498                    default:
499                        problem("Invalid action for generic joystick event.");
500                        break;
501                }
502            }
503        } finally {
504            finishEvent();
505        }
506    }
507
508    /**
509     * Notifies the verifier that a given event was unhandled and the rest of the
510     * trace for the event should be ignored.
511     * This method should only be called if the event was previously checked by
512     * the consistency verifier using {@link #onInputEvent} and other methods.
513     * @param event The event.
514     * @param nestingLevel The nesting level: 0 if called from the base class,
515     * or 1 from a subclass.  If the event was already checked by this consistency verifier
516     * at a higher nesting level, it will not be checked again.  Used to handle the situation
517     * where a subclass dispatching method delegates to its superclass's dispatching method
518     * and both dispatching methods call into the consistency verifier.
519     */
520    public void onUnhandledEvent(InputEvent event, int nestingLevel) {
521        if (nestingLevel != mLastNestingLevel) {
522            return;
523        }
524
525        if (mRecentEventsUnhandled != null) {
526            mRecentEventsUnhandled[mMostRecentEventIndex] = true;
527        }
528
529        if (event instanceof KeyEvent) {
530            final KeyEvent keyEvent = (KeyEvent)event;
531            final int deviceId = keyEvent.getDeviceId();
532            final int source = keyEvent.getSource();
533            final int keyCode = keyEvent.getKeyCode();
534            final KeyState state = findKeyState(deviceId, source, keyCode, /*remove*/ false);
535            if (state != null) {
536                state.unhandled = true;
537            }
538        } else {
539            final MotionEvent motionEvent = (MotionEvent)event;
540            if (motionEvent.isTouchEvent()) {
541                mTouchEventStreamUnhandled = true;
542            } else if ((motionEvent.getSource() & InputDevice.SOURCE_CLASS_TRACKBALL) != 0) {
543                if (mTrackballDown) {
544                    mTrackballUnhandled = true;
545                }
546            }
547        }
548    }
549
550    private void ensureMetaStateIsNormalized(int metaState) {
551        final int normalizedMetaState = KeyEvent.normalizeMetaState(metaState);
552        if (normalizedMetaState != metaState) {
553            problem(String.format("Metastate not normalized.  Was 0x%08x but expected 0x%08x.",
554                    metaState, normalizedMetaState));
555        }
556    }
557
558    private void ensurePointerCountIsOneForThisAction(MotionEvent event) {
559        final int pointerCount = event.getPointerCount();
560        if (pointerCount != 1) {
561            problem("Pointer count is " + pointerCount + " but it should always be 1 for "
562                    + MotionEvent.actionToString(event.getAction()));
563        }
564    }
565
566    private void ensureHistorySizeIsZeroForThisAction(MotionEvent event) {
567        final int historySize = event.getHistorySize();
568        if (historySize != 0) {
569            problem("History size is " + historySize + " but it should always be 0 for "
570                    + MotionEvent.actionToString(event.getAction()));
571        }
572    }
573
574    private boolean startEvent(InputEvent event, int nestingLevel, String eventType) {
575        // Ignore the event if we already checked it at a higher nesting level.
576        final int seq = event.getSequenceNumber();
577        if (seq == mLastEventSeq && nestingLevel < mLastNestingLevel
578                && eventType == mLastEventType) {
579            return false;
580        }
581
582        if (nestingLevel > 0) {
583            mLastEventSeq = seq;
584            mLastEventType = eventType;
585            mLastNestingLevel = nestingLevel;
586        } else {
587            mLastEventSeq = -1;
588            mLastEventType = null;
589            mLastNestingLevel = 0;
590        }
591
592        mCurrentEvent = event;
593        mCurrentEventType = eventType;
594        return true;
595    }
596
597    private void finishEvent() {
598        if (mViolationMessage != null && mViolationMessage.length() != 0) {
599            if (!mCurrentEvent.isTainted()) {
600                // Write a log message only if the event was not already tainted.
601                mViolationMessage.append("\n  in ").append(mCaller);
602                mViolationMessage.append("\n  ");
603                appendEvent(mViolationMessage, 0, mCurrentEvent, false);
604
605                if (RECENT_EVENTS_TO_LOG != 0 && mRecentEvents != null) {
606                    mViolationMessage.append("\n  -- recent events --");
607                    for (int i = 0; i < RECENT_EVENTS_TO_LOG; i++) {
608                        final int index = (mMostRecentEventIndex + RECENT_EVENTS_TO_LOG - i)
609                                % RECENT_EVENTS_TO_LOG;
610                        final InputEvent event = mRecentEvents[index];
611                        if (event == null) {
612                            break;
613                        }
614                        mViolationMessage.append("\n  ");
615                        appendEvent(mViolationMessage, i + 1, event, mRecentEventsUnhandled[index]);
616                    }
617                }
618
619                Log.d(mLogTag, mViolationMessage.toString());
620
621                // Taint the event so that we do not generate additional violations from it
622                // further downstream.
623                mCurrentEvent.setTainted(true);
624            }
625            mViolationMessage.setLength(0);
626        }
627
628        if (RECENT_EVENTS_TO_LOG != 0) {
629            if (mRecentEvents == null) {
630                mRecentEvents = new InputEvent[RECENT_EVENTS_TO_LOG];
631                mRecentEventsUnhandled = new boolean[RECENT_EVENTS_TO_LOG];
632            }
633            final int index = (mMostRecentEventIndex + 1) % RECENT_EVENTS_TO_LOG;
634            mMostRecentEventIndex = index;
635            if (mRecentEvents[index] != null) {
636                mRecentEvents[index].recycle();
637            }
638            mRecentEvents[index] = mCurrentEvent.copy();
639            mRecentEventsUnhandled[index] = false;
640        }
641
642        mCurrentEvent = null;
643        mCurrentEventType = null;
644    }
645
646    private static void appendEvent(StringBuilder message, int index,
647            InputEvent event, boolean unhandled) {
648        message.append(index).append(": sent at ").append(event.getEventTimeNano());
649        message.append(", ");
650        if (unhandled) {
651            message.append("(unhandled) ");
652        }
653        message.append(event);
654    }
655
656    private void problem(String message) {
657        if (mViolationMessage == null) {
658            mViolationMessage = new StringBuilder();
659        }
660        if (mViolationMessage.length() == 0) {
661            mViolationMessage.append(mCurrentEventType).append(": ");
662        } else {
663            mViolationMessage.append("\n  ");
664        }
665        mViolationMessage.append(message);
666    }
667
668    private KeyState findKeyState(int deviceId, int source, int keyCode, boolean remove) {
669        KeyState last = null;
670        KeyState state = mKeyStateList;
671        while (state != null) {
672            if (state.deviceId == deviceId && state.source == source
673                    && state.keyCode == keyCode) {
674                if (remove) {
675                    if (last != null) {
676                        last.next = state.next;
677                    } else {
678                        mKeyStateList = state.next;
679                    }
680                    state.next = null;
681                }
682                return state;
683            }
684            last = state;
685            state = state.next;
686        }
687        return null;
688    }
689
690    private void addKeyState(int deviceId, int source, int keyCode) {
691        KeyState state = KeyState.obtain(deviceId, source, keyCode);
692        state.next = mKeyStateList;
693        mKeyStateList = state;
694    }
695
696    private static final class KeyState {
697        private static Object mRecycledListLock = new Object();
698        private static KeyState mRecycledList;
699
700        public KeyState next;
701        public int deviceId;
702        public int source;
703        public int keyCode;
704        public boolean unhandled;
705
706        private KeyState() {
707        }
708
709        public static KeyState obtain(int deviceId, int source, int keyCode) {
710            KeyState state;
711            synchronized (mRecycledListLock) {
712                state = mRecycledList;
713                if (state != null) {
714                    mRecycledList = state.next;
715                } else {
716                    state = new KeyState();
717                }
718            }
719            state.deviceId = deviceId;
720            state.source = source;
721            state.keyCode = keyCode;
722            state.unhandled = false;
723            return state;
724        }
725
726        public void recycle() {
727            synchronized (mRecycledListLock) {
728                next = mRecycledList;
729                mRecycledList = next;
730            }
731        }
732    }
733}
734