[current results] Return query results sorted by name
Change page token to a base64-encoded pair of (name, configuration)
Change-Id: I7860aa7a1c5e031d80e7c545dc43d53dccefb7a0
Reviewed-on: https://dart-review.googlesource.com/c/dart_ci/+/162881
Reviewed-by: Alexander Thomas <athom@google.com>
diff --git a/current_results/lib/src/iterable.dart b/current_results/lib/src/iterable.dart
new file mode 100644
index 0000000..ff458ed
--- /dev/null
+++ b/current_results/lib/src/iterable.dart
@@ -0,0 +1,53 @@
+// 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:collection';
+
+extension IterableIterator<T> on Iterator<T> {
+ Iterable<T> get iterable => SingleUseIterable(this);
+}
+
+class SingleUseIterable<T> extends IterableBase<T> {
+ final Iterator<T> _iterator;
+ bool _used = false;
+ SingleUseIterable(this._iterator);
+
+ Iterator<T> get iterator {
+ if (_used) throw StateError('SingleUseIterable.iterator called twice');
+ _used = true;
+ return _iterator;
+ }
+}
+
+Iterable<T> merge<T, S extends Comparable>(
+ Iterable<T> a, Iterable<T> b, S Function(T) orderedBy) sync* {
+ final ita = a.iterator;
+ final itb = b.iterator;
+ if (!ita.moveNext()) {
+ yield* itb.iterable;
+ return;
+ }
+ if (!itb.moveNext()) {
+ yield ita.current;
+ yield* ita.iterable;
+ return;
+ }
+ for (;;) {
+ if (orderedBy(ita.current).compareTo(orderedBy(itb.current)) <= 0) {
+ yield ita.current;
+ if (!ita.moveNext()) {
+ yield itb.current;
+ yield* itb.iterable;
+ return;
+ }
+ } else {
+ yield itb.current;
+ if (!itb.moveNext()) {
+ yield ita.current;
+ yield* ita.iterable;
+ return;
+ }
+ }
+ }
+}
diff --git a/current_results/lib/src/result.dart b/current_results/lib/src/result.dart
index 3831306..52c2ec3 100644
--- a/current_results/lib/src/result.dart
+++ b/current_results/lib/src/result.dart
@@ -27,6 +27,8 @@
unique(other.expected),
Duration(milliseconds: other.timeMs));
+ Result.nameOnly(String name) : this(name, null, null, null, null, null, null);
+
static final uniqueStrings = <String>{};
static String unique(String string) =>
diff --git a/current_results/lib/src/slice.dart b/current_results/lib/src/slice.dart
index 6ddd550..e1baac0 100644
--- a/current_results/lib/src/slice.dart
+++ b/current_results/lib/src/slice.dart
@@ -10,11 +10,29 @@
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);
-int compareNamesPrefixMatchesBelow(Result a, Result b) =>
- a.name.compareTo(b.name) < 0 || a.name.startsWith(b.name) ? -1 : 1;
+/// 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.
@@ -92,11 +110,8 @@
query_api.GetResultsResponse results(query_api.GetResultsRequest query) {
final response = query_api.GetResultsResponse();
final limit = min(100000, query.pageSize == 0 ? 100000 : query.pageSize);
- // TODO(whesse): Change the implementation to return results sorted by test name first.
- // This will be less efficient, but it is much better for the clients.
- // The page token will change to a test name and configuration when this is done.
- final skip =
- max(0, query.pageToken.isEmpty ? 0 : int.parse(query.pageToken));
+ 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>();
@@ -117,59 +132,72 @@
testPrefixes.removeAt(i + 1);
}
}
+ if (testPrefixes.isEmpty) {
+ testPrefixes.add('');
+ }
final configurations =
(configurationSet.isEmpty ? _stored.keys : configurationSet).toList()
..sort();
- if (testPrefixes.isEmpty) {
- response.results.addAll(configurations
- .expand((configuration) => _stored[configuration])
- .map(Result.toApi)
- .skip(skip)
- .take(limit));
- if (response.results.length >= limit) {
- response.nextPageToken = (skip + response.results.length).toString();
+ 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;
- }
-
- var skipped = 0;
- for (final configuration in configurations) {
- final sorted = _stored[configuration];
- for (final testNamePrefix in testPrefixes) {
- if (response.results.length >= limit) break;
- final prefixResult =
- Result(testNamePrefix, null, null, null, null, null, null);
- var start =
- lowerBound<Result>(sorted, prefixResult, compare: compareNames);
- if (start < sorted.length &&
- sorted[start].name.startsWith(testNamePrefix)) {
- var end = start + 1;
- if (end < sorted.length &&
- sorted[end].name.startsWith(testNamePrefix)) {
- end = lowerBound<Result>(sorted, prefixResult,
- compare: compareNamesPrefixMatchesBelow);
- }
- if (end - start > skip - skipped) {
- // No-op if skipped == skip
- start += skip - skipped;
- skipped = skip;
- response.results.addAll(sorted
- .getRange(start, end)
- .map(Result.toApi)
- .take(limit - response.results.length));
- } else {
- skipped += end - start;
- }
- }
- }
- }
- if (response.results.length >= limit) {
- response.nextPageToken = (skip + response.results.length).toString();
}
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;
@@ -187,3 +215,22 @@
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,
+ })));
+ }
+}
diff --git a/current_results/pubspec.lock b/current_results/pubspec.lock
index 2f9ebb4..5b84ff6 100644
--- a/current_results/pubspec.lock
+++ b/current_results/pubspec.lock
@@ -36,6 +36,13 @@
url: "https://pub.dartlang.org"
source: hosted
version: "2.4.1"
+ boolean_selector:
+ dependency: transitive
+ description:
+ name: boolean_selector
+ url: "https://pub.dartlang.org"
+ source: hosted
+ version: "2.0.0"
charcode:
dependency: transitive
description:
@@ -57,6 +64,13 @@
url: "https://pub.dartlang.org"
source: hosted
version: "2.1.1"
+ coverage:
+ dependency: transitive
+ description:
+ name: coverage
+ url: "https://pub.dartlang.org"
+ source: hosted
+ version: "0.14.1"
crypto:
dependency: transitive
description:
@@ -141,6 +155,13 @@
url: "https://pub.dartlang.org"
source: hosted
version: "1.0.0"
+ http_multi_server:
+ dependency: transitive
+ description:
+ name: http_multi_server
+ url: "https://pub.dartlang.org"
+ source: hosted
+ version: "2.2.0"
http_parser:
dependency: transitive
description:
@@ -148,6 +169,13 @@
url: "https://pub.dartlang.org"
source: hosted
version: "3.1.4"
+ io:
+ dependency: transitive
+ description:
+ name: io
+ url: "https://pub.dartlang.org"
+ source: hosted
+ version: "0.3.4"
js:
dependency: transitive
description:
@@ -155,6 +183,20 @@
url: "https://pub.dartlang.org"
source: hosted
version: "0.6.2"
+ logging:
+ dependency: transitive
+ description:
+ name: logging
+ url: "https://pub.dartlang.org"
+ source: hosted
+ version: "0.11.4"
+ matcher:
+ dependency: transitive
+ description:
+ name: matcher
+ url: "https://pub.dartlang.org"
+ source: hosted
+ version: "0.12.9"
meta:
dependency: transitive
description:
@@ -162,6 +204,13 @@
url: "https://pub.dartlang.org"
source: hosted
version: "1.1.8"
+ mime:
+ dependency: transitive
+ description:
+ name: mime
+ url: "https://pub.dartlang.org"
+ source: hosted
+ version: "0.9.7"
node_interop:
dependency: transitive
description:
@@ -176,6 +225,13 @@
url: "https://pub.dartlang.org"
source: hosted
version: "1.1.1"
+ node_preamble:
+ dependency: transitive
+ description:
+ name: node_preamble
+ url: "https://pub.dartlang.org"
+ source: hosted
+ version: "1.4.12"
package_config:
dependency: transitive
description:
@@ -232,6 +288,41 @@
url: "https://pub.dartlang.org"
source: hosted
version: "0.7.5"
+ shelf_packages_handler:
+ dependency: transitive
+ description:
+ name: shelf_packages_handler
+ url: "https://pub.dartlang.org"
+ source: hosted
+ version: "2.0.0"
+ shelf_static:
+ dependency: transitive
+ description:
+ name: shelf_static
+ url: "https://pub.dartlang.org"
+ source: hosted
+ version: "0.2.8"
+ shelf_web_socket:
+ dependency: transitive
+ description:
+ name: shelf_web_socket
+ url: "https://pub.dartlang.org"
+ source: hosted
+ version: "0.2.3"
+ source_map_stack_trace:
+ dependency: transitive
+ description:
+ name: source_map_stack_trace
+ url: "https://pub.dartlang.org"
+ source: hosted
+ version: "2.0.0"
+ source_maps:
+ dependency: transitive
+ description:
+ name: source_maps
+ url: "https://pub.dartlang.org"
+ source: hosted
+ version: "0.10.9"
source_span:
dependency: transitive
description:
@@ -267,6 +358,27 @@
url: "https://pub.dartlang.org"
source: hosted
version: "1.1.0"
+ test:
+ dependency: "direct dev"
+ description:
+ name: test
+ url: "https://pub.dartlang.org"
+ source: hosted
+ version: "1.15.4"
+ test_api:
+ dependency: transitive
+ description:
+ name: test_api
+ url: "https://pub.dartlang.org"
+ source: hosted
+ version: "0.2.18"
+ test_core:
+ dependency: transitive
+ description:
+ name: test_core
+ url: "https://pub.dartlang.org"
+ source: hosted
+ version: "0.3.11+1"
typed_data:
dependency: transitive
description:
@@ -274,6 +386,13 @@
url: "https://pub.dartlang.org"
source: hosted
version: "1.1.6"
+ vm_service:
+ dependency: transitive
+ description:
+ name: vm_service
+ url: "https://pub.dartlang.org"
+ source: hosted
+ version: "4.2.0"
watcher:
dependency: transitive
description:
@@ -281,6 +400,20 @@
url: "https://pub.dartlang.org"
source: hosted
version: "0.9.7+15"
+ web_socket_channel:
+ dependency: transitive
+ description:
+ name: web_socket_channel
+ url: "https://pub.dartlang.org"
+ source: hosted
+ version: "1.1.0"
+ webkit_inspection_protocol:
+ dependency: transitive
+ description:
+ name: webkit_inspection_protocol
+ url: "https://pub.dartlang.org"
+ source: hosted
+ version: "0.7.3"
yaml:
dependency: transitive
description:
diff --git a/current_results/pubspec.yaml b/current_results/pubspec.yaml
index df22a24..a3904a5 100644
--- a/current_results/pubspec.yaml
+++ b/current_results/pubspec.yaml
@@ -15,3 +15,4 @@
dev_dependencies:
pedantic: ^1.8.0
protoc_plugin: 19.0.1
+ test: ^1.15.0
diff --git a/current_results/test/iterable_test.dart b/current_results/test/iterable_test.dart
new file mode 100644
index 0000000..974c4b9
--- /dev/null
+++ b/current_results/test/iterable_test.dart
@@ -0,0 +1,99 @@
+// 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 'package:test/test.dart';
+import 'package:current_results/src/iterable.dart';
+
+int intIdentity(int i) => i;
+
+void main() {
+ test('merge int lists', () {
+ final a = [1, 2, 4];
+ final b = [3];
+ final c = [2, 5];
+ final empty = <int>[];
+ expect(merge(a, b, intIdentity), [1, 2, 3, 4]);
+ expect(merge(a, c, intIdentity), [1, 2, 2, 4, 5]);
+ expect(merge(b, b, intIdentity), [3, 3]);
+ expect(merge(c, c, intIdentity), [2, 2, 5, 5]);
+ expect(merge(empty, empty, intIdentity), []);
+ expect(merge<int, int>([], [], intIdentity), []);
+ expect(merge(a, empty, intIdentity), a);
+ expect(merge(b, empty, intIdentity), b);
+ expect(merge(empty, a, intIdentity), a);
+ expect(merge(empty, b, intIdentity), b);
+ });
+
+ test('merge map lists', () {
+ final a = [
+ {'x': 1, 'y': 9},
+ {'x': 2},
+ {'x': 4}
+ ];
+ final b = [
+ {'x': 3, 'y': 8}
+ ];
+ final c = [
+ {'x': 2, 'y': 7},
+ {'x': 5}
+ ];
+ final empty = <Map<String, int>>[];
+
+ int xField(Map<String, int> map) => map['x'];
+ expect(merge(a, b, xField), [
+ {'x': 1, 'y': 9},
+ {'x': 2},
+ {'x': 3, 'y': 8},
+ {'x': 4},
+ ]);
+ expect(merge(a, c, xField), [
+ {'x': 1, 'y': 9},
+ {'x': 2},
+ {'x': 2, 'y': 7},
+ {'x': 4},
+ {'x': 5},
+ ]);
+ expect(merge(b, b, xField), [
+ {'x': 3, 'y': 8},
+ {'x': 3, 'y': 8},
+ ]);
+ expect(merge(c, c, xField), [
+ {'x': 2, 'y': 7},
+ {'x': 2, 'y': 7},
+ {'x': 5},
+ {'x': 5},
+ ]);
+ expect(merge(empty, empty, xField), []);
+ expect(merge<Map<String, int>, int>([], [], xField), []);
+ expect(merge(a, empty, xField), a);
+ expect(merge(b, empty, xField), b);
+ expect(merge(empty, a, xField), a);
+ expect(merge(empty, b, xField), b);
+ });
+
+ test("Iterable from Iterator", () {
+ final a = [
+ 1,
+ 2,
+ 4,
+ ];
+ expect(a.iterator.iterable, a);
+ expect((a.iterator..moveNext()).iterable, a.skip(1));
+ expect([].iterator.iterable, []);
+ expect(() => a.iterator.iterable..toList()..toList(), throwsStateError);
+ expect(a.getRange(1, 2).iterator.iterable.single, 2);
+ expect(a.iterator.iterable.iterator.iterable, a);
+ final m = {'x': 1, 'y': 2};
+ expect(m.keys.iterator.iterable, ['x', 'y']);
+ Iterable<Map<String, int>> unbounded() sync* {
+ for (;;) yield m;
+ }
+
+ expect(unbounded().iterator.iterable.take(2), [m, m]);
+ expect(a.iterator.iterable.length, 3); // hasLength matcher can't be used.
+ expect((() sync* {
+ yield* a.iterator.iterable;
+ })(), a);
+ });
+}
