From ec2a6103d517a1896abffc493e5f883049872ca9 Mon Sep 17 00:00:00 2001 From: Yorke Lee Date: Tue, 30 Apr 2013 12:51:12 -0700 Subject: Fix Smart dialing OOM for extremely long contacts Names with an extremely large number of name tokens were using exponentially increasing amounts of memory since we have to insert entries for all possible initial name combinations. Added a check in the trie insertion algorithm to only add initial matches for the 1st 2, and the last 2 name tokens. This change only affects search by initial matches for names exceeding 4 name tokens. Full token search for names of all lengths should still work. E.g. "frank", "enstein" would still match "Dr Frank En Stein DDS". However initial matching would be limited to the first 2 and last 2 tokens. So "dfsd" or "fsd" would work, but "fes" or "fed" would not. Also fixes a bug caused by integer overflow when calculating thresholds for bucketing frequently used contacts Bug 8737986 Change-Id: I804184368b78fe2fa407667ed83874d839c28115 --- .../android/dialer/dialpad/SmartDialTrieTest.java | 105 +++++++++++++++------ 1 file changed, 75 insertions(+), 30 deletions(-) (limited to 'tests') diff --git a/tests/src/com/android/dialer/dialpad/SmartDialTrieTest.java b/tests/src/com/android/dialer/dialpad/SmartDialTrieTest.java index cd87b6613..876e00de7 100644 --- a/tests/src/com/android/dialer/dialpad/SmartDialTrieTest.java +++ b/tests/src/com/android/dialer/dialpad/SmartDialTrieTest.java @@ -19,6 +19,7 @@ package com.android.dialer.dialpad; import static com.android.dialer.dialpad.SmartDialCache.ContactNumber; import com.android.dialer.dialpad.SmartDialTrie.Node; +import com.android.dialer.dialpad.SmartDialTrie.ParseInfo; import android.test.suitebuilder.annotation.SmallTest; @@ -129,47 +130,91 @@ public class SmartDialTrieTest extends TestCase{ public void testPutForInitialMatchesCombinations() { final SmartDialTrie trie = new SmartDialTrie(); final ContactNumber alphabet = new ContactNumber(0, "abc def ghi jkl mno pqrs tuv wxyz", - "1", "1", 2); + "12345678", "1", 2); trie.put(alphabet); - // 255 (2^8 - 1) combinations for the name, and 1 for the number - assertEquals(256, trie.numEntries()); - - // Test every single combination of the leading initials of each name token by generating - // strings consisting of all combinations of the digits 2-9. - final StringBuilder sb = new StringBuilder(); - - // Create an array of bit positions 0b10000000, 0b01000000, 0b00100000, ... - final int[] pos = new int[8]; - for (int i = 2; i <= 9; i++) { - pos[i - 2] = 1 << (9 - i); - } - for (int i = 1; i < 256; i++) { - sb.setLength(0); - // If the bit at nth position is set to true, then add the nth initial to the target - // string - for (int j = 2; j <= 9; j++) { - if ((i & pos[j - 2]) > 0) { - sb.append(j); - } - } - assertTrue(checkContains(trie, alphabet, sb.toString())); - } + assertEquals(20, trie.numEntries()); + // 8 name entries (abcdefghi..., defghi..., ...) + assertTrue(checkContains(trie, alphabet, "22233344455566677778889999")); + assertTrue(checkContains(trie, alphabet, "33344455566677778889999")); + assertTrue(checkContains(trie, alphabet, "44455566677778889999")); + assertTrue(checkContains(trie, alphabet, "55566677778889999")); + assertTrue(checkContains(trie, alphabet, "66677778889999")); + assertTrue(checkContains(trie, alphabet, "77778889999")); + assertTrue(checkContains(trie, alphabet, "8889999")); + assertTrue(checkContains(trie, alphabet, "9999")); + // 1 number entry + assertTrue(checkContains(trie, alphabet, "12345678")); + // 11 initial entries (adtw, adw, adt, ad, atw, at, aw, dt, dw, dtw, tw) + // 4c2(6) + 4c3(4) + 4c4(1) + assertTrue(checkContains(trie, alphabet, "2389999")); + assertTrue(checkContains(trie, alphabet, "239999")); + assertTrue(checkContains(trie, alphabet, "23888")); + assertTrue(checkContains(trie, alphabet, "2333")); + assertTrue(checkContains(trie, alphabet, "289999")); + assertTrue(checkContains(trie, alphabet, "2888")); + assertTrue(checkContains(trie, alphabet, "29999")); + assertTrue(checkContains(trie, alphabet, "3888")); + assertTrue(checkContains(trie, alphabet, "39999")); + assertTrue(checkContains(trie, alphabet, "389999")); + assertTrue(checkContains(trie, alphabet, "89999")); + } + public void testCheckLongToken() { + final SmartDialTrie trie = new SmartDialTrie(); + final ContactNumber alphabet = new ContactNumber(0, " aaaa bbbb cccc dddd eeee ffff gggg" + + " hhhh iiii jjjj kkkk llll mmmm nnnn oooo pppp qqqq rrrr ssss tttt uuuu vvvv " + + " wwww xxxx yyyy zzzz", "1", "1", 2); + // Make sure the check to prevent overly long tokens from causing an OOM kicks in + trie.put(alphabet); + assertTrue(checkContains(trie, alphabet, "2222")); + // 26 name entries (aaaabbbbcccc...., bbbbccccdddd...., ccccdddd...) + // 1 number entry + // 11 initial entries 4c2(6) + 4c3(4) + 4c4(1) + assertEquals(38, trie.numEntries()); + + final ContactNumber alphabet2 = new ContactNumber(0, "aaaabbbbccccddddeeeeffffgggg" + + "hhhhiiiijjjjkkkkllllmmmmnnnnooooppppqqqqrrrrssssttttuuuuvvvvwwwwxxxxyyyyzzzz", + "1", "1", 2); + trie.put(alphabet2); + // added one name, and one number entry + assertEquals(40, trie.numEntries()); } - public void testSeparators() { - SmartDialTrie trie = new SmartDialTrie(); - String name = "Mcdonald Jamie-Cullum"; - byte[] bytes = trie.toByteArray(name); + public void testParseInfo() { + final SmartDialTrie trie = new SmartDialTrie(); + final String name = "Mcdonald Jamie-Cullum"; + final ParseInfo info = trie.parseToIndexes(name, 2, 2); // Make sure the dash is correctly converted to a separator character for (int i = 0; i < name.length(); i++) { // separators at position 8 and 12 if (i == 8 || i == 14) { - assertTrue(bytes[i] == -1); + assertTrue(info.indexes[i] == -1); } else { - assertFalse(bytes[i] == -1); + assertFalse(info.indexes[i] == -1); } } + assertEquals(14, info.nthFirstTokenPos); + assertEquals(8, info.nthLastTokenPos); + + final String name2 = "aaa bbb ccc ddd eee fff ggg hhh iii jjj kkk"; + final ParseInfo info2 = trie.parseToIndexes(name2, 2, 2); + assertEquals(7, info2.nthFirstTokenPos); + assertEquals(35, info2.nthLastTokenPos); + + final String name3 = "this is- a,test name"; + final ParseInfo info3 = trie.parseToIndexes(name3, 3, 3); + assertEquals(11, info3.nthFirstTokenPos); + assertEquals(8, info3.nthLastTokenPos); + + final String name4 = "M c-Donald James"; + final ParseInfo info4 = trie.parseToIndexes(name4, 2, 3); + assertEquals(3, info4.nthFirstTokenPos); + assertEquals(1, info4.nthLastTokenPos); + + final String name5 = " Aa'Bb c dddd e'e"; + final ParseInfo info5 = trie.parseToIndexes(name5, 4, 4); + assertEquals(21, info5.nthFirstTokenPos); + assertEquals(8, info5.nthLastTokenPos); } public void testAccentedCharacters() { -- cgit v1.2.3