Merge "Better isolate ResearchLogging data"
diff --git a/java/res/values-af/strings.xml b/java/res/values-af/strings.xml
index f5a6245..2892940 100644
--- a/java/res/values-af/strings.xml
+++ b/java/res/values-af/strings.xml
@@ -135,8 +135,7 @@
     <string name="hint_add_to_dictionary" msgid="573678656946085380">"Raak weer om te stoor"</string>
     <string name="has_dictionary" msgid="6071847973466625007">"Woordeboek beskikbaar"</string>
     <string name="prefs_enable_log" msgid="6620424505072963557">"Aktiveer gebruikerterugvoer"</string>
-    <!-- no translation found for prefs_description_log (7525225584555429211) -->
-    <skip />
+    <string name="prefs_description_log" msgid="7525225584555429211">"Help om hierdie invoermetode-redigeerder te verbeter deur gebruikstatistiek en omvalverslae outomaties te stuur"</string>
     <string name="keyboard_layout" msgid="8451164783510487501">"Sleutelbordtema"</string>
     <string name="subtype_en_GB" msgid="88170601942311355">"Engels (VK)"</string>
     <string name="subtype_en_US" msgid="6160452336634534239">"Engels (VS)"</string>
@@ -163,12 +162,9 @@
     <string name="not_now" msgid="6172462888202790482">"Nie nou nie"</string>
     <string name="custom_input_style_already_exists" msgid="8008728952215449707">"Dieselfde invoerstyl bestaan ​​reeds: <xliff:g id="INPUT_STYLE_NAME">%s</xliff:g>"</string>
     <string name="prefs_usability_study_mode" msgid="1261130555134595254">"Bruikbaarheidstudie-modus"</string>
-    <!-- no translation found for prefs_key_longpress_timeout_settings (6102240298932897873) -->
-    <skip />
-    <!-- no translation found for prefs_keypress_vibration_duration_settings (7918341459947439226) -->
-    <skip />
-    <!-- no translation found for prefs_keypress_sound_volume_settings (6027007337036891623) -->
-    <skip />
+    <string name="prefs_key_longpress_timeout_settings" msgid="6102240298932897873">"Vertraging van sleutellangdruk"</string>
+    <string name="prefs_keypress_vibration_duration_settings" msgid="7918341459947439226">"Sleuteldruk se vibrasie-tydsduur"</string>
+    <string name="prefs_keypress_sound_volume_settings" msgid="6027007337036891623">"Sleuteldruk se klankvolume"</string>
     <string name="prefs_read_external_dictionary" msgid="2588931418575013067">"Lees eksterne woordeboeklêer"</string>
     <string name="read_external_dictionary_no_files_message" msgid="4947420942224623792">"Geen woordeboeklêers in die aflaaiselsvouer nie"</string>
     <string name="read_external_dictionary_multiple_files_title" msgid="7637749044265808628">"Kies \'n woordeboeklêer om te installeer"</string>
diff --git a/java/res/values-el/strings.xml b/java/res/values-el/strings.xml
index 41cf098..fad1cf5 100644
--- a/java/res/values-el/strings.xml
+++ b/java/res/values-el/strings.xml
@@ -135,8 +135,7 @@
     <string name="hint_add_to_dictionary" msgid="573678656946085380">"Αγγίξτε ξανά για αποθήκευση"</string>
     <string name="has_dictionary" msgid="6071847973466625007">"Λεξικό διαθέσιμο"</string>
     <string name="prefs_enable_log" msgid="6620424505072963557">"Ενεργοποίηση σχολίων χρηστών"</string>
-    <!-- no translation found for prefs_description_log (7525225584555429211) -->
-    <skip />
+    <string name="prefs_description_log" msgid="7525225584555429211">"Βοηθήστε μας να βελτιώσουμε αυτό το πρόγραμμα επεξεργασίας μεθόδου εισόδου, στέλνοντας αυτόματα στατιστικά στοιχεία και αναφορές σφαλμάτων."</string>
     <string name="keyboard_layout" msgid="8451164783510487501">"Θέμα πληκτρολογίου"</string>
     <string name="subtype_en_GB" msgid="88170601942311355">"Αγγλικά (Η.Β.)"</string>
     <string name="subtype_en_US" msgid="6160452336634534239">"Αγγλικά (Η.Π.Α)"</string>
@@ -163,12 +162,9 @@
     <string name="not_now" msgid="6172462888202790482">"Όχι τώρα"</string>
     <string name="custom_input_style_already_exists" msgid="8008728952215449707">"Το ίδιο στυλ εισόδου υπάρχει ήδη: <xliff:g id="INPUT_STYLE_NAME">%s</xliff:g>"</string>
     <string name="prefs_usability_study_mode" msgid="1261130555134595254">"Λειτουργία μελέτης χρηστικότητας"</string>
-    <!-- no translation found for prefs_key_longpress_timeout_settings (6102240298932897873) -->
-    <skip />
-    <!-- no translation found for prefs_keypress_vibration_duration_settings (7918341459947439226) -->
-    <skip />
-    <!-- no translation found for prefs_keypress_sound_volume_settings (6027007337036891623) -->
-    <skip />
+    <string name="prefs_key_longpress_timeout_settings" msgid="6102240298932897873">"Καθυστέρηση παρατεταμένου πατήματος πλήκτρου"</string>
+    <string name="prefs_keypress_vibration_duration_settings" msgid="7918341459947439226">"Διάρκεια δόνησης πατήμ. πλήκτ."</string>
+    <string name="prefs_keypress_sound_volume_settings" msgid="6027007337036891623">"Ένταση ήχου πατήματος πλήκτρου"</string>
     <string name="prefs_read_external_dictionary" msgid="2588931418575013067">"Ανάγνωση εξωτερικού αρχείου λεξικού"</string>
     <string name="read_external_dictionary_no_files_message" msgid="4947420942224623792">"Δεν υπάρχουν αρχεία λεξικού στο φάκελο \"Λήψεις\""</string>
     <string name="read_external_dictionary_multiple_files_title" msgid="7637749044265808628">"Επιλογή αρχείου λεξικού για εγκατάσταση"</string>
diff --git a/java/res/values-en-rGB/strings.xml b/java/res/values-en-rGB/strings.xml
index 3aab692..c0b9ede 100644
--- a/java/res/values-en-rGB/strings.xml
+++ b/java/res/values-en-rGB/strings.xml
@@ -135,8 +135,7 @@
     <string name="hint_add_to_dictionary" msgid="573678656946085380">"Touch again to save"</string>
     <string name="has_dictionary" msgid="6071847973466625007">"Dictionary available"</string>
     <string name="prefs_enable_log" msgid="6620424505072963557">"Enable user feedback"</string>
-    <!-- no translation found for prefs_description_log (7525225584555429211) -->
-    <skip />
+    <string name="prefs_description_log" msgid="7525225584555429211">"Help improve this input method editor by automatically sending usage statistics and crash reports"</string>
     <string name="keyboard_layout" msgid="8451164783510487501">"Keyboard theme"</string>
     <string name="subtype_en_GB" msgid="88170601942311355">"English (UK)"</string>
     <string name="subtype_en_US" msgid="6160452336634534239">"English (US)"</string>
@@ -163,12 +162,9 @@
     <string name="not_now" msgid="6172462888202790482">"Not now"</string>
     <string name="custom_input_style_already_exists" msgid="8008728952215449707">"The same input style already exists: <xliff:g id="INPUT_STYLE_NAME">%s</xliff:g>"</string>
     <string name="prefs_usability_study_mode" msgid="1261130555134595254">"Usability study mode"</string>
-    <!-- no translation found for prefs_key_longpress_timeout_settings (6102240298932897873) -->
-    <skip />
-    <!-- no translation found for prefs_keypress_vibration_duration_settings (7918341459947439226) -->
-    <skip />
-    <!-- no translation found for prefs_keypress_sound_volume_settings (6027007337036891623) -->
-    <skip />
+    <string name="prefs_key_longpress_timeout_settings" msgid="6102240298932897873">"Key long press delay"</string>
+    <string name="prefs_keypress_vibration_duration_settings" msgid="7918341459947439226">"Keypress vibration duration"</string>
+    <string name="prefs_keypress_sound_volume_settings" msgid="6027007337036891623">"Keypress sound volume"</string>
     <string name="prefs_read_external_dictionary" msgid="2588931418575013067">"Read external dictionary file"</string>
     <string name="read_external_dictionary_no_files_message" msgid="4947420942224623792">"No dictionary files in the Downloads folder"</string>
     <string name="read_external_dictionary_multiple_files_title" msgid="7637749044265808628">"Select a dictionary file to install"</string>
diff --git a/java/res/values-it/strings.xml b/java/res/values-it/strings.xml
index 028a7a2..c64543a 100644
--- a/java/res/values-it/strings.xml
+++ b/java/res/values-it/strings.xml
@@ -135,8 +135,7 @@
     <string name="hint_add_to_dictionary" msgid="573678656946085380">"Tocca di nuovo per salvare"</string>
     <string name="has_dictionary" msgid="6071847973466625007">"Dizionario disponibile"</string>
     <string name="prefs_enable_log" msgid="6620424505072963557">"Attiva commenti degli utenti"</string>
-    <!-- no translation found for prefs_description_log (7525225584555429211) -->
-    <skip />
+    <string name="prefs_description_log" msgid="7525225584555429211">"Contribuisci a migliorare l\'editor del metodo di immissione inviando automaticamente statistiche sull\'utilizzo e rapporti sugli arresti anomali"</string>
     <string name="keyboard_layout" msgid="8451164783510487501">"Tema della tastiera"</string>
     <string name="subtype_en_GB" msgid="88170601942311355">"Inglese (UK)"</string>
     <string name="subtype_en_US" msgid="6160452336634534239">"Inglese (USA)"</string>
@@ -163,12 +162,9 @@
     <string name="not_now" msgid="6172462888202790482">"Non ora"</string>
     <string name="custom_input_style_already_exists" msgid="8008728952215449707">"Esiste già uno stile di inuput uguale: <xliff:g id="INPUT_STYLE_NAME">%s</xliff:g>"</string>
     <string name="prefs_usability_study_mode" msgid="1261130555134595254">"Modalità Studio sull\'usabilità"</string>
-    <!-- no translation found for prefs_key_longpress_timeout_settings (6102240298932897873) -->
-    <skip />
-    <!-- no translation found for prefs_keypress_vibration_duration_settings (7918341459947439226) -->
-    <skip />
-    <!-- no translation found for prefs_keypress_sound_volume_settings (6027007337036891623) -->
-    <skip />
+    <string name="prefs_key_longpress_timeout_settings" msgid="6102240298932897873">"Ritardo pressione lunga tasti"</string>
+    <string name="prefs_keypress_vibration_duration_settings" msgid="7918341459947439226">"Durata vibraz. pressione tasto"</string>
+    <string name="prefs_keypress_sound_volume_settings" msgid="6027007337036891623">"Volume audio a pressione tasto"</string>
     <string name="prefs_read_external_dictionary" msgid="2588931418575013067">"Leggi file dizionario esterno"</string>
     <string name="read_external_dictionary_no_files_message" msgid="4947420942224623792">"Nessun file di dizionario nella cartella Download"</string>
     <string name="read_external_dictionary_multiple_files_title" msgid="7637749044265808628">"Seleziona un file di dizionario da installare"</string>
diff --git a/java/res/values/keypress-vibration-durations.xml b/java/res/values/keypress-vibration-durations.xml
index 9b1d543..10400be 100644
--- a/java/res/values/keypress-vibration-durations.xml
+++ b/java/res/values/keypress-vibration-durations.xml
@@ -18,13 +18,17 @@
 */
 -->
 <resources>
+    <!-- Build.HARDWARE,duration_in_milliseconds -->
     <string-array name="keypress_vibration_durations" translatable="false">
-        <!-- Build.HARDWARE,duration_in_milliseconds -->
+        <!-- Nexus S -->
         <item>herring,5</item>
+        <!-- Galaxy Nexus -->
         <item>tuna,5</item>
+        <!-- Nexus 4 -->
         <item>mako,5</item>
+        <!-- Nexus 10 -->
         <item>manta,16</item>
         <!-- Default value for unknown device -->
-        <item>DEFAULT,10</item>
+        <item>DEFAULT,20</item>
     </string-array>
 </resources>
diff --git a/java/res/xml/prefs.xml b/java/res/xml/prefs.xml
index 7839462..a13021b 100644
--- a/java/res/xml/prefs.xml
+++ b/java/res/xml/prefs.xml
@@ -90,6 +90,7 @@
             android:summary="@string/gesture_input_summary"
             android:persistent="true"
             android:defaultValue="true" />
+        <!-- TODO: Move these two options to the advanced settings. -->
         <CheckBoxPreference
             android:key="pref_gesture_floating_preview_text"
             android:title="@string/gesture_floating_preview_text"
@@ -139,10 +140,6 @@
                 android:summary="@string/include_other_imes_in_language_switch_list_summary"
                 android:persistent="true"
                 android:defaultValue="false" />
-            <PreferenceScreen
-                android:fragment="com.android.inputmethod.latin.AdditionalSubtypeSettings"
-                android:key="custom_input_styles"
-                android:title="@string/custom_input_styles_title" />
             <!-- Values for popup dismiss delay are added programmatically -->
             <CheckBoxPreference
                 android:key="pref_sliding_key_input_preview"
@@ -150,6 +147,10 @@
                 android:summary="@string/sliding_key_input_preview_summary"
                 android:persistent="true"
                 android:defaultValue="true" />
+            <PreferenceScreen
+                android:fragment="com.android.inputmethod.latin.AdditionalSubtypeSettings"
+                android:key="custom_input_styles"
+                android:title="@string/custom_input_styles_title" />
             <ListPreference
                 android:key="pref_key_preview_popup_dismiss_delay"
                 android:title="@string/key_preview_popup_dismiss_delay" />
diff --git a/java/src/com/android/inputmethod/keyboard/KeyboardView.java b/java/src/com/android/inputmethod/keyboard/KeyboardView.java
index 43d28be..e4e75c3 100644
--- a/java/src/com/android/inputmethod/keyboard/KeyboardView.java
+++ b/java/src/com/android/inputmethod/keyboard/KeyboardView.java
@@ -26,10 +26,8 @@
 import android.graphics.PorterDuff;
 import android.graphics.Rect;
 import android.graphics.Region;
-import android.graphics.Typeface;
 import android.graphics.drawable.Drawable;
 import android.util.AttributeSet;
-import android.util.SparseArray;
 import android.view.View;
 
 import com.android.inputmethod.keyboard.internal.KeyDrawParams;
@@ -73,15 +71,15 @@
  */
 public class KeyboardView extends View {
     // XML attributes
-    protected final KeyVisualAttributes mKeyVisualAttributes;
+    private final KeyVisualAttributes mKeyVisualAttributes;
     private final int mKeyLabelHorizontalPadding;
     private final float mKeyHintLetterPadding;
     private final float mKeyPopupHintLetterPadding;
     private final float mKeyShiftedLetterHintPadding;
     private final float mKeyTextShadowRadius;
-    protected final float mVerticalCorrection;
-    protected final Drawable mKeyBackground;
-    protected final Rect mKeyBackgroundPadding = new Rect();
+    private final float mVerticalCorrection;
+    private final Drawable mKeyBackground;
+    private final Rect mKeyBackgroundPadding = new Rect();
 
     // HORIZONTAL ELLIPSIS "...", character for popup hint.
     private static final String POPUP_HINT_CHAR = "\u2026";
@@ -113,10 +111,6 @@
     private final Canvas mOffscreenCanvas = new Canvas();
     private final Paint mPaint = new Paint();
     private final Paint.FontMetrics mFontMetrics = new Paint.FontMetrics();
-    // This sparse array caches key label text height in pixel indexed by key label text size.
-    private static final SparseArray<Float> sTextHeightCache = CollectionUtils.newSparseArray();
-    // This sparse array caches key label text width in pixel indexed by key label text size.
-    private static final SparseArray<Float> sTextWidthCache = CollectionUtils.newSparseArray();
     private static final char[] KEY_LABEL_REFERENCE_CHAR = { 'M' };
     private static final char[] KEY_NUMERIC_HINT_LABEL_REFERENCE_CHAR = { '8' };
 
@@ -134,15 +128,15 @@
         mKeyLabelHorizontalPadding = keyboardViewAttr.getDimensionPixelOffset(
                 R.styleable.KeyboardView_keyLabelHorizontalPadding, 0);
         mKeyHintLetterPadding = keyboardViewAttr.getDimension(
-                R.styleable.KeyboardView_keyHintLetterPadding, 0);
+                R.styleable.KeyboardView_keyHintLetterPadding, 0.0f);
         mKeyPopupHintLetterPadding = keyboardViewAttr.getDimension(
-                R.styleable.KeyboardView_keyPopupHintLetterPadding, 0);
+                R.styleable.KeyboardView_keyPopupHintLetterPadding, 0.0f);
         mKeyShiftedLetterHintPadding = keyboardViewAttr.getDimension(
-                R.styleable.KeyboardView_keyShiftedLetterHintPadding, 0);
+                R.styleable.KeyboardView_keyShiftedLetterHintPadding, 0.0f);
         mKeyTextShadowRadius = keyboardViewAttr.getFloat(
                 R.styleable.KeyboardView_keyTextShadowRadius, 0.0f);
         mVerticalCorrection = keyboardViewAttr.getDimension(
-                R.styleable.KeyboardView_verticalCorrection, 0);
+                R.styleable.KeyboardView_verticalCorrection, 0.0f);
         keyboardViewAttr.recycle();
 
         final TypedArray keyAttr = context.obtainStyledAttributes(attrs,
@@ -185,6 +179,14 @@
         return mKeyboard;
     }
 
+    protected float getVerticalCorrection() {
+        return mVerticalCorrection;
+    }
+
+    protected void updateKeyDrawParams(final int keyHeight) {
+        mKeyDrawParams.updateParams(keyHeight, mKeyVisualAttributes);
+    }
+
     @Override
     protected void onMeasure(final int widthMeasureSpec, final int heightMeasureSpec) {
         if (mKeyboard != null) {
@@ -213,7 +215,7 @@
             }
             onDrawKeyboard(mOffscreenCanvas);
         }
-        canvas.drawBitmap(mOffscreenBuffer, 0, 0, null);
+        canvas.drawBitmap(mOffscreenBuffer, 0.0f, 0.0f, null);
     }
 
     private boolean maybeAllocateOffscreenBuffer() {
@@ -333,7 +335,7 @@
         canvas.translate(bgX, bgY);
         background.draw(canvas);
         if (LatinImeLogger.sVISUALDEBUG) {
-            drawRectangle(canvas, 0, 0, bgWidth, bgHeight, 0x80c00000, new Paint());
+            drawRectangle(canvas, 0.0f, 0.0f, bgWidth, bgHeight, 0x80c00000, new Paint());
         }
         canvas.translate(-bgX, -bgY);
     }
@@ -347,7 +349,7 @@
         final float centerY = keyHeight * 0.5f;
 
         if (LatinImeLogger.sVISUALDEBUG) {
-            drawRectangle(canvas, 0, 0, keyWidth, keyHeight, 0x800000c0, new Paint());
+            drawRectangle(canvas, 0.0f, 0.0f, keyWidth, keyHeight, 0x800000c0, new Paint());
         }
 
         // Draw key label.
@@ -357,14 +359,16 @@
             final String label = key.mLabel;
             paint.setTypeface(key.selectTypeface(params));
             paint.setTextSize(key.selectTextSize(params));
-            final float labelCharHeight = getCharHeight(KEY_LABEL_REFERENCE_CHAR, paint);
-            final float labelCharWidth = getCharWidth(KEY_LABEL_REFERENCE_CHAR, paint);
+            final float labelCharHeight = TypefaceUtils.getCharHeight(
+                    KEY_LABEL_REFERENCE_CHAR, paint);
+            final float labelCharWidth = TypefaceUtils.getCharWidth(
+                    KEY_LABEL_REFERENCE_CHAR, paint);
 
             // Vertical label text alignment.
-            final float baseline = centerY + labelCharHeight / 2;
+            final float baseline = centerY + labelCharHeight / 2.0f;
 
             // Horizontal label text alignment
-            float labelWidth = 0;
+            float labelWidth = 0.0f;
             if (key.isAlignLeft()) {
                 positionX = mKeyLabelHorizontalPadding;
                 paint.setTextAlign(Align.LEFT);
@@ -373,31 +377,31 @@
                 paint.setTextAlign(Align.RIGHT);
             } else if (key.isAlignLeftOfCenter()) {
                 // TODO: Parameterise this?
-                positionX = centerX - labelCharWidth * 7 / 4;
+                positionX = centerX - labelCharWidth * 7.0f / 4.0f;
                 paint.setTextAlign(Align.LEFT);
             } else if (key.hasLabelWithIconLeft() && icon != null) {
-                labelWidth = getLabelWidth(label, paint) + icon.getIntrinsicWidth()
+                labelWidth = TypefaceUtils.getLabelWidth(label, paint) + icon.getIntrinsicWidth()
                         + LABEL_ICON_MARGIN * keyWidth;
-                positionX = centerX + labelWidth / 2;
+                positionX = centerX + labelWidth / 2.0f;
                 paint.setTextAlign(Align.RIGHT);
             } else if (key.hasLabelWithIconRight() && icon != null) {
-                labelWidth = getLabelWidth(label, paint) + icon.getIntrinsicWidth()
+                labelWidth = TypefaceUtils.getLabelWidth(label, paint) + icon.getIntrinsicWidth()
                         + LABEL_ICON_MARGIN * keyWidth;
-                positionX = centerX - labelWidth / 2;
+                positionX = centerX - labelWidth / 2.0f;
                 paint.setTextAlign(Align.LEFT);
             } else {
                 positionX = centerX;
                 paint.setTextAlign(Align.CENTER);
             }
             if (key.needsXScale()) {
-                paint.setTextScaleX(
-                        Math.min(1.0f, (keyWidth * MAX_LABEL_RATIO) / getLabelWidth(label, paint)));
+                paint.setTextScaleX(Math.min(1.0f,
+                        (keyWidth * MAX_LABEL_RATIO) / TypefaceUtils.getLabelWidth(label, paint)));
             }
 
             paint.setColor(key.selectTextColor(params));
             if (key.isEnabled()) {
                 // Set a drop shadow for the text
-                paint.setShadowLayer(mKeyTextShadowRadius, 0, 0, params.mTextShadowColor);
+                paint.setShadowLayer(mKeyTextShadowRadius, 0.0f, 0.0f, params.mTextShadowColor);
             } else {
                 // Make label invisible
                 paint.setColor(Color.TRANSPARENT);
@@ -405,7 +409,7 @@
             blendAlpha(paint, params.mAnimAlpha);
             canvas.drawText(label, 0, label.length(), positionX, baseline, paint);
             // Turn off drop shadow and reset x-scale.
-            paint.setShadowLayer(0, 0, 0, 0);
+            paint.setShadowLayer(0.0f, 0.0f, 0.0f, Color.TRANSPARENT);
             paint.setTextScaleX(1.0f);
 
             if (icon != null) {
@@ -413,10 +417,10 @@
                 final int iconHeight = icon.getIntrinsicHeight();
                 final int iconY = (keyHeight - iconHeight) / 2;
                 if (key.hasLabelWithIconLeft()) {
-                    final int iconX = (int)(centerX - labelWidth / 2);
+                    final int iconX = (int)(centerX - labelWidth / 2.0f);
                     drawIcon(canvas, icon, iconX, iconY, iconWidth, iconHeight);
                 } else if (key.hasLabelWithIconRight()) {
-                    final int iconX = (int)(centerX + labelWidth / 2 - iconWidth);
+                    final int iconX = (int)(centerX + labelWidth / 2.0f - iconWidth);
                     drawIcon(canvas, icon, iconX, iconY, iconWidth, iconHeight);
                 }
             }
@@ -439,20 +443,23 @@
                 // The hint label is placed just right of the key label. Used mainly on
                 // "phone number" layout.
                 // TODO: Generalize the following calculations.
-                hintX = positionX + getCharWidth(KEY_LABEL_REFERENCE_CHAR, paint) * 2;
-                hintY = centerY + getCharHeight(KEY_LABEL_REFERENCE_CHAR, paint) / 2;
+                hintX = positionX
+                        + TypefaceUtils.getCharWidth(KEY_LABEL_REFERENCE_CHAR, paint) * 2.0f;
+                hintY = centerY
+                        + TypefaceUtils.getCharHeight(KEY_LABEL_REFERENCE_CHAR, paint) / 2.0f;
                 paint.setTextAlign(Align.LEFT);
             } else if (key.hasShiftedLetterHint()) {
                 // The hint label is placed at top-right corner of the key. Used mainly on tablet.
                 hintX = keyWidth - mKeyShiftedLetterHintPadding
-                        - getCharWidth(KEY_LABEL_REFERENCE_CHAR, paint) / 2;
+                        - TypefaceUtils.getCharWidth(KEY_LABEL_REFERENCE_CHAR, paint) / 2.0f;
                 paint.getFontMetrics(mFontMetrics);
                 hintY = -mFontMetrics.top;
                 paint.setTextAlign(Align.CENTER);
             } else { // key.hasHintLetter()
                 // The hint letter is placed at top-right corner of the key. Used mainly on phone.
                 hintX = keyWidth - mKeyHintLetterPadding
-                        - getCharWidth(KEY_NUMERIC_HINT_LABEL_REFERENCE_CHAR, paint) / 2;
+                        - TypefaceUtils.getCharWidth(KEY_NUMERIC_HINT_LABEL_REFERENCE_CHAR, paint)
+                        / 2.0f;
                 hintY = -paint.ascent();
                 paint.setTextAlign(Align.CENTER);
             }
@@ -506,7 +513,7 @@
         paint.setColor(params.mHintLabelColor);
         paint.setTextAlign(Align.CENTER);
         final float hintX = keyWidth - mKeyHintLetterPadding
-                - getCharWidth(KEY_LABEL_REFERENCE_CHAR, paint) / 2;
+                - TypefaceUtils.getCharWidth(KEY_LABEL_REFERENCE_CHAR, paint) / 2.0f;
         final float hintY = keyHeight - mKeyPopupHintLetterPadding;
         canvas.drawText(POPUP_HINT_CHAR, hintX, hintY, paint);
 
@@ -517,54 +524,6 @@
         }
     }
 
-    private static int getCharGeometryCacheKey(final char referenceChar, final Paint paint) {
-        final int labelSize = (int)paint.getTextSize();
-        final Typeface face = paint.getTypeface();
-        final int codePointOffset = referenceChar << 15;
-        if (face == Typeface.DEFAULT) {
-            return codePointOffset + labelSize;
-        } else if (face == Typeface.DEFAULT_BOLD) {
-            return codePointOffset + labelSize + 0x1000;
-        } else if (face == Typeface.MONOSPACE) {
-            return codePointOffset + labelSize + 0x2000;
-        } else {
-            return codePointOffset + labelSize;
-        }
-    }
-
-    // Working variable for the following methods.
-    private final Rect mTextBounds = new Rect();
-
-    private float getCharHeight(final char[] referenceChar, final Paint paint) {
-        final int key = getCharGeometryCacheKey(referenceChar[0], paint);
-        final Float cachedValue = sTextHeightCache.get(key);
-        if (cachedValue != null)
-            return cachedValue;
-
-        paint.getTextBounds(referenceChar, 0, 1, mTextBounds);
-        final float height = mTextBounds.height();
-        sTextHeightCache.put(key, height);
-        return height;
-    }
-
-    private float getCharWidth(final char[] referenceChar, final Paint paint) {
-        final int key = getCharGeometryCacheKey(referenceChar[0], paint);
-        final Float cachedValue = sTextWidthCache.get(key);
-        if (cachedValue != null)
-            return cachedValue;
-
-        paint.getTextBounds(referenceChar, 0, 1, mTextBounds);
-        final float width = mTextBounds.width();
-        sTextWidthCache.put(key, width);
-        return width;
-    }
-
-    // TODO: Remove this method.
-    public float getLabelWidth(final String label, final Paint paint) {
-        paint.getTextBounds(label, 0, label.length(), mTextBounds);
-        return mTextBounds.width();
-    }
-
     protected static void drawIcon(final Canvas canvas, final Drawable icon, final int x,
             final int y, final int width, final int height) {
         canvas.translate(x, y);
@@ -578,7 +537,7 @@
         paint.setStyle(Paint.Style.STROKE);
         paint.setStrokeWidth(1.0f);
         paint.setColor(color);
-        canvas.drawLine(0, y, w, y, paint);
+        canvas.drawLine(0.0f, y, w, y, paint);
     }
 
     private static void drawVerticalLine(final Canvas canvas, final float x, final float h,
@@ -586,7 +545,7 @@
         paint.setStyle(Paint.Style.STROKE);
         paint.setStrokeWidth(1.0f);
         paint.setColor(color);
-        canvas.drawLine(x, 0, x, h, paint);
+        canvas.drawLine(x, 0.0f, x, h, paint);
     }
 
     private static void drawRectangle(final Canvas canvas, final float x, final float y,
@@ -595,15 +554,20 @@
         paint.setStrokeWidth(1.0f);
         paint.setColor(color);
         canvas.translate(x, y);
-        canvas.drawRect(0, 0, w, h, paint);
+        canvas.drawRect(0.0f, 0.0f, w, h, paint);
         canvas.translate(-x, -y);
     }
 
-    public Paint newDefaultLabelPaint() {
+    public Paint newLabelPaint(final Key key) {
         final Paint paint = new Paint();
         paint.setAntiAlias(true);
-        paint.setTypeface(mKeyDrawParams.mTypeface);
-        paint.setTextSize(mKeyDrawParams.mLabelSize);
+        if (key == null) {
+            paint.setTypeface(mKeyDrawParams.mTypeface);
+            paint.setTextSize(mKeyDrawParams.mLabelSize);
+        } else {
+            paint.setTypeface(key.selectTypeface(mKeyDrawParams));
+            paint.setTextSize(key.selectTextSize(mKeyDrawParams));
+        }
         return paint;
     }
 
diff --git a/java/src/com/android/inputmethod/keyboard/MainKeyboardView.java b/java/src/com/android/inputmethod/keyboard/MainKeyboardView.java
index 7dfbea3..ba78d01 100644
--- a/java/src/com/android/inputmethod/keyboard/MainKeyboardView.java
+++ b/java/src/com/android/inputmethod/keyboard/MainKeyboardView.java
@@ -530,9 +530,9 @@
                 R.styleable.MainKeyboardView_altCodeKeyWhileTypingFadeinAnimator, 0);
 
         final float keyHysteresisDistance = mainKeyboardViewAttr.getDimension(
-                R.styleable.MainKeyboardView_keyHysteresisDistance, 0);
+                R.styleable.MainKeyboardView_keyHysteresisDistance, 0.0f);
         final float keyHysteresisDistanceForSlidingModifier = mainKeyboardViewAttr.getDimension(
-                R.styleable.MainKeyboardView_keyHysteresisDistanceForSlidingModifier, 0);
+                R.styleable.MainKeyboardView_keyHysteresisDistanceForSlidingModifier, 0.0f);
         mKeyDetector = new KeyDetector(
                 keyHysteresisDistance, keyHysteresisDistanceForSlidingModifier);
         mKeyTimerHandler = new KeyTimerHandler(this, mainKeyboardViewAttr);
@@ -655,7 +655,7 @@
         mKeyTimerHandler.cancelLongPressTimer();
         super.setKeyboard(keyboard);
         mKeyDetector.setKeyboard(
-                keyboard, -getPaddingLeft(), -getPaddingTop() + mVerticalCorrection);
+                keyboard, -getPaddingLeft(), -getPaddingTop() + getVerticalCorrection());
         PointerTracker.setKeyDetector(mKeyDetector);
         mTouchScreenRegulator.setKeyboardGeometry(keyboard.mOccupiedWidth);
         mMoreKeysKeyboardCache.clear();
@@ -1329,7 +1329,7 @@
 
         // Overlay a dark rectangle to dim.
         if (mNeedsToDimEntireKeyboard) {
-            canvas.drawRect(0, 0, getWidth(), getHeight(), mBackgroundDimAlphaPaint);
+            canvas.drawRect(0.0f, 0.0f, getWidth(), getHeight(), mBackgroundDimAlphaPaint);
         }
     }
 
@@ -1353,9 +1353,10 @@
         }
     }
 
-    private boolean fitsTextIntoWidth(final int width, final String text, final Paint paint) {
+    private static boolean fitsTextIntoWidth(final int width, final String text,
+            final Paint paint) {
         paint.setTextScaleX(1.0f);
-        final float textWidth = getLabelWidth(text, paint);
+        final float textWidth = TypefaceUtils.getLabelWidth(text, paint);
         if (textWidth < width) {
             return true;
         }
@@ -1366,12 +1367,12 @@
         }
 
         paint.setTextScaleX(scaleX);
-        return getLabelWidth(text, paint) < width;
+        return TypefaceUtils.getLabelWidth(text, paint) < width;
     }
 
     // Layout language name on spacebar.
-    private String layoutLanguageOnSpacebar(final Paint paint, final InputMethodSubtype subtype,
-            final int width) {
+    private static String layoutLanguageOnSpacebar(final Paint paint,
+            final InputMethodSubtype subtype, final int width) {
         // Choose appropriate language name to fit into the width.
         final String fullText = getFullDisplayName(subtype);
         if (fitsTextIntoWidth(width, fullText, paint)) {
diff --git a/java/src/com/android/inputmethod/keyboard/MoreKeysKeyboard.java b/java/src/com/android/inputmethod/keyboard/MoreKeysKeyboard.java
index 66c3014..ae08a59 100644
--- a/java/src/com/android/inputmethod/keyboard/MoreKeysKeyboard.java
+++ b/java/src/com/android/inputmethod/keyboard/MoreKeysKeyboard.java
@@ -17,6 +17,7 @@
 package com.android.inputmethod.keyboard;
 
 import android.content.Context;
+import android.content.res.Resources;
 import android.graphics.Paint;
 import android.graphics.drawable.Drawable;
 
@@ -73,10 +74,11 @@
                 final int rowHeight, final int coordXInParent, final int parentKeyboardWidth,
                 final boolean isFixedColumnOrder, final int dividerWidth) {
             mIsFixedOrder = isFixedColumnOrder;
-            if (parentKeyboardWidth / keyWidth < maxColumns) {
+            if (parentKeyboardWidth / keyWidth < Math.min(numKeys, maxColumns)) {
                 throw new IllegalArgumentException(
                         "Keyboard is too small to hold more keys keyboard: "
-                                + parentKeyboardWidth + " " + keyWidth + " " + maxColumns);
+                                + parentKeyboardWidth + " " + keyWidth + " "
+                                + numKeys + " " + maxColumns);
             }
             mDefaultKeyWidth = keyWidth;
             mDefaultRowHeight = rowHeight;
@@ -257,7 +259,6 @@
         private static final float LABEL_PADDING_RATIO = 0.2f;
         private static final float DIVIDER_RATIO = 0.2f;
 
-
         /**
          * The builder of MoreKeysKeyboard.
          * @param context the context of {@link MoreKeysKeyboardView}.
@@ -289,11 +290,23 @@
                 // be considered because the vertical positions of both backgrounds were already
                 // adjusted with their bottom paddings deducted.
                 width = keyPreviewDrawParams.mPreviewVisibleWidth;
-                height = keyPreviewDrawParams.mPreviewVisibleHeight
-                        + mParams.mVerticalGap;
+                height = keyPreviewDrawParams.mPreviewVisibleHeight + mParams.mVerticalGap;
+                // TODO: Remove this check.
+                if (width == 0) {
+                    throw new IllegalArgumentException(
+                            "Zero width key detected: " + parentKey + " in " + parentKeyboard.mId);
+                }
             } else {
-                width = getMaxKeyWidth(parentKeyboardView, parentKey, mParams.mDefaultKeyWidth);
+                width = getMaxKeyWidth(parentKeyboardView, parentKey, mParams.mDefaultKeyWidth,
+                        context.getResources());
                 height = parentKeyboard.mMostCommonKeyHeight;
+                // TODO: Remove this check.
+                if (width == 0) {
+                    throw new IllegalArgumentException(
+                            "Zero width calculated: " + parentKey
+                            + " moreKeys=" + java.util.Arrays.toString(parentKey.mMoreKeys)
+                            + " in " + parentKeyboard.mId);
+                }
             }
             final int dividerWidth;
             if (parentKey.needsDividersInMoreKeys()) {
@@ -310,22 +323,18 @@
         }
 
         private static int getMaxKeyWidth(final KeyboardView view, final Key parentKey,
-                final int minKeyWidth) {
-            final int padding = (int)(view.getResources()
-                    .getDimension(R.dimen.more_keys_keyboard_key_horizontal_padding)
-                    + (parentKey.hasLabelsInMoreKeys() ? minKeyWidth * LABEL_PADDING_RATIO : 0));
-            final Paint paint = view.newDefaultLabelPaint();
-            paint.setTypeface(parentKey.selectTypeface(view.mKeyDrawParams));
-            paint.setTextSize(parentKey.selectMoreKeyTextSize(view.mKeyDrawParams));
+                final int minKeyWidth, final Resources res) {
+            final float padding =
+                    res.getDimension(R.dimen.more_keys_keyboard_key_horizontal_padding)
+                    + (parentKey.hasLabelsInMoreKeys() ? minKeyWidth * LABEL_PADDING_RATIO : 0.0f);
+            final Paint paint = view.newLabelPaint(parentKey);
             int maxWidth = minKeyWidth;
             for (final MoreKeySpec spec : parentKey.mMoreKeys) {
                 final String label = spec.mLabel;
                 // If the label is single letter, minKeyWidth is enough to hold the label.
                 if (label != null && StringUtils.codePointCount(label) > 1) {
-                    final int width = (int)view.getLabelWidth(label, paint) + padding;
-                    if (maxWidth < width) {
-                        maxWidth = width;
-                    }
+                    maxWidth = Math.max(maxWidth,
+                            (int)(TypefaceUtils.getLabelWidth(label, paint) + padding));
                 }
             }
             return maxWidth;
diff --git a/java/src/com/android/inputmethod/keyboard/MoreKeysKeyboardView.java b/java/src/com/android/inputmethod/keyboard/MoreKeysKeyboardView.java
index 0d42ab2..a356eb1 100644
--- a/java/src/com/android/inputmethod/keyboard/MoreKeysKeyboardView.java
+++ b/java/src/com/android/inputmethod/keyboard/MoreKeysKeyboardView.java
@@ -71,7 +71,7 @@
     public void setKeyboard(final Keyboard keyboard) {
         super.setKeyboard(keyboard);
         mKeyDetector.setKeyboard(keyboard, -getPaddingLeft(),
-                -getPaddingTop() + mVerticalCorrection);
+                -getPaddingTop() + getVerticalCorrection());
     }
 
     @Override
diff --git a/java/src/com/android/inputmethod/keyboard/TypefaceUtils.java b/java/src/com/android/inputmethod/keyboard/TypefaceUtils.java
new file mode 100644
index 0000000..6a54e11
--- /dev/null
+++ b/java/src/com/android/inputmethod/keyboard/TypefaceUtils.java
@@ -0,0 +1,91 @@
+/*
+ * Copyright (C) 2013 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.inputmethod.keyboard;
+
+import android.graphics.Paint;
+import android.graphics.Rect;
+import android.graphics.Typeface;
+import android.util.SparseArray;
+
+import com.android.inputmethod.latin.CollectionUtils;
+
+public final class TypefaceUtils {
+    private TypefaceUtils() {
+        // This utility class is not publicly instantiable.
+    }
+
+    // This sparse array caches key label text height in pixel indexed by key label text size.
+    private static final SparseArray<Float> sTextHeightCache = CollectionUtils.newSparseArray();
+    // Working variable for the following method.
+    private static final Rect sTextHeightBounds = new Rect();
+
+    public static float getCharHeight(final char[] referenceChar, final Paint paint) {
+        final int key = getCharGeometryCacheKey(referenceChar[0], paint);
+        synchronized (sTextHeightCache) {
+            final Float cachedValue = sTextHeightCache.get(key);
+            if (cachedValue != null) {
+                return cachedValue;
+            }
+
+            paint.getTextBounds(referenceChar, 0, 1, sTextHeightBounds);
+            final float height = sTextHeightBounds.height();
+            sTextHeightCache.put(key, height);
+            return height;
+        }
+    }
+
+    // This sparse array caches key label text width in pixel indexed by key label text size.
+    private static final SparseArray<Float> sTextWidthCache = CollectionUtils.newSparseArray();
+    // Working variable for the following method.
+    private static final Rect sTextWidthBounds = new Rect();
+
+    public static float getCharWidth(final char[] referenceChar, final Paint paint) {
+        final int key = getCharGeometryCacheKey(referenceChar[0], paint);
+        synchronized (sTextWidthCache) {
+            final Float cachedValue = sTextWidthCache.get(key);
+            if (cachedValue != null) {
+                return cachedValue;
+            }
+
+            paint.getTextBounds(referenceChar, 0, 1, sTextWidthBounds);
+            final float width = sTextWidthBounds.width();
+            sTextWidthCache.put(key, width);
+            return width;
+        }
+    }
+
+    private static int getCharGeometryCacheKey(final char referenceChar, final Paint paint) {
+        final int labelSize = (int)paint.getTextSize();
+        final Typeface face = paint.getTypeface();
+        final int codePointOffset = referenceChar << 15;
+        if (face == Typeface.DEFAULT) {
+            return codePointOffset + labelSize;
+        } else if (face == Typeface.DEFAULT_BOLD) {
+            return codePointOffset + labelSize + 0x1000;
+        } else if (face == Typeface.MONOSPACE) {
+            return codePointOffset + labelSize + 0x2000;
+        } else {
+            return codePointOffset + labelSize;
+        }
+    }
+
+    public static float getLabelWidth(final String label, final Paint paint) {
+        final Rect textBounds = new Rect();
+        paint.getTextBounds(label, 0, label.length(), textBounds);
+        return textBounds.width();
+    }
+}
diff --git a/java/src/com/android/inputmethod/latin/StringUtils.java b/java/src/com/android/inputmethod/latin/StringUtils.java
index 11ef60d..3ca209d 100644
--- a/java/src/com/android/inputmethod/latin/StringUtils.java
+++ b/java/src/com/android/inputmethod/latin/StringUtils.java
@@ -222,4 +222,75 @@
         if (1 == capsCount) return CAPITALIZE_FIRST;
         return (letterCount == capsCount ? CAPITALIZE_ALL : CAPITALIZE_NONE);
     }
+
+    public static boolean isIdenticalAfterUpcase(final String text) {
+        final int len = text.length();
+        for (int i = 0; i < len; i = text.offsetByCodePoints(i, 1)) {
+            final int codePoint = text.codePointAt(i);
+            if (Character.isLetter(codePoint) && !Character.isUpperCase(codePoint)) {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    public static boolean isIdenticalAfterDowncase(final String text) {
+        final int len = text.length();
+        for (int i = 0; i < len; i = text.offsetByCodePoints(i, 1)) {
+            final int codePoint = text.codePointAt(i);
+            if (Character.isLetter(codePoint) && !Character.isLowerCase(codePoint)) {
+                return false;
+            }
+        }
+        return true;
+    }
+
+    public static boolean isIdenticalAfterCapitalizeEachWord(final String text,
+            final String separators) {
+        boolean needCapsNext = true;
+        final int len = text.length();
+        for (int i = 0; i < len; i = text.offsetByCodePoints(i, 1)) {
+            final int codePoint = text.codePointAt(i);
+            if (Character.isLetter(codePoint)) {
+                if ((needCapsNext && !Character.isUpperCase(codePoint))
+                        || (!needCapsNext && !Character.isLowerCase(codePoint))) {
+                    return false;
+                }
+            }
+            // We need a capital letter next if this is a separator.
+            needCapsNext = (-1 != separators.indexOf(codePoint));
+        }
+        return true;
+    }
+
+    // TODO: like capitalizeFirst*, this does not work perfectly for Dutch because of the IJ digraph
+    // which should be capitalized together in *some* cases.
+    public static String capitalizeEachWord(final String text, final String separators,
+            final Locale locale) {
+        final StringBuilder builder = new StringBuilder();
+        boolean needCapsNext = true;
+        final int len = text.length();
+        for (int i = 0; i < len; i = text.offsetByCodePoints(i, 1)) {
+            final String nextChar = text.substring(i, text.offsetByCodePoints(i, 1));
+            if (needCapsNext) {
+                builder.append(nextChar.toUpperCase(locale));
+            } else {
+                builder.append(nextChar.toLowerCase(locale));
+            }
+            // We need a capital letter next if this is a separator.
+            needCapsNext = (-1 != separators.indexOf(nextChar.codePointAt(0)));
+        }
+        return builder.toString();
+    }
+
+    public static boolean containsAny(final String string, final String separators) {
+        final int len = separators.length();
+        for (int i = 0; i < len; i = separators.offsetByCodePoints(i, 1)) {
+            final int separator = separators.codePointAt(i);
+            if (-1 != string.indexOf(separator)) {
+                return true;
+            }
+        }
+        return false;
+    }
 }
diff --git a/java/src/com/android/inputmethod/latin/makedict/FusionDictionary.java b/java/src/com/android/inputmethod/latin/makedict/FusionDictionary.java
index e7c7e2b..17d2815 100644
--- a/java/src/com/android/inputmethod/latin/makedict/FusionDictionary.java
+++ b/java/src/com/android/inputmethod/latin/makedict/FusionDictionary.java
@@ -647,7 +647,7 @@
 
         if (index < codePoints.length) return null;
         if (!currentGroup.isTerminal()) return null;
-        if (DBG && !codePoints.equals(checker.toString())) return null;
+        if (DBG && !string.equals(checker.toString())) return null;
         return currentGroup;
     }
 
@@ -853,16 +853,19 @@
                 if (currentPos.pos.hasNext()) {
                     final CharGroup currentGroup = currentPos.pos.next();
                     currentPos.length = mCurrentString.length();
-                    for (int i : currentGroup.mChars)
+                    for (int i : currentGroup.mChars) {
                         mCurrentString.append(Character.toChars(i));
+                    }
                     if (null != currentGroup.mChildren) {
                         currentPos = new Position(currentGroup.mChildren.mData);
+                        currentPos.length = mCurrentString.length();
                         mPositions.addLast(currentPos);
                     }
-                    if (currentGroup.mFrequency >= 0)
+                    if (currentGroup.mFrequency >= 0) {
                         return new Word(mCurrentString.toString(), currentGroup.mFrequency,
                                 currentGroup.mShortcutTargets, currentGroup.mBigrams,
                                 currentGroup.mIsNotAWord, currentGroup.mIsBlacklistEntry);
+                    }
                 } else {
                     mPositions.removeLast();
                     currentPos = mPositions.getLast();
diff --git a/java/src/com/android/inputmethod/latin/spellcheck/SpellCheckerProximityInfo.java b/java/src/com/android/inputmethod/latin/spellcheck/SpellCheckerProximityInfo.java
index 2c18b6e..0c480ea 100644
--- a/java/src/com/android/inputmethod/latin/spellcheck/SpellCheckerProximityInfo.java
+++ b/java/src/com/android/inputmethod/latin/spellcheck/SpellCheckerProximityInfo.java
@@ -16,11 +16,10 @@
 
 package com.android.inputmethod.latin.spellcheck;
 
-import com.android.inputmethod.keyboard.ProximityInfo;
-import com.android.inputmethod.latin.CollectionUtils;
-import com.android.inputmethod.latin.Constants;
+import android.util.SparseIntArray;
 
-import java.util.TreeMap;
+import com.android.inputmethod.keyboard.ProximityInfo;
+import com.android.inputmethod.latin.Constants;
 
 public final class SpellCheckerProximityInfo extends ProximityInfo {
     public SpellCheckerProximityInfo(final int script) {
@@ -43,29 +42,14 @@
     public static final int NOT_A_COORDINATE_PAIR = -1;
 
     // Helper methods
-    static void buildProximityIndices(final int[] proximity,
-            final TreeMap<Integer, Integer> indices) {
-        for (int i = 0; i < proximity.length; i += ROW_SIZE) {
-            if (NUL != proximity[i]) indices.put(proximity[i], i / ROW_SIZE);
+    static void buildProximityIndices(final int[] proximity, final int rowSize,
+            final SparseIntArray indices) {
+        for (int i = 0; i < proximity.length; i += rowSize) {
+            if (NUL != proximity[i]) indices.put(proximity[i], i / rowSize);
         }
     }
 
-    static int computeIndex(final int characterCode,
-            final TreeMap<Integer, Integer> indices) {
-        final Integer result = indices.get(characterCode);
-        if (null == result) return NOT_AN_INDEX;
-        return result;
-    }
-
     private static final class Latin {
-        // This is a map from the code point to the index in the PROXIMITY array.
-        // At the time the native code to read the binary dictionary needs the proximity info be
-        // passed as a flat array spaced by MAX_PROXIMITY_CHARS_SIZE columns, one for each input
-        // character.
-        // Since we need to build such an array, we want to be able to search in our big proximity
-        // data quickly by character, and a map is probably the best way to do this.
-        private static final TreeMap<Integer, Integer> INDICES = CollectionUtils.newTreeMap();
-
         // The proximity here is the union of
         // - the proximity for a QWERTY keyboard.
         // - the proximity for an AZERTY keyboard.
@@ -125,17 +109,20 @@
             NUL, NUL, NUL, NUL, NUL, NUL, NUL, NUL, NUL, NUL, NUL, NUL, NUL, NUL, NUL, NUL,
         };
 
-        static {
-            buildProximityIndices(PROXIMITY, INDICES);
-        }
+        // This is a mapping array from the code point to the index in the PROXIMITY array.
+        // When we check the spelling of a word, we need to pass (x,y) coordinates to the native
+        // code for each letter of the word. These are most easily computed from the index in the
+        // PROXIMITY array. Since we'll need to do that very often, the index lookup from the code
+        // point needs to be as fast as possible, and a map is probably the best way to do this.
+        // To avoid unnecessary boxing conversion to Integer, here we use SparseIntArray.
+        static final SparseIntArray INDICES = new SparseIntArray(PROXIMITY.length / ROW_SIZE);
 
-        static int getIndexOf(int characterCode) {
-            return computeIndex(characterCode, INDICES);
+        static {
+            buildProximityIndices(PROXIMITY, ROW_SIZE, INDICES);
         }
     }
 
     private static final class Cyrillic {
-        private static final TreeMap<Integer, Integer> INDICES = CollectionUtils.newTreeMap();
         // TODO: The following table is solely based on the keyboard layout. Consult with Russian
         // speakers on commonly misspelled words/letters.
         /*
@@ -286,17 +273,14 @@
             NUL, NUL, NUL, NUL, NUL, NUL, NUL, NUL, NUL, NUL, NUL, NUL, NUL, NUL, NUL, NUL,
         };
 
-        static {
-            buildProximityIndices(PROXIMITY, INDICES);
-        }
+        static final SparseIntArray INDICES = new SparseIntArray(PROXIMITY.length / ROW_SIZE);
 
-        static int getIndexOf(int characterCode) {
-            return computeIndex(characterCode, INDICES);
+        static {
+            buildProximityIndices(PROXIMITY, ROW_SIZE, INDICES);
         }
     }
 
     private static final class Greek {
-        private static final TreeMap<Integer, Integer> INDICES = CollectionUtils.newTreeMap();
         // TODO: The following table is solely based on the keyboard layout. Consult with Greek
         // speakers on commonly misspelled words/letters.
         /*
@@ -427,12 +411,10 @@
             NUL, NUL, NUL, NUL, NUL, NUL, NUL, NUL, NUL, NUL, NUL, NUL, NUL, NUL, NUL, NUL,
         };
 
-        static {
-            buildProximityIndices(PROXIMITY, INDICES);
-        }
+        static final SparseIntArray INDICES = new SparseIntArray(PROXIMITY.length / ROW_SIZE);
 
-        static int getIndexOf(int characterCode) {
-            return computeIndex(characterCode, INDICES);
+        static {
+            buildProximityIndices(PROXIMITY, ROW_SIZE, INDICES);
         }
     }
 
@@ -452,11 +434,11 @@
     private static int getIndexOfCodeForScript(final int codePoint, final int script) {
         switch (script) {
         case AndroidSpellCheckerService.SCRIPT_LATIN:
-            return Latin.getIndexOf(codePoint);
+            return Latin.INDICES.get(codePoint, NOT_AN_INDEX);
         case AndroidSpellCheckerService.SCRIPT_CYRILLIC:
-            return Cyrillic.getIndexOf(codePoint);
+            return Cyrillic.INDICES.get(codePoint, NOT_AN_INDEX);
         case AndroidSpellCheckerService.SCRIPT_GREEK:
-            return Greek.getIndexOf(codePoint);
+            return Greek.INDICES.get(codePoint, NOT_AN_INDEX);
         default:
             throw new RuntimeException("Wrong script supplied: " + script);
         }
diff --git a/java/src/com/android/inputmethod/latin/suggestions/MoreSuggestions.java b/java/src/com/android/inputmethod/latin/suggestions/MoreSuggestions.java
index ed408bb..3037669 100644
--- a/java/src/com/android/inputmethod/latin/suggestions/MoreSuggestions.java
+++ b/java/src/com/android/inputmethod/latin/suggestions/MoreSuggestions.java
@@ -16,12 +16,14 @@
 
 package com.android.inputmethod.latin.suggestions;
 
+import android.content.Context;
 import android.content.res.Resources;
 import android.graphics.Paint;
 import android.graphics.drawable.Drawable;
 
 import com.android.inputmethod.keyboard.Key;
 import com.android.inputmethod.keyboard.Keyboard;
+import com.android.inputmethod.keyboard.TypefaceUtils;
 import com.android.inputmethod.keyboard.internal.KeyboardBuilder;
 import com.android.inputmethod.keyboard.internal.KeyboardIconsSet;
 import com.android.inputmethod.keyboard.internal.KeyboardParams;
@@ -50,16 +52,12 @@
             super();
         }
 
-        // TODO: Remove {@link MoreSuggestionsView} argument.
         public int layout(final SuggestedWords suggestions, final int fromPos, final int maxWidth,
-                final int minWidth, final int maxRow, final MoreSuggestionsView view) {
+                final int minWidth, final int maxRow, final Paint paint, final Resources res) {
             clearKeys();
-            final Resources res = view.getResources();
             mDivider = res.getDrawable(R.drawable.more_suggestions_divider);
             mDividerWidth = mDivider.getIntrinsicWidth();
-            final int padding = (int) res.getDimension(
-                    R.dimen.more_suggestions_key_horizontal_padding);
-            final Paint paint = view.newDefaultLabelPaint();
+            final float padding = res.getDimension(R.dimen.more_suggestions_key_horizontal_padding);
 
             int row = 0;
             int pos = fromPos, rowStartPos = fromPos;
@@ -67,7 +65,7 @@
             while (pos < size) {
                 final String word = suggestions.getWord(pos);
                 // TODO: Should take care of text x-scaling.
-                mWidths[pos] = (int)view.getLabelWidth(word, paint) + padding;
+                mWidths[pos] = (int)(TypefaceUtils.getLabelWidth(word, paint) + padding);
                 final int numColumn = pos - rowStartPos + 1;
                 final int columnWidth =
                         (maxWidth - mDividerWidth * (numColumn - 1)) / numColumn;
@@ -169,8 +167,8 @@
         private int mFromPos;
         private int mToPos;
 
-        public Builder(final MoreSuggestionsView paneView) {
-            super(paneView.getContext(), new MoreSuggestionsParam());
+        public Builder(final Context context, final MoreSuggestionsView paneView) {
+            super(context, new MoreSuggestionsParam());
             mPaneView = paneView;
         }
 
@@ -183,7 +181,7 @@
 
             mPaneView.updateKeyboardGeometry(mParams.mDefaultRowHeight);
             final int count = mParams.layout(suggestions, fromPos, maxWidth, minWidth, maxRow,
-                    mPaneView);
+                    mPaneView.newLabelPaint(null /* key */), mResources);
             mFromPos = fromPos;
             mToPos = fromPos + count;
             mSuggestions = suggestions;
diff --git a/java/src/com/android/inputmethod/latin/suggestions/MoreSuggestionsView.java b/java/src/com/android/inputmethod/latin/suggestions/MoreSuggestionsView.java
index 438820d..94715cd 100644
--- a/java/src/com/android/inputmethod/latin/suggestions/MoreSuggestionsView.java
+++ b/java/src/com/android/inputmethod/latin/suggestions/MoreSuggestionsView.java
@@ -43,7 +43,7 @@
     }
 
     public void updateKeyboardGeometry(final int keyHeight) {
-        mKeyDrawParams.updateParams(keyHeight, mKeyVisualAttributes);
+        updateKeyDrawParams(keyHeight);
     }
 
     @Override
diff --git a/java/src/com/android/inputmethod/latin/suggestions/SuggestionStripView.java b/java/src/com/android/inputmethod/latin/suggestions/SuggestionStripView.java
index eeaf828..4ef36fa 100644
--- a/java/src/com/android/inputmethod/latin/suggestions/SuggestionStripView.java
+++ b/java/src/com/android/inputmethod/latin/suggestions/SuggestionStripView.java
@@ -596,7 +596,7 @@
         mMoreSuggestionsContainer = inflater.inflate(R.layout.more_suggestions, null);
         mMoreSuggestionsView = (MoreSuggestionsView)mMoreSuggestionsContainer
                 .findViewById(R.id.more_suggestions_view);
-        mMoreSuggestionsBuilder = new MoreSuggestions.Builder(mMoreSuggestionsView);
+        mMoreSuggestionsBuilder = new MoreSuggestions.Builder(context, mMoreSuggestionsView);
 
         final Resources res = context.getResources();
         mMoreSuggestionsModalTolerance = res.getDimensionPixelOffset(
diff --git a/java/src/com/android/inputmethod/research/MotionEventReader.java b/java/src/com/android/inputmethod/research/MotionEventReader.java
index e1cc2da..fbfd9b5 100644
--- a/java/src/com/android/inputmethod/research/MotionEventReader.java
+++ b/java/src/com/android/inputmethod/research/MotionEventReader.java
@@ -22,6 +22,7 @@
 import android.view.MotionEvent.PointerCoords;
 import android.view.MotionEvent.PointerProperties;
 
+import com.android.inputmethod.annotations.UsedForTesting;
 import com.android.inputmethod.latin.define.ProductionFlag;
 
 import java.io.BufferedReader;
@@ -64,6 +65,7 @@
         return replayData;
     }
 
+    @UsedForTesting
     static class ReplayData {
         final ArrayList<Integer> mActions = new ArrayList<Integer>();
         final ArrayList<PointerProperties[]> mPointerPropertiesArrays
@@ -134,6 +136,7 @@
      * },
      * </pre>
      */
+    @UsedForTesting
     /* package for test */ void readLogStatement(final JsonReader jsonReader,
             final ReplayData replayData) throws IOException {
         String logStatementType = null;
diff --git a/native/jni/src/defines.h b/native/jni/src/defines.h
index a456912..a7b023a 100644
--- a/native/jni/src/defines.h
+++ b/native/jni/src/defines.h
@@ -216,6 +216,7 @@
 #define DEBUG_DOUBLE_LETTER false
 #define DEBUG_CACHE false
 #define DEBUG_DUMP_ERROR false
+#define DEBUG_EVALUATE_MOST_PROBABLE_STRING false
 
 #ifdef FLAG_FULL_DBG
 #define DEBUG_GEO_FULL true
@@ -241,6 +242,7 @@
 #define DEBUG_DOUBLE_LETTER false
 #define DEBUG_CACHE false
 #define DEBUG_DUMP_ERROR false
+#define DEBUG_EVALUATE_MOST_PROBABLE_STRING false
 
 #define DEBUG_GEO_FULL false
 
diff --git a/native/jni/src/digraph_utils.cpp b/native/jni/src/digraph_utils.cpp
index 8781c50..6a1ab02 100644
--- a/native/jni/src/digraph_utils.cpp
+++ b/native/jni/src/digraph_utils.cpp
@@ -27,39 +27,47 @@
 const DigraphUtils::digraph_t DigraphUtils::FRENCH_LIGATURES_DIGRAPHS[] =
         { { 'a', 'e', 0x00E6 }, // U+00E6 : LATIN SMALL LETTER AE
         { 'o', 'e', 0x0153 } }; // U+0153 : LATIN SMALL LIGATURE OE
+const DigraphUtils::DigraphType DigraphUtils::USED_DIGRAPH_TYPES[] =
+        { DIGRAPH_TYPE_GERMAN_UMLAUT, DIGRAPH_TYPE_FRENCH_LIGATURES };
 
 /* static */ bool DigraphUtils::hasDigraphForCodePoint(
         const int dictFlags, const int compositeGlyphCodePoint) {
-    if (DigraphUtils::getDigraphForCodePoint(dictFlags, compositeGlyphCodePoint)) {
+    const DigraphUtils::DigraphType digraphType = getDigraphTypeForDictionary(dictFlags);
+    if (DigraphUtils::getDigraphForDigraphTypeAndCodePoint(digraphType, compositeGlyphCodePoint)) {
         return true;
     }
     return false;
 }
 
-// Retrieves the set of all digraphs associated with the given dictionary.
-// Returns the size of the digraph array, or 0 if none exist.
-/* static */ int DigraphUtils::getAllDigraphsForDictionaryAndReturnSize(
-        const int dictFlags, const DigraphUtils::digraph_t **digraphs) {
+// Returns the digraph type associated with the given dictionary.
+/* static */ DigraphUtils::DigraphType DigraphUtils::getDigraphTypeForDictionary(
+        const int dictFlags) {
     if (BinaryFormat::REQUIRES_GERMAN_UMLAUT_PROCESSING & dictFlags) {
-        *digraphs = DigraphUtils::GERMAN_UMLAUT_DIGRAPHS;
-        return NELEMS(DigraphUtils::GERMAN_UMLAUT_DIGRAPHS);
+        return DIGRAPH_TYPE_GERMAN_UMLAUT;
     }
     if (BinaryFormat::REQUIRES_FRENCH_LIGATURES_PROCESSING & dictFlags) {
-        *digraphs = DigraphUtils::FRENCH_LIGATURES_DIGRAPHS;
-        return NELEMS(DigraphUtils::FRENCH_LIGATURES_DIGRAPHS);
+        return DIGRAPH_TYPE_FRENCH_LIGATURES;
     }
-    return 0;
+    return DIGRAPH_TYPE_NONE;
+}
+
+// Retrieves the set of all digraphs associated with the given dictionary flags.
+// Returns the size of the digraph array, or 0 if none exist.
+/* static */ int DigraphUtils::getAllDigraphsForDictionaryAndReturnSize(
+        const int dictFlags, const DigraphUtils::digraph_t **const digraphs) {
+    const DigraphUtils::DigraphType digraphType = getDigraphTypeForDictionary(dictFlags);
+    return getAllDigraphsForDigraphTypeAndReturnSize(digraphType, digraphs);
 }
 
 // Returns the digraph codepoint for the given composite glyph codepoint and digraph codepoint index
 // (which specifies the first or second codepoint in the digraph).
-/* static */ int DigraphUtils::getDigraphCodePointForIndex(const int dictFlags,
-        const int compositeGlyphCodePoint, const DigraphCodePointIndex digraphCodePointIndex) {
+/* static */ int DigraphUtils::getDigraphCodePointForIndex(const int compositeGlyphCodePoint,
+        const DigraphCodePointIndex digraphCodePointIndex) {
     if (digraphCodePointIndex == NOT_A_DIGRAPH_INDEX) {
         return NOT_A_CODE_POINT;
     }
-    const DigraphUtils::digraph_t *digraph =
-            DigraphUtils::getDigraphForCodePoint(dictFlags, compositeGlyphCodePoint);
+    const DigraphUtils::digraph_t *const digraph =
+            DigraphUtils::getDigraphForCodePoint(compositeGlyphCodePoint);
     if (!digraph) {
         return NOT_A_CODE_POINT;
     }
@@ -72,16 +80,48 @@
     return NOT_A_CODE_POINT;
 }
 
+// Retrieves the set of all digraphs associated with the given digraph type.
+// Returns the size of the digraph array, or 0 if none exist.
+/* static */ int DigraphUtils::getAllDigraphsForDigraphTypeAndReturnSize(
+        const DigraphUtils::DigraphType digraphType,
+        const DigraphUtils::digraph_t **const digraphs) {
+    if (digraphType == DigraphUtils::DIGRAPH_TYPE_GERMAN_UMLAUT) {
+        *digraphs = GERMAN_UMLAUT_DIGRAPHS;
+        return NELEMS(GERMAN_UMLAUT_DIGRAPHS);
+    }
+    if (digraphType == DIGRAPH_TYPE_FRENCH_LIGATURES) {
+        *digraphs = FRENCH_LIGATURES_DIGRAPHS;
+        return NELEMS(FRENCH_LIGATURES_DIGRAPHS);
+    }
+    return 0;
+}
+
 /**
  * Returns the digraph for the input composite glyph codepoint, or 0 if none exists.
- * dictFlags: the dictionary flags needed to determine which digraphs are supported.
  * compositeGlyphCodePoint: the method returns the digraph corresponding to this codepoint.
  */
 /* static */ const DigraphUtils::digraph_t *DigraphUtils::getDigraphForCodePoint(
-        const int dictFlags, const int compositeGlyphCodePoint) {
+        const int compositeGlyphCodePoint) {
+    for (size_t i = 0; i < NELEMS(USED_DIGRAPH_TYPES); i++) {
+        const DigraphUtils::digraph_t *const digraph = getDigraphForDigraphTypeAndCodePoint(
+                USED_DIGRAPH_TYPES[i], compositeGlyphCodePoint);
+        if (digraph) {
+            return digraph;
+        }
+    }
+    return 0;
+}
+
+/**
+ * Returns the digraph for the input composite glyph codepoint, or 0 if none exists.
+ * digraphType: the type of digraphs supported.
+ * compositeGlyphCodePoint: the method returns the digraph corresponding to this codepoint.
+ */
+/* static */ const DigraphUtils::digraph_t *DigraphUtils::getDigraphForDigraphTypeAndCodePoint(
+        const DigraphUtils::DigraphType digraphType, const int compositeGlyphCodePoint) {
     const DigraphUtils::digraph_t *digraphs = 0;
     const int digraphsSize =
-            DigraphUtils::getAllDigraphsForDictionaryAndReturnSize(dictFlags, &digraphs);
+            DigraphUtils::getAllDigraphsForDictionaryAndReturnSize(digraphType, &digraphs);
     for (int i = 0; i < digraphsSize; i++) {
         if (digraphs[i].compositeGlyph == compositeGlyphCodePoint) {
             return &digraphs[i];
diff --git a/native/jni/src/digraph_utils.h b/native/jni/src/digraph_utils.h
index 6e364b6..9443522 100644
--- a/native/jni/src/digraph_utils.h
+++ b/native/jni/src/digraph_utils.h
@@ -27,21 +27,34 @@
         SECOND_DIGRAPH_CODEPOINT
     } DigraphCodePointIndex;
 
+    typedef enum {
+        DIGRAPH_TYPE_NONE,
+        DIGRAPH_TYPE_GERMAN_UMLAUT,
+        DIGRAPH_TYPE_FRENCH_LIGATURES
+    } DigraphType;
+
     typedef struct { int first; int second; int compositeGlyph; } digraph_t;
 
     static bool hasDigraphForCodePoint(const int dictFlags, const int compositeGlyphCodePoint);
     static int getAllDigraphsForDictionaryAndReturnSize(
-            const int dictFlags, const digraph_t **digraphs);
+            const int dictFlags, const digraph_t **const digraphs);
     static int getDigraphCodePointForIndex(const int dictFlags, const int compositeGlyphCodePoint,
             const DigraphCodePointIndex digraphCodePointIndex);
+    static int getDigraphCodePointForIndex(const int compositeGlyphCodePoint,
+            const DigraphCodePointIndex digraphCodePointIndex);
 
  private:
     DISALLOW_IMPLICIT_CONSTRUCTORS(DigraphUtils);
-    static const digraph_t *getDigraphForCodePoint(
-            const int dictFlags, const int compositeGlyphCodePoint);
+    static DigraphType getDigraphTypeForDictionary(const int dictFlags);
+    static int getAllDigraphsForDigraphTypeAndReturnSize(
+            const DigraphType digraphType, const digraph_t **const digraphs);
+    static const digraph_t *getDigraphForCodePoint(const int compositeGlyphCodePoint);
+    static const digraph_t *getDigraphForDigraphTypeAndCodePoint(
+            const DigraphType digraphType, const int compositeGlyphCodePoint);
 
     static const digraph_t GERMAN_UMLAUT_DIGRAPHS[];
     static const digraph_t FRENCH_LIGATURES_DIGRAPHS[];
+    static const DigraphType USED_DIGRAPH_TYPES[];
 };
 } // namespace latinime
 #endif // DIGRAPH_UTILS_H
diff --git a/native/jni/src/suggest/core/dicnode/dic_node.h b/native/jni/src/suggest/core/dicnode/dic_node.h
index cde7b99..32faae5 100644
--- a/native/jni/src/suggest/core/dicnode/dic_node.h
+++ b/native/jni/src/suggest/core/dicnode/dic_node.h
@@ -23,6 +23,7 @@
 #include "dic_node_profiler.h"
 #include "dic_node_properties.h"
 #include "dic_node_release_listener.h"
+#include "digraph_utils.h"
 
 #if DEBUG_DICT
 #define LOGI_SHOW_ADD_COST_PROP \
@@ -399,8 +400,15 @@
     // TODO: Remove     //
     //////////////////////
     // TODO: Remove once touch path is merged into ProximityInfoState
+    // Note: Returned codepoint may be a digraph codepoint if the node is in a composite glyph.
     int getNodeCodePoint() const {
-        return mDicNodeProperties.getNodeCodePoint();
+        const int codePoint = mDicNodeProperties.getNodeCodePoint();
+        const DigraphUtils::DigraphCodePointIndex digraphIndex =
+                mDicNodeState.mDicNodeStateScoring.getDigraphIndex();
+        if (digraphIndex == DigraphUtils::NOT_A_DIGRAPH_INDEX) {
+            return codePoint;
+        }
+        return DigraphUtils::getDigraphCodePointForIndex(codePoint, digraphIndex);
     }
 
     ////////////////////////////////
@@ -452,6 +460,15 @@
         mDicNodeState.mDicNodeStateScoring.setDoubleLetterLevel(doubleLetterLevel);
     }
 
+    bool isInDigraph() const {
+        return mDicNodeState.mDicNodeStateScoring.getDigraphIndex()
+                != DigraphUtils::NOT_A_DIGRAPH_INDEX;
+    }
+
+    void advanceDigraphIndex() {
+        mDicNodeState.mDicNodeStateScoring.advanceDigraphIndex();
+    }
+
     uint8_t getFlags() const {
         return mDicNodeProperties.getFlags();
     }
diff --git a/native/jni/src/suggest/core/dicnode/dic_node_state_scoring.h b/native/jni/src/suggest/core/dicnode/dic_node_state_scoring.h
index 8e81632..8902d31 100644
--- a/native/jni/src/suggest/core/dicnode/dic_node_state_scoring.h
+++ b/native/jni/src/suggest/core/dicnode/dic_node_state_scoring.h
@@ -20,6 +20,7 @@
 #include <stdint.h>
 
 #include "defines.h"
+#include "digraph_utils.h"
 
 namespace latinime {
 
@@ -27,6 +28,7 @@
  public:
     AK_FORCE_INLINE DicNodeStateScoring()
             : mDoubleLetterLevel(NOT_A_DOUBLE_LETTER),
+              mDigraphIndex(DigraphUtils::NOT_A_DIGRAPH_INDEX),
               mEditCorrectionCount(0), mProximityCorrectionCount(0),
               mNormalizedCompoundDistance(0.0f), mSpatialDistance(0.0f), mLanguageDistance(0.0f),
               mTotalPrevWordsLanguageCost(0.0f), mRawLength(0.0f) {
@@ -43,6 +45,7 @@
         mTotalPrevWordsLanguageCost = 0.0f;
         mRawLength = 0.0f;
         mDoubleLetterLevel = NOT_A_DOUBLE_LETTER;
+        mDigraphIndex = DigraphUtils::NOT_A_DIGRAPH_INDEX;
     }
 
     AK_FORCE_INLINE void init(const DicNodeStateScoring *const scoring) {
@@ -54,6 +57,7 @@
         mTotalPrevWordsLanguageCost = scoring->mTotalPrevWordsLanguageCost;
         mRawLength = scoring->mRawLength;
         mDoubleLetterLevel = scoring->mDoubleLetterLevel;
+        mDigraphIndex = scoring->mDigraphIndex;
     }
 
     void addCost(const float spatialCost, const float languageCost, const bool doNormalization,
@@ -126,6 +130,24 @@
         }
     }
 
+    DigraphUtils::DigraphCodePointIndex getDigraphIndex() const {
+        return mDigraphIndex;
+    }
+
+    void advanceDigraphIndex() {
+        switch(mDigraphIndex) {
+            case DigraphUtils::NOT_A_DIGRAPH_INDEX:
+                mDigraphIndex = DigraphUtils::FIRST_DIGRAPH_CODEPOINT;
+                break;
+            case DigraphUtils::FIRST_DIGRAPH_CODEPOINT:
+                mDigraphIndex = DigraphUtils::SECOND_DIGRAPH_CODEPOINT;
+                break;
+            case DigraphUtils::SECOND_DIGRAPH_CODEPOINT:
+                mDigraphIndex = DigraphUtils::NOT_A_DIGRAPH_INDEX;
+                break;
+        }
+    }
+
     float getTotalPrevWordsLanguageCost() const {
         return mTotalPrevWordsLanguageCost;
     }
@@ -135,6 +157,7 @@
     // Use a default copy constructor and an assign operator because shallow copies are ok
     // for this class
     DoubleLetterLevel mDoubleLetterLevel;
+    DigraphUtils::DigraphCodePointIndex mDigraphIndex;
 
     int16_t mEditCorrectionCount;
     int16_t mProximityCorrectionCount;
diff --git a/native/jni/src/suggest/core/suggest.cpp b/native/jni/src/suggest/core/suggest.cpp
index 764c372..67d351f 100644
--- a/native/jni/src/suggest/core/suggest.cpp
+++ b/native/jni/src/suggest/core/suggest.cpp
@@ -18,6 +18,7 @@
 
 #include "char_utils.h"
 #include "dictionary.h"
+#include "digraph_utils.h"
 #include "proximity_info.h"
 #include "suggest/core/dicnode/dic_node.h"
 #include "suggest/core/dicnode/dic_node_priority_queue.h"
@@ -123,8 +124,12 @@
  */
 int Suggest::outputSuggestions(DicTraverseSession *traverseSession, int *frequencies,
         int *outputCodePoints, int *spaceIndices, int *outputTypes) const {
+#if DEBUG_EVALUATE_MOST_PROBABLE_STRING
+    const int terminalSize = 0;
+#else
     const int terminalSize = min(MAX_RESULTS,
             static_cast<int>(traverseSession->getDicTraverseCache()->terminalSize()));
+#endif
     DicNode terminals[MAX_RESULTS]; // Avoiding non-POD variable length array
 
     for (int index = terminalSize - 1; index >= 0; --index) {
@@ -221,7 +226,7 @@
 void Suggest::expandCurrentDicNodes(DicTraverseSession *traverseSession) const {
     const int inputSize = traverseSession->getInputSize();
     DicNodeVector childDicNodes(TRAVERSAL->getDefaultExpandDicNodeSize());
-    DicNode omissionDicNode;
+    DicNode correctionDicNode;
 
     // TODO: Find more efficient caching
     const bool shouldDepthLevelCache = TRAVERSAL->shouldDepthLevelCache(traverseSession);
@@ -257,7 +262,10 @@
             dicNode.setCached();
         }
 
-        if (isLookAheadCorrection) {
+        if (dicNode.isInDigraph()) {
+            // Finish digraph handling if the node is in the middle of a digraph expansion.
+            processDicNodeAsDigraph(traverseSession, &dicNode);
+        } else if (isLookAheadCorrection) {
             // The algorithm maintains a small set of "deferred" nodes that have not consumed the
             // latest touch point yet. These are needed to apply look-ahead correction operations
             // that require special handling of the latest touch point. For example, with insertions
@@ -291,12 +299,18 @@
                     processDicNodeAsMatch(traverseSession, childDicNode);
                     continue;
                 }
+                if (DigraphUtils::hasDigraphForCodePoint(traverseSession->getDictFlags(),
+                        childDicNode->getNodeCodePoint())) {
+                    correctionDicNode.initByCopy(childDicNode);
+                    correctionDicNode.advanceDigraphIndex();
+                    processDicNodeAsDigraph(traverseSession, &correctionDicNode);
+                }
                 if (allowsErrorCorrections
                         && TRAVERSAL->isOmission(traverseSession, &dicNode, childDicNode)) {
                     // TODO: (Gesture) Change weight between omission and substitution errors
                     // TODO: (Gesture) Terminal node should not be handled as omission
-                    omissionDicNode.initByCopy(childDicNode);
-                    processDicNodeAsOmission(traverseSession, &omissionDicNode);
+                    correctionDicNode.initByCopy(childDicNode);
+                    processDicNodeAsOmission(traverseSession, &correctionDicNode);
                 }
                 const ProximityType proximityType = TRAVERSAL->getProximityType(
                         traverseSession, &dicNode, childDicNode);
@@ -400,6 +414,16 @@
     processExpandedDicNode(traverseSession, childDicNode);
 }
 
+// Process the node codepoint as a digraph. This means that composite glyphs like the German
+// u-umlaut is expanded to the transliteration "ue". Note that this happens in parallel with
+// the normal non-digraph traversal, so both "uber" and "ueber" can be corrected to "[u-umlaut]ber".
+void Suggest::processDicNodeAsDigraph(DicTraverseSession *traverseSession,
+        DicNode *childDicNode) const {
+    weightChildNode(traverseSession, childDicNode);
+    childDicNode->advanceDigraphIndex();
+    processExpandedDicNode(traverseSession, childDicNode);
+}
+
 /**
  * Handle the dicNode as an omission error (e.g., ths => this). Skip the current letter and consider
  * matches for all possible next letters. Note that just skipping the current letter without any
diff --git a/native/jni/src/suggest/core/suggest.h b/native/jni/src/suggest/core/suggest.h
index 6c09b94..136c4e5 100644
--- a/native/jni/src/suggest/core/suggest.h
+++ b/native/jni/src/suggest/core/suggest.h
@@ -64,6 +64,7 @@
     void generateFeatures(
             DicTraverseSession *traverseSession, DicNode *dicNode, float *features) const;
     void processDicNodeAsOmission(DicTraverseSession *traverseSession, DicNode *dicNode) const;
+    void processDicNodeAsDigraph(DicTraverseSession *traverseSession, DicNode *dicNode) const;
     void processDicNodeAsTransposition(DicTraverseSession *traverseSession,
             DicNode *dicNode) const;
     void processDicNodeAsInsertion(DicTraverseSession *traverseSession, DicNode *dicNode) const;
diff --git a/tests/src/com/android/inputmethod/latin/StringUtilsTests.java b/tests/src/com/android/inputmethod/latin/StringUtilsTests.java
index b6a05e9..136faff 100644
--- a/tests/src/com/android/inputmethod/latin/StringUtilsTests.java
+++ b/tests/src/com/android/inputmethod/latin/StringUtilsTests.java
@@ -154,4 +154,83 @@
         assertEquals(StringUtils.CAPITALIZE_NONE,
                 StringUtils.getCapitalizationType(""));
     }
+
+    public void testIsIdenticalAfterUpcaseIsIdenticalAfterDowncase() {
+        assertFalse(StringUtils.isIdenticalAfterUpcase("capitalize"));
+        assertTrue(StringUtils.isIdenticalAfterDowncase("capitalize"));
+        assertFalse(StringUtils.isIdenticalAfterUpcase("cApITalize"));
+        assertFalse(StringUtils.isIdenticalAfterDowncase("cApITalize"));
+        assertFalse(StringUtils.isIdenticalAfterUpcase("capitalizE"));
+        assertFalse(StringUtils.isIdenticalAfterDowncase("capitalizE"));
+        assertFalse(StringUtils.isIdenticalAfterUpcase("__c a piu$@tali56ze"));
+        assertTrue(StringUtils.isIdenticalAfterDowncase("__c a piu$@tali56ze"));
+        assertFalse(StringUtils.isIdenticalAfterUpcase("A__c a piu$@tali56ze"));
+        assertFalse(StringUtils.isIdenticalAfterDowncase("A__c a piu$@tali56ze"));
+        assertFalse(StringUtils.isIdenticalAfterUpcase("Capitalize"));
+        assertFalse(StringUtils.isIdenticalAfterDowncase("Capitalize"));
+        assertFalse(StringUtils.isIdenticalAfterUpcase("     Capitalize"));
+        assertFalse(StringUtils.isIdenticalAfterDowncase("     Capitalize"));
+        assertTrue(StringUtils.isIdenticalAfterUpcase("CAPITALIZE"));
+        assertFalse(StringUtils.isIdenticalAfterDowncase("CAPITALIZE"));
+        assertTrue(StringUtils.isIdenticalAfterUpcase("  PI26LIE"));
+        assertFalse(StringUtils.isIdenticalAfterDowncase("  PI26LIE"));
+        assertTrue(StringUtils.isIdenticalAfterUpcase(""));
+        assertTrue(StringUtils.isIdenticalAfterDowncase(""));
+    }
+
+    private void checkCapitalize(final String src, final String dst, final String separators,
+            final Locale locale) {
+        assertEquals(dst, StringUtils.capitalizeEachWord(src, separators, locale));
+        assert(src.equals(dst)
+                == StringUtils.isIdenticalAfterCapitalizeEachWord(src, separators));
+    }
+
+    public void testCapitalizeEachWord() {
+        checkCapitalize("", "", " ", Locale.ENGLISH);
+        checkCapitalize("test", "Test", " ", Locale.ENGLISH);
+        checkCapitalize("    test", "    Test", " ", Locale.ENGLISH);
+        checkCapitalize("Test", "Test", " ", Locale.ENGLISH);
+        checkCapitalize("    Test", "    Test", " ", Locale.ENGLISH);
+        checkCapitalize(".Test", ".test", " ", Locale.ENGLISH);
+        checkCapitalize(".Test", ".Test", " .", Locale.ENGLISH);
+        checkCapitalize(".Test", ".Test", ". ", Locale.ENGLISH);
+        checkCapitalize("test and retest", "Test And Retest", " .", Locale.ENGLISH);
+        checkCapitalize("Test and retest", "Test And Retest", " .", Locale.ENGLISH);
+        checkCapitalize("Test And Retest", "Test And Retest", " .", Locale.ENGLISH);
+        checkCapitalize("Test And.Retest  ", "Test And.Retest  ", " .", Locale.ENGLISH);
+        checkCapitalize("Test And.retest  ", "Test And.Retest  ", " .", Locale.ENGLISH);
+        checkCapitalize("Test And.retest  ", "Test And.retest  ", " ", Locale.ENGLISH);
+        checkCapitalize("Test And.Retest  ", "Test And.retest  ", " ", Locale.ENGLISH);
+        checkCapitalize("test and ietest", "Test And İetest", " .", new Locale("tr"));
+        checkCapitalize("test and ietest", "Test And Ietest", " .", Locale.ENGLISH);
+        checkCapitalize("Test&Retest", "Test&Retest", " \n.!?*()&", Locale.ENGLISH);
+        checkCapitalize("Test&retest", "Test&Retest", " \n.!?*()&", Locale.ENGLISH);
+        checkCapitalize("test&Retest", "Test&Retest", " \n.!?*()&", Locale.ENGLISH);
+        checkCapitalize("rest\nrecreation! And in the end...",
+                "Rest\nRecreation! And In The End...", " \n.!?*,();&", Locale.ENGLISH);
+        checkCapitalize("lorem ipsum dolor sit amet", "Lorem Ipsum Dolor Sit Amet",
+                " \n.,!?*()&;", Locale.ENGLISH);
+        checkCapitalize("Lorem!Ipsum (Dolor) Sit * Amet", "Lorem!Ipsum (Dolor) Sit * Amet",
+                " \n,.;!?*()&", Locale.ENGLISH);
+        checkCapitalize("Lorem!Ipsum (dolor) Sit * Amet", "Lorem!Ipsum (Dolor) Sit * Amet",
+                " \n,.;!?*()&", Locale.ENGLISH);
+    }
+
+    public void testContainsAny() {
+        assertFalse(StringUtils.containsAny("", " "));
+        assertFalse(StringUtils.containsAny("test and retest", ""));
+        assertTrue(StringUtils.containsAny("test and retest", "x3iq o"));
+        assertTrue(StringUtils.containsAny("test and retest", "x3iqo "));
+        assertTrue(StringUtils.containsAny("test and retest", " x3iqo"));
+        assertFalse(StringUtils.containsAny("test and retest", "x3iqo"));
+        assertTrue(StringUtils.containsAny("test and retest", "tse "));
+        assertTrue(StringUtils.containsAny("test and retest.", ".?()"));
+        assertFalse(StringUtils.containsAny("test and retest", ".?()"));
+        // Surrogate pair
+        assertTrue(StringUtils.containsAny("test and \uD861\uDED7 retest.", "\uD861\uDED7"));
+        // Ill-formed string
+        assertFalse(StringUtils.containsAny("test and \uD861 retest.", "\uD861\uDED7"));
+        // Ill-formed string
+        assertFalse(StringUtils.containsAny("test and \uDED7 retest.", "\uD861\uDED7"));
+    }
 }