Revert "WindowList be gone!"

This reverts commit 4551c8bbee4114fa884938dbe90ac0d06ca78fc5.

Reason for revert: Broke a lot of things!

Bug: 33098800
Bug: 33098294
Change-Id: I307b1c7ee39445d6155a4bbce2bf5f289de55285
diff --git a/services/core/java/com/android/server/wm/AppWindowAnimator.java b/services/core/java/com/android/server/wm/AppWindowAnimator.java
index c42647e..e1b598a 100644
--- a/services/core/java/com/android/server/wm/AppWindowAnimator.java
+++ b/services/core/java/com/android/server/wm/AppWindowAnimator.java
@@ -411,7 +411,7 @@
         }
         if (mService.mInputMethodTarget != null
                 && mService.mInputMethodTarget.mAppToken == mAppToken) {
-            mAppToken.getDisplayContent().computeImeTarget(true /* updateImeTarget */);
+            mAppToken.getDisplayContent().moveInputMethodWindowsIfNeeded(true);
         }
 
         if (DEBUG_ANIM) Slog.v(TAG, "Animation done in " + mAppToken
diff --git a/services/core/java/com/android/server/wm/AppWindowToken.java b/services/core/java/com/android/server/wm/AppWindowToken.java
index 4569596..5d739d1 100644
--- a/services/core/java/com/android/server/wm/AppWindowToken.java
+++ b/services/core/java/com/android/server/wm/AppWindowToken.java
@@ -1006,7 +1006,10 @@
             tStartingWindow.mToken = this;
             tStartingWindow.mAppToken = this;
 
-            if (DEBUG_ADD_REMOVE || DEBUG_STARTING_WINDOW) Slog.v(TAG_WM,
+            if (DEBUG_WINDOW_MOVEMENT || DEBUG_ADD_REMOVE || DEBUG_STARTING_WINDOW) Slog.v(TAG_WM,
+                    "Removing starting window: " + tStartingWindow);
+            getDisplayContent().removeFromWindowList(tStartingWindow);
+            if (DEBUG_ADD_REMOVE) Slog.v(TAG_WM,
                     "Removing starting " + tStartingWindow + " from " + fromToken);
             fromToken.removeChild(tStartingWindow);
             fromToken.postWindowRemoveStartingWindowCleanup(tStartingWindow);
@@ -1256,6 +1259,18 @@
         }
     }
 
+    int rebuildWindowListUnchecked(int addIndex) {
+        return super.rebuildWindowList(addIndex);
+    }
+
+    @Override
+    int rebuildWindowList(int addIndex) {
+        if (mIsExiting && !waitingForReplacement()) {
+            return addIndex;
+        }
+        return rebuildWindowListUnchecked(addIndex);
+    }
+
     @Override
     boolean forAllWindows(ToBooleanFunction<WindowState> callback, boolean traverseTopToBottom) {
         // For legacy reasons we process the TaskStack.mExitingAppTokens first in DisplayContent
@@ -1317,32 +1332,6 @@
         mLastContainsShowWhenLockedWindow = containsShowWhenLocked;
     }
 
-    WindowState getImeTargetBelowWindow(WindowState w) {
-        final int index = mChildren.indexOf(w);
-        if (index > 0) {
-            final WindowState target = mChildren.get(index - 1);
-            if (target.canBeImeTarget()) {
-                return target;
-            }
-        }
-        return null;
-    }
-
-    WindowState getHighestAnimLayerWindow(WindowState currentTarget) {
-        WindowState candidate = null;
-        for (int i = mChildren.indexOf(currentTarget); i >= 0; i--) {
-            final WindowState w = mChildren.get(i);
-            if (w.mRemoved) {
-                continue;
-            }
-            if (candidate == null || w.mWinAnimator.mAnimLayer >
-                    candidate.mWinAnimator.mAnimLayer) {
-                candidate = w;
-            }
-        }
-        return candidate;
-    }
-
     @Override
     void dump(PrintWriter pw, String prefix) {
         super.dump(pw, prefix);
diff --git a/services/core/java/com/android/server/wm/DisplayContent.java b/services/core/java/com/android/server/wm/DisplayContent.java
index 24b9d69..e73acde 100644
--- a/services/core/java/com/android/server/wm/DisplayContent.java
+++ b/services/core/java/com/android/server/wm/DisplayContent.java
@@ -33,6 +33,10 @@
 import static android.view.WindowManager.DOCKED_BOTTOM;
 import static android.view.WindowManager.DOCKED_INVALID;
 import static android.view.WindowManager.DOCKED_TOP;
+import static android.view.WindowManager.INPUT_CONSUMER_NAVIGATION;
+import static android.view.WindowManager.INPUT_CONSUMER_PIP;
+import static android.view.WindowManager.INPUT_CONSUMER_WALLPAPER;
+import static android.view.WindowManager.LayoutParams.FLAG_ALT_FOCUSABLE_IM;
 import static android.view.WindowManager.LayoutParams.FLAG_NOT_FOCUSABLE;
 import static android.view.WindowManager.LayoutParams.FLAG_NOT_TOUCHABLE;
 import static android.view.WindowManager.LayoutParams.FLAG_NOT_TOUCH_MODAL;
@@ -40,10 +44,13 @@
 import static android.view.WindowManager.LayoutParams.FLAG_SHOW_WALLPAPER;
 import static android.view.WindowManager.LayoutParams.NEEDS_MENU_SET_TRUE;
 import static android.view.WindowManager.LayoutParams.NEEDS_MENU_UNSET;
+import static android.view.WindowManager.LayoutParams.PRIVATE_FLAG_DISABLE_WALLPAPER_TOUCH_EVENTS;
 import static android.view.WindowManager.LayoutParams.PRIVATE_FLAG_KEYGUARD;
 import static android.view.WindowManager.LayoutParams.TYPE_APPLICATION;
 import static android.view.WindowManager.LayoutParams.TYPE_APPLICATION_STARTING;
+import static android.view.WindowManager.LayoutParams.TYPE_BASE_APPLICATION;
 import static android.view.WindowManager.LayoutParams.TYPE_BOOT_PROGRESS;
+import static android.view.WindowManager.LayoutParams.TYPE_DOCK_DIVIDER;
 import static android.view.WindowManager.LayoutParams.TYPE_DRAWN_APPLICATION;
 import static android.view.WindowManager.LayoutParams.TYPE_DREAM;
 import static android.view.WindowManager.LayoutParams.TYPE_INPUT_METHOD;
@@ -57,6 +64,7 @@
 import static android.view.WindowManagerPolicy.FINISH_LAYOUT_REDO_CONFIG;
 import static android.view.WindowManagerPolicy.FINISH_LAYOUT_REDO_LAYOUT;
 import static android.view.WindowManagerPolicy.FINISH_LAYOUT_REDO_WALLPAPER;
+import static com.android.server.wm.WindowManagerDebugConfig.DEBUG_ADD_REMOVE;
 import static com.android.server.wm.WindowManagerDebugConfig.DEBUG_BOOT;
 import static com.android.server.wm.WindowManagerDebugConfig.DEBUG_DISPLAY;
 import static com.android.server.wm.WindowManagerDebugConfig.DEBUG_FOCUS;
@@ -69,8 +77,10 @@
 import static com.android.server.wm.WindowManagerDebugConfig.DEBUG_SCREENSHOT;
 import static com.android.server.wm.WindowManagerDebugConfig.DEBUG_SCREEN_ON;
 import static com.android.server.wm.WindowManagerDebugConfig.DEBUG_STACK;
+import static com.android.server.wm.WindowManagerDebugConfig.DEBUG_VISIBILITY;
 import static com.android.server.wm.WindowManagerDebugConfig.DEBUG_WALLPAPER;
 import static com.android.server.wm.WindowManagerDebugConfig.DEBUG_WALLPAPER_LIGHT;
+import static com.android.server.wm.WindowManagerDebugConfig.DEBUG_WINDOW_MOVEMENT;
 import static com.android.server.wm.WindowManagerDebugConfig.SHOW_STACK_CRAWLS;
 import static com.android.server.wm.WindowManagerDebugConfig.SHOW_TRANSACTIONS;
 import static com.android.server.wm.WindowManagerDebugConfig.TAG_WITH_CLASS_NAME;
@@ -84,6 +94,7 @@
 import static com.android.server.wm.WindowManagerService.UPDATE_FOCUS_WILL_PLACE_SURFACES;
 import static com.android.server.wm.WindowManagerService.WINDOWS_FREEZING_SCREENS_TIMEOUT;
 import static com.android.server.wm.WindowManagerService.dipToPixel;
+import static com.android.server.wm.WindowManagerService.localLOGV;
 import static com.android.server.wm.WindowManagerService.logSurface;
 import static com.android.server.wm.WindowState.RESIZE_HANDLE_WIDTH_IN_DP;
 import static com.android.server.wm.WindowStateAnimator.DRAW_PENDING;
@@ -109,21 +120,29 @@
 import android.util.Slog;
 import android.view.Display;
 import android.view.DisplayInfo;
+import android.view.IWindow;
+import android.view.InputChannel;
 import android.view.Surface;
 import android.view.SurfaceControl;
 import android.view.WindowManagerPolicy;
 
+import com.android.internal.util.FastPrintWriter;
 import com.android.internal.util.ToBooleanFunction;
 import com.android.internal.view.IInputMethodClient;
+import com.android.server.input.InputWindowHandle;
 
 import java.io.FileDescriptor;
 import java.io.PrintWriter;
+import java.io.StringWriter;
 import java.util.ArrayList;
+import java.util.Arrays;
 import java.util.Comparator;
 import java.util.HashMap;
 import java.util.Iterator;
 import java.util.LinkedList;
 import java.util.List;
+import java.util.function.Consumer;
+import java.util.function.Function;
 
 /**
  * Utility class for keeping track of the WindowStates and other pertinent contents of a
@@ -155,7 +174,8 @@
     private final NonAppWindowContainers mImeWindowsContainers =
             new NonAppWindowContainers("mImeWindowsContainers");
 
-    private WindowState mTmpWindow;
+    // Z-ordered (bottom-most first) list of all Window objects.
+    private final WindowList mWindows = new WindowList();
 
     // Mapping from a token IBinder to a WindowToken object on this display.
     private final HashMap<IBinder, WindowToken> mTokenMap = new HashMap();
@@ -212,19 +232,21 @@
 
     final ArrayList<WindowState> mTapExcludedWindows = new ArrayList<>();
 
-    private boolean mHaveBootMsg = false;
-    private boolean mHaveApp = false;
-    private boolean mHaveWallpaper = false;
-    private boolean mHaveKeyguard = true;
+    /** Used when rebuilding window list to keep track of windows that have been removed. */
+    private WindowState[] mRebuildTmp = new WindowState[20];
+
+    /**
+     * Temporary list for comparison. Always clear this after use so we don't end up with
+     * orphaned windows references
+     */
+    private final ArrayList<WindowState> mTmpWindows = new ArrayList<>();
 
     private final LinkedList<AppWindowToken> mTmpUpdateAllDrawn = new LinkedList();
 
     private final TaskForResizePointSearchResult mTmpTaskForResizePointSearchResult =
             new TaskForResizePointSearchResult();
-    private final ApplySurfaceChangesTransactionState mTmpApplySurfaceChangesTransactionState =
-            new ApplySurfaceChangesTransactionState();
-    private final ScreenshotApplicationState mScreenshotApplicationState =
-            new ScreenshotApplicationState();
+    private final GetWindowOnDisplaySearchResult mTmpGetWindowOnDisplaySearchResult =
+            new GetWindowOnDisplaySearchResult();
 
     // True if this display is in the process of being removed. Used to determine if the removal of
     // the display's direct children should be allowed.
@@ -433,13 +455,17 @@
     @Override
     void onAppTransitionDone() {
         super.onAppTransitionDone();
-        mService.mWindowsChanged = true;
+        rebuildAppWindowList();
     }
 
     @Override
     int getOrientation() {
         final WindowManagerPolicy policy = mService.mPolicy;
 
+        // TODO: All the logic before the last return statement in this method should really go in
+        // #NonAppWindowContainer.getOrientation() since it is trying to decide orientation based
+        // on non-app windows. But, we can not do that until the window list is always correct in
+        // terms of z-ordering based on layers.
         if (mService.mDisplayFrozen) {
             if (mService.mLastWindowForcedOrientation != SCREEN_ORIENTATION_UNSPECIFIED) {
                 if (DEBUG_ORIENTATION) Slog.v(TAG_WM,
@@ -460,9 +486,31 @@
                 return mService.mLastOrientation;
             }
         } else {
-            final int orientation = mAboveAppWindowsContainers.getOrientation();
-            if (orientation != SCREEN_ORIENTATION_UNSET) {
-                return orientation;
+            for (int pos = mWindows.size() - 1; pos >= 0; --pos) {
+                final WindowState win = mWindows.get(pos);
+                if (win.mAppToken != null) {
+                    // We hit an application window. so the orientation will be determined by the
+                    // app window. No point in continuing further.
+                    break;
+                }
+                if (!win.isVisibleLw() || !win.mPolicyVisibilityAfterAnim) {
+                    continue;
+                }
+                int req = win.mAttrs.screenOrientation;
+                if(req == SCREEN_ORIENTATION_UNSPECIFIED || req == SCREEN_ORIENTATION_BEHIND) {
+                    continue;
+                }
+
+                if (DEBUG_ORIENTATION) Slog.v(TAG_WM, win + " forcing orientation to " + req);
+                if (policy.isKeyguardHostWindow(win.mAttrs)) {
+                    mService.mLastKeyguardForcedOrientation = req;
+                }
+                return (mService.mLastWindowForcedOrientation = req);
+            }
+            mService.mLastWindowForcedOrientation = SCREEN_ORIENTATION_UNSPECIFIED;
+
+            if (policy.isKeyguardShowingAndNotOccluded()) {
+                return mService.mLastKeyguardForcedOrientation;
             }
         }
 
@@ -690,10 +738,22 @@
         }
     }
 
-    @Override
     void switchUser() {
-        super.switchUser();
-        mService.mWindowsChanged = true;
+        final int count = mWindows.size();
+        for (int i = 0; i < count; i++) {
+            final WindowState win = mWindows.get(i);
+            if (win.isHiddenFromUserLocked()) {
+                if (DEBUG_VISIBILITY) Slog.w(TAG_WM, "user changing, hiding " + win
+                        + ", attrs=" + win.mAttrs.type + ", belonging to " + win.mOwnerUid);
+                win.hideLw(false);
+            }
+        }
+
+        for (int stackNdx = mTaskStackContainers.size() - 1; stackNdx >= 0; --stackNdx) {
+            mTaskStackContainers.get(stackNdx).switchUser();
+        }
+
+        rebuildAppWindowList();
     }
 
     private void resetAnimationBackgroundAnimator() {
@@ -855,9 +915,19 @@
     void setInputMethodAnimLayerAdjustment(int adj) {
         if (DEBUG_LAYERS) Slog.v(TAG_WM, "Setting im layer adj to " + adj);
         mInputMethodAnimLayerAdjustment = adj;
-        mImeWindowsContainers.forAllWindows(w -> {
-            w.adjustAnimLayer(adj);
-        }, true /* traverseTopToBottom */);
+        final WindowState imw = mService.mInputMethodWindow;
+        if (imw != null) {
+            imw.adjustAnimLayer(adj);
+        }
+        for (int i = mService.mInputMethodDialogs.size() - 1; i >= 0; i--) {
+            final WindowState dialog = mService.mInputMethodDialogs.get(i);
+            // TODO: This and other places setting mAnimLayer can probably use WS.adjustAnimLayer,
+            // but need to make sure we are not setting things twice for child windows that are
+            // already in the list.
+            dialog.mWinAnimator.mAnimLayer = dialog.mLayer + adj;
+            if (DEBUG_LAYERS) Slog.v(TAG_WM, "IM win " + imw
+                    + " anim layer: " + dialog.mWinAnimator.mAnimLayer);
+        }
     }
 
     /**
@@ -866,11 +936,11 @@
      * suddenly disappear.
      */
     int getLayerForAnimationBackground(WindowStateAnimator winAnimator) {
-        final WindowState visibleWallpaper = mBelowAppWindowsContainers.getWindow(
-                w -> w.mIsWallpaper && w.isVisibleNow());
-
-        if (visibleWallpaper != null) {
-            return visibleWallpaper.mWinAnimator.mAnimLayer;
+        for (int i = mWindows.size() - 1; i >= 0; --i) {
+            final WindowState win = mWindows.get(i);
+            if (win.mIsWallpaper && win.isVisibleNow()) {
+                return win.mWinAnimator.mAnimLayer;
+            }
         }
         return winAnimator.mAnimLayer;
     }
@@ -1018,37 +1088,48 @@
 
     /** Find the visible, touch-deliverable window under the given point */
     WindowState getTouchableWinAtPointLocked(float xf, float yf) {
+        WindowState touchedWin = null;
         final int x = (int) xf;
         final int y = (int) yf;
-        final WindowState touchedWin = getWindow(w -> {
-            final int flags = w.mAttrs.flags;
-            if (!w.isVisibleLw()) {
-                return false;
+
+        for (int i = mWindows.size() - 1; i >= 0; i--) {
+            WindowState window = mWindows.get(i);
+            final int flags = window.mAttrs.flags;
+            if (!window.isVisibleLw()) {
+                continue;
             }
             if ((flags & FLAG_NOT_TOUCHABLE) != 0) {
-                return false;
+                continue;
             }
 
-            w.getVisibleBounds(mTmpRect);
+            window.getVisibleBounds(mTmpRect);
             if (!mTmpRect.contains(x, y)) {
-                return false;
+                continue;
             }
 
-            w.getTouchableRegion(mTmpRegion);
+            window.getTouchableRegion(mTmpRegion);
 
             final int touchFlags = flags & (FLAG_NOT_FOCUSABLE | FLAG_NOT_TOUCH_MODAL);
-            return mTmpRegion.contains(x, y) || touchFlags == 0;
-        });
+            if (mTmpRegion.contains(x, y) || touchFlags == 0) {
+                touchedWin = window;
+                break;
+            }
+        }
 
         return touchedWin;
     }
 
     boolean canAddToastWindowForUid(int uid) {
         // We allow one toast window per UID being shown at a time.
-        final WindowState win = getWindow(w ->
-                w.mAttrs.type == TYPE_TOAST && w.mOwnerUid == uid && !w.mPermanentlyHidden
-                && !w.mWindowRemovalAllowed);
-        return win == null;
+        final int windowCount = mWindows.size();
+        for (int i = 0; i < windowCount; i++) {
+            final WindowState window = mWindows.get(i);
+            if (window.mAttrs.type == TYPE_TOAST && window.mOwnerUid == uid
+                    && !window.mPermanentlyHidden && !window.mWindowRemovalAllowed) {
+                return false;
+            }
+        }
+        return true;
     }
 
     void scheduleToastWindowsTimeoutIfNeededLocked(WindowState oldFocus, WindowState newFocus) {
@@ -1056,76 +1137,268 @@
             return;
         }
         final int lostFocusUid = oldFocus.mOwnerUid;
+        final int windowCount = mWindows.size();
         final Handler handler = mService.mH;
-
-        forAllWindows(w -> {
-            if (w.mAttrs.type == TYPE_TOAST && w.mOwnerUid == lostFocusUid) {
-                if (!handler.hasMessages(WINDOW_HIDE_TIMEOUT, w)) {
-                    handler.sendMessageDelayed(handler.obtainMessage(WINDOW_HIDE_TIMEOUT, w),
-                            w.mAttrs.hideTimeoutMilliseconds);
+        for (int i = 0; i < windowCount; i++) {
+            final WindowState window = mWindows.get(i);
+            if (window.mAttrs.type == TYPE_TOAST && window.mOwnerUid == lostFocusUid) {
+                if (!handler.hasMessages(WINDOW_HIDE_TIMEOUT, window)) {
+                    handler.sendMessageDelayed(handler.obtainMessage(WINDOW_HIDE_TIMEOUT, window),
+                            window.mAttrs.hideTimeoutMilliseconds);
                 }
             }
-        }, false /* traverseTopToBottom */);
+        }
     }
 
     WindowState findFocusedWindow() {
         final AppWindowToken focusedApp = mService.mFocusedApp;
-        mTmpWindow = null;
 
-        forAllWindows(w -> {
-            if (DEBUG_FOCUS) Slog.v(TAG_WM, "Looking for focus: " + w
-                    + ", flags=" + w.mAttrs.flags + ", canReceive=" + w.canReceiveKeys());
+        for (int i = mWindows.size() - 1; i >= 0; i--) {
+            final WindowState win = mWindows.get(i);
 
-            if (!w.canReceiveKeys()) {
-                return false;
+            if (DEBUG_FOCUS) Slog.v(TAG_WM, "Looking for focus: " + i + " = " + win
+                    + ", flags=" + win.mAttrs.flags + ", canReceive=" + win.canReceiveKeys());
+
+            if (!win.canReceiveKeys()) {
+                continue;
             }
 
-            final AppWindowToken wtoken = w.mAppToken;
+            final AppWindowToken wtoken = win.mAppToken;
 
             // If this window's application has been removed, just skip it.
             if (wtoken != null && (wtoken.removed || wtoken.sendingToBottom)) {
                 if (DEBUG_FOCUS) Slog.v(TAG_WM, "Skipping " + wtoken + " because "
                         + (wtoken.removed ? "removed" : "sendingToBottom"));
-                return false;
+                continue;
             }
 
             if (focusedApp == null) {
                 if (DEBUG_FOCUS_LIGHT) Slog.v(TAG_WM, "findFocusedWindow: focusedApp=null"
-                        + " using new focus @ " + w);
-                mTmpWindow = w;
-                return true;
+                        + " using new focus @ " + i + " = " + win);
+                return win;
             }
 
             if (!focusedApp.windowsAreFocusable()) {
                 // Current focused app windows aren't focusable...
                 if (DEBUG_FOCUS_LIGHT) Slog.v(TAG_WM, "findFocusedWindow: focusedApp windows not"
-                        + " focusable using new focus @ " + w);
-                mTmpWindow = w;
-                return true;
+                        + " focusable using new focus @ " + i + " = " + win);
+                return win;
             }
 
             // Descend through all of the app tokens and find the first that either matches
             // win.mAppToken (return win) or mFocusedApp (return null).
-            if (wtoken != null && w.mAttrs.type != TYPE_APPLICATION_STARTING) {
+            if (wtoken != null && win.mAttrs.type != TYPE_APPLICATION_STARTING) {
                 if (focusedApp.compareTo(wtoken) > 0) {
                     // App stack below focused app stack. No focus for you!!!
                     if (DEBUG_FOCUS_LIGHT) Slog.v(TAG_WM,
                             "findFocusedWindow: Reached focused app=" + focusedApp);
-                    mTmpWindow = null;
-                    return true;
+                    return null;
                 }
             }
 
-            if (DEBUG_FOCUS_LIGHT) Slog.v(TAG_WM, "findFocusedWindow: Found new focus @ " + w);
-            mTmpWindow = w;
-            return true;
-        }, true /* traverseTopToBottom */);
-
-        if (mTmpWindow == null) {
-            if (DEBUG_FOCUS_LIGHT) Slog.v(TAG_WM, "findFocusedWindow: No focusable windows.");
-            return null;
+            if (DEBUG_FOCUS_LIGHT) Slog.v(TAG_WM, "findFocusedWindow: Found new focus @ "
+                    + i + " = " + win);
+            return win;
         }
-        return mTmpWindow;
+
+        if (DEBUG_FOCUS_LIGHT) Slog.v(TAG_WM, "findFocusedWindow: No focusable windows.");
+        return null;
+    }
+
+    void addAppWindowToWindowList(final WindowState win) {
+        final IWindow client = win.mClient;
+
+        WindowList tokenWindowList = getTokenWindowsOnDisplay(win.mToken);
+        if (!tokenWindowList.isEmpty()) {
+            addAppWindowExisting(win, tokenWindowList);
+            return;
+        }
+
+        // No windows from this token on this display
+        if (localLOGV) Slog.v(TAG_WM, "Figuring out where to add app window "
+                + client.asBinder() + " (token=" + this + ")");
+
+        final WindowToken wToken = win.mToken;
+
+        // Figure out where the window should go, based on the order of applications.
+        mTmpGetWindowOnDisplaySearchResult.reset();
+        for (int i = mTaskStackContainers.size() - 1; i >= 0; --i) {
+            final TaskStack stack = mTaskStackContainers.get(i);
+            stack.getWindowOnDisplayBeforeToken(this, wToken, mTmpGetWindowOnDisplaySearchResult);
+            if (mTmpGetWindowOnDisplaySearchResult.reachedToken) {
+                // We have reach the token we are interested in. End search.
+                break;
+            }
+        }
+
+        WindowState pos = mTmpGetWindowOnDisplaySearchResult.foundWindow;
+
+        // We now know the index into the apps. If we found an app window above, that gives us the
+        // position; else we need to look some more.
+        if (pos != null) {
+            // Move behind any windows attached to this one.
+            final WindowToken atoken = getWindowToken(pos.mClient.asBinder());
+            if (atoken != null) {
+                tokenWindowList = getTokenWindowsOnDisplay(atoken);
+                final int NC = tokenWindowList.size();
+                if (NC > 0) {
+                    WindowState bottom = tokenWindowList.get(0);
+                    if (bottom.mSubLayer < 0) {
+                        pos = bottom;
+                    }
+                }
+            }
+            addWindowToListBefore(win, pos);
+            return;
+        }
+
+        // Continue looking down until we find the first token that has windows on this display.
+        mTmpGetWindowOnDisplaySearchResult.reset();
+        for (int i = mTaskStackContainers.size() - 1; i >= 0; --i) {
+            final TaskStack stack = mTaskStackContainers.get(i);
+            stack.getWindowOnDisplayAfterToken(this, wToken, mTmpGetWindowOnDisplaySearchResult);
+            if (mTmpGetWindowOnDisplaySearchResult.foundWindow != null) {
+                // We have found a window after the token. End search.
+                break;
+            }
+        }
+
+        pos = mTmpGetWindowOnDisplaySearchResult.foundWindow;
+
+        if (pos != null) {
+            // Move in front of any windows attached to this one.
+            final WindowToken atoken = getWindowToken(pos.mClient.asBinder());
+            if (atoken != null) {
+                final WindowState top = atoken.getTopWindow();
+                if (top != null && top.mSubLayer >= 0) {
+                    pos = top;
+                }
+            }
+            addWindowToListAfter(win, pos);
+            return;
+        }
+
+        // Just search for the start of this layer.
+        final int myLayer = win.mBaseLayer;
+        int i;
+        for (i = mWindows.size() - 1; i >= 0; --i) {
+            final WindowState w = mWindows.get(i);
+            // Dock divider shares the base layer with application windows, but we want to always
+            // keep it above the application windows. The sharing of the base layer is intended
+            // for window animations, which need to be above the dock divider for the duration
+            // of the animation.
+            if (w.mBaseLayer <= myLayer && w.mAttrs.type != TYPE_DOCK_DIVIDER) {
+                break;
+            }
+        }
+        if (DEBUG_FOCUS || DEBUG_WINDOW_MOVEMENT || DEBUG_ADD_REMOVE) Slog.v(TAG_WM,
+                "Based on layer: Adding window " + win + " at " + (i + 1) + " of "
+                + mWindows.size());
+        mWindows.add(i + 1, win);
+        mService.mWindowsChanged = true;
+    }
+
+    /** Adds this non-app window to the window list. */
+    void addNonAppWindowToWindowList(WindowState win) {
+        // Figure out where window should go, based on layer.
+        int i;
+        for (i = mWindows.size() - 1; i >= 0; i--) {
+            final WindowState otherWin = mWindows.get(i);
+            if (otherWin.getBaseType() != TYPE_WALLPAPER && otherWin.mBaseLayer <= win.mBaseLayer) {
+                // Wallpaper wanders through the window list, for example to position itself
+                // directly behind keyguard. Because of this it will break the ordering based on
+                // WindowState.mBaseLayer. There might windows with higher mBaseLayer behind it and
+                // we don't want the new window to appear above them. An example of this is adding
+                // of the docked stack divider. Consider a scenario with the following ordering (top
+                // to bottom): keyguard, wallpaper, assist preview, apps. We want the dock divider
+                // to land below the assist preview, so the dock divider must ignore the wallpaper,
+                // with which it shares the base layer.
+                break;
+            }
+        }
+
+        i++;
+        if (DEBUG_FOCUS || DEBUG_WINDOW_MOVEMENT || DEBUG_ADD_REMOVE) Slog.v(TAG_WM,
+                "Free window: Adding window " + this + " at " + i + " of " + mWindows.size());
+        mWindows.add(i, win);
+        mService.mWindowsChanged = true;
+    }
+
+    void addToWindowList(WindowState win, int index) {
+        mService.mWindowsChanged = true;
+        mWindows.add(index, win);
+    }
+
+    boolean removeFromWindowList(WindowState win) {
+        mService.mWindowsChanged = true;
+        return mWindows.remove(win);
+    }
+
+    private int removeWindowAndChildrenFromWindowList(WindowState win, int interestingPos) {
+        int wpos = mWindows.indexOf(win);
+        if (wpos < 0) {
+            return interestingPos;
+        }
+
+        if (wpos < interestingPos) interestingPos--;
+        if (DEBUG_WINDOW_MOVEMENT) Slog.v(TAG_WM, "Temp removing at " + wpos + ": " + this);
+        mWindows.remove(wpos);
+        mService.mWindowsChanged = true;
+        int childWinCount = win.mChildren.size();
+        while (childWinCount > 0) {
+            childWinCount--;
+            final WindowState cw = win.mChildren.get(childWinCount);
+            int cpos = mWindows.indexOf(cw);
+            if (cpos >= 0) {
+                if (cpos < interestingPos) interestingPos--;
+                if (DEBUG_WINDOW_MOVEMENT) Slog.v(TAG_WM,
+                        "Temp removing child at " + cpos + ": " + cw);
+                mWindows.remove(cpos);
+            }
+        }
+        return interestingPos;
+    }
+
+    void addChildWindowToWindowList(WindowState win) {
+        final WindowState parentWindow = win.getParentWindow();
+
+        WindowList windowsOnSameDisplay = getTokenWindowsOnDisplay(win.mToken);
+
+        // Figure out this window's ordering relative to the parent window.
+        final int wCount = windowsOnSameDisplay.size();
+        final int sublayer = win.mSubLayer;
+        int largestSublayer = Integer.MIN_VALUE;
+        WindowState windowWithLargestSublayer = null;
+        int i;
+        for (i = 0; i < wCount; i++) {
+            WindowState w = windowsOnSameDisplay.get(i);
+            final int wSublayer = w.mSubLayer;
+            if (wSublayer >= largestSublayer) {
+                largestSublayer = wSublayer;
+                windowWithLargestSublayer = w;
+            }
+            if (sublayer < 0) {
+                // For negative sublayers, we go below all windows in the same sublayer.
+                if (wSublayer >= sublayer) {
+                    addWindowToListBefore(win, wSublayer >= 0 ? parentWindow : w);
+                    break;
+                }
+            } else {
+                // For positive sublayers, we go above all windows in the same sublayer.
+                if (wSublayer > sublayer) {
+                    addWindowToListBefore(win, w);
+                    break;
+                }
+            }
+        }
+        if (i >= wCount) {
+            if (sublayer < 0) {
+                addWindowToListBefore(win, parentWindow);
+            } else {
+                addWindowToListAfter(win,
+                        largestSublayer >= 0 ? windowWithLargestSublayer : parentWindow);
+            }
+        }
     }
 
     /** Updates the layer assignment of windows on this display. */
@@ -1136,9 +1409,136 @@
         }
     }
 
-    void layoutAndAssignWindowLayersIfNeeded() {
-        mService.mWindowsChanged = true;
-        setLayoutNeeded();
+    void adjustWallpaperWindows() {
+        mWallpaperController.adjustWallpaperWindows(this);
+    }
+
+    /**
+     * Z-orders the display window list so that:
+     * <ul>
+     * <li>Any windows that are currently below the wallpaper window stay below the wallpaper
+     *      window.
+     * <li>Exiting application windows are at the bottom, but above the wallpaper window.
+     * <li>All other application windows are above the exiting application windows and ordered based
+     *      on the ordering of their stacks and tasks on the display.
+     * <li>Non-application windows are at the very top.
+     * </ul>
+     * <p>
+     * NOTE: This isn't a complete picture of what the user see. Further manipulation of the window
+     *       surface layering is done in {@link WindowLayersController}.
+     */
+    void rebuildAppWindowList() {
+        int count = mWindows.size();
+        int i;
+        int lastBelow = -1;
+        int numRemoved = 0;
+
+        if (mRebuildTmp.length < count) {
+            mRebuildTmp = new WindowState[count + 10];
+        }
+
+        // First remove all existing app windows.
+        i = 0;
+        while (i < count) {
+            final WindowState w = mWindows.get(i);
+            if (w.mAppToken != null) {
+                final WindowState win = mWindows.remove(i);
+                win.mRebuilding = true;
+                mRebuildTmp[numRemoved] = win;
+                mService.mWindowsChanged = true;
+                if (DEBUG_WINDOW_MOVEMENT) Slog.v(TAG_WM, "Rebuild removing window: " + win);
+                count--;
+                numRemoved++;
+                continue;
+            } else if (lastBelow == i-1) {
+                if (w.mAttrs.type == TYPE_WALLPAPER) {
+                    lastBelow = i;
+                }
+            }
+            i++;
+        }
+
+        // Keep whatever windows were below the app windows still below, by skipping them.
+        lastBelow++;
+        i = lastBelow;
+
+        // First add all of the exiting app tokens...  these are no longer in the main app list,
+        // but still have windows shown. We put them in the back because now that the animation is
+        // over we no longer will care about them.
+        final int numStacks = mTaskStackContainers.size();
+        for (int stackNdx = 0; stackNdx < numStacks; ++stackNdx) {
+            AppTokenList exitingAppTokens = mTaskStackContainers.get(stackNdx).mExitingAppTokens;
+            int NT = exitingAppTokens.size();
+            for (int j = 0; j < NT; j++) {
+                i = exitingAppTokens.get(j).rebuildWindowListUnchecked(i);
+            }
+        }
+
+        // And add in the still active app tokens in Z order.
+        for (int stackNdx = 0; stackNdx < numStacks; ++stackNdx) {
+            i = mTaskStackContainers.get(stackNdx).rebuildWindowList(i);
+        }
+
+        i -= lastBelow;
+        if (i != numRemoved) {
+            setLayoutNeeded();
+            Slog.w(TAG_WM, "On display=" + mDisplayId + " Rebuild removed " + numRemoved
+                    + " windows but added " + i + " rebuildAppWindowListLocked() "
+                    + " callers=" + Debug.getCallers(10));
+            for (i = 0; i < numRemoved; i++) {
+                WindowState ws = mRebuildTmp[i];
+                if (ws.mRebuilding) {
+                    StringWriter sw = new StringWriter();
+                    PrintWriter pw = new FastPrintWriter(sw, false, 1024);
+                    ws.dump(pw, "", true);
+                    pw.flush();
+                    Slog.w(TAG_WM, "This window was lost: " + ws);
+                    Slog.w(TAG_WM, sw.toString());
+                    ws.mWinAnimator.destroySurfaceLocked();
+                }
+            }
+            Slog.w(TAG_WM, "Current window hierarchy:");
+            dumpChildrenNames();
+            Slog.w(TAG_WM, "Final window list:");
+            dumpWindows();
+        }
+        Arrays.fill(mRebuildTmp, null);
+    }
+
+    /** Rebuilds the display's window list and does a relayout if something changed. */
+    void rebuildAppWindowsAndLayoutIfNeeded() {
+        mTmpWindows.clear();
+        mTmpWindows.addAll(mWindows);
+
+        rebuildAppWindowList();
+
+        // Set displayContent.mLayoutNeeded if window order changed.
+        final int tmpSize = mTmpWindows.size();
+        final int winSize = mWindows.size();
+        int tmpNdx = 0, winNdx = 0;
+        while (tmpNdx < tmpSize && winNdx < winSize) {
+            // Skip over all exiting windows, they've been moved out of order.
+            WindowState tmp;
+            do {
+                tmp = mTmpWindows.get(tmpNdx++);
+            } while (tmpNdx < tmpSize && tmp.mAppToken != null && tmp.mAppToken.mIsExiting);
+
+            WindowState win;
+            do {
+                win = mWindows.get(winNdx++);
+            } while (winNdx < winSize && win.mAppToken != null && win.mAppToken.mIsExiting);
+
+            if (tmp != win) {
+                // Window order changed.
+                setLayoutNeeded();
+                break;
+            }
+        }
+        if (tmpNdx != winNdx) {
+            // One list was different from the other.
+            setLayoutNeeded();
+        }
+        mTmpWindows.clear();
 
         if (!mService.updateFocusedWindowLocked(UPDATE_FOCUS_WILL_PLACE_SURFACES,
                 false /*updateInputWindows*/)) {
@@ -1150,69 +1550,321 @@
         mService.mInputMonitor.updateInputWindowsLw(false /*force*/);
     }
 
+    void updateInputWindows(InputMonitor inputMonitor, WindowState inputFocus, boolean inDrag) {
+        final InputConsumerImpl navInputConsumer =
+                mService.mInputMonitor.getInputConsumer(INPUT_CONSUMER_NAVIGATION, mDisplayId);
+        final InputConsumerImpl pipInputConsumer =
+                mService.mInputMonitor.getInputConsumer(INPUT_CONSUMER_PIP, mDisplayId);
+        final InputConsumerImpl wallpaperInputConsumer =
+                mService.mInputMonitor.getInputConsumer(INPUT_CONSUMER_WALLPAPER, mDisplayId);
+        boolean addInputConsumerHandle = navInputConsumer != null;
+        boolean addPipInputConsumerHandle = pipInputConsumer != null;
+        boolean addWallpaperInputConsumerHandle = wallpaperInputConsumer != null;
+        final Rect pipTouchableBounds = addPipInputConsumerHandle ? new Rect() : null;
+        boolean disableWallpaperTouchEvents = false;
+
+        for (int winNdx = mWindows.size() - 1; winNdx >= 0; --winNdx) {
+            final WindowState child = mWindows.get(winNdx);
+            final InputChannel inputChannel = child.mInputChannel;
+            final InputWindowHandle inputWindowHandle = child.mInputWindowHandle;
+            if (inputChannel == null || inputWindowHandle == null || child.mRemoved
+                    || child.isAdjustedForMinimizedDock()) {
+                // Skip this window because it cannot possibly receive input.
+                continue;
+            }
+
+            if (addPipInputConsumerHandle
+                    && child.getStackId() == PINNED_STACK_ID
+                    && inputWindowHandle.layer <= pipInputConsumer.mWindowHandle.layer) {
+                // Update the bounds of the Pip input consumer to match the Pinned stack
+                child.getStack().getBounds(pipTouchableBounds);
+                pipInputConsumer.mWindowHandle.touchableRegion.set(pipTouchableBounds);
+                inputMonitor.addInputWindowHandle(pipInputConsumer.mWindowHandle);
+                addPipInputConsumerHandle = false;
+            }
+
+            if (addInputConsumerHandle
+                    && inputWindowHandle.layer <= navInputConsumer.mWindowHandle.layer) {
+                inputMonitor.addInputWindowHandle(navInputConsumer.mWindowHandle);
+                addInputConsumerHandle = false;
+            }
+
+            if (addWallpaperInputConsumerHandle) {
+                if (child.mAttrs.type == TYPE_WALLPAPER && child.isVisibleLw()) {
+                    // Add the wallpaper input consumer above the first visible wallpaper.
+                    inputMonitor.addInputWindowHandle(wallpaperInputConsumer.mWindowHandle);
+                    addWallpaperInputConsumerHandle = false;
+                }
+            }
+
+            final int flags = child.mAttrs.flags;
+            final int privateFlags = child.mAttrs.privateFlags;
+            final int type = child.mAttrs.type;
+
+            final boolean hasFocus = child == inputFocus;
+            final boolean isVisible = child.isVisibleLw();
+            if ((privateFlags & PRIVATE_FLAG_DISABLE_WALLPAPER_TOUCH_EVENTS) != 0) {
+                disableWallpaperTouchEvents = true;
+            }
+            final boolean hasWallpaper = mWallpaperController.isWallpaperTarget(child)
+                    && (privateFlags & PRIVATE_FLAG_KEYGUARD) == 0
+                    && !disableWallpaperTouchEvents;
+
+            // If there's a drag in progress and 'child' is a potential drop target,
+            // make sure it's been told about the drag
+            if (inDrag && isVisible && isDefaultDisplay) {
+                mService.mDragState.sendDragStartedIfNeededLw(child);
+            }
+
+            inputMonitor.addInputWindowHandle(
+                    inputWindowHandle, child, flags, type, isVisible, hasFocus, hasWallpaper);
+        }
+
+        if (addWallpaperInputConsumerHandle) {
+            // No visible wallpaper found, add the wallpaper input consumer at the end.
+            inputMonitor.addInputWindowHandle(wallpaperInputConsumer.mWindowHandle);
+        }
+    }
+
     /** Returns true if a leaked surface was destroyed */
     boolean destroyLeakedSurfaces() {
-        // Used to indicate that a surface was leaked.
-        mTmpWindow = null;
-        forAllWindows(w -> {
-            final WindowStateAnimator wsa = w.mWinAnimator;
+        boolean leakedSurface = false;
+        final int numWindows = mWindows.size();
+        for (int winNdx = 0; winNdx < numWindows; ++winNdx) {
+            final WindowState ws = mWindows.get(winNdx);
+            final WindowStateAnimator wsa = ws.mWinAnimator;
             if (wsa.mSurfaceController == null) {
-                return;
+                continue;
             }
             if (!mService.mSessions.contains(wsa.mSession)) {
                 Slog.w(TAG_WM, "LEAKED SURFACE (session doesn't exist): "
-                        + w + " surface=" + wsa.mSurfaceController
-                        + " token=" + w.mToken
-                        + " pid=" + w.mSession.mPid
-                        + " uid=" + w.mSession.mUid);
+                        + ws + " surface=" + wsa.mSurfaceController
+                        + " token=" + ws.mToken
+                        + " pid=" + ws.mSession.mPid
+                        + " uid=" + ws.mSession.mUid);
                 wsa.destroySurface();
-                mService.mForceRemoves.add(w);
-                mTmpWindow = w;
-            } else if (w.mAppToken != null && w.mAppToken.clientHidden) {
+                mService.mForceRemoves.add(ws);
+                leakedSurface = true;
+            } else if (ws.mAppToken != null && ws.mAppToken.clientHidden) {
                 Slog.w(TAG_WM, "LEAKED SURFACE (app token hidden): "
-                        + w + " surface=" + wsa.mSurfaceController
-                        + " token=" + w.mAppToken
-                        + " saved=" + w.hasSavedSurface());
-                if (SHOW_TRANSACTIONS) logSurface(w, "LEAK DESTROY", false);
+                        + ws + " surface=" + wsa.mSurfaceController
+                        + " token=" + ws.mAppToken
+                        + " saved=" + ws.hasSavedSurface());
+                if (SHOW_TRANSACTIONS) logSurface(ws, "LEAK DESTROY", false);
                 wsa.destroySurface();
-                mTmpWindow = w;
-            }
-        }, false /* traverseTopToBottom */);
-
-        return mTmpWindow != null;
-    }
-
-    /**
-     * Determine and return the window that should be the IME target.
-     * @param updateImeTarget If true the system IME target will be updated to match what we found.
-     * @return The window that should be used as the IME target or null if there isn't any.
-     */
-    WindowState computeImeTarget(boolean updateImeTarget) {
-        // TODO(multidisplay): Needs some serious rethought when the target and IME are not on the
-        // same display. Or even when the current IME/target are not on the same screen as the next
-        // IME/target. For now only look for input windows on the main screen.
-        WindowState target = getWindow(w -> {
-            if (DEBUG_INPUT_METHOD && updateImeTarget) Slog.i(TAG_WM, "Checking window @"
-                    + w + " fl=0x" + Integer.toHexString(w.mAttrs.flags));
-            return w.canBeImeTarget();
-        });
-
-
-        // Yet more tricksyness!  If this window is a "starting" window, we do actually want
-        // to be on top of it, but it is not -really- where input will go. So look down below
-        // for a real window to target...
-        if (target != null && target.mAttrs.type == TYPE_APPLICATION_STARTING) {
-            final AppWindowToken token = target.mAppToken;
-            if (token != null) {
-                final WindowState betterTarget = token.getImeTargetBelowWindow(target);
-                if (betterTarget != null) {
-                    target = betterTarget;
-                }
+                leakedSurface = true;
             }
         }
 
-        if (DEBUG_INPUT_METHOD && updateImeTarget) Slog.v(TAG_WM,
-                "Proposed new IME target: " + target);
+        return leakedSurface;
+    }
+
+    /** Return the list of Windows on this display associated with the input token. */
+    WindowList getTokenWindowsOnDisplay(WindowToken token) {
+        final WindowList windowList = new WindowList();
+        final int count = mWindows.size();
+        for (int i = 0; i < count; i++) {
+            final WindowState win = mWindows.get(i);
+            if (win.mToken == token) {
+                windowList.add(win);
+            }
+        }
+        return windowList;
+    }
+
+    private void reAddToWindowList(WindowState win) {
+        win.mToken.addWindow(win);
+        // This is a hack to get all of the child windows added as well at the right position. Child
+        // windows should be rare and this case should be rare, so it shouldn't be that big a deal.
+        int wpos = mWindows.indexOf(win);
+        if (wpos >= 0) {
+            if (DEBUG_WINDOW_MOVEMENT) Slog.v(TAG_WM, "ReAdd removing from " + wpos + ": " + win);
+            mWindows.remove(wpos);
+            mService.mWindowsChanged = true;
+            win.reAddWindow(wpos);
+        }
+    }
+
+    void moveInputMethodDialogs(int pos) {
+        ArrayList<WindowState> dialogs = mService.mInputMethodDialogs;
+
+        final int N = dialogs.size();
+        if (DEBUG_INPUT_METHOD) Slog.v(TAG_WM, "Removing " + N + " dialogs w/pos=" + pos);
+        for (int i = 0; i < N; i++) {
+            pos = removeWindowAndChildrenFromWindowList(dialogs.get(i), pos);
+        }
+        if (DEBUG_INPUT_METHOD) {
+            Slog.v(TAG_WM, "Window list w/pos=" + pos);
+            logWindowList(mWindows, "  ");
+        }
+
+        WindowState ime = mService.mInputMethodWindow;
+        if (pos >= 0) {
+            // Skip windows owned by the input method.
+            if (ime != null) {
+                while (pos < mWindows.size()) {
+                    WindowState wp = mWindows.get(pos);
+                    if (wp == ime || wp.getParentWindow() == ime) {
+                        pos++;
+                        continue;
+                    }
+                    break;
+                }
+            }
+            if (DEBUG_INPUT_METHOD) Slog.v(TAG_WM, "Adding " + N + " dialogs at pos=" + pos);
+            for (int i=0; i<N; i++) {
+                WindowState win = dialogs.get(i);
+                pos = win.reAddWindow(pos);
+            }
+            if (DEBUG_INPUT_METHOD) {
+                Slog.v(TAG_WM, "Final window list:");
+                logWindowList(mWindows, "  ");
+            }
+            return;
+        }
+        for (int i=0; i<N; i++) {
+            WindowState win = dialogs.get(i);
+            reAddToWindowList(win);
+            if (DEBUG_INPUT_METHOD) {
+                Slog.v(TAG_WM, "No IM target, final list:");
+                logWindowList(mWindows, "  ");
+            }
+        }
+    }
+
+    boolean moveInputMethodWindowsIfNeeded(boolean needAssignLayers) {
+        final WindowState imWin = mService.mInputMethodWindow;
+        final int DN = mService.mInputMethodDialogs.size();
+        if (imWin == null && DN == 0) {
+            return false;
+        }
+
+        // TODO(multidisplay): IMEs are only supported on the default display.
+        int imPos = findDesiredInputMethodWindowIndex(true);
+        if (imPos >= 0) {
+            // In this case, the input method windows are to be placed
+            // immediately above the window they are targeting.
+
+            // First check to see if the input method windows are already
+            // located here, and contiguous.
+            final int N = mWindows.size();
+            final WindowState firstImWin = imPos < N ? mWindows.get(imPos) : null;
+
+            // Figure out the actual input method window that should be
+            // at the bottom of their stack.
+            WindowState baseImWin = imWin != null ? imWin : mService.mInputMethodDialogs.get(0);
+            final WindowState cw = baseImWin.getBottomChild();
+            if (cw != null && cw.mSubLayer < 0) {
+                baseImWin = cw;
+            }
+
+            if (firstImWin == baseImWin) {
+                // The windows haven't moved...  but are they still contiguous?
+                // First find the top IM window.
+                int pos = imPos+1;
+                while (pos < N) {
+                    if (!(mWindows.get(pos)).mIsImWindow) {
+                        break;
+                    }
+                    pos++;
+                }
+                pos++;
+                // Now there should be no more input method windows above.
+                while (pos < N) {
+                    if ((mWindows.get(pos)).mIsImWindow) {
+                        break;
+                    }
+                    pos++;
+                }
+                if (pos >= N) {
+                    return false;
+                }
+            }
+
+            if (imWin != null) {
+                if (DEBUG_INPUT_METHOD) {
+                    Slog.v(TAG_WM, "Moving IM from " + imPos);
+                    logWindowList(mWindows, "  ");
+                }
+                imPos = removeWindowAndChildrenFromWindowList(imWin, imPos);
+                if (DEBUG_INPUT_METHOD) {
+                    Slog.v(TAG_WM, "List after removing with new pos " + imPos + ":");
+                    logWindowList(mWindows, "  ");
+                }
+                imWin.reAddWindow(imPos);
+                if (DEBUG_INPUT_METHOD) {
+                    Slog.v(TAG_WM, "List after moving IM to " + imPos + ":");
+                    logWindowList(mWindows, "  ");
+                }
+                if (DN > 0) moveInputMethodDialogs(imPos+1);
+            } else {
+                moveInputMethodDialogs(imPos);
+            }
+
+        } else {
+            // In this case, the input method windows go in a fixed layer,
+            // because they aren't currently associated with a focus window.
+
+            if (imWin != null) {
+                if (DEBUG_INPUT_METHOD) Slog.v(TAG_WM, "Moving IM from " + imPos);
+                removeWindowAndChildrenFromWindowList(imWin, 0);
+                reAddToWindowList(imWin);
+                if (DEBUG_INPUT_METHOD) {
+                    Slog.v(TAG_WM, "List with no IM target:");
+                    logWindowList(mWindows, "  ");
+                }
+                if (DN > 0) moveInputMethodDialogs(-1);
+            } else {
+                moveInputMethodDialogs(-1);
+            }
+
+        }
+
+        if (needAssignLayers) {
+            assignWindowLayers(false /* setLayoutNeeded */);
+        }
+
+        return true;
+    }
+
+    /**
+     * Dig through the WindowStates and find the one that the Input Method will target.
+     * @param willMove
+     * @return The index+1 in mWindows of the discovered target.
+     */
+    int findDesiredInputMethodWindowIndex(boolean willMove) {
+        // TODO(multidisplay): Needs some serious rethought when the target and IME are not on the
+        // same display. Or even when the current IME/target are not on the same screen as the next
+        // IME/target. For now only look for input windows on the main screen.
+        WindowState w = null;
+        int i;
+        for (i = mWindows.size() - 1; i >= 0; --i) {
+            final WindowState win = mWindows.get(i);
+
+            if (DEBUG_INPUT_METHOD && willMove) Slog.i(TAG_WM, "Checking window @" + i
+                    + " " + win + " fl=0x" + Integer.toHexString(win.mAttrs.flags));
+            if (canBeImeTarget(win)) {
+                w = win;
+                //Slog.i(TAG_WM, "Putting input method here!");
+
+                // Yet more tricksyness!  If this window is a "starting" window, we do actually want
+                // to be on top of it, but it is not -really- where input will go.  So if the caller
+                // is not actually looking to move the IME, look down below for a real window to
+                // target...
+                if (!willMove && w.mAttrs.type == TYPE_APPLICATION_STARTING && i > 0) {
+                    final WindowState wb = mWindows.get(i-1);
+                    if (wb.mAppToken == w.mAppToken && canBeImeTarget(wb)) {
+                        i--;
+                        w = wb;
+                    }
+                }
+                break;
+            }
+        }
+
+        // Now w is either mWindows[0] or an IME (or null if mWindows is empty).
+
+        if (DEBUG_INPUT_METHOD && willMove) Slog.v(TAG_WM, "Proposed new IME target: " + w);
 
         // Now, a special case -- if the last target's window is in the process of exiting, and is
         // above the new target, keep on the last target to avoid flicker. Consider for example a
@@ -1220,28 +1872,18 @@
         // until it is completely gone so it doesn't drop behind the dialog or its full-screen
         // scrim.
         final WindowState curTarget = mService.mInputMethodTarget;
-        if (curTarget != null && curTarget.isDisplayedLw() && curTarget.isClosing()
-                && (target == null
-                    || curTarget.mWinAnimator.mAnimLayer > target.mWinAnimator.mAnimLayer)) {
+        if (curTarget != null
+                && curTarget.isDisplayedLw()
+                && curTarget.isClosing()
+                && (w == null || curTarget.mWinAnimator.mAnimLayer > w.mWinAnimator.mAnimLayer)) {
             if (DEBUG_INPUT_METHOD) Slog.v(TAG_WM, "Current target higher, not changing");
-            return curTarget;
+            return mWindows.indexOf(curTarget) + 1;
         }
 
-        if (DEBUG_INPUT_METHOD) Slog.v(TAG_WM, "Desired input method target=" + target
-                + " updateImeTarget=" + updateImeTarget);
+        if (DEBUG_INPUT_METHOD) Slog.v(TAG_WM, "Desired input method target="
+                + w + " willMove=" + willMove);
 
-        if (target == null) {
-            if (updateImeTarget) {
-                if (DEBUG_INPUT_METHOD) Slog.w(TAG_WM, "Moving IM target from " + curTarget
-                        + " to null." + (SHOW_STACK_CRAWLS ? " Callers="
-                        + Debug.getCallers(4) : ""));
-                setInputMethodTarget(null, mService.mInputMethodTargetWaitingAnim, 0);
-            }
-
-            return null;
-        }
-
-        if (updateImeTarget) {
+        if (willMove && w != null) {
             AppWindowToken token = curTarget == null ? null : curTarget.mAppToken;
             if (token != null) {
 
@@ -1249,8 +1891,24 @@
                 // to look at all windows below the current target that are in this app, finding the
                 // highest visible one in layering.
                 WindowState highestTarget = null;
+                int highestPos = 0;
                 if (token.mAppAnimator.animating || token.mAppAnimator.animation != null) {
-                    highestTarget = token.getHighestAnimLayerWindow(curTarget);
+                    WindowList curWindows = token.getDisplayContent().mWindows;
+                    int pos = curWindows.indexOf(curTarget);
+                    while (pos >= 0) {
+                        WindowState win = curWindows.get(pos);
+                        if (win.mAppToken != token) {
+                            break;
+                        }
+                        if (!win.mRemoved) {
+                            if (highestTarget == null || win.mWinAnimator.mAnimLayer >
+                                    highestTarget.mWinAnimator.mAnimLayer) {
+                                highestTarget = win;
+                                highestPos = pos;
+                            }
+                        }
+                        pos--;
+                    }
                 }
 
                 if (highestTarget != null) {
@@ -1258,76 +1916,121 @@
                     if (DEBUG_INPUT_METHOD) Slog.v(TAG_WM, appTransition + " " + highestTarget
                             + " animating=" + highestTarget.mWinAnimator.isAnimationSet()
                             + " layer=" + highestTarget.mWinAnimator.mAnimLayer
-                            + " new layer=" + target.mWinAnimator.mAnimLayer);
+                            + " new layer=" + w.mWinAnimator.mAnimLayer);
 
                     if (appTransition.isTransitionSet()) {
                         // If we are currently setting up for an animation, hold everything until we
                         // can find out what will happen.
-                        setInputMethodTarget(highestTarget, true, mInputMethodAnimLayerAdjustment);
-                        return highestTarget;
+                        mService.mInputMethodTargetWaitingAnim = true;
+                        mService.mInputMethodTarget = highestTarget;
+                        return highestPos + 1;
                     } else if (highestTarget.mWinAnimator.isAnimationSet() &&
-                            highestTarget.mWinAnimator.mAnimLayer > target.mWinAnimator.mAnimLayer) {
+                            highestTarget.mWinAnimator.mAnimLayer > w.mWinAnimator.mAnimLayer) {
                         // If the window we are currently targeting is involved with an animation,
                         // and it is on top of the next target we will be over, then hold off on
                         // moving until that is done.
-                        setInputMethodTarget(highestTarget, true, mInputMethodAnimLayerAdjustment);
-                        return highestTarget;
+                        mService.mInputMethodTargetWaitingAnim = true;
+                        mService.mInputMethodTarget = highestTarget;
+                        return highestPos + 1;
                     }
                 }
             }
-
-            if (DEBUG_INPUT_METHOD) Slog.w(TAG_WM, "Moving IM target from " + curTarget + " to "
-                    + target + (SHOW_STACK_CRAWLS ? " Callers=" + Debug.getCallers(4) : ""));
-            setInputMethodTarget(target, false, target.mAppToken != null
-                    ? target.mAppToken.mAppAnimator.animLayerAdjustment : 0);
         }
 
-        return target;
-    }
-
-    private void setInputMethodTarget(WindowState target, boolean targetWaitingAnim, int layerAdj) {
-        if (target == mService.mInputMethodTarget
-                && mService.mInputMethodTargetWaitingAnim == targetWaitingAnim
-                && mInputMethodAnimLayerAdjustment == layerAdj) {
-            return;
-        }
-
-        mService.mInputMethodTarget = target;
-        mService.mInputMethodTargetWaitingAnim = targetWaitingAnim;
-        setInputMethodAnimLayerAdjustment(layerAdj);
-        assignWindowLayers(false /* setLayoutNeeded */);
-    }
-
-    boolean getNeedsMenu(WindowState top, WindowManagerPolicy.WindowState bottom) {
-        if (top.mAttrs.needsMenuKey != NEEDS_MENU_UNSET) {
-            return top.mAttrs.needsMenuKey == NEEDS_MENU_SET_TRUE;
-        }
-
-        // Used to indicate we have reached the first window in the range we are interested in.
-        mTmpWindow = null;
-
-        // TODO: Figure-out a more efficient way to do this.
-        final WindowState candidate = getWindow(w -> {
-            if (w == top) {
-                // Reached the first window in the range we are interested in.
-                mTmpWindow = w;
-            }
-            if (mTmpWindow == null) {
-                return false;
+        //Slog.i(TAG_WM, "Placing input method @" + (i+1));
+        if (w != null) {
+            if (willMove) {
+                if (DEBUG_INPUT_METHOD) Slog.w(TAG_WM, "Moving IM target from " + curTarget + " to "
+                        + w + (SHOW_STACK_CRAWLS ? " Callers=" + Debug.getCallers(4) : ""));
+                mService.mInputMethodTarget = w;
+                mService.mInputMethodTargetWaitingAnim = false;
+                if (w.mAppToken != null) {
+                    setInputMethodAnimLayerAdjustment(
+                            w.mAppToken.mAppAnimator.animLayerAdjustment);
+                } else {
+                    setInputMethodAnimLayerAdjustment(0);
+                }
             }
 
-            if (w.mAttrs.needsMenuKey != NEEDS_MENU_UNSET) {
-                return true;
+            // If the docked divider is visible, we still need to go through this whole excercise to
+            // find the appropriate input method target (used for animations and dialog
+            // adjustments), but for purposes of Z ordering we simply wish to place it above the
+            // docked divider. Unless it is already above the divider.
+            final WindowState dockedDivider = mDividerControllerLocked.getWindow();
+            if (dockedDivider != null && dockedDivider.isVisibleLw()) {
+                int dividerIndex = mWindows.indexOf(dockedDivider);
+                if (dividerIndex > 0 && dividerIndex > i) {
+                    return dividerIndex + 1;
+                }
+            }
+            return i+1;
+        }
+        if (willMove) {
+            if (DEBUG_INPUT_METHOD) Slog.w(TAG_WM, "Moving IM target from " + curTarget
+                    + " to null." + (SHOW_STACK_CRAWLS ? " Callers=" + Debug.getCallers(4) : ""));
+            mService.mInputMethodTarget = null;
+            setInputMethodAnimLayerAdjustment(0);
+        }
+        return -1;
+    }
+
+    private static boolean canBeImeTarget(WindowState w) {
+        final int fl = w.mAttrs.flags & (FLAG_NOT_FOCUSABLE|FLAG_ALT_FOCUSABLE_IM);
+        final int type = w.mAttrs.type;
+
+        if (fl != 0 && fl != (FLAG_NOT_FOCUSABLE | FLAG_ALT_FOCUSABLE_IM)
+                && type != TYPE_APPLICATION_STARTING) {
+            return false;
+        }
+
+        if (DEBUG_INPUT_METHOD) {
+            Slog.i(TAG_WM, "isVisibleOrAdding " + w + ": " + w.isVisibleOrAdding());
+            if (!w.isVisibleOrAdding()) {
+                Slog.i(TAG_WM, "  mSurfaceController=" + w.mWinAnimator.mSurfaceController
+                        + " relayoutCalled=" + w.mRelayoutCalled
+                        + " viewVis=" + w.mViewVisibility
+                        + " policyVis=" + w.mPolicyVisibility
+                        + " policyVisAfterAnim=" + w.mPolicyVisibilityAfterAnim
+                        + " parentHidden=" + w.isParentWindowHidden()
+                        + " exiting=" + w.mAnimatingExit + " destroying=" + w.mDestroying);
+                if (w.mAppToken != null) {
+                    Slog.i(TAG_WM, "  mAppToken.hiddenRequested=" + w.mAppToken.hiddenRequested);
+                }
+            }
+        }
+        return w.isVisibleOrAdding();
+    }
+
+    private void logWindowList(final WindowList windows, String prefix) {
+        int N = windows.size();
+        while (N > 0) {
+            N--;
+            Slog.v(TAG_WM, prefix + "#" + N + ": " + windows.get(N));
+        }
+    }
+
+    boolean getNeedsMenu(WindowState win, WindowManagerPolicy.WindowState bottom) {
+        int index = -1;
+        while (true) {
+            if (win.mAttrs.needsMenuKey != NEEDS_MENU_UNSET) {
+                return win.mAttrs.needsMenuKey == NEEDS_MENU_SET_TRUE;
             }
             // If we reached the bottom of the range of windows we are considering,
             // assume no menu is needed.
-            if (w == bottom) {
-                return true;
+            if (win == bottom) {
+                return false;
             }
-            return false;
-        });
-
-        return candidate != null && candidate.mAttrs.needsMenuKey == NEEDS_MENU_SET_TRUE;
+            // The current window hasn't specified whether menu key is needed; look behind it.
+            // First, we may need to determine the starting position.
+            if (index < 0) {
+                index = mWindows.indexOf(win);
+            }
+            index--;
+            if (index < 0) {
+                return false;
+            }
+            win = mWindows.get(index);
+        }
     }
 
     void setLayoutNeeded() {
@@ -1344,6 +2047,85 @@
         return mLayoutNeeded;
     }
 
+    private void addAppWindowExisting(WindowState win, WindowList tokenWindowList) {
+
+        // If this application has existing windows, we simply place the new window on top of
+        // them... but keep the starting window on top.
+        if (win.mAttrs.type == TYPE_BASE_APPLICATION) {
+            // Base windows go behind everything else.
+            final WindowState lowestWindow = tokenWindowList.get(0);
+            addWindowToListBefore(win, lowestWindow);
+        } else {
+            final AppWindowToken atoken = win.mAppToken;
+            final int windowListPos = tokenWindowList.size();
+            final WindowState lastWindow = tokenWindowList.get(windowListPos - 1);
+            if (atoken != null && lastWindow == atoken.startingWindow) {
+                addWindowToListBefore(win, lastWindow);
+            } else {
+                int newIdx = findIdxBasedOnAppTokens(win);
+                // There is a window above this one associated with the same apptoken note that the
+                // window could be a floating window that was created later or a window at the top
+                // of the list of windows associated with this token.
+                if (DEBUG_FOCUS || DEBUG_WINDOW_MOVEMENT || DEBUG_ADD_REMOVE) Slog.v(TAG_WM,
+                        "not Base app: Adding window " + win + " at " + (newIdx + 1) + " of "
+                                + mWindows.size());
+                mWindows.add(newIdx + 1, win);
+                mService.mWindowsChanged = true;
+            }
+        }
+    }
+
+    /** Places the first input window after the second input window in the window list. */
+    private void addWindowToListAfter(WindowState first, WindowState second) {
+        final int i = mWindows.indexOf(second);
+        if (DEBUG_FOCUS || DEBUG_WINDOW_MOVEMENT || DEBUG_ADD_REMOVE) Slog.v(TAG_WM,
+                "Adding window " + this + " at " + (i + 1) + " of " + mWindows.size()
+                + " (after " + second + ")");
+        mWindows.add(i + 1, first);
+        mService.mWindowsChanged = true;
+    }
+
+    /** Places the first input window before the second input window in the window list. */
+    private void addWindowToListBefore(WindowState first, WindowState second) {
+        int i = mWindows.indexOf(second);
+        if (DEBUG_FOCUS || DEBUG_WINDOW_MOVEMENT || DEBUG_ADD_REMOVE) Slog.v(TAG_WM,
+                "Adding window " + this + " at " + i + " of " + mWindows.size()
+                + " (before " + second + ")");
+        if (i < 0) {
+            Slog.w(TAG_WM, "addWindowToListBefore: Unable to find " + second + " in " + mWindows);
+            i = 0;
+        }
+        mWindows.add(i, first);
+        mService.mWindowsChanged = true;
+    }
+
+    /**
+     * This method finds out the index of a window that has the same app token as win. used for z
+     * ordering the windows in mWindows
+     */
+    private int findIdxBasedOnAppTokens(WindowState win) {
+        for(int j = mWindows.size() - 1; j >= 0; j--) {
+            final WindowState wentry = mWindows.get(j);
+            if(wentry.mAppToken == win.mAppToken) {
+                return j;
+            }
+        }
+        return -1;
+    }
+
+    private void dumpChildrenNames() {
+        StringBuilder output = new StringBuilder();
+        dumpChildrenNames(output, " ");
+        Slog.v(TAG_WM, output.toString());
+    }
+
+    private void dumpWindows() {
+        Slog.v(TAG_WM, " Display #" + mDisplayId);
+        for (int winNdx = mWindows.size() - 1; winNdx >= 0; --winNdx) {
+            Slog.v(TAG_WM, "  #" + winNdx + ": " + mWindows.get(winNdx));
+        }
+    }
+
     void dumpTokens(PrintWriter pw, boolean dumpAll) {
         if (mTokenMap.isEmpty()) {
             return;
@@ -1364,24 +2146,25 @@
     }
 
     void dumpWindowAnimators(PrintWriter pw, String subPrefix) {
-        final int[] index = new int[1];
-        forAllWindows(w -> {
-            final WindowStateAnimator wAnim = w.mWinAnimator;
-            pw.println(subPrefix + "Window #" + index[0] + ": " + wAnim);
-            index[0] = index[0] + 1;
-        }, false /* traverseTopToBottom */);
+        final int count = mWindows.size();
+        for (int j = 0; j < count; j++) {
+            final WindowStateAnimator wAnim = mWindows.get(j).mWinAnimator;
+            pw.println(subPrefix + "Window #" + j + ": " + wAnim);
+        }
     }
 
     void enableSurfaceTrace(FileDescriptor fd) {
-        forAllWindows(w -> {
-            w.mWinAnimator.enableSurfaceTrace(fd);
-        }, true /* traverseTopToBottom */);
+        for (int i = mWindows.size() - 1; i >= 0; i--) {
+            final WindowState win = mWindows.get(i);
+            win.mWinAnimator.enableSurfaceTrace(fd);
+        }
     }
 
     void disableSurfaceTrace() {
-        forAllWindows(w -> {
-            w.mWinAnimator.disableSurfaceTrace();
-        }, true /* traverseTopToBottom */);
+        for (int i = mWindows.size() - 1; i >= 0; i--) {
+            final WindowState win = mWindows.get(i);
+            win.mWinAnimator.disableSurfaceTrace();
+        }
     }
 
     /**
@@ -1389,68 +2172,63 @@
      */
     void startKeyguardExitOnNonAppWindows(boolean onWallpaper, boolean goingToShade) {
         final WindowManagerPolicy policy = mService.mPolicy;
-        forAllWindows(w -> {
-            if (w.mAppToken == null && policy.canBeHiddenByKeyguardLw(w)) {
-                w.mWinAnimator.setAnimation(
+        for (int i = mWindows.size() - 1; i >= 0; i--) {
+            final WindowState window = mWindows.get(i);
+            if (window.mAppToken == null && policy.canBeHiddenByKeyguardLw(window)) {
+                window.mWinAnimator.setAnimation(
                         policy.createHiddenByKeyguardExit(onWallpaper, goingToShade));
             }
-        }, true /* traverseTopToBottom */);
+        }
     }
 
     boolean checkWaitingForWindows() {
 
-        mHaveBootMsg = false;
-        mHaveApp = false;
-        mHaveWallpaper = false;
-        mHaveKeyguard = true;
-
-        final WindowState visibleWindow = getWindow(w -> {
+        boolean haveBootMsg = false;
+        boolean haveApp = false;
+        // if the wallpaper service is disabled on the device, we're never going to have
+        // wallpaper, don't bother waiting for it
+        boolean haveWallpaper = false;
+        boolean wallpaperEnabled = mService.mContext.getResources().getBoolean(
+                com.android.internal.R.bool.config_enableWallpaperService)
+                && !mService.mOnlyCore;
+        boolean haveKeyguard = true;
+        final int count = mWindows.size();
+        for (int i = 0; i < count; i++) {
+            final WindowState w = mWindows.get(i);
             if (w.isVisibleLw() && !w.mObscured && !w.isDrawnLw()) {
                 return true;
             }
             if (w.isDrawnLw()) {
                 if (w.mAttrs.type == TYPE_BOOT_PROGRESS) {
-                    mHaveBootMsg = true;
+                    haveBootMsg = true;
                 } else if (w.mAttrs.type == TYPE_APPLICATION
                         || w.mAttrs.type == TYPE_DRAWN_APPLICATION) {
-                    mHaveApp = true;
+                    haveApp = true;
                 } else if (w.mAttrs.type == TYPE_WALLPAPER) {
-                    mHaveWallpaper = true;
+                    haveWallpaper = true;
                 } else if (w.mAttrs.type == TYPE_STATUS_BAR) {
-                    mHaveKeyguard = mService.mPolicy.isKeyguardDrawnLw();
+                    haveKeyguard = mService.mPolicy.isKeyguardDrawnLw();
                 }
             }
-            return false;
-        });
-
-        if (visibleWindow != null) {
-            // We have a visible window.
-            return true;
         }
 
-        // if the wallpaper service is disabled on the device, we're never going to have
-        // wallpaper, don't bother waiting for it
-        boolean wallpaperEnabled = mService.mContext.getResources().getBoolean(
-                com.android.internal.R.bool.config_enableWallpaperService)
-                && !mService.mOnlyCore;
-
         if (DEBUG_SCREEN_ON || DEBUG_BOOT) Slog.i(TAG_WM,
                 "******** booted=" + mService.mSystemBooted
                 + " msg=" + mService.mShowingBootMessages
-                + " haveBoot=" + mHaveBootMsg + " haveApp=" + mHaveApp
-                + " haveWall=" + mHaveWallpaper + " wallEnabled=" + wallpaperEnabled
-                + " haveKeyguard=" + mHaveKeyguard);
+                + " haveBoot=" + haveBootMsg + " haveApp=" + haveApp
+                + " haveWall=" + haveWallpaper + " wallEnabled=" + wallpaperEnabled
+                + " haveKeyguard=" + haveKeyguard);
 
         // If we are turning on the screen to show the boot message, don't do it until the boot
         // message is actually displayed.
-        if (!mService.mSystemBooted && !mHaveBootMsg) {
+        if (!mService.mSystemBooted && !haveBootMsg) {
             return true;
         }
 
         // If we are turning on the screen after the boot is completed normally, don't do so until
         // we have the application and wallpaper.
-        if (mService.mSystemBooted
-                && ((!mHaveApp && !mHaveKeyguard) || (wallpaperEnabled && !mHaveWallpaper))) {
+        if (mService.mSystemBooted && ((!haveApp && !haveKeyguard) ||
+                (wallpaperEnabled && !haveWallpaper))) {
             return true;
         }
 
@@ -1458,8 +2236,10 @@
     }
 
     void updateWindowsForAnimator(WindowAnimator animator) {
-        forAllWindows(w -> {
-            WindowStateAnimator winAnimator = w.mWinAnimator;
+        final WallpaperController wallpaperController = mWallpaperController;
+        for (int i = mWindows.size() - 1; i >= 0; i--) {
+            WindowState win = mWindows.get(i);
+            WindowStateAnimator winAnimator = win.mWinAnimator;
             if (winAnimator.hasSurface()) {
                 final boolean wasAnimating = winAnimator.mWasAnimating;
                 final boolean nowAnimating = winAnimator.stepAnimationLocked(animator.mCurrentTime);
@@ -1467,10 +2247,10 @@
                 animator.orAnimating(nowAnimating);
 
                 if (DEBUG_WALLPAPER) Slog.v(TAG,
-                        w + ": wasAnimating=" + wasAnimating + ", nowAnimating=" + nowAnimating);
+                        win + ": wasAnimating=" + wasAnimating + ", nowAnimating=" + nowAnimating);
 
                 if (wasAnimating && !winAnimator.mAnimating
-                        && mWallpaperController.isWallpaperTarget(w)) {
+                        && wallpaperController.isWallpaperTarget(win)) {
                     animator.mBulkUpdateParams |= SET_WALLPAPER_MAY_CHANGE;
                     pendingLayoutChanges |= FINISH_LAYOUT_REDO_WALLPAPER;
                     if (DEBUG_LAYOUT_REPEATS) {
@@ -1480,10 +2260,10 @@
                 }
             }
 
-            final AppWindowToken atoken = w.mAppToken;
+            final AppWindowToken atoken = win.mAppToken;
             if (winAnimator.mDrawState == READY_TO_SHOW) {
                 if (atoken == null || atoken.allDrawn) {
-                    if (w.performShowLocked()) {
+                    if (win.performShowLocked()) {
                         pendingLayoutChanges |= FINISH_LAYOUT_REDO_ANIM;
                         if (DEBUG_LAYOUT_REPEATS) {
                             mService.mWindowPlacerLocked.debugLayoutRepeats(
@@ -1502,22 +2282,23 @@
                     appAnimator.thumbnailLayer = winAnimator.mAnimLayer;
                 }
             }
-        }, true /* traverseTopToBottom */);
+        } // end forall windows
     }
 
     void updateWallpaperForAnimator(WindowAnimator animator) {
         resetAnimationBackgroundAnimator();
 
-        // Used to indicate a detached wallpaper.
-        mTmpWindow = null;
+        final WindowList windows = mWindows;
+        WindowState detachedWallpaper = null;
 
-        forAllWindows(w -> {
-            final WindowStateAnimator winAnimator = w.mWinAnimator;
+        for (int i = windows.size() - 1; i >= 0; i--) {
+            final WindowState win = windows.get(i);
+            final WindowStateAnimator winAnimator = win.mWinAnimator;
             if (winAnimator.mSurfaceController == null || !winAnimator.hasSurface()) {
-                return;
+                continue;
             }
 
-            final int flags = w.mAttrs.flags;
+            final int flags = win.mAttrs.flags;
 
             // If this window is animating, make a note that we have an animating window and take
             // care of a request to run a detached wallpaper animation.
@@ -1525,11 +2306,11 @@
                 if (winAnimator.mAnimation != null) {
                     if ((flags & FLAG_SHOW_WALLPAPER) != 0
                             && winAnimator.mAnimation.getDetachWallpaper()) {
-                        mTmpWindow = w;
+                        detachedWallpaper = win;
                     }
                     final int color = winAnimator.mAnimation.getBackgroundColor();
                     if (color != 0) {
-                        final TaskStack stack = w.getStack();
+                        final TaskStack stack = win.getStack();
                         if (stack != null) {
                             stack.setAnimationBackground(winAnimator, color);
                         }
@@ -1545,45 +2326,64 @@
                     && appAnimator.animating) {
                 if ((flags & FLAG_SHOW_WALLPAPER) != 0
                         && appAnimator.animation.getDetachWallpaper()) {
-                    mTmpWindow = w;
+                    detachedWallpaper = win;
                 }
 
                 final int color = appAnimator.animation.getBackgroundColor();
                 if (color != 0) {
-                    final TaskStack stack = w.getStack();
+                    final TaskStack stack = win.getStack();
                     if (stack != null) {
                         stack.setAnimationBackground(winAnimator, color);
                     }
                 }
             }
-        }, true /* traverseTopToBottom */);
+        } // end forall windows
 
-        if (animator.mWindowDetachedWallpaper != mTmpWindow) {
+        if (animator.mWindowDetachedWallpaper != detachedWallpaper) {
             if (DEBUG_WALLPAPER) Slog.v(TAG, "Detached wallpaper changed from "
-                    + animator.mWindowDetachedWallpaper + " to " + mTmpWindow);
-            animator.mWindowDetachedWallpaper = mTmpWindow;
+                    + animator.mWindowDetachedWallpaper + " to " + detachedWallpaper);
+            animator.mWindowDetachedWallpaper = detachedWallpaper;
             animator.mBulkUpdateParams |= SET_WALLPAPER_MAY_CHANGE;
         }
     }
 
     void prepareWindowSurfaces() {
-        forAllWindows(w -> {
-            w.mWinAnimator.prepareSurfaceLocked(true);
-        }, false /* traverseTopToBottom */);
+        final int count = mWindows.size();
+        for (int j = 0; j < count; j++) {
+            mWindows.get(j).mWinAnimator.prepareSurfaceLocked(true);
+        }
     }
 
     boolean inputMethodClientHasFocus(IInputMethodClient client) {
-        final WindowState imFocus = computeImeTarget(false /* updateImeTarget */);
-        if (imFocus == null) {
+        // The focus for the client is the window immediately below where we would place the input
+        // method window.
+        int idx = findDesiredInputMethodWindowIndex(false);
+        if (idx <= 0) {
             return false;
         }
 
+        WindowState imFocus = mWindows.get(idx - 1);
         if (DEBUG_INPUT_METHOD) {
             Slog.i(TAG_WM, "Desired input method target: " + imFocus);
             Slog.i(TAG_WM, "Current focus: " + mService.mCurrentFocus);
             Slog.i(TAG_WM, "Last focus: " + mService.mLastFocus);
         }
 
+        if (imFocus == null) {
+            return false;
+        }
+
+        // This may be a starting window, in which case we still want to count it as okay.
+        if (imFocus.mAttrs.type == TYPE_APPLICATION_STARTING && imFocus.mAppToken != null) {
+            // The client has definitely started, so it really should have a window in this app
+            // token. Let's look for it.
+            final WindowState w = imFocus.mAppToken.getFirstNonStartingWindow();
+            if (w != null) {
+                if (DEBUG_INPUT_METHOD) Slog.i(TAG_WM, "Switching to real app window: " + w);
+                imFocus = w;
+            }
+        }
+
         final IInputMethodClient imeClient = imFocus.mSession.mClient;
 
         if (DEBUG_INPUT_METHOD) {
@@ -1598,63 +2398,75 @@
     }
 
     boolean hasSecureWindowOnScreen() {
-        final WindowState win = getWindow(
-                w -> w.isOnScreen() && (w.mAttrs.flags & FLAG_SECURE) != 0);
-        return win != null;
+        for (int i = mWindows.size() - 1; i >= 0; --i) {
+            final WindowState ws = mWindows.get(i);
+            if (ws.isOnScreen() && (ws.mAttrs.flags & FLAG_SECURE) != 0) {
+                return true;
+            }
+        }
+        return false;
     }
 
     void updateSystemUiVisibility(int visibility, int globalDiff) {
-        forAllWindows(w -> {
+        for (int i = mWindows.size() - 1; i >= 0; --i) {
+            final WindowState ws = mWindows.get(i);
             try {
-                final int curValue = w.mSystemUiVisibility;
-                final int diff = (curValue ^ visibility) & globalDiff;
-                final int newValue = (curValue & ~diff) | (visibility & diff);
+                int curValue = ws.mSystemUiVisibility;
+                int diff = (curValue ^ visibility) & globalDiff;
+                int newValue = (curValue & ~diff) | (visibility & diff);
                 if (newValue != curValue) {
-                    w.mSeq++;
-                    w.mSystemUiVisibility = newValue;
+                    ws.mSeq++;
+                    ws.mSystemUiVisibility = newValue;
                 }
-                if (newValue != curValue || w.mAttrs.hasSystemUiListeners) {
-                    w.mClient.dispatchSystemUiVisibilityChanged(w.mSeq,
+                if (newValue != curValue || ws.mAttrs.hasSystemUiListeners) {
+                    ws.mClient.dispatchSystemUiVisibilityChanged(ws.mSeq,
                             visibility, newValue, diff);
                 }
             } catch (RemoteException e) {
                 // so sorry
             }
-        }, true /* traverseTopToBottom */);
+        }
     }
 
     void onWindowFreezeTimeout() {
         Slog.w(TAG_WM, "Window freeze timeout expired.");
         mService.mWindowsFreezingScreen = WINDOWS_FREEZING_SCREENS_TIMEOUT;
-
-        forAllWindows(w -> {
+        for (int i = mWindows.size() - 1; i >= 0; --i) {
+            final WindowState w = mWindows.get(i);
             if (!w.mOrientationChanging) {
-                return;
+                continue;
             }
             w.mOrientationChanging = false;
             w.mLastFreezeDuration = (int)(SystemClock.elapsedRealtime()
                     - mService.mDisplayFreezeTime);
             Slog.w(TAG_WM, "Force clearing orientation change: " + w);
-        }, true /* traverseTopToBottom */);
+        }
         mService.mWindowPlacerLocked.performSurfacePlacement();
     }
 
     void waitForAllWindowsDrawn() {
         final WindowManagerPolicy policy = mService.mPolicy;
-        forAllWindows(w -> {
-            final boolean keyguard = policy.isKeyguardHostWindow(w.mAttrs);
-            if (w.isVisibleLw() && (w.mAppToken != null || keyguard)) {
-                w.mWinAnimator.mDrawState = DRAW_PENDING;
+        for (int winNdx = mWindows.size() - 1; winNdx >= 0; --winNdx) {
+            final WindowState win = mWindows.get(winNdx);
+            final boolean keyguard = policy.isKeyguardHostWindow(win.mAttrs);
+            if (win.isVisibleLw() && (win.mAppToken != null || keyguard)) {
+                win.mWinAnimator.mDrawState = DRAW_PENDING;
                 // Force add to mResizingWindows.
-                w.mLastContentInsets.set(-1, -1, -1, -1);
-                mService.mWaitingForDrawn.add(w);
+                win.mLastContentInsets.set(-1, -1, -1, -1);
+                mService.mWaitingForDrawn.add(win);
             }
-        }, true /* traverseTopToBottom */);
+        }
     }
 
     // TODO: Super crazy long method that should be broken down...
     boolean applySurfaceChangesTransaction(boolean recoveringMemory) {
 
+        boolean focusDisplayed = false;
+        boolean displayHasContent = false;
+        float preferredRefreshRate = 0;
+        int preferredModeId = 0;
+
+
         final int dw = mDisplayInfo.logicalWidth;
         final int dh = mDisplayInfo.logicalHeight;
         final WindowSurfacePlacer surfacePlacer = mService.mWindowPlacerLocked;
@@ -1678,7 +2490,7 @@
             // Remove check for default display when there will be support for multiple wallpaper
             // targets (on different displays).
             if (isDefaultDisplay && (pendingLayoutChanges & FINISH_LAYOUT_REDO_WALLPAPER) != 0) {
-                mWallpaperController.adjustWallpaperWindows(this);
+                adjustWallpaperWindows();
             }
 
             if (isDefaultDisplay && (pendingLayoutChanges & FINISH_LAYOUT_REDO_CONFIG) != 0) {
@@ -1705,59 +2517,55 @@
 
             if (isDefaultDisplay) {
                 mService.mPolicy.beginPostLayoutPolicyLw(dw, dh);
-                forAllWindows(w -> {
+                for (int i = mWindows.size() - 1; i >= 0; i--) {
+                    final WindowState w = mWindows.get(i);
                     mService.mPolicy.applyPostLayoutPolicyLw(w, w.mAttrs, w.getParentWindow(),
                             mService.mInputMethodTarget);
-                }, true /* traverseTopToBottom */);
+                }
                 pendingLayoutChanges |= mService.mPolicy.finishPostLayoutPolicyLw();
                 if (DEBUG_LAYOUT_REPEATS) surfacePlacer.debugLayoutRepeats(
                         "after finishPostLayoutPolicyLw", pendingLayoutChanges);
             }
         } while (pendingLayoutChanges != 0);
 
-        final RootWindowContainer root = mService.mRoot;
-        mTmpApplySurfaceChangesTransactionState.reset();
+        RootWindowContainer root = mService.mRoot;
+        boolean obscured = false;
+        boolean syswin = false;
         resetDimming();
 
         // Only used if default window
         final boolean someoneLosingFocus = !mService.mLosingFocus.isEmpty();
 
-        forAllWindows(w -> {
-            final boolean obscuredChanged = w.mObscured !=
-                    mTmpApplySurfaceChangesTransactionState.obscured;
+        for (int i = mWindows.size() - 1; i >= 0; i--) {
+            final WindowState w = mWindows.get(i);
+            final Task task = w.getTask();
+            final boolean obscuredChanged = w.mObscured != obscured;
 
             // Update effect.
-            w.mObscured = mTmpApplySurfaceChangesTransactionState.obscured;
-            if (!mTmpApplySurfaceChangesTransactionState.obscured) {
+            w.mObscured = obscured;
+            if (!obscured) {
                 final boolean isDisplayed = w.isDisplayedLw();
 
                 if (isDisplayed && w.isObscuringFullscreen(mDisplayInfo)) {
                     // This window completely covers everything behind it, so we want to leave all
                     // of them as undimmed (for performance reasons).
                     root.mObscuringWindow = w;
-                    mTmpApplySurfaceChangesTransactionState.obscured = true;
+                    obscured = true;
                 }
 
-                mTmpApplySurfaceChangesTransactionState.displayHasContent |=
-                        root.handleNotObscuredLocked(w,
-                                mTmpApplySurfaceChangesTransactionState.obscured,
-                                mTmpApplySurfaceChangesTransactionState.syswin);
+                displayHasContent |= root.handleNotObscuredLocked(w, obscured, syswin);
 
                 if (w.mHasSurface && isDisplayed) {
                     final int type = w.mAttrs.type;
                     if (type == TYPE_SYSTEM_DIALOG || type == TYPE_SYSTEM_ERROR
                             || (w.mAttrs.privateFlags & PRIVATE_FLAG_KEYGUARD) != 0) {
-                        mTmpApplySurfaceChangesTransactionState.syswin = true;
+                        syswin = true;
                     }
-                    if (mTmpApplySurfaceChangesTransactionState.preferredRefreshRate == 0
-                            && w.mAttrs.preferredRefreshRate != 0) {
-                        mTmpApplySurfaceChangesTransactionState.preferredRefreshRate
-                                = w.mAttrs.preferredRefreshRate;
+                    if (preferredRefreshRate == 0 && w.mAttrs.preferredRefreshRate != 0) {
+                        preferredRefreshRate = w.mAttrs.preferredRefreshRate;
                     }
-                    if (mTmpApplySurfaceChangesTransactionState.preferredModeId == 0
-                            && w.mAttrs.preferredDisplayModeId != 0) {
-                        mTmpApplySurfaceChangesTransactionState.preferredModeId
-                                = w.mAttrs.preferredDisplayModeId;
+                    if (preferredModeId == 0 && w.mAttrs.preferredDisplayModeId != 0) {
+                        preferredModeId = w.mAttrs.preferredDisplayModeId;
                     }
                 }
             }
@@ -1830,16 +2638,16 @@
 
             if (isDefaultDisplay && someoneLosingFocus && w == mService.mCurrentFocus
                     && w.isDisplayedLw()) {
-                mTmpApplySurfaceChangesTransactionState.focusDisplayed = true;
+                focusDisplayed = true;
             }
 
             w.updateResizingWindowIfNeeded();
-        }, true /* traverseTopToBottom */);
+        }
 
         mService.mDisplayManagerInternal.setDisplayProperties(mDisplayId,
-                mTmpApplySurfaceChangesTransactionState.displayHasContent,
-                mTmpApplySurfaceChangesTransactionState.preferredRefreshRate,
-                mTmpApplySurfaceChangesTransactionState.preferredModeId,
+                displayHasContent,
+                preferredRefreshRate,
+                preferredModeId,
                 true /* inTraversal, must call performTraversalInTrans... below */);
 
         stopDimmingIfNeeded();
@@ -1851,7 +2659,7 @@
             atoken.updateAllDrawn(this);
         }
 
-        return mTmpApplySurfaceChangesTransactionState.focusDisplayed;
+        return focusDisplayed;
     }
 
     void performLayout(boolean initial, boolean updateInputWindows) {
@@ -1884,110 +2692,110 @@
         if (seq < 0) seq = 0;
         mService.mLayoutSeq = seq;
 
-        // Used to indicate that we have processed the dream window and all additional windows are
-        // behind it.
-        mTmpWindow = null;
+        boolean behindDream = false;
 
         // First perform layout of any root windows (not attached to another window).
-        forAllWindows(w -> {
+        int topAttached = -1;
+        for (i = mWindows.size() - 1; i >= 0; i--) {
+            final WindowState win = mWindows.get(i);
+
             // Don't do layout of a window if it is not visible, or soon won't be visible, to avoid
             // wasting time and funky changes while a window is animating away.
-            final boolean gone = (mTmpWindow != null && mService.mPolicy.canBeHiddenByKeyguardLw(w))
-                    || w.isGoneForLayoutLw();
+            final boolean gone = (behindDream && mService.mPolicy.canBeHiddenByKeyguardLw(win))
+                    || win.isGoneForLayoutLw();
 
-            if (DEBUG_LAYOUT && !w.mLayoutAttached) {
-                Slog.v(TAG, "1ST PASS " + w + ": gone=" + gone + " mHaveFrame=" + w.mHaveFrame
-                        + " mLayoutAttached=" + w.mLayoutAttached
-                        + " screen changed=" + w.isConfigChanged());
-                final AppWindowToken atoken = w.mAppToken;
-                if (gone) Slog.v(TAG, "  GONE: mViewVisibility=" + w.mViewVisibility
-                        + " mRelayoutCalled=" + w.mRelayoutCalled + " hidden=" + w.mToken.hidden
+            if (DEBUG_LAYOUT && !win.mLayoutAttached) {
+                Slog.v(TAG, "1ST PASS " + win + ": gone=" + gone + " mHaveFrame=" + win.mHaveFrame
+                        + " mLayoutAttached=" + win.mLayoutAttached
+                        + " screen changed=" + win.isConfigChanged());
+                final AppWindowToken atoken = win.mAppToken;
+                if (gone) Slog.v(TAG, "  GONE: mViewVisibility=" + win.mViewVisibility
+                        + " mRelayoutCalled=" + win.mRelayoutCalled + " hidden=" + win.mToken.hidden
                         + " hiddenRequested=" + (atoken != null && atoken.hiddenRequested)
-                        + " parentHidden=" + w.isParentWindowHidden());
-                else Slog.v(TAG, "  VIS: mViewVisibility=" + w.mViewVisibility
-                        + " mRelayoutCalled=" + w.mRelayoutCalled + " hidden=" + w.mToken.hidden
+                        + " parentHidden=" + win.isParentWindowHidden());
+                else Slog.v(TAG, "  VIS: mViewVisibility=" + win.mViewVisibility
+                        + " mRelayoutCalled=" + win.mRelayoutCalled + " hidden=" + win.mToken.hidden
                         + " hiddenRequested=" + (atoken != null && atoken.hiddenRequested)
-                        + " parentHidden=" + w.isParentWindowHidden());
+                        + " parentHidden=" + win.isParentWindowHidden());
             }
 
             // If this view is GONE, then skip it -- keep the current frame, and let the caller know
             // so they can ignore it if they want.  (We do the normal layout for INVISIBLE windows,
             // since that means "perform layout as normal, just don't display").
-            if (!gone || !w.mHaveFrame || w.mLayoutNeeded
-                    || ((w.isConfigChanged() || w.setReportResizeHints())
-                    && !w.isGoneForLayoutLw() &&
-                    ((w.mAttrs.privateFlags & PRIVATE_FLAG_KEYGUARD) != 0 ||
-                            (w.mHasSurface && w.mAppToken != null &&
-                                    w.mAppToken.layoutConfigChanges)))) {
-                if (!w.mLayoutAttached) {
+            if (!gone || !win.mHaveFrame || win.mLayoutNeeded
+                    || ((win.isConfigChanged() || win.setReportResizeHints())
+                    && !win.isGoneForLayoutLw() &&
+                    ((win.mAttrs.privateFlags & PRIVATE_FLAG_KEYGUARD) != 0 ||
+                            (win.mHasSurface && win.mAppToken != null &&
+                                    win.mAppToken.layoutConfigChanges)))) {
+                if (!win.mLayoutAttached) {
                     if (initial) {
                         //Slog.i(TAG, "Window " + this + " clearing mContentChanged - initial");
-                        w.mContentChanged = false;
+                        win.mContentChanged = false;
                     }
-                    if (w.mAttrs.type == TYPE_DREAM) {
+                    if (win.mAttrs.type == TYPE_DREAM) {
                         // Don't layout windows behind a dream, so that if it does stuff like hide
                         // the status bar we won't get a bad transition when it goes away.
-                        mTmpWindow = w;
+                        behindDream = true;
                     }
-                    w.mLayoutNeeded = false;
-                    w.prelayout();
-                    mService.mPolicy.layoutWindowLw(w, null);
-                    w.mLayoutSeq = mService.mLayoutSeq;
+                    win.mLayoutNeeded = false;
+                    win.prelayout();
+                    mService.mPolicy.layoutWindowLw(win, null);
+                    win.mLayoutSeq = seq;
 
                     // Window frames may have changed. Update dim layer with the new bounds.
-                    final Task task = w.getTask();
+                    final Task task = win.getTask();
                     if (task != null) {
                         mDimLayerController.updateDimLayer(task);
                     }
 
-                    if (DEBUG_LAYOUT) Slog.v(TAG, "  LAYOUT: mFrame=" + w.mFrame
-                            + " mContainingFrame=" + w.mContainingFrame
-                            + " mDisplayFrame=" + w.mDisplayFrame);
+                    if (DEBUG_LAYOUT) Slog.v(TAG, "  LAYOUT: mFrame=" + win.mFrame
+                            + " mContainingFrame=" + win.mContainingFrame
+                            + " mDisplayFrame=" + win.mDisplayFrame);
+                } else {
+                    if (topAttached < 0) topAttached = i;
                 }
             }
-        }, true /* traverseTopToBottom */);
+        }
 
-        // Used to indicate that we have processed the dream window and all additional attached
-        // windows are behind it.
-        final WindowState dreamWin = mTmpWindow;
-        mTmpWindow = null;
+        boolean attachedBehindDream = false;
 
         // Now perform layout of attached windows, which usually depend on the position of the
         // window they are attached to. XXX does not deal with windows that are attached to windows
         // that are themselves attached.
-        forAllWindows(w -> {
-            if (w.mLayoutAttached) {
-                if (DEBUG_LAYOUT) Slog.v(TAG, "2ND PASS " + w + " mHaveFrame=" + w.mHaveFrame
-                        + " mViewVisibility=" + w.mViewVisibility
-                        + " mRelayoutCalled=" + w.mRelayoutCalled);
-                // If this view is GONE, then skip it -- keep the current frame, and let the
-                // caller know so they can ignore it if they want.  (We do the normal layout for
-                // INVISIBLE windows, since that means "perform layout as normal, just don't
-                // display").
-                if (mTmpWindow != null && mService.mPolicy.canBeHiddenByKeyguardLw(w)) {
-                    return;
+        for (i = topAttached; i >= 0; i--) {
+            final WindowState win = mWindows.get(i);
+
+            if (win.mLayoutAttached) {
+                if (DEBUG_LAYOUT) Slog.v(TAG, "2ND PASS " + win + " mHaveFrame=" + win.mHaveFrame
+                        + " mViewVisibility=" + win.mViewVisibility
+                        + " mRelayoutCalled=" + win.mRelayoutCalled);
+                // If this view is GONE, then skip it -- keep the current frame, and let the caller
+                // know so they can ignore it if they want.  (We do the normal layout for INVISIBLE
+                // windows, since that means "perform layout as normal, just don't display").
+                if (attachedBehindDream && mService.mPolicy.canBeHiddenByKeyguardLw(win)) {
+                    continue;
                 }
-                if ((w.mViewVisibility != GONE && w.mRelayoutCalled) || !w.mHaveFrame
-                        || w.mLayoutNeeded) {
+                if ((win.mViewVisibility != GONE && win.mRelayoutCalled) || !win.mHaveFrame
+                        || win.mLayoutNeeded) {
                     if (initial) {
                         //Slog.i(TAG, "Window " + this + " clearing mContentChanged - initial");
-                        w.mContentChanged = false;
+                        win.mContentChanged = false;
                     }
-                    w.mLayoutNeeded = false;
-                    w.prelayout();
-                    mService.mPolicy.layoutWindowLw(w, w.getParentWindow());
-                    w.mLayoutSeq = mService.mLayoutSeq;
-                    if (DEBUG_LAYOUT)
-                        Slog.v(TAG, "  LAYOUT: mFrame=" + w.mFrame
-                                + " mContainingFrame=" + w.mContainingFrame
-                                + " mDisplayFrame=" + w.mDisplayFrame);
+                    win.mLayoutNeeded = false;
+                    win.prelayout();
+                    mService.mPolicy.layoutWindowLw(win, win.getParentWindow());
+                    win.mLayoutSeq = seq;
+                    if (DEBUG_LAYOUT) Slog.v(TAG, "  LAYOUT: mFrame=" + win.mFrame
+                            + " mContainingFrame=" + win.mContainingFrame
+                            + " mDisplayFrame=" + win.mDisplayFrame);
                 }
-            } else if (w.mAttrs.type == TYPE_DREAM) {
+            } else if (win.mAttrs.type == TYPE_DREAM) {
                 // Don't layout windows behind a dream, so that if it does stuff like hide the
                 // status bar we won't get a bad transition when it goes away.
-                mTmpWindow = dreamWin;
+                attachedBehindDream = behindDream;
             }
-        }, true /* traverseTopToBottom */);
+        }
 
         // Window frames may have changed. Tell the input dispatcher about it.
         mService.mInputMonitor.layoutInputConsumers(dw, dh);
@@ -2011,7 +2819,7 @@
      * @param config of the output bitmap
      * @param wallpaperOnly true if only the wallpaper layer should be included in the screenshot
      */
-    Bitmap screenshotApplications(IBinder appToken, int width, int height,
+    Bitmap screenshotApplications(IBinder appToken, int displayId, int width, int height,
             boolean includeFullDisplay, float frameScale, Bitmap.Config config,
             boolean wallpaperOnly) {
         int dw = mDisplayInfo.logicalWidth;
@@ -2024,10 +2832,22 @@
 
         Bitmap bm = null;
 
-        mScreenshotApplicationState.reset(appToken == null && !wallpaperOnly);
+        int maxLayer = 0;
         final Rect frame = new Rect();
         final Rect stackBounds = new Rect();
 
+        boolean screenshotReady;
+        int minLayer;
+        if (appToken == null && !wallpaperOnly) {
+            screenshotReady = true;
+            minLayer = 0;
+        } else {
+            screenshotReady = false;
+            minLayer = Integer.MAX_VALUE;
+        }
+
+        WindowState appWin = null;
+
         boolean includeImeInScreenshot;
         synchronized(mService.mWindowMap) {
             final AppWindowToken imeTargetAppToken = mService.mInputMethodTarget != null
@@ -2048,69 +2868,70 @@
 
         synchronized(mService.mWindowMap) {
             // Figure out the part of the screen that is actually the app.
-            mScreenshotApplicationState.appWin = null;
-            forAllWindows(w -> {
-                if (!w.mHasSurface) {
-                    return false;
+            appWin = null;
+            for (int i = mWindows.size() - 1; i >= 0; i--) {
+                final WindowState ws = mWindows.get(i);
+                if (!ws.mHasSurface) {
+                    continue;
                 }
-                if (w.mLayer >= aboveAppLayer) {
-                    return false;
+                if (ws.mLayer >= aboveAppLayer) {
+                    continue;
                 }
-                if (wallpaperOnly && !w.mIsWallpaper) {
-                    return false;
+                if (wallpaperOnly && !ws.mIsWallpaper) {
+                    continue;
                 }
-                if (w.mIsImWindow) {
+                if (ws.mIsImWindow) {
                     if (!includeImeInScreenshot) {
-                        return false;
+                        continue;
                     }
-                } else if (w.mIsWallpaper) {
+                } else if (ws.mIsWallpaper) {
                     // If this is the wallpaper layer and we're only looking for the wallpaper layer
                     // then the target window state is this one.
                     if (wallpaperOnly) {
-                        mScreenshotApplicationState.appWin = w;
+                        appWin = ws;
                     }
 
-                    if (mScreenshotApplicationState.appWin == null) {
+                    if (appWin == null) {
                         // We have not ran across the target window yet, so it is probably behind
                         // the wallpaper. This can happen when the keyguard is up and all windows
                         // are moved behind the wallpaper. We don't want to include the wallpaper
                         // layer in the screenshot as it will cover-up the layer of the target
                         // window.
-                        return false;
+                        continue;
                     }
                     // Fall through. The target window is in front of the wallpaper. For this
                     // case we want to include the wallpaper layer in the screenshot because
                     // the target window might have some transparent areas.
                 } else if (appToken != null) {
-                    if (w.mAppToken == null || w.mAppToken.token != appToken) {
+                    if (ws.mAppToken == null || ws.mAppToken.token != appToken) {
                         // This app window is of no interest if it is not associated with the
                         // screenshot app.
-                        return false;
+                        continue;
                     }
-                    mScreenshotApplicationState.appWin = w;
+                    appWin = ws;
                 }
 
                 // Include this window.
 
-                final WindowStateAnimator winAnim = w.mWinAnimator;
+                final WindowStateAnimator winAnim = ws.mWinAnimator;
                 int layer = winAnim.mSurfaceController.getLayer();
-                if (mScreenshotApplicationState.maxLayer < layer) {
-                    mScreenshotApplicationState.maxLayer = layer;
+                if (maxLayer < layer) {
+                    maxLayer = layer;
                 }
-                if (mScreenshotApplicationState.minLayer > layer) {
-                    mScreenshotApplicationState.minLayer = layer;
+                if (minLayer > layer) {
+                    minLayer = layer;
                 }
 
                 // Don't include wallpaper in bounds calculation
-                if (!includeFullDisplay && !w.mIsWallpaper) {
-                    final Rect wf = w.mFrame;
-                    final Rect cr = w.mContentInsets;
+                if (!includeFullDisplay && !ws.mIsWallpaper) {
+                    final Rect wf = ws.mFrame;
+                    final Rect cr = ws.mContentInsets;
                     int left = wf.left + cr.left;
                     int top = wf.top + cr.top;
                     int right = wf.right - cr.right;
                     int bottom = wf.bottom - cr.bottom;
                     frame.union(left, top, right, bottom);
-                    w.getVisibleBounds(stackBounds);
+                    ws.getVisibleBounds(stackBounds);
                     if (!Rect.intersects(frame, stackBounds)) {
                         // Set frame empty if there's no intersection.
                         frame.setEmpty();
@@ -2118,22 +2939,16 @@
                 }
 
                 final boolean foundTargetWs =
-                        (w.mAppToken != null && w.mAppToken.token == appToken)
-                                || (mScreenshotApplicationState.appWin != null && wallpaperOnly);
-                if (foundTargetWs && w.isDisplayedLw() && winAnim.getShown()) {
-                    mScreenshotApplicationState.screenshotReady = true;
+                        (ws.mAppToken != null && ws.mAppToken.token == appToken)
+                                || (appWin != null && wallpaperOnly);
+                if (foundTargetWs && ws.isDisplayedLw() && winAnim.getShown()) {
+                    screenshotReady = true;
                 }
 
-                if (w.isObscuringFullscreen(mDisplayInfo)){
-                    return true;
+                if (ws.isObscuringFullscreen(mDisplayInfo)){
+                    break;
                 }
-                return false;
-            }, true /* traverseTopToBottom */);
-
-            final WindowState appWin = mScreenshotApplicationState.appWin;
-            final boolean screenshotReady = mScreenshotApplicationState.screenshotReady;
-            final int maxLayer = mScreenshotApplicationState.maxLayer;
-            final int minLayer = mScreenshotApplicationState.minLayer;
+            }
 
             if (appToken != null && appWin == null) {
                 // Can't find a window to snapshot.
@@ -2205,13 +3020,14 @@
             if (DEBUG_SCREENSHOT) {
                 Slog.i(TAG_WM, "Screenshot: " + dw + "x" + dh + " from " + minLayer + " to "
                         + maxLayer + " appToken=" + appToken);
-                forAllWindows(w -> {
-                    final WindowSurfaceController controller = w.mWinAnimator.mSurfaceController;
-                    Slog.i(TAG_WM, w + ": " + w.mLayer
-                            + " animLayer=" + w.mWinAnimator.mAnimLayer
+                for (int i = 0; i < mWindows.size(); i++) {
+                    final WindowState win = mWindows.get(i);
+                    final WindowSurfaceController controller = win.mWinAnimator.mSurfaceController;
+                    Slog.i(TAG_WM, win + ": " + win.mLayer
+                            + " animLayer=" + win.mWinAnimator.mAnimLayer
                             + " surfaceLayer=" + ((controller == null)
                             ? "null" : controller.getLayer()));
-                }, false /* traverseTopToBottom */);
+                }
             }
 
             final ScreenRotationAnimation screenRotationAnimation =
@@ -2248,9 +3064,6 @@
                 }
             }
             if (allBlack) {
-                final WindowState appWin = mScreenshotApplicationState.appWin;
-                final int maxLayer = mScreenshotApplicationState.maxLayer;
-                final int minLayer = mScreenshotApplicationState.minLayer;
                 Slog.i(TAG_WM, "Screenshot " + appWin + " was monochrome(" +
                         Integer.toHexString(firstColor) + ")! mSurfaceLayer=" +
                         (appWin != null ?
@@ -2291,23 +3104,32 @@
     }
 
     void onSeamlessRotationTimeout() {
-        // Used to indicate the layout is needed.
-        mTmpWindow = null;
-
-        forAllWindows(w -> {
+        boolean layoutNeeded = false;
+        for (int i = mWindows.size() - 1; i >= 0; i--) {
+            final WindowState w = mWindows.get(i);
             if (!w.mSeamlesslyRotated) {
-                return;
+                continue;
             }
-            mTmpWindow = w;
+            layoutNeeded = true;
             w.setDisplayLayoutNeeded();
             mService.markForSeamlessRotation(w, false);
-        }, true /* traverseTopToBottom */);
+        }
 
-        if (mTmpWindow != null) {
+        if (layoutNeeded) {
             mService.mWindowPlacerLocked.performSurfacePlacement();
         }
     }
 
+    static final class GetWindowOnDisplaySearchResult {
+        boolean reachedToken;
+        WindowState foundWindow;
+
+        void reset() {
+            reachedToken = false;
+            foundWindow = null;
+        }
+    }
+
     static final class TaskForResizePointSearchResult {
         boolean searchDone;
         Task taskForResize;
@@ -2318,39 +3140,6 @@
         }
     }
 
-    private static final class ApplySurfaceChangesTransactionState {
-        boolean displayHasContent;
-        boolean obscured;
-        boolean syswin;
-        boolean focusDisplayed;
-        float preferredRefreshRate;
-        int preferredModeId;
-
-        void reset() {
-            displayHasContent = false;
-            obscured = false;
-            syswin = false;
-            focusDisplayed = false;
-            preferredRefreshRate = 0;
-            preferredModeId = 0;
-        }
-    }
-
-    private static final class ScreenshotApplicationState {
-        WindowState appWin;
-        int maxLayer;
-        int minLayer;
-        boolean screenshotReady;
-
-        void reset(boolean screenshotReady) {
-            appWin = null;
-            maxLayer = 0;
-            minLayer = 0;
-            this.screenshotReady = screenshotReady;
-            minLayer = (screenshotReady) ? 0 : Integer.MAX_VALUE;
-        }
-    }
-
     /**
      * Base class for any direct child window container of {@link #DisplayContent} need to inherit
      * from. This is mainly a pass through class that allows {@link #DisplayContent} to have
@@ -2403,6 +3192,15 @@
         void removeStackFromDisplay(TaskStack stack) {
             removeChild(stack);
             stack.onRemovedFromDisplay();
+            // TODO: remove when window list will be gone.
+            // Manually remove records from window list and tap excluded windows list.
+            for (int i = mWindows.size() - 1; i >= 0; --i) {
+                final WindowState windowState = mWindows.get(i);
+                if (stack == windowState.getStack()) {
+                    mWindows.remove(i);
+                    mTapExcludedWindows.remove(windowState);
+                }
+            }
         }
 
         void moveStack(TaskStack stack, boolean toTop) {
@@ -2547,40 +3345,6 @@
         }
 
         @Override
-        int getOrientation() {
-            final WindowManagerPolicy policy = mService.mPolicy;
-            // Find a window requesting orientation.
-            final WindowState win = getWindow((w) -> {
-                if (!w.isVisibleLw() || !w.mPolicyVisibilityAfterAnim) {
-                    return false;
-                }
-                final int req = w.mAttrs.screenOrientation;
-                if(req == SCREEN_ORIENTATION_UNSPECIFIED || req == SCREEN_ORIENTATION_BEHIND
-                        || req == SCREEN_ORIENTATION_UNSET) {
-                    return false;
-                }
-                return true;
-            });
-
-            if (win != null) {
-                final int req = win.mAttrs.screenOrientation;
-                if (DEBUG_ORIENTATION) Slog.v(TAG_WM, win + " forcing orientation to " + req);
-                if (policy.isKeyguardHostWindow(win.mAttrs)) {
-                    mService.mLastKeyguardForcedOrientation = req;
-                }
-                return (mService.mLastWindowForcedOrientation = req);
-            }
-
-            mService.mLastWindowForcedOrientation = SCREEN_ORIENTATION_UNSPECIFIED;
-
-            if (policy.isKeyguardShowingAndNotOccluded()) {
-                return mService.mLastKeyguardForcedOrientation;
-            }
-
-            return SCREEN_ORIENTATION_UNSET;
-        }
-
-        @Override
         String getName() {
             return mName;
         }
diff --git a/services/core/java/com/android/server/wm/InputMonitor.java b/services/core/java/com/android/server/wm/InputMonitor.java
index 01d1c30..12c72e9 100644
--- a/services/core/java/com/android/server/wm/InputMonitor.java
+++ b/services/core/java/com/android/server/wm/InputMonitor.java
@@ -16,15 +16,10 @@
 
 package com.android.server.wm;
 
-import static android.app.ActivityManager.StackId.PINNED_STACK_ID;
 import static android.view.Display.DEFAULT_DISPLAY;
-import static android.view.WindowManager.INPUT_CONSUMER_NAVIGATION;
 import static android.view.WindowManager.INPUT_CONSUMER_PIP;
 import static android.view.WindowManager.INPUT_CONSUMER_WALLPAPER;
 import static android.view.WindowManager.LayoutParams.FLAG_NOT_TOUCH_MODAL;
-import static android.view.WindowManager.LayoutParams.PRIVATE_FLAG_DISABLE_WALLPAPER_TOUCH_EVENTS;
-import static android.view.WindowManager.LayoutParams.PRIVATE_FLAG_KEYGUARD;
-import static android.view.WindowManager.LayoutParams.TYPE_WALLPAPER;
 import static com.android.server.wm.WindowManagerDebugConfig.DEBUG_DRAG;
 import static com.android.server.wm.WindowManagerDebugConfig.DEBUG_FOCUS_LIGHT;
 import static com.android.server.wm.WindowManagerDebugConfig.DEBUG_INPUT;
@@ -75,10 +70,6 @@
     // Array of window handles to provide to the input dispatcher.
     private InputWindowHandle[] mInputWindowHandles;
     private int mInputWindowHandleCount;
-    private boolean mAddInputConsumerHandle;
-    private boolean mAddPipInputConsumerHandle;
-    private boolean mAddWallpaperInputConsumerHandle;
-    private boolean mDisableWallpaperTouchEvents;
 
     // Set to true when the first input device configuration change notification
     // is received to indicate that the input devices are ready.
@@ -332,12 +323,12 @@
         }
     }
 
-    void setUpdateInputWindowsNeededLw() {
+    public void setUpdateInputWindowsNeededLw() {
         mUpdateInputWindowsNeeded = true;
     }
 
     /* Updates the cached window information provided to the input dispatcher. */
-    void updateInputWindowsLw(boolean force) {
+    public void updateInputWindowsLw(boolean force) {
         if (!force && !mUpdateInputWindowsNeeded) {
             return;
         }
@@ -381,92 +372,15 @@
         }
 
         // Add all windows on the default display.
-        updateInputWindows(inDrag);
-
-        if (false) Slog.d(TAG_WM, "<<<<<<< EXITED updateInputWindowsLw");
-    }
-
-    private void updateInputWindows(boolean inDrag) {
-
-        clearInputWindowHandlesLw();
-
-        // TODO: multi-display
-        final InputConsumerImpl navInputConsumer =
-                getInputConsumer(INPUT_CONSUMER_NAVIGATION, DEFAULT_DISPLAY);
-        final InputConsumerImpl pipInputConsumer =
-                getInputConsumer(INPUT_CONSUMER_PIP, DEFAULT_DISPLAY);
-        final InputConsumerImpl wallpaperInputConsumer =
-                getInputConsumer(INPUT_CONSUMER_WALLPAPER, DEFAULT_DISPLAY);
-        mAddInputConsumerHandle = navInputConsumer != null;
-        mAddPipInputConsumerHandle = pipInputConsumer != null;
-        mAddWallpaperInputConsumerHandle = wallpaperInputConsumer != null;
-        final Rect pipTouchableBounds = mAddPipInputConsumerHandle ? new Rect() : null;
-        mDisableWallpaperTouchEvents = false;
-
-        final WallpaperController wallpaperController = mService.mRoot.mWallpaperController;
-        mService.mRoot.forAllWindows(w -> {
-            final InputChannel inputChannel = w.mInputChannel;
-            final InputWindowHandle inputWindowHandle = w.mInputWindowHandle;
-            if (inputChannel == null || inputWindowHandle == null || w.mRemoved
-                    || w.isAdjustedForMinimizedDock()) {
-                // Skip this window because it cannot possibly receive input.
-                return;
-            }
-
-            if (mAddPipInputConsumerHandle
-                    && w.getStackId() == PINNED_STACK_ID
-                    && inputWindowHandle.layer <= pipInputConsumer.mWindowHandle.layer) {
-                // Update the bounds of the Pip input consumer to match the Pinned stack
-                w.getStack().getBounds(pipTouchableBounds);
-                pipInputConsumer.mWindowHandle.touchableRegion.set(pipTouchableBounds);
-                addInputWindowHandle(pipInputConsumer.mWindowHandle);
-                mAddPipInputConsumerHandle = false;
-            }
-
-            if (mAddInputConsumerHandle
-                    && inputWindowHandle.layer <= navInputConsumer.mWindowHandle.layer) {
-                addInputWindowHandle(navInputConsumer.mWindowHandle);
-                mAddInputConsumerHandle = false;
-            }
-
-            if (mAddWallpaperInputConsumerHandle) {
-                if (w.mAttrs.type == TYPE_WALLPAPER && w.isVisibleLw()) {
-                    // Add the wallpaper input consumer above the first visible wallpaper.
-                    addInputWindowHandle(wallpaperInputConsumer.mWindowHandle);
-                    mAddWallpaperInputConsumerHandle = false;
-                }
-            }
-
-            final int flags = w.mAttrs.flags;
-            final int privateFlags = w.mAttrs.privateFlags;
-            final int type = w.mAttrs.type;
-
-            final boolean hasFocus = w == mInputFocus;
-            final boolean isVisible = w.isVisibleLw();
-            if ((privateFlags & PRIVATE_FLAG_DISABLE_WALLPAPER_TOUCH_EVENTS) != 0) {
-                mDisableWallpaperTouchEvents = true;
-            }
-            final boolean hasWallpaper = wallpaperController.isWallpaperTarget(w)
-                    && (privateFlags & PRIVATE_FLAG_KEYGUARD) == 0
-                    && !mDisableWallpaperTouchEvents;
-
-            // If there's a drag in progress and 'child' is a potential drop target,
-            // make sure it's been told about the drag
-            if (inDrag && isVisible && w.getDisplayContent().isDefaultDisplay) {
-                mService.mDragState.sendDragStartedIfNeededLw(w);
-            }
-
-            addInputWindowHandle(
-                    inputWindowHandle, w, flags, type, isVisible, hasFocus, hasWallpaper);
-        }, true /* traverseTopToBottom */);
-
-        if (mAddWallpaperInputConsumerHandle) {
-            // No visible wallpaper found, add the wallpaper input consumer at the end.
-            addInputWindowHandle(wallpaperInputConsumer.mWindowHandle);
-        }
+        mService.mRoot.updateInputWindows(this, mInputFocus, inDrag);
 
         // Send windows to native code.
         mService.mInputManager.setInputWindows(mInputWindowHandles);
+
+        // Clear the list in preparation for the next round.
+        clearInputWindowHandlesLw();
+
+        if (false) Slog.d(TAG_WM, "<<<<<<< EXITED updateInputWindowsLw");
     }
 
     /* Notifies that the input device configuration has changed. */
diff --git a/services/core/java/com/android/server/wm/RootWindowContainer.java b/services/core/java/com/android/server/wm/RootWindowContainer.java
index 1962ca7..88986e3 100644
--- a/services/core/java/com/android/server/wm/RootWindowContainer.java
+++ b/services/core/java/com/android/server/wm/RootWindowContainer.java
@@ -219,7 +219,7 @@
         return false;
     }
 
-    void getWindowsByName(ArrayList<WindowState> output, String name) {
+    void getWindowsByName(WindowList output, String name) {
         int objectId = 0;
         // See if this is an object ID.
         try {
@@ -231,7 +231,7 @@
         getWindowsByName(output, name, objectId);
     }
 
-    private void getWindowsByName(ArrayList<WindowState> output, String name, int objectId) {
+    private void getWindowsByName(WindowList output, String name, int objectId) {
         forAllWindows((w) -> {
             if (name != null) {
                 if (w.mAttrs.getTitle().toString().contains(name)) {
@@ -276,6 +276,15 @@
         return null;
     }
 
+    // TODO: Users would have their own window containers under the display container?
+    void switchUser() {
+        final int count = mChildren.size();
+        for (int i = 0; i < count; ++i) {
+            final DisplayContent dc = mChildren.get(i);
+            dc.switchUser();
+        }
+    }
+
     /**
      * Set new display override config and return array of ids of stacks that were changed during
      * update. If called for the default display, global configuration will also be updated.
@@ -420,6 +429,14 @@
         return hasChanges;
     }
 
+    void updateInputWindows(InputMonitor inputMonitor, WindowState inputFocus, boolean inDrag) {
+        final int count = mChildren.size();
+        for (int i = 0; i < count; ++i) {
+            final DisplayContent dc = mChildren.get(i);
+            dc.updateInputWindows(inputMonitor, inputFocus, inDrag);
+        }
+    }
+
     boolean reclaimSomeSurfaceMemory(WindowStateAnimator winAnimator, String operation,
             boolean secure) {
         final WindowSurfaceController surfaceController = winAnimator.mSurfaceController;
diff --git a/services/core/java/com/android/server/wm/Task.java b/services/core/java/com/android/server/wm/Task.java
index 772833c8..b889db2 100644
--- a/services/core/java/com/android/server/wm/Task.java
+++ b/services/core/java/com/android/server/wm/Task.java
@@ -589,6 +589,46 @@
         }
     }
 
+    void getWindowOnDisplayBeforeToken(DisplayContent dc, WindowToken token,
+            DisplayContent.GetWindowOnDisplaySearchResult result) {
+        for (int i = mChildren.size() - 1; i >= 0; --i) {
+            final AppWindowToken current = mChildren.get(i);
+            if (current == token) {
+                // We have reach the token we are interested in. End search.
+                result.reachedToken = true;
+                return;
+            }
+
+            // We haven't reached the token yet; if this token is not going to the bottom and
+            // has windows on this display, then it is a candidate for what we are looking for.
+            final WindowList tokenWindowList = dc.getTokenWindowsOnDisplay(current);
+            if (!current.sendingToBottom && tokenWindowList.size() > 0) {
+                result.foundWindow = tokenWindowList.get(0);
+            }
+        }
+    }
+
+    void getWindowOnDisplayAfterToken(DisplayContent dc, WindowToken token,
+            DisplayContent.GetWindowOnDisplaySearchResult result) {
+        for (int i = mChildren.size() - 1; i >= 0; --i) {
+            final AppWindowToken current = mChildren.get(i);
+            if (!result.reachedToken) {
+                if (current == token) {
+                    // We have reached the token we are interested in. Get whichever window occurs
+                    // after it that is on the same display.
+                    result.reachedToken = true;
+                }
+                continue;
+            }
+
+            final WindowList tokenWindowList = dc.getTokenWindowsOnDisplay(current);
+            if (tokenWindowList.size() > 0) {
+                result.foundWindow = tokenWindowList.get(tokenWindowList.size() - 1);
+                return;
+            }
+        }
+    }
+
     @Override
     boolean fillsParent() {
         return mFillsParent || !StackId.isTaskResizeAllowed(mStack.mStackId);
diff --git a/services/core/java/com/android/server/wm/TaskStack.java b/services/core/java/com/android/server/wm/TaskStack.java
index f2c74df..203ba72 100644
--- a/services/core/java/com/android/server/wm/TaskStack.java
+++ b/services/core/java/com/android/server/wm/TaskStack.java
@@ -859,9 +859,7 @@
     }
 
     // TODO: Should each user have there own stacks?
-    @Override
     void switchUser() {
-        super.switchUser();
         int top = mChildren.size();
         for (int taskNdx = 0; taskNdx < top; ++taskNdx) {
             Task task = mChildren.get(taskNdx);
@@ -1490,6 +1488,30 @@
         }
     }
 
+    void getWindowOnDisplayBeforeToken(DisplayContent dc, WindowToken token,
+            DisplayContent.GetWindowOnDisplaySearchResult result) {
+        for (int i = mChildren.size() - 1; i >= 0; --i) {
+            final Task task = mChildren.get(i);
+            task.getWindowOnDisplayBeforeToken(dc, token, result);
+            if (result.reachedToken) {
+                // We have reach the token we are interested in. End search.
+                return;
+            }
+        }
+    }
+
+    void getWindowOnDisplayAfterToken(DisplayContent dc, WindowToken token,
+            DisplayContent.GetWindowOnDisplaySearchResult result) {
+        for (int i = mChildren.size() - 1; i >= 0; --i) {
+            final Task task = mChildren.get(i);
+            task.getWindowOnDisplayAfterToken(dc, token, result);
+            if (result.foundWindow != null) {
+                // We have found a window after the token. End search.
+                return;
+            }
+        }
+    }
+
     @Override
     int getOrientation() {
         return (StackId.canSpecifyOrientation(mStackId))
diff --git a/services/core/java/com/android/server/wm/WallpaperController.java b/services/core/java/com/android/server/wm/WallpaperController.java
index 7fd8028..8dbf2b3 100644
--- a/services/core/java/com/android/server/wm/WallpaperController.java
+++ b/services/core/java/com/android/server/wm/WallpaperController.java
@@ -683,6 +683,24 @@
         }
     }
 
+    void dumpTokens(PrintWriter pw, String prefix, boolean dumpAll) {
+        if (!mWallpaperTokens.isEmpty()) {
+            pw.println();
+            pw.print(prefix); pw.println("Wallpaper tokens:");
+            for (int i = mWallpaperTokens.size() - 1; i >= 0; i--) {
+                WindowToken token = mWallpaperTokens.get(i);
+                pw.print(prefix); pw.print("Wallpaper #"); pw.print(i);
+                pw.print(' '); pw.print(token);
+                if (dumpAll) {
+                    pw.println(':');
+                    token.dump(pw, "    ");
+                } else {
+                    pw.println();
+                }
+            }
+        }
+    }
+
     /** Helper class for storing the results of a wallpaper target find operation. */
     final private static class FindWallpaperTargetResult {
         WindowState topWallpaper = null;
diff --git a/services/core/java/com/android/server/wm/WindowContainer.java b/services/core/java/com/android/server/wm/WindowContainer.java
index f5db0b6..a6a907c 100644
--- a/services/core/java/com/android/server/wm/WindowContainer.java
+++ b/services/core/java/com/android/server/wm/WindowContainer.java
@@ -18,6 +18,7 @@
 
 import android.annotation.CallSuper;
 import android.content.res.Configuration;
+import android.view.animation.Animation;
 import com.android.internal.util.ToBooleanFunction;
 
 import java.util.Comparator;
@@ -482,11 +483,19 @@
         return false;
     }
 
-    // TODO: Users would have their own window containers under the display container?
-    void switchUser() {
-        for (int i = mChildren.size() - 1; i >= 0; --i) {
-            mChildren.get(i).switchUser();
+    /**
+     * Rebuilds the WindowList for the input display content.
+     * @param addIndex The index in the window list to add the next entry to.
+     * @return The next index in the window list to.
+     */
+    // TODO: Hoping we can get rid of WindowList so this method wouldn't be needed.
+    int rebuildWindowList(int addIndex) {
+        final int count = mChildren.size();
+        for (int i = 0; i < count; i++) {
+            final WindowContainer wc = mChildren.get(i);
+            addIndex = wc.rebuildWindowList(addIndex);
         }
+        return addIndex;
     }
 
     /**
diff --git a/services/core/java/com/android/server/wm/WindowManagerService.java b/services/core/java/com/android/server/wm/WindowManagerService.java
index 507679b..00d8fba 100644
--- a/services/core/java/com/android/server/wm/WindowManagerService.java
+++ b/services/core/java/com/android/server/wm/WindowManagerService.java
@@ -606,6 +606,17 @@
     boolean mInputMethodTargetWaitingAnim;
 
     WindowState mInputMethodWindow = null;
+    // TODO: Remove with extreme prejudice! This list is maintained so that we can keep track of
+    // dialogs that should go on top of the IME so they can be re-arranged in the window list any
+    // time the IME changes position in the window list. Normally you would have a dialog be a child
+    // window of the IME, but they don't share the same token since they are added by different
+    // clients. This doesn't really affect what the user sees on screen since this dialogs have an
+    // higher base layer than the IME window, but it will affect users of the window list that
+    // expect the list to represent the order of things on-screen (e.g input service). This makes
+    // the code for managing the window list hard to follow (see all the places it is used).
+    // We can remove the use of this field when we automatically assign layers and z-order the
+    // window list before it is used whenever window container order changes.
+    final ArrayList<WindowState> mInputMethodDialogs = new ArrayList<>();
 
     boolean mHardKeyboardAvailable;
     WindowManagerInternal.OnHardKeyboardStatusChangeListener mHardKeyboardStatusChangeListener;
@@ -1366,16 +1377,19 @@
 
             boolean imMayMove = true;
 
-            win.mToken.addWindow(win);
             if (type == TYPE_INPUT_METHOD) {
                 win.mGivenInsetsPending = true;
                 mInputMethodWindow = win;
-                displayContent.computeImeTarget(true /* updateImeTarget */);
+                win.mToken.addImeWindow(win);
                 imMayMove = false;
             } else if (type == TYPE_INPUT_METHOD_DIALOG) {
-                displayContent.computeImeTarget(true /* updateImeTarget */);
+                mInputMethodDialogs.add(win);
+                win.mToken.addWindow(win);
+                displayContent.moveInputMethodDialogs(
+                        displayContent.findDesiredInputMethodWindowIndex(true));
                 imMayMove = false;
             } else {
+                win.mToken.addWindow(win);
                 if (type == TYPE_WALLPAPER) {
                     displayContent.mWallpaperController.clearLastWallpaperTimeoutTime();
                     displayContent.pendingLayoutChanges |= FINISH_LAYOUT_REDO_WALLPAPER;
@@ -1448,7 +1462,7 @@
             }
 
             if (imMayMove) {
-                displayContent.computeImeTarget(true /* updateImeTarget */);
+                displayContent.moveInputMethodWindowsIfNeeded(false);
             }
 
             // Don't do layout here, the window must call
@@ -1632,6 +1646,8 @@
 
         if (mInputMethodWindow == win) {
             mInputMethodWindow = null;
+        } else if (win.mAttrs.type == TYPE_INPUT_METHOD_DIALOG) {
+            mInputMethodDialogs.remove(win);
         }
 
         final WindowToken token = win.mToken;
@@ -1661,11 +1677,13 @@
             dc.pendingLayoutChanges |= FINISH_LAYOUT_REDO_WALLPAPER;
         }
 
-        if (dc != null && !mWindowPlacerLocked.isInLayout()) {
-            dc.assignWindowLayers(true /* setLayoutNeeded */);
-            mWindowPlacerLocked.performSurfacePlacement();
-            if (win.mAppToken != null) {
-                win.mAppToken.updateReportedVisibilityLocked();
+        if (dc != null && dc.removeFromWindowList(win)) {
+            if (!mWindowPlacerLocked.isInLayout()) {
+                dc.assignWindowLayers(true /* setLayoutNeeded */);
+                mWindowPlacerLocked.performSurfacePlacement();
+                if (win.mAppToken != null) {
+                    win.mAppToken.updateReportedVisibilityLocked();
+                }
             }
         }
 
@@ -2046,15 +2064,14 @@
             // reassign them at this point if the IM window state gets shuffled
             boolean toBeDisplayed = (result & WindowManagerGlobal.RELAYOUT_RES_FIRST_TIME) != 0;
             final DisplayContent dc = win.getDisplayContent();
-            if (imMayMove) {
-                dc.computeImeTarget(true /* updateImeTarget */);
-                if (toBeDisplayed) {
-                    // Little hack here -- we -should- be able to rely on the function to return
-                    // true if the IME has moved and needs its layer recomputed. However, if the IME
-                    // was hidden and isn't actually moved in the list, its layer may be out of data
-                    // so we make sure to recompute it.
-                    dc.assignWindowLayers(false /* setLayoutNeeded */);
-                }
+            if (imMayMove && (dc.moveInputMethodWindowsIfNeeded(false) || toBeDisplayed)) {
+                // Little hack here -- we -should- be able to rely on the function to return true if
+                // the IME has moved and needs its layer recomputed.  However, if the IME was hidden
+                // and isn't actually moved in the list, its layer may be out of data so we make
+                // sure to recompute it.
+                // TODO: Probably not needed once the window list always has the right z-ordering
+                // when the window hierarchy is updated.
+                dc.assignWindowLayers(false /* setLayoutNeeded */);
             }
 
             if (wallpaperMayMove) {
@@ -3334,7 +3351,7 @@
                 if (mAppTransition.isTransitionSet()) {
                     task.setSendingToBottom(false);
                 }
-                displayContent.layoutAndAssignWindowLayersIfNeeded();
+                displayContent.rebuildAppWindowsAndLayoutIfNeeded();
             }
         } finally {
             Binder.restoreCallingIdentity(origId);
@@ -3356,7 +3373,7 @@
                 if (mAppTransition.isTransitionSet()) {
                     task.setSendingToBottom(true);
                 }
-                stack.getDisplayContent().layoutAndAssignWindowLayersIfNeeded();
+                stack.getDisplayContent().rebuildAppWindowsAndLayoutIfNeeded();
             }
         } finally {
             Binder.restoreCallingIdentity(origId);
@@ -4602,7 +4619,7 @@
                 return null;
             }
         }
-        return displayContent.screenshotApplications(appToken, width, height,
+        return displayContent.screenshotApplications(appToken, displayId, width, height,
                 includeFullDisplay, frameScale, config, wallpaperOnly);
     }
 
@@ -5164,7 +5181,7 @@
 
         boolean result = true;
 
-        final ArrayList<WindowState> windows = new ArrayList();
+        final WindowList windows = new WindowList();
         synchronized (mWindowMap) {
             mRoot.forAllWindows(w -> {
                 windows.add(w);
@@ -7295,7 +7312,7 @@
         changes |= FINISH_LAYOUT_REDO_LAYOUT;
         if (DEBUG_WALLPAPER_LIGHT) Slog.v(TAG_WM,
                 "Wallpaper layer changed: assigning layers + relayout");
-        dc.computeImeTarget(true /* updateImeTarget */);
+        dc.moveInputMethodWindowsIfNeeded(true);
         mRoot.mWallpaperMayChange = true;
         // Since the window list has been rebuilt, focus might have to be recomputed since the
         // actual order of windows might have changed again.
@@ -7388,25 +7405,10 @@
             mH.sendEmptyMessage(H.REPORT_FOCUS_CHANGE);
             // TODO(multidisplay): Focused windows on default display only.
             final DisplayContent displayContent = getDefaultDisplayContentLocked();
-            boolean imWindowChanged = false;
-            if (mInputMethodWindow != null) {
-                final WindowState prevTarget = mInputMethodTarget;
-                final WindowState newTarget =
-                        displayContent.computeImeTarget(true /* updateImeTarget*/);
-
-                imWindowChanged = prevTarget != newTarget;
-
-                if (mode != UPDATE_FOCUS_WILL_ASSIGN_LAYERS
-                        && mode != UPDATE_FOCUS_WILL_PLACE_SURFACES) {
-                    final int prevImeAnimLayer = mInputMethodWindow.mWinAnimator.mAnimLayer;
-                    displayContent.assignWindowLayers(false /* setLayoutNeeded */);
-                    imWindowChanged |=
-                            prevImeAnimLayer != mInputMethodWindow.mWinAnimator.mAnimLayer;
-                }
-            }
-
+            final boolean imWindowChanged = displayContent.moveInputMethodWindowsIfNeeded(
+                    mode != UPDATE_FOCUS_WILL_ASSIGN_LAYERS
+                            && mode != UPDATE_FOCUS_WILL_PLACE_SURFACES);
             if (imWindowChanged) {
-                mWindowsChanged = true;
                 displayContent.setLayoutNeeded();
                 newFocus = mRoot.computeFocusedWindow();
             }
@@ -7881,6 +7883,7 @@
     private void dumpTokensLocked(PrintWriter pw, boolean dumpAll) {
         pw.println("WINDOW MANAGER TOKENS (dumpsys window tokens)");
         mRoot.dumpTokens(pw, dumpAll);
+        mRoot.mWallpaperController.dumpTokens(pw, "  ", dumpAll);
         if (!mFinishedStarting.isEmpty()) {
             pw.println();
             pw.println("  Finishing start of application tokens:");
@@ -7926,6 +7929,16 @@
             ArrayList<WindowState> windows) {
         mRoot.dumpWindowsNoHeader(pw, dumpAll, windows);
 
+        if (mInputMethodDialogs.size() > 0) {
+            pw.println();
+            pw.println("  Input method dialogs:");
+            for (int i=mInputMethodDialogs.size()-1; i>=0; i--) {
+                WindowState w = mInputMethodDialogs.get(i);
+                if (windows == null || windows.contains(w)) {
+                    pw.print("  IM Dialog #"); pw.print(i); pw.print(": "); pw.println(w);
+                }
+            }
+        }
         if (mPendingRemove.size() > 0) {
             pw.println();
             pw.println("  Remove pending for:");
@@ -8084,7 +8097,7 @@
 
     private boolean dumpWindows(PrintWriter pw, String name, String[] args, int opti,
             boolean dumpAll) {
-        final ArrayList<WindowState> windows = new ArrayList();
+        final WindowList windows = new WindowList();
         if ("apps".equals(name) || "visible".equals(name) || "visible-apps".equals(name)) {
             final boolean appsOnly = name.contains("apps");
             final boolean visibleOnly = name.contains("visible");
diff --git a/services/core/java/com/android/server/wm/WindowState.java b/services/core/java/com/android/server/wm/WindowState.java
index d959d8c..661df9cd 100644
--- a/services/core/java/com/android/server/wm/WindowState.java
+++ b/services/core/java/com/android/server/wm/WindowState.java
@@ -76,7 +76,6 @@
 import static android.view.WindowManager.LayoutParams.FIRST_SUB_WINDOW;
 import static android.view.WindowManager.LayoutParams.FIRST_SYSTEM_WINDOW;
 import static android.view.WindowManager.LayoutParams.FLAG_ALLOW_LOCK_WHILE_SCREEN_ON;
-import static android.view.WindowManager.LayoutParams.FLAG_ALT_FOCUSABLE_IM;
 import static android.view.WindowManager.LayoutParams.FLAG_DIM_BEHIND;
 import static android.view.WindowManager.LayoutParams.FLAG_DISMISS_KEYGUARD;
 import static android.view.WindowManager.LayoutParams.FLAG_LAYOUT_NO_LIMITS;
@@ -116,7 +115,6 @@
 import static com.android.server.wm.WindowManagerDebugConfig.DEBUG_CONFIGURATION;
 import static com.android.server.wm.WindowManagerDebugConfig.DEBUG_FOCUS;
 import static com.android.server.wm.WindowManagerDebugConfig.DEBUG_FOCUS_LIGHT;
-import static com.android.server.wm.WindowManagerDebugConfig.DEBUG_INPUT_METHOD;
 import static com.android.server.wm.WindowManagerDebugConfig.DEBUG_LAYERS;
 import static com.android.server.wm.WindowManagerDebugConfig.DEBUG_LAYOUT;
 import static com.android.server.wm.WindowManagerDebugConfig.DEBUG_ORIENTATION;
@@ -142,6 +140,9 @@
 import static com.android.server.wm.WindowStateAnimator.HAS_DRAWN;
 import static com.android.server.wm.WindowStateAnimator.READY_TO_SHOW;
 
+class WindowList extends ArrayList<WindowState> {
+}
+
 /** A window in the window manager. */
 class WindowState extends WindowContainer<WindowState> implements WindowManagerPolicy.WindowState {
     static final String TAG = TAG_WITH_CLASS_NAME ? "WindowState" : TAG_WM;
@@ -447,6 +448,12 @@
      */
     boolean mWindowRemovalAllowed;
 
+    /**
+     * Temp for keeping track of windows that have been removed when
+     * rebuilding window list.
+     */
+    boolean mRebuilding;
+
     // Input channel and input window handle used by the input dispatcher.
     final InputWindowHandle mInputWindowHandle;
     InputChannel mInputChannel;
@@ -1714,7 +1721,7 @@
 
         final DisplayContent dc = getDisplayContent();
         if (mService.mInputMethodTarget == this) {
-            dc.computeImeTarget(true /* updateImeTarget */);
+            dc.moveInputMethodWindowsIfNeeded(false);
         }
 
         final int type = mAttrs.type;
@@ -1924,33 +1931,6 @@
         return mLayer + specialAdjustment;
     }
 
-    boolean canBeImeTarget() {
-        final int fl = mAttrs.flags & (FLAG_NOT_FOCUSABLE|FLAG_ALT_FOCUSABLE_IM);
-        final int type = mAttrs.type;
-
-        if (fl != 0 && fl != (FLAG_NOT_FOCUSABLE | FLAG_ALT_FOCUSABLE_IM)
-                && type != TYPE_APPLICATION_STARTING) {
-            return false;
-        }
-
-        if (DEBUG_INPUT_METHOD) {
-            Slog.i(TAG_WM, "isVisibleOrAdding " + this + ": " + isVisibleOrAdding());
-            if (!isVisibleOrAdding()) {
-                Slog.i(TAG_WM, "  mSurfaceController=" + mWinAnimator.mSurfaceController
-                        + " relayoutCalled=" + mRelayoutCalled
-                        + " viewVis=" + mViewVisibility
-                        + " policyVis=" + mPolicyVisibility
-                        + " policyVisAfterAnim=" + mPolicyVisibilityAfterAnim
-                        + " parentHidden=" + isParentWindowHidden()
-                        + " exiting=" + mAnimatingExit + " destroying=" + mDestroying);
-                if (mAppToken != null) {
-                    Slog.i(TAG_WM, "  mAppToken.hiddenRequested=" + mAppToken.hiddenRequested);
-                }
-            }
-        }
-        return isVisibleOrAdding();
-    }
-
     void scheduleAnimationIfDimming() {
         final DisplayContent dc = getDisplayContent();
         if (dc == null) {
@@ -2105,7 +2085,7 @@
         return false;
     }
 
-    private void removeReplacedWindow() {
+    void removeReplacedWindow() {
         if (DEBUG_ADD_REMOVE) Slog.d(TAG, "Removing replaced window: " + this);
         if (isDimming()) {
             transferDimToReplacement();
@@ -2158,16 +2138,6 @@
         }
     }
 
-    @Override
-    void switchUser() {
-        super.switchUser();
-        if (isHiddenFromUserLocked()) {
-            if (DEBUG_VISIBILITY) Slog.w(TAG_WM, "user changing, hiding " + this
-                    + ", attrs=" + mAttrs.type + ", belonging to " + mOwnerUid);
-            hideLw(false);
-        }
-    }
-
     int getTouchableRegion(Region region, int flags) {
         final boolean modal = (flags & (FLAG_NOT_TOUCH_MODAL | FLAG_NOT_FOCUSABLE)) == 0;
         if (modal && mAppToken != null) {
@@ -3529,6 +3499,16 @@
         return mIsChildWindow;
     }
 
+    /**
+     * Returns the bottom child window in regards to z-order of this window or null if no children.
+     */
+    WindowState getBottomChild() {
+        // Child windows are z-ordered based on sub-layer using {@link #sWindowSubLayerComparator}
+        // and the child with the lowest z-order will be at the head of the list.
+        WindowState c = mChildren.peekFirst();
+        return c == null ? null : c;
+    }
+
     boolean layoutInParentFrame() {
         return mIsChildWindow
                 && (mAttrs.privateFlags & PRIVATE_FLAG_LAYOUT_CHILD_WINDOW_IN_PARENT_FRAME) != 0;
@@ -3815,6 +3795,44 @@
     }
 
     @Override
+    int rebuildWindowList(int addIndex) {
+        return reAddWindow(addIndex);
+    }
+
+    // TODO: come-up with a better name for this method that represents what it does.
+    // Or, it is probably not going to matter anyways if we are successful in getting rid of
+    // the WindowList concept.
+    int reAddWindow(int index) {
+        final DisplayContent dc = getDisplayContent();
+        // Adding child windows relies on child windows being ordered by mSubLayer using
+        // {@link #sWindowSubLayerComparator}.
+        final int childCount = mChildren.size();
+        boolean winAdded = false;
+        for (int j = 0; j < childCount; j++) {
+            final WindowState child = mChildren.get(j);
+            if (!winAdded && child.mSubLayer >= 0) {
+                if (DEBUG_WINDOW_MOVEMENT) Slog.v(TAG_WM,
+                        "Re-adding child window at " + index + ": " + child);
+                mRebuilding = false;
+                dc.addToWindowList(this, index);
+                index++;
+                winAdded = true;
+            }
+            if (DEBUG_WINDOW_MOVEMENT) Slog.v(TAG_WM, "Re-adding window at " + index + ": " + child);
+            child.mRebuilding = false;
+            dc.addToWindowList(child, index);
+            index++;
+        }
+        if (!winAdded) {
+            if (DEBUG_WINDOW_MOVEMENT) Slog.v(TAG_WM, "Re-adding window at " + index + ": " + this);
+            mRebuilding = false;
+            dc.addToWindowList(this, index);
+            index++;
+        }
+        return index;
+    }
+
+    @Override
     boolean forAllWindows(ToBooleanFunction<WindowState> callback, boolean traverseTopToBottom) {
         if (mChildren.isEmpty()) {
             // The window has no children so we just return it.
diff --git a/services/core/java/com/android/server/wm/WindowSurfacePlacer.java b/services/core/java/com/android/server/wm/WindowSurfacePlacer.java
index de80837..7e1880f 100644
--- a/services/core/java/com/android/server/wm/WindowSurfacePlacer.java
+++ b/services/core/java/com/android/server/wm/WindowSurfacePlacer.java
@@ -239,8 +239,7 @@
         mService.mH.removeMessages(H.APP_TRANSITION_TIMEOUT);
 
         final DisplayContent displayContent = mService.getDefaultDisplayContentLocked();
-        // TODO: Don't believe this is really needed...
-        //mService.mWindowsChanged = true;
+        displayContent.rebuildAppWindowList();
 
         mService.mRoot.mWallpaperMayChange = false;
 
@@ -357,8 +356,12 @@
         displayContent.setLayoutNeeded();
 
         // TODO(multidisplay): IMEs are only supported on the default display.
+        // TODO: Probably not needed once the window list always has the right z-ordering
+        // when the window hierarchy is updated.
         final DisplayContent dc = mService.getDefaultDisplayContentLocked();
-        dc.computeImeTarget(true /* updateImeTarget */);
+        if (!dc.moveInputMethodWindowsIfNeeded(true)) {
+            dc.assignWindowLayers(false /*setLayoutNeeded*/);
+        }
         mService.updateFocusedWindowLocked(UPDATE_FOCUS_PLACING_SURFACES,
                 true /*updateInputWindows*/);
         mService.mFocusMayChange = false;
diff --git a/services/core/java/com/android/server/wm/WindowToken.java b/services/core/java/com/android/server/wm/WindowToken.java
index 40bd3fb..a2eebc3 100644
--- a/services/core/java/com/android/server/wm/WindowToken.java
+++ b/services/core/java/com/android/server/wm/WindowToken.java
@@ -168,6 +168,13 @@
         return highestAnimLayer;
     }
 
+    WindowState getTopWindow() {
+        if (mChildren.isEmpty()) {
+            return null;
+        }
+        return (WindowState) mChildren.get(mChildren.size() - 1).getTop();
+    }
+
     /**
      * Returns true if the new window is considered greater than the existing window in terms of
      * z-order.
@@ -182,16 +189,51 @@
         if (DEBUG_FOCUS) Slog.d(TAG_WM,
                 "addWindow: win=" + win + " Callers=" + Debug.getCallers(5));
 
-        if (win.isChildWindow()) {
-            // Child windows are added to their parent windows.
+        if (!win.isChildWindow()) {
+            if (asAppWindowToken() != null) {
+                mDisplayContent.addAppWindowToWindowList(win);
+            } else {
+                mDisplayContent.addNonAppWindowToWindowList(win);
+            }
+
+            if (!mChildren.contains(win)) {
+                if (DEBUG_ADD_REMOVE) Slog.v(TAG_WM, "Adding " + win + " to " + this);
+                addChild(win, mWindowComparator);
+            }
+        } else {
+            mDisplayContent.addChildWindowToWindowList(win);
+        }
+    }
+
+    void addImeWindow(WindowState win) {
+        int pos = mDisplayContent.findDesiredInputMethodWindowIndex(true);
+
+        if (pos < 0) {
+            addWindow(win);
+            mDisplayContent.moveInputMethodDialogs(pos);
             return;
         }
+
+        if (DEBUG_WINDOW_MOVEMENT || DEBUG_ADD_REMOVE) Slog.v(TAG_WM,
+                "Adding input method window " + win + " at " + pos);
+        mDisplayContent.addToWindowList(win, pos);
         if (!mChildren.contains(win)) {
-            if (DEBUG_ADD_REMOVE) Slog.v(TAG_WM, "Adding " + win + " to " + this);
-            addChild(win, mWindowComparator);
-            mService.mWindowsChanged = true;
-            // TODO: Should we also be setting layout needed here and other places?
+            addChild(win, null);
         }
+        mDisplayContent.moveInputMethodDialogs(pos + 1);
+    }
+
+    /** Return the first window in the token window list that isn't a starting window or null. */
+    WindowState getFirstNonStartingWindow() {
+        final int count = mChildren.size();
+        // We only care about parent windows so no need to loop through child windows.
+        for (int i = 0; i < count; i++) {
+            final WindowState w = mChildren.get(i);
+            if (w.mAttrs.type != TYPE_APPLICATION_STARTING) {
+                return w;
+            }
+        }
+        return null;
     }
 
     /** Returns true if the token windows list is empty. */
diff --git a/services/tests/servicestests/src/com/android/server/wm/WindowStateTests.java b/services/tests/servicestests/src/com/android/server/wm/WindowStateTests.java
index 3f47d5c..50e5a22 100644
--- a/services/tests/servicestests/src/com/android/server/wm/WindowStateTests.java
+++ b/services/tests/servicestests/src/com/android/server/wm/WindowStateTests.java
@@ -117,6 +117,35 @@
     }
 
     @Test
+    public void testGetBottomChild() throws Exception {
+        final WindowState parentWindow =
+                createWindow(null, TYPE_APPLICATION, mWindowToken, "parentWindow");
+        assertNull(parentWindow.getBottomChild());
+
+        final WindowState child1 =
+                createWindow(parentWindow, TYPE_APPLICATION_PANEL, mWindowToken, "child1");
+        assertEquals(child1, parentWindow.getBottomChild());
+
+        final WindowState child2 =
+                createWindow(parentWindow, TYPE_APPLICATION_PANEL, mWindowToken, "child2");
+        // Since child1 and child2 are at the same layer, then child2 is expect to be added on top
+        // on child1
+        assertEquals(child1, parentWindow.getBottomChild());
+
+        final WindowState child3 =
+                createWindow(parentWindow, TYPE_APPLICATION_MEDIA_OVERLAY, mWindowToken, "child3");
+        // Since child3 is a negative layer, we would expect it to be added below current children
+        // with positive layers.
+        assertEquals(child3, parentWindow.getBottomChild());
+
+        final WindowState child4 =
+                createWindow(parentWindow, TYPE_APPLICATION_MEDIA_OVERLAY, mWindowToken, "child4");
+        // We would also expect additional negative layers to be added below existing negative
+        // layers.
+        assertEquals(child4, parentWindow.getBottomChild());
+    }
+
+    @Test
     public void testGetParentWindow() throws Exception {
         final WindowState parentWindow =
                 createWindow(null, TYPE_APPLICATION, mWindowToken, "parentWindow");