1 /* 2 * Copyright (C) 2012 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 package com.android.dialer.smartdial; 18 19 import android.support.annotation.Nullable; 20 import android.support.annotation.VisibleForTesting; 21 import android.text.TextUtils; 22 import com.android.dialer.smartdial.SmartDialPrefix.PhoneNumberTokens; 23 import java.util.ArrayList; 24 25 /** 26 * {@link #SmartDialNameMatcher} contains utility functions to remove accents from accented 27 * characters and normalize a phone number. It also contains the matching logic that determines if a 28 * contact's display name matches a numeric query. The boolean variable {@link #ALLOW_INITIAL_MATCH} 29 * controls the behavior of the matching logic and determines whether we allow matches like 57 - 30 * (J)ohn (S)mith. 31 */ 32 public class SmartDialNameMatcher { 33 34 public static final SmartDialMap LATIN_SMART_DIAL_MAP = new LatinSmartDialMap(); 35 // Whether or not we allow matches like 57 - (J)ohn (S)mith 36 private static final boolean ALLOW_INITIAL_MATCH = true; 37 38 // The maximum length of the initial we will match - typically set to 1 to minimize false 39 // positives 40 private static final int INITIAL_LENGTH_LIMIT = 1; 41 42 private final ArrayList<SmartDialMatchPosition> mMatchPositions = new ArrayList<>(); 43 private final SmartDialMap mMap; 44 private String mQuery; 45 private String mNameMatchMask = ""; 46 private String mPhoneNumberMatchMask = ""; 47 48 // Controls whether to treat an empty query as a match (with anything). 49 private boolean mShouldMatchEmptyQuery = false; 50 51 @VisibleForTesting 52 public SmartDialNameMatcher(String query) { 53 this(query, LATIN_SMART_DIAL_MAP); 54 } 55 56 public SmartDialNameMatcher(String query, SmartDialMap map) { 57 mQuery = query; 58 mMap = map; 59 } 60 61 /** 62 * Strips a phone number of unnecessary characters (spaces, dashes, etc.) 63 * 64 * @param number Phone number we want to normalize 65 * @return Phone number consisting of digits from 0-9 66 */ 67 public static String normalizeNumber(String number, SmartDialMap map) { 68 return normalizeNumber(number, 0, map); 69 } 70 71 /** 72 * Strips a phone number of unnecessary characters (spaces, dashes, etc.) 73 * 74 * @param number Phone number we want to normalize 75 * @param offset Offset to start from 76 * @return Phone number consisting of digits from 0-9 77 */ 78 public static String normalizeNumber(String number, int offset, SmartDialMap map) { 79 final StringBuilder s = new StringBuilder(); 80 for (int i = offset; i < number.length(); i++) { 81 char ch = number.charAt(i); 82 if (map.isValidDialpadNumericChar(ch)) { 83 s.append(ch); 84 } 85 } 86 return s.toString(); 87 } 88 89 /** 90 * Constructs empty highlight mask. Bit 0 at a position means there is no match, Bit 1 means there 91 * is a match and should be highlighted in the TextView. 92 * 93 * @param builder StringBuilder object 94 * @param length Length of the desired mask. 95 */ 96 private void constructEmptyMask(StringBuilder builder, int length) { 97 for (int i = 0; i < length; ++i) { 98 builder.append("0"); 99 } 100 } 101 102 /** 103 * Replaces the 0-bit at a position with 1-bit, indicating that there is a match. 104 * 105 * @param builder StringBuilder object. 106 * @param matchPos Match Positions to mask as 1. 107 */ 108 private void replaceBitInMask(StringBuilder builder, SmartDialMatchPosition matchPos) { 109 for (int i = matchPos.start; i < matchPos.end; ++i) { 110 builder.replace(i, i + 1, "1"); 111 } 112 } 113 114 /** 115 * Matches a phone number against a query. Let the test application overwrite the NANP setting. 116 * 117 * @param phoneNumber - Raw phone number 118 * @param query - Normalized query (only contains numbers from 0-9) 119 * @param useNanp - Overwriting nanp setting boolean, used for testing. 120 * @return {@literal null} if the number and the query don't match, a valid SmartDialMatchPosition 121 * with the matching positions otherwise 122 */ 123 @VisibleForTesting 124 @Nullable 125 public SmartDialMatchPosition matchesNumber(String phoneNumber, String query, boolean useNanp) { 126 if (TextUtils.isEmpty(phoneNumber)) { 127 return mShouldMatchEmptyQuery ? new SmartDialMatchPosition(0, 0) : null; 128 } 129 StringBuilder builder = new StringBuilder(); 130 constructEmptyMask(builder, phoneNumber.length()); 131 mPhoneNumberMatchMask = builder.toString(); 132 133 // Try matching the number as is 134 SmartDialMatchPosition matchPos = matchesNumberWithOffset(phoneNumber, query, 0); 135 if (matchPos == null) { 136 final PhoneNumberTokens phoneNumberTokens = SmartDialPrefix.parsePhoneNumber(phoneNumber); 137 138 if (phoneNumberTokens == null) { 139 return matchPos; 140 } 141 if (phoneNumberTokens.countryCodeOffset != 0) { 142 matchPos = matchesNumberWithOffset(phoneNumber, query, phoneNumberTokens.countryCodeOffset); 143 } 144 if (matchPos == null && phoneNumberTokens.nanpCodeOffset != 0 && useNanp) { 145 matchPos = matchesNumberWithOffset(phoneNumber, query, phoneNumberTokens.nanpCodeOffset); 146 } 147 } 148 if (matchPos != null) { 149 replaceBitInMask(builder, matchPos); 150 mPhoneNumberMatchMask = builder.toString(); 151 } 152 return matchPos; 153 } 154 155 /** 156 * Matches a phone number against the saved query, taking care of formatting characters and also 157 * taking into account country code prefixes and special NANP number treatment. 158 * 159 * @param phoneNumber - Raw phone number 160 * @return {@literal null} if the number and the query don't match, a valid SmartDialMatchPosition 161 * with the matching positions otherwise 162 */ 163 public SmartDialMatchPosition matchesNumber(String phoneNumber) { 164 return matchesNumber(phoneNumber, mQuery, true); 165 } 166 167 /** 168 * Matches a phone number against a query, taking care of formatting characters and also taking 169 * into account country code prefixes and special NANP number treatment. 170 * 171 * @param phoneNumber - Raw phone number 172 * @param query - Normalized query (only contains numbers from 0-9) 173 * @return {@literal null} if the number and the query don't match, a valid SmartDialMatchPosition 174 * with the matching positions otherwise 175 */ 176 public SmartDialMatchPosition matchesNumber(String phoneNumber, String query) { 177 return matchesNumber(phoneNumber, query, true); 178 } 179 180 /** 181 * Matches a phone number against a query, taking care of formatting characters 182 * 183 * @param phoneNumber - Raw phone number 184 * @param query - Normalized query (only contains numbers from 0-9) 185 * @param offset - The position in the number to start the match against (used to ignore leading 186 * prefixes/country codes) 187 * @return {@literal null} if the number and the query don't match, a valid SmartDialMatchPosition 188 * with the matching positions otherwise 189 */ 190 private SmartDialMatchPosition matchesNumberWithOffset( 191 String phoneNumber, String query, int offset) { 192 if (TextUtils.isEmpty(phoneNumber) || TextUtils.isEmpty(query)) { 193 return mShouldMatchEmptyQuery ? new SmartDialMatchPosition(offset, offset) : null; 194 } 195 int queryAt = 0; 196 int numberAt = offset; 197 for (int i = offset; i < phoneNumber.length(); i++) { 198 if (queryAt == query.length()) { 199 break; 200 } 201 char ch = phoneNumber.charAt(i); 202 if (mMap.isValidDialpadNumericChar(ch)) { 203 if (ch != query.charAt(queryAt)) { 204 return null; 205 } 206 queryAt++; 207 } else { 208 if (queryAt == 0) { 209 // Found a separator before any part of the query was matched, so advance the 210 // offset to avoid prematurely highlighting separators before the rest of the 211 // query. 212 // E.g. don't highlight the first '-' if we're matching 1-510-111-1111 with 213 // '510'. 214 // However, if the current offset is 0, just include the beginning separators 215 // anyway, otherwise the highlighting ends up looking weird. 216 // E.g. if we're matching (510)-111-1111 with '510', we should include the 217 // first '('. 218 if (offset != 0) { 219 offset++; 220 } 221 } 222 } 223 numberAt++; 224 } 225 return new SmartDialMatchPosition(0 + offset, numberAt); 226 } 227 228 /** 229 * This function iterates through each token in the display name, trying to match the query to the 230 * numeric equivalent of the token. 231 * 232 * <p>A token is defined as a range in the display name delimited by characters that have no latin 233 * alphabet equivalents (e.g. spaces - ' ', periods - ',', underscores - '_' or chinese characters 234 * - ''). Transliteration from non-latin characters to latin character will be done on a best 235 * effort basis - e.g. '' - 'u'. 236 * 237 * <p>For example, the display name "Phillips Thomas Jr" contains three tokens: "phillips", 238 * "thomas", and "jr". 239 * 240 * <p>A match must begin at the start of a token. For example, typing 846(Tho) would match 241 * "Phillips Thomas", but 466(hom) would not. 242 * 243 * <p>Also, a match can extend across tokens. For example, typing 37337(FredS) would match (Fred 244 * S)mith. 245 * 246 * @param displayName The normalized(no accented characters) display name we intend to match 247 * against. 248 * @param query The string of digits that we want to match the display name to. 249 * @param matchList An array list of {@link SmartDialMatchPosition}s that we add matched positions 250 * to. 251 * @return Returns true if a combination of the tokens in displayName match the query string 252 * contained in query. If the function returns true, matchList will contain an ArrayList of 253 * match positions (multiple matches correspond to initial matches). 254 */ 255 @VisibleForTesting 256 boolean matchesCombination( 257 String displayName, String query, ArrayList<SmartDialMatchPosition> matchList) { 258 StringBuilder builder = new StringBuilder(); 259 constructEmptyMask(builder, displayName.length()); 260 mNameMatchMask = builder.toString(); 261 final int nameLength = displayName.length(); 262 final int queryLength = query.length(); 263 264 if (nameLength < queryLength) { 265 return false; 266 } 267 268 if (queryLength == 0) { 269 return false; 270 } 271 272 // The current character index in displayName 273 // E.g. 3 corresponds to 'd' in "Fred Smith" 274 int nameStart = 0; 275 276 // The current character in the query we are trying to match the displayName against 277 int queryStart = 0; 278 279 // The start position of the current token we are inspecting 280 int tokenStart = 0; 281 282 // The number of non-alphabetic characters we've encountered so far in the current match. 283 // E.g. if we've currently matched 3733764849 to (Fred Smith W)illiam, then the 284 // seperatorCount should be 2. This allows us to correctly calculate offsets for the match 285 // positions 286 int seperatorCount = 0; 287 288 ArrayList<SmartDialMatchPosition> partial = new ArrayList<SmartDialMatchPosition>(); 289 // Keep going until we reach the end of displayName 290 while (nameStart < nameLength && queryStart < queryLength) { 291 char ch = displayName.charAt(nameStart); 292 // Strip diacritics from accented characters if any 293 ch = mMap.normalizeCharacter(ch); 294 if (mMap.isValidDialpadCharacter(ch)) { 295 if (mMap.isValidDialpadAlphabeticChar(ch)) { 296 ch = mMap.getDialpadNumericCharacter(ch); 297 } 298 if (ch != query.charAt(queryStart)) { 299 // Failed to match the current character in the query. 300 301 // Case 1: Failed to match the first character in the query. Skip to the next 302 // token since there is no chance of this token matching the query. 303 304 // Case 2: Previous characters in the query matched, but the current character 305 // failed to match. This happened in the middle of a token. Skip to the next 306 // token since there is no chance of this token matching the query. 307 308 // Case 3: Previous characters in the query matched, but the current character 309 // failed to match. This happened right at the start of the current token. In 310 // this case, we should restart the query and try again with the current token. 311 // Otherwise, we would fail to match a query like "964"(yog) against a name 312 // Yo-Yoghurt because the query match would fail on the 3rd character, and 313 // then skip to the end of the "Yoghurt" token. 314 315 if (queryStart == 0 316 || mMap.isValidDialpadCharacter( 317 mMap.normalizeCharacter(displayName.charAt(nameStart - 1)))) { 318 // skip to the next token, in the case of 1 or 2. 319 while (nameStart < nameLength 320 && mMap.isValidDialpadCharacter( 321 mMap.normalizeCharacter(displayName.charAt(nameStart)))) { 322 nameStart++; 323 } 324 nameStart++; 325 } 326 327 // Restart the query and set the correct token position 328 queryStart = 0; 329 seperatorCount = 0; 330 tokenStart = nameStart; 331 } else { 332 if (queryStart == queryLength - 1) { 333 334 // As much as possible, we prioritize a full token match over a sub token 335 // one so if we find a full token match, we can return right away 336 matchList.add( 337 new SmartDialMatchPosition(tokenStart, queryLength + tokenStart + seperatorCount)); 338 for (SmartDialMatchPosition match : matchList) { 339 replaceBitInMask(builder, match); 340 } 341 mNameMatchMask = builder.toString(); 342 return true; 343 } else if (ALLOW_INITIAL_MATCH && queryStart < INITIAL_LENGTH_LIMIT) { 344 // we matched the first character. 345 // branch off and see if we can find another match with the remaining 346 // characters in the query string and the remaining tokens 347 // find the next separator in the query string 348 int j; 349 for (j = nameStart; j < nameLength; j++) { 350 if (!mMap.isValidDialpadCharacter(mMap.normalizeCharacter(displayName.charAt(j)))) { 351 break; 352 } 353 } 354 // this means there is at least one character left after the separator 355 if (j < nameLength - 1) { 356 final String remainder = displayName.substring(j + 1); 357 final ArrayList<SmartDialMatchPosition> partialTemp = new ArrayList<>(); 358 if (matchesCombination(remainder, query.substring(queryStart + 1), partialTemp)) { 359 360 // store the list of possible match positions 361 SmartDialMatchPosition.advanceMatchPositions(partialTemp, j + 1); 362 partialTemp.add(0, new SmartDialMatchPosition(nameStart, nameStart + 1)); 363 // we found a partial token match, store the data in a 364 // temp buffer and return it if we end up not finding a full 365 // token match 366 partial = partialTemp; 367 } 368 } 369 } 370 nameStart++; 371 queryStart++; 372 // we matched the current character in the name against one in the query, 373 // continue and see if the rest of the characters match 374 } 375 } else { 376 // found a separator, we skip this character and continue to the next one 377 nameStart++; 378 if (queryStart == 0) { 379 // This means we found a separator before the start of a token, 380 // so we should increment the token's start position to reflect its true 381 // start position 382 tokenStart = nameStart; 383 } else { 384 // Otherwise this separator was found in the middle of a token being matched, 385 // so increase the separator count 386 seperatorCount++; 387 } 388 } 389 } 390 // if we have no complete match at this point, then we attempt to fall back to the partial 391 // token match(if any). If we don't allow initial matching (ALLOW_INITIAL_MATCH = false) 392 // then partial will always be empty. 393 if (!partial.isEmpty()) { 394 matchList.addAll(partial); 395 for (SmartDialMatchPosition match : matchList) { 396 replaceBitInMask(builder, match); 397 } 398 mNameMatchMask = builder.toString(); 399 return true; 400 } 401 return false; 402 } 403 404 public boolean matches(String displayName) { 405 mMatchPositions.clear(); 406 return matchesCombination(displayName, mQuery, mMatchPositions); 407 } 408 409 public ArrayList<SmartDialMatchPosition> getMatchPositions() { 410 // Return a clone of mMatchPositions so that the caller can use it without 411 // worrying about it changing 412 return new ArrayList<SmartDialMatchPosition>(mMatchPositions); 413 } 414 415 public String getNameMatchPositionsInString() { 416 return mNameMatchMask; 417 } 418 419 public String getNumberMatchPositionsInString() { 420 return mPhoneNumberMatchMask; 421 } 422 423 public String getQuery() { 424 return mQuery; 425 } 426 427 public void setQuery(String query) { 428 mQuery = query; 429 } 430 431 public void setShouldMatchEmptyQuery(boolean matches) { 432 mShouldMatchEmptyQuery = matches; 433 } 434 } 435