1/*
2 * Copyright (C) 2013 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 *      http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package com.android.internal.inputmethod;
18
19import android.annotation.NonNull;
20import android.annotation.Nullable;
21import android.annotation.UserIdInt;
22import android.app.AppOpsManager;
23import android.content.ContentResolver;
24import android.content.Context;
25import android.content.pm.ApplicationInfo;
26import android.content.pm.IPackageManager;
27import android.content.pm.PackageManager;
28import android.content.res.Resources;
29import android.os.LocaleList;
30import android.os.RemoteException;
31import android.provider.Settings;
32import android.text.TextUtils;
33import android.text.TextUtils.SimpleStringSplitter;
34import android.util.ArrayMap;
35import android.util.ArraySet;
36import android.util.Pair;
37import android.util.Printer;
38import android.util.Slog;
39import android.view.inputmethod.InputMethodInfo;
40import android.view.inputmethod.InputMethodSubtype;
41import android.view.textservice.SpellCheckerInfo;
42import android.view.textservice.TextServicesManager;
43
44import com.android.internal.annotations.GuardedBy;
45import com.android.internal.annotations.VisibleForTesting;
46
47import java.util.ArrayList;
48import java.util.Arrays;
49import java.util.HashMap;
50import java.util.LinkedHashSet;
51import java.util.List;
52import java.util.Locale;
53
54/**
55 * InputMethodManagerUtils contains some static methods that provides IME informations.
56 * This methods are supposed to be used in both the framework and the Settings application.
57 */
58public class InputMethodUtils {
59    public static final boolean DEBUG = false;
60    public static final int NOT_A_SUBTYPE_ID = -1;
61    public static final String SUBTYPE_MODE_ANY = null;
62    public static final String SUBTYPE_MODE_KEYBOARD = "keyboard";
63    public static final String SUBTYPE_MODE_VOICE = "voice";
64    private static final String TAG = "InputMethodUtils";
65    private static final Locale ENGLISH_LOCALE = new Locale("en");
66    private static final String NOT_A_SUBTYPE_ID_STR = String.valueOf(NOT_A_SUBTYPE_ID);
67    private static final String TAG_ENABLED_WHEN_DEFAULT_IS_NOT_ASCII_CAPABLE =
68            "EnabledWhenDefaultIsNotAsciiCapable";
69    private static final String TAG_ASCII_CAPABLE = "AsciiCapable";
70
71    // The string for enabled input method is saved as follows:
72    // example: ("ime0;subtype0;subtype1;subtype2:ime1:ime2;subtype0")
73    private static final char INPUT_METHOD_SEPARATOR = ':';
74    private static final char INPUT_METHOD_SUBTYPE_SEPARATOR = ';';
75    /**
76     * Used in {@link #getFallbackLocaleForDefaultIme(ArrayList, Context)} to find the fallback IMEs
77     * that are mainly used until the system becomes ready. Note that {@link Locale} in this array
78     * is checked with {@link Locale#equals(Object)}, which means that {@code Locale.ENGLISH}
79     * doesn't automatically match {@code Locale("en", "IN")}.
80     */
81    private static final Locale[] SEARCH_ORDER_OF_FALLBACK_LOCALES = {
82        Locale.ENGLISH, // "en"
83        Locale.US, // "en_US"
84        Locale.UK, // "en_GB"
85    };
86
87    // A temporary workaround for the performance concerns in
88    // #getImplicitlyApplicableSubtypesLocked(Resources, InputMethodInfo).
89    // TODO: Optimize all the critical paths including this one.
90    private static final Object sCacheLock = new Object();
91    @GuardedBy("sCacheLock")
92    private static LocaleList sCachedSystemLocales;
93    @GuardedBy("sCacheLock")
94    private static InputMethodInfo sCachedInputMethodInfo;
95    @GuardedBy("sCacheLock")
96    private static ArrayList<InputMethodSubtype> sCachedResult;
97
98    private InputMethodUtils() {
99        // This utility class is not publicly instantiable.
100    }
101
102    // ----------------------------------------------------------------------
103    // Utilities for debug
104    public static String getApiCallStack() {
105        String apiCallStack = "";
106        try {
107            throw new RuntimeException();
108        } catch (RuntimeException e) {
109            final StackTraceElement[] frames = e.getStackTrace();
110            for (int j = 1; j < frames.length; ++j) {
111                final String tempCallStack = frames[j].toString();
112                if (TextUtils.isEmpty(apiCallStack)) {
113                    // Overwrite apiCallStack if it's empty
114                    apiCallStack = tempCallStack;
115                } else if (tempCallStack.indexOf("Transact(") < 0) {
116                    // Overwrite apiCallStack if it's not a binder call
117                    apiCallStack = tempCallStack;
118                } else {
119                    break;
120                }
121            }
122        }
123        return apiCallStack;
124    }
125    // ----------------------------------------------------------------------
126
127    public static boolean isSystemIme(InputMethodInfo inputMethod) {
128        return (inputMethod.getServiceInfo().applicationInfo.flags
129                & ApplicationInfo.FLAG_SYSTEM) != 0;
130    }
131
132    public static boolean isSystemImeThatHasSubtypeOf(final InputMethodInfo imi,
133            final Context context, final boolean checkDefaultAttribute,
134            @Nullable final Locale requiredLocale, final boolean checkCountry,
135            final String requiredSubtypeMode) {
136        if (!isSystemIme(imi)) {
137            return false;
138        }
139        if (checkDefaultAttribute && !imi.isDefault(context)) {
140            return false;
141        }
142        if (!containsSubtypeOf(imi, requiredLocale, checkCountry, requiredSubtypeMode)) {
143            return false;
144        }
145        return true;
146    }
147
148    @Nullable
149    public static Locale getFallbackLocaleForDefaultIme(final ArrayList<InputMethodInfo> imis,
150            final Context context) {
151        // At first, find the fallback locale from the IMEs that are declared as "default" in the
152        // current locale.  Note that IME developers can declare an IME as "default" only for
153        // some particular locales but "not default" for other locales.
154        for (final Locale fallbackLocale : SEARCH_ORDER_OF_FALLBACK_LOCALES) {
155            for (int i = 0; i < imis.size(); ++i) {
156                if (isSystemImeThatHasSubtypeOf(imis.get(i), context,
157                        true /* checkDefaultAttribute */, fallbackLocale,
158                        true /* checkCountry */, SUBTYPE_MODE_KEYBOARD)) {
159                    return fallbackLocale;
160                }
161            }
162        }
163        // If no fallback locale is found in the above condition, find fallback locales regardless
164        // of the "default" attribute as a last resort.
165        for (final Locale fallbackLocale : SEARCH_ORDER_OF_FALLBACK_LOCALES) {
166            for (int i = 0; i < imis.size(); ++i) {
167                if (isSystemImeThatHasSubtypeOf(imis.get(i), context,
168                        false /* checkDefaultAttribute */, fallbackLocale,
169                        true /* checkCountry */, SUBTYPE_MODE_KEYBOARD)) {
170                    return fallbackLocale;
171                }
172            }
173        }
174        Slog.w(TAG, "Found no fallback locale. imis=" + Arrays.toString(imis.toArray()));
175        return null;
176    }
177
178    private static boolean isSystemAuxilialyImeThatHasAutomaticSubtype(final InputMethodInfo imi,
179            final Context context, final boolean checkDefaultAttribute) {
180        if (!isSystemIme(imi)) {
181            return false;
182        }
183        if (checkDefaultAttribute && !imi.isDefault(context)) {
184            return false;
185        }
186        if (!imi.isAuxiliaryIme()) {
187            return false;
188        }
189        final int subtypeCount = imi.getSubtypeCount();
190        for (int i = 0; i < subtypeCount; ++i) {
191            final InputMethodSubtype s = imi.getSubtypeAt(i);
192            if (s.overridesImplicitlyEnabledSubtype()) {
193                return true;
194            }
195        }
196        return false;
197    }
198
199    public static Locale getSystemLocaleFromContext(final Context context) {
200        try {
201            return context.getResources().getConfiguration().locale;
202        } catch (Resources.NotFoundException ex) {
203            return null;
204        }
205    }
206
207    private static final class InputMethodListBuilder {
208        // Note: We use LinkedHashSet instead of android.util.ArraySet because the enumeration
209        // order can have non-trivial effect in the call sites.
210        @NonNull
211        private final LinkedHashSet<InputMethodInfo> mInputMethodSet = new LinkedHashSet<>();
212
213        public InputMethodListBuilder fillImes(final ArrayList<InputMethodInfo> imis,
214                final Context context, final boolean checkDefaultAttribute,
215                @Nullable final Locale locale, final boolean checkCountry,
216                final String requiredSubtypeMode) {
217            for (int i = 0; i < imis.size(); ++i) {
218                final InputMethodInfo imi = imis.get(i);
219                if (isSystemImeThatHasSubtypeOf(imi, context, checkDefaultAttribute, locale,
220                        checkCountry, requiredSubtypeMode)) {
221                    mInputMethodSet.add(imi);
222                }
223            }
224            return this;
225        }
226
227        // TODO: The behavior of InputMethodSubtype#overridesImplicitlyEnabledSubtype() should be
228        // documented more clearly.
229        public InputMethodListBuilder fillAuxiliaryImes(final ArrayList<InputMethodInfo> imis,
230                final Context context) {
231            // If one or more auxiliary input methods are available, OK to stop populating the list.
232            for (final InputMethodInfo imi : mInputMethodSet) {
233                if (imi.isAuxiliaryIme()) {
234                    return this;
235                }
236            }
237            boolean added = false;
238            for (int i = 0; i < imis.size(); ++i) {
239                final InputMethodInfo imi = imis.get(i);
240                if (isSystemAuxilialyImeThatHasAutomaticSubtype(imi, context,
241                        true /* checkDefaultAttribute */)) {
242                    mInputMethodSet.add(imi);
243                    added = true;
244                }
245            }
246            if (added) {
247                return this;
248            }
249            for (int i = 0; i < imis.size(); ++i) {
250                final InputMethodInfo imi = imis.get(i);
251                if (isSystemAuxilialyImeThatHasAutomaticSubtype(imi, context,
252                        false /* checkDefaultAttribute */)) {
253                    mInputMethodSet.add(imi);
254                }
255            }
256            return this;
257        }
258
259        public boolean isEmpty() {
260            return mInputMethodSet.isEmpty();
261        }
262
263        @NonNull
264        public ArrayList<InputMethodInfo> build() {
265            return new ArrayList<>(mInputMethodSet);
266        }
267    }
268
269    private static InputMethodListBuilder getMinimumKeyboardSetWithoutSystemLocale(
270            final ArrayList<InputMethodInfo> imis, final Context context,
271            @Nullable final Locale fallbackLocale) {
272        // Before the system becomes ready, we pick up at least one keyboard in the following order.
273        // The first user (device owner) falls into this category.
274        // 1. checkDefaultAttribute: true, locale: fallbackLocale, checkCountry: true
275        // 2. checkDefaultAttribute: false, locale: fallbackLocale, checkCountry: true
276        // 3. checkDefaultAttribute: true, locale: fallbackLocale, checkCountry: false
277        // 4. checkDefaultAttribute: false, locale: fallbackLocale, checkCountry: false
278        // TODO: We should check isAsciiCapable instead of relying on fallbackLocale.
279
280        final InputMethodListBuilder builder = new InputMethodListBuilder();
281        builder.fillImes(imis, context, true /* checkDefaultAttribute */, fallbackLocale,
282                true /* checkCountry */, SUBTYPE_MODE_KEYBOARD);
283        if (!builder.isEmpty()) {
284            return builder;
285        }
286        builder.fillImes(imis, context, false /* checkDefaultAttribute */, fallbackLocale,
287                true /* checkCountry */, SUBTYPE_MODE_KEYBOARD);
288        if (!builder.isEmpty()) {
289            return builder;
290        }
291        builder.fillImes(imis, context, true /* checkDefaultAttribute */, fallbackLocale,
292                false /* checkCountry */, SUBTYPE_MODE_KEYBOARD);
293        if (!builder.isEmpty()) {
294            return builder;
295        }
296        builder.fillImes(imis, context, false /* checkDefaultAttribute */, fallbackLocale,
297                false /* checkCountry */, SUBTYPE_MODE_KEYBOARD);
298        if (!builder.isEmpty()) {
299            return builder;
300        }
301        Slog.w(TAG, "No software keyboard is found. imis=" + Arrays.toString(imis.toArray())
302                + " fallbackLocale=" + fallbackLocale);
303        return builder;
304    }
305
306    private static InputMethodListBuilder getMinimumKeyboardSetWithSystemLocale(
307            final ArrayList<InputMethodInfo> imis, final Context context,
308            @Nullable final Locale systemLocale, @Nullable final Locale fallbackLocale) {
309        // Once the system becomes ready, we pick up at least one keyboard in the following order.
310        // Secondary users fall into this category in general.
311        // 1. checkDefaultAttribute: true, locale: systemLocale, checkCountry: true
312        // 2. checkDefaultAttribute: true, locale: systemLocale, checkCountry: false
313        // 3. checkDefaultAttribute: true, locale: fallbackLocale, checkCountry: true
314        // 4. checkDefaultAttribute: true, locale: fallbackLocale, checkCountry: false
315        // 5. checkDefaultAttribute: false, locale: fallbackLocale, checkCountry: true
316        // 6. checkDefaultAttribute: false, locale: fallbackLocale, checkCountry: false
317        // TODO: We should check isAsciiCapable instead of relying on fallbackLocale.
318
319        final InputMethodListBuilder builder = new InputMethodListBuilder();
320        builder.fillImes(imis, context, true /* checkDefaultAttribute */, systemLocale,
321                true /* checkCountry */, SUBTYPE_MODE_KEYBOARD);
322        if (!builder.isEmpty()) {
323            return builder;
324        }
325        builder.fillImes(imis, context, true /* checkDefaultAttribute */, systemLocale,
326                false /* checkCountry */, SUBTYPE_MODE_KEYBOARD);
327        if (!builder.isEmpty()) {
328            return builder;
329        }
330        builder.fillImes(imis, context, true /* checkDefaultAttribute */, fallbackLocale,
331                true /* checkCountry */, SUBTYPE_MODE_KEYBOARD);
332        if (!builder.isEmpty()) {
333            return builder;
334        }
335        builder.fillImes(imis, context, true /* checkDefaultAttribute */, fallbackLocale,
336                false /* checkCountry */, SUBTYPE_MODE_KEYBOARD);
337        if (!builder.isEmpty()) {
338            return builder;
339        }
340        builder.fillImes(imis, context, false /* checkDefaultAttribute */, fallbackLocale,
341                true /* checkCountry */, SUBTYPE_MODE_KEYBOARD);
342        if (!builder.isEmpty()) {
343            return builder;
344        }
345        builder.fillImes(imis, context, false /* checkDefaultAttribute */, fallbackLocale,
346                false /* checkCountry */, SUBTYPE_MODE_KEYBOARD);
347        if (!builder.isEmpty()) {
348            return builder;
349        }
350        Slog.w(TAG, "No software keyboard is found. imis=" + Arrays.toString(imis.toArray())
351                + " systemLocale=" + systemLocale + " fallbackLocale=" + fallbackLocale);
352        return builder;
353    }
354
355    public static ArrayList<InputMethodInfo> getDefaultEnabledImes(final Context context,
356            final boolean isSystemReady, final ArrayList<InputMethodInfo> imis) {
357        final Locale fallbackLocale = getFallbackLocaleForDefaultIme(imis, context);
358        if (!isSystemReady) {
359            // When the system is not ready, the system locale is not stable and reliable. Hence
360            // we will pick up IMEs that support software keyboard based on the fallback locale.
361            // Also pick up suitable IMEs regardless of the software keyboard support.
362            // (e.g. Voice IMEs)
363            return getMinimumKeyboardSetWithoutSystemLocale(imis, context, fallbackLocale)
364                    .fillImes(imis, context, true /* checkDefaultAttribute */, fallbackLocale,
365                            true /* checkCountry */, SUBTYPE_MODE_ANY)
366                    .build();
367        }
368
369        // When the system is ready, we will primarily rely on the system locale, but also keep
370        // relying on the fallback locale as a last resort.
371        // Also pick up suitable IMEs regardless of the software keyboard support (e.g. Voice IMEs),
372        // then pick up suitable auxiliary IMEs when necessary (e.g. Voice IMEs with "automatic"
373        // subtype)
374        final Locale systemLocale = getSystemLocaleFromContext(context);
375        return getMinimumKeyboardSetWithSystemLocale(imis, context, systemLocale, fallbackLocale)
376                .fillImes(imis, context, true /* checkDefaultAttribute */, systemLocale,
377                        true /* checkCountry */, SUBTYPE_MODE_ANY)
378                .fillAuxiliaryImes(imis, context)
379                .build();
380    }
381
382    public static Locale constructLocaleFromString(String localeStr) {
383        if (TextUtils.isEmpty(localeStr)) {
384            return null;
385        }
386        // TODO: Use {@link Locale#toLanguageTag()} and {@link Locale#forLanguageTag(languageTag)}.
387        String[] localeParams = localeStr.split("_", 3);
388        if (localeParams.length >= 1 && "tl".equals(localeParams[0])) {
389             // Convert a locale whose language is "tl" to one whose language is "fil".
390             // For example, "tl_PH" will get converted to "fil_PH".
391             // Versions of Android earlier than Lollipop did not support three letter language
392             // codes, and used "tl" (Tagalog) as the language string for "fil" (Filipino).
393             // On Lollipop and above, the current three letter version must be used.
394             localeParams[0] = "fil";
395        }
396        // The length of localeStr is guaranteed to always return a 1 <= value <= 3
397        // because localeStr is not empty.
398        if (localeParams.length == 1) {
399            return new Locale(localeParams[0]);
400        } else if (localeParams.length == 2) {
401            return new Locale(localeParams[0], localeParams[1]);
402        } else if (localeParams.length == 3) {
403            return new Locale(localeParams[0], localeParams[1], localeParams[2]);
404        }
405        return null;
406    }
407
408    public static boolean containsSubtypeOf(final InputMethodInfo imi,
409            @Nullable final Locale locale, final boolean checkCountry, final String mode) {
410        if (locale == null) {
411            return false;
412        }
413        final int N = imi.getSubtypeCount();
414        for (int i = 0; i < N; ++i) {
415            final InputMethodSubtype subtype = imi.getSubtypeAt(i);
416            if (checkCountry) {
417                final Locale subtypeLocale = subtype.getLocaleObject();
418                if (subtypeLocale == null ||
419                        !TextUtils.equals(subtypeLocale.getLanguage(), locale.getLanguage()) ||
420                        !TextUtils.equals(subtypeLocale.getCountry(), locale.getCountry())) {
421                    continue;
422                }
423            } else {
424                final Locale subtypeLocale = new Locale(getLanguageFromLocaleString(
425                        subtype.getLocale()));
426                if (!TextUtils.equals(subtypeLocale.getLanguage(), locale.getLanguage())) {
427                    continue;
428                }
429            }
430            if (mode == SUBTYPE_MODE_ANY || TextUtils.isEmpty(mode) ||
431                    mode.equalsIgnoreCase(subtype.getMode())) {
432                return true;
433            }
434        }
435        return false;
436    }
437
438    public static ArrayList<InputMethodSubtype> getSubtypes(InputMethodInfo imi) {
439        ArrayList<InputMethodSubtype> subtypes = new ArrayList<>();
440        final int subtypeCount = imi.getSubtypeCount();
441        for (int i = 0; i < subtypeCount; ++i) {
442            subtypes.add(imi.getSubtypeAt(i));
443        }
444        return subtypes;
445    }
446
447    public static ArrayList<InputMethodSubtype> getOverridingImplicitlyEnabledSubtypes(
448            InputMethodInfo imi, String mode) {
449        ArrayList<InputMethodSubtype> subtypes = new ArrayList<>();
450        final int subtypeCount = imi.getSubtypeCount();
451        for (int i = 0; i < subtypeCount; ++i) {
452            final InputMethodSubtype subtype = imi.getSubtypeAt(i);
453            if (subtype.overridesImplicitlyEnabledSubtype() && subtype.getMode().equals(mode)) {
454                subtypes.add(subtype);
455            }
456        }
457        return subtypes;
458    }
459
460    public static InputMethodInfo getMostApplicableDefaultIME(List<InputMethodInfo> enabledImes) {
461        if (enabledImes == null || enabledImes.isEmpty()) {
462            return null;
463        }
464        // We'd prefer to fall back on a system IME, since that is safer.
465        int i = enabledImes.size();
466        int firstFoundSystemIme = -1;
467        while (i > 0) {
468            i--;
469            final InputMethodInfo imi = enabledImes.get(i);
470            if (imi.isAuxiliaryIme()) {
471                continue;
472            }
473            if (InputMethodUtils.isSystemIme(imi)
474                    && containsSubtypeOf(imi, ENGLISH_LOCALE, false /* checkCountry */,
475                            SUBTYPE_MODE_KEYBOARD)) {
476                return imi;
477            }
478            if (firstFoundSystemIme < 0 && InputMethodUtils.isSystemIme(imi)) {
479                firstFoundSystemIme = i;
480            }
481        }
482        return enabledImes.get(Math.max(firstFoundSystemIme, 0));
483    }
484
485    public static boolean isValidSubtypeId(InputMethodInfo imi, int subtypeHashCode) {
486        return getSubtypeIdFromHashCode(imi, subtypeHashCode) != NOT_A_SUBTYPE_ID;
487    }
488
489    public static int getSubtypeIdFromHashCode(InputMethodInfo imi, int subtypeHashCode) {
490        if (imi != null) {
491            final int subtypeCount = imi.getSubtypeCount();
492            for (int i = 0; i < subtypeCount; ++i) {
493                InputMethodSubtype ims = imi.getSubtypeAt(i);
494                if (subtypeHashCode == ims.hashCode()) {
495                    return i;
496                }
497            }
498        }
499        return NOT_A_SUBTYPE_ID;
500    }
501
502    private static final LocaleUtils.LocaleExtractor<InputMethodSubtype> sSubtypeToLocale =
503            new LocaleUtils.LocaleExtractor<InputMethodSubtype>() {
504                @Override
505                public Locale get(InputMethodSubtype source) {
506                    return source != null ? source.getLocaleObject() : null;
507                }
508            };
509
510    @VisibleForTesting
511    public static ArrayList<InputMethodSubtype> getImplicitlyApplicableSubtypesLocked(
512            Resources res, InputMethodInfo imi) {
513        final LocaleList systemLocales = res.getConfiguration().getLocales();
514
515        synchronized (sCacheLock) {
516            // We intentionally do not use InputMethodInfo#equals(InputMethodInfo) here because
517            // it does not check if subtypes are also identical.
518            if (systemLocales.equals(sCachedSystemLocales) && sCachedInputMethodInfo == imi) {
519                return new ArrayList<>(sCachedResult);
520            }
521        }
522
523        // Note: Only resource info in "res" is used in getImplicitlyApplicableSubtypesLockedImpl().
524        // TODO: Refactor getImplicitlyApplicableSubtypesLockedImpl() so that it can receive
525        // LocaleList rather than Resource.
526        final ArrayList<InputMethodSubtype> result =
527                getImplicitlyApplicableSubtypesLockedImpl(res, imi);
528        synchronized (sCacheLock) {
529            // Both LocaleList and InputMethodInfo are immutable. No need to copy them here.
530            sCachedSystemLocales = systemLocales;
531            sCachedInputMethodInfo = imi;
532            sCachedResult = new ArrayList<>(result);
533        }
534        return result;
535    }
536
537    private static ArrayList<InputMethodSubtype> getImplicitlyApplicableSubtypesLockedImpl(
538            Resources res, InputMethodInfo imi) {
539        final List<InputMethodSubtype> subtypes = InputMethodUtils.getSubtypes(imi);
540        final LocaleList systemLocales = res.getConfiguration().getLocales();
541        final String systemLocale = systemLocales.get(0).toString();
542        if (TextUtils.isEmpty(systemLocale)) return new ArrayList<>();
543        final int numSubtypes = subtypes.size();
544
545        // Handle overridesImplicitlyEnabledSubtype mechanism.
546        final HashMap<String, InputMethodSubtype> applicableModeAndSubtypesMap = new HashMap<>();
547        for (int i = 0; i < numSubtypes; ++i) {
548            // scan overriding implicitly enabled subtypes.
549            final InputMethodSubtype subtype = subtypes.get(i);
550            if (subtype.overridesImplicitlyEnabledSubtype()) {
551                final String mode = subtype.getMode();
552                if (!applicableModeAndSubtypesMap.containsKey(mode)) {
553                    applicableModeAndSubtypesMap.put(mode, subtype);
554                }
555            }
556        }
557        if (applicableModeAndSubtypesMap.size() > 0) {
558            return new ArrayList<>(applicableModeAndSubtypesMap.values());
559        }
560
561        final HashMap<String, ArrayList<InputMethodSubtype>> nonKeyboardSubtypesMap =
562                new HashMap<>();
563        final ArrayList<InputMethodSubtype> keyboardSubtypes = new ArrayList<>();
564
565        for (int i = 0; i < numSubtypes; ++i) {
566            final InputMethodSubtype subtype = subtypes.get(i);
567            final String mode = subtype.getMode();
568            if (SUBTYPE_MODE_KEYBOARD.equals(mode)) {
569                keyboardSubtypes.add(subtype);
570            } else {
571                if (!nonKeyboardSubtypesMap.containsKey(mode)) {
572                    nonKeyboardSubtypesMap.put(mode, new ArrayList<>());
573                }
574                nonKeyboardSubtypesMap.get(mode).add(subtype);
575            }
576        }
577
578        final ArrayList<InputMethodSubtype> applicableSubtypes = new ArrayList<>();
579        LocaleUtils.filterByLanguage(keyboardSubtypes, sSubtypeToLocale, systemLocales,
580                applicableSubtypes);
581
582        if (!applicableSubtypes.isEmpty()) {
583            boolean hasAsciiCapableKeyboard = false;
584            final int numApplicationSubtypes = applicableSubtypes.size();
585            for (int i = 0; i < numApplicationSubtypes; ++i) {
586                final InputMethodSubtype subtype = applicableSubtypes.get(i);
587                if (subtype.containsExtraValueKey(TAG_ASCII_CAPABLE)) {
588                    hasAsciiCapableKeyboard = true;
589                    break;
590                }
591            }
592            if (!hasAsciiCapableKeyboard) {
593                final int numKeyboardSubtypes = keyboardSubtypes.size();
594                for (int i = 0; i < numKeyboardSubtypes; ++i) {
595                    final InputMethodSubtype subtype = keyboardSubtypes.get(i);
596                    final String mode = subtype.getMode();
597                    if (SUBTYPE_MODE_KEYBOARD.equals(mode) && subtype.containsExtraValueKey(
598                            TAG_ENABLED_WHEN_DEFAULT_IS_NOT_ASCII_CAPABLE)) {
599                        applicableSubtypes.add(subtype);
600                    }
601                }
602            }
603        }
604
605        if (applicableSubtypes.isEmpty()) {
606            InputMethodSubtype lastResortKeyboardSubtype = findLastResortApplicableSubtypeLocked(
607                    res, subtypes, SUBTYPE_MODE_KEYBOARD, systemLocale, true);
608            if (lastResortKeyboardSubtype != null) {
609                applicableSubtypes.add(lastResortKeyboardSubtype);
610            }
611        }
612
613        // For each non-keyboard mode, extract subtypes with system locales.
614        for (final ArrayList<InputMethodSubtype> subtypeList : nonKeyboardSubtypesMap.values()) {
615            LocaleUtils.filterByLanguage(subtypeList, sSubtypeToLocale, systemLocales,
616                    applicableSubtypes);
617        }
618
619        return applicableSubtypes;
620    }
621
622    /**
623     * Returns the language component of a given locale string.
624     * TODO: Use {@link Locale#toLanguageTag()} and {@link Locale#forLanguageTag(String)}
625     */
626    public static String getLanguageFromLocaleString(String locale) {
627        final int idx = locale.indexOf('_');
628        if (idx < 0) {
629            return locale;
630        } else {
631            return locale.substring(0, idx);
632        }
633    }
634
635    /**
636     * If there are no selected subtypes, tries finding the most applicable one according to the
637     * given locale.
638     * @param subtypes this function will search the most applicable subtype in subtypes
639     * @param mode subtypes will be filtered by mode
640     * @param locale subtypes will be filtered by locale
641     * @param canIgnoreLocaleAsLastResort if this function can't find the most applicable subtype,
642     * it will return the first subtype matched with mode
643     * @return the most applicable subtypeId
644     */
645    public static InputMethodSubtype findLastResortApplicableSubtypeLocked(
646            Resources res, List<InputMethodSubtype> subtypes, String mode, String locale,
647            boolean canIgnoreLocaleAsLastResort) {
648        if (subtypes == null || subtypes.size() == 0) {
649            return null;
650        }
651        if (TextUtils.isEmpty(locale)) {
652            locale = res.getConfiguration().locale.toString();
653        }
654        final String language = getLanguageFromLocaleString(locale);
655        boolean partialMatchFound = false;
656        InputMethodSubtype applicableSubtype = null;
657        InputMethodSubtype firstMatchedModeSubtype = null;
658        final int N = subtypes.size();
659        for (int i = 0; i < N; ++i) {
660            InputMethodSubtype subtype = subtypes.get(i);
661            final String subtypeLocale = subtype.getLocale();
662            final String subtypeLanguage = getLanguageFromLocaleString(subtypeLocale);
663            // An applicable subtype should match "mode". If mode is null, mode will be ignored,
664            // and all subtypes with all modes can be candidates.
665            if (mode == null || subtypes.get(i).getMode().equalsIgnoreCase(mode)) {
666                if (firstMatchedModeSubtype == null) {
667                    firstMatchedModeSubtype = subtype;
668                }
669                if (locale.equals(subtypeLocale)) {
670                    // Exact match (e.g. system locale is "en_US" and subtype locale is "en_US")
671                    applicableSubtype = subtype;
672                    break;
673                } else if (!partialMatchFound && language.equals(subtypeLanguage)) {
674                    // Partial match (e.g. system locale is "en_US" and subtype locale is "en")
675                    applicableSubtype = subtype;
676                    partialMatchFound = true;
677                }
678            }
679        }
680
681        if (applicableSubtype == null && canIgnoreLocaleAsLastResort) {
682            return firstMatchedModeSubtype;
683        }
684
685        // The first subtype applicable to the system locale will be defined as the most applicable
686        // subtype.
687        if (DEBUG) {
688            if (applicableSubtype != null) {
689                Slog.d(TAG, "Applicable InputMethodSubtype was found: "
690                        + applicableSubtype.getMode() + "," + applicableSubtype.getLocale());
691            }
692        }
693        return applicableSubtype;
694    }
695
696    public static boolean canAddToLastInputMethod(InputMethodSubtype subtype) {
697        if (subtype == null) return true;
698        return !subtype.isAuxiliary();
699    }
700
701    public static void setNonSelectedSystemImesDisabledUntilUsed(
702            IPackageManager packageManager, List<InputMethodInfo> enabledImis,
703            int userId, String callingPackage) {
704        if (DEBUG) {
705            Slog.d(TAG, "setNonSelectedSystemImesDisabledUntilUsed");
706        }
707        final String[] systemImesDisabledUntilUsed = Resources.getSystem().getStringArray(
708                com.android.internal.R.array.config_disabledUntilUsedPreinstalledImes);
709        if (systemImesDisabledUntilUsed == null || systemImesDisabledUntilUsed.length == 0) {
710            return;
711        }
712        // Only the current spell checker should be treated as an enabled one.
713        final SpellCheckerInfo currentSpellChecker =
714                TextServicesManager.getInstance().getCurrentSpellChecker();
715        for (final String packageName : systemImesDisabledUntilUsed) {
716            if (DEBUG) {
717                Slog.d(TAG, "check " + packageName);
718            }
719            boolean enabledIme = false;
720            for (int j = 0; j < enabledImis.size(); ++j) {
721                final InputMethodInfo imi = enabledImis.get(j);
722                if (packageName.equals(imi.getPackageName())) {
723                    enabledIme = true;
724                    break;
725                }
726            }
727            if (enabledIme) {
728                // enabled ime. skip
729                continue;
730            }
731            if (currentSpellChecker != null
732                    && packageName.equals(currentSpellChecker.getPackageName())) {
733                // enabled spell checker. skip
734                if (DEBUG) {
735                    Slog.d(TAG, packageName + " is the current spell checker. skip");
736                }
737                continue;
738            }
739            ApplicationInfo ai = null;
740            try {
741                ai = packageManager.getApplicationInfo(packageName,
742                        PackageManager.GET_DISABLED_UNTIL_USED_COMPONENTS, userId);
743            } catch (RemoteException e) {
744                Slog.w(TAG, "getApplicationInfo failed. packageName=" + packageName
745                        + " userId=" + userId, e);
746                continue;
747            }
748            if (ai == null) {
749                // No app found for packageName
750                continue;
751            }
752            final boolean isSystemPackage = (ai.flags & ApplicationInfo.FLAG_SYSTEM) != 0;
753            if (!isSystemPackage) {
754                continue;
755            }
756            setDisabledUntilUsed(packageManager, packageName, userId, callingPackage);
757        }
758    }
759
760    private static void setDisabledUntilUsed(IPackageManager packageManager, String packageName,
761            int userId, String callingPackage) {
762        final int state;
763        try {
764            state = packageManager.getApplicationEnabledSetting(packageName, userId);
765        } catch (RemoteException e) {
766            Slog.w(TAG, "getApplicationEnabledSetting failed. packageName=" + packageName
767                    + " userId=" + userId, e);
768            return;
769        }
770        if (state == PackageManager.COMPONENT_ENABLED_STATE_DEFAULT
771                || state == PackageManager.COMPONENT_ENABLED_STATE_ENABLED) {
772            if (DEBUG) {
773                Slog.d(TAG, "Update state(" + packageName + "): DISABLED_UNTIL_USED");
774            }
775            try {
776                packageManager.setApplicationEnabledSetting(packageName,
777                        PackageManager.COMPONENT_ENABLED_STATE_DISABLED_UNTIL_USED,
778                        0 /* newState */, userId, callingPackage);
779            } catch (RemoteException e) {
780                Slog.w(TAG, "setApplicationEnabledSetting failed. packageName=" + packageName
781                        + " userId=" + userId + " callingPackage=" + callingPackage, e);
782                return;
783            }
784        } else {
785            if (DEBUG) {
786                Slog.d(TAG, packageName + " is already DISABLED_UNTIL_USED");
787            }
788        }
789    }
790
791    public static CharSequence getImeAndSubtypeDisplayName(Context context, InputMethodInfo imi,
792            InputMethodSubtype subtype) {
793        final CharSequence imiLabel = imi.loadLabel(context.getPackageManager());
794        return subtype != null
795                ? TextUtils.concat(subtype.getDisplayName(context,
796                        imi.getPackageName(), imi.getServiceInfo().applicationInfo),
797                                (TextUtils.isEmpty(imiLabel) ?
798                                        "" : " - " + imiLabel))
799                : imiLabel;
800    }
801
802    /**
803     * Returns true if a package name belongs to a UID.
804     *
805     * <p>This is a simple wrapper of {@link AppOpsManager#checkPackage(int, String)}.</p>
806     * @param appOpsManager the {@link AppOpsManager} object to be used for the validation.
807     * @param uid the UID to be validated.
808     * @param packageName the package name.
809     * @return {@code true} if the package name belongs to the UID.
810     */
811    public static boolean checkIfPackageBelongsToUid(final AppOpsManager appOpsManager,
812            final int uid, final String packageName) {
813        try {
814            appOpsManager.checkPackage(uid, packageName);
815            return true;
816        } catch (SecurityException e) {
817            return false;
818        }
819    }
820
821    /**
822     * Parses the setting stored input methods and subtypes string value.
823     *
824     * @param inputMethodsAndSubtypesString The input method subtypes value stored in settings.
825     * @return Map from input method ID to set of input method subtypes IDs.
826     */
827    @VisibleForTesting
828    public static ArrayMap<String, ArraySet<String>> parseInputMethodsAndSubtypesString(
829            @Nullable final String inputMethodsAndSubtypesString) {
830
831        final ArrayMap<String, ArraySet<String>> imeMap = new ArrayMap<>();
832        if (TextUtils.isEmpty(inputMethodsAndSubtypesString)) {
833            return imeMap;
834        }
835
836        final SimpleStringSplitter typeSplitter =
837                new SimpleStringSplitter(INPUT_METHOD_SEPARATOR);
838        final SimpleStringSplitter subtypeSplitter =
839                new SimpleStringSplitter(INPUT_METHOD_SUBTYPE_SEPARATOR);
840
841        List<Pair<String, ArrayList<String>>> allImeSettings =
842                InputMethodSettings.buildInputMethodsAndSubtypeList(inputMethodsAndSubtypesString,
843                        typeSplitter,
844                        subtypeSplitter);
845        for (Pair<String, ArrayList<String>> ime : allImeSettings) {
846            ArraySet<String> subtypes = new ArraySet<>();
847            if (ime.second != null) {
848                subtypes.addAll(ime.second);
849            }
850            imeMap.put(ime.first, subtypes);
851        }
852        return imeMap;
853    }
854
855    @NonNull
856    public static String buildInputMethodsAndSubtypesString(
857            @NonNull final ArrayMap<String, ArraySet<String>> map) {
858        // we want to use the canonical InputMethodSettings implementation,
859        // so we convert data structures first.
860        List<Pair<String, ArrayList<String>>> imeMap = new ArrayList<>(4);
861        for (ArrayMap.Entry<String, ArraySet<String>> entry : map.entrySet()) {
862            final String imeName = entry.getKey();
863            final ArraySet<String> subtypeSet = entry.getValue();
864            final ArrayList<String> subtypes = new ArrayList<>(2);
865            if (subtypeSet != null) {
866                subtypes.addAll(subtypeSet);
867            }
868            imeMap.add(new Pair<>(imeName, subtypes));
869        }
870        return InputMethodSettings.buildInputMethodsSettingString(imeMap);
871    }
872
873    /**
874     * Utility class for putting and getting settings for InputMethod
875     * TODO: Move all putters and getters of settings to this class.
876     */
877    public static class InputMethodSettings {
878        private final TextUtils.SimpleStringSplitter mInputMethodSplitter =
879                new TextUtils.SimpleStringSplitter(INPUT_METHOD_SEPARATOR);
880
881        private final TextUtils.SimpleStringSplitter mSubtypeSplitter =
882                new TextUtils.SimpleStringSplitter(INPUT_METHOD_SUBTYPE_SEPARATOR);
883
884        private final Resources mRes;
885        private final ContentResolver mResolver;
886        private final HashMap<String, InputMethodInfo> mMethodMap;
887        private final ArrayList<InputMethodInfo> mMethodList;
888
889        /**
890         * On-memory data store to emulate when {@link #mCopyOnWrite} is {@code true}.
891         */
892        private final HashMap<String, String> mCopyOnWriteDataStore = new HashMap<>();
893
894        private boolean mCopyOnWrite = false;
895        @NonNull
896        private String mEnabledInputMethodsStrCache = "";
897        @UserIdInt
898        private int mCurrentUserId;
899        private int[] mCurrentProfileIds = new int[0];
900
901        private static void buildEnabledInputMethodsSettingString(
902                StringBuilder builder, Pair<String, ArrayList<String>> ime) {
903            builder.append(ime.first);
904            // Inputmethod and subtypes are saved in the settings as follows:
905            // ime0;subtype0;subtype1:ime1;subtype0:ime2:ime3;subtype0;subtype1
906            for (String subtypeId: ime.second) {
907                builder.append(INPUT_METHOD_SUBTYPE_SEPARATOR).append(subtypeId);
908            }
909        }
910
911        public static String buildInputMethodsSettingString(
912                List<Pair<String, ArrayList<String>>> allImeSettingsMap) {
913            final StringBuilder b = new StringBuilder();
914            boolean needsSeparator = false;
915            for (Pair<String, ArrayList<String>> ime : allImeSettingsMap) {
916                if (needsSeparator) {
917                    b.append(INPUT_METHOD_SEPARATOR);
918                }
919                buildEnabledInputMethodsSettingString(b, ime);
920                needsSeparator = true;
921            }
922            return b.toString();
923        }
924
925        public static List<Pair<String, ArrayList<String>>> buildInputMethodsAndSubtypeList(
926                String enabledInputMethodsStr,
927                TextUtils.SimpleStringSplitter inputMethodSplitter,
928                TextUtils.SimpleStringSplitter subtypeSplitter) {
929            ArrayList<Pair<String, ArrayList<String>>> imsList = new ArrayList<>();
930            if (TextUtils.isEmpty(enabledInputMethodsStr)) {
931                return imsList;
932            }
933            inputMethodSplitter.setString(enabledInputMethodsStr);
934            while (inputMethodSplitter.hasNext()) {
935                String nextImsStr = inputMethodSplitter.next();
936                subtypeSplitter.setString(nextImsStr);
937                if (subtypeSplitter.hasNext()) {
938                    ArrayList<String> subtypeHashes = new ArrayList<>();
939                    // The first element is ime id.
940                    String imeId = subtypeSplitter.next();
941                    while (subtypeSplitter.hasNext()) {
942                        subtypeHashes.add(subtypeSplitter.next());
943                    }
944                    imsList.add(new Pair<>(imeId, subtypeHashes));
945                }
946            }
947            return imsList;
948        }
949
950        public InputMethodSettings(
951                Resources res, ContentResolver resolver,
952                HashMap<String, InputMethodInfo> methodMap, ArrayList<InputMethodInfo> methodList,
953                @UserIdInt int userId, boolean copyOnWrite) {
954            mRes = res;
955            mResolver = resolver;
956            mMethodMap = methodMap;
957            mMethodList = methodList;
958            switchCurrentUser(userId, copyOnWrite);
959        }
960
961        /**
962         * Must be called when the current user is changed.
963         *
964         * @param userId The user ID.
965         * @param copyOnWrite If {@code true}, for each settings key
966         * (e.g. {@link Settings.Secure#ACTION_INPUT_METHOD_SUBTYPE_SETTINGS}) we use the actual
967         * settings on the {@link Settings.Secure} until we do the first write operation.
968         */
969        public void switchCurrentUser(@UserIdInt int userId, boolean copyOnWrite) {
970            if (DEBUG) {
971                Slog.d(TAG, "--- Switch the current user from " + mCurrentUserId + " to " + userId);
972            }
973            if (mCurrentUserId != userId || mCopyOnWrite != copyOnWrite) {
974                mCopyOnWriteDataStore.clear();
975                mEnabledInputMethodsStrCache = "";
976                // TODO: mCurrentProfileIds should be cleared here.
977            }
978            mCurrentUserId = userId;
979            mCopyOnWrite = copyOnWrite;
980            // TODO: mCurrentProfileIds should be updated here.
981        }
982
983        private void putString(@NonNull final String key, @Nullable final String str) {
984            if (mCopyOnWrite) {
985                mCopyOnWriteDataStore.put(key, str);
986            } else {
987                Settings.Secure.putStringForUser(mResolver, key, str, mCurrentUserId);
988            }
989        }
990
991        @Nullable
992        private String getString(@NonNull final String key, @Nullable final String defaultValue) {
993            final String result;
994            if (mCopyOnWrite && mCopyOnWriteDataStore.containsKey(key)) {
995                result = mCopyOnWriteDataStore.get(key);
996            } else {
997                result = Settings.Secure.getStringForUser(mResolver, key, mCurrentUserId);
998            }
999            return result != null ? result : defaultValue;
1000        }
1001
1002        private void putInt(final String key, final int value) {
1003            if (mCopyOnWrite) {
1004                mCopyOnWriteDataStore.put(key, String.valueOf(value));
1005            } else {
1006                Settings.Secure.putIntForUser(mResolver, key, value, mCurrentUserId);
1007            }
1008        }
1009
1010        private int getInt(final String key, final int defaultValue) {
1011            if (mCopyOnWrite && mCopyOnWriteDataStore.containsKey(key)) {
1012                final String result = mCopyOnWriteDataStore.get(key);
1013                return result != null ? Integer.parseInt(result) : 0;
1014            }
1015            return Settings.Secure.getIntForUser(mResolver, key, defaultValue, mCurrentUserId);
1016        }
1017
1018        private void putBoolean(final String key, final boolean value) {
1019            putInt(key, value ? 1 : 0);
1020        }
1021
1022        private boolean getBoolean(final String key, final boolean defaultValue) {
1023            return getInt(key, defaultValue ? 1 : 0) == 1;
1024        }
1025
1026        public void setCurrentProfileIds(int[] currentProfileIds) {
1027            synchronized (this) {
1028                mCurrentProfileIds = currentProfileIds;
1029            }
1030        }
1031
1032        public boolean isCurrentProfile(int userId) {
1033            synchronized (this) {
1034                if (userId == mCurrentUserId) return true;
1035                for (int i = 0; i < mCurrentProfileIds.length; i++) {
1036                    if (userId == mCurrentProfileIds[i]) return true;
1037                }
1038                return false;
1039            }
1040        }
1041
1042        public ArrayList<InputMethodInfo> getEnabledInputMethodListLocked() {
1043            return createEnabledInputMethodListLocked(
1044                    getEnabledInputMethodsAndSubtypeListLocked());
1045        }
1046
1047        public List<InputMethodSubtype> getEnabledInputMethodSubtypeListLocked(
1048                Context context, InputMethodInfo imi, boolean allowsImplicitlySelectedSubtypes) {
1049            List<InputMethodSubtype> enabledSubtypes =
1050                    getEnabledInputMethodSubtypeListLocked(imi);
1051            if (allowsImplicitlySelectedSubtypes && enabledSubtypes.isEmpty()) {
1052                enabledSubtypes = InputMethodUtils.getImplicitlyApplicableSubtypesLocked(
1053                        context.getResources(), imi);
1054            }
1055            return InputMethodSubtype.sort(context, 0, imi, enabledSubtypes);
1056        }
1057
1058        public List<InputMethodSubtype> getEnabledInputMethodSubtypeListLocked(
1059                InputMethodInfo imi) {
1060            List<Pair<String, ArrayList<String>>> imsList =
1061                    getEnabledInputMethodsAndSubtypeListLocked();
1062            ArrayList<InputMethodSubtype> enabledSubtypes = new ArrayList<>();
1063            if (imi != null) {
1064                for (Pair<String, ArrayList<String>> imsPair : imsList) {
1065                    InputMethodInfo info = mMethodMap.get(imsPair.first);
1066                    if (info != null && info.getId().equals(imi.getId())) {
1067                        final int subtypeCount = info.getSubtypeCount();
1068                        for (int i = 0; i < subtypeCount; ++i) {
1069                            InputMethodSubtype ims = info.getSubtypeAt(i);
1070                            for (String s: imsPair.second) {
1071                                if (String.valueOf(ims.hashCode()).equals(s)) {
1072                                    enabledSubtypes.add(ims);
1073                                }
1074                            }
1075                        }
1076                        break;
1077                    }
1078                }
1079            }
1080            return enabledSubtypes;
1081        }
1082
1083        // At the initial boot, the settings for input methods are not set,
1084        // so we need to enable IME in that case.
1085        public void enableAllIMEsIfThereIsNoEnabledIME() {
1086            if (TextUtils.isEmpty(getEnabledInputMethodsStr())) {
1087                StringBuilder sb = new StringBuilder();
1088                final int N = mMethodList.size();
1089                for (int i = 0; i < N; i++) {
1090                    InputMethodInfo imi = mMethodList.get(i);
1091                    Slog.i(TAG, "Adding: " + imi.getId());
1092                    if (i > 0) sb.append(':');
1093                    sb.append(imi.getId());
1094                }
1095                putEnabledInputMethodsStr(sb.toString());
1096            }
1097        }
1098
1099        public List<Pair<String, ArrayList<String>>> getEnabledInputMethodsAndSubtypeListLocked() {
1100            return buildInputMethodsAndSubtypeList(getEnabledInputMethodsStr(),
1101                    mInputMethodSplitter,
1102                    mSubtypeSplitter);
1103        }
1104
1105        public void appendAndPutEnabledInputMethodLocked(String id, boolean reloadInputMethodStr) {
1106            if (reloadInputMethodStr) {
1107                getEnabledInputMethodsStr();
1108            }
1109            if (TextUtils.isEmpty(mEnabledInputMethodsStrCache)) {
1110                // Add in the newly enabled input method.
1111                putEnabledInputMethodsStr(id);
1112            } else {
1113                putEnabledInputMethodsStr(
1114                        mEnabledInputMethodsStrCache + INPUT_METHOD_SEPARATOR + id);
1115            }
1116        }
1117
1118        /**
1119         * Build and put a string of EnabledInputMethods with removing specified Id.
1120         * @return the specified id was removed or not.
1121         */
1122        public boolean buildAndPutEnabledInputMethodsStrRemovingIdLocked(
1123                StringBuilder builder, List<Pair<String, ArrayList<String>>> imsList, String id) {
1124            boolean isRemoved = false;
1125            boolean needsAppendSeparator = false;
1126            for (Pair<String, ArrayList<String>> ims: imsList) {
1127                String curId = ims.first;
1128                if (curId.equals(id)) {
1129                    // We are disabling this input method, and it is
1130                    // currently enabled.  Skip it to remove from the
1131                    // new list.
1132                    isRemoved = true;
1133                } else {
1134                    if (needsAppendSeparator) {
1135                        builder.append(INPUT_METHOD_SEPARATOR);
1136                    } else {
1137                        needsAppendSeparator = true;
1138                    }
1139                    buildEnabledInputMethodsSettingString(builder, ims);
1140                }
1141            }
1142            if (isRemoved) {
1143                // Update the setting with the new list of input methods.
1144                putEnabledInputMethodsStr(builder.toString());
1145            }
1146            return isRemoved;
1147        }
1148
1149        private ArrayList<InputMethodInfo> createEnabledInputMethodListLocked(
1150                List<Pair<String, ArrayList<String>>> imsList) {
1151            final ArrayList<InputMethodInfo> res = new ArrayList<>();
1152            for (Pair<String, ArrayList<String>> ims: imsList) {
1153                InputMethodInfo info = mMethodMap.get(ims.first);
1154                if (info != null) {
1155                    res.add(info);
1156                }
1157            }
1158            return res;
1159        }
1160
1161        private void putEnabledInputMethodsStr(@Nullable String str) {
1162            if (DEBUG) {
1163                Slog.d(TAG, "putEnabledInputMethodStr: " + str);
1164            }
1165            if (TextUtils.isEmpty(str)) {
1166                // OK to coalesce to null, since getEnabledInputMethodsStr() can take care of the
1167                // empty data scenario.
1168                putString(Settings.Secure.ENABLED_INPUT_METHODS, null);
1169            } else {
1170                putString(Settings.Secure.ENABLED_INPUT_METHODS, str);
1171            }
1172            // TODO: Update callers of putEnabledInputMethodsStr to make str @NonNull.
1173            mEnabledInputMethodsStrCache = (str != null ? str : "");
1174        }
1175
1176        @NonNull
1177        public String getEnabledInputMethodsStr() {
1178            mEnabledInputMethodsStrCache = getString(Settings.Secure.ENABLED_INPUT_METHODS, "");
1179            if (DEBUG) {
1180                Slog.d(TAG, "getEnabledInputMethodsStr: " + mEnabledInputMethodsStrCache
1181                        + ", " + mCurrentUserId);
1182            }
1183            return mEnabledInputMethodsStrCache;
1184        }
1185
1186        private void saveSubtypeHistory(
1187                List<Pair<String, String>> savedImes, String newImeId, String newSubtypeId) {
1188            StringBuilder builder = new StringBuilder();
1189            boolean isImeAdded = false;
1190            if (!TextUtils.isEmpty(newImeId) && !TextUtils.isEmpty(newSubtypeId)) {
1191                builder.append(newImeId).append(INPUT_METHOD_SUBTYPE_SEPARATOR).append(
1192                        newSubtypeId);
1193                isImeAdded = true;
1194            }
1195            for (Pair<String, String> ime: savedImes) {
1196                String imeId = ime.first;
1197                String subtypeId = ime.second;
1198                if (TextUtils.isEmpty(subtypeId)) {
1199                    subtypeId = NOT_A_SUBTYPE_ID_STR;
1200                }
1201                if (isImeAdded) {
1202                    builder.append(INPUT_METHOD_SEPARATOR);
1203                } else {
1204                    isImeAdded = true;
1205                }
1206                builder.append(imeId).append(INPUT_METHOD_SUBTYPE_SEPARATOR).append(
1207                        subtypeId);
1208            }
1209            // Remove the last INPUT_METHOD_SEPARATOR
1210            putSubtypeHistoryStr(builder.toString());
1211        }
1212
1213        private void addSubtypeToHistory(String imeId, String subtypeId) {
1214            List<Pair<String, String>> subtypeHistory = loadInputMethodAndSubtypeHistoryLocked();
1215            for (Pair<String, String> ime: subtypeHistory) {
1216                if (ime.first.equals(imeId)) {
1217                    if (DEBUG) {
1218                        Slog.v(TAG, "Subtype found in the history: " + imeId + ", "
1219                                + ime.second);
1220                    }
1221                    // We should break here
1222                    subtypeHistory.remove(ime);
1223                    break;
1224                }
1225            }
1226            if (DEBUG) {
1227                Slog.v(TAG, "Add subtype to the history: " + imeId + ", " + subtypeId);
1228            }
1229            saveSubtypeHistory(subtypeHistory, imeId, subtypeId);
1230        }
1231
1232        private void putSubtypeHistoryStr(@NonNull String str) {
1233            if (DEBUG) {
1234                Slog.d(TAG, "putSubtypeHistoryStr: " + str);
1235            }
1236            if (TextUtils.isEmpty(str)) {
1237                // OK to coalesce to null, since getSubtypeHistoryStr() can take care of the empty
1238                // data scenario.
1239                putString(Settings.Secure.INPUT_METHODS_SUBTYPE_HISTORY, null);
1240            } else {
1241                putString(Settings.Secure.INPUT_METHODS_SUBTYPE_HISTORY, str);
1242            }
1243        }
1244
1245        public Pair<String, String> getLastInputMethodAndSubtypeLocked() {
1246            // Gets the first one from the history
1247            return getLastSubtypeForInputMethodLockedInternal(null);
1248        }
1249
1250        public String getLastSubtypeForInputMethodLocked(String imeId) {
1251            Pair<String, String> ime = getLastSubtypeForInputMethodLockedInternal(imeId);
1252            if (ime != null) {
1253                return ime.second;
1254            } else {
1255                return null;
1256            }
1257        }
1258
1259        private Pair<String, String> getLastSubtypeForInputMethodLockedInternal(String imeId) {
1260            List<Pair<String, ArrayList<String>>> enabledImes =
1261                    getEnabledInputMethodsAndSubtypeListLocked();
1262            List<Pair<String, String>> subtypeHistory = loadInputMethodAndSubtypeHistoryLocked();
1263            for (Pair<String, String> imeAndSubtype : subtypeHistory) {
1264                final String imeInTheHistory = imeAndSubtype.first;
1265                // If imeId is empty, returns the first IME and subtype in the history
1266                if (TextUtils.isEmpty(imeId) || imeInTheHistory.equals(imeId)) {
1267                    final String subtypeInTheHistory = imeAndSubtype.second;
1268                    final String subtypeHashCode =
1269                            getEnabledSubtypeHashCodeForInputMethodAndSubtypeLocked(
1270                                    enabledImes, imeInTheHistory, subtypeInTheHistory);
1271                    if (!TextUtils.isEmpty(subtypeHashCode)) {
1272                        if (DEBUG) {
1273                            Slog.d(TAG, "Enabled subtype found in the history: " + subtypeHashCode);
1274                        }
1275                        return new Pair<>(imeInTheHistory, subtypeHashCode);
1276                    }
1277                }
1278            }
1279            if (DEBUG) {
1280                Slog.d(TAG, "No enabled IME found in the history");
1281            }
1282            return null;
1283        }
1284
1285        private String getEnabledSubtypeHashCodeForInputMethodAndSubtypeLocked(List<Pair<String,
1286                ArrayList<String>>> enabledImes, String imeId, String subtypeHashCode) {
1287            for (Pair<String, ArrayList<String>> enabledIme: enabledImes) {
1288                if (enabledIme.first.equals(imeId)) {
1289                    final ArrayList<String> explicitlyEnabledSubtypes = enabledIme.second;
1290                    final InputMethodInfo imi = mMethodMap.get(imeId);
1291                    if (explicitlyEnabledSubtypes.size() == 0) {
1292                        // If there are no explicitly enabled subtypes, applicable subtypes are
1293                        // enabled implicitly.
1294                        // If IME is enabled and no subtypes are enabled, applicable subtypes
1295                        // are enabled implicitly, so needs to treat them to be enabled.
1296                        if (imi != null && imi.getSubtypeCount() > 0) {
1297                            List<InputMethodSubtype> implicitlySelectedSubtypes =
1298                                    getImplicitlyApplicableSubtypesLocked(mRes, imi);
1299                            if (implicitlySelectedSubtypes != null) {
1300                                final int N = implicitlySelectedSubtypes.size();
1301                                for (int i = 0; i < N; ++i) {
1302                                    final InputMethodSubtype st = implicitlySelectedSubtypes.get(i);
1303                                    if (String.valueOf(st.hashCode()).equals(subtypeHashCode)) {
1304                                        return subtypeHashCode;
1305                                    }
1306                                }
1307                            }
1308                        }
1309                    } else {
1310                        for (String s: explicitlyEnabledSubtypes) {
1311                            if (s.equals(subtypeHashCode)) {
1312                                // If both imeId and subtypeId are enabled, return subtypeId.
1313                                try {
1314                                    final int hashCode = Integer.parseInt(subtypeHashCode);
1315                                    // Check whether the subtype id is valid or not
1316                                    if (isValidSubtypeId(imi, hashCode)) {
1317                                        return s;
1318                                    } else {
1319                                        return NOT_A_SUBTYPE_ID_STR;
1320                                    }
1321                                } catch (NumberFormatException e) {
1322                                    return NOT_A_SUBTYPE_ID_STR;
1323                                }
1324                            }
1325                        }
1326                    }
1327                    // If imeId was enabled but subtypeId was disabled.
1328                    return NOT_A_SUBTYPE_ID_STR;
1329                }
1330            }
1331            // If both imeId and subtypeId are disabled, return null
1332            return null;
1333        }
1334
1335        private List<Pair<String, String>> loadInputMethodAndSubtypeHistoryLocked() {
1336            ArrayList<Pair<String, String>> imsList = new ArrayList<>();
1337            final String subtypeHistoryStr = getSubtypeHistoryStr();
1338            if (TextUtils.isEmpty(subtypeHistoryStr)) {
1339                return imsList;
1340            }
1341            mInputMethodSplitter.setString(subtypeHistoryStr);
1342            while (mInputMethodSplitter.hasNext()) {
1343                String nextImsStr = mInputMethodSplitter.next();
1344                mSubtypeSplitter.setString(nextImsStr);
1345                if (mSubtypeSplitter.hasNext()) {
1346                    String subtypeId = NOT_A_SUBTYPE_ID_STR;
1347                    // The first element is ime id.
1348                    String imeId = mSubtypeSplitter.next();
1349                    while (mSubtypeSplitter.hasNext()) {
1350                        subtypeId = mSubtypeSplitter.next();
1351                        break;
1352                    }
1353                    imsList.add(new Pair<>(imeId, subtypeId));
1354                }
1355            }
1356            return imsList;
1357        }
1358
1359        @NonNull
1360        private String getSubtypeHistoryStr() {
1361            final String history = getString(Settings.Secure.INPUT_METHODS_SUBTYPE_HISTORY, "");
1362            if (DEBUG) {
1363                Slog.d(TAG, "getSubtypeHistoryStr: " + history);
1364            }
1365            return history;
1366        }
1367
1368        public void putSelectedInputMethod(String imeId) {
1369            if (DEBUG) {
1370                Slog.d(TAG, "putSelectedInputMethodStr: " + imeId + ", "
1371                        + mCurrentUserId);
1372            }
1373            putString(Settings.Secure.DEFAULT_INPUT_METHOD, imeId);
1374        }
1375
1376        public void putSelectedSubtype(int subtypeId) {
1377            if (DEBUG) {
1378                Slog.d(TAG, "putSelectedInputMethodSubtypeStr: " + subtypeId + ", "
1379                        + mCurrentUserId);
1380            }
1381            putInt(Settings.Secure.SELECTED_INPUT_METHOD_SUBTYPE, subtypeId);
1382        }
1383
1384        @Nullable
1385        public String getSelectedInputMethod() {
1386            final String imi = getString(Settings.Secure.DEFAULT_INPUT_METHOD, null);
1387            if (DEBUG) {
1388                Slog.d(TAG, "getSelectedInputMethodStr: " + imi);
1389            }
1390            return imi;
1391        }
1392
1393        public boolean isSubtypeSelected() {
1394            return getSelectedInputMethodSubtypeHashCode() != NOT_A_SUBTYPE_ID;
1395        }
1396
1397        private int getSelectedInputMethodSubtypeHashCode() {
1398            return getInt(Settings.Secure.SELECTED_INPUT_METHOD_SUBTYPE, NOT_A_SUBTYPE_ID);
1399        }
1400
1401        public boolean isShowImeWithHardKeyboardEnabled() {
1402            return getBoolean(Settings.Secure.SHOW_IME_WITH_HARD_KEYBOARD, false);
1403        }
1404
1405        public void setShowImeWithHardKeyboard(boolean show) {
1406            putBoolean(Settings.Secure.SHOW_IME_WITH_HARD_KEYBOARD, show);
1407        }
1408
1409        @UserIdInt
1410        public int getCurrentUserId() {
1411            return mCurrentUserId;
1412        }
1413
1414        public int getSelectedInputMethodSubtypeId(String selectedImiId) {
1415            final InputMethodInfo imi = mMethodMap.get(selectedImiId);
1416            if (imi == null) {
1417                return NOT_A_SUBTYPE_ID;
1418            }
1419            final int subtypeHashCode = getSelectedInputMethodSubtypeHashCode();
1420            return getSubtypeIdFromHashCode(imi, subtypeHashCode);
1421        }
1422
1423        public void saveCurrentInputMethodAndSubtypeToHistory(
1424                String curMethodId, InputMethodSubtype currentSubtype) {
1425            String subtypeId = NOT_A_SUBTYPE_ID_STR;
1426            if (currentSubtype != null) {
1427                subtypeId = String.valueOf(currentSubtype.hashCode());
1428            }
1429            if (canAddToLastInputMethod(currentSubtype)) {
1430                addSubtypeToHistory(curMethodId, subtypeId);
1431            }
1432        }
1433
1434        public HashMap<InputMethodInfo, List<InputMethodSubtype>>
1435                getExplicitlyOrImplicitlyEnabledInputMethodsAndSubtypeListLocked(Context context) {
1436            HashMap<InputMethodInfo, List<InputMethodSubtype>> enabledInputMethodAndSubtypes =
1437                    new HashMap<>();
1438            for (InputMethodInfo imi: getEnabledInputMethodListLocked()) {
1439                enabledInputMethodAndSubtypes.put(
1440                        imi, getEnabledInputMethodSubtypeListLocked(context, imi, true));
1441            }
1442            return enabledInputMethodAndSubtypes;
1443        }
1444
1445        public void dumpLocked(final Printer pw, final String prefix) {
1446            pw.println(prefix + "mCurrentUserId=" + mCurrentUserId);
1447            pw.println(prefix + "mCurrentProfileIds=" + Arrays.toString(mCurrentProfileIds));
1448            pw.println(prefix + "mCopyOnWrite=" + mCopyOnWrite);
1449            pw.println(prefix + "mEnabledInputMethodsStrCache=" + mEnabledInputMethodsStrCache);
1450        }
1451    }
1452
1453    // For spell checker service manager.
1454    // TODO: Should we have TextServicesUtils.java?
1455    private static final Locale LOCALE_EN_US = new Locale("en", "US");
1456    private static final Locale LOCALE_EN_GB = new Locale("en", "GB");
1457
1458    /**
1459     * Returns a list of {@link Locale} in the order of appropriateness for the default spell
1460     * checker service.
1461     *
1462     * <p>If the system language is English, and the region is also explicitly specified in the
1463     * system locale, the following fallback order will be applied.</p>
1464     * <ul>
1465     * <li>(system-locale-language, system-locale-region, system-locale-variant) (if exists)</li>
1466     * <li>(system-locale-language, system-locale-region)</li>
1467     * <li>("en", "US")</li>
1468     * <li>("en", "GB")</li>
1469     * <li>("en")</li>
1470     * </ul>
1471     *
1472     * <p>If the system language is English, but no region is specified in the system locale,
1473     * the following fallback order will be applied.</p>
1474     * <ul>
1475     * <li>("en")</li>
1476     * <li>("en", "US")</li>
1477     * <li>("en", "GB")</li>
1478     * </ul>
1479     *
1480     * <p>If the system language is not English, the following fallback order will be applied.</p>
1481     * <ul>
1482     * <li>(system-locale-language, system-locale-region, system-locale-variant) (if exists)</li>
1483     * <li>(system-locale-language, system-locale-region) (if exists)</li>
1484     * <li>(system-locale-language) (if exists)</li>
1485     * <li>("en", "US")</li>
1486     * <li>("en", "GB")</li>
1487     * <li>("en")</li>
1488     * </ul>
1489     *
1490     * @param systemLocale the current system locale to be taken into consideration.
1491     * @return a list of {@link Locale}. The first one is considered to be most appropriate.
1492     */
1493    @VisibleForTesting
1494    public static ArrayList<Locale> getSuitableLocalesForSpellChecker(
1495            @Nullable final Locale systemLocale) {
1496        final Locale systemLocaleLanguageCountryVariant;
1497        final Locale systemLocaleLanguageCountry;
1498        final Locale systemLocaleLanguage;
1499        if (systemLocale != null) {
1500            final String language = systemLocale.getLanguage();
1501            final boolean hasLanguage = !TextUtils.isEmpty(language);
1502            final String country = systemLocale.getCountry();
1503            final boolean hasCountry = !TextUtils.isEmpty(country);
1504            final String variant = systemLocale.getVariant();
1505            final boolean hasVariant = !TextUtils.isEmpty(variant);
1506            if (hasLanguage && hasCountry && hasVariant) {
1507                systemLocaleLanguageCountryVariant = new Locale(language, country, variant);
1508            } else {
1509                systemLocaleLanguageCountryVariant = null;
1510            }
1511            if (hasLanguage && hasCountry) {
1512                systemLocaleLanguageCountry = new Locale(language, country);
1513            } else {
1514                systemLocaleLanguageCountry = null;
1515            }
1516            if (hasLanguage) {
1517                systemLocaleLanguage = new Locale(language);
1518            } else {
1519                systemLocaleLanguage = null;
1520            }
1521        } else {
1522            systemLocaleLanguageCountryVariant = null;
1523            systemLocaleLanguageCountry = null;
1524            systemLocaleLanguage = null;
1525        }
1526
1527        final ArrayList<Locale> locales = new ArrayList<>();
1528        if (systemLocaleLanguageCountryVariant != null) {
1529            locales.add(systemLocaleLanguageCountryVariant);
1530        }
1531
1532        if (Locale.ENGLISH.equals(systemLocaleLanguage)) {
1533            if (systemLocaleLanguageCountry != null) {
1534                // If the system language is English, and the region is also explicitly specified,
1535                // following fallback order will be applied.
1536                // - systemLocaleLanguageCountry [if systemLocaleLanguageCountry is non-null]
1537                // - en_US [if systemLocaleLanguageCountry is non-null and not en_US]
1538                // - en_GB [if systemLocaleLanguageCountry is non-null and not en_GB]
1539                // - en
1540                if (systemLocaleLanguageCountry != null) {
1541                    locales.add(systemLocaleLanguageCountry);
1542                }
1543                if (!LOCALE_EN_US.equals(systemLocaleLanguageCountry)) {
1544                    locales.add(LOCALE_EN_US);
1545                }
1546                if (!LOCALE_EN_GB.equals(systemLocaleLanguageCountry)) {
1547                    locales.add(LOCALE_EN_GB);
1548                }
1549                locales.add(Locale.ENGLISH);
1550            } else {
1551                // If the system language is English, but no region is specified, following
1552                // fallback order will be applied.
1553                // - en
1554                // - en_US
1555                // - en_GB
1556                locales.add(Locale.ENGLISH);
1557                locales.add(LOCALE_EN_US);
1558                locales.add(LOCALE_EN_GB);
1559            }
1560        } else {
1561            // If the system language is not English, the fallback order will be
1562            // - systemLocaleLanguageCountry  [if non-null]
1563            // - systemLocaleLanguage  [if non-null]
1564            // - en_US
1565            // - en_GB
1566            // - en
1567            if (systemLocaleLanguageCountry != null) {
1568                locales.add(systemLocaleLanguageCountry);
1569            }
1570            if (systemLocaleLanguage != null) {
1571                locales.add(systemLocaleLanguage);
1572            }
1573            locales.add(LOCALE_EN_US);
1574            locales.add(LOCALE_EN_GB);
1575            locales.add(Locale.ENGLISH);
1576        }
1577        return locales;
1578    }
1579}
1580