1 /* 2 * Copyright (C) 2017 The Libphonenumber Authors. 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 package com.google.i18n.phonenumbers.metadata; 17 18 import static com.google.common.truth.Truth.assertThat; 19 import static com.google.i18n.phonenumbers.metadata.RangeTree.empty; 20 import static com.google.i18n.phonenumbers.metadata.testing.RangeTreeSubject.assertThat; 21 22 import java.util.Arrays; 23 import org.junit.Test; 24 import org.junit.runner.RunWith; 25 import org.junit.runners.JUnit4; 26 27 @RunWith(JUnit4.class) 28 public class PrefixTreeTest { 29 @Test testNewInstancesNormalized()30 public void testNewInstancesNormalized() { 31 assertThat(prefixes("123", "1234")).containsExactly("123"); 32 assertThat(prefixes("70x", "7[1-9]")).containsExactly("7"); 33 // Regression test for b/68707522 34 assertThat(prefixes("123xxx", "123x_xxx", "567xxx", "567x_xxx")).containsExactly("123", "567"); 35 } 36 37 @Test testRetainFrom()38 public void testRetainFrom() { 39 PrefixTree prefix = prefixes("123", "124", "126", "555"); 40 RangeTree ranges = ranges("1xxxxxx", "5xxxxxx", "6xxxxxx"); 41 assertThat(prefix.retainFrom(ranges)).containsExactly("12[346]xxxx", "555xxxx"); 42 } 43 44 @Test testPrefixes()45 public void testPrefixes() { 46 PrefixTree prefix = prefixes("123", "124", "126", "555"); 47 assertThat(prefix.prefixes(seq("1230000"))).isTrue(); 48 assertThat(prefix.prefixes(seq("555000"))).isTrue(); 49 assertThat(prefix.prefixes(seq("12"))).isFalse(); 50 assertThat(prefix.prefixes(seq("120000"))).isFalse(); 51 } 52 53 @Test testEmptyVsZeroLength()54 public void testEmptyVsZeroLength() { 55 PrefixTree empty = PrefixTree.from(empty()); 56 PrefixTree zeroLength = prefixes("xxx"); 57 58 assertThat(empty).isEmpty(); 59 assertThat(zeroLength).isNotEmpty(); 60 assertThat(zeroLength).hasSize(1); 61 assertThat(zeroLength).containsExactly(RangeSpecification.empty()); 62 63 // While the empty prefix tree filters out everything, the zero length tree allows everything 64 // to pass. This is because the zero length prefix tree represents a single prefix of length 65 // zero and all digit sequences start with a zero length sub-sequence. 66 RangeTree ranges = ranges("12x", "3xx", "456"); 67 assertThat(empty.retainFrom(ranges)).isEqualTo(empty()); 68 assertThat(zeroLength.retainFrom(ranges)).isEqualTo(ranges); 69 } 70 71 @Test testNoTrailingAnyPath()72 public void testNoTrailingAnyPath() { 73 assertThat(prefixes("123xxx", "456xx", "789x")).containsExactly("123", "456", "789"); 74 } 75 76 @Test testRangeAndPrefixSameLength()77 public void testRangeAndPrefixSameLength() { 78 PrefixTree prefix = prefixes("1234"); 79 RangeTree ranges = ranges("xxxx"); 80 assertThat(prefix.retainFrom(ranges)).containsExactly("1234"); 81 } 82 83 @Test testRangeShorterThanPrefix()84 public void testRangeShorterThanPrefix() { 85 PrefixTree prefix = prefixes("1234"); 86 RangeTree ranges = ranges("xxx"); 87 assertThat(prefix.retainFrom(ranges)).isEmpty(); 88 } 89 90 @Test testComplex()91 public void testComplex() { 92 PrefixTree prefix = prefixes("[12]", "3x4x5", "67890", "987xx9"); 93 RangeTree ranges = ranges("x", "xx", "xxx", "1234xx", "234xxx", "3xx8xx", "67890"); 94 assertThat(prefix.retainFrom(ranges)) 95 .containsExactly("[12]", "[12]x", "[12]xx", "67890", "1234xx", "234xxx", "3x485x"); 96 } 97 98 @Test testEmptyPrefixTree()99 public void testEmptyPrefixTree() { 100 // The empty filter filters everything out, since a filter operation is defined to return 101 // only ranges which are prefixed by an element in the filter (of which there are none). 102 assertThat(PrefixTree.from(empty()).retainFrom(ranges("12xxx"))).isEmpty(); 103 } 104 105 @Test testZeroLengthPrefix()106 public void testZeroLengthPrefix() { 107 // The non-empty prefix tree which contains a single prefix of zero length. This has no effect 108 // as a filter, since all ranges "have a zero length prefix". 109 PrefixTree prefix = PrefixTree.from(RangeTree.from(RangeSpecification.empty())); 110 RangeTree input = ranges("12xxx"); 111 assertThat(prefix.retainFrom(input)).isEqualTo(input); 112 } 113 114 @Test testUnion()115 public void testUnion() { 116 // Overlapping prefixes retain the more general (shorter) one. 117 assertThat(prefixes("1234").union(prefixes("12"))).containsExactly("12"); 118 // Indentical prefixes treated like normal union. 119 assertThat(prefixes("12").union(prefixes("12"))).containsExactly("12"); 120 // Non-overlapping prefixes treated like normal union. 121 assertThat(prefixes("123").union(prefixes("124"))).containsExactly("12[34]"); 122 // Complex case where prefixes are split into 2 lengths due to a partial overlap. 123 assertThat(prefixes("1234", "45", "800").union(prefixes("12", "4x67"))) 124 .containsExactly("12", "45", "4[0-46-9]67", "800"); 125 } 126 127 @Test testIntersection()128 public void testIntersection() { 129 // Overlapping prefixes retain the more specific (longer) one. 130 assertThat(prefixes("1234").intersect(prefixes("12"))).containsExactly("1234"); 131 // Indentical prefixes treated like normal intersection. 132 assertThat(prefixes("12").intersect(prefixes("12"))).containsExactly("12"); 133 // Non-overlapping prefixes treated like normal intersection. 134 assertThat(prefixes("123").intersect(prefixes("124"))).isEmpty(); 135 // Unlike the union case, with intersection, only the longest prefix remains. 136 assertThat(prefixes("1234", "45x", "800").intersect(prefixes("12x", "4x67"))) 137 .containsExactly("1234", "4567"); 138 } 139 140 @Test testTrim()141 public void testTrim() { 142 assertThat(prefixes("1234").trim(3)).containsExactly("123"); 143 assertThat(prefixes("12").trim(3)).containsExactly("12"); 144 assertThat(prefixes("1234").trim(0)).containsExactly(RangeSpecification.empty()); 145 // Trimming can result in prefixes shorter than the stated length if by collapsing the original 146 // prefix tree you end up with trailing any digit sequences. 147 assertThat(prefixes("12[0-4]5", "12[5-9]").trim(3)).containsExactly("12"); 148 assertThat(prefixes("7001", "70[1-9]", "7[1-9]").trim(3)).containsExactly("7"); 149 } 150 151 @Test testMinimal()152 public void testMinimal() { 153 // If there are no ranges to include, the minimal prefix is empty (matching nothing). 154 assertThat(PrefixTree.minimal(RangeTree.empty(), ranges("123x"), 0)).isEmpty(); 155 156 // If the prefix for the included ranges is the identity, then the result is the identity 157 // (after converting to a prefix, ranges like "xxx.." become the identity prefix). 158 assertThat(PrefixTree.minimal(ranges("xxxx"), ranges("123"), 0).isIdentity()).isTrue(); 159 // Without an exclude set, the prefix returned (at zero length) can just accept everything. 160 assertThat(PrefixTree.minimal(ranges("123x"), RangeTree.empty(), 0).isIdentity()).isTrue(); 161 162 assertThat(PrefixTree.minimal(ranges("123x", "456x"), ranges("13xx", "459x"), 0)) 163 .containsExactly("12", "456"); 164 165 assertThat(PrefixTree.minimal(ranges("123x", "456x"), empty(), 1)).containsExactly("[14]"); 166 assertThat(PrefixTree.minimal(ranges("123x", "456x"), empty(), 2)).containsExactly("12", "45"); 167 168 // Pick the shortest prefix when several suffice. 169 assertThat(PrefixTree.minimal(ranges("12", "1234", "56"), ranges("1xx", "5xxx"), 0)) 170 .containsExactly("12", "56"); 171 assertThat(PrefixTree.minimal(ranges("12", "1234", "56"), ranges("1xx", "5xxx"), 3)) 172 .containsExactly("12", "56"); 173 174 // When ranges are contested, split the prefix (only "12" is contested out of "1[2-4]"). 175 assertThat(PrefixTree.minimal(ranges("1[2-4]5xx", "189xx"), ranges("128xx"), 0)) 176 .containsExactly("125", "1[348]"); 177 178 // If the include range already prefixes an entire path of the exclude set, ignore that path. 179 // Here '12' (the shorter path) already captures '123', so '123' is ignored. 180 assertThat(PrefixTree.minimal(ranges("12", "1234", "56"), ranges("123", "5xxx"), 0)) 181 .containsExactly("1", "56"); 182 // Now all exclude paths are ignored, so you get the "identity" prefix that catches everything. 183 assertThat(PrefixTree.minimal(ranges("12", "1234", "56"), ranges("123", "5678"), 0)) 184 .containsExactly(""); 185 } 186 187 @Test testMinimal_regression()188 public void testMinimal_regression() { 189 // This is extracted from a real case in which the old algorithm would fail for this case. The 190 // "281xxxxxxx" path was necessary for failing since while visiting this, the old algorithm 191 // became "confused" and added an additional "250" path to the minimal prefix, meaning that 192 // the resulting range tree was "250", "250395". When this was turned into a prefix tree, the 193 // shorter, early terminating, path took precedence and the result was (incorrectly) "250". 194 assertThat( 195 PrefixTree.minimal( 196 ranges("250395xxxx"), 197 ranges("250[24-9]xxxxxx", "2503[0-8]xxxxx", "25039[0-46-9]xxxx", "281xxxxxxx"), 198 3)) 199 .containsExactly("250395"); 200 } 201 seq(String s)202 private static DigitSequence seq(String s) { 203 return DigitSequence.of(s); 204 } 205 prefixes(String... specs)206 private static PrefixTree prefixes(String... specs) { 207 return PrefixTree.from(ranges(specs)); 208 } 209 ranges(String... specs)210 private static RangeTree ranges(String... specs) { 211 return RangeTree.from(Arrays.stream(specs).map(RangeSpecification::parse)); 212 } 213 } 214