1 /** 2 * Copyright 2016 Google Inc. All Rights Reserved. 3 * 4 * <p>Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file 5 * except in compliance with the License. You may obtain a copy of the License at 6 * 7 * <p>http://www.apache.org/licenses/LICENSE-2.0 8 * 9 * <p>Unless required by applicable law or agreed to in writing, software distributed under the 10 * License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either 11 * express or implied. See the License for the specific language governing permissions and 12 * limitations under the License. 13 */ 14 package com.android.vts.util; 15 16 import com.android.vts.entity.DeviceInfoEntity; 17 import com.android.vts.entity.ProfilingPointRunEntity; 18 import com.android.vts.entity.TestRunEntity; 19 import com.google.appengine.api.datastore.DatastoreService; 20 import com.google.appengine.api.datastore.DatastoreServiceFactory; 21 import com.google.appengine.api.datastore.Entity; 22 import com.google.appengine.api.datastore.FetchOptions; 23 import com.google.appengine.api.datastore.Key; 24 import com.google.appengine.api.datastore.KeyFactory; 25 import com.google.appengine.api.datastore.Query; 26 import com.google.appengine.api.datastore.Query.CompositeFilterOperator; 27 import com.google.appengine.api.datastore.Query.Filter; 28 import com.google.appengine.api.datastore.Query.FilterOperator; 29 import com.google.appengine.api.datastore.Query.FilterPredicate; 30 import com.google.common.collect.Sets; 31 import com.google.gson.Gson; 32 import java.util.ArrayList; 33 import java.util.Collection; 34 import java.util.Comparator; 35 import java.util.EnumSet; 36 import java.util.HashMap; 37 import java.util.HashSet; 38 import java.util.Iterator; 39 import java.util.LinkedHashSet; 40 import java.util.List; 41 import java.util.Map; 42 import java.util.Set; 43 import java.util.concurrent.TimeUnit; 44 import java.util.logging.Logger; 45 import java.util.regex.Matcher; 46 import java.util.regex.Pattern; 47 import javax.servlet.http.HttpServletRequest; 48 49 /** FilterUtil, a helper class for parsing and matching search queries to data. */ 50 public class FilterUtil { 51 protected static final Logger logger = Logger.getLogger(FilterUtil.class.getName()); 52 private static final String INEQUALITY_REGEX = "(<=|>=|<|>|=)"; 53 54 /** Key class to represent a filter token. */ 55 public enum FilterKey { 56 DEVICE_BUILD_ID("deviceBuildId", DeviceInfoEntity.BUILD_ID, true), 57 BRANCH("branch", DeviceInfoEntity.BRANCH, true), 58 TARGET("device", DeviceInfoEntity.BUILD_FLAVOR, true), 59 VTS_BUILD_ID("testBuildId", TestRunEntity.TEST_BUILD_ID, false), 60 HOSTNAME("hostname", TestRunEntity.HOST_NAME, false), 61 PASSING("passing", TestRunEntity.PASS_COUNT, false), 62 NONPASSING("nonpassing", TestRunEntity.FAIL_COUNT, false); 63 64 private static final Map<String, FilterKey> keyMap; 65 66 static { 67 keyMap = new HashMap<>(); 68 for (FilterKey k : EnumSet.allOf(FilterKey.class)) { 69 keyMap.put(k.keyString, k); 70 } 71 } 72 73 /** 74 * Test if a string is a valid device key. 75 * 76 * @param keyString The key string. 77 * @return True if they key string matches a key and the key is a device filter. 78 */ 79 public static boolean isDeviceKey(String keyString) { 80 return keyMap.containsKey(keyString) && keyMap.get(keyString).isDevice; 81 } 82 83 /** 84 * Test if a string is a valid test key. 85 * 86 * @param keyString The key string. 87 * @return True if they key string matches a key and the key is a test filter. 88 */ 89 public static boolean isTestKey(String keyString) { 90 return keyMap.containsKey(keyString) && !keyMap.get(keyString).isDevice; 91 } 92 93 /** 94 * Parses a key string into a key. 95 * 96 * @param keyString The key string. 97 * @return The key matching the key string. 98 */ 99 public static FilterKey parse(String keyString) { 100 return keyMap.get(keyString); 101 } 102 103 private final String keyString; 104 private final String property; 105 private final boolean isDevice; 106 107 /** 108 * Constructs a key with the specified key string. 109 * 110 * @param keyString The identifying key string. 111 * @param propertyName The name of the property to match. 112 */ 113 private FilterKey(String keyString, String propertyName, boolean isDevice) { 114 this.keyString = keyString; 115 this.property = propertyName; 116 this.isDevice = isDevice; 117 } 118 119 /** 120 * Return a filter predicate for string equality. 121 * 122 * @param matchString The string to match. 123 * @return A filter predicate enforcing equality on the property. 124 */ 125 public FilterPredicate getFilterForString(String matchString) { 126 return new FilterPredicate(this.property, FilterOperator.EQUAL, matchString); 127 } 128 129 /** 130 * Return a filter predicate for number inequality or equality. 131 * 132 * @param matchNumber A string, either a number or an inequality symbol followed by a 133 * number. 134 * @return A filter predicate enforcing equality on the property, or null if invalid. 135 */ 136 public FilterPredicate getFilterForNumber(String matchNumber) { 137 String numberString = matchNumber.trim(); 138 Pattern p = Pattern.compile(INEQUALITY_REGEX); 139 Matcher m = p.matcher(numberString); 140 141 // Default operator is equality. 142 FilterOperator op = FilterOperator.EQUAL; 143 144 // Determine if there is an inequality operator. 145 if (m.find() && m.start() == 0 && m.end() != numberString.length()) { 146 String opString = m.group(); 147 148 // Inequality operator can be <=, <, >, >=, or =. 149 if (opString.equals("<=")) { 150 op = FilterOperator.LESS_THAN_OR_EQUAL; 151 } else if (opString.equals("<")) { 152 op = FilterOperator.LESS_THAN; 153 } else if (opString.equals(">")) { 154 op = FilterOperator.GREATER_THAN; 155 } else if (opString.equals(">=")) { 156 op = FilterOperator.GREATER_THAN_OR_EQUAL; 157 } else if (!opString.equals("=")) { // unrecognized inequality. 158 return null; 159 } 160 numberString = matchNumber.substring(m.end()).trim(); 161 } 162 try { 163 long number = Long.parseLong(numberString); 164 return new FilterPredicate(this.property, op, number); 165 } catch (NumberFormatException e) { 166 // invalid number 167 return null; 168 } 169 } 170 171 /** 172 * Get the enum value 173 * 174 * @return The string value associated with the key. 175 */ 176 public String getValue() { 177 return this.keyString; 178 } 179 } 180 181 /** 182 * Get the common elements among multiple collections. 183 * 184 * @param collections The collections containing all sub collections to find common element. 185 * @return The common elements set found from the collections param. 186 */ 187 public static <T> Set<T> getCommonElements(Collection<? extends Collection<T>> collections) { 188 189 Set<T> common = new LinkedHashSet<T>(); 190 if (!collections.isEmpty()) { 191 Iterator<? extends Collection<T>> iterator = collections.iterator(); 192 common.addAll(iterator.next()); 193 while (iterator.hasNext()) { 194 common.retainAll(iterator.next()); 195 } 196 } 197 return common; 198 } 199 200 /** 201 * Get the first value associated with the key in the parameter map. 202 * 203 * @param parameterMap The parameter map with string keys and (Object) String[] values. 204 * @param key The key whose value to get. 205 * @return The first value associated with the provided key. 206 */ 207 public static String getFirstParameter(Map<String, Object> parameterMap, String key) { 208 String[] values = (String[]) parameterMap.get(key); 209 if (values.length == 0) return null; 210 return values[0]; 211 } 212 213 /** 214 * Get a filter on devices from a user search query. 215 * 216 * @param parameterMap The key-value map of url parameters. 217 * @return A filter with the values from the user search parameters. 218 */ 219 public static Filter getUserDeviceFilter(Map<String, Object> parameterMap) { 220 Filter deviceFilter = null; 221 for (String key : parameterMap.keySet()) { 222 if (!FilterKey.isDeviceKey(key)) continue; 223 String value = getFirstParameter(parameterMap, key); 224 if (value == null) continue; 225 FilterKey filterKey = FilterKey.parse(key); 226 Filter f = filterKey.getFilterForString(value); 227 if (deviceFilter == null) { 228 deviceFilter = f; 229 } else { 230 deviceFilter = CompositeFilterOperator.and(deviceFilter, f); 231 } 232 } 233 return deviceFilter; 234 } 235 236 /** 237 * Get a list of test filters given the user parameters. 238 * 239 * @param parameterMap The key-value map of url parameters. 240 * @return A list of filters, each having at most one inequality filter. 241 */ 242 public static List<Filter> getUserTestFilters(Map<String, Object> parameterMap) { 243 List<Filter> userFilters = new ArrayList<>(); 244 for (String key : parameterMap.keySet()) { 245 if (!FilterKey.isTestKey(key)) continue; 246 String stringValue = getFirstParameter(parameterMap, key); 247 if (stringValue == null) continue; 248 FilterKey filterKey = FilterKey.parse(key); 249 switch (filterKey) { 250 case NONPASSING: 251 case PASSING: 252 userFilters.add(filterKey.getFilterForNumber(stringValue)); 253 break; 254 case HOSTNAME: 255 case VTS_BUILD_ID: 256 userFilters.add(filterKey.getFilterForString(stringValue.toLowerCase())); 257 break; 258 default: 259 continue; 260 } 261 } 262 return userFilters; 263 } 264 265 /** 266 * Get a filter on the test run type. 267 * 268 * @param showPresubmit True to display presubmit tests. 269 * @param showPostsubmit True to display postsubmit tests. 270 * @param unfiltered True if no filtering should be applied. 271 * @return A filter on the test type. 272 */ 273 public static Filter getTestTypeFilter( 274 boolean showPresubmit, boolean showPostsubmit, boolean unfiltered) { 275 if (unfiltered) { 276 return null; 277 } else if (showPresubmit && !showPostsubmit) { 278 return new FilterPredicate( 279 TestRunEntity.TYPE, 280 FilterOperator.EQUAL, 281 TestRunEntity.TestRunType.PRESUBMIT.getNumber()); 282 } else if (showPostsubmit && !showPresubmit) { 283 return new FilterPredicate( 284 TestRunEntity.TYPE, 285 FilterOperator.EQUAL, 286 TestRunEntity.TestRunType.POSTSUBMIT.getNumber()); 287 } else { 288 List<Integer> types = new ArrayList<>(); 289 types.add(TestRunEntity.TestRunType.PRESUBMIT.getNumber()); 290 types.add(TestRunEntity.TestRunType.POSTSUBMIT.getNumber()); 291 return new FilterPredicate(TestRunEntity.TYPE, FilterOperator.IN, types); 292 } 293 } 294 295 /** 296 * Get a filter for profiling points between a specified time window. 297 * 298 * @param grandparentKey The key of the profiling point grandparent entity. 299 * @param parentKind The kind of the profiling point parent. 300 * @param startTime The start time of the window, or null if unbounded. 301 * @param endTime The end time of the window, or null if unbounded. 302 * @return A filter to query for profiling points in the time window. 303 */ 304 public static Filter getProfilingTimeFilter( 305 Key grandparentKey, String parentKind, Long startTime, Long endTime) { 306 if (startTime == null && endTime == null) { 307 endTime = TimeUnit.MILLISECONDS.toMicros(System.currentTimeMillis()); 308 } 309 Filter startFilter = null; 310 Filter endFilter = null; 311 Filter filter = null; 312 if (startTime != null) { 313 Key minRunKey = KeyFactory.createKey(grandparentKey, parentKind, startTime); 314 Key startKey = 315 KeyFactory.createKey( 316 minRunKey, ProfilingPointRunEntity.KIND, String.valueOf((char) 0x0)); 317 startFilter = 318 new FilterPredicate( 319 Entity.KEY_RESERVED_PROPERTY, 320 FilterOperator.GREATER_THAN_OR_EQUAL, 321 startKey); 322 filter = startFilter; 323 } 324 if (endTime != null) { 325 Key maxRunKey = KeyFactory.createKey(grandparentKey, parentKind, endTime); 326 Key endKey = 327 KeyFactory.createKey( 328 maxRunKey, ProfilingPointRunEntity.KIND, String.valueOf((char) 0xff)); 329 endFilter = 330 new FilterPredicate( 331 Entity.KEY_RESERVED_PROPERTY, 332 FilterOperator.LESS_THAN_OR_EQUAL, 333 endKey); 334 filter = endFilter; 335 } 336 if (startFilter != null && endFilter != null) { 337 filter = CompositeFilterOperator.and(startFilter, endFilter); 338 } 339 return filter; 340 } 341 342 /** 343 * Get a filter for device information between a specified time window. 344 * 345 * @param grandparentKey The key of the device's grandparent entity. 346 * @param parentKind The kind of the device's parent. 347 * @param startTime The start time of the window, or null if unbounded. 348 * @param endTime The end time of the window, or null if unbounded. 349 * @return A filter to query for devices in the time window. 350 */ 351 public static Filter getDeviceTimeFilter( 352 Key grandparentKey, String parentKind, Long startTime, Long endTime) { 353 if (startTime == null && endTime == null) { 354 endTime = TimeUnit.MILLISECONDS.toMicros(System.currentTimeMillis()); 355 } 356 Filter startFilter = null; 357 Filter endFilter = null; 358 Filter filter = null; 359 if (startTime != null) { 360 Key minRunKey = KeyFactory.createKey(grandparentKey, parentKind, startTime); 361 Key startKey = KeyFactory.createKey(minRunKey, DeviceInfoEntity.KIND, 1); 362 startFilter = 363 new FilterPredicate( 364 Entity.KEY_RESERVED_PROPERTY, 365 FilterOperator.GREATER_THAN_OR_EQUAL, 366 startKey); 367 filter = startFilter; 368 } 369 if (endTime != null) { 370 Key maxRunKey = KeyFactory.createKey(grandparentKey, parentKind, endTime); 371 Key endKey = KeyFactory.createKey(maxRunKey, DeviceInfoEntity.KIND, Long.MAX_VALUE); 372 endFilter = 373 new FilterPredicate( 374 Entity.KEY_RESERVED_PROPERTY, 375 FilterOperator.LESS_THAN_OR_EQUAL, 376 endKey); 377 filter = endFilter; 378 } 379 if (startFilter != null && endFilter != null) { 380 filter = CompositeFilterOperator.and(startFilter, endFilter); 381 } 382 return filter; 383 } 384 385 /** 386 * Get the time range filter to apply to a query. 387 * 388 * @param testKey The key of the parent TestEntity object. 389 * @param kind The kind to use for the filters. 390 * @param startTime The start time in microseconds, or null if unbounded. 391 * @param endTime The end time in microseconds, or null if unbounded. 392 * @param testRunFilter The existing filter on test runs to apply, or null. 393 * @return A filter to apply on test runs. 394 */ 395 public static Filter getTimeFilter( 396 Key testKey, String kind, Long startTime, Long endTime, Filter testRunFilter) { 397 if (startTime == null && endTime == null) { 398 endTime = TimeUnit.MILLISECONDS.toMicros(System.currentTimeMillis()); 399 } 400 401 Filter startFilter = null; 402 Filter endFilter = null; 403 Filter filter = null; 404 if (startTime != null) { 405 Key startKey = KeyFactory.createKey(testKey, kind, startTime); 406 startFilter = 407 new FilterPredicate( 408 Entity.KEY_RESERVED_PROPERTY, 409 FilterOperator.GREATER_THAN_OR_EQUAL, 410 startKey); 411 filter = startFilter; 412 } 413 if (endTime != null) { 414 Key endKey = KeyFactory.createKey(testKey, kind, endTime); 415 endFilter = 416 new FilterPredicate( 417 Entity.KEY_RESERVED_PROPERTY, 418 FilterOperator.LESS_THAN_OR_EQUAL, 419 endKey); 420 filter = endFilter; 421 } 422 if (startFilter != null && endFilter != null) { 423 filter = CompositeFilterOperator.and(startFilter, endFilter); 424 } 425 if (testRunFilter != null) { 426 filter = CompositeFilterOperator.and(filter, testRunFilter); 427 } 428 return filter; 429 } 430 431 public static Filter getTimeFilter(Key testKey, String kind, Long startTime, Long endTime) { 432 return getTimeFilter(testKey, kind, startTime, endTime, null); 433 } 434 435 /** 436 * Get the list of keys matching the provided test filter and device filter. 437 * 438 * @param ancestorKey The ancestor key to use in the query. 439 * @param kind The entity kind to use in the test query. 440 * @param testFilters The filter list to apply to test runs (each having <=1 inequality filter). 441 * @param deviceFilter The filter to apply to associated devices. 442 * @param dir The sort direction of the returned list. 443 * @param maxSize The maximum number of entities to return. 444 * @return a list of keys matching the provided test and device filters. 445 */ 446 public static List<Key> getMatchingKeys( 447 Key ancestorKey, 448 String kind, 449 List<Filter> testFilters, 450 Filter deviceFilter, 451 Query.SortDirection dir, 452 int maxSize) { 453 DatastoreService datastore = DatastoreServiceFactory.getDatastoreService(); 454 Set<Key> matchingTestKeys = null; 455 Key minKey = null; 456 Key maxKey = null; 457 for (Filter testFilter : testFilters) { 458 Query testQuery = 459 new Query(kind).setAncestor(ancestorKey).setFilter(testFilter).setKeysOnly(); 460 Set<Key> filterMatches = new HashSet<>(); 461 FetchOptions ops = DatastoreHelper.getLargeBatchOptions(); 462 if (deviceFilter == null && testFilters.size() == 1) { 463 ops.limit(maxSize); 464 testQuery.addSort(Entity.KEY_RESERVED_PROPERTY, dir); 465 } 466 for (Entity testRunKey : datastore.prepare(testQuery).asIterable(ops)) { 467 filterMatches.add(testRunKey.getKey()); 468 if (maxKey == null || testRunKey.getKey().compareTo(maxKey) > 0) 469 maxKey = testRunKey.getKey(); 470 if (minKey == null || testRunKey.getKey().compareTo(minKey) < 0) 471 minKey = testRunKey.getKey(); 472 } 473 if (matchingTestKeys == null) { 474 matchingTestKeys = filterMatches; 475 } else { 476 matchingTestKeys = Sets.intersection(matchingTestKeys, filterMatches); 477 } 478 } 479 480 Set<Key> allMatchingKeys; 481 if (deviceFilter == null || matchingTestKeys.size() == 0) { 482 allMatchingKeys = matchingTestKeys; 483 } else { 484 deviceFilter = 485 CompositeFilterOperator.and( 486 deviceFilter, 487 getDeviceTimeFilter( 488 minKey.getParent(), 489 minKey.getKind(), 490 minKey.getId(), 491 maxKey.getId())); 492 allMatchingKeys = new HashSet<>(); 493 Query deviceQuery = 494 new Query(DeviceInfoEntity.KIND) 495 .setAncestor(ancestorKey) 496 .setFilter(deviceFilter) 497 .setKeysOnly(); 498 for (Entity device : 499 datastore 500 .prepare(deviceQuery) 501 .asIterable(DatastoreHelper.getLargeBatchOptions())) { 502 if (matchingTestKeys.contains(device.getKey().getParent())) { 503 allMatchingKeys.add(device.getKey().getParent()); 504 } 505 } 506 } 507 List<Key> gets = new ArrayList<>(allMatchingKeys); 508 if (dir == Query.SortDirection.DESCENDING) { 509 gets.sort(Comparator.reverseOrder()); 510 } else { 511 gets.sort(Comparator.naturalOrder()); 512 } 513 gets = gets.subList(0, Math.min(gets.size(), maxSize)); 514 return gets; 515 } 516 517 /** 518 * Set the request with the provided key/value attribute map. 519 * 520 * @param request The request whose attributes to set. 521 * @param parameterMap The map from key to (Object) String[] value whose entries to parse. 522 */ 523 public static void setAttributes(HttpServletRequest request, Map<String, Object> parameterMap) { 524 for (String key : parameterMap.keySet()) { 525 if (!FilterKey.isDeviceKey(key) && !FilterKey.isTestKey(key)) continue; 526 FilterKey filterKey = FilterKey.parse(key); 527 String[] values = (String[]) parameterMap.get(key); 528 if (values.length == 0) continue; 529 String stringValue = values[0]; 530 request.setAttribute(filterKey.keyString, new Gson().toJson(stringValue)); 531 } 532 } 533 } 534