Merge "Add a little input event consistency verifier."
diff --git a/core/java/android/view/GestureDetector.java b/core/java/android/view/GestureDetector.java
index c1e1049..f284f51 100644
--- a/core/java/android/view/GestureDetector.java
+++ b/core/java/android/view/GestureDetector.java
@@ -245,6 +245,13 @@
      */
     private VelocityTracker mVelocityTracker;
 
+    /**
+     * Consistency verifier for debugging purposes.
+     */
+    private final InputEventConsistencyVerifier mInputEventConsistencyVerifier =
+            InputEventConsistencyVerifier.isInstrumentationEnabled() ?
+                    new InputEventConsistencyVerifier(this, 0) : null;
+
     private class GestureHandler extends Handler {
         GestureHandler() {
             super();
@@ -443,6 +450,10 @@
      *              else false.
      */
     public boolean onTouchEvent(MotionEvent ev) {
+        if (mInputEventConsistencyVerifier != null) {
+            mInputEventConsistencyVerifier.onTouchEvent(ev, 0);
+        }
+
         final int action = ev.getAction();
         final float y = ev.getY();
         final float x = ev.getX();
diff --git a/core/java/android/view/InputEvent.java b/core/java/android/view/InputEvent.java
index 03189ca..87e7ea7 100755
--- a/core/java/android/view/InputEvent.java
+++ b/core/java/android/view/InputEvent.java
@@ -68,6 +68,14 @@
     public abstract void setSource(int source);
 
     /**
+     * Copies the event.
+     *
+     * @return A deep copy of the event.
+     * @hide
+     */
+    public abstract InputEvent copy();
+
+    /**
      * Recycles the event.
      * This method should only be used by the system since applications do not
      * expect {@link KeyEvent} objects to be recycled, although {@link MotionEvent}
@@ -76,6 +84,28 @@
      */
     public abstract void recycle();
 
+    /**
+     * Gets a private flag that indicates when the system has detected that this input event
+     * may be inconsistent with respect to the sequence of previously delivered input events,
+     * such as when a key up event is sent but the key was not down or when a pointer
+     * move event is sent but the pointer is not down.
+     *
+     * @return True if this event is tainted.
+     * @hide
+     */
+    public abstract boolean isTainted();
+
+    /**
+     * Sets a private flag that indicates when the system has detected that this input event
+     * may be inconsistent with respect to the sequence of previously delivered input events,
+     * such as when a key up event is sent but the key was not down or when a pointer
+     * move event is sent but the pointer is not down.
+     *
+     * @param tainted True if this event is tainted.
+     * @hide
+     */
+    public abstract void setTainted(boolean tainted);
+
     public int describeContents() {
         return 0;
     }
diff --git a/core/java/android/view/InputEventConsistencyVerifier.java b/core/java/android/view/InputEventConsistencyVerifier.java
new file mode 100644
index 0000000..6618f07
--- /dev/null
+++ b/core/java/android/view/InputEventConsistencyVerifier.java
@@ -0,0 +1,638 @@
+/*
+ * 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.
+ */
+
+package android.view;
+
+import android.os.Build;
+import android.util.Log;
+
+/**
+ * Checks whether a sequence of input events is self-consistent.
+ * Logs a description of each problem detected.
+ * <p>
+ * When a problem is detected, the event is tainted.  This mechanism prevents the same
+ * error from being reported multiple times.
+ * </p>
+ *
+ * @hide
+ */
+public final class InputEventConsistencyVerifier {
+    private static final String TAG = "InputEventConsistencyVerifier";
+    private static final boolean IS_ENG_BUILD = "eng".equals(Build.TYPE);
+
+    // The number of recent events to log when a problem is detected.
+    // Can be set to 0 to disable logging recent events but the runtime overhead of
+    // this feature is negligible on current hardware.
+    private static final int RECENT_EVENTS_TO_LOG = 5;
+
+    // The object to which the verifier is attached.
+    private final Object mCaller;
+
+    // Consistency verifier flags.
+    private final int mFlags;
+
+    // The most recently checked event and the nesting level at which it was checked.
+    // This is only set when the verifier is called from a nesting level greater than 0
+    // so that the verifier can detect when it has been asked to verify the same event twice.
+    // It does not make sense to examine the contents of the last event since it may have
+    // been recycled.
+    private InputEvent mLastEvent;
+    private int mLastNestingLevel;
+
+    // Copy of the most recent events.
+    private InputEvent[] mRecentEvents;
+    private int mMostRecentEventIndex;
+
+    // Current event and its type.
+    private InputEvent mCurrentEvent;
+    private String mCurrentEventType;
+
+    // Linked list of key state objects.
+    private KeyState mKeyStateList;
+
+    // Current state of the trackball.
+    private boolean mTrackballDown;
+
+    // Bitfield of pointer ids that are currently down.
+    // Assumes that the largest possible pointer id is 31, which is potentially subject to change.
+    // (See MAX_POINTER_ID in frameworks/base/include/ui/Input.h)
+    private int mTouchEventStreamPointers;
+
+    // The device id and source of the current stream of touch events.
+    private int mTouchEventStreamDeviceId = -1;
+    private int mTouchEventStreamSource;
+
+    // Set to true when we discover that the touch event stream is inconsistent.
+    // Reset on down or cancel.
+    private boolean mTouchEventStreamIsTainted;
+
+    // Set to true if we received hover enter.
+    private boolean mHoverEntered;
+
+    // The current violation message.
+    private StringBuilder mViolationMessage;
+
+    /**
+     * Indicates that the verifier is intended to act on raw device input event streams.
+     * Disables certain checks for invariants that are established by the input dispatcher
+     * itself as it delivers input events, such as key repeating behavior.
+     */
+    public static final int FLAG_RAW_DEVICE_INPUT = 1 << 0;
+
+    /**
+     * Creates an input consistency verifier.
+     * @param caller The object to which the verifier is attached.
+     * @param flags Flags to the verifier, or 0 if none.
+     */
+    public InputEventConsistencyVerifier(Object caller, int flags) {
+        this.mCaller = caller;
+        this.mFlags = flags;
+    }
+
+    /**
+     * Determines whether the instrumentation should be enabled.
+     * @return True if it should be enabled.
+     */
+    public static boolean isInstrumentationEnabled() {
+        return IS_ENG_BUILD;
+    }
+
+    /**
+     * Resets the state of the input event consistency verifier.
+     */
+    public void reset() {
+        mLastEvent = null;
+        mLastNestingLevel = 0;
+        mTrackballDown = false;
+        mTouchEventStreamPointers = 0;
+        mTouchEventStreamIsTainted = false;
+        mHoverEntered = false;
+    }
+
+    /**
+     * Checks an arbitrary input event.
+     * @param event The event.
+     * @param nestingLevel The nesting level: 0 if called from the base class,
+     * or 1 from a subclass.  If the event was already checked by this consistency verifier
+     * at a higher nesting level, it will not be checked again.  Used to handle the situation
+     * where a subclass dispatching method delegates to its superclass's dispatching method
+     * and both dispatching methods call into the consistency verifier.
+     */
+    public void onInputEvent(InputEvent event, int nestingLevel) {
+        if (event instanceof KeyEvent) {
+            final KeyEvent keyEvent = (KeyEvent)event;
+            onKeyEvent(keyEvent, nestingLevel);
+        } else {
+            final MotionEvent motionEvent = (MotionEvent)event;
+            if (motionEvent.isTouchEvent()) {
+                onTouchEvent(motionEvent, nestingLevel);
+            } else if ((motionEvent.getSource() & InputDevice.SOURCE_CLASS_TRACKBALL) != 0) {
+                onTrackballEvent(motionEvent, nestingLevel);
+            } else {
+                onGenericMotionEvent(motionEvent, nestingLevel);
+            }
+        }
+    }
+
+    /**
+     * Checks a key event.
+     * @param event The event.
+     * @param nestingLevel The nesting level: 0 if called from the base class,
+     * or 1 from a subclass.  If the event was already checked by this consistency verifier
+     * at a higher nesting level, it will not be checked again.  Used to handle the situation
+     * where a subclass dispatching method delegates to its superclass's dispatching method
+     * and both dispatching methods call into the consistency verifier.
+     */
+    public void onKeyEvent(KeyEvent event, int nestingLevel) {
+        if (!startEvent(event, nestingLevel, "KeyEvent")) {
+            return;
+        }
+
+        try {
+            ensureMetaStateIsNormalized(event.getMetaState());
+
+            final int action = event.getAction();
+            final int deviceId = event.getDeviceId();
+            final int source = event.getSource();
+            final int keyCode = event.getKeyCode();
+            switch (action) {
+                case KeyEvent.ACTION_DOWN: {
+                    KeyState state = findKeyState(deviceId, source, keyCode, /*remove*/ false);
+                    if (state != null) {
+                        // If the key is already down, ensure it is a repeat.
+                        // We don't perform this check when processing raw device input
+                        // because the input dispatcher itself is responsible for setting
+                        // the key repeat count before it delivers input events.
+                        if ((mFlags & FLAG_RAW_DEVICE_INPUT) == 0
+                                && event.getRepeatCount() == 0) {
+                            problem("ACTION_DOWN but key is already down and this event "
+                                    + "is not a key repeat.");
+                        }
+                    } else {
+                        addKeyState(deviceId, source, keyCode);
+                    }
+                    break;
+                }
+                case KeyEvent.ACTION_UP: {
+                    KeyState state = findKeyState(deviceId, source, keyCode, /*remove*/ true);
+                    if (state == null) {
+                        problem("ACTION_UP but key was not down.");
+                    } else {
+                        state.recycle();
+                    }
+                    break;
+                }
+                case KeyEvent.ACTION_MULTIPLE:
+                    break;
+                default:
+                    problem("Invalid action " + KeyEvent.actionToString(action)
+                            + " for key event.");
+                    break;
+            }
+        } finally {
+            finishEvent(false);
+        }
+    }
+
+    /**
+     * Checks a trackball event.
+     * @param event The event.
+     * @param nestingLevel The nesting level: 0 if called from the base class,
+     * or 1 from a subclass.  If the event was already checked by this consistency verifier
+     * at a higher nesting level, it will not be checked again.  Used to handle the situation
+     * where a subclass dispatching method delegates to its superclass's dispatching method
+     * and both dispatching methods call into the consistency verifier.
+     */
+    public void onTrackballEvent(MotionEvent event, int nestingLevel) {
+        if (!startEvent(event, nestingLevel, "TrackballEvent")) {
+            return;
+        }
+
+        try {
+            ensureMetaStateIsNormalized(event.getMetaState());
+
+            final int action = event.getAction();
+            final int source = event.getSource();
+            if ((source & InputDevice.SOURCE_CLASS_TRACKBALL) != 0) {
+                switch (action) {
+                    case MotionEvent.ACTION_DOWN:
+                        if (mTrackballDown) {
+                            problem("ACTION_DOWN but trackball is already down.");
+                        } else {
+                            mTrackballDown = true;
+                        }
+                        ensureHistorySizeIsZeroForThisAction(event);
+                        ensurePointerCountIsOneForThisAction(event);
+                        break;
+                    case MotionEvent.ACTION_UP:
+                        if (!mTrackballDown) {
+                            problem("ACTION_UP but trackball is not down.");
+                        } else {
+                            mTrackballDown = false;
+                        }
+                        ensureHistorySizeIsZeroForThisAction(event);
+                        ensurePointerCountIsOneForThisAction(event);
+                        break;
+                    case MotionEvent.ACTION_MOVE:
+                        ensurePointerCountIsOneForThisAction(event);
+                        break;
+                    default:
+                        problem("Invalid action " + MotionEvent.actionToString(action)
+                                + " for trackball event.");
+                        break;
+                }
+
+                if (mTrackballDown && event.getPressure() <= 0) {
+                    problem("Trackball is down but pressure is not greater than 0.");
+                } else if (!mTrackballDown && event.getPressure() != 0) {
+                    problem("Trackball is up but pressure is not equal to 0.");
+                }
+            } else {
+                problem("Source was not SOURCE_CLASS_TRACKBALL.");
+            }
+        } finally {
+            finishEvent(false);
+        }
+    }
+
+    /**
+     * Checks a touch event.
+     * @param event The event.
+     * @param nestingLevel The nesting level: 0 if called from the base class,
+     * or 1 from a subclass.  If the event was already checked by this consistency verifier
+     * at a higher nesting level, it will not be checked again.  Used to handle the situation
+     * where a subclass dispatching method delegates to its superclass's dispatching method
+     * and both dispatching methods call into the consistency verifier.
+     */
+    public void onTouchEvent(MotionEvent event, int nestingLevel) {
+        if (!startEvent(event, nestingLevel, "TouchEvent")) {
+            return;
+        }
+
+        final int action = event.getAction();
+        final boolean newStream = action == MotionEvent.ACTION_DOWN
+                || action == MotionEvent.ACTION_CANCEL;
+        if (mTouchEventStreamIsTainted) {
+            if (newStream) {
+                mTouchEventStreamIsTainted = false;
+            } else {
+                finishEvent(true);
+                return;
+            }
+        }
+
+        try {
+            ensureMetaStateIsNormalized(event.getMetaState());
+
+            final int deviceId = event.getDeviceId();
+            final int source = event.getSource();
+
+            if (!newStream && mTouchEventStreamDeviceId != -1
+                    && (mTouchEventStreamDeviceId != deviceId
+                            || mTouchEventStreamSource != source)) {
+                problem("Touch event stream contains events from multiple sources: "
+                        + "previous device id " + mTouchEventStreamDeviceId
+                        + ", previous source " + Integer.toHexString(mTouchEventStreamSource)
+                        + ", new device id " + deviceId
+                        + ", new source " + Integer.toHexString(source));
+            }
+            mTouchEventStreamDeviceId = deviceId;
+            mTouchEventStreamSource = source;
+
+            final int pointerCount = event.getPointerCount();
+            if ((source & InputDevice.SOURCE_CLASS_POINTER) != 0) {
+                switch (action) {
+                    case MotionEvent.ACTION_DOWN:
+                        if (mTouchEventStreamPointers != 0) {
+                            problem("ACTION_DOWN but pointers are already down.  "
+                                    + "Probably missing ACTION_UP from previous gesture.");
+                        }
+                        ensureHistorySizeIsZeroForThisAction(event);
+                        ensurePointerCountIsOneForThisAction(event);
+                        mTouchEventStreamPointers = 1 << event.getPointerId(0);
+                        break;
+                    case MotionEvent.ACTION_UP:
+                        ensureHistorySizeIsZeroForThisAction(event);
+                        ensurePointerCountIsOneForThisAction(event);
+                        mTouchEventStreamPointers = 0;
+                        mTouchEventStreamIsTainted = false;
+                        break;
+                    case MotionEvent.ACTION_MOVE: {
+                        final int expectedPointerCount =
+                                Integer.bitCount(mTouchEventStreamPointers);
+                        if (pointerCount != expectedPointerCount) {
+                            problem("ACTION_MOVE contained " + pointerCount
+                                    + " pointers but there are currently "
+                                    + expectedPointerCount + " pointers down.");
+                            mTouchEventStreamIsTainted = true;
+                        }
+                        break;
+                    }
+                    case MotionEvent.ACTION_CANCEL:
+                        mTouchEventStreamPointers = 0;
+                        mTouchEventStreamIsTainted = false;
+                        break;
+                    case MotionEvent.ACTION_OUTSIDE:
+                        if (mTouchEventStreamPointers != 0) {
+                            problem("ACTION_OUTSIDE but pointers are still down.");
+                        }
+                        ensureHistorySizeIsZeroForThisAction(event);
+                        ensurePointerCountIsOneForThisAction(event);
+                        mTouchEventStreamIsTainted = false;
+                        break;
+                    default: {
+                        final int actionMasked = event.getActionMasked();
+                        final int actionIndex = event.getActionIndex();
+                        if (actionMasked == MotionEvent.ACTION_POINTER_DOWN) {
+                            if (mTouchEventStreamPointers == 0) {
+                                problem("ACTION_POINTER_DOWN but no other pointers were down.");
+                                mTouchEventStreamIsTainted = true;
+                            }
+                            if (actionIndex < 0 || actionIndex >= pointerCount) {
+                                problem("ACTION_POINTER_DOWN index is " + actionIndex
+                                        + " but the pointer count is " + pointerCount + ".");
+                                mTouchEventStreamIsTainted = true;
+                            } else {
+                                final int id = event.getPointerId(actionIndex);
+                                final int idBit = 1 << id;
+                                if ((mTouchEventStreamPointers & idBit) != 0) {
+                                    problem("ACTION_POINTER_DOWN specified pointer id " + id
+                                            + " which is already down.");
+                                    mTouchEventStreamIsTainted = true;
+                                } else {
+                                    mTouchEventStreamPointers |= idBit;
+                                }
+                            }
+                            ensureHistorySizeIsZeroForThisAction(event);
+                        } else if (actionMasked == MotionEvent.ACTION_POINTER_UP) {
+                            if (actionIndex < 0 || actionIndex >= pointerCount) {
+                                problem("ACTION_POINTER_UP index is " + actionIndex
+                                        + " but the pointer count is " + pointerCount + ".");
+                                mTouchEventStreamIsTainted = true;
+                            } else {
+                                final int id = event.getPointerId(actionIndex);
+                                final int idBit = 1 << id;
+                                if ((mTouchEventStreamPointers & idBit) == 0) {
+                                    problem("ACTION_POINTER_UP specified pointer id " + id
+                                            + " which is not currently down.");
+                                    mTouchEventStreamIsTainted = true;
+                                } else {
+                                    mTouchEventStreamPointers &= ~idBit;
+                                }
+                            }
+                            ensureHistorySizeIsZeroForThisAction(event);
+                        } else {
+                            problem("Invalid action " + MotionEvent.actionToString(action)
+                                    + " for touch event.");
+                        }
+                        break;
+                    }
+                }
+            } else {
+                problem("Source was not SOURCE_CLASS_POINTER.");
+            }
+        } finally {
+            finishEvent(false);
+        }
+    }
+
+    /**
+     * Checks a generic motion event.
+     * @param event The event.
+     * @param nestingLevel The nesting level: 0 if called from the base class,
+     * or 1 from a subclass.  If the event was already checked by this consistency verifier
+     * at a higher nesting level, it will not be checked again.  Used to handle the situation
+     * where a subclass dispatching method delegates to its superclass's dispatching method
+     * and both dispatching methods call into the consistency verifier.
+     */
+    public void onGenericMotionEvent(MotionEvent event, int nestingLevel) {
+        if (!startEvent(event, nestingLevel, "GenericMotionEvent")) {
+            return;
+        }
+
+        try {
+            ensureMetaStateIsNormalized(event.getMetaState());
+
+            final int action = event.getAction();
+            final int source = event.getSource();
+            if ((source & InputDevice.SOURCE_CLASS_POINTER) != 0) {
+                switch (action) {
+                    case MotionEvent.ACTION_HOVER_ENTER:
+                        ensurePointerCountIsOneForThisAction(event);
+                        mHoverEntered = true;
+                        break;
+                    case MotionEvent.ACTION_HOVER_MOVE:
+                        ensurePointerCountIsOneForThisAction(event);
+                        break;
+                    case MotionEvent.ACTION_HOVER_EXIT:
+                        ensurePointerCountIsOneForThisAction(event);
+                        if (!mHoverEntered) {
+                            problem("ACTION_HOVER_EXIT without prior ACTION_HOVER_ENTER");
+                        }
+                        mHoverEntered = false;
+                        break;
+                    case MotionEvent.ACTION_SCROLL:
+                        ensureHistorySizeIsZeroForThisAction(event);
+                        ensurePointerCountIsOneForThisAction(event);
+                        break;
+                    default:
+                        problem("Invalid action for generic pointer event.");
+                        break;
+                }
+            } else if ((source & InputDevice.SOURCE_CLASS_JOYSTICK) != 0) {
+                switch (action) {
+                    case MotionEvent.ACTION_MOVE:
+                        ensurePointerCountIsOneForThisAction(event);
+                        break;
+                    default:
+                        problem("Invalid action for generic joystick event.");
+                        break;
+                }
+            }
+        } finally {
+            finishEvent(false);
+        }
+    }
+
+    private void ensureMetaStateIsNormalized(int metaState) {
+        final int normalizedMetaState = KeyEvent.normalizeMetaState(metaState);
+        if (normalizedMetaState != metaState) {
+            problem(String.format("Metastate not normalized.  Was 0x%08x but expected 0x%08x.",
+                    metaState, normalizedMetaState));
+        }
+    }
+
+    private void ensurePointerCountIsOneForThisAction(MotionEvent event) {
+        final int pointerCount = event.getPointerCount();
+        if (pointerCount != 1) {
+            problem("Pointer count is " + pointerCount + " but it should always be 1 for "
+                    + MotionEvent.actionToString(event.getAction()));
+        }
+    }
+
+    private void ensureHistorySizeIsZeroForThisAction(MotionEvent event) {
+        final int historySize = event.getHistorySize();
+        if (historySize != 0) {
+            problem("History size is " + historySize + " but it should always be 0 for "
+                    + MotionEvent.actionToString(event.getAction()));
+        }
+    }
+
+    private boolean startEvent(InputEvent event, int nestingLevel, String eventType) {
+        // Ignore the event if it is already tainted.
+        if (event.isTainted()) {
+            return false;
+        }
+
+        // Ignore the event if we already checked it at a higher nesting level.
+        if (event == mLastEvent && nestingLevel < mLastNestingLevel) {
+            return false;
+        }
+
+        if (nestingLevel > 0) {
+            mLastEvent = event;
+            mLastNestingLevel = nestingLevel;
+        } else {
+            mLastEvent = null;
+            mLastNestingLevel = 0;
+        }
+
+        mCurrentEvent = event;
+        mCurrentEventType = eventType;
+        return true;
+    }
+
+    private void finishEvent(boolean tainted) {
+        if (mViolationMessage != null && mViolationMessage.length() != 0) {
+            mViolationMessage.append("\n  in ").append(mCaller);
+            mViolationMessage.append("\n  ").append(mCurrentEvent);
+
+            if (RECENT_EVENTS_TO_LOG != 0 && mRecentEvents != null) {
+                mViolationMessage.append("\n  -- recent events --");
+                for (int i = 0; i < RECENT_EVENTS_TO_LOG; i++) {
+                    final int index = (mMostRecentEventIndex + RECENT_EVENTS_TO_LOG - i)
+                            % RECENT_EVENTS_TO_LOG;
+                    final InputEvent event = mRecentEvents[index];
+                    if (event == null) {
+                        break;
+                    }
+                    mViolationMessage.append("\n  ").append(i + 1).append(": ").append(event);
+                }
+            }
+
+            Log.d(TAG, mViolationMessage.toString());
+            mViolationMessage.setLength(0);
+            tainted = true;
+        }
+
+        if (tainted) {
+            // Taint the event so that we do not generate additional violations from it
+            // further downstream.
+            mCurrentEvent.setTainted(true);
+        }
+
+        if (RECENT_EVENTS_TO_LOG != 0) {
+            if (mRecentEvents == null) {
+                mRecentEvents = new InputEvent[RECENT_EVENTS_TO_LOG];
+            }
+            final int index = (mMostRecentEventIndex + 1) % RECENT_EVENTS_TO_LOG;
+            mMostRecentEventIndex = index;
+            if (mRecentEvents[index] != null) {
+                mRecentEvents[index].recycle();
+            }
+            mRecentEvents[index] = mCurrentEvent.copy();
+        }
+
+        mCurrentEvent = null;
+        mCurrentEventType = null;
+    }
+
+    private void problem(String message) {
+        if (mViolationMessage == null) {
+            mViolationMessage = new StringBuilder();
+        }
+        if (mViolationMessage.length() == 0) {
+            mViolationMessage.append(mCurrentEventType).append(": ");
+        } else {
+            mViolationMessage.append("\n  ");
+        }
+        mViolationMessage.append(message);
+    }
+
+    private KeyState findKeyState(int deviceId, int source, int keyCode, boolean remove) {
+        KeyState last = null;
+        KeyState state = mKeyStateList;
+        while (state != null) {
+            if (state.deviceId == deviceId && state.source == source
+                    && state.keyCode == keyCode) {
+                if (remove) {
+                    if (last != null) {
+                        last.next = state.next;
+                    } else {
+                        mKeyStateList = state.next;
+                    }
+                    state.next = null;
+                }
+                return state;
+            }
+            last = state;
+            state = state.next;
+        }
+        return null;
+    }
+
+    private void addKeyState(int deviceId, int source, int keyCode) {
+        KeyState state = KeyState.obtain(deviceId, source, keyCode);
+        state.next = mKeyStateList;
+        mKeyStateList = state;
+    }
+
+    private static final class KeyState {
+        private static Object mRecycledListLock = new Object();
+        private static KeyState mRecycledList;
+
+        public KeyState next;
+        public int deviceId;
+        public int source;
+        public int keyCode;
+
+        private KeyState() {
+        }
+
+        public static KeyState obtain(int deviceId, int source, int keyCode) {
+            KeyState state;
+            synchronized (mRecycledListLock) {
+                state = mRecycledList;
+                if (state != null) {
+                    mRecycledList = state.next;
+                } else {
+                    state = new KeyState();
+                }
+            }
+            state.deviceId = deviceId;
+            state.source = source;
+            state.keyCode = keyCode;
+            return state;
+        }
+
+        public void recycle() {
+            synchronized (mRecycledListLock) {
+                next = mRecycledList;
+                mRecycledList = next;
+            }
+        }
+    }
+}
diff --git a/core/java/android/view/KeyEvent.java b/core/java/android/view/KeyEvent.java
index 8070c6a..4320160 100755
--- a/core/java/android/view/KeyEvent.java
+++ b/core/java/android/view/KeyEvent.java
@@ -1170,7 +1170,18 @@
      * @hide
      */
     public static final int FLAG_START_TRACKING = 0x40000000;
-    
+
+    /**
+     * Private flag that indicates when the system has detected that this key event
+     * may be inconsistent with respect to the sequence of previously delivered key events,
+     * such as when a key up event is sent but the key was not down.
+     *
+     * @hide
+     * @see #isTainted
+     * @see #setTainted
+     */
+    public static final int FLAG_TAINTED = 0x80000000;
+
     /**
      * Returns the maximum keycode.
      */
@@ -1535,6 +1546,33 @@
     }
 
     /**
+     * Obtains a (potentially recycled) copy of another key event.
+     *
+     * @hide
+     */
+    public static KeyEvent obtain(KeyEvent other) {
+        KeyEvent ev = obtain();
+        ev.mDownTime = other.mDownTime;
+        ev.mEventTime = other.mEventTime;
+        ev.mAction = other.mAction;
+        ev.mKeyCode = other.mKeyCode;
+        ev.mRepeatCount = other.mRepeatCount;
+        ev.mMetaState = other.mMetaState;
+        ev.mDeviceId = other.mDeviceId;
+        ev.mScanCode = other.mScanCode;
+        ev.mFlags = other.mFlags;
+        ev.mSource = other.mSource;
+        ev.mCharacters = other.mCharacters;
+        return ev;
+    }
+
+    /** @hide */
+    @Override
+    public KeyEvent copy() {
+        return obtain(this);
+    }
+
+    /**
      * Recycles a key event.
      * Key events should only be recycled if they are owned by the system since user
      * code expects them to be essentially immutable, "tracking" notwithstanding.
@@ -1635,7 +1673,19 @@
         event.mFlags = flags;
         return event;
     }
-    
+
+    /** @hide */
+    @Override
+    public final boolean isTainted() {
+        return (mFlags & FLAG_TAINTED) != 0;
+    }
+
+    /** @hide */
+    @Override
+    public final void setTainted(boolean tainted) {
+        mFlags = tainted ? mFlags | FLAG_TAINTED : mFlags & ~FLAG_TAINTED;
+    }
+
     /**
      * Don't use in new code, instead explicitly check
      * {@link #getAction()}.
diff --git a/core/java/android/view/MotionEvent.java b/core/java/android/view/MotionEvent.java
index 3c34479..7611b08 100644
--- a/core/java/android/view/MotionEvent.java
+++ b/core/java/android/view/MotionEvent.java
@@ -308,6 +308,17 @@
     public static final int FLAG_WINDOW_IS_OBSCURED = 0x1;
 
     /**
+     * Private flag that indicates when the system has detected that this motion event
+     * may be inconsistent with respect to the sequence of previously delivered motion events,
+     * such as when a pointer move event is sent but the pointer is not down.
+     *
+     * @hide
+     * @see #isTainted
+     * @see #setTainted
+     */
+    public static final int FLAG_TAINTED = 0x80000000;
+
+    /**
      * Flag indicating the motion event intersected the top edge of the screen.
      */
     public static final int EDGE_TOP = 0x00000001;
@@ -1054,6 +1065,7 @@
     private static native void nativeSetAction(int nativePtr, int action);
     private static native boolean nativeIsTouchEvent(int nativePtr);
     private static native int nativeGetFlags(int nativePtr);
+    private static native void nativeSetFlags(int nativePtr, int flags);
     private static native int nativeGetEdgeFlags(int nativePtr);
     private static native void nativeSetEdgeFlags(int nativePtr, int action);
     private static native int nativeGetMetaState(int nativePtr);
@@ -1290,6 +1302,12 @@
         return ev;
     }
 
+    /** @hide */
+    @Override
+    public MotionEvent copy() {
+        return obtain(this);
+    }
+
     /**
      * Recycle the MotionEvent, to be re-used by a later caller.  After calling
      * this function you must not ever touch the event again.
@@ -1403,6 +1421,20 @@
         return nativeGetFlags(mNativePtr);
     }
 
+    /** @hide */
+    @Override
+    public final boolean isTainted() {
+        final int flags = getFlags();
+        return (flags & FLAG_TAINTED) != 0;
+    }
+
+    /** @hide */
+    @Override
+    public final void setTainted(boolean tainted) {
+        final int flags = getFlags();
+        nativeSetFlags(mNativePtr, tainted ? flags | FLAG_TAINTED : flags & ~FLAG_TAINTED);
+    }
+
     /**
      * Returns the time (in ms) when the user originally pressed down to start
      * a stream of position events.
diff --git a/core/java/android/view/ScaleGestureDetector.java b/core/java/android/view/ScaleGestureDetector.java
index d638e70..456857a 100644
--- a/core/java/android/view/ScaleGestureDetector.java
+++ b/core/java/android/view/ScaleGestureDetector.java
@@ -163,6 +163,13 @@
     private int mActiveId1;
     private boolean mActive0MostRecent;
 
+    /**
+     * Consistency verifier for debugging purposes.
+     */
+    private final InputEventConsistencyVerifier mInputEventConsistencyVerifier =
+            InputEventConsistencyVerifier.isInstrumentationEnabled() ?
+                    new InputEventConsistencyVerifier(this, 0) : null;
+
     public ScaleGestureDetector(Context context, OnScaleGestureListener listener) {
         ViewConfiguration config = ViewConfiguration.get(context);
         mContext = context;
@@ -171,6 +178,10 @@
     }
 
     public boolean onTouchEvent(MotionEvent event) {
+        if (mInputEventConsistencyVerifier != null) {
+            mInputEventConsistencyVerifier.onTouchEvent(event, 0);
+        }
+
         final int action = event.getActionMasked();
         boolean handled = true;
 
diff --git a/core/java/android/view/View.java b/core/java/android/view/View.java
index 0ef56cc..e329e97d 100644
--- a/core/java/android/view/View.java
+++ b/core/java/android/view/View.java
@@ -2384,6 +2384,14 @@
     Rect mLocalDirtyRect;
 
     /**
+     * Consistency verifier for debugging purposes.
+     * @hide
+     */
+    protected final InputEventConsistencyVerifier mInputEventConsistencyVerifier =
+            InputEventConsistencyVerifier.isInstrumentationEnabled() ?
+                    new InputEventConsistencyVerifier(this, 0) : null;
+
+    /**
      * Simple constructor to use when creating a view from code.
      *
      * @param context The Context the view is running in, through which it can
@@ -4590,13 +4598,16 @@
      * @return True if the event was handled, false otherwise.
      */
     public boolean dispatchKeyEvent(KeyEvent event) {
-        // If any attached key listener a first crack at the event.
+        if (mInputEventConsistencyVerifier != null) {
+            mInputEventConsistencyVerifier.onKeyEvent(event, 0);
+        }
 
         //noinspection SimplifiableIfStatement,deprecation
         if (android.util.Config.LOGV) {
             captureViewInfo("captureViewKeyEvent", this);
         }
 
+        // Give any attached key listener a first crack at the event.
         //noinspection SimplifiableIfStatement
         if (mOnKeyListener != null && (mViewFlags & ENABLED_MASK) == ENABLED
                 && mOnKeyListener.onKey(this, event.getKeyCode(), event)) {
@@ -4625,6 +4636,10 @@
      * @return True if the event was handled by the view, false otherwise.
      */
     public boolean dispatchTouchEvent(MotionEvent event) {
+        if (mInputEventConsistencyVerifier != null) {
+            mInputEventConsistencyVerifier.onTouchEvent(event, 0);
+        }
+
         if (!onFilterTouchEventForSecurity(event)) {
             return false;
         }
@@ -4662,6 +4677,10 @@
      * @return True if the event was handled by the view, false otherwise.
      */
     public boolean dispatchTrackballEvent(MotionEvent event) {
+        if (mInputEventConsistencyVerifier != null) {
+            mInputEventConsistencyVerifier.onTrackballEvent(event, 0);
+        }
+
         //Log.i("view", "view=" + this + ", " + event.toString());
         return onTrackballEvent(event);
     }
@@ -4679,6 +4698,10 @@
      * @return True if the event was handled by the view, false otherwise.
      */
     public boolean dispatchGenericMotionEvent(MotionEvent event) {
+        if (mInputEventConsistencyVerifier != null) {
+            mInputEventConsistencyVerifier.onGenericMotionEvent(event, 0);
+        }
+
         final int source = event.getSource();
         if ((source & InputDevice.SOURCE_CLASS_POINTER) != 0) {
             final int action = event.getAction();
diff --git a/core/java/android/view/ViewGroup.java b/core/java/android/view/ViewGroup.java
index f7f2685..0d4f3d0 100644
--- a/core/java/android/view/ViewGroup.java
+++ b/core/java/android/view/ViewGroup.java
@@ -1126,6 +1126,10 @@
      */
     @Override
     public boolean dispatchKeyEvent(KeyEvent event) {
+        if (mInputEventConsistencyVerifier != null) {
+            mInputEventConsistencyVerifier.onKeyEvent(event, 1);
+        }
+
         if ((mPrivateFlags & (FOCUSED | HAS_BOUNDS)) == (FOCUSED | HAS_BOUNDS)) {
             return super.dispatchKeyEvent(event);
         } else if (mFocused != null && (mFocused.mPrivateFlags & HAS_BOUNDS) == HAS_BOUNDS) {
@@ -1152,6 +1156,10 @@
      */
     @Override
     public boolean dispatchTrackballEvent(MotionEvent event) {
+        if (mInputEventConsistencyVerifier != null) {
+            mInputEventConsistencyVerifier.onTrackballEvent(event, 1);
+        }
+
         if ((mPrivateFlags & (FOCUSED | HAS_BOUNDS)) == (FOCUSED | HAS_BOUNDS)) {
             return super.dispatchTrackballEvent(event);
         } else if (mFocused != null && (mFocused.mPrivateFlags & HAS_BOUNDS) == HAS_BOUNDS) {
@@ -1332,6 +1340,10 @@
      */
     @Override
     public boolean dispatchTouchEvent(MotionEvent ev) {
+        if (mInputEventConsistencyVerifier != null) {
+            mInputEventConsistencyVerifier.onTouchEvent(ev, 1);
+        }
+
         if (!onFilterTouchEventForSecurity(ev)) {
             return false;
         }
diff --git a/core/java/android/view/ViewRoot.java b/core/java/android/view/ViewRoot.java
index 3c386b4..2f9d501 100644
--- a/core/java/android/view/ViewRoot.java
+++ b/core/java/android/view/ViewRoot.java
@@ -250,6 +250,13 @@
 
     private final int mDensity;
 
+    /**
+     * Consistency verifier for debugging purposes.
+     */
+    protected final InputEventConsistencyVerifier mInputEventConsistencyVerifier =
+            InputEventConsistencyVerifier.isInstrumentationEnabled() ?
+                    new InputEventConsistencyVerifier(this, 0) : null;
+
     public static IWindowSession getWindowSession(Looper mainLooper) {
         synchronized (mStaticInit) {
             if (!mInitialized) {
@@ -2316,6 +2323,14 @@
     }
 
     private void deliverPointerEvent(MotionEvent event, boolean sendDone) {
+        if (mInputEventConsistencyVerifier != null) {
+            if (event.isTouchEvent()) {
+                mInputEventConsistencyVerifier.onTouchEvent(event, 0);
+            } else {
+                mInputEventConsistencyVerifier.onGenericMotionEvent(event, 0);
+            }
+        }
+
         // If there is no view, then the event will not be handled.
         if (mView == null || !mAdded) {
             finishMotionEvent(event, sendDone, false);
@@ -2422,6 +2437,10 @@
     private void deliverTrackballEvent(MotionEvent event, boolean sendDone) {
         if (DEBUG_TRACKBALL) Log.v(TAG, "Motion event:" + event);
 
+        if (mInputEventConsistencyVerifier != null) {
+            mInputEventConsistencyVerifier.onTrackballEvent(event, 0);
+        }
+
         // If there is no view, then the event will not be handled.
         if (mView == null || !mAdded) {
             finishMotionEvent(event, sendDone, false);
@@ -2550,6 +2569,10 @@
     }
 
     private void deliverGenericMotionEvent(MotionEvent event, boolean sendDone) {
+        if (mInputEventConsistencyVerifier != null) {
+            mInputEventConsistencyVerifier.onGenericMotionEvent(event, 0);
+        }
+
         final int source = event.getSource();
         final boolean isJoystick = (source & InputDevice.SOURCE_CLASS_JOYSTICK) != 0;
 
@@ -2785,6 +2808,10 @@
     }
 
     private void deliverKeyEvent(KeyEvent event, boolean sendDone) {
+        if (mInputEventConsistencyVerifier != null) {
+            mInputEventConsistencyVerifier.onKeyEvent(event, 0);
+        }
+
         // If there is no view, then the event will not be handled.
         if (mView == null || !mAdded) {
             finishKeyEvent(event, sendDone, false);
diff --git a/core/jni/android_view_MotionEvent.cpp b/core/jni/android_view_MotionEvent.cpp
index 4ce471e..2ede7ec 100644
--- a/core/jni/android_view_MotionEvent.cpp
+++ b/core/jni/android_view_MotionEvent.cpp
@@ -430,6 +430,12 @@
     return event->getFlags();
 }
 
+static void android_view_MotionEvent_nativeSetFlags(JNIEnv* env, jclass clazz,
+        jint nativePtr, jint flags) {
+    MotionEvent* event = reinterpret_cast<MotionEvent*>(nativePtr);
+    event->setFlags(flags);
+}
+
 static jint android_view_MotionEvent_nativeGetEdgeFlags(JNIEnv* env, jclass clazz,
         jint nativePtr) {
     MotionEvent* event = reinterpret_cast<MotionEvent*>(nativePtr);
@@ -656,6 +662,9 @@
     { "nativeGetFlags",
             "(I)I",
             (void*)android_view_MotionEvent_nativeGetFlags },
+    { "nativeSetFlags",
+            "(II)V",
+            (void*)android_view_MotionEvent_nativeSetFlags },
     { "nativeGetEdgeFlags",
             "(I)I",
             (void*)android_view_MotionEvent_nativeGetEdgeFlags },
diff --git a/include/ui/Input.h b/include/ui/Input.h
index b22986d..0dc29c8 100644
--- a/include/ui/Input.h
+++ b/include/ui/Input.h
@@ -37,10 +37,16 @@
  * Additional private constants not defined in ndk/ui/input.h.
  */
 enum {
-    /*
-     * Private control to determine when an app is tracking a key sequence.
-     */
-    AKEY_EVENT_FLAG_START_TRACKING = 0x40000000
+    /* Private control to determine when an app is tracking a key sequence. */
+    AKEY_EVENT_FLAG_START_TRACKING = 0x40000000,
+
+    /* Key event is inconsistent with previously sent key events. */
+    AKEY_EVENT_FLAG_TAINTED = 0x80000000,
+};
+
+enum {
+    /* Motion event is inconsistent with previously sent motion events. */
+    AMOTION_EVENT_FLAG_TAINTED = 0x80000000,
 };
 
 enum {
@@ -328,6 +334,8 @@
 
     inline int32_t getFlags() const { return mFlags; }
 
+    inline void setFlags(int32_t flags) { mFlags = flags; }
+
     inline int32_t getEdgeFlags() const { return mEdgeFlags; }
 
     inline void setEdgeFlags(int32_t edgeFlags) { mEdgeFlags = edgeFlags; }
diff --git a/services/java/com/android/server/wm/InputFilter.java b/services/java/com/android/server/wm/InputFilter.java
index 78b87fe..7e1ab07 100644
--- a/services/java/com/android/server/wm/InputFilter.java
+++ b/services/java/com/android/server/wm/InputFilter.java
@@ -20,6 +20,7 @@
 import android.os.Looper;
 import android.os.Message;
 import android.view.InputEvent;
+import android.view.InputEventConsistencyVerifier;
 import android.view.KeyEvent;
 import android.view.MotionEvent;
 import android.view.WindowManagerPolicy;
@@ -100,6 +101,16 @@
     private final H mH;
     private Host mHost;
 
+    // Consistency verifiers for debugging purposes.
+    private final InputEventConsistencyVerifier mInboundInputEventConsistencyVerifier =
+            InputEventConsistencyVerifier.isInstrumentationEnabled() ?
+                    new InputEventConsistencyVerifier(this,
+                            InputEventConsistencyVerifier.FLAG_RAW_DEVICE_INPUT) : null;
+    private final InputEventConsistencyVerifier mOutboundInputEventConsistencyVerifier =
+            InputEventConsistencyVerifier.isInstrumentationEnabled() ?
+                    new InputEventConsistencyVerifier(this,
+                            InputEventConsistencyVerifier.FLAG_RAW_DEVICE_INPUT) : null;
+
     /**
      * Creates the input filter.
      *
@@ -152,6 +163,9 @@
             throw new IllegalStateException("Cannot send input event because the input filter " +
                     "is not installed.");
         }
+        if (mOutboundInputEventConsistencyVerifier != null) {
+            mOutboundInputEventConsistencyVerifier.onInputEvent(event, 0);
+        }
         mHost.sendInputEvent(event, policyFlags);
     }
 
@@ -201,6 +215,12 @@
             switch (msg.what) {
                 case MSG_INSTALL:
                     mHost = (Host)msg.obj;
+                    if (mInboundInputEventConsistencyVerifier != null) {
+                        mInboundInputEventConsistencyVerifier.reset();
+                    }
+                    if (mOutboundInputEventConsistencyVerifier != null) {
+                        mOutboundInputEventConsistencyVerifier.reset();
+                    }
                     onInstalled();
                     break;
 
@@ -215,6 +235,9 @@
                 case MSG_INPUT_EVENT: {
                     final InputEvent event = (InputEvent)msg.obj;
                     try {
+                        if (mInboundInputEventConsistencyVerifier != null) {
+                            mInboundInputEventConsistencyVerifier.onInputEvent(event, 0);
+                        }
                         onInputEvent(event, msg.arg1);
                     } finally {
                         event.recycle();