Implement compareStrictly() using phone_number_compare() written in C.

As per several discussions, we stick to the default behavior now.
In stead, we provide compareStrictly() as a hidden method, so that some
internal components are able to use the method if needed.

Since these are static methods, they cannot refer to the configuration files,
whose values can be obtained only via Resources object.

Please make callers' side if you want to use strict version of compare().

Internal issue number: 1892808

1 files changed, 492 insertions, 120 deletions

diff --git a/telephony/java/android/telephony/PhoneNumberUtils.java b/telephony/java/android/telephony/PhoneNumberUtils.java
index 2672c6d..2d8afb7 100644
--- a/telephony/java/android/telephony/PhoneNumberUtils.java
+++ b/telephony/java/android/telephony/PhoneNumberUtils.java
@@ -111,6 +111,11 @@ public class PhoneNumberUtils
         return c == PAUSE || c == WAIT;
     }
 
+    /** Returns true if ch is not dialable or alpha char */
+    private static boolean isSeparator(char ch) {
+        return !isDialable(ch) && !(('a' <= ch && ch <= 'z') || ('A' <= ch && ch <= 'Z'));
+    }
+
     /** Extracts the phone number from an Intent.
      *
      * @param intent the intent to get the number of
@@ -293,6 +298,21 @@ public class PhoneNumberUtils
     }
 
     /**
+     * Compare phone numbers a and b, return true if they're identical enough for caller ID purposes.
+     */
+    public static boolean compare(String a, String b) {
+        // We've used loose comparation at least Eclair, which may change in the future.
+        return compare(a, b, false);
+    }
+
+    /**
+     * @hide only for testing.
+     */
+    public static boolean compare(String a, String b, boolean useStrictComparation) {
+        return (useStrictComparation ? compareStrictly(a, b) : compareLoosely(a, b));
+    }
+
+    /**
      * Compare phone numbers a and b, return true if they're identical
      * enough for caller ID purposes.
      *
@@ -301,10 +321,13 @@ public class PhoneNumberUtils
      * - handles common trunk prefixes and international prefixes
      *   (basically, everything except the Russian trunk prefix)
      *
-     * Tolerates nulls
+     * Note that this method does not return false even when the two phone numbers
+     * are not exactly same; rather; we can call this method "similar()", not "equals()".
+     *
+     * @hide
      */
     public static boolean
-    compare(String a, String b) {
+    compareLoosely(String a, String b) {
         int ia, ib;
         int matched;
 
@@ -391,6 +414,160 @@ public class PhoneNumberUtils
     }
 
     /**
+     * @hide
+     */
+    public static boolean
+    compareStrictly(String a, String b) {
+        return compareStrictly(a, b, true);
+    }
+
+    /**
+     * @hide
+     */
+    public static boolean
+    compareStrictly(String a, String b, boolean acceptInvalidCCCPrefix) {
+        if (a == null || b == null) {
+            return a == b;
+        } else if (a.length() == 0 && b.length() == 0) {
+            return false;
+        }
+
+        int forwardIndexA = 0;
+        int forwardIndexB = 0;
+
+        CountryCallingCodeAndNewIndex cccA =
+            tryGetCountryCallingCodeAndNewIndex(a, acceptInvalidCCCPrefix);
+        CountryCallingCodeAndNewIndex cccB =
+            tryGetCountryCallingCodeAndNewIndex(b, acceptInvalidCCCPrefix);
+        boolean bothHasCountryCallingCode = false;
+        boolean okToIgnorePrefix = true;
+        boolean trunkPrefixIsOmittedA = false;
+        boolean trunkPrefixIsOmittedB = false;
+        if (cccA != null && cccB != null) {
+            if (cccA.countryCallingCode != cccB.countryCallingCode) {
+                // Different Country Calling Code. Must be different phone number.
+                return false;
+            }
+            // When both have ccc, do not ignore trunk prefix. Without this,
+            // "+81123123" becomes same as "+810123123" (+81 == Japan)
+            okToIgnorePrefix = false;
+            bothHasCountryCallingCode = true;
+            forwardIndexA = cccA.newIndex;
+            forwardIndexB = cccB.newIndex;
+        } else if (cccA == null && cccB == null) {
+            // When both do not have ccc, do not ignore trunk prefix. Without this,
+            // "123123" becomes same as "0123123"
+            okToIgnorePrefix = false;
+        } else {
+            if (cccA != null) {
+                forwardIndexA = cccA.newIndex;
+            } else {
+                int tmp = tryGetTrunkPrefixOmittedIndex(b, 0);
+                if (tmp >= 0) {
+                    forwardIndexA = tmp;
+                    trunkPrefixIsOmittedA = true;
+                }
+            }
+            if (cccB != null) {
+                forwardIndexB = cccB.newIndex;
+            } else {
+                int tmp = tryGetTrunkPrefixOmittedIndex(b, 0);
+                if (tmp >= 0) {
+                    forwardIndexB = tmp;
+                    trunkPrefixIsOmittedB = true;
+                }
+            }
+        }
+
+        int backwardIndexA = a.length() - 1;
+        int backwardIndexB = b.length() - 1;
+        while (backwardIndexA >= forwardIndexA && backwardIndexB >= forwardIndexB) {
+            boolean skip_compare = false;
+            final char chA = a.charAt(backwardIndexA);
+            final char chB = b.charAt(backwardIndexB);
+            if (isSeparator(chA)) {
+                backwardIndexA--;
+                skip_compare = true;
+            }
+            if (isSeparator(chB)) {
+                backwardIndexB--;
+                skip_compare = true;
+            }
+
+            if (!skip_compare) {
+                if (chA != chB) {
+                    return false;
+                }
+                backwardIndexA--;
+                backwardIndexB--;
+            }
+        }
+
+        if (okToIgnorePrefix) {
+            if ((trunkPrefixIsOmittedA && forwardIndexA <= backwardIndexA) ||
+                !checkPrefixIsIgnorable(a, forwardIndexA, backwardIndexA)) {
+                if (acceptInvalidCCCPrefix) {
+                    // Maybe the code handling the special case for Thailand makes the
+                    // result garbled, so disable the code and try again.
+                    // e.g. "16610001234" must equal to "6610001234", but with
+                    //      Thailand-case handling code, they become equal to each other.
+                    //
+                    // Note: we select simplicity rather than adding some complicated
+                    //       logic here for performance(like "checking whether remaining
+                    //       numbers are just 66 or not"), assuming inputs are small
+                    //       enough.
+                    return compare(a, b, false);
+                } else {
+                    return false;
+                }
+            }
+            if ((trunkPrefixIsOmittedB && forwardIndexB <= backwardIndexB) ||
+                !checkPrefixIsIgnorable(b, forwardIndexA, backwardIndexB)) {
+                if (acceptInvalidCCCPrefix) {
+                    return compare(a, b, false);
+                } else {
+                    return false;
+                }
+            }
+        } else {
+            // In the US, 1-650-555-1234 must be equal to 650-555-1234,
+            // while 090-1234-1234 must not be equalt to 90-1234-1234 in Japan.
+            // This request exists just in US (with 1 trunk (NDD) prefix).
+            // In addition, "011 11 7005554141" must not equal to "+17005554141",
+            // while "011 1 7005554141" must equal to "+17005554141"
+            //
+            // In this comparison, we ignore the prefix '1' just once, when
+            // - at least either does not have CCC, or
+            // - the remaining non-separator number is 1
+            boolean maybeNamp = !bothHasCountryCallingCode;
+            while (backwardIndexA >= forwardIndexA) {
+                final char chA = a.charAt(backwardIndexA);
+                if (isDialable(chA)) {
+                    if (maybeNamp && tryGetISODigit(chA) == 1) {
+                        maybeNamp = false;
+                    } else {
+                        return false;
+                    }
+                }
+                backwardIndexA--;
+            }
+            while (backwardIndexB >= forwardIndexB) {
+                final char chB = b.charAt(backwardIndexB);
+                if (isDialable(chB)) {
+                    if (maybeNamp && tryGetISODigit(chB) == 1) {
+                        maybeNamp = false;
+                    } else {
+                        return false;
+                    }
+                }
+                backwardIndexB--;
+            }
+        }
+
+        return true;
+    }
+
+    /**
      * Returns the rightmost MIN_MATCH (5) characters in the network portion
      * in *reversed* order
      *
@@ -475,54 +652,6 @@ public class PhoneNumberUtils
     }
 
     /**
-     * Phone numbers are stored in "lookup" form in the database
-     * as reversed strings to allow for caller ID lookup
-     *
-     * This method takes a phone number and makes a valid SQL "LIKE"
-     * string that will match the lookup form
-     *
-     */
-    /** all of a up to len must be an international prefix or
-     *  separators/non-dialing digits
-     */
-    private static boolean
-    matchIntlPrefix(String a, int len) {
-        /* '([^0-9*#+pwn]\+[^0-9*#+pwn] | [^0-9*#+pwn]0(0|11)[^0-9*#+pwn] )$' */
-        /*        0       1                           2 3 45               */
-
-        int state = 0;
-        for (int i = 0 ; i < len ; i++) {
-            char c = a.charAt(i);
-
-            switch (state) {
-                case 0:
-                    if      (c == '+') state = 1;
-                    else if (c == '0') state = 2;
-                    else if (isNonSeparator(c)) return false;
-                break;
-
-                case 2:
-                    if      (c == '0') state = 3;
-                    else if (c == '1') state = 4;
-                    else if (isNonSeparator(c)) return false;
-                break;
-
-                case 4:
-                    if      (c == '1') state = 5;
-                    else if (isNonSeparator(c)) return false;
-                break;
-
-                default:
-                    if (isNonSeparator(c)) return false;
-                break;
-
-            }
-        }
-
-        return state == 1 || state == 3 || state == 5;
-    }
-
-    /**
      *  3GPP TS 24.008 10.5.4.7
      *  Called Party BCD Number
      *
@@ -835,76 +964,6 @@ public class PhoneNumberUtils
         return result;
     }
 
-    /** all of 'a' up to len must match non-US trunk prefix ('0') */
-    private static boolean
-    matchTrunkPrefix(String a, int len) {
-        boolean found;
-
-        found = false;
-
-        for (int i = 0 ; i < len ; i++) {
-            char c = a.charAt(i);
-
-            if (c == '0' && !found) {
-                found = true;
-            } else if (isNonSeparator(c)) {
-                return false;
-            }
-        }
-
-        return found;
-    }
-
-    /** all of 'a' up to len must be a (+|00|011)country code)
-     *  We're fast and loose with the country code. Any \d{1,3} matches */
-    private static boolean
-    matchIntlPrefixAndCC(String a, int len) {
-        /*  [^0-9*#+pwn]*(\+|0(0|11)\d\d?\d? [^0-9*#+pwn] $ */
-        /*      0          1 2 3 45  6 7  8                 */
-
-        int state = 0;
-        for (int i = 0 ; i < len ; i++ ) {
-            char c = a.charAt(i);
-
-            switch (state) {
-                case 0:
-                    if      (c == '+') state = 1;
-                    else if (c == '0') state = 2;
-                    else if (isNonSeparator(c)) return false;
-                break;
-
-                case 2:
-                    if      (c == '0') state = 3;
-                    else if (c == '1') state = 4;
-                    else if (isNonSeparator(c)) return false;
-                break;
-
-                case 4:
-                    if      (c == '1') state = 5;
-                    else if (isNonSeparator(c)) return false;
-                break;
-
-                case 1:
-                case 3:
-                case 5:
-                    if      (isISODigit(c)) state = 6;
-                    else if (isNonSeparator(c)) return false;
-                break;
-
-                case 6:
-                case 7:
-                    if      (isISODigit(c)) state++;
-                    else if (isNonSeparator(c)) return false;
-                break;
-
-                default:
-                    if (isNonSeparator(c)) return false;
-            }
-        }
-
-        return state == 6 || state == 7 || state == 8;
-    }
-
     //================ Number formatting =========================
 
     /** The current locale is unknown, look for a country code or don't format */
@@ -1553,4 +1612,317 @@ public class PhoneNumberUtils
         }
         return retStr;
     }
+
+    //===== Begining of utility methods used in compareLoosely() =====
+
+    /**
+     * Phone numbers are stored in "lookup" form in the database
+     * as reversed strings to allow for caller ID lookup
+     *
+     * This method takes a phone number and makes a valid SQL "LIKE"
+     * string that will match the lookup form
+     *
+     */
+    /** all of a up to len must be an international prefix or
+     *  separators/non-dialing digits
+     */
+    private static boolean
+    matchIntlPrefix(String a, int len) {
+        /* '([^0-9*#+pwn]\+[^0-9*#+pwn] | [^0-9*#+pwn]0(0|11)[^0-9*#+pwn] )$' */
+        /*        0       1                           2 3 45               */
+
+        int state = 0;
+        for (int i = 0 ; i < len ; i++) {
+            char c = a.charAt(i);
+
+            switch (state) {
+                case 0:
+                    if      (c == '+') state = 1;
+                    else if (c == '0') state = 2;
+                    else if (isNonSeparator(c)) return false;
+                break;
+
+                case 2:
+                    if      (c == '0') state = 3;
+                    else if (c == '1') state = 4;
+                    else if (isNonSeparator(c)) return false;
+                break;
+
+                case 4:
+                    if      (c == '1') state = 5;
+                    else if (isNonSeparator(c)) return false;
+                break;
+
+                default:
+                    if (isNonSeparator(c)) return false;
+                break;
+
+            }
+        }
+
+        return state == 1 || state == 3 || state == 5;
+    }
+
+    /** all of 'a' up to len must be a (+|00|011)country code)
+     *  We're fast and loose with the country code. Any \d{1,3} matches */
+    private static boolean
+    matchIntlPrefixAndCC(String a, int len) {
+        /*  [^0-9*#+pwn]*(\+|0(0|11)\d\d?\d? [^0-9*#+pwn] $ */
+        /*      0          1 2 3 45  6 7  8                 */
+
+        int state = 0;
+        for (int i = 0 ; i < len ; i++ ) {
+            char c = a.charAt(i);
+
+            switch (state) {
+                case 0:
+                    if      (c == '+') state = 1;
+                    else if (c == '0') state = 2;
+                    else if (isNonSeparator(c)) return false;
+                break;
+
+                case 2:
+                    if      (c == '0') state = 3;
+                    else if (c == '1') state = 4;
+                    else if (isNonSeparator(c)) return false;
+                break;
+
+                case 4:
+                    if      (c == '1') state = 5;
+                    else if (isNonSeparator(c)) return false;
+                break;
+
+                case 1:
+                case 3:
+                case 5:
+                    if      (isISODigit(c)) state = 6;
+                    else if (isNonSeparator(c)) return false;
+                break;
+
+                case 6:
+                case 7:
+                    if      (isISODigit(c)) state++;
+                    else if (isNonSeparator(c)) return false;
+                break;
+
+                default:
+                    if (isNonSeparator(c)) return false;
+            }
+        }
+
+        return state == 6 || state == 7 || state == 8;
+    }
+
+    /** all of 'a' up to len must match non-US trunk prefix ('0') */
+    private static boolean
+    matchTrunkPrefix(String a, int len) {
+        boolean found;
+
+        found = false;
+
+        for (int i = 0 ; i < len ; i++) {
+            char c = a.charAt(i);
+
+            if (c == '0' && !found) {
+                found = true;
+            } else if (isNonSeparator(c)) {
+                return false;
+            }
+        }
+
+        return found;
+    }
+
+    //===== End of utility methods used only in compareLoosely() =====
+
+    //===== Beggining of utility methods used only in compareStrictly() ====
+
+    /*
+     * If true, the number is country calling code.
+     */
+    private static final boolean COUNTLY_CALLING_CALL[] = {
+        true, true, false, false, false, false, false, true, false, false,
+        false, false, false, false, false, false, false, false, false, false,
+        true, false, false, false, false, false, false, true, true, false,
+        true, true, true, true, true, false, true, false, false, true,
+        true, false, false, true, true, true, true, true, true, true,
+        false, true, true, true, true, true, true, true, true, false,
+        true, true, true, true, true, true, true, false, false, false,
+        false, false, false, false, false, false, false, false, false, false,
+        false, true, true, true, true, false, true, false, false, true,
+        true, true, true, true, true, true, false, false, true, false,
+    };
+    private static final int CCC_LENGTH = COUNTLY_CALLING_CALL.length;
+
+    /**
+     * @return true when input is valid Country Calling Code.
+     */
+    private static boolean isCountryCallingCode(int countryCallingCodeCandidate) {
+        return countryCallingCodeCandidate > 0 && countryCallingCodeCandidate < CCC_LENGTH &&
+                COUNTLY_CALLING_CALL[countryCallingCodeCandidate];
+    }
+
+    /**
+     * Returns interger corresponding to the input if input "ch" is
+     * ISO-LATIN characters 0-9.
+     * Returns -1 otherwise
+     */
+    private static int tryGetISODigit(char ch) {
+        if ('0' <= ch && ch <= '9') {
+            return ch - '0';
+        } else {
+            return -1;
+        }
+    }
+
+    private static class CountryCallingCodeAndNewIndex {
+        public final int countryCallingCode;
+        public final int newIndex;
+        public CountryCallingCodeAndNewIndex(int countryCode, int newIndex) {
+            this.countryCallingCode = countryCode;
+            this.newIndex = newIndex;
+        }
+    }
+
+    /*
+     * Note that this function does not strictly care the country calling code with
+     * 3 length (like Morocco: +212), assuming it is enough to use the first two
+     * digit to compare two phone numbers.
+     */
+    private static CountryCallingCodeAndNewIndex tryGetCountryCallingCodeAndNewIndex(
+        String str, boolean acceptThailandCase) {
+        // Rough regexp:
+        //  ^[^0-9*#+]*((\+|0(0|11)\d\d?|166) [^0-9*#+] $
+        //         0        1 2 3 45  6 7  89
+        //
+        // In all the states, this function ignores separator characters.
+        // "166" is the special case for the call from Thailand to the US. Uguu!
+        int state = 0;
+        int ccc = 0;
+        final int length = str.length();
+        for (int i = 0 ; i < length ; i++ ) {
+            char ch = str.charAt(i);
+            switch (state) {
+                case 0:
+                    if      (ch == '+') state = 1;
+                    else if (ch == '0') state = 2;
+                    else if (ch == '1') {
+                        if (acceptThailandCase) {
+                            state = 8;
+                        } else {
+                            return null;
+                        }
+                    } else if (isDialable(ch)) {
+                        return null;
+                    }
+                break;
+
+                case 2:
+                    if      (ch == '0') state = 3;
+                    else if (ch == '1') state = 4;
+                    else if (isDialable(ch)) {
+                        return null;
+                    }
+                break;
+
+                case 4:
+                    if      (ch == '1') state = 5;
+                    else if (isDialable(ch)) {
+                        return null;
+                    }
+                break;
+
+                case 1:
+                case 3:
+                case 5:
+                case 6:
+                case 7:
+                    {
+                        int ret = tryGetISODigit(ch);
+                        if (ret > 0) {
+                            ccc = ccc * 10 + ret;
+                            if (ccc >= 100 || isCountryCallingCode(ccc)) {
+                                return new CountryCallingCodeAndNewIndex(ccc, i + 1);
+                            }
+                            if (state == 1 || state == 3 || state == 5) {
+                                state = 6;
+                            } else {
+                                state++;
+                            }
+                        } else if (isDialable(ch)) {
+                            return null;
+                        }
+                    }
+                    break;
+                case 8:
+                    if (ch == '6') state = 9;
+                    else if (isDialable(ch)) {
+                        return null;
+                    }
+                    break;
+                case 9:
+                    if (ch == '6') {
+                        return new CountryCallingCodeAndNewIndex(66, i + 1);
+                    } else {
+                        return null;
+                    }
+                default:
+                    return null;
+            }
+        }
+
+        return null;
+    }
+
+    /**
+     * Currently this function simply ignore the first digit assuming it is
+     * trunk prefix. Actually trunk prefix is different in each country.
+     *
+     * e.g.
+     * "+79161234567" equals "89161234567" (Russian trunk digit is 8)
+     * "+33123456789" equals "0123456789" (French trunk digit is 0)
+     *
+     */
+    private static int tryGetTrunkPrefixOmittedIndex(String str, int currentIndex) {
+        int length = str.length();
+        for (int i = currentIndex ; i < length ; i++) {
+            final char ch = str.charAt(i);
+            if (tryGetISODigit(ch) >= 0) {
+                return i + 1;
+            } else if (isDialable(ch)) {
+                return -1;
+            }
+        }
+        return -1;
+    }
+
+    /**
+     * Return true if the prefix of "str" is "ignorable". Here, "ignorable" means
+     * that "str" has only one digit and separater characters. The one digit is
+     * assumed to be trunk prefix.
+     */
+    private static boolean checkPrefixIsIgnorable(final String str,
+            int forwardIndex, int backwardIndex) {
+        boolean trunk_prefix_was_read = false;
+        while (backwardIndex >= forwardIndex) {
+            if (tryGetISODigit(str.charAt(backwardIndex)) >= 0) {
+                if (trunk_prefix_was_read) {
+                    // More than one digit appeared, meaning that "a" and "b"
+                    // is different.
+                    return false;
+                } else {
+                    // Ignore just one digit, assuming it is trunk prefix.
+                    trunk_prefix_was_read = true;
+                }
+            } else if (isDialable(str.charAt(backwardIndex))) {
+                // Trunk prefix is a digit, not "*", "#"...
+                return false;
+            }
+            backwardIndex--;
+        }
+
+        return true;
+    }
+
+    //==== End of utility methods used only in compareStrictly() =====
 }