[ledger][sledge] Add inequalities to Queries.
Queries now store a mapping from fieldPaths to QueryFieldComparison.
A helper to facilitate building queries will be introduced in follow up
CLs.
TEST=dart_sledge_tests
Change-Id: I958ed7a079889d83a5203f6ea681094cc5bad51a
diff --git a/public/dart/sledge/lib/sledge.dart b/public/dart/sledge/lib/sledge.dart
index 4d482b3..5a8b297 100644
--- a/public/dart/sledge/lib/sledge.dart
+++ b/public/dart/sledge/lib/sledge.dart
@@ -7,6 +7,7 @@
export 'src/document/document_id.dart';
export 'src/query/index_definition.dart';
export 'src/query/query.dart';
+export 'src/query/query_field_comparison.dart';
export 'src/schema/base_type.dart';
export 'src/schema/schema.dart';
export 'src/sledge.dart';
diff --git a/public/dart/sledge/lib/src/conflict_resolver/conflict_resolver.dart b/public/dart/sledge/lib/src/conflict_resolver/conflict_resolver.dart
index 5c7483d..a22e0d7 100644
--- a/public/dart/sledge/lib/src/conflict_resolver/conflict_resolver.dart
+++ b/public/dart/sledge/lib/src/conflict_resolver/conflict_resolver.dart
@@ -2,7 +2,6 @@
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
-// import 'dart:async';
import 'dart:typed_data';
import 'package:fidl/fidl.dart';
diff --git a/public/dart/sledge/lib/src/query/field_value.dart b/public/dart/sledge/lib/src/query/field_value.dart
index 988c99d..edf14fd 100644
--- a/public/dart/sledge/lib/src/query/field_value.dart
+++ b/public/dart/sledge/lib/src/query/field_value.dart
@@ -13,17 +13,12 @@
import '../schema/types/trivial_types.dart';
/// Stores the value of a field in queries.
-abstract class FieldValue {
+abstract class FieldValue implements Comparable<Value> {
/// The hash of the field's value.
Uint8List get hash;
/// Returns whether this can be compared to [type].
bool comparableTo(BaseType type);
-
- /// Returns whether this is equal to [value].
- /// If `value` is not instantiated from a BaseType comparable to this,
- /// an exception is thrown.
- bool equalsTo(Value value);
}
/// Template to ease the implementation of FieldValue specializations.
@@ -51,14 +46,12 @@
}
@override
- bool equalsTo(Value documentValue) {
+ int compareTo(Value documentValue) {
if (documentValue is PosNegCounterValue<int>) {
- PosNegCounterValue<int> downcastedValue = documentValue;
- return _value == downcastedValue.value;
+ return _value.compareTo(documentValue.value);
}
if (documentValue is LastOneWinsValue<int>) {
- LastOneWinsValue<int> downcastedValue = documentValue;
- return _value == downcastedValue.value;
+ return _value.compareTo(documentValue.value);
}
throw new ArgumentError('`documentValue` is not comparable to a integer.');
}
diff --git a/public/dart/sledge/lib/src/query/query.dart b/public/dart/sledge/lib/src/query/query.dart
index 0e97653..62bd39b 100644
--- a/public/dart/sledge/lib/src/query/query.dart
+++ b/public/dart/sledge/lib/src/query/query.dart
@@ -9,35 +9,37 @@
import '../schema/schema.dart';
import '../storage/kv_encoding.dart' as sledge_storage;
import '../uint8list_ops.dart' as utils;
-import 'field_value.dart';
+import 'query_field_comparison.dart';
/// Represents a query for retrieving documents from Sledge.
-/// TODO: Add support for inequality.
class Query {
final Schema _schema;
- /// Stores the value each document's field needs to have in order to be
- /// returned by the query.
- SplayTreeMap<String, FieldValue> _equalities;
+ /// Stores a QueryFieldComparison each document's field needs respect in
+ /// order to be returned by the query.
+ SplayTreeMap<String, QueryFieldComparison> _comparisons;
/// Default constructor.
- /// `schema` describes the type of documents the query returns.
- /// `equalities` associates field names with their expected values.
- /// Throws an exception if `equalities` references a field not part of
- /// `schema`.
- Query(this._schema, {Map<String, FieldValue> equalities}) {
- // TODO: throw an exception if `equalities` references fields not part of
- // `schema`.
- equalities ??= <String, FieldValue>{};
- equalities.forEach((fieldPath, fieldValue) {
- final expectedType = schema.fieldAtPath(fieldPath);
- if (!fieldValue.comparableTo(expectedType)) {
- String runtimeType = expectedType.runtimeType.toString();
- throw new ArgumentError(
- 'Field `$fieldPath` of type `$runtimeType` is not comparable with `$fieldValue`.');
+ /// [schema] describes the type of documents the query returns.
+ /// [comparisons] associates field names with constraints documents returned
+ /// by the query respects.
+ /// Throws an exception if [comparisons] references a field not part of
+ /// [schema], or if multiple inequalities are present.
+ Query(this._schema, {Map<String, QueryFieldComparison> comparisons}) {
+ comparisons ??= <String, QueryFieldComparison>{};
+ final fieldsWithInequalities = <String>[];
+ comparisons.forEach((fieldPath, comparison) {
+ if (comparison.comparisonType != ComparisonType.equal) {
+ fieldsWithInequalities.add(fieldPath);
}
+ _checkComparisonWithField(fieldPath, comparison);
});
- _equalities = new SplayTreeMap<String, FieldValue>.from(equalities);
+ if (fieldsWithInequalities.length > 1) {
+ throw new ArgumentError(
+ 'Queries can have at most one inequality. Inequalities founds: $fieldsWithInequalities.');
+ }
+ _comparisons =
+ new SplayTreeMap<String, QueryFieldComparison>.from(comparisons);
}
/// The Schema of documents returned by this query.
@@ -46,7 +48,7 @@
/// Returns whether this query filters the Documents based on the content of
/// their fields.
bool filtersDocuments() {
- return _equalities.isNotEmpty;
+ return _comparisons.isNotEmpty;
}
/// The prefix of the key values encoding the index that helps compute the
@@ -54,16 +56,20 @@
/// Must only be called if `filtersDocuments()` returns true.
Uint8List prefixInIndex() {
assert(filtersDocuments());
- List<Uint8List> hashes = <Uint8List>[];
- _equalities.forEach((field, value) {
- hashes.add(value.hash);
+ final equalityValueHashes = <Uint8List>[];
+ _comparisons.forEach((field, comparison) {
+ if (comparison.comparisonType == ComparisonType.equal) {
+ equalityValueHashes.add(utils.getUint8ListFromString(field));
+ }
});
- Uint8List equalityHash = utils.hash(utils.concatListOfUint8Lists(hashes));
+ Uint8List equalityHash =
+ utils.hash(utils.concatListOfUint8Lists(equalityValueHashes));
// TODO: get the correct index hash.
Uint8List indexHash = new Uint8List(20);
+ // TODO: take into account the inequality to compute the prefix.
Uint8List prefix = utils.concatListOfUint8Lists([
sledge_storage.prefixForType(sledge_storage.KeyValueType.indexEntry),
indexHash,
@@ -81,11 +87,21 @@
throw new ArgumentError(
'The Document `doc` is of a incorrect Schema type.');
}
- for (final fieldName in _equalities.keys) {
- if (!_equalities[fieldName].equalsTo(doc[fieldName])) {
+ for (final fieldName in _comparisons.keys) {
+ if (!_comparisons[fieldName].valueMatchesComparison(doc[fieldName])) {
return false;
}
}
return true;
}
+
+ void _checkComparisonWithField(
+ String fieldPath, QueryFieldComparison comparison) {
+ final expectedType = _schema.fieldAtPath(fieldPath);
+ if (!comparison.comparisonValue.comparableTo(expectedType)) {
+ String runtimeType = expectedType.runtimeType.toString();
+ throw new ArgumentError(
+ 'Field `$fieldPath` of type `$runtimeType` is not comparable with `$comparison.comparisonValue`.');
+ }
+ }
}
diff --git a/public/dart/sledge/lib/src/query/query_field_comparison.dart b/public/dart/sledge/lib/src/query/query_field_comparison.dart
new file mode 100644
index 0000000..df7d543
--- /dev/null
+++ b/public/dart/sledge/lib/src/query/query_field_comparison.dart
@@ -0,0 +1,60 @@
+// Copyright 2018 The Fuchsia Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style license that can be
+// found in the LICENSE file.
+
+import '../document/value.dart';
+import 'field_value.dart';
+
+/// The types of comparison possible in queries on the field of a document.
+enum ComparisonType {
+ /// Field must be less than a given value.
+ less,
+
+ /// Field must be less than or equal to a given value.
+ lessOrEqual,
+
+ /// Field must be equal to a given value.
+ equal,
+
+ /// Field must be greater than or equal to a given value.
+ greaterOrEqual,
+
+ /// Field must be greater than a given value.
+ greater
+}
+
+/// Holds the information necessary to compare to a Value:
+/// It holds a comparison type (<, <=, ==, >, >=), and a value (e.g. 42).
+class QueryFieldComparison {
+ FieldValue _comparisonValue;
+ ComparisonType _comparisonType;
+
+ /// Default constructor.
+ QueryFieldComparison(this._comparisonValue, this._comparisonType);
+
+ /// Returns how [value] compares to the value stored in [this].
+ bool valueMatchesComparison(Value value) {
+ int comparisonResult = _comparisonValue.compareTo(value);
+
+ // the value in [_comparisonValue] is equal to [value].
+ if (comparisonResult == 0) {
+ return _comparisonType == ComparisonType.equal ||
+ _comparisonType == ComparisonType.lessOrEqual ||
+ _comparisonType == ComparisonType.greaterOrEqual;
+ }
+ // the value in [_comparisonValue] is greater than [value].
+ if (comparisonResult > 0) {
+ return _comparisonType == ComparisonType.lessOrEqual ||
+ _comparisonType == ComparisonType.less;
+ }
+ // the value in [_comparisonValue] is less than [value].
+ return _comparisonType == ComparisonType.greaterOrEqual ||
+ _comparisonType == ComparisonType.greater;
+ }
+
+ /// Returns the value stored in [this].
+ FieldValue get comparisonValue => _comparisonValue;
+
+ /// Returns the type of comparison.
+ ComparisonType get comparisonType => _comparisonType;
+}
diff --git a/public/dart/sledge/lib/src/uint8list_ops.dart b/public/dart/sledge/lib/src/uint8list_ops.dart
index 87fbf99..b36f5e0 100644
--- a/public/dart/sledge/lib/src/uint8list_ops.dart
+++ b/public/dart/sledge/lib/src/uint8list_ops.dart
@@ -10,6 +10,8 @@
import 'package:collection/collection.dart';
import 'package:crypto/crypto.dart';
+import 'document/values/converter.dart';
+
// TODO: consider short function names and importing with prefix.
/// Concatenate two byte arrays.
@@ -47,6 +49,12 @@
return new Uint8List.fromList(utf8.encode(string));
}
+/// Returns a Uint8List created from the binary encoding of [number].
+Uint8List getUint8ListFromNumber(num number) {
+ IntConverter converter = new IntConverter();
+ return converter.serialize(number);
+}
+
/// Returns a new HashMap with Uint8Lists as a keys.
/// Note: The type T is enforced only at compile time.
HashMap<Uint8List, T> newUint8ListMap<T>() {
diff --git a/public/dart/sledge/test/get_documents_test.dart b/public/dart/sledge/test/get_documents_test.dart
index e8c75ef..3a37a8d 100644
--- a/public/dart/sledge/test/get_documents_test.dart
+++ b/public/dart/sledge/test/get_documents_test.dart
@@ -78,8 +78,11 @@
Schema schema = _newSchema3();
Sledge sledge = newSledgeForTesting();
await sledge.runInTransaction(() async {
- final equalities = <String, FieldValue>{'i1': new IntFieldValue(42)};
- final query = new Query(schema, equalities: equalities);
+ final comparisons = <String, QueryFieldComparison>{
+ 'i1': new QueryFieldComparison(
+ new IntFieldValue(42), ComparisonType.equal)
+ };
+ final query = new Query(schema, comparisons: comparisons);
final docs = await sledge.getDocuments(query);
expect(docs.length, equals(0));
});
@@ -111,33 +114,84 @@
doc5['i1'].value = 2;
doc5['i2'].value = 20;
});
- // Run 3 queries and verify that the results are correct.
+ // Verify the resuts of queries with equalities.
await sledge.runInTransaction(() async {
{
- final equalities = <String, FieldValue>{'i1': new IntFieldValue(1)};
- final query = new Query(schema, equalities: equalities);
+ final comparisons = <String, QueryFieldComparison>{
+ 'i1': new QueryFieldComparison(
+ new IntFieldValue(1), ComparisonType.equal)
+ };
+ final query = new Query(schema, comparisons: comparisons);
final docs = await sledge.getDocuments(query);
expect(docs.length, equals(2));
expect(docs, containsAll([doc1, doc3]));
}
{
- final equalities = <String, FieldValue>{'i2': new IntFieldValue(30)};
- final query = new Query(schema, equalities: equalities);
+ final comparisons = <String, QueryFieldComparison>{
+ 'i2': new QueryFieldComparison(
+ new IntFieldValue(30), ComparisonType.equal)
+ };
+ final query = new Query(schema, comparisons: comparisons);
final docs = await sledge.getDocuments(query);
expect(docs.length, equals(2));
expect(docs, containsAll([doc3, doc4]));
}
{
- final equalities = <String, FieldValue>{
- 'i1': new IntFieldValue(2),
- 'i2': new IntFieldValue(30)
+ final comparisons = <String, QueryFieldComparison>{
+ 'i1': new QueryFieldComparison(
+ new IntFieldValue(2), ComparisonType.equal),
+ 'i2': new QueryFieldComparison(
+ new IntFieldValue(30), ComparisonType.equal)
};
- final query = new Query(schema, equalities: equalities);
+ final query = new Query(schema, comparisons: comparisons);
final docs = await sledge.getDocuments(query);
expect(docs.length, equals(1));
expect(docs, containsAll([doc4]));
}
});
+ // Verify the resuts of queries with inequalities.
+ await sledge.runInTransaction(() async {
+ final less = <String, QueryFieldComparison>{
+ 'i2': new QueryFieldComparison(
+ new IntFieldValue(20), ComparisonType.less)
+ };
+ final lessOrEqual = <String, QueryFieldComparison>{
+ 'i2': new QueryFieldComparison(
+ new IntFieldValue(20), ComparisonType.lessOrEqual)
+ };
+ final greaterOrEqual = <String, QueryFieldComparison>{
+ 'i2': new QueryFieldComparison(
+ new IntFieldValue(20), ComparisonType.greaterOrEqual)
+ };
+ final greater = <String, QueryFieldComparison>{
+ 'i2': new QueryFieldComparison(
+ new IntFieldValue(20), ComparisonType.greater)
+ };
+ {
+ final docs =
+ await sledge.getDocuments(new Query(schema, comparisons: less));
+ expect(docs.length, equals(1));
+ expect(docs, containsAll([doc1]));
+ }
+ {
+ final docs = await sledge
+ .getDocuments(new Query(schema, comparisons: lessOrEqual));
+ expect(docs.length, equals(3));
+ expect(docs, containsAll([doc1, doc2, doc5]));
+ }
+ {
+ final docs = await sledge
+ .getDocuments(new Query(schema, comparisons: greaterOrEqual));
+ expect(docs.length, equals(4));
+ expect(docs, containsAll([doc2, doc3, doc4, doc5]));
+ }
+ {
+ final docs = await sledge
+ .getDocuments(new Query(schema, comparisons: greater));
+ expect(docs.length, equals(2));
+ expect(docs, containsAll([doc3, doc4]));
+ }
+ });
});
});
}
diff --git a/public/dart/sledge/test/query/query_test.dart b/public/dart/sledge/test/query/query_test.dart
index 048604e..a270231 100644
--- a/public/dart/sledge/test/query/query_test.dart
+++ b/public/dart/sledge/test/query/query_test.dart
@@ -13,6 +13,7 @@
final schemaDescription = <String, BaseType>{
'a': new Integer(),
'b': new LastOneWinsString(),
+ 'c': new Integer(),
};
return new Schema(schemaDescription);
}
@@ -29,47 +30,90 @@
test('Verify that creating invalid queries throws an error', () async {
Schema schema = _newSchema();
- final equalitiesWithNonExistantField = <String, FieldValue>{
- 'foo': new IntFieldValue(42)
+
+ // Test invalid comparisons
+ final comparisonWithNonExistantField = <String, QueryFieldComparison>{
+ 'foo':
+ new QueryFieldComparison(new IntFieldValue(42), ComparisonType.equal)
};
- expect(() => new Query(schema, equalities: equalitiesWithNonExistantField),
+ expect(() => new Query(schema, comparisons: comparisonWithNonExistantField),
throwsArgumentError);
- final equalitiesWithWrongType = <String, FieldValue>{
- 'b': new IntFieldValue(42)
+ final comparisonWithWrongType = <String, QueryFieldComparison>{
+ 'b': new QueryFieldComparison(new IntFieldValue(42), ComparisonType.equal)
};
- expect(() => new Query(schema, equalities: equalitiesWithWrongType),
+ expect(() => new Query(schema, comparisons: comparisonWithWrongType),
+ throwsArgumentError);
+
+ // Test too many inequalities
+ final comparisonWithMultipleInequalities = <String, QueryFieldComparison>{
+ 'a': new QueryFieldComparison(
+ new IntFieldValue(42), ComparisonType.greater),
+ 'c': new QueryFieldComparison(
+ new IntFieldValue(42), ComparisonType.greater)
+ };
+ expect(
+ () =>
+ new Query(schema, comparisons: comparisonWithMultipleInequalities),
throwsArgumentError);
});
test('Verify `filtersDocuments`', () async {
Schema schema = _newSchema();
- final equalities = <String, FieldValue>{'a': new IntFieldValue(42)};
- final query2 = new Query(schema);
- expect(query2.filtersDocuments(), equals(false));
- final query1 = new Query(schema, equalities: equalities);
- expect(query1.filtersDocuments(), equals(true));
+ final query1 = new Query(schema);
+ expect(query1.filtersDocuments(), equals(false));
+
+ // Test with equalities
+ final equality = <String, QueryFieldComparison>{
+ 'a': new QueryFieldComparison(new IntFieldValue(42), ComparisonType.equal)
+ };
+ final query2 = new Query(schema, comparisons: equality);
+ expect(query2.filtersDocuments(), equals(true));
+
+ // Test with inequality
+ final inequality = <String, QueryFieldComparison>{
+ 'a': new QueryFieldComparison(
+ new IntFieldValue(42), ComparisonType.greater)
+ };
+ final query3 = new Query(schema, comparisons: inequality);
+ expect(query3.filtersDocuments(), equals(true));
});
test('Verify `documentMatchesQuery`', () async {
Sledge sledge = newSledgeForTesting();
Schema schema = _newSchema();
- final equalities = <String, FieldValue>{'a': new IntFieldValue(42)};
- final query1 = new Query(schema);
- final query2 = new Query(schema, equalities: equalities);
+ final equality = <String, QueryFieldComparison>{
+ 'a': new QueryFieldComparison(new IntFieldValue(42), ComparisonType.equal)
+ };
+ final inequality = <String, QueryFieldComparison>{
+ 'a': new QueryFieldComparison(
+ new IntFieldValue(42), ComparisonType.greater)
+ };
+ final queryWithoutFilter = new Query(schema);
+ final queryWithEqualities = new Query(schema, comparisons: equality);
+ final queryWithInequality = new Query(schema, comparisons: inequality);
await sledge.runInTransaction(() async {
Document doc1 = await sledge.getDocument(new DocumentId(schema));
doc1['a'].value = 1;
Document doc2 = await sledge.getDocument(new DocumentId(schema));
doc2['a'].value = 42;
- Document doc3 = await sledge.getDocument(new DocumentId(_newSchema2()));
- doc3['a'].value = 42;
- expect(query1.documentMatchesQuery(doc1), equals(true));
- expect(query1.documentMatchesQuery(doc2), equals(true));
- expect(query2.documentMatchesQuery(doc1), equals(false));
- expect(query2.documentMatchesQuery(doc2), equals(true));
- expect(() => query1.documentMatchesQuery(doc3), throwsArgumentError);
- expect(() => query2.documentMatchesQuery(doc3), throwsArgumentError);
+ Document doc3 = await sledge.getDocument(new DocumentId(schema));
+ doc3['a'].value = 43;
+ Document doc4 = await sledge.getDocument(new DocumentId(_newSchema2()));
+ doc4['a'].value = 42;
+ expect(queryWithoutFilter.documentMatchesQuery(doc1), equals(true));
+ expect(queryWithoutFilter.documentMatchesQuery(doc2), equals(true));
+ expect(queryWithEqualities.documentMatchesQuery(doc1), equals(false));
+ expect(queryWithEqualities.documentMatchesQuery(doc2), equals(true));
+ expect(queryWithInequality.documentMatchesQuery(doc1), equals(false));
+ expect(queryWithInequality.documentMatchesQuery(doc2), equals(false));
+ expect(queryWithInequality.documentMatchesQuery(doc3), equals(true));
+ expect(() => queryWithoutFilter.documentMatchesQuery(doc4),
+ throwsArgumentError);
+ expect(() => queryWithEqualities.documentMatchesQuery(doc4),
+ throwsArgumentError);
+ expect(() => queryWithInequality.documentMatchesQuery(doc4),
+ throwsArgumentError);
});
});
}
