1 /*
2  * Copyright (C) 2010 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 package com.android.loganalysis.util;
17 
18 import static org.junit.Assert.assertEquals;
19 import static org.junit.Assert.assertFalse;
20 import static org.junit.Assert.assertNotEquals;
21 import static org.junit.Assert.assertNull;
22 import static org.junit.Assert.assertTrue;
23 
24 import com.android.loganalysis.util.RegexTrie.CompPattern;
25 
26 import org.junit.Before;
27 import org.junit.Test;
28 import org.junit.runner.RunWith;
29 import org.junit.runners.JUnit4;
30 
31 import java.util.ArrayList;
32 import java.util.Arrays;
33 import java.util.HashMap;
34 import java.util.List;
35 import java.util.regex.Pattern;
36 
37 /** Set of unit tests to verify the behavior of the RegexTrie */
38 @RunWith(JUnit4.class)
39 public class RegexTrieTest {
40     private RegexTrie<Integer> mTrie = null;
41     private static final Integer STORED_VAL = 42;
42     private static final List<String> NULL_LIST = Arrays.asList((String)null);
43 
44     @Before
setUp()45     public void setUp() throws Exception {
46         mTrie = new RegexTrie<Integer>();
47     }
48 
49     @Test
testStringPattern()50     public void testStringPattern() {
51         mTrie.put(STORED_VAL, "[p]art1", "[p]art2", "[p]art3");
52         Integer retrieved = mTrie.retrieve("part1", "part2", "part3");
53         assertEquals(STORED_VAL, retrieved);
54     }
55 
56     @Test
testAlternation_single()57     public void testAlternation_single() {
58         mTrie.put(STORED_VAL, "alpha|beta");
59         Integer retrieved;
60         retrieved = mTrie.retrieve("alpha");
61         assertEquals(STORED_VAL, retrieved);
62         retrieved = mTrie.retrieve("beta");
63         assertEquals(STORED_VAL, retrieved);
64         retrieved = mTrie.retrieve("alpha|beta");
65         assertNull(retrieved);
66         retrieved = mTrie.retrieve("gamma");
67         assertNull(retrieved);
68         retrieved = mTrie.retrieve("alph");
69         assertNull(retrieved);
70     }
71 
72     @Test
testAlternation_multiple()73     public void testAlternation_multiple() {
74         mTrie.put(STORED_VAL, "a|alpha", "b|beta");
75         Integer retrieved;
76         retrieved = mTrie.retrieve("a", "b");
77         assertEquals(STORED_VAL, retrieved);
78         retrieved = mTrie.retrieve("a", "beta");
79         assertEquals(STORED_VAL, retrieved);
80         retrieved = mTrie.retrieve("alpha", "b");
81         assertEquals(STORED_VAL, retrieved);
82         retrieved = mTrie.retrieve("alpha", "beta");
83         assertEquals(STORED_VAL, retrieved);
84 
85         retrieved = mTrie.retrieve("alpha");
86         assertNull(retrieved);
87         retrieved = mTrie.retrieve("beta");
88         assertNull(retrieved);
89         retrieved = mTrie.retrieve("alpha", "bet");
90         assertNull(retrieved);
91     }
92 
93     @Test
testGroups_fullMatch()94     public void testGroups_fullMatch() {
95         mTrie.put(STORED_VAL, "a|(alpha)", "b|(beta)");
96         Integer retrieved;
97         List<List<String>> groups = new ArrayList<List<String>>();
98 
99         retrieved = mTrie.retrieve(groups, "a", "b");
100         assertEquals(STORED_VAL, retrieved);
101         assertEquals(2, groups.size());
102         assertEquals(NULL_LIST, groups.get(0));
103         assertEquals(NULL_LIST, groups.get(1));
104 
105         retrieved = mTrie.retrieve(groups, "a", "beta");
106         assertEquals(STORED_VAL, retrieved);
107         assertEquals(2, groups.size());
108         assertEquals(NULL_LIST, groups.get(0));
109         assertEquals(Arrays.asList("beta"), groups.get(1));
110 
111         retrieved = mTrie.retrieve(groups, "alpha", "b");
112         assertEquals(STORED_VAL, retrieved);
113         assertEquals(2, groups.size());
114         assertEquals(Arrays.asList("alpha"), groups.get(0));
115         assertEquals(NULL_LIST, groups.get(1));
116 
117         retrieved = mTrie.retrieve(groups, "alpha", "beta");
118         assertEquals(STORED_VAL, retrieved);
119         assertEquals(2, groups.size());
120         assertEquals(Arrays.asList("alpha"), groups.get(0));
121         assertEquals(Arrays.asList("beta"), groups.get(1));
122     }
123 
124     @Test
testGroups_partialMatch()125     public void testGroups_partialMatch() {
126         mTrie.put(STORED_VAL, "a|(alpha)", "b|(beta)");
127         Integer retrieved;
128         List<List<String>> groups = new ArrayList<List<String>>();
129 
130         retrieved = mTrie.retrieve(groups, "alpha");
131         assertNull(retrieved);
132         assertEquals(1, groups.size());
133         assertEquals(Arrays.asList("alpha"), groups.get(0));
134 
135         retrieved = mTrie.retrieve(groups, "beta");
136         assertNull(retrieved);
137         assertEquals(0, groups.size());
138 
139         retrieved = mTrie.retrieve(groups, "alpha", "bet");
140         assertNull(retrieved);
141         assertEquals(1, groups.size());
142         assertEquals(Arrays.asList("alpha"), groups.get(0));
143 
144         retrieved = mTrie.retrieve(groups, "alpha", "betar");
145         assertNull(retrieved);
146         assertEquals(1, groups.size());
147         assertEquals(Arrays.asList("alpha"), groups.get(0));
148 
149         retrieved = mTrie.retrieve(groups, "alpha", "beta", "gamma");
150         assertNull(retrieved);
151         assertEquals(2, groups.size());
152         assertEquals(Arrays.asList("alpha"), groups.get(0));
153         assertEquals(Arrays.asList("beta"), groups.get(1));
154     }
155 
156     /** Make sure that the wildcard functionality works */
157     @Test
testWildcard()158     public void testWildcard() {
159         mTrie.put(STORED_VAL, "a", null);
160         Integer retrieved;
161         List<List<String>> groups = new ArrayList<List<String>>();
162 
163         retrieved = mTrie.retrieve(groups, "a", "b", "c");
164         assertEquals(STORED_VAL, retrieved);
165         assertEquals(3, groups.size());
166         assertTrue(groups.get(0).isEmpty());
167         assertEquals(Arrays.asList("b"), groups.get(1));
168         assertEquals(Arrays.asList("c"), groups.get(2));
169 
170         retrieved = mTrie.retrieve(groups, "a");
171         assertNull(retrieved);
172         assertEquals(1, groups.size());
173         assertTrue(groups.get(0).isEmpty());
174     }
175 
176     /**
177      * Make sure that if a wildcard and a more specific match could both match, that the more
178      * specific match takes precedence
179      */
180     @Test
testWildcard_precedence()181     public void testWildcard_precedence() {
182         // Do one before and one after the wildcard to check for ordering effects
183         mTrie.put(STORED_VAL + 1, "a", "(b)");
184         mTrie.put(STORED_VAL, "a", null);
185         mTrie.put(STORED_VAL + 2, "a", "(c)");
186         Integer retrieved;
187         List<List<String>> groups = new ArrayList<List<String>>();
188 
189         retrieved = mTrie.retrieve(groups, "a", "d");
190         assertEquals(STORED_VAL, retrieved);
191         assertEquals(2, groups.size());
192         assertTrue(groups.get(0).isEmpty());
193         assertEquals(Arrays.asList("d"), groups.get(1));
194 
195         retrieved = mTrie.retrieve(groups, "a", "b");
196         assertEquals((Integer)(STORED_VAL + 1), retrieved);
197         assertEquals(2, groups.size());
198         assertTrue(groups.get(0).isEmpty());
199         assertEquals(Arrays.asList("b"), groups.get(1));
200 
201         retrieved = mTrie.retrieve(groups, "a", "c");
202         assertEquals((Integer)(STORED_VAL + 2), retrieved);
203         assertEquals(2, groups.size());
204         assertTrue(groups.get(0).isEmpty());
205         assertEquals(Arrays.asList("c"), groups.get(1));
206     }
207 
208     /**
209      * Verify a bugfix: make sure that no NPE results from calling #retrieve with a wildcard but
210      * without a place to retrieve captures.
211      */
212     @Test
testWildcard_noCapture()213     public void testWildcard_noCapture() throws NullPointerException {
214         mTrie.put(STORED_VAL, "a", null);
215         String[] key = new String[] {"a", "b", "c"};
216 
217         mTrie.retrieve(key);
218         mTrie.retrieve(null, key);
219         // test passes if no exceptions were thrown
220     }
221 
222     @Test
testMultiChild()223     public void testMultiChild() {
224         mTrie.put(STORED_VAL + 1, "a", "b");
225         mTrie.put(STORED_VAL + 2, "a", "c");
226 
227         Object retrieved;
228         retrieved = mTrie.retrieve("a", "b");
229         assertEquals(STORED_VAL + 1, retrieved);
230         retrieved = mTrie.retrieve("a", "c");
231         assertEquals(STORED_VAL + 2, retrieved);
232     }
233 
234     /**
235      * Make sure that {@link CompPattern#equals} works as expected. Shake a proverbial fist at Java
236      */
237     @Test
testCompPattern_equality()238     public void testCompPattern_equality() {
239         String regex = "regex";
240         Pattern p1 = Pattern.compile(regex);
241         Pattern p2 = Pattern.compile(regex);
242         Pattern pOther = Pattern.compile("other");
243         CompPattern cp1 = new CompPattern(p1);
244         CompPattern cp2 = new CompPattern(p2);
245         CompPattern cpOther = new CompPattern(pOther);
246 
247         // This is the problem with Pattern as implemented
248         assertNotEquals(p1, p2);
249         assertNotEquals(p2, p1);
250 
251         // Make sure that wrapped patterns with the same regex are considered equivalent
252         assertEquals(cp2, p1);
253         assertEquals(cp2, p1);
254         assertEquals(cp2, cp1);
255 
256         // And make sure that wrapped patterns with different regexen are still considered different
257         assertNotEquals(cp2, pOther);
258         assertNotEquals(cp2, cpOther);
259     }
260 
261     @Test
testCompPattern_hashmap()262     public void testCompPattern_hashmap() {
263         HashMap<CompPattern, Integer> map = new HashMap<CompPattern, Integer>();
264         String regex = "regex";
265         Pattern p1 = Pattern.compile(regex);
266         Pattern p2 = Pattern.compile(regex);
267         Pattern pOther = Pattern.compile("other");
268         CompPattern cp1 = new CompPattern(p1);
269         CompPattern cp2 = new CompPattern(p2);
270         CompPattern cpOther = new CompPattern(pOther);
271 
272         map.put(cp1, STORED_VAL);
273         assertTrue(map.containsKey(cp1));
274         assertTrue(map.containsKey(cp2));
275         assertFalse(map.containsKey(cpOther));
276 
277         map.put(cpOther, STORED_VAL);
278         assertEquals(map.size(), 2);
279         assertTrue(map.containsKey(cp1));
280         assertTrue(map.containsKey(cp2));
281         assertTrue(map.containsKey(cpOther));
282     }
283 }
284 
285