current_results/lib/src/slice.dart - dart_ci - Git at Google

 // Copyright (c) 2020, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.

 import 'dart:convert';
 import 'dart:math';

 import 'package:collection/collection.dart';

 import 'package:current_results/src/result.dart';
 import 'package:current_results/src/generated/query.pb.dart' as query_api;
 import 'package:current_results/src/generated/result.pb.dart' as api;
 import 'package:current_results/src/iterable.dart';

 int compareNames(Result a, Result b) => a.name.compareTo(b.name);

 /// All result names before or starting with [prefix] are "before" prefix.
 int isAfterPrefix(Result a, Result prefix) {
   if (a.name.startsWith(prefix.name)) return -1;
   return compareNames(a, prefix);
 }

 /// Returns the range from [sorted] of Result entries that are at or after
 /// [startResult] and begin with [prefixResult].
 Iterable<Result> getResultRange(
     List<Result> sorted, Result startResult, Result prefixResult) {
   var start = lowerBound<Result>(sorted, startResult, compare: compareNames);
   if (start >= sorted.length) return [];
   if (!sorted[start].name.startsWith(prefixResult.name)) return [];
   var end = start + 1;
   if (end < sorted.length && sorted[end].name.startsWith(prefixResult.name)) {
     end = lowerBound<Result>(sorted, prefixResult, compare: isAfterPrefix);
   }
   return sorted.getRange(start, end);
 }

 /// Holds the test results for all configurations.
 /// Answers queries about the test results.
 /// Used for holding the current test results in memory.
 /// Can also be used to hold a snapshot of results data at a past time.
 class Slice {
   /// The current results, stored separately for each configuration in a
   /// list sorted by test name.
   final _stored = <String, List<Result>>{};

   /// A sorted list of all test names seen. Names are not removed from this list.
   List<String> testNames = [];
   int _size = 0;

   int get size => _size;

   void add(List<String> lines) {
     if (lines.isEmpty) return;
     final results = lines.map((line) => Result.fromApi(api.Result()
       ..mergeFromProto3Json(json.decode(line),
           supportNamesWithUnderscores: true)));
     final configuration = results.first.configuration;
     if (results.any((result) => result.configuration != configuration)) {
       print('Loaded results list with multiple configurations: '
           'first result: ${results.first}');
       return;
     }
     final sorted = results.toList()..sort(compareNames);
     _size -= _stored[configuration]?.length ?? 0;
     _stored[configuration] = sorted;
     _size += sorted.length;
     testNames = _mergeIfNeeded(testNames, sorted);
     print('latest results of $configuration: ${sorted.length} results '
         '(total: $_size)');
   }

   static List<String> _mergeIfNeeded(List<String> names, List<Result> sorted) {
     var i = 0;
     var j = 0;
     while (i < names.length && j < sorted.length) {
       final compare = names[i].compareTo(sorted[j].name);
       if (compare < 0) {
         i++;
       } else if (compare == 0) {
         i++;
         j++;
       } else
         break;
     }
     if (j == sorted.length) return names;

     // J points to the first unfound element in sorted.
     // I points to the first element in names greater than the unfound name.
     final result = names.sublist(0, i);
     while (i < names.length && j < sorted.length) {
       final compare = names[i].compareTo(sorted[j].name);
       if (compare <= 0) {
         result.add(names[i++]);
         if (compare == 0) j++;
       } else {
         result.add(sorted[j++].name);
       }
     }
     if (i < names.length) {
       result.addAll(names.getRange(i, names.length));
     }
     while (j < sorted.length) {
       result.add(sorted[j++].name);
     }
     print('Added ${result.length - names.length} new test names '
         '(total ${result.length})');
     return result;
   }

   query_api.GetResultsResponse results(query_api.GetResultsRequest query) {
     final response = query_api.GetResultsResponse();
     final limit = min(100000, query.pageSize == 0 ? 100000 : query.pageSize);
     final pageStart =
         query.pageToken.isEmpty ? null : PageStart.parse(query.pageToken);
     final filterTerms =
         query.filter.split(',').map((s) => s.trim()).where((s) => s.isNotEmpty);
     final configurationSet = Set<String>();
     final testPrefixes = <String>[];
     for (final prefix in filterTerms) {
       final matchingConfigurations = _stored.keys
           .where((configuration) => configuration.startsWith(prefix));
       if (matchingConfigurations.isEmpty) {
         testPrefixes.add(prefix);
       } else {
         configurationSet.addAll(matchingConfigurations);
       }
     }
     testPrefixes..sort();
     for (int i = 0; i < testPrefixes.length; ++i) {
       while (i + 1 < testPrefixes.length &&
           testPrefixes[i + 1].startsWith(testPrefixes[i])) {
         testPrefixes.removeAt(i + 1);
       }
     }
     if (testPrefixes.isEmpty) {
       testPrefixes.add('');
     }
     final configurations =
         (configurationSet.isEmpty ? _stored.keys : configurationSet).toList()
           ..sort();

     for (final prefix in testPrefixes) {
       response.results.addAll(getSortedResults(
               prefix, configurations, pageStart,
               needed: limit - response.results.length)
           .map(Result.toApi));
       if (response.results.length == limit) {
         response.nextPageToken = PageStart(
                 response.results.last.name, response.results.last.configuration)
             .encode();
         break;
       }
     }
     return response;
   }

   /// Returns up to [needed] results from the configurations in [configurations],
   /// with test names that start with [prefix], sorted by test name.
   /// If [pageStart] is not null, test names before pageStart.name are
   /// filtered out.
   List<Result> getSortedResults(
       String prefix, List<String> configurations, PageStart pageStart,
       {int needed}) {
     final prefixResult = Result.nameOnly(prefix);
     var startResult;
     if (pageStart == null || pageStart.test.compareTo(prefixResult.name) <= 0) {
       startResult = prefixResult;
     } else if (pageStart.test.startsWith(prefixResult.name)) {
       startResult = Result.nameOnly(pageStart.test);
     } else {
       return [];
     }

     var results = <Result>[];

     for (final configuration in configurations) {
       var configurationRange =
           getResultRange(_stored[configuration], startResult, prefixResult);

       if (configurationRange.isEmpty) continue;
       if (pageStart != null &&
           configurationRange.first.name == pageStart.test &&
           configuration.compareTo(pageStart.configuration) <= 0) {
         configurationRange = configurationRange.skip(1);
         if (configurationRange.isEmpty) continue;
       }
       if (results.isEmpty ||
           results.last.name.compareTo(configurationRange.first.name) <= 0) {
         // Optimization
         results.addAll(configurationRange.take(needed - results.length));
       } else {
         results =
             merge(results, configurationRange, (Result result) => result.name)
                 .take(needed)
                 .toList();
       }
     }
     return results;
   }

   query_api.ListTestsResponse listTests(query_api.ListTestsRequest query) {
     var limit = min(query.limit, 100000);
     if (limit == 0) limit = 20;
     final prefix = query.prefix;
     final response = query_api.ListTestsResponse();
     final start = lowerBound(testNames, prefix);
     final end = min(start + limit, testNames.length);
     for (final name in testNames.getRange(start, end)) {
       if (name.startsWith(prefix)) {
         response.names.add(name);
       } else {
         break;
       }
     }
     return response;
   }
 }

 class PageStart {
   final String test;
   final String configuration;

   PageStart(this.test, this.configuration);

   factory PageStart.parse(String token) {
     final decoded = jsonDecode(ascii.decode(base64Decode(token)));
     return PageStart(decoded['test'], decoded['configuration']);
   }

   String encode() {
     return base64UrlEncode(ascii.encode(jsonEncode({
       'test': test,
       'configuration': configuration,
     })));
   }
 }
	// Copyright (c) 2020, the Dart project authors. Please see the AUTHORS file
	// for details. All rights reserved. Use of this source code is governed by a
	// BSD-style license that can be found in the LICENSE file.

	import 'dart:convert';
	import 'dart:math';

	import 'package:collection/collection.dart';

	import 'package:current_results/src/result.dart';
	import 'package:current_results/src/generated/query.pb.dart' as query_api;
	import 'package:current_results/src/generated/result.pb.dart' as api;
	import 'package:current_results/src/iterable.dart';

	int compareNames(Result a, Result b) => a.name.compareTo(b.name);

	/// All result names before or starting with [prefix] are "before" prefix.
	int isAfterPrefix(Result a, Result prefix) {
	if (a.name.startsWith(prefix.name)) return -1;
	return compareNames(a, prefix);
	}

	/// Returns the range from [sorted] of Result entries that are at or after
	/// [startResult] and begin with [prefixResult].
	Iterable<Result> getResultRange(
	List<Result> sorted, Result startResult, Result prefixResult) {
	var start = lowerBound<Result>(sorted, startResult, compare: compareNames);
	if (start >= sorted.length) return [];
	if (!sorted[start].name.startsWith(prefixResult.name)) return [];
	var end = start + 1;
	if (end < sorted.length && sorted[end].name.startsWith(prefixResult.name)) {
	end = lowerBound<Result>(sorted, prefixResult, compare: isAfterPrefix);
	}
	return sorted.getRange(start, end);
	}

	/// Holds the test results for all configurations.
	/// Answers queries about the test results.
	/// Used for holding the current test results in memory.
	/// Can also be used to hold a snapshot of results data at a past time.
	class Slice {
	/// The current results, stored separately for each configuration in a
	/// list sorted by test name.
	final _stored = <String, List<Result>>{};

	/// A sorted list of all test names seen. Names are not removed from this list.
	List<String> testNames = [];
	int _size = 0;

	int get size => _size;

	void add(List<String> lines) {
	if (lines.isEmpty) return;
	final results = lines.map((line) => Result.fromApi(api.Result()
	..mergeFromProto3Json(json.decode(line),
	supportNamesWithUnderscores: true)));
	final configuration = results.first.configuration;
	if (results.any((result) => result.configuration != configuration)) {
	print('Loaded results list with multiple configurations: '
	'first result: ${results.first}');
	return;
	}
	final sorted = results.toList()..sort(compareNames);
	_size -= _stored[configuration]?.length ?? 0;
	_stored[configuration] = sorted;
	_size += sorted.length;
	testNames = _mergeIfNeeded(testNames, sorted);
	print('latest results of $configuration: ${sorted.length} results '
	'(total: $_size)');
	}

	static List<String> _mergeIfNeeded(List<String> names, List<Result> sorted) {
	var i = 0;
	var j = 0;
	while (i < names.length && j < sorted.length) {
	final compare = names[i].compareTo(sorted[j].name);
	if (compare < 0) {
	i++;
	} else if (compare == 0) {
	i++;
	j++;
	} else
	break;
	}
	if (j == sorted.length) return names;

	// J points to the first unfound element in sorted.
	// I points to the first element in names greater than the unfound name.
	final result = names.sublist(0, i);
	while (i < names.length && j < sorted.length) {
	final compare = names[i].compareTo(sorted[j].name);
	if (compare <= 0) {
	result.add(names[i++]);
	if (compare == 0) j++;
	} else {
	result.add(sorted[j++].name);
	}
	}
	if (i < names.length) {
	result.addAll(names.getRange(i, names.length));
	}
	while (j < sorted.length) {
	result.add(sorted[j++].name);
	}
	print('Added ${result.length - names.length} new test names '
	'(total ${result.length})');
	return result;
	}

	query_api.GetResultsResponse results(query_api.GetResultsRequest query) {
	final response = query_api.GetResultsResponse();
	final limit = min(100000, query.pageSize == 0 ? 100000 : query.pageSize);
	final pageStart =
	query.pageToken.isEmpty ? null : PageStart.parse(query.pageToken);
	final filterTerms =
	query.filter.split(',').map((s) => s.trim()).where((s) => s.isNotEmpty);
	final configurationSet = Set<String>();
	final testPrefixes = <String>[];
	for (final prefix in filterTerms) {
	final matchingConfigurations = _stored.keys
	.where((configuration) => configuration.startsWith(prefix));
	if (matchingConfigurations.isEmpty) {
	testPrefixes.add(prefix);
	} else {
	configurationSet.addAll(matchingConfigurations);
	}
	}
	testPrefixes..sort();
	for (int i = 0; i < testPrefixes.length; ++i) {
	while (i + 1 < testPrefixes.length &&
	testPrefixes[i + 1].startsWith(testPrefixes[i])) {
	testPrefixes.removeAt(i + 1);
	}
	}
	if (testPrefixes.isEmpty) {
	testPrefixes.add('');
	}
	final configurations =
	(configurationSet.isEmpty ? _stored.keys : configurationSet).toList()
	..sort();

	for (final prefix in testPrefixes) {
	response.results.addAll(getSortedResults(
	prefix, configurations, pageStart,
	needed: limit - response.results.length)
	.map(Result.toApi));
	if (response.results.length == limit) {
	response.nextPageToken = PageStart(
	response.results.last.name, response.results.last.configuration)
	.encode();
	break;
	}
	}
	return response;
	}

	/// Returns up to [needed] results from the configurations in [configurations],
	/// with test names that start with [prefix], sorted by test name.
	/// If [pageStart] is not null, test names before pageStart.name are
	/// filtered out.
	List<Result> getSortedResults(
	String prefix, List<String> configurations, PageStart pageStart,
	{int needed}) {
	final prefixResult = Result.nameOnly(prefix);
	var startResult;
	if (pageStart == null \|\| pageStart.test.compareTo(prefixResult.name) <= 0) {
	startResult = prefixResult;
	} else if (pageStart.test.startsWith(prefixResult.name)) {
	startResult = Result.nameOnly(pageStart.test);
	} else {
	return [];
	}

	var results = <Result>[];

	for (final configuration in configurations) {
	var configurationRange =
	getResultRange(_stored[configuration], startResult, prefixResult);

	if (configurationRange.isEmpty) continue;
	if (pageStart != null &&
	configurationRange.first.name == pageStart.test &&
	configuration.compareTo(pageStart.configuration) <= 0) {
	configurationRange = configurationRange.skip(1);
	if (configurationRange.isEmpty) continue;
	}
	if (results.isEmpty \|\|
	results.last.name.compareTo(configurationRange.first.name) <= 0) {
	// Optimization
	results.addAll(configurationRange.take(needed - results.length));
	} else {
	results =
	merge(results, configurationRange, (Result result) => result.name)
	.take(needed)
	.toList();
	}
	}
	return results;
	}

	query_api.ListTestsResponse listTests(query_api.ListTestsRequest query) {
	var limit = min(query.limit, 100000);
	if (limit == 0) limit = 20;
	final prefix = query.prefix;
	final response = query_api.ListTestsResponse();
	final start = lowerBound(testNames, prefix);
	final end = min(start + limit, testNames.length);
	for (final name in testNames.getRange(start, end)) {
	if (name.startsWith(prefix)) {
	response.names.add(name);
	} else {
	break;
	}
	}
	return response;
	}
	}

	class PageStart {
	final String test;
	final String configuration;

	PageStart(this.test, this.configuration);

	factory PageStart.parse(String token) {
	final decoded = jsonDecode(ascii.decode(base64Decode(token)));
	return PageStart(decoded['test'], decoded['configuration']);
	}

	String encode() {
	return base64UrlEncode(ascii.encode(jsonEncode({
	'test': test,
	'configuration': configuration,
	})));
	}
	}