Introduce IME subtype switching auto mode

Create a new RotationList inside InputMethodSubtypeSwitchingController,
enabling switching in either static or recency order and either forwards
or backwards direction. Also introduce a new auto mode for IME subtype
switching, which resolves to recency order for the first switch after a
user action (reset after each switch), and to static order otherwise.
This also handles switching using the hardware keyboard shortcut
to maintain consistency.

Flag: android.view.inputmethod.ime_switcher_revamp
Test: atest InputMethodSubtypeSwitchingControllerTest
Bug: 311791923
Change-Id: I71e3a0f4234f829ca6791cd575fda977bc3df13f

4 files changed, 1078 insertions, 24 deletions

diff --git a/core/java/android/inputmethodservice/AbstractInputMethodService.java b/core/java/android/inputmethodservice/AbstractInputMethodService.java
index e2d215ebfed4..4bc5bd2427ea 100644
--- a/core/java/android/inputmethodservice/AbstractInputMethodService.java
+++ b/core/java/android/inputmethodservice/AbstractInputMethodService.java
@@ -29,6 +29,7 @@ import android.view.KeyEvent;
 import android.view.MotionEvent;
 import android.view.WindowManager;
 import android.view.WindowManagerGlobal;
+import android.view.inputmethod.Flags;
 import android.view.inputmethod.InputMethod;
 import android.view.inputmethod.InputMethodSession;
 import android.window.WindowProviderService;
@@ -186,6 +187,10 @@ public abstract class AbstractInputMethodService extends WindowProviderService
             if (callback != null) {
                 callback.finishedEvent(seq, handled);
             }
+            if (Flags.imeSwitcherRevamp() && !handled && event.getAction() == KeyEvent.ACTION_DOWN
+                    && event.getUnicodeChar() > 0 && mInputMethodServiceInternal != null) {
+                mInputMethodServiceInternal.notifyUserActionIfNecessary();
+            }
         }
 
         /**
diff --git a/services/core/java/com/android/server/inputmethod/InputMethodManagerService.java b/services/core/java/com/android/server/inputmethod/InputMethodManagerService.java
index 7daf9582cdd6..18612f78d47b 100644
--- a/services/core/java/com/android/server/inputmethod/InputMethodManagerService.java
+++ b/services/core/java/com/android/server/inputmethod/InputMethodManagerService.java
@@ -53,6 +53,7 @@ import static com.android.server.inputmethod.ImeVisibilityStateComputer.ImeTarge
 import static com.android.server.inputmethod.ImeVisibilityStateComputer.ImeVisibilityResult;
 import static com.android.server.inputmethod.ImeVisibilityStateComputer.STATE_HIDE_IME;
 import static com.android.server.inputmethod.InputMethodBindingController.TIME_TO_RECONNECT;
+import static com.android.server.inputmethod.InputMethodSubtypeSwitchingController.MODE_AUTO;
 import static com.android.server.inputmethod.InputMethodUtils.isSoftInputModeStateVisibleAllowed;
 
 import static java.lang.annotation.RetentionPolicy.SOURCE;
@@ -4138,7 +4139,8 @@ public final class InputMethodManagerService implements IInputMethodManagerImpl.
         final var currentImi = bindingController.getSelectedMethod();
         final ImeSubtypeListItem nextSubtype = getUserData(userId).mSwitchingController
                 .getNextInputMethodLocked(onlyCurrentIme, currentImi,
-                        bindingController.getCurrentSubtype());
+                        bindingController.getCurrentSubtype(),
+                        MODE_AUTO, true /* forward */);
         if (nextSubtype == null) {
             return false;
         }
@@ -4158,7 +4160,8 @@ public final class InputMethodManagerService implements IInputMethodManagerImpl.
             final var currentImi = bindingController.getSelectedMethod();
             final ImeSubtypeListItem nextSubtype = getUserData(userId).mSwitchingController
                     .getNextInputMethodLocked(false /* onlyCurrentIme */, currentImi,
-                            bindingController.getCurrentSubtype());
+                            bindingController.getCurrentSubtype(),
+                            MODE_AUTO, true /* forward */);
             return nextSubtype != null;
         }
     }
@@ -5459,6 +5462,10 @@ public final class InputMethodManagerService implements IInputMethodManagerImpl.
             // Set InputMethod here
             settings.putSelectedInputMethod(imi != null ? imi.getId() : "");
         }
+
+        if (Flags.imeSwitcherRevamp()) {
+            getUserData(userId).mSwitchingController.onInputMethodSubtypeChanged();
+        }
     }
 
     @GuardedBy("ImfLock.class")
@@ -5579,11 +5586,29 @@ public final class InputMethodManagerService implements IInputMethodManagerImpl.
         if (currentImi == null) {
             return;
         }
-        final InputMethodSubtypeHandle currentSubtypeHandle =
-                InputMethodSubtypeHandle.of(currentImi, bindingController.getCurrentSubtype());
-        final InputMethodSubtypeHandle nextSubtypeHandle =
-                getUserData(userId).mHardwareKeyboardShortcutController.onSubtypeSwitch(
+        final var currentSubtype = bindingController.getCurrentSubtype();
+        final InputMethodSubtypeHandle nextSubtypeHandle;
+        if (Flags.imeSwitcherRevamp()) {
+            final var nextItem = getUserData(userId).mSwitchingController
+                    .getNextInputMethodForHardware(
+                            false /* onlyCurrentIme */, currentImi, currentSubtype, MODE_AUTO,
+                            direction > 0 /* forward */);
+            if (nextItem == null) {
+                Slog.i(TAG, "Hardware keyboard switching shortcut,"
+                        + " next input method and subtype not found");
+                return;
+            }
+
+            final var nextSubtype = nextItem.mSubtypeId > NOT_A_SUBTYPE_ID
+                    ? nextItem.mImi.getSubtypeAt(nextItem.mSubtypeId) : null;
+            nextSubtypeHandle = InputMethodSubtypeHandle.of(nextItem.mImi, nextSubtype);
+        } else {
+            final InputMethodSubtypeHandle currentSubtypeHandle =
+                    InputMethodSubtypeHandle.of(currentImi, currentSubtype);
+            nextSubtypeHandle =
+                    getUserData(userId).mHardwareKeyboardShortcutController.onSubtypeSwitch(
                         currentSubtypeHandle, direction > 0);
+        }
         if (nextSubtypeHandle == null) {
             return;
         }
diff --git a/services/core/java/com/android/server/inputmethod/InputMethodSubtypeSwitchingController.java b/services/core/java/com/android/server/inputmethod/InputMethodSubtypeSwitchingController.java
index bb1b9df6cf4c..8b3c718c0537 100644
--- a/services/core/java/com/android/server/inputmethod/InputMethodSubtypeSwitchingController.java
+++ b/services/core/java/com/android/server/inputmethod/InputMethodSubtypeSwitchingController.java
@@ -16,6 +16,8 @@
 
 package com.android.server.inputmethod;
 
+import android.annotation.IntDef;
+import android.annotation.IntRange;
 import android.annotation.NonNull;
 import android.annotation.Nullable;
 import android.content.Context;
@@ -24,11 +26,14 @@ import android.text.TextUtils;
 import android.util.ArraySet;
 import android.util.Printer;
 import android.util.Slog;
+import android.view.inputmethod.Flags;
 import android.view.inputmethod.InputMethodInfo;
 import android.view.inputmethod.InputMethodSubtype;
 
 import com.android.internal.annotations.VisibleForTesting;
 
+import java.lang.annotation.Retention;
+import java.lang.annotation.RetentionPolicy;
 import java.util.ArrayList;
 import java.util.Collections;
 import java.util.List;
@@ -45,6 +50,34 @@ final class InputMethodSubtypeSwitchingController {
     private static final boolean DEBUG = false;
     private static final int NOT_A_SUBTYPE_ID = InputMethodUtils.NOT_A_SUBTYPE_ID;
 
+    @IntDef(prefix = {"MODE_"}, value = {
+            MODE_STATIC,
+            MODE_RECENT,
+            MODE_AUTO
+    })
+    @Retention(RetentionPolicy.SOURCE)
+    public @interface SwitchMode {
+    }
+
+    /**
+     * Switch using the static order (the order of the given list of input methods and subtypes).
+     * This order is only set when given a new list, and never updated.
+     */
+    public static final int MODE_STATIC = 0;
+
+    /**
+     * Switch using the recency based order, going from most recent to least recent,
+     * updated on {@link #onUserActionLocked user action}.
+     */
+    public static final int MODE_RECENT = 1;
+
+    /**
+     * If there was a {@link #onUserActionLocked user action} since the last
+     * {@link #onInputMethodSubtypeChanged() switch}, and direction is forward,
+     * use {@link #MODE_RECENT}, otherwise use {@link #MODE_STATIC}.
+     */
+    public static final int MODE_AUTO = 2;
+
     public static class ImeSubtypeListItem implements Comparable<ImeSubtypeListItem> {
 
         @NonNull
@@ -226,6 +259,59 @@ final class InputMethodSubtypeSwitchingController {
         return imList;
     }
 
+    @NonNull
+    private static List<ImeSubtypeListItem> getInputMethodAndSubtypeListForHardwareKeyboard(
+            @NonNull Context context, @NonNull InputMethodSettings settings) {
+        if (!Flags.imeSwitcherRevamp()) {
+            return new ArrayList<>();
+        }
+        final int userId = settings.getUserId();
+        final Context userAwareContext = context.getUserId() == userId
+                ? context
+                : context.createContextAsUser(UserHandle.of(userId), 0 /* flags */);
+        final String mSystemLocaleStr = SystemLocaleWrapper.get(userId).get(0).toLanguageTag();
+
+        final ArrayList<InputMethodInfo> imis = settings.getEnabledInputMethodList();
+        if (imis.isEmpty()) {
+            Slog.w(TAG, "Enabled input method list is empty.");
+            return new ArrayList<>();
+        }
+
+        final ArrayList<ImeSubtypeListItem> imList = new ArrayList<>();
+        final int numImes = imis.size();
+        for (int i = 0; i < numImes; ++i) {
+            final InputMethodInfo imi = imis.get(i);
+            if (!imi.shouldShowInInputMethodPicker()) {
+                continue;
+            }
+            final var subtypes = settings.getEnabledInputMethodSubtypeList(imi, true);
+            final ArraySet<InputMethodSubtype> enabledSubtypeSet = new ArraySet<>(subtypes);
+            final CharSequence imeLabel = imi.loadLabel(userAwareContext.getPackageManager());
+            if (!subtypes.isEmpty()) {
+                final int subtypeCount = imi.getSubtypeCount();
+                if (DEBUG) {
+                    Slog.v(TAG, "Add subtypes: " + subtypeCount + ", " + imi.getId());
+                }
+                for (int j = 0; j < subtypeCount; j++) {
+                    final InputMethodSubtype subtype = imi.getSubtypeAt(j);
+                    if (enabledSubtypeSet.contains(subtype)
+                            && subtype.isSuitableForPhysicalKeyboardLayoutMapping()) {
+                        final CharSequence subtypeLabel =
+                                subtype.overridesImplicitlyEnabledSubtype() ? null : subtype
+                                        .getDisplayName(userAwareContext, imi.getPackageName(),
+                                                imi.getServiceInfo().applicationInfo);
+                        imList.add(new ImeSubtypeListItem(imeLabel,
+                                subtypeLabel, imi, j, subtype.getLocale(), mSystemLocaleStr));
+                    }
+                }
+            } else {
+                imList.add(new ImeSubtypeListItem(imeLabel, null, imi, NOT_A_SUBTYPE_ID, null,
+                        mSystemLocaleStr));
+            }
+        }
+        return imList;
+    }
+
     private static int calculateSubtypeId(@NonNull InputMethodInfo imi,
             @Nullable InputMethodSubtype subtype) {
         return subtype != null ? SubtypeUtils.getSubtypeIdFromHashCode(imi, subtype.hashCode())
@@ -385,6 +471,132 @@ final class InputMethodSubtypeSwitchingController {
         }
     }
 
+    /**
+     * List container that allows getting the next item in either forwards or backwards direction,
+     * in either static or recency order, and either in the same IME or not.
+     */
+    private static class RotationList {
+
+        /**
+         * List of items in a static order.
+         */
+        @NonNull
+        private final List<ImeSubtypeListItem> mItems;
+
+        /**
+         * Mapping of recency index to static index (in {@link #mItems}), with lower indices being
+         * more recent.
+         */
+        @NonNull
+        private final int[] mRecencyMap;
+
+        RotationList(@NonNull List<ImeSubtypeListItem> items) {
+            mItems = items;
+            mRecencyMap = new int[items.size()];
+            for (int i = 0; i < mItems.size(); i++) {
+                mRecencyMap[i] = i;
+            }
+        }
+
+        /**
+         * Gets the next input method and subtype from the given ones.
+         *
+         * @param imi            the input method to find the next value from.
+         * @param subtype        the input method subtype to find the next value from, if any.
+         * @param onlyCurrentIme whether to consider only subtypes of the current input method.
+         * @param useRecency     whether to use the recency order, or the static order.
+         * @param forward        whether to search forwards to backwards in the list.
+         * @return the next input method and subtype if found, otherwise {@code null}.
+         */
+        @Nullable
+        public ImeSubtypeListItem next(@NonNull InputMethodInfo imi,
+                @Nullable InputMethodSubtype subtype, boolean onlyCurrentIme,
+                boolean useRecency, boolean forward) {
+            final int size = mItems.size();
+            if (size <= 1) {
+                return null;
+            }
+            final int index = getIndex(imi, subtype, useRecency);
+            if (index < 0) {
+                return null;
+            }
+
+            final int incrementSign = (forward ? 1 : -1);
+
+            for (int i = 1; i < size; i++) {
+                final int nextIndex = (index + i * incrementSign + size) % size;
+                final int mappedIndex = useRecency ? mRecencyMap[nextIndex] : nextIndex;
+                final var nextItem = mItems.get(mappedIndex);
+                if (!onlyCurrentIme || nextItem.mImi.equals(imi)) {
+                    return nextItem;
+                }
+            }
+            return null;
+        }
+
+        /**
+         * Sets the given input method and subtype as the most recent one.
+         *
+         * @param imi     the input method to set as the most recent.
+         * @param subtype the input method subtype to set as the most recent, if any.
+         * @return {@code true} if the recency was updated, otherwise {@code false}.
+         */
+        public boolean setMostRecent(@NonNull InputMethodInfo imi,
+                @Nullable InputMethodSubtype subtype) {
+            if (mItems.size() <= 1) {
+                return false;
+            }
+
+            final int recencyIndex = getIndex(imi, subtype, true /* useRecency */);
+            if (recencyIndex <= 0) {
+                // Already most recent or not found.
+                return false;
+            }
+            final int staticIndex = mRecencyMap[recencyIndex];
+            System.arraycopy(mRecencyMap, 0, mRecencyMap, 1, recencyIndex);
+            mRecencyMap[0] = staticIndex;
+            return true;
+        }
+
+        /**
+         * Gets the index of the given input method and subtype, in either recency or static order.
+         *
+         * @param imi        the input method to get the index of.
+         * @param subtype    the input method subtype to get the index of, if any.
+         * @param useRecency whether to get the index in the recency or static order.
+         * @return an index in either {@link #mItems} or {@link #mRecencyMap}, or {@code -1}
+         * if not found.
+         */
+        @IntRange(from = -1)
+        private int getIndex(@NonNull InputMethodInfo imi, @Nullable InputMethodSubtype subtype,
+                boolean useRecency) {
+            final int subtypeIndex = calculateSubtypeId(imi, subtype);
+            for (int i = 0; i < mItems.size(); i++) {
+                final int mappedIndex = useRecency ? mRecencyMap[i] : i;
+                final var item = mItems.get(mappedIndex);
+                if (item.mImi.equals(imi) && item.mSubtypeId == subtypeIndex) {
+                    return i;
+                }
+            }
+            return -1;
+        }
+
+        /** Dumps the state of the list into the given printer. */
+        private void dump(@NonNull Printer pw, @NonNull String prefix) {
+            pw.println(prefix + "Static order:");
+            for (int i = 0; i < mItems.size(); ++i) {
+                final var item = mItems.get(i);
+                pw.println(prefix + "i=" + i + " item=" + item);
+            }
+            pw.println(prefix + "Recency order:");
+            for (int i = 0; i < mRecencyMap.length; ++i) {
+                final int index = mRecencyMap[i];
+                final var item = mItems.get(index);
+                pw.println(prefix + "i=" + i + " item=" + item);
+            }
+        }
+    }
+
     @VisibleForTesting
     public static class ControllerImpl {
 
@@ -392,10 +604,23 @@ final class InputMethodSubtypeSwitchingController {
         private final DynamicRotationList mSwitchingAwareRotationList;
         @NonNull
         private final StaticRotationList mSwitchingUnawareRotationList;
+        /** List of input methods and subtypes. */
+        @Nullable
+        private final RotationList mRotationList;
+        /** List of input methods and subtypes suitable for hardware keyboards. */
+        @Nullable
+        private final RotationList mHardwareRotationList;
+
+        /**
+         * Whether there was a user action since the last input method and subtype switch.
+         * Used to determine the switching behaviour for {@link #MODE_AUTO}.
+         */
+        private boolean mUserActionSinceSwitch;
 
         @NonNull
         public static ControllerImpl createFrom(@Nullable ControllerImpl currentInstance,
-                @NonNull List<ImeSubtypeListItem> sortedEnabledItems) {
+                @NonNull List<ImeSubtypeListItem> sortedEnabledItems,
+                @NonNull List<ImeSubtypeListItem> hardwareKeyboardItems) {
             final var switchingAwareImeSubtypes = filterImeSubtypeList(sortedEnabledItems,
                     true /* supportsSwitchingToNextInputMethod */);
             final var switchingUnawareImeSubtypes = filterImeSubtypeList(sortedEnabledItems,
@@ -421,22 +646,55 @@ final class InputMethodSubtypeSwitchingController {
                 switchingUnawareRotationList = new StaticRotationList(switchingUnawareImeSubtypes);
             }
 
-            return new ControllerImpl(switchingAwareRotationList, switchingUnawareRotationList);
+            final RotationList rotationList;
+            if (!Flags.imeSwitcherRevamp()) {
+                rotationList = null;
+            } else if (currentInstance != null && currentInstance.mRotationList != null
+                    && Objects.equals(
+                            currentInstance.mRotationList.mItems, sortedEnabledItems)) {
+                // Can reuse the current instance.
+                rotationList = currentInstance.mRotationList;
+            } else {
+                rotationList = new RotationList(sortedEnabledItems);
+            }
+
+            final RotationList hardwareRotationList;
+            if (!Flags.imeSwitcherRevamp()) {
+                hardwareRotationList = null;
+            } else if (currentInstance != null && currentInstance.mHardwareRotationList != null
+                    && Objects.equals(
+                            currentInstance.mHardwareRotationList.mItems, hardwareKeyboardItems)) {
+                // Can reuse the current instance.
+                hardwareRotationList = currentInstance.mHardwareRotationList;
+            } else {
+                hardwareRotationList = new RotationList(hardwareKeyboardItems);
+            }
+
+            return new ControllerImpl(switchingAwareRotationList, switchingUnawareRotationList,
+                    rotationList, hardwareRotationList);
         }
 
         private ControllerImpl(@NonNull DynamicRotationList switchingAwareRotationList,
-                @NonNull StaticRotationList switchingUnawareRotationList) {
+                @NonNull StaticRotationList switchingUnawareRotationList,
+                @Nullable RotationList rotationList,
+                @Nullable RotationList hardwareRotationList) {
             mSwitchingAwareRotationList = switchingAwareRotationList;
             mSwitchingUnawareRotationList = switchingUnawareRotationList;
+            mRotationList = rotationList;
+            mHardwareRotationList = hardwareRotationList;
         }
 
         @Nullable
         public ImeSubtypeListItem getNextInputMethod(boolean onlyCurrentIme,
-                @Nullable InputMethodInfo imi, @Nullable InputMethodSubtype subtype) {
+                @Nullable InputMethodInfo imi, @Nullable InputMethodSubtype subtype,
+                @SwitchMode int mode, boolean forward) {
             if (imi == null) {
                 return null;
             }
-            if (imi.supportsSwitchingToNextInputMethod()) {
+            if (Flags.imeSwitcherRevamp() && mRotationList != null) {
+                return mRotationList.next(imi, subtype, onlyCurrentIme,
+                        isRecency(mode, forward), forward);
+            } else if (imi.supportsSwitchingToNextInputMethod()) {
                 return mSwitchingAwareRotationList.getNextInputMethodLocked(onlyCurrentIme, imi,
                         subtype);
             } else {
@@ -445,11 +703,66 @@ final class InputMethodSubtypeSwitchingController {
             }
         }
 
-        public void onUserActionLocked(@NonNull InputMethodInfo imi,
+        @Nullable
+        public ImeSubtypeListItem getNextInputMethodForHardware(boolean onlyCurrentIme,
+                @NonNull InputMethodInfo imi, @Nullable InputMethodSubtype subtype,
+                @SwitchMode int mode, boolean forward) {
+            if (Flags.imeSwitcherRevamp() && mHardwareRotationList != null) {
+                return mHardwareRotationList.next(imi, subtype, onlyCurrentIme,
+                        isRecency(mode, forward), forward);
+            }
+            return null;
+        }
+
+        /**
+         * Called when the user took an action that should update the recency of the current
+         * input method and subtype in the switching list.
+         *
+         * @param imi     the currently selected input method.
+         * @param subtype the currently selected input method subtype, if any.
+         * @return {@code true} if the recency was updated, otherwise {@code false}.
+         * @see android.inputmethodservice.InputMethodServiceInternal#notifyUserActionIfNecessary()
+         */
+        public boolean onUserActionLocked(@NonNull InputMethodInfo imi,
                 @Nullable InputMethodSubtype subtype) {
-            if (imi.supportsSwitchingToNextInputMethod()) {
+            boolean recencyUpdated = false;
+            if (Flags.imeSwitcherRevamp()) {
+                if (mRotationList != null) {
+                    recencyUpdated |= mRotationList.setMostRecent(imi, subtype);
+                }
+                if (mHardwareRotationList != null) {
+                    recencyUpdated |= mHardwareRotationList.setMostRecent(imi, subtype);
+                }
+                if (recencyUpdated) {
+                    mUserActionSinceSwitch = true;
+                }
+            } else if (imi.supportsSwitchingToNextInputMethod()) {
                 mSwitchingAwareRotationList.onUserAction(imi, subtype);
             }
+            return recencyUpdated;
+        }
+
+        /** Called when the input method and subtype was changed. */
+        public void onInputMethodSubtypeChanged() {
+            mUserActionSinceSwitch = false;
+        }
+
+        /**
+         * Whether the given mode and direction result in recency or static order.
+         *
+         * <p>{@link #MODE_AUTO} resolves to the recency order for the first forwards switch
+         * after an {@link #onUserActionLocked user action}, and otherwise to the static order.</p>
+         *
+         * @param mode    the switching mode.
+         * @param forward the switching direction.
+         * @return {@code true} for the recency order, otherwise {@code false}.
+         */
+        private boolean isRecency(@SwitchMode int mode, boolean forward) {
+            if (mode == MODE_AUTO && mUserActionSinceSwitch && forward) {
+                return true;
+            } else {
+                return mode == MODE_RECENT;
+            }
         }
 
         @NonNull
@@ -473,6 +786,17 @@ final class InputMethodSubtypeSwitchingController {
             mSwitchingAwareRotationList.dump(pw, prefix + "  ");
             pw.println(prefix + "mSwitchingUnawareRotationList:");
             mSwitchingUnawareRotationList.dump(pw, prefix + "  ");
+            if (Flags.imeSwitcherRevamp()) {
+                if (mRotationList != null) {
+                    pw.println(prefix + "mRotationList:");
+                    mRotationList.dump(pw, prefix + "  ");
+                }
+                if (mHardwareRotationList != null) {
+                    pw.println(prefix + "mHardwareRotationList:");
+                    mHardwareRotationList.dump(pw, prefix + "  ");
+                }
+                pw.println("User action since last switch: " + mUserActionSinceSwitch);
+            }
         }
     }
 
@@ -480,26 +804,71 @@ final class InputMethodSubtypeSwitchingController {
     private ControllerImpl mController;
 
     InputMethodSubtypeSwitchingController() {
-        mController = ControllerImpl.createFrom(null, Collections.emptyList());
+        mController = ControllerImpl.createFrom(null, Collections.emptyList(),
+                Collections.emptyList());
     }
 
+    /**
+     * Called when the user took an action that should update the recency of the current
+     * input method and subtype in the switching list.
+     *
+     * @param imi     the currently selected input method.
+     * @param subtype the currently selected input method subtype, if any.
+     * @see android.inputmethodservice.InputMethodServiceInternal#notifyUserActionIfNecessary()
+     */
     public void onUserActionLocked(@NonNull InputMethodInfo imi,
             @Nullable InputMethodSubtype subtype) {
         mController.onUserActionLocked(imi, subtype);
     }
 
+    /** Called when the input method and subtype was changed. */
+    public void onInputMethodSubtypeChanged() {
+        mController.onInputMethodSubtypeChanged();
+    }
+
     public void resetCircularListLocked(@NonNull Context context,
             @NonNull InputMethodSettings settings) {
         mController = ControllerImpl.createFrom(mController,
                 getSortedInputMethodAndSubtypeList(
                         false /* includeAuxiliarySubtypes */, false /* isScreenLocked */,
-                        false /* forImeMenu */, context, settings));
+                        false /* forImeMenu */, context, settings),
+                getInputMethodAndSubtypeListForHardwareKeyboard(context, settings));
     }
 
+    /**
+     * Gets the next input method and subtype, starting from the given ones, in the given direction.
+     *
+     * @param onlyCurrentIme whether to consider only subtypes of the current input method.
+     * @param imi            the input method to find the next value from.
+     * @param subtype        the input method subtype to find the next value from, if any.
+     * @param mode           the switching mode.
+     * @param forward        whether to search search forwards or backwards in the list.
+     * @return the next input method and subtype if found, otherwise {@code null}.
+     */
     @Nullable
     public ImeSubtypeListItem getNextInputMethodLocked(boolean onlyCurrentIme,
-            @Nullable InputMethodInfo imi, @Nullable InputMethodSubtype subtype) {
-        return mController.getNextInputMethod(onlyCurrentIme, imi, subtype);
+            @Nullable InputMethodInfo imi, @Nullable InputMethodSubtype subtype,
+            @SwitchMode int mode, boolean forward) {
+        return mController.getNextInputMethod(onlyCurrentIme, imi, subtype, mode, forward);
+    }
+
+    /**
+     * Gets the next input method and subtype suitable for hardware keyboards, starting from the
+     * given ones, in the given direction.
+     *
+     * @param onlyCurrentIme whether to consider only subtypes of the current input method.
+     * @param imi            the input method to find the next value from.
+     * @param subtype        the input method subtype to find the next value from, if any.
+     * @param mode           the switching mode
+     * @param forward        whether to search search forwards or backwards in the list.
+     * @return the next input method and subtype if found, otherwise {@code null}.
+     */
+    @Nullable
+    public ImeSubtypeListItem getNextInputMethodForHardware(boolean onlyCurrentIme,
+            @NonNull InputMethodInfo imi, @Nullable InputMethodSubtype subtype,
+            @SwitchMode int mode, boolean forward) {
+        return mController.getNextInputMethodForHardware(onlyCurrentIme, imi, subtype, mode,
+                forward);
     }
 
     public void dump(@NonNull Printer pw, @NonNull String prefix) {
diff --git a/services/tests/InputMethodSystemServerTests/src/com/android/server/inputmethod/InputMethodSubtypeSwitchingControllerTest.java b/services/tests/InputMethodSystemServerTests/src/com/android/server/inputmethod/InputMethodSubtypeSwitchingControllerTest.java
index e81cf9df6660..4186b48ab82a 100644
--- a/services/tests/InputMethodSystemServerTests/src/com/android/server/inputmethod/InputMethodSubtypeSwitchingControllerTest.java
+++ b/services/tests/InputMethodSystemServerTests/src/com/android/server/inputmethod/InputMethodSubtypeSwitchingControllerTest.java
@@ -16,15 +16,26 @@
 
 package com.android.server.inputmethod;
 
+import static com.android.server.inputmethod.InputMethodSubtypeSwitchingController.MODE_AUTO;
+import static com.android.server.inputmethod.InputMethodSubtypeSwitchingController.MODE_RECENT;
+import static com.android.server.inputmethod.InputMethodSubtypeSwitchingController.MODE_STATIC;
+import static com.android.server.inputmethod.InputMethodSubtypeSwitchingController.SwitchMode;
+
 import static org.junit.Assert.assertEquals;
 import static org.junit.Assert.assertFalse;
 import static org.junit.Assert.assertNotEquals;
+import static org.junit.Assert.assertNotNull;
 import static org.junit.Assert.assertTrue;
 
 import android.content.ComponentName;
 import android.content.pm.ApplicationInfo;
 import android.content.pm.ResolveInfo;
 import android.content.pm.ServiceInfo;
+import android.platform.test.annotations.RequiresFlagsDisabled;
+import android.platform.test.annotations.RequiresFlagsEnabled;
+import android.platform.test.flag.junit.CheckFlagsRule;
+import android.platform.test.flag.junit.DeviceFlagsValueProvider;
+import android.view.inputmethod.Flags;
 import android.view.inputmethod.InputMethodInfo;
 import android.view.inputmethod.InputMethodSubtype;
 import android.view.inputmethod.InputMethodSubtype.InputMethodSubtypeBuilder;
@@ -35,6 +46,7 @@ import androidx.annotation.Nullable;
 import com.android.server.inputmethod.InputMethodSubtypeSwitchingController.ControllerImpl;
 import com.android.server.inputmethod.InputMethodSubtypeSwitchingController.ImeSubtypeListItem;
 
+import org.junit.Rule;
 import org.junit.Test;
 
 import java.util.ArrayList;
@@ -51,6 +63,9 @@ public final class InputMethodSubtypeSwitchingControllerTest {
     private static final String SYSTEM_LOCALE = "en_US";
     private static final int NOT_A_SUBTYPE_ID = InputMethodUtils.NOT_A_SUBTYPE_ID;
 
+    @Rule
+    public final CheckFlagsRule mCheckFlagsRule = DeviceFlagsValueProvider.createCheckFlagsRule();
+
     @NonNull
     private static InputMethodSubtype createTestSubtype(@NonNull String locale) {
         return new InputMethodSubtypeBuilder()
@@ -170,7 +185,7 @@ public final class InputMethodSubtypeSwitchingControllerTest {
             subtype = createTestSubtype(currentItem.mSubtypeName.toString());
         }
         final ImeSubtypeListItem nextIme = controller.getNextInputMethod(onlyCurrentIme,
-                currentItem.mImi, subtype);
+                currentItem.mImi, subtype, MODE_STATIC, true /* forward */);
         assertEquals(nextItem, nextIme);
     }
 
@@ -185,15 +200,16 @@ public final class InputMethodSubtypeSwitchingControllerTest {
         }
     }
 
-    private void onUserAction(@NonNull ControllerImpl controller,
+    private boolean onUserAction(@NonNull ControllerImpl controller,
             @NonNull ImeSubtypeListItem subtypeListItem) {
         InputMethodSubtype subtype = null;
         if (subtypeListItem.mSubtypeName != null) {
             subtype = createTestSubtype(subtypeListItem.mSubtypeName.toString());
         }
-        controller.onUserActionLocked(subtypeListItem.mImi, subtype);
+        return controller.onUserActionLocked(subtypeListItem.mImi, subtype);
     }
 
+    @RequiresFlagsDisabled(Flags.FLAG_IME_SWITCHER_REVAMP)
     @Test
     public void testControllerImpl() {
         final List<ImeSubtypeListItem> disabledItems = createDisabledImeSubtypes();
@@ -213,7 +229,7 @@ public final class InputMethodSubtypeSwitchingControllerTest {
         final ImeSubtypeListItem switchUnawareJapaneseIme_ja_jp = enabledItems.get(7);
 
         final ControllerImpl controller = ControllerImpl.createFrom(
-                null /* currentInstance */, enabledItems);
+                null /* currentInstance */, enabledItems, new ArrayList<>());
 
         // switching-aware loop
         assertRotationOrder(controller, false /* onlyCurrentIme */,
@@ -257,6 +273,7 @@ public final class InputMethodSubtypeSwitchingControllerTest {
                 disabledSubtypeUnawareIme, null);
     }
 
+    @RequiresFlagsDisabled(Flags.FLAG_IME_SWITCHER_REVAMP)
     @Test
     public void testControllerImplWithUserAction() {
         final List<ImeSubtypeListItem> enabledItems = createEnabledImeSubtypes();
@@ -270,7 +287,7 @@ public final class InputMethodSubtypeSwitchingControllerTest {
         final ImeSubtypeListItem switchUnawareJapaneseIme_ja_jp = enabledItems.get(7);
 
         final ControllerImpl controller = ControllerImpl.createFrom(
-                null /* currentInstance */, enabledItems);
+                null /* currentInstance */, enabledItems, new ArrayList<>());
 
         // === switching-aware loop ===
         assertRotationOrder(controller, false /* onlyCurrentIme */,
@@ -320,7 +337,7 @@ public final class InputMethodSubtypeSwitchingControllerTest {
         // Rotation order should be preserved when created with the same subtype list.
         final List<ImeSubtypeListItem> sameEnabledItems = createEnabledImeSubtypes();
         final ControllerImpl newController = ControllerImpl.createFrom(controller,
-                sameEnabledItems);
+                sameEnabledItems, new ArrayList<>());
         assertRotationOrder(newController, false /* onlyCurrentIme */,
                 subtypeAwareIme, latinIme_fr, latinIme_en_us, japaneseIme_ja_jp);
         assertRotationOrder(newController, false /* onlyCurrentIme */,
@@ -332,7 +349,7 @@ public final class InputMethodSubtypeSwitchingControllerTest {
                 latinIme_en_us, latinIme_fr, subtypeAwareIme, switchingUnawareLatinIme_en_uk,
                 switchUnawareJapaneseIme_ja_jp, subtypeUnawareIme);
         final ControllerImpl anotherController = ControllerImpl.createFrom(controller,
-                differentEnabledItems);
+                differentEnabledItems, new ArrayList<>());
         assertRotationOrder(anotherController, false /* onlyCurrentIme */,
                 latinIme_en_us, latinIme_fr, subtypeAwareIme);
         assertRotationOrder(anotherController, false /* onlyCurrentIme */,
@@ -471,4 +488,642 @@ public final class InputMethodSubtypeSwitchingControllerTest {
             assertNotEquals(ime2, ime1);
         }
     }
+
+    /** Verifies the static mode. */
+    @RequiresFlagsEnabled(Flags.FLAG_IME_SWITCHER_REVAMP)
+    @Test
+    public void testModeStatic() {
+        final var items = new ArrayList<ImeSubtypeListItem>();
+        addTestImeSubtypeListItems(items, "LatinIme", "LatinIme",
+                List.of("en", "fr", "it"), true /* supportsSwitchingToNextInputMethod */);
+        addTestImeSubtypeListItems(items, "SimpleIme", "SimpleIme",
+                null, true /* supportsSwitchingToNextInputMethod */);
+
+        final var english = items.get(0);
+        final var french = items.get(1);
+        final var italian = items.get(2);
+        final var simple = items.get(3);
+        final var latinIme = List.of(english, french, italian);
+        final var simpleIme = List.of(simple);
+
+        final var hardwareItems = new ArrayList<ImeSubtypeListItem>();
+        addTestImeSubtypeListItems(hardwareItems, "HardwareLatinIme", "HardwareLatinIme",
+                List.of("en", "fr", "it"), true /* supportsSwitchingToNextInputMethod */);
+        addTestImeSubtypeListItems(hardwareItems, "HardwareSimpleIme", "HardwareSimpleIme",
+                null, true /* supportsSwitchingToNextInputMethod */);
+
+        final var hardwareEnglish = hardwareItems.get(0);
+        final var hardwareFrench = hardwareItems.get(1);
+        final var hardwareItalian = hardwareItems.get(2);
+        final var hardwareSimple = hardwareItems.get(3);
+        final var hardwareLatinIme = List.of(hardwareEnglish, hardwareFrench, hardwareItalian);
+        final var hardwareSimpleIme = List.of(hardwareSimple);
+
+        final var controller = ControllerImpl.createFrom(null /* currentInstance */, items,
+                hardwareItems);
+
+        final int mode = MODE_STATIC;
+
+        // Static mode matches the given items order.
+        assertNextOrder(controller, false /* forHardware */, mode,
+                items, List.of(latinIme, simpleIme));
+
+        assertNextOrder(controller, true /* forHardware */, mode,
+                hardwareItems, List.of(hardwareLatinIme, hardwareSimpleIme));
+
+        // Set french IME as most recent.
+        assertTrue("Recency updated for french IME", onUserAction(controller, french));
+
+        // Static mode is not influenced by recency updates on non-hardware item.
+        assertNextOrder(controller, false /* forHardware */, mode,
+                items, List.of(latinIme, simpleIme));
+
+        assertNextOrder(controller, true /* forHardware */, mode,
+                hardwareItems, List.of(hardwareLatinIme, hardwareSimpleIme));
+
+        assertTrue("Recency updated for french hardware IME",
+                onUserAction(controller, hardwareFrench));
+
+        // Static mode is not influenced by recency updates on hardware item.
+        assertNextOrder(controller, false /* forHardware */, mode,
+                items, List.of(latinIme, simpleIme));
+
+        assertNextOrder(controller, true /* forHardware */, mode,
+                hardwareItems, List.of(hardwareLatinIme, hardwareSimpleIme));
+    }
+
+    /** Verifies the recency mode. */
+    @RequiresFlagsEnabled(Flags.FLAG_IME_SWITCHER_REVAMP)
+    @Test
+    public void testModeRecent() {
+        final var items = new ArrayList<ImeSubtypeListItem>();
+        addTestImeSubtypeListItems(items, "LatinIme", "LatinIme",
+                List.of("en", "fr", "it"), true /* supportsSwitchingToNextInputMethod */);
+        addTestImeSubtypeListItems(items, "SimpleIme", "SimpleIme",
+                null, true /* supportsSwitchingToNextInputMethod */);
+
+        final var english = items.get(0);
+        final var french = items.get(1);
+        final var italian = items.get(2);
+        final var simple = items.get(3);
+        final var latinIme = List.of(english, french, italian);
+        final var simpleIme = List.of(simple);
+
+        final var hardwareItems = new ArrayList<ImeSubtypeListItem>();
+        addTestImeSubtypeListItems(hardwareItems, "HardwareLatinIme", "HardwareLatinIme",
+                List.of("en", "fr", "it"), true /* supportsSwitchingToNextInputMethod */);
+        addTestImeSubtypeListItems(hardwareItems, "HardwareSimpleIme", "HardwareSimpleIme",
+                null, true /* supportsSwitchingToNextInputMethod */);
+
+        final var hardwareEnglish = hardwareItems.get(0);
+        final var hardwareFrench = hardwareItems.get(1);
+        final var hardwareItalian = hardwareItems.get(2);
+        final var hardwareSimple = hardwareItems.get(3);
+        final var hardwareLatinIme = List.of(hardwareEnglish, hardwareFrench, hardwareItalian);
+        final var hardwareSimpleIme = List.of(hardwareSimple);
+
+        final var controller = ControllerImpl.createFrom(null /* currentInstance */, items,
+                hardwareItems);
+
+        final int mode = MODE_RECENT;
+
+        // Recency order is initialized to static order.
+        assertNextOrder(controller, false /* forHardware */, mode,
+                items, List.of(latinIme, simpleIme));
+
+        assertNextOrder(controller, true /* forHardware */, mode,
+                hardwareItems, List.of(hardwareLatinIme, hardwareSimpleIme));
+
+        assertTrue("Recency updated for french IME", onUserAction(controller, french));
+        final var recencyItems = List.of(french, english, italian, simple);
+        final var recencyLatinIme = List.of(french, english, italian);
+        final var recencySimpleIme = List.of(simple);
+
+        // The order of non-hardware items is updated.
+        assertNextOrder(controller, false /* forHardware */, mode,
+                recencyItems, List.of(recencyLatinIme, recencySimpleIme));
+
+        // The order of hardware items remains unchanged for an action on a non-hardware item.
+        assertNextOrder(controller, true /* forHardware */, mode,
+                hardwareItems, List.of(hardwareLatinIme, hardwareSimpleIme));
+
+        assertFalse("Recency not updated again for same IME", onUserAction(controller, french));
+
+        // The order of non-hardware items remains unchanged.
+        assertNextOrder(controller, false /* forHardware */, mode,
+                recencyItems, List.of(recencyLatinIme, recencySimpleIme));
+
+        // The order of hardware items remains unchanged.
+        assertNextOrder(controller, true /* forHardware */, mode,
+                hardwareItems, List.of(hardwareLatinIme, hardwareSimpleIme));
+
+        assertTrue("Recency updated for french hardware IME",
+                onUserAction(controller, hardwareFrench));
+
+        final var recencyHardwareItems =
+                List.of(hardwareFrench, hardwareEnglish, hardwareItalian, hardwareSimple);
+        final var recencyHardwareLatinIme =
+                List.of(hardwareFrench, hardwareEnglish, hardwareItalian);
+        final var recencyHardwareSimpleIme = List.of(hardwareSimple);
+
+        // The order of non-hardware items is unchanged.
+        assertNextOrder(controller, false /* forHardware */, mode,
+                recencyItems, List.of(recencyLatinIme, recencySimpleIme));
+
+        // The order of hardware items is updated.
+        assertNextOrder(controller, true /* forHardware */, mode,
+                recencyHardwareItems, List.of(recencyHardwareLatinIme, recencyHardwareSimpleIme));
+    }
+
+    /** Verifies the auto mode. */
+    @RequiresFlagsEnabled(Flags.FLAG_IME_SWITCHER_REVAMP)
+    @Test
+    public void testModeAuto() {
+        final var items = new ArrayList<ImeSubtypeListItem>();
+        addTestImeSubtypeListItems(items, "LatinIme", "LatinIme",
+                List.of("en", "fr", "it"), true /* supportsSwitchingToNextInputMethod */);
+        addTestImeSubtypeListItems(items, "SimpleIme", "SimpleIme",
+                null, true /* supportsSwitchingToNextInputMethod */);
+
+        final var english = items.get(0);
+        final var french = items.get(1);
+        final var italian = items.get(2);
+        final var simple = items.get(3);
+        final var latinIme = List.of(english, french, italian);
+        final var simpleIme = List.of(simple);
+
+        final var hardwareItems = new ArrayList<ImeSubtypeListItem>();
+        addTestImeSubtypeListItems(hardwareItems, "HardwareLatinIme", "HardwareLatinIme",
+                List.of("en", "fr", "it"), true /* supportsSwitchingToNextInputMethod */);
+        addTestImeSubtypeListItems(hardwareItems, "HardwareSimpleIme", "HardwareSimpleIme",
+                null, true /* supportsSwitchingToNextInputMethod */);
+
+        final var hardwareEnglish = hardwareItems.get(0);
+        final var hardwareFrench = hardwareItems.get(1);
+        final var hardwareItalian = hardwareItems.get(2);
+        final var hardwareSimple = hardwareItems.get(3);
+        final var hardwareLatinIme = List.of(hardwareEnglish, hardwareFrench, hardwareItalian);
+        final var hardwareSimpleIme = List.of(hardwareSimple);
+
+        final var controller = ControllerImpl.createFrom(null /* currentInstance */, items,
+                hardwareItems);
+
+        final int mode = MODE_AUTO;
+
+        // Auto mode resolves to static order initially.
+        assertNextOrder(controller, false /* forHardware */, mode,
+                items, List.of(latinIme, simpleIme));
+
+        assertNextOrder(controller, true /* forHardware */, mode,
+                hardwareItems, List.of(hardwareLatinIme, hardwareSimpleIme));
+
+        // User action on french IME.
+        assertTrue("Recency updated for french IME", onUserAction(controller, french));
+
+        final var recencyItems = List.of(french, english, italian, simple);
+        final var recencyLatinIme = List.of(french, english, italian);
+        final var recencySimpleIme = List.of(simple);
+
+        // Auto mode resolves to recency order for the first forward after user action, and to
+        // static order for the backwards direction.
+        assertNextOrder(controller, false /* forHardware */, mode, true /* forward */,
+                recencyItems, List.of(recencyLatinIme, recencySimpleIme));
+        assertNextOrder(controller, false /* forHardware */, mode, false /* forward */,
+                items.reversed(), List.of(latinIme.reversed(), simpleIme.reversed()));
+
+        // Auto mode resolves to recency order for the first forward after user action,
+        // but the recency was not updated for hardware items, so it's equivalent to static order.
+        assertNextOrder(controller, true /* forHardware */, mode,
+                hardwareItems, List.of(hardwareLatinIme, hardwareSimpleIme));
+
+        // Change IME, reset user action having happened.
+        controller.onInputMethodSubtypeChanged();
+
+        // Auto mode resolves to static order as there was no user action since changing IMEs.
+        assertNextOrder(controller, false /* forHardware */, mode,
+                items, List.of(latinIme, simpleIme));
+
+        assertNextOrder(controller, true /* forHardware */, mode,
+                hardwareItems, List.of(hardwareLatinIme, hardwareSimpleIme));
+
+        // User action on french IME again.
+        assertFalse("Recency not updated again for same IME", onUserAction(controller, french));
+
+        // Auto mode still resolves to static order, as a user action on the currently most
+        // recent IME has no effect.
+        assertNextOrder(controller, false /* forHardware */, mode,
+                items, List.of(latinIme, simpleIme));
+
+        assertNextOrder(controller, true /* forHardware */, mode,
+                hardwareItems, List.of(hardwareLatinIme, hardwareSimpleIme));
+
+        // User action on hardware french IME.
+        assertTrue("Recency updated for french hardware IME",
+                onUserAction(controller, hardwareFrench));
+
+        final var recencyHardware =
+                List.of(hardwareFrench, hardwareEnglish, hardwareItalian, hardwareSimple);
+        final var recencyHardwareLatin =
+                List.of(hardwareFrench, hardwareEnglish, hardwareItalian);
+        final var recencyHardwareSimple = List.of(hardwareSimple);
+
+        // Auto mode resolves to recency order for the first forward direction after a user action
+        // on a hardware IME, and to static order for the backwards direction.
+        assertNextOrder(controller, false /* forHardware */, mode, true /* forward */,
+                recencyItems, List.of(recencyLatinIme, recencySimpleIme));
+        assertNextOrder(controller, false /* forHardware */, mode, false /* forward */,
+                items.reversed(), List.of(latinIme.reversed(), simpleIme.reversed()));
+
+        assertNextOrder(controller, true /* forHardware */, mode, true /* forward */,
+                recencyHardware, List.of(recencyHardwareLatin, recencyHardwareSimple));
+
+        assertNextOrder(controller, true /* forHardware */, mode, false /* forward */,
+                hardwareItems.reversed(),
+                List.of(hardwareLatinIme.reversed(), hardwareSimpleIme.reversed()));
+    }
+
+    /**
+     * Verifies that the recency order is preserved only when updating with an equal list of items.
+     */
+    @RequiresFlagsEnabled(Flags.FLAG_IME_SWITCHER_REVAMP)
+    @Test
+    public void testUpdateList() {
+        final var items = new ArrayList<ImeSubtypeListItem>();
+        addTestImeSubtypeListItems(items, "LatinIme", "LatinIme",
+                List.of("en", "fr", "it"), true /* supportsSwitchingToNextInputMethod */);
+        addTestImeSubtypeListItems(items, "SimpleIme", "SimpleIme",
+                null, true /* supportsSwitchingToNextInputMethod */);
+
+        final var english = items.get(0);
+        final var french = items.get(1);
+        final var italian = items.get(2);
+        final var simple = items.get(3);
+
+        final var latinIme = List.of(english, french, italian);
+        final var simpleIme = List.of(simple);
+
+        final var hardwareItems = new ArrayList<ImeSubtypeListItem>();
+        addTestImeSubtypeListItems(hardwareItems, "HardwareLatinIme", "HardwareLatinIme",
+                List.of("en", "fr", "it"), true /* supportsSwitchingToNextInputMethod */);
+        addTestImeSubtypeListItems(hardwareItems, "HardwareSimpleIme", "HardwareSimpleIme",
+                null, true /* supportsSwitchingToNextInputMethod */);
+
+        final var hardwareEnglish = hardwareItems.get(0);
+        final var hardwareFrench = hardwareItems.get(1);
+        final var hardwareItalian = hardwareItems.get(2);
+        final var hardwareSimple = hardwareItems.get(3);
+
+        final var hardwareLatinIme = List.of(hardwareEnglish, hardwareFrench, hardwareItalian);
+        final var hardwareSimpleIme = List.of(hardwareSimple);
+
+        final var controller = ControllerImpl.createFrom(null /* currentInstance */, items,
+                hardwareItems);
+
+        final int mode = MODE_RECENT;
+
+        // Recency order is initialized to static order.
+        assertNextOrder(controller, false /* forHardware */, mode,
+                items, List.of(latinIme, simpleIme));
+
+        assertNextOrder(controller, true /* forHardware */, mode,
+                hardwareItems, List.of(hardwareLatinIme, hardwareSimpleIme));
+
+        // User action on french IME.
+        assertTrue("Recency updated for french IME", onUserAction(controller, french));
+
+        final var equalItems = new ArrayList<>(items);
+        final var otherItems = new ArrayList<>(items);
+        otherItems.remove(simple);
+
+        final var equalController = ControllerImpl.createFrom(controller, equalItems,
+                hardwareItems);
+        final var otherController = ControllerImpl.createFrom(controller, otherItems,
+                hardwareItems);
+
+        final var recencyItems = List.of(french, english, italian, simple);
+        final var recencyLatinIme = List.of(french, english, italian);
+        final var recencySimpleIme = List.of(simple);
+
+        assertNextOrder(controller, false /* forHardware */, mode,
+                recencyItems, List.of(recencyLatinIme, recencySimpleIme));
+
+        // The order of equal non-hardware items is unchanged.
+        assertNextOrder(equalController, false /* forHardware */, mode,
+                recencyItems, List.of(recencyLatinIme, recencySimpleIme));
+
+        // The order of other hardware items is reset.
+        assertNextOrder(otherController, false /* forHardware */, mode,
+                latinIme, List.of(latinIme));
+
+        // The order of hardware remains unchanged.
+        assertNextOrder(controller, true /* forHardware */, mode,
+                hardwareItems, List.of(hardwareLatinIme, hardwareSimpleIme));
+
+        assertNextOrder(equalController, true /* forHardware */, mode,
+                hardwareItems, List.of(hardwareLatinIme, hardwareSimpleIme));
+
+        assertNextOrder(otherController, true /* forHardware */, mode,
+                hardwareItems, List.of(hardwareLatinIme, hardwareSimpleIme));
+
+        assertTrue("Recency updated for french hardware IME",
+                onUserAction(controller, hardwareFrench));
+
+        final var equalHardwareItems = new ArrayList<>(hardwareItems);
+        final var otherHardwareItems = new ArrayList<>(hardwareItems);
+        otherHardwareItems.remove(hardwareSimple);
+
+        final var equalHardwareController = ControllerImpl.createFrom(controller, items,
+                equalHardwareItems);
+        final var otherHardwareController = ControllerImpl.createFrom(controller, items,
+                otherHardwareItems);
+
+        final var recencyHardwareItems =
+                List.of(hardwareFrench, hardwareEnglish, hardwareItalian, hardwareSimple);
+        final var recencyHardwareLatinIme =
+                List.of(hardwareFrench, hardwareEnglish, hardwareItalian);
+        final var recencyHardwareSimpleIme = List.of(hardwareSimple);
+
+        // The order of non-hardware items remains unchanged.
+        assertNextOrder(controller, false /* forHardware */, mode,
+                recencyItems, List.of(recencyLatinIme, recencySimpleIme));
+
+        assertNextOrder(equalHardwareController, false /* forHardware */, mode,
+                recencyItems, List.of(recencyLatinIme, recencySimpleIme));
+
+        assertNextOrder(otherHardwareController, false /* forHardware */, mode,
+                recencyItems, List.of(recencyLatinIme, recencySimpleIme));
+
+        assertNextOrder(controller, true /* forHardware */, mode,
+                recencyHardwareItems, List.of(recencyHardwareLatinIme, recencyHardwareSimpleIme));
+
+        // The order of equal hardware items is unchanged.
+        assertNextOrder(equalHardwareController, true /* forHardware */, mode,
+                recencyHardwareItems, List.of(recencyHardwareLatinIme, recencyHardwareSimpleIme));
+
+        // The order of other hardware items is reset.
+        assertNextOrder(otherHardwareController, true /* forHardware */, mode,
+                hardwareLatinIme, List.of(hardwareLatinIme));
+    }
+
+    /** Verifies that switch aware and switch unaware IMEs are combined together. */
+    @RequiresFlagsEnabled(Flags.FLAG_IME_SWITCHER_REVAMP)
+    @Test
+    public void testSwitchAwareAndUnawareCombined() {
+        final var items = new ArrayList<ImeSubtypeListItem>();
+        addTestImeSubtypeListItems(items, "switchAware", "switchAware",
+                null, true /* supportsSwitchingToNextInputMethod*/);
+        addTestImeSubtypeListItems(items, "switchUnaware", "switchUnaware",
+                null, false /* supportsSwitchingToNextInputMethod*/);
+
+        final var hardwareItems = new ArrayList<ImeSubtypeListItem>();
+        addTestImeSubtypeListItems(hardwareItems, "hardwareSwitchAware", "hardwareSwitchAware",
+                null, true /* supportsSwitchingToNextInputMethod*/);
+        addTestImeSubtypeListItems(hardwareItems, "hardwareSwitchUnaware", "hardwareSwitchUnaware",
+                null, false /* supportsSwitchingToNextInputMethod*/);
+
+        final var controller = ControllerImpl.createFrom(null /* currentInstance */, items,
+                hardwareItems);
+
+        for (int mode = MODE_STATIC; mode <= MODE_AUTO; mode++) {
+            assertNextOrder(controller, false /* forHardware */, false /* onlyCurrentIme */,
+                    mode, true /* forward */, items);
+            assertNextOrder(controller, false /* forHardware */, false /* onlyCurrentIme */,
+                    mode, false /* forward */, items.reversed());
+
+            assertNextOrder(controller, true /* forHardware */, false /* onlyCurrentIme */,
+                    mode, true /* forward */, hardwareItems);
+            assertNextOrder(controller, true /* forHardware */, false /* onlyCurrentIme */,
+                    mode, false /* forward */, hardwareItems.reversed());
+        }
+    }
+
+    /** Verifies that an empty controller can't take any actions. */
+    @RequiresFlagsEnabled(Flags.FLAG_IME_SWITCHER_REVAMP)
+    @Test
+    public void testEmptyList() {
+        final var items = new ArrayList<ImeSubtypeListItem>();
+        addTestImeSubtypeListItems(items, "LatinIme", "LatinIme",
+                List.of("en", "fr"), true /* supportsSwitchingToNextInputMethod */);
+
+        final var hardwareItems = new ArrayList<ImeSubtypeListItem>();
+        addTestImeSubtypeListItems(hardwareItems, "HardwareIme", "HardwareIme",
+                List.of("en", "fr"), true /* supportsSwitchingToNextInputMethod */);
+
+        final var controller = ControllerImpl.createFrom(null /* currentInstance */, List.of(),
+                List.of());
+
+        assertNoAction(controller, false /* forHardware */, items);
+        assertNoAction(controller, true /* forHardware */, hardwareItems);
+    }
+
+    /** Verifies that a controller with a single item can't take any actions. */
+    @RequiresFlagsEnabled(Flags.FLAG_IME_SWITCHER_REVAMP)
+    @Test
+    public void testSingleItemList() {
+        final var items = new ArrayList<ImeSubtypeListItem>();
+        addTestImeSubtypeListItems(items, "LatinIme", "LatinIme",
+                List.of("en", "fr"), true /* supportsSwitchingToNextInputMethod */);
+
+        final var hardwareItems = new ArrayList<ImeSubtypeListItem>();
+        addTestImeSubtypeListItems(hardwareItems, "HardwareIme", "HardwareIme",
+                List.of("en", "fr"), true /* supportsSwitchingToNextInputMethod */);
+
+        final var controller = ControllerImpl.createFrom(null /* currentInstance */,
+                List.of(items.get(0)), List.of(hardwareItems.get(0)));
+
+        assertNoAction(controller, false /* forHardware */, items);
+        assertNoAction(controller, true /* forHardware */, hardwareItems);
+    }
+
+    /** Verifies that a controller can't take any actions for unknown items. */
+    @RequiresFlagsEnabled(Flags.FLAG_IME_SWITCHER_REVAMP)
+    @Test
+    public void testUnknownItems() {
+        final var items = new ArrayList<ImeSubtypeListItem>();
+        addTestImeSubtypeListItems(items, "LatinIme", "LatinIme",
+                List.of("en", "fr"), true /* supportsSwitchingToNextInputMethod */);
+        final var unknownItems = new ArrayList<ImeSubtypeListItem>();
+        addTestImeSubtypeListItems(unknownItems, "UnknownIme", "UnknownIme",
+                List.of("en", "fr"), true /* supportsSwitchingToNextInputMethod */);
+
+        final var hardwareItems = new ArrayList<ImeSubtypeListItem>();
+        addTestImeSubtypeListItems(hardwareItems, "HardwareIme", "HardwareIme",
+                List.of("en", "fr"), true /* supportsSwitchingToNextInputMethod */);
+        final var unknownHardwareItems = new ArrayList<ImeSubtypeListItem>();
+        addTestImeSubtypeListItems(unknownHardwareItems, "HardwareUnknownIme", "HardwareUnknownIme",
+                List.of("en", "fr"), true /* supportsSwitchingToNextInputMethod */);
+
+        final var controller = ControllerImpl.createFrom(null /* currentInstance */, items,
+                hardwareItems);
+
+        assertNoAction(controller, false /* forHardware */, unknownItems);
+        assertNoAction(controller, true /* forHardware */, unknownHardwareItems);
+    }
+
+    /**
+     * Verifies that the controller's next item order matches the given one, and cycles back at
+     * the end, both across all IMEs, and also per each IME. If a single item is given, verifies
+     * that no next item is returned.
+     *
+     * @param controller  the controller to use for finding the next items.
+     * @param forHardware whether to find the next hardware item, or software item.
+     * @param mode        the switching mode.
+     * @param forward     whether to search forwards or backwards in the list.
+     * @param allItems    the list of items across all IMEs.
+     * @param perImeItems the list of lists of items per IME.
+     */
+    private static void assertNextOrder(@NonNull ControllerImpl controller, boolean forHardware,
+            @SwitchMode int mode, boolean forward, @NonNull List<ImeSubtypeListItem> allItems,
+            @NonNull List<List<ImeSubtypeListItem>> perImeItems) {
+        assertNextOrder(controller, forHardware, false /* onlyCurrentIme */, mode,
+                forward, allItems);
+
+        for (var imeItems : perImeItems) {
+            assertNextOrder(controller, forHardware, true /* onlyCurrentIme */, mode,
+                    forward, imeItems);
+        }
+    }
+
+    /**
+     * Verifies that the controller's next item order matches the given one, and cycles back at
+     * the end, both across all IMEs, and also per each IME. This checks the forward direction
+     * with the given items, and the backwards order with the items reversed. If a single item is
+     * given, verifies that no next item is returned.
+     *
+     * @param controller  the controller to use for finding the next items.
+     * @param forHardware whether to find the next hardware item, or software item.
+     * @param mode        the switching mode.
+     * @param allItems    the list of items across all IMEs.
+     * @param perImeItems the list of lists of items per IME.
+     */
+    private static void assertNextOrder(@NonNull ControllerImpl controller, boolean forHardware,
+            @SwitchMode int mode, @NonNull List<ImeSubtypeListItem> allItems,
+            @NonNull List<List<ImeSubtypeListItem>> perImeItems) {
+        assertNextOrder(controller, forHardware, false /* onlyCurrentIme */, mode,
+                true /* forward */, allItems);
+        assertNextOrder(controller, forHardware, false /* onlyCurrentIme */, mode,
+                false /* forward */, allItems.reversed());
+
+        for (var imeItems : perImeItems) {
+            assertNextOrder(controller, forHardware, true /* onlyCurrentIme */, mode,
+                    true /* forward */, imeItems);
+            assertNextOrder(controller, forHardware, true /* onlyCurrentIme */, mode,
+                    false /* forward */, imeItems.reversed());
+        }
+    }
+
+    /**
+     * Verifies that the controller's next item order (starting from the first one in {@code items}
+     * matches the given on, and cycles back at the end. If a single item is given, verifies that
+     * no next item is returned.
+     *
+     * @param controller     the controller to use for finding the next items.
+     * @param forHardware    whether to find the next hardware item, or software item.
+     * @param onlyCurrentIme whether to consider only subtypes of the current input method.
+     * @param mode           the switching mode.
+     * @param forward        whether to search forwards or backwards in the list.
+     * @param items          the list of items to verify, in the expected order.
+     */
+    private static void assertNextOrder(@NonNull ControllerImpl controller,
+            boolean forHardware, boolean onlyCurrentIme, @SwitchMode int mode, boolean forward,
+            @NonNull List<ImeSubtypeListItem> items) {
+        final int numItems = items.size();
+        if (numItems == 0) {
+            return;
+        } else if (numItems == 1) {
+            // Single item controllers should never return a next item.
+            assertNextItem(controller, forHardware, onlyCurrentIme, mode, forward, items.get(0),
+                    null /* expectedNext*/);
+            return;
+        }
+
+        var item = items.get(0);
+
+        final var expectedNextItems = new ArrayList<>(items);
+        // Add first item in the last position of expected order, to ensure the order is cyclic.
+        expectedNextItems.add(item);
+
+        final var nextItems = new ArrayList<>();
+        // Add first item in the first position of actual order, to ensure the order is cyclic.
+        nextItems.add(item);
+
+        // Compute the nextItems starting from the first given item, and compare the order.
+        for (int i = 0; i < numItems; i++) {
+            item = getNextItem(controller, forHardware, onlyCurrentIme, mode, forward, item);
+            assertNotNull("Next item shouldn't be null.", item);
+            nextItems.add(item);
+        }
+
+        assertEquals("Rotation order doesn't match.", expectedNextItems, nextItems);
+    }
+
+    /**
+     * Verifies that the controller gets the expected next value from the given item.
+     *
+     * @param controller     the controller to sue for finding the next value.
+     * @param forHardware    whether to find the next hardware item, or software item.
+     * @param onlyCurrentIme whether to consider only subtypes of the current input method.
+     * @param mode           the switching mode.
+     * @param forward        whether to search forwards or backwards in the list.
+     * @param item           the item to find the next value from.
+     * @param expectedNext   the expected next value.
+     */
+    private static void assertNextItem(@NonNull ControllerImpl controller,
+            boolean forHardware, boolean onlyCurrentIme, @SwitchMode int mode, boolean forward,
+            @NonNull ImeSubtypeListItem item, @Nullable ImeSubtypeListItem expectedNext) {
+        final var nextItem = getNextItem(controller, forHardware, onlyCurrentIme, mode, forward,
+                item);
+        assertEquals("Next item doesn't match.", expectedNext, nextItem);
+    }
+
+    /**
+     * Gets the next value from the given item.
+     *
+     * @param controller     the controller to use for finding the next value.
+     * @param forHardware    whether to find the next hardware item, or software item.
+     * @param onlyCurrentIme whether to consider only subtypes of the current input method.
+     * @param mode           the switching mode.
+     * @param forward        whether to search forwards or backwards in the list.
+     * @param item           the item to find the next value from.
+     * @return the next item found, otherwise {@code null}.
+     */
+    @Nullable
+    private static ImeSubtypeListItem getNextItem(@NonNull ControllerImpl controller,
+            boolean forHardware, boolean onlyCurrentIme, @SwitchMode int mode, boolean forward,
+            @NonNull ImeSubtypeListItem item) {
+        final var subtype = item.mSubtypeName != null
+                ? createTestSubtype(item.mSubtypeName.toString()) : null;
+        return forHardware
+                ? controller.getNextInputMethodForHardware(
+                        onlyCurrentIme, item.mImi, subtype, mode, forward)
+                : controller.getNextInputMethod(
+                        onlyCurrentIme, item.mImi, subtype, mode, forward);
+    }
+
+    /**
+     * Verifies that no next items can be found, and the recency cannot be updated for the
+     * given items.
+     *
+     * @param controller  the controller to verify the items on.
+     * @param forHardware whether to try finding the next hardware item, or software item.
+     * @param items       the list of items to verify.
+     */
+    private void assertNoAction(@NonNull ControllerImpl controller, boolean forHardware,
+            @NonNull List<ImeSubtypeListItem> items) {
+        for (var item : items) {
+            for (int mode = MODE_STATIC; mode <= MODE_AUTO; mode++) {
+                assertNextItem(controller, forHardware, false /* onlyCurrentIme */, mode,
+                        false /* forward */, item, null /* expectedNext */);
+                assertNextItem(controller, forHardware, false /* onlyCurrentIme */, mode,
+                        true /* forward */, item, null /* expectedNext */);
+                assertNextItem(controller, forHardware, true /* onlyCurrentIme */, mode,
+                        false /* forward */, item, null /* expectedNext */);
+                assertNextItem(controller, forHardware, true /* onlyCurrentIme */, mode,
+                        true /* forward */, item, null /* expectedNext */);
+            }
+
+            assertFalse("User action shouldn't have updated the recency.",
+                    onUserAction(controller, item));
+        }
+    }
 }