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