/*
 * Copyright (C) 2013 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package com.android.server.inputmethod;

import android.annotation.Nullable;
import android.content.Context;
import android.content.pm.PackageManager;
import android.text.TextUtils;
import android.util.ArraySet;
import android.util.Log;
import android.util.Printer;
import android.util.Slog;
import android.view.inputmethod.InputMethodInfo;
import android.view.inputmethod.InputMethodSubtype;

import com.android.internal.annotations.VisibleForTesting;
import com.android.server.inputmethod.InputMethodUtils.InputMethodSettings;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Locale;
import java.util.Objects;

/**
 * InputMethodSubtypeSwitchingController controls the switching behavior of the subtypes.
 *
 * <p>This class is designed to be used from and only from {@link InputMethodManagerService} by
 * using {@link InputMethodManagerService#mMethodMap} as a global lock.</p>
 */
final class InputMethodSubtypeSwitchingController {
    private static final String TAG = InputMethodSubtypeSwitchingController.class.getSimpleName();
    private static final boolean DEBUG = false;
    private static final int NOT_A_SUBTYPE_ID = InputMethodUtils.NOT_A_SUBTYPE_ID;

    public static class ImeSubtypeListItem implements Comparable<ImeSubtypeListItem> {
        public final CharSequence mImeName;
        public final CharSequence mSubtypeName;
        public final InputMethodInfo mImi;
        public final int mSubtypeId;
        public final boolean mIsSystemLocale;
        public final boolean mIsSystemLanguage;

        public ImeSubtypeListItem(CharSequence imeName, CharSequence subtypeName,
                InputMethodInfo imi, int subtypeId, String subtypeLocale, String systemLocale) {
            mImeName = imeName;
            mSubtypeName = subtypeName;
            mImi = imi;
            mSubtypeId = subtypeId;
            if (TextUtils.isEmpty(subtypeLocale)) {
                mIsSystemLocale = false;
                mIsSystemLanguage = false;
            } else {
                mIsSystemLocale = subtypeLocale.equals(systemLocale);
                if (mIsSystemLocale) {
                    mIsSystemLanguage = true;
                } else {
                    // TODO: Use Locale#getLanguage or Locale#toLanguageTag
                    final String systemLanguage = parseLanguageFromLocaleString(systemLocale);
                    final String subtypeLanguage = parseLanguageFromLocaleString(subtypeLocale);
                    mIsSystemLanguage = systemLanguage.length() >= 2 &&
                            systemLanguage.equals(subtypeLanguage);
                }
            }
        }

        /**
         * Returns the language component of a given locale string.
         * TODO: Use {@link Locale#getLanguage()} instead.
         */
        private static String parseLanguageFromLocaleString(final String locale) {
            final int idx = locale.indexOf('_');
            if (idx < 0) {
                return locale;
            } else {
                return locale.substring(0, idx);
            }
        }

        private static int compareNullableCharSequences(@Nullable CharSequence c1,
                @Nullable CharSequence c2) {
            // For historical reasons, an empty text needs to put at the last.
            final boolean empty1 = TextUtils.isEmpty(c1);
            final boolean empty2 = TextUtils.isEmpty(c2);
            if (empty1 || empty2) {
                return (empty1 ? 1 : 0) - (empty2 ? 1 : 0);
            }
            return c1.toString().compareTo(c2.toString());
        }

        /**
         * Compares this object with the specified object for order. The fields of this class will
         * be compared in the following order.
         * <ol>
         *   <li>{@link #mImeName}</li>
         *   <li>{@link #mIsSystemLocale}</li>
         *   <li>{@link #mIsSystemLanguage}</li>
         *   <li>{@link #mSubtypeName}</li>
         *   <li>{@link #mImi} with {@link InputMethodInfo#getId()}</li>
         * </ol>
         * Note: this class has a natural ordering that is inconsistent with {@link #equals(Object).
         * This method doesn't compare {@link #mSubtypeId} but {@link #equals(Object)} does.
         *
         * @param other the object to be compared.
         * @return a negative integer, zero, or positive integer as this object is less than, equal
         *         to, or greater than the specified <code>other</code> object.
         */
        @Override
        public int compareTo(ImeSubtypeListItem other) {
            int result = compareNullableCharSequences(mImeName, other.mImeName);
            if (result != 0) {
                return result;
            }
            // Subtype that has the same locale of the system's has higher priority.
            result = (mIsSystemLocale ? -1 : 0) - (other.mIsSystemLocale ? -1 : 0);
            if (result != 0) {
                return result;
            }
            // Subtype that has the same language of the system's has higher priority.
            result = (mIsSystemLanguage ? -1 : 0) - (other.mIsSystemLanguage ? -1 : 0);
            if (result != 0) {
                return result;
            }
            result = compareNullableCharSequences(mSubtypeName, other.mSubtypeName);
            if (result != 0) {
                return result;
            }
            return mImi.getId().compareTo(other.mImi.getId());
        }

        @Override
        public String toString() {
            return "ImeSubtypeListItem{"
                    + "mImeName=" + mImeName
                    + " mSubtypeName=" + mSubtypeName
                    + " mSubtypeId=" + mSubtypeId
                    + " mIsSystemLocale=" + mIsSystemLocale
                    + " mIsSystemLanguage=" + mIsSystemLanguage
                    + "}";
        }

        @Override
        public boolean equals(Object o) {
            if (o == this) {
                return true;
            }
            if (o instanceof ImeSubtypeListItem) {
                final ImeSubtypeListItem that = (ImeSubtypeListItem)o;
                return Objects.equals(this.mImi, that.mImi) && this.mSubtypeId == that.mSubtypeId;
            }
            return false;
        }
    }

    private static class InputMethodAndSubtypeList {
        private final Context mContext;
        // Used to load label
        private final PackageManager mPm;
        private final String mSystemLocaleStr;
        private final InputMethodSettings mSettings;

        public InputMethodAndSubtypeList(Context context, InputMethodSettings settings) {
            mContext = context;
            mSettings = settings;
            mPm = context.getPackageManager();
            final Locale locale = context.getResources().getConfiguration().locale;
            mSystemLocaleStr = locale != null ? locale.toString() : "";
        }

        public List<ImeSubtypeListItem> getSortedInputMethodAndSubtypeList(
                boolean includeAuxiliarySubtypes, boolean isScreenLocked) {
            final ArrayList<InputMethodInfo> imis = mSettings.getEnabledInputMethodListLocked();
            if (imis.isEmpty()) {
                return Collections.emptyList();
            }
            if (isScreenLocked && includeAuxiliarySubtypes) {
                if (DEBUG) {
                    Slog.w(TAG, "Auxiliary subtypes are not allowed to be shown in lock screen.");
                }
                includeAuxiliarySubtypes = false;
            }
            final ArrayList<ImeSubtypeListItem> imList = new ArrayList<>();
            final int numImes = imis.size();
            for (int i = 0; i < numImes; ++i) {
                final InputMethodInfo imi = imis.get(i);
                final List<InputMethodSubtype> explicitlyOrImplicitlyEnabledSubtypeList =
                        mSettings.getEnabledInputMethodSubtypeListLocked(mContext, imi, true);
                final ArraySet<String> enabledSubtypeSet = new ArraySet<>();
                for (InputMethodSubtype subtype : explicitlyOrImplicitlyEnabledSubtypeList) {
                    enabledSubtypeSet.add(String.valueOf(subtype.hashCode()));
                }
                final CharSequence imeLabel = imi.loadLabel(mPm);
                if (enabledSubtypeSet.size() > 0) {
                    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);
                        final String subtypeHashCode = String.valueOf(subtype.hashCode());
                        // We show all enabled IMEs and subtypes when an IME is shown.
                        if (enabledSubtypeSet.contains(subtypeHashCode)
                                && (includeAuxiliarySubtypes || !subtype.isAuxiliary())) {
                            final CharSequence subtypeLabel =
                                    subtype.overridesImplicitlyEnabledSubtype() ? null : subtype
                                            .getDisplayName(mContext, imi.getPackageName(),
                                                    imi.getServiceInfo().applicationInfo);
                            imList.add(new ImeSubtypeListItem(imeLabel,
                                    subtypeLabel, imi, j, subtype.getLocale(), mSystemLocaleStr));

                            // Removing this subtype from enabledSubtypeSet because we no
                            // longer need to add an entry of this subtype to imList to avoid
                            // duplicated entries.
                            enabledSubtypeSet.remove(subtypeHashCode);
                        }
                    }
                } else {
                    imList.add(new ImeSubtypeListItem(imeLabel, null, imi, NOT_A_SUBTYPE_ID, null,
                            mSystemLocaleStr));
                }
            }
            Collections.sort(imList);
            return imList;
        }
    }

    private static int calculateSubtypeId(InputMethodInfo imi, InputMethodSubtype subtype) {
        return subtype != null ? InputMethodUtils.getSubtypeIdFromHashCode(imi,
                subtype.hashCode()) : NOT_A_SUBTYPE_ID;
    }

    private static class StaticRotationList {
        private final List<ImeSubtypeListItem> mImeSubtypeList;
        public StaticRotationList(final List<ImeSubtypeListItem> imeSubtypeList) {
            mImeSubtypeList = imeSubtypeList;
        }

        /**
         * Returns the index of the specified input method and subtype in the given list.
         * @param imi The {@link InputMethodInfo} to be searched.
         * @param subtype The {@link InputMethodSubtype} to be searched. null if the input method
         * does not have a subtype.
         * @return The index in the given list. -1 if not found.
         */
        private int getIndex(InputMethodInfo imi, InputMethodSubtype subtype) {
            final int currentSubtypeId = calculateSubtypeId(imi, subtype);
            final int N = mImeSubtypeList.size();
            for (int i = 0; i < N; ++i) {
                final ImeSubtypeListItem isli = mImeSubtypeList.get(i);
                // Skip until the current IME/subtype is found.
                if (imi.equals(isli.mImi) && isli.mSubtypeId == currentSubtypeId) {
                    return i;
                }
            }
            return -1;
        }

        public ImeSubtypeListItem getNextInputMethodLocked(boolean onlyCurrentIme,
                InputMethodInfo imi, InputMethodSubtype subtype) {
            if (imi == null) {
                return null;
            }
            if (mImeSubtypeList.size() <= 1) {
                return null;
            }
            final int currentIndex = getIndex(imi, subtype);
            if (currentIndex < 0) {
                return null;
            }
            final int N = mImeSubtypeList.size();
            for (int offset = 1; offset < N; ++offset) {
                // Start searching the next IME/subtype from the next of the current index.
                final int candidateIndex = (currentIndex + offset) % N;
                final ImeSubtypeListItem candidate = mImeSubtypeList.get(candidateIndex);
                // Skip if searching inside the current IME only, but the candidate is not
                // the current IME.
                if (onlyCurrentIme && !imi.equals(candidate.mImi)) {
                    continue;
                }
                return candidate;
            }
            return null;
        }

        protected void dump(final Printer pw, final String prefix) {
            final int N = mImeSubtypeList.size();
            for (int i = 0; i < N; ++i) {
                final int rank = i;
                final ImeSubtypeListItem item = mImeSubtypeList.get(i);
                pw.println(prefix + "rank=" + rank + " item=" + item);
            }
        }
    }

    private static class DynamicRotationList {
        private static final String TAG = DynamicRotationList.class.getSimpleName();
        private final List<ImeSubtypeListItem> mImeSubtypeList;
        private final int[] mUsageHistoryOfSubtypeListItemIndex;

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

        protected void dump(final Printer pw, final String prefix) {
            for (int i = 0; i < mUsageHistoryOfSubtypeListItemIndex.length; ++i) {
                final int rank = mUsageHistoryOfSubtypeListItemIndex[i];
                final ImeSubtypeListItem item = mImeSubtypeList.get(i);
                pw.println(prefix + "rank=" + rank + " item=" + item);
            }
        }
    }

    @VisibleForTesting
    public static class ControllerImpl {
        private final DynamicRotationList mSwitchingAwareRotationList;
        private final StaticRotationList mSwitchingUnawareRotationList;

        public static ControllerImpl createFrom(final ControllerImpl currentInstance,
                final List<ImeSubtypeListItem> sortedEnabledItems) {
            DynamicRotationList switchingAwareRotationList = null;
            {
                final List<ImeSubtypeListItem> switchingAwareImeSubtypes =
                        filterImeSubtypeList(sortedEnabledItems,
                                true /* supportsSwitchingToNextInputMethod */);
                if (currentInstance != null &&
                        currentInstance.mSwitchingAwareRotationList != null &&
                        Objects.equals(currentInstance.mSwitchingAwareRotationList.mImeSubtypeList,
                                switchingAwareImeSubtypes)) {
                    // Can reuse the current instance.
                    switchingAwareRotationList = currentInstance.mSwitchingAwareRotationList;
                }
                if (switchingAwareRotationList == null) {
                    switchingAwareRotationList = new DynamicRotationList(switchingAwareImeSubtypes);
                }
            }

            StaticRotationList switchingUnawareRotationList = null;
            {
                final List<ImeSubtypeListItem> switchingUnawareImeSubtypes = filterImeSubtypeList(
                        sortedEnabledItems, false /* supportsSwitchingToNextInputMethod */);
                if (currentInstance != null &&
                        currentInstance.mSwitchingUnawareRotationList != null &&
                        Objects.equals(
                                currentInstance.mSwitchingUnawareRotationList.mImeSubtypeList,
                                switchingUnawareImeSubtypes)) {
                    // Can reuse the current instance.
                    switchingUnawareRotationList = currentInstance.mSwitchingUnawareRotationList;
                }
                if (switchingUnawareRotationList == null) {
                    switchingUnawareRotationList =
                            new StaticRotationList(switchingUnawareImeSubtypes);
                }
            }

            return new ControllerImpl(switchingAwareRotationList, switchingUnawareRotationList);
        }

        private ControllerImpl(final DynamicRotationList switchingAwareRotationList,
                final StaticRotationList switchingUnawareRotationList) {
            mSwitchingAwareRotationList = switchingAwareRotationList;
            mSwitchingUnawareRotationList = switchingUnawareRotationList;
        }

        public ImeSubtypeListItem getNextInputMethod(boolean onlyCurrentIme, InputMethodInfo imi,
                InputMethodSubtype subtype) {
            if (imi == null) {
                return null;
            }
            if (imi.supportsSwitchingToNextInputMethod()) {
                return mSwitchingAwareRotationList.getNextInputMethodLocked(onlyCurrentIme, imi,
                        subtype);
            } else {
                return mSwitchingUnawareRotationList.getNextInputMethodLocked(onlyCurrentIme, imi,
                        subtype);
            }
        }

        public void onUserActionLocked(InputMethodInfo imi, InputMethodSubtype subtype) {
            if (imi == null) {
                return;
            }
            if (imi.supportsSwitchingToNextInputMethod()) {
                mSwitchingAwareRotationList.onUserAction(imi, subtype);
            }
        }

        private static List<ImeSubtypeListItem> filterImeSubtypeList(
                final List<ImeSubtypeListItem> items,
                final boolean supportsSwitchingToNextInputMethod) {
            final ArrayList<ImeSubtypeListItem> result = new ArrayList<>();
            final int ALL_ITEMS_COUNT = items.size();
            for (int i = 0; i < ALL_ITEMS_COUNT; i++) {
                final ImeSubtypeListItem item = items.get(i);
                if (item.mImi.supportsSwitchingToNextInputMethod() ==
                        supportsSwitchingToNextInputMethod) {
                    result.add(item);
                }
            }
            return result;
        }

        protected void dump(final Printer pw) {
            pw.println("    mSwitchingAwareRotationList:");
            mSwitchingAwareRotationList.dump(pw, "      ");
            pw.println("    mSwitchingUnawareRotationList:");
            mSwitchingUnawareRotationList.dump(pw, "      ");
        }
    }

    private final InputMethodSettings mSettings;
    private InputMethodAndSubtypeList mSubtypeList;
    private ControllerImpl mController;

    private InputMethodSubtypeSwitchingController(InputMethodSettings settings, Context context) {
        mSettings = settings;
        resetCircularListLocked(context);
    }

    public static InputMethodSubtypeSwitchingController createInstanceLocked(
            InputMethodSettings settings, Context context) {
        return new InputMethodSubtypeSwitchingController(settings, context);
    }

    public void onUserActionLocked(InputMethodInfo imi, InputMethodSubtype subtype) {
        if (mController == null) {
            if (DEBUG) {
                Log.e(TAG, "mController shouldn't be null.");
            }
            return;
        }
        mController.onUserActionLocked(imi, subtype);
    }

    public void resetCircularListLocked(Context context) {
        mSubtypeList = new InputMethodAndSubtypeList(context, mSettings);
        mController = ControllerImpl.createFrom(mController,
                mSubtypeList.getSortedInputMethodAndSubtypeList(
                        false /* includeAuxiliarySubtypes */, false /* isScreenLocked */));
    }

    public ImeSubtypeListItem getNextInputMethodLocked(boolean onlyCurrentIme, InputMethodInfo imi,
            InputMethodSubtype subtype) {
        if (mController == null) {
            if (DEBUG) {
                Log.e(TAG, "mController shouldn't be null.");
            }
            return null;
        }
        return mController.getNextInputMethod(onlyCurrentIme, imi, subtype);
    }

    public List<ImeSubtypeListItem> getSortedInputMethodAndSubtypeListLocked(
            boolean includingAuxiliarySubtypes, boolean isScreenLocked) {
        return mSubtypeList.getSortedInputMethodAndSubtypeList(
                includingAuxiliarySubtypes, isScreenLocked);
    }

    public void dump(final Printer pw) {
        if (mController != null) {
            mController.dump(pw);
        } else {
            pw.println("    mController=null");
        }
    }
}