Implement dynamic IME rotation based on user action

With this CL, the IME rotation order will be updated dynamically
based on user actions on IMEs. Currently only onCommitText is
took into considered.

Imagine that we have the following rotation order.
  [A, B, C, D, E]
If a user action for C is observed, the rotation order will be
updated as follows:
  [C, A, B, D, E]
Then another user action for D updates the rotation order as
follows:
  [D, C, A, B, E]

BUG: 7043015
Change-Id: Ic005b94379f9d847ea87046473ed77d8018d930e

2 files changed, 182 insertions, 25 deletions

diff --git a/core/java/com/android/internal/inputmethod/InputMethodSubtypeSwitchingController.java b/core/java/com/android/internal/inputmethod/InputMethodSubtypeSwitchingController.java
index 70c77b8..bfa5c22 100644
--- a/core/java/com/android/internal/inputmethod/InputMethodSubtypeSwitchingController.java
+++ b/core/java/com/android/internal/inputmethod/InputMethodSubtypeSwitchingController.java
@@ -271,13 +271,87 @@ public class InputMethodSubtypeSwitchingController {
         }
     }
 
+    private static class DynamicRotationList {
+        private static final String TAG = DynamicRotationList.class.getSimpleName();
+        private final List<ImeSubtypeListItem> mImeSubtypeList;
+        private final int[] mUsageHistoryOfSubtypeListItemIndex;
+
+        public DynamicRotationList(final List<ImeSubtypeListItem> imeSubtypeListItems) {
+            mImeSubtypeList = imeSubtypeListItems;
+            mUsageHistoryOfSubtypeListItemIndex = new int[mImeSubtypeList.size()];
+            final int N = mImeSubtypeList.size();
+            for (int i = 0; i < N; i++) {
+                mUsageHistoryOfSubtypeListItemIndex[i] = i;
+            }
+        }
+
+        /**
+         * Returns the index of the specified object in
+         * {@link #mUsageHistoryOfSubtypeListItemIndex}.
+         * <p>We call the index of {@link #mUsageHistoryOfSubtypeListItemIndex} as "Usage Rank"
+         * so as not to be confused with the index in {@link #mImeSubtypeList}.
+         * @return -1 when the specified item doesn't belong to {@link #mImeSubtypeList} actually.
+         */
+        private int getUsageRank(final InputMethodInfo imi, InputMethodSubtype subtype) {
+            final int currentSubtypeId = calculateSubtypeId(imi, subtype);
+            final int N = mUsageHistoryOfSubtypeListItemIndex.length;
+            for (int usageRank = 0; usageRank < N; usageRank++) {
+                final int subtypeListItemIndex = mUsageHistoryOfSubtypeListItemIndex[usageRank];
+                final ImeSubtypeListItem subtypeListItem =
+                        mImeSubtypeList.get(subtypeListItemIndex);
+                if (subtypeListItem.mImi.equals(imi) &&
+                        subtypeListItem.mSubtypeId == currentSubtypeId) {
+                    return usageRank;
+                }
+            }
+            // Not found in the known IME/Subtype list.
+            return -1;
+        }
+
+        public void onUserAction(InputMethodInfo imi, InputMethodSubtype subtype) {
+            final int currentUsageRank = getUsageRank(imi, subtype);
+            // Do nothing if currentUsageRank == -1 (not found), or currentUsageRank == 0
+            if (currentUsageRank <= 0) {
+                return;
+            }
+            final int currentItemIndex = mUsageHistoryOfSubtypeListItemIndex[currentUsageRank];
+            System.arraycopy(mUsageHistoryOfSubtypeListItemIndex, 0,
+                    mUsageHistoryOfSubtypeListItemIndex, 1, currentUsageRank);
+            mUsageHistoryOfSubtypeListItemIndex[0] = currentItemIndex;
+        }
+
+        public ImeSubtypeListItem getNextInputMethodLocked(boolean onlyCurrentIme,
+                InputMethodInfo imi, InputMethodSubtype subtype) {
+            int currentUsageRank = getUsageRank(imi, subtype);
+            if (currentUsageRank < 0) {
+                if (DEBUG) {
+                    Slog.d(TAG, "IME/subtype is not found: " + imi.getId() + ", " + subtype);
+                }
+                return null;
+            }
+            final int N = mUsageHistoryOfSubtypeListItemIndex.length;
+            for (int i = 1; i < N; i++) {
+                final int subtypeListItemRank = (currentUsageRank + i) % N;
+                final int subtypeListItemIndex =
+                        mUsageHistoryOfSubtypeListItemIndex[subtypeListItemRank];
+                final ImeSubtypeListItem subtypeListItem =
+                        mImeSubtypeList.get(subtypeListItemIndex);
+                if (onlyCurrentIme && !imi.equals(subtypeListItem.mImi)) {
+                    continue;
+                }
+                return subtypeListItem;
+            }
+            return null;
+        }
+    }
+
     @VisibleForTesting
     public static class ControllerImpl {
-        private final StaticRotationList mSwitchingAwareSubtypeList;
+        private final DynamicRotationList mSwitchingAwareSubtypeList;
         private final StaticRotationList mSwitchingUnawareSubtypeList;
 
         public ControllerImpl(final List<ImeSubtypeListItem> sortedItems) {
-            mSwitchingAwareSubtypeList = new StaticRotationList(filterImeSubtypeList(sortedItems,
+            mSwitchingAwareSubtypeList = new DynamicRotationList(filterImeSubtypeList(sortedItems,
                     true /* supportsSwitchingToNextInputMethod */));
             mSwitchingUnawareSubtypeList = new StaticRotationList(filterImeSubtypeList(sortedItems,
                     false /* supportsSwitchingToNextInputMethod */));
@@ -297,6 +371,15 @@ public class InputMethodSubtypeSwitchingController {
             }
         }
 
+        public void onUserActionLocked(InputMethodInfo imi, InputMethodSubtype subtype) {
+            if (imi == null) {
+                return;
+            }
+            if (imi.supportsSwitchingToNextInputMethod()) {
+                mSwitchingAwareSubtypeList.onUserAction(imi, subtype);
+            }
+        }
+
         private static List<ImeSubtypeListItem> filterImeSubtypeList(
                 final List<ImeSubtypeListItem> items,
                 final boolean supportsSwitchingToNextInputMethod) {
@@ -327,9 +410,14 @@ public class InputMethodSubtypeSwitchingController {
         return new InputMethodSubtypeSwitchingController(settings, context);
     }
 
-    // TODO: write unit tests for this method and the logic that determines the next subtype
     public void onCommitTextLocked(InputMethodInfo imi, InputMethodSubtype subtype) {
-        // TODO: Implement this.
+        if (mController == null) {
+            if (DEBUG) {
+                Log.e(TAG, "mController shouldn't be null.");
+            }
+            return;
+        }
+        mController.onUserActionLocked(imi, subtype);
     }
 
     public void resetCircularListLocked(Context context) {
diff --git a/core/tests/inputmethodtests/src/android/os/InputMethodSubtypeSwitchingControllerTest.java b/core/tests/inputmethodtests/src/android/os/InputMethodSubtypeSwitchingControllerTest.java
index 459bed5..04cfe05 100644
--- a/core/tests/inputmethodtests/src/android/os/InputMethodSubtypeSwitchingControllerTest.java
+++ b/core/tests/inputmethodtests/src/android/os/InputMethodSubtypeSwitchingControllerTest.java
@@ -132,6 +132,29 @@ public class InputMethodSubtypeSwitchingControllerTest extends InstrumentationTe
         assertEquals(nextItem, nextIme);
     }
 
+    private void assertRotationOrder(final ControllerImpl controller,
+            final boolean onlyCurrentIme,
+            final ImeSubtypeListItem... expectedRotationOrderOfImeSubtypeList) {
+        final int N = expectedRotationOrderOfImeSubtypeList.length;
+        for (int i = 0; i < N; i++) {
+            final int currentIndex = i;
+            final int nextIndex = (currentIndex + 1) % N;
+            final ImeSubtypeListItem currentItem =
+                    expectedRotationOrderOfImeSubtypeList[currentIndex];
+            final ImeSubtypeListItem nextItem = expectedRotationOrderOfImeSubtypeList[nextIndex];
+            assertNextInputMethod(controller, onlyCurrentIme, currentItem, nextItem);
+        }
+    }
+
+    private void onUserAction(final ControllerImpl controller,
+            final ImeSubtypeListItem subtypeListItem) {
+        InputMethodSubtype subtype = null;
+        if (subtypeListItem.mSubtypeName != null) {
+            subtype = createDummySubtype(subtypeListItem.mSubtypeName.toString());
+        }
+        controller.onUserActionLocked(subtypeListItem.mImi, subtype);
+    }
+
     @SmallTest
     public void testControllerImpl() throws Exception {
         final List<ImeSubtypeListItem> disabledItems = createDisabledImeSubtypes();
@@ -152,33 +175,20 @@ public class InputMethodSubtypeSwitchingControllerTest extends InstrumentationTe
         final ControllerImpl controller = new ControllerImpl(enabledItems);
 
         // switching-aware loop
-        assertNextInputMethod(controller, false /* onlyCurrentIme */,
-                latinIme_en_US, latinIme_fr);
-        assertNextInputMethod(controller, false /* onlyCurrentIme */,
-                latinIme_fr, japaneseIme_ja_JP);
-        assertNextInputMethod(controller, false /* onlyCurrentIme */,
-                japaneseIme_ja_JP, latinIme_en_US);
+        assertRotationOrder(controller, false /* onlyCurrentIme */,
+                latinIme_en_US, latinIme_fr, japaneseIme_ja_JP);
 
         // switching-unaware loop
-        assertNextInputMethod(controller, false /* onlyCurrentIme */,
-                switchingUnawarelatinIme_en_UK, switchingUnawarelatinIme_hi);
-        assertNextInputMethod(controller, false /* onlyCurrentIme */,
-                switchingUnawarelatinIme_hi, subtypeUnawareIme);
-        assertNextInputMethod(controller, false /* onlyCurrentIme */,
-                subtypeUnawareIme, switchUnawareJapaneseIme_ja_JP);
-        assertNextInputMethod(controller, false /* onlyCurrentIme */,
-                switchUnawareJapaneseIme_ja_JP, switchingUnawarelatinIme_en_UK);
+        assertRotationOrder(controller, false /* onlyCurrentIme */,
+                switchingUnawarelatinIme_en_UK, switchingUnawarelatinIme_hi, subtypeUnawareIme,
+                switchUnawareJapaneseIme_ja_JP);
 
         // test onlyCurrentIme == true
-        assertNextInputMethod(controller, true /* onlyCurrentIme */,
+        assertRotationOrder(controller, true /* onlyCurrentIme */,
                 latinIme_en_US, latinIme_fr);
-        assertNextInputMethod(controller, true /* onlyCurrentIme */,
-                latinIme_fr, latinIme_en_US);
-        assertNextInputMethod(controller, true /* onlyCurrentIme */,
+        assertRotationOrder(controller, true /* onlyCurrentIme */,
                 switchingUnawarelatinIme_en_UK, switchingUnawarelatinIme_hi);
         assertNextInputMethod(controller, true /* onlyCurrentIme */,
-                switchingUnawarelatinIme_hi, switchingUnawarelatinIme_en_UK);
-        assertNextInputMethod(controller, true /* onlyCurrentIme */,
                 subtypeUnawareIme, null);
         assertNextInputMethod(controller, true /* onlyCurrentIme */,
                 japaneseIme_ja_JP, null);
@@ -203,4 +213,63 @@ public class InputMethodSubtypeSwitchingControllerTest extends InstrumentationTe
         assertNextInputMethod(controller, true /* onlyCurrentIme */,
                 disabledSubtypeUnawareIme, null);
     }
- }
+
+    @SmallTest
+    public void testControllerImplWithUserAction() throws Exception {
+        final List<ImeSubtypeListItem> enabledItems = createEnabledImeSubtypes();
+        final ImeSubtypeListItem latinIme_en_US = enabledItems.get(0);
+        final ImeSubtypeListItem latinIme_fr = enabledItems.get(1);
+        final ImeSubtypeListItem switchingUnawarelatinIme_en_UK = enabledItems.get(2);
+        final ImeSubtypeListItem switchingUnawarelatinIme_hi = enabledItems.get(3);
+        final ImeSubtypeListItem subtypeUnawareIme = enabledItems.get(4);
+        final ImeSubtypeListItem japaneseIme_ja_JP = enabledItems.get(5);
+        final ImeSubtypeListItem switchUnawareJapaneseIme_ja_JP = enabledItems.get(6);
+
+        final ControllerImpl controller = new ControllerImpl(enabledItems);
+
+        // === switching-aware loop ===
+        assertRotationOrder(controller, false /* onlyCurrentIme */,
+                latinIme_en_US, latinIme_fr, japaneseIme_ja_JP);
+        // Then notify that a user did something for latinIme_fr.
+        onUserAction(controller, latinIme_fr);
+        assertRotationOrder(controller, false /* onlyCurrentIme */,
+                latinIme_fr, latinIme_en_US, japaneseIme_ja_JP);
+        // Then notify that a user did something for latinIme_fr again.
+        onUserAction(controller, latinIme_fr);
+        assertRotationOrder(controller, false /* onlyCurrentIme */,
+                latinIme_fr, latinIme_en_US, japaneseIme_ja_JP);
+        // Then notify that a user did something for japaneseIme_ja_JP.
+        onUserAction(controller, latinIme_fr);
+        assertRotationOrder(controller, false /* onlyCurrentIme */,
+                japaneseIme_ja_JP, latinIme_fr, latinIme_en_US);
+        // Check onlyCurrentIme == true.
+        assertNextInputMethod(controller, true /* onlyCurrentIme */,
+                japaneseIme_ja_JP, null);
+        assertRotationOrder(controller, true /* onlyCurrentIme */,
+                latinIme_fr, latinIme_en_US);
+        assertRotationOrder(controller, true /* onlyCurrentIme */,
+                latinIme_en_US, latinIme_fr);
+
+        // === switching-unaware loop ===
+        assertRotationOrder(controller, false /* onlyCurrentIme */,
+                switchingUnawarelatinIme_en_UK, switchingUnawarelatinIme_hi, subtypeUnawareIme,
+                switchUnawareJapaneseIme_ja_JP);
+        // User action should be ignored for switching unaware IMEs.
+        onUserAction(controller, switchingUnawarelatinIme_hi);
+        assertRotationOrder(controller, false /* onlyCurrentIme */,
+                switchingUnawarelatinIme_en_UK, switchingUnawarelatinIme_hi, subtypeUnawareIme,
+                switchUnawareJapaneseIme_ja_JP);
+        // User action should be ignored for switching unaware IMEs.
+        onUserAction(controller, switchUnawareJapaneseIme_ja_JP);
+        assertRotationOrder(controller, false /* onlyCurrentIme */,
+                switchingUnawarelatinIme_en_UK, switchingUnawarelatinIme_hi, subtypeUnawareIme,
+                switchUnawareJapaneseIme_ja_JP);
+        // Check onlyCurrentIme == true.
+        assertRotationOrder(controller, true /* onlyCurrentIme */,
+                switchingUnawarelatinIme_en_UK, switchingUnawarelatinIme_hi);
+        assertNextInputMethod(controller, true /* onlyCurrentIme */,
+                subtypeUnawareIme, null);
+        assertNextInputMethod(controller, true /* onlyCurrentIme */,
+                switchUnawareJapaneseIme_ja_JP, null);
+    }
+}