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.tradefed.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.tradefed.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 45 public void setUp() throws Exception { 46 mTrie = new RegexTrie<Integer>(); 47 } 48 49 @Test 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 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 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 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 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 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 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 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 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 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 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
