Fixed window ordering issue with TYPE_VOICE_INTERACTION.

WC.forAllWindows returns windows based on their token order in the
hierarchy and the non-app windows are ordered in the hierarchy based
on their types. For most window tokens their types is specified when
the token is added, but for some others we use the type of the first
window added to the token. This becomes a problem if various window
types are added to the same token (sys-ui I am looking at you...) and
someone adds another token with a window type that should be z-ordered
in-between the windows of the first token.
For now we work around the problem by collecting all the non-app windows
and making sure they are in order before return any window to the caller.
Long term we want to change sys-ui and other callers to use different
window tokens based on the window types they are adding.

Fixes: 33538278
Test: bit FrameworksServicesTests:com.android.server.wm.DisplayContentTests
Change-Id: I83357975c87c704af9d0702c939ca99984462365
diff --git a/services/tests/servicestests/src/com/android/server/wm/DisplayContentTests.java b/services/tests/servicestests/src/com/android/server/wm/DisplayContentTests.java
index 162a1a9..0e20c4e 100644
--- a/services/tests/servicestests/src/com/android/server/wm/DisplayContentTests.java
+++ b/services/tests/servicestests/src/com/android/server/wm/DisplayContentTests.java
@@ -26,6 +26,7 @@
 import java.util.ArrayList;
 
 import static android.view.WindowManager.LayoutParams.TYPE_BASE_APPLICATION;
+import static android.view.WindowManager.LayoutParams.TYPE_VOICE_INTERACTION;
 import static org.junit.Assert.assertEquals;
 
 /**
@@ -77,6 +78,8 @@
         assertEquals(sNavBarWindow, windows.get(2));
         assertEquals(sImeWindow, windows.get(1));
         assertEquals(sImeDialogWindow, windows.get(0));
+
+        exitingAppWindow.removeImmediately();
     }
 
     @Test
@@ -121,4 +124,45 @@
         sWm.mInputMethodTarget = null;
         imeAppTarget.removeImmediately();
     }
+
+    @Test
+    public void testForAllWindows_WithInBetweenWindowToken() throws Exception {
+        // This window is set-up to be z-ordered between some windows that go in the same token like
+        // the nav bar and status bar.
+        final WindowState voiceInteractionWindow = createWindow(null, TYPE_VOICE_INTERACTION,
+                sDisplayContent, "voiceInteractionWindow");
+
+        final ArrayList<WindowState> windows = new ArrayList();
+
+        // Test forward traversal.
+        sDisplayContent.forAllWindows(w -> {windows.add(w);}, false /* traverseTopToBottom */);
+
+        assertEquals(sWallpaperWindow, windows.get(0));
+        assertEquals(sChildAppWindowBelow, windows.get(1));
+        assertEquals(sAppWindow, windows.get(2));
+        assertEquals(sChildAppWindowAbove, windows.get(3));
+        assertEquals(sDockedDividerWindow, windows.get(4));
+        assertEquals(voiceInteractionWindow, windows.get(5));
+        assertEquals(sStatusBarWindow, windows.get(6));
+        assertEquals(sNavBarWindow, windows.get(7));
+        assertEquals(sImeWindow, windows.get(8));
+        assertEquals(sImeDialogWindow, windows.get(9));
+
+        // Test backward traversal.
+        windows.clear();
+        sDisplayContent.forAllWindows(w -> {windows.add(w);}, true /* traverseTopToBottom */);
+
+        assertEquals(sWallpaperWindow, windows.get(9));
+        assertEquals(sChildAppWindowBelow, windows.get(8));
+        assertEquals(sAppWindow, windows.get(7));
+        assertEquals(sChildAppWindowAbove, windows.get(6));
+        assertEquals(sDockedDividerWindow, windows.get(5));
+        assertEquals(voiceInteractionWindow, windows.get(4));
+        assertEquals(sStatusBarWindow, windows.get(3));
+        assertEquals(sNavBarWindow, windows.get(2));
+        assertEquals(sImeWindow, windows.get(1));
+        assertEquals(sImeDialogWindow, windows.get(0));
+
+        voiceInteractionWindow.removeImmediately();
+    }
 }