Merge "Quit auto-correct explicit accented letters to base letters."
diff --git a/common/src/com/android/inputmethod/latin/common/Constants.java b/common/src/com/android/inputmethod/latin/common/Constants.java
index abc377a..a860d35 100644
--- a/common/src/com/android/inputmethod/latin/common/Constants.java
+++ b/common/src/com/android/inputmethod/latin/common/Constants.java
@@ -179,7 +179,7 @@
 
     // (MAX_PREV_WORD_COUNT_FOR_N_GRAM + 1)-gram is supported in Java side. Needs to modify
     // MAX_PREV_WORD_COUNT_FOR_N_GRAM in native/jni/src/defines.h for suggestions.
-    public static final int MAX_PREV_WORD_COUNT_FOR_N_GRAM = 2;
+    public static final int MAX_PREV_WORD_COUNT_FOR_N_GRAM = 3;
 
     // Key events coming any faster than this are long-presses.
     public static final int LONG_PRESS_MILLISECONDS = 200;
diff --git a/java/res/values-eu-rES/strings-emoji-descriptions.xml b/java/res/values-eu-rES/strings-emoji-descriptions.xml
index 50c6924..49cf216 100644
--- a/java/res/values-eu-rES/strings-emoji-descriptions.xml
+++ b/java/res/values-eu-rES/strings-emoji-descriptions.xml
@@ -602,7 +602,7 @@
     <string name="spoken_emoji_1F4F0" msgid="6330208624731662525">"Egunkaria"</string>
     <string name="spoken_emoji_1F4F1" msgid="3966503935581675695">"Telefono mugikorra"</string>
     <string name="spoken_emoji_1F4F2" msgid="1057540341746100087">"Telefono mugikorra eta geziak eskuinalderantz ezkerraldean"</string>
-    <string name="spoken_emoji_1F4F3" msgid="5003984447315754658">"Bibrazio-modua"</string>
+    <string name="spoken_emoji_1F4F3" msgid="5003984447315754658">"Dardara modua"</string>
     <string name="spoken_emoji_1F4F4" msgid="5549847566968306253">"Telefono mugikorra itzalita"</string>
     <string name="spoken_emoji_1F4F5" msgid="3660199448671699238">"Telefono mugikorrik ez"</string>
     <string name="spoken_emoji_1F4F6" msgid="2676974903233268860">"Antena barrekin"</string>
diff --git a/java/res/values-fi/strings.xml b/java/res/values-fi/strings.xml
index 0308d18..6ef4b4e 100644
--- a/java/res/values-fi/strings.xml
+++ b/java/res/values-fi/strings.xml
@@ -170,9 +170,9 @@
     <string name="install_dict" msgid="180852772562189365">"Asenna"</string>
     <string name="cancel_download_dict" msgid="7843340278507019303">"Peruuta"</string>
     <string name="delete_dict" msgid="756853268088330054">"Poista"</string>
-    <string name="should_download_over_metered_prompt" msgid="1583881200688185508">"Laitteesi käyttökielelle on saatavilla sanakirja.&lt;br/&gt; Suosittelemme <xliff:g id="LANGUAGE_NAME">%1$s</xliff:g>-sanakirjan &lt;b&gt;lataamista&lt;/b&gt;, sillä se helpottaa laitteella kirjoittamista.&lt;br/&gt; &lt;br/&gt; Lataus kestää useimmiten muutaman minuutin 3G-yhteydellä. Latauksesta saatetaan periä maksu, ellei käytössäsi ole &lt;b&gt;rajoittamatonta tiedonsiirtopakettia&lt;/b&gt;.&lt;br/&gt; Jos et ole varma tiedonsiirtosopimuksesi tyypistä, etsi käyttöösi wifi-yhteys, niin lataus alkaa automaattisesti.&lt;br/&gt; &lt;br/&gt; Vinkki: voit ladata ja poistaa sanakirjoja mobiililaitteesi &lt;b&gt;Asetukset&lt;/b&gt;-valikon &lt;b&gt;Kieli ja syöttötapa&lt;/b&gt; -osiossa."</string>
+    <string name="should_download_over_metered_prompt" msgid="1583881200688185508">"Laitteesi käyttökielelle on saatavilla sanakirja.&lt;br/&gt; Suosittelemme <xliff:g id="LANGUAGE_NAME">%1$s</xliff:g>-sanakirjan &lt;b&gt;lataamista&lt;/b&gt;, sillä se helpottaa laitteella kirjoittamista.&lt;br/&gt; &lt;br/&gt; Lataus kestää useimmiten muutaman minuutin 3G-yhteydellä. Latauksesta saatetaan periä maksu, ellei käytössäsi ole &lt;b&gt;rajoittamatonta tiedonsiirtopakettia&lt;/b&gt;.&lt;br/&gt; Jos et ole varma tiedonsiirtosopimuksesi tyypistä, etsi käyttöösi Wi-Fi-yhteys, niin lataus alkaa automaattisesti.&lt;br/&gt; &lt;br/&gt; Vinkki: voit ladata ja poistaa sanakirjoja mobiililaitteesi &lt;b&gt;Asetukset&lt;/b&gt;-valikon &lt;b&gt;Kieli ja syöttötapa&lt;/b&gt; -osiossa."</string>
     <string name="download_over_metered" msgid="1643065851159409546">"Lataa nyt (<xliff:g id="SIZE_IN_MEGABYTES">%1$.1f</xliff:g> Mt)"</string>
-    <string name="do_not_download_over_metered" msgid="2176209579313941583">"Lataa wifi-yhteydellä"</string>
+    <string name="do_not_download_over_metered" msgid="2176209579313941583">"Lataa Wi-Fi-yhteydellä"</string>
     <string name="dict_available_notification_title" msgid="4583842811218581658">"Sanakirja on saatavilla kielelle <xliff:g id="LANGUAGE_NAME">%1$s</xliff:g>"</string>
     <string name="dict_available_notification_description" msgid="1075194169443163487">"Paina tätä, jos haluat tarkastella kohdetta ja ladata sen"</string>
     <string name="toast_downloading_suggestions" msgid="6128155879830851739">"Ladataan: kielen <xliff:g id="LANGUAGE_NAME">%1$s</xliff:g> ehdotukset ovat pian käytettävissä."</string>
diff --git a/java/res/values-gl-rES/strings.xml b/java/res/values-gl-rES/strings.xml
index d72bcb8..9616a26 100644
--- a/java/res/values-gl-rES/strings.xml
+++ b/java/res/values-gl-rES/strings.xml
@@ -30,9 +30,9 @@
     <string name="settings_screen_accounts" msgid="7570397912370223287">"Contas e privacidade"</string>
     <string name="settings_screen_appearance" msgid="9153102634339912029">"Aparencia e deseños"</string>
     <string name="settings_screen_multilingual" msgid="1391301621464509659">"Opcións multilingües"</string>
-    <string name="settings_screen_gesture" msgid="8826372746901183556">"Escritura mediante xestos"</string>
+    <string name="settings_screen_gesture" msgid="8826372746901183556">"Escritura xestual"</string>
     <string name="settings_screen_correction" msgid="1616818407747682955">"Corrección de texto"</string>
-    <string name="settings_screen_advanced" msgid="7472408607625972994">"Avanzada"</string>
+    <string name="settings_screen_advanced" msgid="7472408607625972994">"Opcións avanzadas"</string>
     <string name="settings_screen_theme" msgid="2137262503543943871">"Tema"</string>
     <string name="enable_split_keyboard" msgid="4177264923999493614">"Activar teclado dividido"</string>
     <string name="include_other_imes_in_language_switch_list" msgid="4533689960308565519">"Outros métodos de entrada"</string>
diff --git a/java/res/values-hi/strings.xml b/java/res/values-hi/strings.xml
index 239b56f..a4f2dd3 100644
--- a/java/res/values-hi/strings.xml
+++ b/java/res/values-hi/strings.xml
@@ -94,12 +94,12 @@
     <string name="subtype_en_GB" msgid="88170601942311355">"अंग्रेज़ी (यूके)"</string>
     <string name="subtype_en_US" msgid="6160452336634534239">"अंग्रेज़ी (यूएस)"</string>
     <string name="subtype_es_US" msgid="5583145191430180200">"स्पेनिश (यूएस)"</string>
-    <string name="subtype_hi_ZZ" msgid="8860448146262798623">"Hinglish"</string>
+    <string name="subtype_hi_ZZ" msgid="8860448146262798623">"हिंग्लिश"</string>
     <string name="subtype_sr_ZZ" msgid="9059219552986034343">"सर्बियाई (लैटिन)"</string>
     <string name="subtype_with_layout_en_GB" msgid="1931018968641592304">"अंग्रेज़ी (यूके) (<xliff:g id="KEYBOARD_LAYOUT">%s</xliff:g>)"</string>
     <string name="subtype_with_layout_en_US" msgid="8809311287529805422">"अंग्रेज़ी (यूएस) (<xliff:g id="KEYBOARD_LAYOUT">%s</xliff:g>)"</string>
     <string name="subtype_with_layout_es_US" msgid="510930471167541338">"स्‍पेनिश (यूएस) (<xliff:g id="KEYBOARD_LAYOUT">%s</xliff:g>)"</string>
-    <string name="subtype_with_layout_hi_ZZ" msgid="6827402953860547044">"Hinglish (<xliff:g id="KEYBOARD_LAYOUT">%s</xliff:g>)"</string>
+    <string name="subtype_with_layout_hi_ZZ" msgid="6827402953860547044">"हिंग्लिश (<xliff:g id="KEYBOARD_LAYOUT">%s</xliff:g>)"</string>
     <string name="subtype_with_layout_sr_ZZ" msgid="2859024772719772407">"सर्बियाई (<xliff:g id="KEYBOARD_LAYOUT">%s</xliff:g>)"</string>
     <string name="subtype_generic_traditional" msgid="8584594350973800586">"<xliff:g id="LANGUAGE_NAME">%s</xliff:g> (पारंपरिक)"</string>
     <string name="subtype_generic_compact" msgid="3353673321203202922">"<xliff:g id="LANGUAGE_NAME">%s</xliff:g> (संक्षिप्त)"</string>
diff --git a/java/res/values-ml-rIN/strings-emoji-descriptions.xml b/java/res/values-ml-rIN/strings-emoji-descriptions.xml
index a846f31..2fad192 100644
--- a/java/res/values-ml-rIN/strings-emoji-descriptions.xml
+++ b/java/res/values-ml-rIN/strings-emoji-descriptions.xml
@@ -348,7 +348,7 @@
     <string name="spoken_emoji_1F3E0" msgid="6277213201655811842">"വീടുനിർമ്മാണം"</string>
     <string name="spoken_emoji_1F3E1" msgid="233476176077538885">"പൂന്തോട്ടനുള്ള വീട്"</string>
     <string name="spoken_emoji_1F3E2" msgid="919736380093964570">"ഓഫീസ് കെട്ടിടം"</string>
-    <string name="spoken_emoji_1F3E3" msgid="6177606081825094184">"ജപ്പാനീസ് പോസ്‌റ്റ് ഓഫീസ്"</string>
+    <string name="spoken_emoji_1F3E3" msgid="6177606081825094184">"ജാപ്പനീസ്‌ പോസ്‌റ്റ് ഓഫീസ്"</string>
     <string name="spoken_emoji_1F3E4" msgid="717377871070970293">"യൂറോപ്പ്യൻ പോസ്‌റ്റ് ഓഫീസ്"</string>
     <string name="spoken_emoji_1F3E5" msgid="1350532500431776780">"ആശുപത്രി"</string>
     <string name="spoken_emoji_1F3E6" msgid="342132788513806214">"ബാങ്ക്"</string>
@@ -659,7 +659,7 @@
     <string name="spoken_emoji_1F52D" msgid="7549551775445177140">"ടെലിസ്‌കോപ്പ്"</string>
     <string name="spoken_emoji_1F52E" msgid="4457099417872625141">"സ്ഥടിക ബോൾ"</string>
     <string name="spoken_emoji_1F52F" msgid="8899031001317442792">"മധ്യഭാഗത്ത് കറുത്ത ഡോട്ടുള്ള ആറ് പോയിന്റുള്ള നക്ഷത്രം"</string>
-    <string name="spoken_emoji_1F530" msgid="3572898444281774023">"തുടക്കക്കാർക്കുള്ള ജപ്പാനീസ് ചിഹ്നം"</string>
+    <string name="spoken_emoji_1F530" msgid="3572898444281774023">"തുടക്കക്കാർക്കുള്ള ജാപ്പനീസ്‌ ചിഹ്നം"</string>
     <string name="spoken_emoji_1F531" msgid="5225633376450025396">"ത്രിശൂലത്തിന്റെ ചിഹ്നം"</string>
     <string name="spoken_emoji_1F532" msgid="9169568490485180779">"കറുത്ത ചതുര ബട്ടൺ"</string>
     <string name="spoken_emoji_1F533" msgid="6554193837201918598">"വെള്ള ചതുര ബട്ടൺ"</string>
diff --git a/java/res/values-si-rLK/strings-emoji-descriptions.xml b/java/res/values-si-rLK/strings-emoji-descriptions.xml
index 14187a6..ae341dc 100644
--- a/java/res/values-si-rLK/strings-emoji-descriptions.xml
+++ b/java/res/values-si-rLK/strings-emoji-descriptions.xml
@@ -267,7 +267,7 @@
     <string name="spoken_emoji_1F36A" msgid="2726271795913042295">"කුකීය"</string>
     <string name="spoken_emoji_1F36B" msgid="6342163604299875931">"චොකලට් බාරය"</string>
     <string name="spoken_emoji_1F36C" msgid="2168934753998218790">"පැණිරස"</string>
-    <string name="spoken_emoji_1F36D" msgid="3671507903799975792">"ලොලිපොප්"</string>
+    <string name="spoken_emoji_1F36D" msgid="3671507903799975792">"Lollipop"</string>
     <string name="spoken_emoji_1F36E" msgid="4630541402785165902">"කස්ටට්"</string>
     <string name="spoken_emoji_1F36F" msgid="5577915387425169439">"මී පැණි මුට්ටිය"</string>
     <string name="spoken_emoji_1F370" msgid="7243244547866114951">"ෂොට් කේක්"</string>
diff --git a/java/res/values-v19/spinner-style.xml b/java/res/values-v19/spinner-style.xml
index 7de59ed..a699905 100644
--- a/java/res/values-v19/spinner-style.xml
+++ b/java/res/values-v19/spinner-style.xml
@@ -21,7 +21,7 @@
 <resources xmlns:android="http://schemas.android.com/apk/res/android">
     <!-- Until KitKat (API 19), {@link android.widget.Spinner} of dialog mode in a Dialog can't
          handle orientation change correctly. Using dropdown mode avoids the issue.
-         This file overrides values/spinner-style.xml on KitKat and newer device. -->
+         This file overrides values/spinner-style.xml on KitKat and up. -->
     <style name="additionalSubtypeSpinnerStyle">
         <item name="android:spinnerMode">dialog</item>
     </style>
diff --git a/java/res/values/spinner-style.xml b/java/res/values/spinner-style.xml
index 4043ad4..c0f32ab 100644
--- a/java/res/values/spinner-style.xml
+++ b/java/res/values/spinner-style.xml
@@ -21,7 +21,7 @@
 <resources xmlns:android="http://schemas.android.com/apk/res/android">
     <!-- Until KitKat (API 19), {@link android.widget.Spinner} of dialog mode in a Dialog can't
          handle orientation change correctly. Using dropdown mode avoids the issue.
-         This file is overridden by values-v19/spinner-style.xml on KitKat and newer device. -->
+         This file is overridden by values-v19/spinner-style.xml on KitKat and up. -->
     <style name="additionalSubtypeSpinnerStyle">
         <item name="android:spinnerMode">dropdown</item>
     </style>
diff --git a/java/src/com/android/inputmethod/keyboard/KeyboardLayoutSet.java b/java/src/com/android/inputmethod/keyboard/KeyboardLayoutSet.java
index 5d9b8a7..d71dc59 100644
--- a/java/src/com/android/inputmethod/keyboard/KeyboardLayoutSet.java
+++ b/java/src/com/android/inputmethod/keyboard/KeyboardLayoutSet.java
@@ -34,7 +34,7 @@
 import com.android.inputmethod.compat.InputMethodSubtypeCompatUtils;
 import com.android.inputmethod.keyboard.internal.KeyboardBuilder;
 import com.android.inputmethod.keyboard.internal.KeyboardParams;
-import com.android.inputmethod.keyboard.internal.KeysCache;
+import com.android.inputmethod.keyboard.internal.UniqueKeysCache;
 import com.android.inputmethod.latin.InputAttributes;
 import com.android.inputmethod.latin.R;
 import com.android.inputmethod.latin.RichInputMethodSubtype;
@@ -86,7 +86,7 @@
     private static final HashMap<KeyboardId, SoftReference<Keyboard>> sKeyboardCache =
             new HashMap<>();
     @Nonnull
-    private static final KeysCache sKeysCache = new KeysCache();
+    private static final UniqueKeysCache sUniqueKeysCache = UniqueKeysCache.newInstance();
     private final static HashMap<InputMethodSubtype, Integer> sScriptIdsForSubtypes =
             new HashMap<>();
 
@@ -144,7 +144,7 @@
 
     private static void clearKeyboardCache() {
         sKeyboardCache.clear();
-        sKeysCache.clear();
+        sUniqueKeysCache.clear();
     }
 
     public static int getScriptId(final Resources resources,
@@ -219,10 +219,8 @@
         }
 
         final KeyboardBuilder<KeyboardParams> builder =
-                new KeyboardBuilder<>(mContext, new KeyboardParams());
-        if (id.isAlphabetKeyboard()) {
-            builder.setAutoGenerate(sKeysCache);
-        }
+                new KeyboardBuilder<>(mContext, new KeyboardParams(sUniqueKeysCache));
+        sUniqueKeysCache.setEnabled(id.isAlphabetKeyboard());
         builder.setAllowRedundantMoreKes(elementParams.mAllowRedundantMoreKeys);
         final int keyboardXmlId = elementParams.mKeyboardXmlId;
         builder.load(keyboardXmlId, id);
diff --git a/java/src/com/android/inputmethod/keyboard/internal/KeyboardBuilder.java b/java/src/com/android/inputmethod/keyboard/internal/KeyboardBuilder.java
index 5743ef9..2b07e1d 100644
--- a/java/src/com/android/inputmethod/keyboard/internal/KeyboardBuilder.java
+++ b/java/src/com/android/inputmethod/keyboard/internal/KeyboardBuilder.java
@@ -161,10 +161,6 @@
         params.GRID_HEIGHT = res.getInteger(R.integer.config_keyboard_grid_height);
     }
 
-    public void setAutoGenerate(final KeysCache keysCache) {
-        mParams.mKeysCache = keysCache;
-    }
-
     public void setAllowRedundantMoreKes(final boolean enabled) {
         mParams.mAllowRedundantMoreKeys = enabled;
     }
diff --git a/java/src/com/android/inputmethod/keyboard/internal/KeyboardParams.java b/java/src/com/android/inputmethod/keyboard/internal/KeyboardParams.java
index 4326876..738d6a4 100644
--- a/java/src/com/android/inputmethod/keyboard/internal/KeyboardParams.java
+++ b/java/src/com/android/inputmethod/keyboard/internal/KeyboardParams.java
@@ -77,9 +77,8 @@
     @Nonnull
     public final KeyStylesSet mKeyStyles = new KeyStylesSet(mTextsSet);
 
-    // TODO: Make this @Nonnull
-    @Nullable
-    public KeysCache mKeysCache;
+    @Nonnull
+    private final UniqueKeysCache mUniqueKeysCache;
     public boolean mAllowRedundantMoreKeys;
 
     public int mMostCommonKeyHeight = 0;
@@ -103,6 +102,14 @@
         }
     };
 
+    public KeyboardParams() {
+        this(UniqueKeysCache.NO_CACHE);
+    }
+
+    public KeyboardParams(@Nonnull final UniqueKeysCache keysCache) {
+        mUniqueKeysCache = keysCache;
+    }
+
     protected void clearKeys() {
         mSortedKeys.clear();
         mShiftKeys.clear();
@@ -110,9 +117,7 @@
     }
 
     public void onAddKey(@Nonnull final Key newKey) {
-        // To avoid possible null pointer access.
-        final KeysCache keysCache = mKeysCache;
-        final Key key = (keysCache != null) ? keysCache.get(newKey) : newKey;
+        final Key key = mUniqueKeysCache.getUniqueKey(newKey);
         final boolean isSpacer = key.isSpacer();
         if (isSpacer && key.getWidth() == 0) {
             // Ignore zero width {@link Spacer}.
@@ -140,16 +145,11 @@
         for (final Key key : mSortedKeys) {
             lettersOnBaseLayout.addLetter(key);
         }
-        // To avoid possible null pointer access.
-        final KeysCache keysCache = mKeysCache;
         final ArrayList<Key> allKeys = new ArrayList<>(mSortedKeys);
         mSortedKeys.clear();
         for (final Key key : allKeys) {
             final Key filteredKey = Key.removeRedundantMoreKeys(key, lettersOnBaseLayout);
-            if (keysCache != null) {
-                keysCache.replace(key, filteredKey);
-            }
-            mSortedKeys.add(filteredKey);
+            mSortedKeys.add(mUniqueKeysCache.getUniqueKey(filteredKey));
         }
     }
 
diff --git a/java/src/com/android/inputmethod/keyboard/internal/KeysCache.java b/java/src/com/android/inputmethod/keyboard/internal/KeysCache.java
deleted file mode 100644
index 6ad450c..0000000
--- a/java/src/com/android/inputmethod/keyboard/internal/KeysCache.java
+++ /dev/null
@@ -1,50 +0,0 @@
-/*
- * Copyright (C) 2012 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.inputmethod.keyboard.internal;
-
-import com.android.inputmethod.keyboard.Key;
-
-import java.util.HashMap;
-
-// TODO: Rename more appropriate name.
-public final class KeysCache {
-    private final HashMap<Key, Key> mMap = new HashMap<>();
-
-    public void clear() {
-        mMap.clear();
-    }
-
-    // TODO: Rename more descriptive name.
-    public Key get(final Key key) {
-        final Key existingKey = mMap.get(key);
-        if (existingKey != null) {
-            // Reuse the existing element that equals to "key" without adding "key" to the map.
-            return existingKey;
-        }
-        mMap.put(key, key);
-        return key;
-    }
-
-    // TODO: Rename more descriptive name.
-    public Key replace(final Key oldKey, final Key newKey) {
-        if (oldKey.equals(newKey)) {
-            return oldKey;
-        }
-        mMap.remove(oldKey);
-        return get(newKey);
-    }
-}
diff --git a/java/src/com/android/inputmethod/keyboard/internal/UniqueKeysCache.java b/java/src/com/android/inputmethod/keyboard/internal/UniqueKeysCache.java
new file mode 100644
index 0000000..5b329dc
--- /dev/null
+++ b/java/src/com/android/inputmethod/keyboard/internal/UniqueKeysCache.java
@@ -0,0 +1,81 @@
+/*
+ * Copyright (C) 2014 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.inputmethod.keyboard.internal;
+
+import com.android.inputmethod.keyboard.Key;
+
+import java.util.HashMap;
+
+import javax.annotation.Nonnull;
+
+public abstract class UniqueKeysCache {
+    public abstract void setEnabled(boolean enabled);
+    public abstract void clear();
+    public abstract @Nonnull Key getUniqueKey(@Nonnull Key key);
+
+    @Nonnull
+    public static final UniqueKeysCache NO_CACHE = new UniqueKeysCache() {
+        @Override
+        public void setEnabled(boolean enabled) {}
+
+        @Override
+        public void clear() {}
+
+        @Override
+        public Key getUniqueKey(Key key) { return key; }
+    };
+
+    @Nonnull
+    public static UniqueKeysCache newInstance() {
+        return new UniqueKeysCacheImpl();
+    }
+
+    private static final class UniqueKeysCacheImpl extends UniqueKeysCache {
+        private final HashMap<Key, Key> mCache;
+
+        private boolean mEnabled;
+
+        UniqueKeysCacheImpl() {
+            mCache = new HashMap<>();
+        }
+
+        @Override
+        public void setEnabled(final boolean enabled) {
+            mEnabled = enabled;
+        }
+
+        @Override
+        public void clear() {
+            mCache.clear();
+        }
+
+        @Override
+        public Key getUniqueKey(final Key key) {
+            if (!mEnabled) {
+                return key;
+            }
+            final Key existingKey = mCache.get(key);
+            if (existingKey != null) {
+                // Reuse the existing object that equals to "key" without adding "key" to
+                // the cache.
+                return existingKey;
+            }
+            mCache.put(key, key);
+            return key;
+        }
+    }
+}
diff --git a/java/src/com/android/inputmethod/latin/ExpandableBinaryDictionary.java b/java/src/com/android/inputmethod/latin/ExpandableBinaryDictionary.java
index d9d22e0..1c54a20 100644
--- a/java/src/com/android/inputmethod/latin/ExpandableBinaryDictionary.java
+++ b/java/src/com/android/inputmethod/latin/ExpandableBinaryDictionary.java
@@ -77,6 +77,9 @@
 
     private static final int DICTIONARY_FORMAT_VERSION = FormatSpec.VERSION4;
 
+    private static final WordProperty[] DEFAULT_WORD_PROPERTIES_FOR_SYNC =
+            new WordProperty[0] /* default */;
+
     /** The application context. */
     protected final Context mContext;
 
@@ -802,4 +805,38 @@
             }
         });
     }
+
+    /**
+     * Returns dictionary content required for syncing.
+     */
+    public WordProperty[] getWordPropertiesForSyncing() {
+        reloadDictionaryIfRequired();
+        final AsyncResultHolder<WordProperty[]> result = new AsyncResultHolder<>();
+        asyncExecuteTaskWithLock(mLock.readLock(), "sync-read", new Runnable() {
+            @Override
+            public void run() {
+                final ArrayList<WordProperty> wordPropertyList = new ArrayList<>();
+                final BinaryDictionary binaryDictionary = getBinaryDictionary();
+                if (binaryDictionary == null) {
+                    return;
+                }
+                int token = 0;
+                do {
+                    // TODO: We need a new API that returns *new* un-synced data.
+                    final BinaryDictionary.GetNextWordPropertyResult nextWordPropertyResult =
+                            binaryDictionary.getNextWordProperty(token);
+                    final WordProperty wordProperty = nextWordPropertyResult.mWordProperty;
+                    if (wordProperty == null) {
+                        break;
+                    }
+                    wordPropertyList.add(wordProperty);
+                    token = nextWordPropertyResult.mNextToken;
+                } while (token != 0);
+                result.set(wordPropertyList.toArray(new WordProperty[wordPropertyList.size()]));
+            }
+        });
+        // TODO: Figure out the best timeout duration for this API.
+        return result.get(DEFAULT_WORD_PROPERTIES_FOR_SYNC,
+                TIMEOUT_FOR_READ_OPS_IN_MILLISECONDS);
+    }
 }
diff --git a/java/src/com/android/inputmethod/latin/LatinIME.java b/java/src/com/android/inputmethod/latin/LatinIME.java
index 66746cb..27115e2 100644
--- a/java/src/com/android/inputmethod/latin/LatinIME.java
+++ b/java/src/com/android/inputmethod/latin/LatinIME.java
@@ -590,7 +590,6 @@
         // TODO: Resolve mutual dependencies of {@link #loadSettings()} and
         // {@link #resetDictionaryFacilitatorIfNecessary()}.
         loadSettings();
-        mSubtypeSwitcher.onSubtypeChanged(mRichImm.getCurrentRawSubtype());
         resetDictionaryFacilitatorIfNecessary();
 
         // Register to receive ringer mode change and network state change.
@@ -731,6 +730,7 @@
         unregisterReceiver(mDictionaryPackInstallReceiver);
         unregisterReceiver(mDictionaryDumpBroadcastReceiver);
         mStatsUtilsManager.onDestroy();
+        DictionaryDecayBroadcastReciever.cancelIntervalAlarmForDictionaryDecaying(this);
         super.onDestroy();
     }
 
@@ -865,7 +865,8 @@
     public void onCurrentInputMethodSubtypeChanged(final InputMethodSubtype subtype) {
         // Note that the calling sequence of onCreate() and onCurrentInputMethodSubtypeChanged()
         // is not guaranteed. It may even be called at the same time on a different thread.
-        mSubtypeSwitcher.onSubtypeChanged(subtype);
+        mRichImm.onSubtypeChanged(subtype);
+        mSubtypeSwitcher.onSubtypeChanged(mRichImm.getCurrentSubtype());
         mInputLogic.onSubtypeChanged(SubtypeLocaleUtils.getCombiningRulesExtraValue(subtype),
                 mSettings.getCurrent());
         loadKeyboard();
@@ -881,8 +882,8 @@
         // Switch to the null consumer to handle cases leading to early exit below, for which we
         // also wouldn't be consuming gesture data.
         mGestureConsumer = GestureConsumer.NULL_GESTURE_CONSUMER;
-        mRichImm.clearSubtypeCaches();
-        mSubtypeSwitcher.onSubtypeChanged(mRichImm.getCurrentRawSubtype());
+        mRichImm.refreshSubtypeCaches();
+        mSubtypeSwitcher.onSubtypeChanged(mRichImm.getCurrentSubtype());
         final KeyboardSwitcher switcher = mKeyboardSwitcher;
         switcher.updateKeyboardTheme();
         final MainKeyboardView mainKeyboardView = switcher.getMainKeyboardView();
@@ -1448,7 +1449,7 @@
     // completely replace #onCodeInput.
     public void onEvent(@Nonnull final Event event) {
         if (Constants.CODE_SHORTCUT == event.mKeyCode) {
-            mRichImm.switchToShortcutIME(this);
+            mRichImm.switchToShortcutIme(this);
         }
         final InputTransaction completeInputTransaction =
                 mInputLogic.onCodeInput(mSettings.getCurrent(), event,
diff --git a/java/src/com/android/inputmethod/latin/RichInputMethodManager.java b/java/src/com/android/inputmethod/latin/RichInputMethodManager.java
index 686c3a4..4621217 100644
--- a/java/src/com/android/inputmethod/latin/RichInputMethodManager.java
+++ b/java/src/com/android/inputmethod/latin/RichInputMethodManager.java
@@ -111,7 +111,11 @@
         // Initialize additional subtypes.
         SubtypeLocaleUtils.init(context);
         final InputMethodSubtype[] additionalSubtypes = getAdditionalSubtypes();
-        setAdditionalInputMethodSubtypes(additionalSubtypes);
+        mImmWrapper.mImm.setAdditionalInputMethodSubtypes(
+                getInputMethodIdOfThisIme(), additionalSubtypes);
+
+        // Initialize the current input method subtype and the shortcut IME.
+        refreshSubtypeCaches();
 
         final ConnectivityManager connectivityManager =
                 (ConnectivityManager) context.getSystemService(Context.CONNECTIVITY_SERVICE);
@@ -324,23 +328,22 @@
         return INDEX_NOT_FOUND;
     }
 
-    @Nonnull
-    public RichInputMethodSubtype onSubtypeChanged(@Nonnull final InputMethodSubtype newSubtype) {
-        final RichInputMethodSubtype richSubtype = createCurrentRichInputMethodSubtype(newSubtype);
+    public void onSubtypeChanged(@Nonnull final InputMethodSubtype newSubtype) {
+        updateCurrentSubtype(newSubtype);
+        updateShortcutIme();
         if (DEBUG) {
-            Log.w(TAG, "onSubtypeChanged: " + richSubtype.getNameForLogging());
+            Log.w(TAG, "onSubtypeChanged: " + mCurrentRichInputMethodSubtype.getNameForLogging());
         }
-        mCurrentRichInputMethodSubtype = richSubtype;
-        return richSubtype;
     }
 
     private static RichInputMethodSubtype sForcedSubtypeForTesting = null;
 
     @UsedForTesting
-    static void forceSubtype(final InputMethodSubtype subtype) {
+    static void forceSubtype(@Nonnull final InputMethodSubtype subtype) {
         sForcedSubtypeForTesting = new RichInputMethodSubtype(subtype);
     }
 
+    @Nonnull
     public Locale[] getCurrentSubtypeLocales() {
         if (null != sForcedSubtypeForTesting) {
             return sForcedSubtypeForTesting.getLocales();
@@ -348,6 +351,7 @@
         return getCurrentSubtype().getLocales();
     }
 
+    @Nonnull
     public RichInputMethodSubtype getCurrentSubtype() {
         if (null != sForcedSubtypeForTesting) {
             return sForcedSubtypeForTesting;
@@ -360,18 +364,6 @@
         return SubtypeLocaleUtils.getCombiningRulesExtraValue(getCurrentSubtype().getRawSubtype());
     }
 
-    @Nonnull
-    public InputMethodSubtype getCurrentRawSubtype() {
-        return mImmWrapper.mImm.getCurrentInputMethodSubtype();
-    }
-
-    @Nonnull
-    public RichInputMethodSubtype createCurrentRichInputMethodSubtype(
-            @Nonnull final InputMethodSubtype rawSubtype) {
-        return AdditionalFeaturesSettingUtils.createRichInputMethodSubtype(this, rawSubtype,
-                mContext);
-    }
-
     public boolean hasMultipleEnabledIMEsOrSubtypes(final boolean shouldIncludeAuxiliarySubtypes) {
         final List<InputMethodInfo> enabledImis = mImmWrapper.mImm.getEnabledInputMethodList();
         return hasMultipleEnabledSubtypes(shouldIncludeAuxiliarySubtypes, enabledImis);
@@ -457,7 +449,7 @@
                 getInputMethodIdOfThisIme(), subtypes);
         // Clear the cache so that we go read the {@link InputMethodInfo} of this IME and list of
         // subtypes again next time.
-        clearSubtypeCaches();
+        refreshSubtypeCaches();
     }
 
     private List<InputMethodSubtype> getEnabledInputMethodSubtypeList(final InputMethodInfo imi,
@@ -474,10 +466,12 @@
         return result;
     }
 
-    public void clearSubtypeCaches() {
+    public void refreshSubtypeCaches() {
         mSubtypeListCacheWithImplicitlySelectedSubtypes.clear();
         mSubtypeListCacheWithoutImplicitlySelectedSubtypes.clear();
         mInputMethodInfoCache.clear();
+        updateCurrentSubtype(mImmWrapper.mImm.getCurrentInputMethodSubtype());
+        updateShortcutIme();
     }
 
     public boolean shouldOfferSwitchingToNextInputMethod(final IBinder binder,
@@ -516,8 +510,13 @@
         return true;
     }
 
-    // TODO: Make this private
-    void updateShortcutIME() {
+    private void updateCurrentSubtype(@Nonnull final InputMethodSubtype subtype) {
+        final RichInputMethodSubtype richSubtype = AdditionalFeaturesSettingUtils
+                .createRichInputMethodSubtype(this, subtype, mContext);
+        mCurrentRichInputMethodSubtype = richSubtype;
+    }
+
+    private void updateShortcutIme() {
         if (DEBUG) {
             Log.d(TAG, "Update shortcut IME from : "
                     + (mShortcutInputMethodInfo == null
@@ -549,7 +548,7 @@
         }
     }
 
-    public void switchToShortcutIME(final InputMethodService context) {
+    public void switchToShortcutIme(final InputMethodService context) {
         if (mShortcutInputMethodInfo == null) {
             return;
         }
@@ -575,19 +574,16 @@
     }
 
     public boolean isShortcutImeEnabled() {
-        updateShortcutIME();
         if (mShortcutInputMethodInfo == null) {
             return false;
         }
         if (mShortcutSubtype == null) {
             return true;
         }
-        return checkIfSubtypeBelongsToImeAndEnabled(
-                mShortcutInputMethodInfo, mShortcutSubtype);
+        return checkIfSubtypeBelongsToImeAndEnabled(mShortcutInputMethodInfo, mShortcutSubtype);
     }
 
     public boolean isShortcutImeReady() {
-        updateShortcutIME();
         if (mShortcutInputMethodInfo == null) {
             return false;
         }
diff --git a/java/src/com/android/inputmethod/latin/SubtypeSwitcher.java b/java/src/com/android/inputmethod/latin/SubtypeSwitcher.java
index 23e348b..92ba6c2 100644
--- a/java/src/com/android/inputmethod/latin/SubtypeSwitcher.java
+++ b/java/src/com/android/inputmethod/latin/SubtypeSwitcher.java
@@ -57,7 +57,7 @@
         mResources = context.getResources();
         mRichImm = RichInputMethodManager.getInstance();
 
-        onSubtypeChanged(mRichImm.getCurrentRawSubtype());
+        onSubtypeChanged(mRichImm.getCurrentSubtype());
         updateParametersOnStartInputView();
     }
 
@@ -69,17 +69,14 @@
         final List<InputMethodSubtype> enabledSubtypesOfThisIme =
                 mRichImm.getMyEnabledInputMethodSubtypeList(true);
         mLanguageOnSpacebarHelper.onUpdateEnabledSubtypes(enabledSubtypesOfThisIme);
-        mRichImm.updateShortcutIME();
     }
 
     // Update the current subtype. LatinIME.onCurrentInputMethodSubtypeChanged calls this function.
-    public void onSubtypeChanged(@Nonnull final InputMethodSubtype newSubtype) {
-        final RichInputMethodSubtype richSubtype = mRichImm.onSubtypeChanged(newSubtype);
+    public void onSubtypeChanged(@Nonnull final RichInputMethodSubtype richSubtype) {
         final boolean implicitlyEnabledSubtype = mRichImm
-                .checkIfSubtypeBelongsToThisImeAndImplicitlyEnabled(newSubtype);
+                .checkIfSubtypeBelongsToThisImeAndImplicitlyEnabled(richSubtype.getRawSubtype());
         mLanguageOnSpacebarHelper.onSubtypeChanged(
                 richSubtype, implicitlyEnabledSubtype, mResources.getConfiguration().locale);
-        mRichImm.updateShortcutIME();
     }
 
     public int getLanguageOnSpacebarFormatType(final RichInputMethodSubtype subtype) {
diff --git a/java/src/com/android/inputmethod/latin/personalization/DictionaryDecayBroadcastReciever.java b/java/src/com/android/inputmethod/latin/personalization/DictionaryDecayBroadcastReciever.java
index 221bb9a..e974f33 100644
--- a/java/src/com/android/inputmethod/latin/personalization/DictionaryDecayBroadcastReciever.java
+++ b/java/src/com/android/inputmethod/latin/personalization/DictionaryDecayBroadcastReciever.java
@@ -43,17 +43,40 @@
     /**
      * Interval to update for decaying dictionaries.
      */
-    /* package */ static final long DICTIONARY_DECAY_INTERVAL = TimeUnit.MINUTES.toMillis(60);
+    static final long DICTIONARY_DECAY_INTERVAL_IN_MILLIS = TimeUnit.MINUTES.toMillis(60);
 
-    public static void setUpIntervalAlarmForDictionaryDecaying(Context context) {
-        AlarmManager alarmManager = (AlarmManager)context.getSystemService(Context.ALARM_SERVICE);
+    private static PendingIntent getPendingIntentForDictionaryDecay(final Context context) {
         final Intent updateIntent = new Intent(DICTIONARY_DECAY_INTENT_ACTION);
         updateIntent.setClass(context, DictionaryDecayBroadcastReciever.class);
-        final long alarmTime =  System.currentTimeMillis() + DICTIONARY_DECAY_INTERVAL;
-        final PendingIntent pendingIntent = PendingIntent.getBroadcast(context, 0 /* requestCode */,
+        return PendingIntent.getBroadcast(context, 0 /* requestCode */,
                 updateIntent, PendingIntent.FLAG_CANCEL_CURRENT);
-        if (null != alarmManager) alarmManager.setInexactRepeating(AlarmManager.RTC,
-                alarmTime, DICTIONARY_DECAY_INTERVAL, pendingIntent);
+    }
+
+    /**
+     * Set up interval alarm for dynamic dictionaries.
+     */
+    public static void setUpIntervalAlarmForDictionaryDecaying(final Context context) {
+        final AlarmManager alarmManager =
+                (AlarmManager)context.getSystemService(Context.ALARM_SERVICE);
+        if (null == alarmManager) {
+            return;
+        }
+        final long alarmTriggerTimeInMillis =
+                System.currentTimeMillis() + DICTIONARY_DECAY_INTERVAL_IN_MILLIS;
+        alarmManager.setInexactRepeating(AlarmManager.RTC, alarmTriggerTimeInMillis,
+                DICTIONARY_DECAY_INTERVAL_IN_MILLIS, getPendingIntentForDictionaryDecay(context));
+    }
+
+    /**
+     * Cancel interval alarm that has been set up.
+     */
+    public static void cancelIntervalAlarmForDictionaryDecaying(final Context context) {
+        final AlarmManager alarmManager =
+                (AlarmManager)context.getSystemService(Context.ALARM_SERVICE);
+        if (null == alarmManager) {
+            return;
+        }
+        alarmManager.cancel(getPendingIntentForDictionaryDecay(context));
     }
 
     @Override
diff --git a/java/src/com/android/inputmethod/latin/personalization/PersonalizationHelper.java b/java/src/com/android/inputmethod/latin/personalization/PersonalizationHelper.java
index 8c5eb0a..b595f39 100644
--- a/java/src/com/android/inputmethod/latin/personalization/PersonalizationHelper.java
+++ b/java/src/com/android/inputmethod/latin/personalization/PersonalizationHelper.java
@@ -58,8 +58,7 @@
                 final UserHistoryDictionary dict = ref == null ? null : ref.get();
                 if (dict != null) {
                     if (DEBUG) {
-                        Log.d(TAG, "Use cached UserHistoryDictionary for " + locale +
-                                " & account" + accountName);
+                        Log.d(TAG, "Use cached UserHistoryDictionary with lookup: " + lookupStr);
                     }
                     dict.reloadDictionaryIfRequired();
                     return dict;
@@ -74,7 +73,7 @@
     private static int sCurrentTimestampForTesting = 0;
     public static void currentTimeChangedForTesting(final int currentTimestamp) {
         if (TimeUnit.MILLISECONDS.toSeconds(
-                DictionaryDecayBroadcastReciever.DICTIONARY_DECAY_INTERVAL)
+                DictionaryDecayBroadcastReciever.DICTIONARY_DECAY_INTERVAL_IN_MILLIS)
                         < currentTimestamp - sCurrentTimestampForTesting) {
             runGCOnAllOpenedUserHistoryDictionaries();
             runGCOnAllOpenedPersonalizationDictionaries();
diff --git a/java/src/com/android/inputmethod/latin/settings/PreferencesSettingsFragment.java b/java/src/com/android/inputmethod/latin/settings/PreferencesSettingsFragment.java
index c0ceb88..975396d 100644
--- a/java/src/com/android/inputmethod/latin/settings/PreferencesSettingsFragment.java
+++ b/java/src/com/android/inputmethod/latin/settings/PreferencesSettingsFragment.java
@@ -71,6 +71,7 @@
         super.onResume();
         final Preference voiceInputKeyOption = findPreference(Settings.PREF_VOICE_INPUT_KEY);
         if (voiceInputKeyOption != null) {
+            RichInputMethodManager.getInstance().refreshSubtypeCaches();
             final boolean isShortcutImeEnabled = RichInputMethodManager.getInstance()
                     .isShortcutImeEnabled();
             voiceInputKeyOption.setEnabled(isShortcutImeEnabled);
diff --git a/native/jni/src/defines.h b/native/jni/src/defines.h
index 0e67b4d..10b930e 100644
--- a/native/jni/src/defines.h
+++ b/native/jni/src/defines.h
@@ -275,7 +275,7 @@
 #define MAX_POINTER_COUNT_G 2
 
 // (MAX_PREV_WORD_COUNT_FOR_N_GRAM + 1)-gram is supported.
-#define MAX_PREV_WORD_COUNT_FOR_N_GRAM 2
+#define MAX_PREV_WORD_COUNT_FOR_N_GRAM 3
 
 #define DISALLOW_DEFAULT_CONSTRUCTOR(TypeName) \
   TypeName() = delete
diff --git a/native/jni/src/suggest/policyimpl/dictionary/header/header_policy.cpp b/native/jni/src/suggest/policyimpl/dictionary/header/header_policy.cpp
index a2a0f11..c93f310 100644
--- a/native/jni/src/suggest/policyimpl/dictionary/header/header_policy.cpp
+++ b/native/jni/src/suggest/policyimpl/dictionary/header/header_policy.cpp
@@ -31,10 +31,11 @@
 const char *const HeaderPolicy::DATE_KEY = "date";
 const char *const HeaderPolicy::LAST_DECAYED_TIME_KEY = "LAST_DECAYED_TIME";
 const char *const HeaderPolicy::NGRAM_COUNT_KEYS[] =
-        {"UNIGRAM_COUNT", "BIGRAM_COUNT", "TRIGRAM_COUNT"};
+        {"UNIGRAM_COUNT", "BIGRAM_COUNT", "TRIGRAM_COUNT", "QUADGRAM_COUNT"};
 const char *const HeaderPolicy::MAX_NGRAM_COUNT_KEYS[] =
-        {"MAX_UNIGRAM_ENTRY_COUNT", "MAX_BIGRAM_ENTRY_COUNT", "MAX_TRIGRAM_ENTRY_COUNT"};
-const int HeaderPolicy::DEFAULT_MAX_NGRAM_COUNTS[] = {10000, 30000, 30000};
+        {"MAX_UNIGRAM_ENTRY_COUNT", "MAX_BIGRAM_ENTRY_COUNT", "MAX_TRIGRAM_ENTRY_COUNT",
+                "MAX_QUADGRAM_ENTRY_COUNT"};
+const int HeaderPolicy::DEFAULT_MAX_NGRAM_COUNTS[] = {10000, 30000, 30000, 30000};
 const char *const HeaderPolicy::EXTENDED_REGION_SIZE_KEY = "EXTENDED_REGION_SIZE";
 // Historical info is information that is needed to support decaying such as timestamp, level and
 // count.
diff --git a/native/jni/src/suggest/policyimpl/dictionary/structure/v4/content/dynamic_language_model_probability_utils.cpp b/native/jni/src/suggest/policyimpl/dictionary/structure/v4/content/dynamic_language_model_probability_utils.cpp
index 29bc7f7..025ee99 100644
--- a/native/jni/src/suggest/policyimpl/dictionary/structure/v4/content/dynamic_language_model_probability_utils.cpp
+++ b/native/jni/src/suggest/policyimpl/dictionary/structure/v4/content/dynamic_language_model_probability_utils.cpp
@@ -19,12 +19,13 @@
 namespace latinime {
 
 // Used to provide stable probabilities even if the user's input count is small.
-const int DynamicLanguageModelProbabilityUtils::ASSUMED_MIN_COUNTS[] = {8192, 2, 2};
+const int DynamicLanguageModelProbabilityUtils::ASSUMED_MIN_COUNTS[] = {8192, 2, 2, 1};
 
 // Encoded backoff weights.
-// Note that we give positive value for trigrams that means the weight is more than 1.
+// Note that we give positive values for trigrams and quadgrams that means the weight is more than
+// 1.
 // TODO: Apply backoff for main dictionaries and quit giving a positive backoff weight.
-const int DynamicLanguageModelProbabilityUtils::ENCODED_BACKOFF_WEIGHTS[] = {-32, 0, 8};
+const int DynamicLanguageModelProbabilityUtils::ENCODED_BACKOFF_WEIGHTS[] = {-32, -4, 2, 8};
 
 // This value is used to remove too old entries from the dictionary.
 const int DynamicLanguageModelProbabilityUtils::DURATION_TO_DISCARD_ENTRY_IN_SECONDS =
diff --git a/native/jni/src/suggest/policyimpl/dictionary/structure/v4/content/dynamic_language_model_probability_utils.h b/native/jni/src/suggest/policyimpl/dictionary/structure/v4/content/dynamic_language_model_probability_utils.h
index b38047f..644ae2c 100644
--- a/native/jni/src/suggest/policyimpl/dictionary/structure/v4/content/dynamic_language_model_probability_utils.h
+++ b/native/jni/src/suggest/policyimpl/dictionary/structure/v4/content/dynamic_language_model_probability_utils.h
@@ -66,7 +66,7 @@
 private:
     DISALLOW_IMPLICIT_CONSTRUCTORS(DynamicLanguageModelProbabilityUtils);
 
-    static_assert(MAX_PREV_WORD_COUNT_FOR_N_GRAM <= 2, "Max supported Ngram is Trigram.");
+    static_assert(MAX_PREV_WORD_COUNT_FOR_N_GRAM <= 3, "Max supported Ngram is Quadgram.");
 
     static const int ASSUMED_MIN_COUNTS[];
     static const int ENCODED_BACKOFF_WEIGHTS[];
diff --git a/native/jni/src/suggest/policyimpl/dictionary/utils/entry_counters.h b/native/jni/src/suggest/policyimpl/dictionary/utils/entry_counters.h
index 7269913..5e44302 100644
--- a/native/jni/src/suggest/policyimpl/dictionary/utils/entry_counters.h
+++ b/native/jni/src/suggest/policyimpl/dictionary/utils/entry_counters.h
@@ -27,7 +27,7 @@
 // Copyable but immutable
 class EntryCounts final {
  public:
-    EntryCounts() : mEntryCounts({{0, 0, 0}}) {}
+    EntryCounts() : mEntryCounts({{0, 0, 0, 0}}) {}
 
     explicit EntryCounts(const std::array<int, MAX_PREV_WORD_COUNT_FOR_N_GRAM + 1> &counters)
             : mEntryCounts(counters) {}
diff --git a/native/jni/src/utils/ngram_utils.h b/native/jni/src/utils/ngram_utils.h
index 6227812..fa85ba3 100644
--- a/native/jni/src/utils/ngram_utils.h
+++ b/native/jni/src/utils/ngram_utils.h
@@ -25,6 +25,7 @@
     Unigram = 0,
     Bigram = 1,
     Trigram = 2,
+    Quadgram = 3,
     NotANgramType = -1,
 };
 
diff --git a/tests/src/com/android/inputmethod/keyboard/layout/tests/LayoutTestsBase.java b/tests/src/com/android/inputmethod/keyboard/layout/tests/LayoutTestsBase.java
index a8c4ac8..27519ee 100644
--- a/tests/src/com/android/inputmethod/keyboard/layout/tests/LayoutTestsBase.java
+++ b/tests/src/com/android/inputmethod/keyboard/layout/tests/LayoutTestsBase.java
@@ -120,31 +120,13 @@
 
     // TODO: Add phone, phone symbols, number, number password layout tests.
 
-    public final void testAlphabet() {
+    public final void testLayouts() {
         doKeyboardTests(KeyboardId.ELEMENT_ALPHABET);
-    }
-
-    public final void testAlphabetAutomaticShifted() {
         doKeyboardTests(KeyboardId.ELEMENT_ALPHABET_AUTOMATIC_SHIFTED);
-    }
-
-    public final void testAlphabetManualShifted() {
         doKeyboardTests(KeyboardId.ELEMENT_ALPHABET_MANUAL_SHIFTED);
-    }
-
-    public final void testAlphabetShiftLocked() {
         doKeyboardTests(KeyboardId.ELEMENT_ALPHABET_SHIFT_LOCKED);
-    }
-
-    public final void testAlphabetShiftLockShifted() {
         doKeyboardTests(KeyboardId.ELEMENT_ALPHABET_SHIFT_LOCK_SHIFTED);
-    }
-
-    public final void testSymbols() {
         doKeyboardTests(KeyboardId.ELEMENT_SYMBOLS);
-    }
-
-    public final void testSymbolsShifted() {
         doKeyboardTests(KeyboardId.ELEMENT_SYMBOLS_SHIFTED);
     }
 
diff --git a/tests/src/com/android/inputmethod/latin/personalization/UserHistoryDictionaryTests.java b/tests/src/com/android/inputmethod/latin/personalization/UserHistoryDictionaryTests.java
index a84df28..d83c4a5 100644
--- a/tests/src/com/android/inputmethod/latin/personalization/UserHistoryDictionaryTests.java
+++ b/tests/src/com/android/inputmethod/latin/personalization/UserHistoryDictionaryTests.java
@@ -25,15 +25,11 @@
 import com.android.inputmethod.latin.ExpandableBinaryDictionary;
 import com.android.inputmethod.latin.NgramContext;
 import com.android.inputmethod.latin.NgramContext.WordInfo;
-import com.android.inputmethod.latin.common.FileUtils;
 import com.android.inputmethod.latin.settings.LocalSettingsConstants;
 import com.android.inputmethod.latin.utils.BinaryDictionaryUtils;
 import com.android.inputmethod.latin.utils.DistracterFilter;
 
 import java.io.File;
-import java.io.FilenameFilter;
-import java.util.ArrayList;
-import java.util.HashSet;
 import java.util.List;
 import java.util.Locale;
 import java.util.Random;
@@ -48,34 +44,13 @@
 public class UserHistoryDictionaryTests extends AndroidTestCase {
     private static final String TAG = UserHistoryDictionaryTests.class.getSimpleName();
     private static final int WAIT_FOR_WRITING_FILE_IN_MILLISECONDS = 3000;
-    private static final String TEST_LOCALE_PREFIX = "test_";
     private static final String TEST_ACCOUNT = "account@example.com";
 
-    private static final String[] CHARACTERS = {
-        "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m",
-        "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"
-    };
-
     private int mCurrentTime = 0;
 
     private SharedPreferences mPrefs;
     private String mLastKnownAccount = null;
 
-    private void removeAllTestDictFiles() {
-        final Locale dummyLocale = new Locale(TEST_LOCALE_PREFIX);
-        final String dictName = UserHistoryDictionary.getUserHistoryDictName(
-                UserHistoryDictionary.NAME, dummyLocale, null /* dictFile */, getContext());
-        final File dictFile = ExpandableBinaryDictionary.getDictFile(
-                mContext, dictName, null /* dictFile */);
-        final FilenameFilter filenameFilter = new FilenameFilter() {
-            @Override
-            public boolean accept(final File dir, final String filename) {
-                return filename.startsWith(UserHistoryDictionary.NAME + "." + TEST_LOCALE_PREFIX);
-            }
-        };
-        FileUtils.deleteFilteredFiles(dictFile.getParentFile(), filenameFilter);
-    }
-
     private static void printAllFiles(final File dir) {
         Log.d(TAG, dir.getAbsolutePath());
         for (final File file : dir.listFiles()) {
@@ -83,7 +58,7 @@
         }
     }
 
-    private static void checkExistenceAndRemoveDictFile(final UserHistoryDictionary dict,
+    private static void assertDictionaryExists(final UserHistoryDictionary dict,
             final File dictFile) {
         Log.d(TAG, "waiting for writing ...");
         dict.waitAllTasksForTests();
@@ -97,12 +72,7 @@
                 Log.e(TAG, "Interrupted during waiting for writing the dict file.");
             }
         }
-        assertTrue("check exisiting of " + dictFile, dictFile.exists());
-        FileUtils.deleteRecursively(dictFile);
-    }
-
-    private static Locale getDummyLocale(final String name) {
-        return new Locale(TEST_LOCALE_PREFIX + name + System.currentTimeMillis());
+        assertTrue("Following dictionary file doesn't exist: " + dictFile, dictFile.exists());
     }
 
     @Override
@@ -115,12 +85,14 @@
         updateAccountName(TEST_ACCOUNT);
 
         resetCurrentTimeForTestMode();
-        removeAllTestDictFiles();
+        UserHistoryDictionaryTestsHelper.removeAllTestDictFiles(
+                UserHistoryDictionaryTestsHelper.TEST_LOCALE_PREFIX, mContext);
     }
 
     @Override
     protected void tearDown() throws Exception {
-        removeAllTestDictFiles();
+        UserHistoryDictionaryTestsHelper.removeAllTestDictFiles(
+                UserHistoryDictionaryTestsHelper.TEST_LOCALE_PREFIX, mContext);
         stopTestModeInNativeCode();
 
         // Restore the account that was present before running the test.
@@ -165,58 +137,6 @@
     }
 
     /**
-     * Generates a random word.
-     */
-    private static String generateWord(final int value) {
-        final int lengthOfChars = CHARACTERS.length;
-        final StringBuilder builder = new StringBuilder();
-        long lvalue = Math.abs((long)value);
-        while (lvalue > 0) {
-            builder.append(CHARACTERS[(int)(lvalue % lengthOfChars)]);
-            lvalue /= lengthOfChars;
-        }
-        return builder.toString();
-    }
-
-    private static List<String> generateWords(final int number, final Random random) {
-        final HashSet<String> wordSet = new HashSet<>();
-        while (wordSet.size() < number) {
-            wordSet.add(generateWord(random.nextInt()));
-        }
-        return new ArrayList<>(wordSet);
-    }
-
-    private static void addToDict(final UserHistoryDictionary dict, final List<String> words,
-            final int timestamp) {
-        NgramContext ngramContext = NgramContext.EMPTY_PREV_WORDS_INFO;
-        for (final String word : words) {
-            UserHistoryDictionary.addToDictionary(dict, ngramContext, word, true, timestamp,
-                    DistracterFilter.EMPTY_DISTRACTER_FILTER);
-            ngramContext = ngramContext.getNextNgramContext(new WordInfo(word));
-        }
-    }
-
-    /**
-     * @param checkContents if true, checks whether written words are actually in the dictionary
-     * or not.
-     */
-    private void addAndWriteRandomWords(final UserHistoryDictionary dict,
-            final int numberOfWords, final Random random, final boolean checkContents) {
-        final List<String> words = generateWords(numberOfWords, random);
-        // Add random words to the user history dictionary.
-        addToDict(dict, words, mCurrentTime);
-        if (checkContents) {
-            dict.waitAllTasksForTests();
-            for (int i = 0; i < numberOfWords; ++i) {
-                final String word = words.get(i);
-                assertTrue(dict.isInDictionary(word));
-            }
-        }
-        // write to file.
-        dict.close();
-    }
-
-    /**
      * Clear all entries in the user history dictionary.
      * @param dict the user history dictionary.
      */
@@ -230,19 +150,19 @@
     public void testRandomWords() {
         Log.d(TAG, "This test can be used for profiling.");
         Log.d(TAG, "Usage: please set UserHistoryDictionary.PROFILE_SAVE_RESTORE to true.");
-        final Locale dummyLocale = getDummyLocale("random_words");
+        final Locale dummyLocale = UserHistoryDictionaryTestsHelper.getDummyLocale("random_words");
         final String dictName = UserHistoryDictionary.getUserHistoryDictName(
                 UserHistoryDictionary.NAME, dummyLocale, null /* dictFile */, getContext());
         final File dictFile = ExpandableBinaryDictionary.getDictFile(
                 mContext, dictName, null /* dictFile */);
         final UserHistoryDictionary dict = PersonalizationHelper.getUserHistoryDictionary(
                 getContext(), dummyLocale, TEST_ACCOUNT);
-
+        clearHistory(dict);
         final int numberOfWords = 1000;
         final Random random = new Random(123456);
-        clearHistory(dict);
-        addAndWriteRandomWords(dict, numberOfWords, random, true /* checksContents */);
-        checkExistenceAndRemoveDictFile(dict, dictFile);
+        assertTrue(UserHistoryDictionaryTestsHelper.addAndWriteRandomWords(
+                dict, numberOfWords, random, true /* checksContents */, mCurrentTime));
+        assertDictionaryExists(dict, dictFile);
     }
 
     public void testStressTestForSwitchingLanguagesAndAddingWords() {
@@ -258,7 +178,8 @@
 
             // Create filename suffixes for this test.
             for (int i = 0; i < numberOfLanguages; i++) {
-                final Locale dummyLocale = getDummyLocale("switching_languages" + i);
+                final Locale dummyLocale =
+                        UserHistoryDictionaryTestsHelper.getDummyLocale("switching_languages" + i);
                 final String dictName = UserHistoryDictionary.getUserHistoryDictName(
                         UserHistoryDictionary.NAME, dummyLocale, null /* dictFile */, getContext());
                 dictFiles[i] = ExpandableBinaryDictionary.getDictFile(
@@ -273,8 +194,11 @@
             for (int i = 0; i < numberOfLanguageSwitching; i++) {
                 final int index = i % numberOfLanguages;
                 // Switch to dicts[index].
-                addAndWriteRandomWords(dicts[index], numberOfWordsInsertedForEachLanguageSwitch,
-                        random, false /* checksContents */);
+                assertTrue(UserHistoryDictionaryTestsHelper.addAndWriteRandomWords(dicts[index],
+                        numberOfWordsInsertedForEachLanguageSwitch,
+                        random,
+                        false /* checksContents */,
+                        mCurrentTime));
             }
 
             final long end = System.currentTimeMillis();
@@ -282,13 +206,14 @@
                     + (end - start) + " ms");
         } finally {
             for (int i = 0; i < numberOfLanguages; i++) {
-                checkExistenceAndRemoveDictFile(dicts[i], dictFiles[i]);
+                assertDictionaryExists(dicts[i], dictFiles[i]);
             }
         }
     }
 
     public void testAddManyWords() {
-        final Locale dummyLocale = getDummyLocale("many_random_words");
+        final Locale dummyLocale =
+                UserHistoryDictionaryTestsHelper.getDummyLocale("many_random_words");
         final String dictName = UserHistoryDictionary.getUserHistoryDictName(
                 UserHistoryDictionary.NAME, dummyLocale, null /* dictFile */, getContext());
         final File dictFile = ExpandableBinaryDictionary.getDictFile(
@@ -298,23 +223,23 @@
         final UserHistoryDictionary dict = PersonalizationHelper.getUserHistoryDictionary(
                 getContext(), dummyLocale, TEST_ACCOUNT);
         clearHistory(dict);
-        try {
-            addAndWriteRandomWords(dict, numberOfWords, random, true /* checksContents */);
-        } finally {
-            checkExistenceAndRemoveDictFile(dict, dictFile);
-        }
+        assertTrue(UserHistoryDictionaryTestsHelper.addAndWriteRandomWords(dict,
+                numberOfWords, random, true /* checksContents */, mCurrentTime));
+        assertDictionaryExists(dict, dictFile);
     }
 
     public void testDecaying() {
-        final Locale dummyLocale = getDummyLocale("decaying");
+        final Locale dummyLocale = UserHistoryDictionaryTestsHelper.getDummyLocale("decaying");
         final UserHistoryDictionary dict = PersonalizationHelper.getUserHistoryDictionary(
                 getContext(), dummyLocale, TEST_ACCOUNT);
-        final int numberOfWords = 5000;
-        final Random random = new Random(123456);
         resetCurrentTimeForTestMode();
         clearHistory(dict);
-        final List<String> words = generateWords(numberOfWords, random);
         dict.waitAllTasksForTests();
+
+        final int numberOfWords = 5000;
+        final Random random = new Random(123456);
+        final List<String> words = UserHistoryDictionaryTestsHelper.generateWords(numberOfWords,
+                random);
         NgramContext ngramContext = NgramContext.EMPTY_PREV_WORDS_INFO;
         for (final String word : words) {
             UserHistoryDictionary.addToDictionary(dict, ngramContext, word, true, mCurrentTime,
@@ -329,6 +254,7 @@
         for (final String word : words) {
             assertTrue(dict.isInDictionary(word));
         }
+        // Long term decay results in words removed from the dictionary.
         forcePassingLongTime();
         dict.runGCIfRequired();
         dict.waitAllTasksForTests();
diff --git a/tests/src/com/android/inputmethod/latin/personalization/UserHistoryDictionaryTestsHelper.java b/tests/src/com/android/inputmethod/latin/personalization/UserHistoryDictionaryTestsHelper.java
new file mode 100644
index 0000000..d394c0f
--- /dev/null
+++ b/tests/src/com/android/inputmethod/latin/personalization/UserHistoryDictionaryTestsHelper.java
@@ -0,0 +1,144 @@
+/*
+ * Copyright (C) 2014 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.inputmethod.latin.personalization;
+
+import android.content.Context;
+
+import com.android.inputmethod.latin.NgramContext;
+import com.android.inputmethod.latin.NgramContext.WordInfo;
+import com.android.inputmethod.latin.common.FileUtils;
+import com.android.inputmethod.latin.utils.DistracterFilter;
+
+import java.io.File;
+import java.io.FilenameFilter;
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.List;
+import java.util.Locale;
+import java.util.Random;
+
+/**
+ * Utility class for helping while running tests involving {@link UserHistoryDictionary}.
+ */
+public class UserHistoryDictionaryTestsHelper {
+
+    /**
+     * Locale prefix for generating dummy locales for tests.
+     */
+    public static final String TEST_LOCALE_PREFIX = "test-";
+
+    /**
+     * Characters for generating random words.
+     */
+    private static final String[] CHARACTERS = {
+        "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m",
+        "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z"
+    };
+
+    /**
+     * Remove all the test dictionary files created for the given locale.
+     */
+    public static void removeAllTestDictFiles(final String filter, final Context context) {
+        final FilenameFilter filenameFilter = new FilenameFilter() {
+            @Override
+            public boolean accept(final File dir, final String filename) {
+                return filename.startsWith(UserHistoryDictionary.NAME + "." + filter);
+            }
+        };
+        FileUtils.deleteFilteredFiles(context.getFilesDir(), filenameFilter);
+    }
+
+    /**
+     * Generates and writes random words to dictionary. Caller can be assured
+     * that the write tasks would be finished; and its success would be reflected
+     * in the returned boolean.
+     *
+     * @param dict {@link UserHistoryDictionary} to which words should be added.
+     * @param numberOfWords number of words to be added.
+     * @param random helps generate random words.
+     * @param checkContents if true, checks whether written words are actually in the dictionary.
+     * @param currentTime timestamp that would be used for adding the words.
+     * @returns true if all words have been written to dictionary successfully.
+     */
+    public static boolean addAndWriteRandomWords(final UserHistoryDictionary dict,
+            final int numberOfWords, final Random random, final boolean checkContents,
+            final int currentTime) {
+        final List<String> words = generateWords(numberOfWords, random);
+        // Add random words to the user history dictionary.
+        addWordsToDictionary(dict, words, currentTime);
+        boolean success = true;
+        if (checkContents) {
+            dict.waitAllTasksForTests();
+            for (int i = 0; i < numberOfWords; ++i) {
+                final String word = words.get(i);
+                if (!dict.isInDictionary(word)) {
+                    success = false;
+                    break;
+                }
+            }
+        }
+        // write to file.
+        dict.close();
+        dict.waitAllTasksForTests();
+        return success;
+    }
+
+    private static void addWordsToDictionary(final UserHistoryDictionary dict,
+            final List<String> words, final int timestamp) {
+        NgramContext ngramContext = NgramContext.EMPTY_PREV_WORDS_INFO;
+        for (final String word : words) {
+            UserHistoryDictionary.addToDictionary(dict, ngramContext, word, true, timestamp,
+                    DistracterFilter.EMPTY_DISTRACTER_FILTER);
+            ngramContext = ngramContext.getNextNgramContext(new WordInfo(word));
+        }
+    }
+
+    /**
+     * Creates unique test locale for using within tests.
+     */
+    public static Locale getDummyLocale(final String name) {
+        return new Locale(TEST_LOCALE_PREFIX + name + System.currentTimeMillis());
+    }
+
+    /**
+     * Generates random words.
+     *
+     * @param numberOfWords number of words to generate.
+     * @param random salt used for generating random words.
+     */
+    public static List<String> generateWords(final int numberOfWords, final Random random) {
+        final HashSet<String> wordSet = new HashSet<>();
+        while (wordSet.size() < numberOfWords) {
+            wordSet.add(generateWord(random.nextInt()));
+        }
+        return new ArrayList<>(wordSet);
+    }
+
+    /**
+     * Generates a random word.
+     */
+    private static String generateWord(final int value) {
+        final int lengthOfChars = CHARACTERS.length;
+        final StringBuilder builder = new StringBuilder();
+        long lvalue = Math.abs((long)value);
+        while (lvalue > 0) {
+            builder.append(CHARACTERS[(int)(lvalue % lengthOfChars)]);
+            lvalue /= lengthOfChars;
+        }
+        return builder.toString();
+    }
+}