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