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;
         }