From cf630bfee60694f9bf1577972df169badda0b6e0 Mon Sep 17 00:00:00 2001 From: Gil Date: Wed, 21 Mar 2018 18:43:29 -0700 Subject: Port FSTLevelDBKey to C++ (#937) --- .../Example/Firestore.xcodeproj/project.pbxproj | 12 + Firestore/Source/Core/FSTTypes.h | 6 +- Firestore/core/CMakeLists.txt | 2 + .../src/firebase/firestore/local/CMakeLists.txt | 25 + .../src/firebase/firestore/local/leveldb_key.cc | 769 +++++++++++++++++++++ .../src/firebase/firestore/local/leveldb_key.h | 485 +++++++++++++ .../src/firebase/firestore/local/leveldb_util.h | 43 ++ .../core/src/firebase/firestore/model/types.h | 12 +- .../core/src/firebase/firestore/util/string_util.h | 9 +- .../test/firebase/firestore/local/CMakeLists.txt | 22 + .../firebase/firestore/local/leveldb_key_test.cc | 364 ++++++++++ 11 files changed, 1744 insertions(+), 5 deletions(-) create mode 100644 Firestore/core/src/firebase/firestore/local/CMakeLists.txt create mode 100644 Firestore/core/src/firebase/firestore/local/leveldb_key.cc create mode 100644 Firestore/core/src/firebase/firestore/local/leveldb_key.h create mode 100644 Firestore/core/src/firebase/firestore/local/leveldb_util.h create mode 100644 Firestore/core/test/firebase/firestore/local/CMakeLists.txt create mode 100644 Firestore/core/test/firebase/firestore/local/leveldb_key_test.cc (limited to 'Firestore') diff --git a/Firestore/Example/Firestore.xcodeproj/project.pbxproj b/Firestore/Example/Firestore.xcodeproj/project.pbxproj index f80bd8c..28627ec 100644 --- a/Firestore/Example/Firestore.xcodeproj/project.pbxproj +++ b/Firestore/Example/Firestore.xcodeproj/project.pbxproj @@ -108,6 +108,7 @@ 5492E0C92021557E00B64F25 /* FSTRemoteEventTests.mm in Sources */ = {isa = PBXBuildFile; fileRef = 5492E0C32021557E00B64F25 /* FSTRemoteEventTests.mm */; }; 5492E0CA2021557E00B64F25 /* FSTWatchChangeTests.mm in Sources */ = {isa = PBXBuildFile; fileRef = 5492E0C52021557E00B64F25 /* FSTWatchChangeTests.mm */; }; 5495EB032040E90200EBA509 /* CodableGeoPointTests.swift in Sources */ = {isa = PBXBuildFile; fileRef = 5495EB022040E90200EBA509 /* CodableGeoPointTests.swift */; }; + 54995F6F205B6E12004EFFA0 /* leveldb_key_test.cc in Sources */ = {isa = PBXBuildFile; fileRef = 54995F6E205B6E12004EFFA0 /* leveldb_key_test.cc */; }; 54C2294F1FECABAE007D065B /* log_test.cc in Sources */ = {isa = PBXBuildFile; fileRef = 54C2294E1FECABAE007D065B /* log_test.cc */; }; 54DA12A61F315EE100DD57A1 /* collection_spec_test.json in Resources */ = {isa = PBXBuildFile; fileRef = 54DA129C1F315EE100DD57A1 /* collection_spec_test.json */; }; 54DA12A71F315EE100DD57A1 /* existence_filter_spec_test.json in Resources */ = {isa = PBXBuildFile; fileRef = 54DA129D1F315EE100DD57A1 /* existence_filter_spec_test.json */; }; @@ -324,6 +325,7 @@ 5492E0C42021557E00B64F25 /* FSTWatchChange+Testing.h */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.h; path = "FSTWatchChange+Testing.h"; sourceTree = ""; }; 5492E0C52021557E00B64F25 /* FSTWatchChangeTests.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = FSTWatchChangeTests.mm; sourceTree = ""; }; 5495EB022040E90200EBA509 /* CodableGeoPointTests.swift */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.swift; path = CodableGeoPointTests.swift; sourceTree = ""; }; + 54995F6E205B6E12004EFFA0 /* leveldb_key_test.cc */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = leveldb_key_test.cc; path = ../../core/test/firebase/firestore/local/leveldb_key_test.cc; sourceTree = ""; }; 54C2294E1FECABAE007D065B /* log_test.cc */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = log_test.cc; path = ../../core/test/firebase/firestore/util/log_test.cc; sourceTree = ""; }; 54C9EDF12040E16300A969CD /* Firestore_SwiftTests_iOS.xctest */ = {isa = PBXFileReference; explicitFileType = wrapper.cfbundle; includeInIndex = 0; path = Firestore_SwiftTests_iOS.xctest; sourceTree = BUILT_PRODUCTS_DIR; }; 54C9EDF52040E16300A969CD /* Info.plist */ = {isa = PBXFileReference; lastKnownFileType = text.plist.xml; path = Info.plist; sourceTree = ""; }; @@ -496,6 +498,7 @@ AB38D9312023962A000A432D /* auth */, AB380CF7201937B800D97691 /* core */, 54EB764B202277970088B8F3 /* immutable */, + 54995F70205B6E1A004EFFA0 /* local */, AB356EF5200E9D1A0089B766 /* model */, 5467FB05203E652F009C9584 /* testutil */, 54740A561FC913EB00713A1A /* util */, @@ -513,6 +516,14 @@ path = Codable; sourceTree = ""; }; + 54995F70205B6E1A004EFFA0 /* local */ = { + isa = PBXGroup; + children = ( + 54995F6E205B6E12004EFFA0 /* leveldb_key_test.cc */, + ); + name = local; + sourceTree = ""; + }; 54C9EDF22040E16300A969CD /* SwiftTests */ = { isa = PBXGroup; children = ( @@ -1514,6 +1525,7 @@ 5492E0B92021555100B64F25 /* FSTDocumentKeyTests.mm in Sources */, DE2EF0871F3D0B6E003D0CDC /* FSTImmutableSortedSet+Testing.m in Sources */, 5492E0C82021557E00B64F25 /* FSTDatastoreTests.mm in Sources */, + 54995F6F205B6E12004EFFA0 /* leveldb_key_test.cc in Sources */, 5492E065202154B900B64F25 /* FSTViewTests.mm in Sources */, 5492E03C2021401F00B64F25 /* XCTestCase+Await.mm in Sources */, B6152AD7202A53CB000E5744 /* document_key_test.cc in Sources */, diff --git a/Firestore/Source/Core/FSTTypes.h b/Firestore/Source/Core/FSTTypes.h index 688b2bf..f15f463 100644 --- a/Firestore/Source/Core/FSTTypes.h +++ b/Firestore/Source/Core/FSTTypes.h @@ -16,15 +16,17 @@ #import +#include "Firestore/core/src/firebase/firestore/model/types.h" + NS_ASSUME_NONNULL_BEGIN @class FSTMaybeDocument; @class FSTTransaction; /** FSTBatchID is a locally assigned ID for a batch of mutations that have been applied. */ -typedef int32_t FSTBatchID; +typedef firebase::firestore::model::BatchId FSTBatchID; -typedef int32_t FSTTargetID; +typedef firebase::firestore::model::TargetId FSTTargetID; typedef int64_t FSTListenSequenceNumber; diff --git a/Firestore/core/CMakeLists.txt b/Firestore/core/CMakeLists.txt index 5bf8c5e..43188e9 100644 --- a/Firestore/core/CMakeLists.txt +++ b/Firestore/core/CMakeLists.txt @@ -16,6 +16,7 @@ add_subdirectory(src/firebase/firestore) add_subdirectory(src/firebase/firestore/auth) add_subdirectory(src/firebase/firestore/core) add_subdirectory(src/firebase/firestore/immutable) +add_subdirectory(src/firebase/firestore/local) add_subdirectory(src/firebase/firestore/model) add_subdirectory(src/firebase/firestore/remote) add_subdirectory(src/firebase/firestore/util) @@ -25,6 +26,7 @@ add_subdirectory(test/firebase/firestore) add_subdirectory(test/firebase/firestore/auth) add_subdirectory(test/firebase/firestore/core) add_subdirectory(test/firebase/firestore/immutable) +add_subdirectory(test/firebase/firestore/local) add_subdirectory(test/firebase/firestore/model) add_subdirectory(test/firebase/firestore/remote) add_subdirectory(test/firebase/firestore/util) diff --git a/Firestore/core/src/firebase/firestore/local/CMakeLists.txt b/Firestore/core/src/firebase/firestore/local/CMakeLists.txt new file mode 100644 index 0000000..089d03c --- /dev/null +++ b/Firestore/core/src/firebase/firestore/local/CMakeLists.txt @@ -0,0 +1,25 @@ +# Copyright 2018 Google +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. + +cc_library( + firebase_firestore_local + SOURCES + leveldb_key.h + leveldb_key.cc + DEPENDS + LevelDB::LevelDB + absl_strings + firebase_firestore_model + firebase_firestore_util +) diff --git a/Firestore/core/src/firebase/firestore/local/leveldb_key.cc b/Firestore/core/src/firebase/firestore/local/leveldb_key.cc new file mode 100644 index 0000000..25e4322 --- /dev/null +++ b/Firestore/core/src/firebase/firestore/local/leveldb_key.cc @@ -0,0 +1,769 @@ +/* + * Copyright 2018 Google + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "Firestore/core/src/firebase/firestore/local/leveldb_key.h" + +#include +#include + +#include "Firestore/core/src/firebase/firestore/local/leveldb_util.h" +#include "Firestore/core/src/firebase/firestore/util/ordered_code.h" +#include "absl/strings/escaping.h" +#include "absl/strings/str_cat.h" + +using firebase::firestore::model::DocumentKey; +using firebase::firestore::model::ResourcePath; +using firebase::firestore::util::OrderedCode; + +namespace firebase { +namespace firestore { +namespace local { + +namespace { + +const char *kVersionGlobalTable = "version"; +const char *kMutationsTable = "mutation"; +const char *kDocumentMutationsTable = "document_mutation"; +const char *kMutationQueuesTable = "mutation_queue"; +const char *kTargetGlobalTable = "target_global"; +const char *kTargetsTable = "target"; +const char *kQueryTargetsTable = "query_target"; +const char *kTargetDocumentsTable = "target_document"; +const char *kDocumentTargetsTable = "document_target"; +const char *kRemoteDocumentsTable = "remote_document"; + +/** + * Labels for the components of keys. These serve to make keys self-describing. + * + * These are intended to sort similarly to keys in the server storage format. + * + * Note that the server writes component labels using the equivalent to + * OrderedCode::WriteSignedNumDecreasing. This means that despite the higher + * numeric value, a terminator sorts before a path segment. In order to avoid + * needing the WriteSignedNumDecreasing code just for these values, this enum's + * values are in the reverse order to the server side. + * + * Most server-side values don't apply here. For example, the server embeds + * projects, databases, namespaces and similar values in its entity keys where + * the clients just open a different leveldb. Similarly, many of these values + * don't apply to the server since the server is backed by spanner which + * natively has concepts of tables and indexes. Where there's overlap, a comment + * denotes the server value from the storage_format_internal.proto. + */ +enum ComponentLabel { + /** + * A terminator is the final component of a key. All complete keys have a + * terminator and a key is known to be a key prefix if it doesn't have a + * terminator. + */ + Terminator = 0, // TERMINATOR_COMPONENT = 63, server-side + + /** + * A table name component names the logical table to which the key belongs. + */ + TableName = 5, + + /** A component containing the batch Id of a mutation. */ + BatchId = 10, + + /** A component containing the canonical Id of a query. */ + CanonicalId = 11, + + /** A component containing the target Id of a query. */ + TargetId = 12, + + /** A component containing a user Id. */ + UserId = 13, + + /** + * A path segment describes just a single segment in a resource path. Path + * segments that occur sequentially in a key represent successive segments in + * a single path. + * + * This value must be greater than ComponentLabel::Terminator to ensure that + * longer paths sort after paths that are prefixes of them. + * + * This value must also be larger than other separators so that path suffixes + * sort after other key components. + */ + PathSegment = 62, // PATH = 60, server-side + + /** + * The maximum value that can be encoded by WriteSignedNumIncreasing in a + * single byte. + */ + Unknown = 63, +}; + +/** OrderedCode::ReadSignedNumIncreasing adapted to leveldb::Slice. */ +bool ReadSignedNumIncreasing(leveldb::Slice *src, int64_t *result) { + absl::string_view tmp = MakeStringView(*src); + if (OrderedCode::ReadSignedNumIncreasing(&tmp, result)) { + *src = MakeSlice(tmp); + return true; + } + return false; +} + +/** OrderedCode::ReadString adapted to leveldb::Slice. */ +bool ReadString(leveldb::Slice *src, std::string *result) { + absl::string_view tmp = MakeStringView(*src); + if (OrderedCode::ReadString(&tmp, result)) { + *src = MakeSlice(tmp); + return true; + } + return false; +} + +/** Writes a component label to the given key destination. */ +void WriteComponentLabel(std::string *dest, ComponentLabel label) { + OrderedCode::WriteSignedNumIncreasing(dest, label); +} + +/** + * Reads a component label from the given key contents. + * + * If the read is unsuccessful, returns false, and changes none of its + * arguments. + * + * If the read is successful, returns true, contents will be updated to the next + * unread byte, and label will be set to the decoded label value. + */ +bool ReadComponentLabel(leveldb::Slice *contents, ComponentLabel *label) { + int64_t raw_result = 0; + leveldb::Slice tmp = *contents; + if (ReadSignedNumIncreasing(&tmp, &raw_result)) { + if (raw_result >= ComponentLabel::Terminator && + raw_result <= ComponentLabel::Unknown) { + *contents = tmp; + *label = static_cast(raw_result); + return true; + } + } + return false; +} + +/** + * Reads a component label from the given key contents. + * + * If the read is unsuccessful or if the read was successful but the label that + * was read did not match the expected_label returns false and changes none of + * its arguments. + * + * If the read is successful, returns true and contents will be updated to the + * next unread byte. + */ +bool ReadComponentLabelMatching(leveldb::Slice *contents, + ComponentLabel expected_label) { + int64_t raw_result = 0; + leveldb::Slice tmp = *contents; + if (ReadSignedNumIncreasing(&tmp, &raw_result)) { + if (raw_result == expected_label) { + *contents = tmp; + return true; + } + } + return false; +} + +/** + * Reads a signed number from the given key contents and verifies that the value + * fits in a 32-bit integer. + * + * If the read is unsuccessful or the number that was read was out of bounds for + * an int32_t, returns false, and changes none of its arguments. + * + * If the read is successful, returns true, contents will be updated to the next + * unread byte, and result will be set to the decoded integer value. + */ +bool ReadInt32(leveldb::Slice *contents, int32_t *result) { + int64_t raw_result = 0; + leveldb::Slice tmp = *contents; + if (ReadSignedNumIncreasing(&tmp, &raw_result)) { + if (raw_result >= INT32_MIN && raw_result <= INT32_MAX) { + *contents = tmp; + *result = static_cast(raw_result); + return true; + } + } + return false; +} + +/** + * Writes a component label and a signed integer to the given key destination. + */ +void WriteLabeledInt32(std::string *dest, ComponentLabel label, int32_t value) { + WriteComponentLabel(dest, label); + OrderedCode::WriteSignedNumIncreasing(dest, value); +} + +/** + * Reads a component label and signed number from the given key contents and + * verifies that the label matches the expected_label and the value fits in a + * 32-bit integer. + * + * If the read is unsuccessful, the label didn't match, or the number that was + * read was out of bounds for an int32_t, returns false, and changes none of its + * arguments. + * + * If the read is successful, returns true, contents will be updated to the next + * unread byte, and value will be set to the decoded integer value. + */ +bool ReadLabeledInt32(leveldb::Slice *contents, + ComponentLabel expected_label, + int32_t *value) { + leveldb::Slice tmp = *contents; + if (ReadComponentLabelMatching(&tmp, expected_label)) { + if (ReadInt32(&tmp, value)) { + *contents = tmp; + return true; + } + } + return false; +} + +/** + * Writes a component label and an encoded string to the given key destination. + */ +void WriteLabeledString(std::string *dest, + ComponentLabel label, + absl::string_view value) { + WriteComponentLabel(dest, label); + OrderedCode::WriteString(dest, value); +} + +/** + * Reads a component label and a string from the given key contents and verifies + * that the label matches the expected_label. + * + * If the read is unsuccessful or the label didn't match, returns false, and + * changes none of its arguments. + * + * If the read is successful, returns true, contents will be updated to the next + * unread byte, and value will be set to the decoded string value. + */ +bool ReadLabeledString(leveldb::Slice *contents, + ComponentLabel expected_label, + std::string *value) { + leveldb::Slice tmp = *contents; + if (ReadComponentLabelMatching(&tmp, expected_label)) { + if (ReadString(&tmp, value)) { + *contents = tmp; + return true; + } + } + return false; +} + +/** + * Reads a component label and a string from the given key contents and verifies + * that the label matches the expected_label and the string matches the + * expected_value. + * + * If the read is unsuccessful, the label or didn't match, or the string value + * didn't match, returns false, and changes none of its arguments. + * + * If the read is successful, returns true, contents will be updated to the next + * unread byte. + */ +bool ReadLabeledStringMatching(leveldb::Slice *contents, + ComponentLabel expected_label, + const char *expected_value) { + std::string value; + leveldb::Slice tmp = *contents; + if (ReadLabeledString(&tmp, expected_label, &value)) { + if (value == expected_value) { + *contents = tmp; + return true; + } + } + + return false; +} + +/** + * For each segment in the given resource path writes an + * ComponentLabel::PathSegment component label and a string containing the path + * segment. + */ +void WriteResourcePath(std::string *dest, const ResourcePath &path) { + for (const auto &segment : path) { + WriteComponentLabel(dest, ComponentLabel::PathSegment); + OrderedCode::WriteString(dest, segment); + } +} + +/** + * Reads component labels and strings from the given key contents until it finds + * a component label other that ComponentLabel::PathSegment. All matched path + * segments are assembled into a resource path and wrapped in an DocumentKey. + * + * If the read is unsuccessful or the document key is invalid, returns false, + * and changes none of its arguments. + * + * If the read is successful, returns true, contents will be updated to the next + * unread byte, and value will be set to the decoded document key. + */ +bool ReadDocumentKey(leveldb::Slice *contents, DocumentKey *result) { + leveldb::Slice complete_segments = *contents; + + std::string segment; + std::vector path_segments; + for (;;) { + // Advance a temporary slice to avoid advancing contents into the next key + // component which may not be a path segment. + leveldb::Slice read_position = complete_segments; + if (!ReadComponentLabelMatching(&read_position, + ComponentLabel::PathSegment)) { + break; + } + if (!ReadString(&read_position, &segment)) { + return false; + } + + path_segments.push_back(std::move(segment)); + segment.clear(); + + complete_segments = read_position; + } + + ResourcePath path{std::move(path_segments)}; + if (path.size() > 0 && DocumentKey::IsDocumentKey(path)) { + *contents = complete_segments; + *result = DocumentKey{std::move(path)}; + return true; + } + + return false; +} + +// Trivial shortcuts that make reading and writing components type-safe. + +inline void WriteTerminator(std::string *dest) { + OrderedCode::WriteSignedNumIncreasing(dest, ComponentLabel::Terminator); +} + +inline bool ReadTerminator(leveldb::Slice *contents) { + return ReadComponentLabelMatching(contents, ComponentLabel::Terminator); +} + +inline void WriteTableName(std::string *dest, const char *table_name) { + WriteLabeledString(dest, ComponentLabel::TableName, table_name); +} + +inline bool ReadTableNameMatching(leveldb::Slice *contents, + const char *expected_table_name) { + return ReadLabeledStringMatching(contents, ComponentLabel::TableName, + expected_table_name); +} + +inline void WriteBatchId(std::string *dest, model::BatchId batch_id) { + WriteLabeledInt32(dest, ComponentLabel::BatchId, batch_id); +} + +inline bool ReadBatchId(leveldb::Slice *contents, model::BatchId *batch_id) { + return ReadLabeledInt32(contents, ComponentLabel::BatchId, batch_id); +} + +inline void WriteCanonicalId(std::string *dest, + absl::string_view canonical_id) { + WriteLabeledString(dest, ComponentLabel::CanonicalId, canonical_id); +} + +inline bool ReadCanonicalId(leveldb::Slice *contents, + std::string *canonical_id) { + return ReadLabeledString(contents, ComponentLabel::CanonicalId, canonical_id); +} + +inline void WriteTargetId(std::string *dest, model::TargetId target_id) { + WriteLabeledInt32(dest, ComponentLabel::TargetId, target_id); +} + +inline bool ReadTargetId(leveldb::Slice *contents, model::TargetId *target_id) { + return ReadLabeledInt32(contents, ComponentLabel::TargetId, target_id); +} + +inline void WriteUserId(std::string *dest, absl::string_view user_id) { + WriteLabeledString(dest, ComponentLabel::UserId, user_id); +} + +inline bool ReadUserId(leveldb::Slice *contents, std::string *user_id) { + return ReadLabeledString(contents, ComponentLabel::UserId, user_id); +} + +/** + * Returns a base64-encoded string for an invalid key, used for debug-friendly + * description text. + */ +std::string InvalidKey(leveldb::Slice key) { + std::string result; + absl::Base64Escape(MakeStringView(key), &result); + return result; +} + +} // namespace + +std::string Describe(leveldb::Slice key) { + leveldb::Slice contents = key; + bool is_terminated = false; + + std::string description; + absl::StrAppend(&description, "["); + + while (contents.size() > 0) { + leveldb::Slice tmp = contents; + ComponentLabel label = ComponentLabel::Unknown; + if (!ReadComponentLabel(&tmp, &label)) { + break; + } + + if (label == ComponentLabel::Terminator) { + is_terminated = true; + contents = tmp; + break; + } + + // Reset tmp since all the different read routines expect to see the + // separator first + tmp = contents; + + if (label == ComponentLabel::PathSegment) { + DocumentKey document_key; + if (!ReadDocumentKey(&tmp, &document_key)) { + break; + } + absl::StrAppend(&description, + " key=", document_key.path().CanonicalString()); + + } else if (label == ComponentLabel::TableName) { + std::string table; + if (!ReadLabeledString(&tmp, ComponentLabel::TableName, &table)) { + break; + } + absl::StrAppend(&description, table, ":"); + + } else if (label == ComponentLabel::BatchId) { + model::BatchId batch_id; + if (!ReadBatchId(&tmp, &batch_id)) { + break; + } + absl::StrAppend(&description, " batch_id=", batch_id); + + } else if (label == ComponentLabel::CanonicalId) { + std::string canonical_id; + if (!ReadCanonicalId(&tmp, &canonical_id)) { + break; + } + absl::StrAppend(&description, " canonical_id=", canonical_id); + + } else if (label == ComponentLabel::TargetId) { + model::TargetId target_id; + if (!ReadTargetId(&tmp, &target_id)) { + break; + } + absl::StrAppend(&description, " target_id=", target_id); + + } else if (label == ComponentLabel::UserId) { + std::string user_id; + if (!ReadUserId(&tmp, &user_id)) { + break; + } + absl::StrAppend(&description, " user_id=", user_id); + + } else { + absl::StrAppend(&description, " unknown label=", static_cast(label)); + break; + } + + contents = tmp; + } + + if (contents.size() > 0) { + absl::StrAppend(&description, " invalid key=<", InvalidKey(key), ">"); + + } else if (!is_terminated) { + absl::StrAppend(&description, " incomplete key"); + } + + absl::StrAppend(&description, "]"); + return description; +} + +std::string LevelDbVersionKey::Key() { + std::string result; + WriteTableName(&result, kVersionGlobalTable); + WriteTerminator(&result); + return result; +} + +std::string LevelDbMutationKey::KeyPrefix() { + std::string result; + WriteTableName(&result, kMutationsTable); + return result; +} + +std::string LevelDbMutationKey::KeyPrefix(absl::string_view user_id) { + std::string result; + WriteTableName(&result, kMutationsTable); + WriteUserId(&result, user_id); + return result; +} + +std::string LevelDbMutationKey::Key(absl::string_view user_id, + model::BatchId batch_id) { + std::string result; + WriteTableName(&result, kMutationsTable); + WriteUserId(&result, user_id); + WriteBatchId(&result, batch_id); + WriteTerminator(&result); + return result; +} + +bool LevelDbMutationKey::Decode(leveldb::Slice key) { + user_id_.clear(); + batch_id_ = 0; + + return ReadTableNameMatching(&key, kMutationsTable) && + ReadUserId(&key, &user_id_) && ReadBatchId(&key, &batch_id_) && + ReadTerminator(&key); +} + +std::string LevelDbDocumentMutationKey::KeyPrefix() { + std::string result; + WriteTableName(&result, kDocumentMutationsTable); + return result; +} + +std::string LevelDbDocumentMutationKey::KeyPrefix(absl::string_view user_id) { + std::string result; + WriteTableName(&result, kDocumentMutationsTable); + WriteUserId(&result, user_id); + return result; +} + +std::string LevelDbDocumentMutationKey::KeyPrefix( + absl::string_view user_id, const ResourcePath &resource_path) { + std::string result; + WriteTableName(&result, kDocumentMutationsTable); + WriteUserId(&result, user_id); + WriteResourcePath(&result, resource_path); + return result; +} + +std::string LevelDbDocumentMutationKey::Key(absl::string_view user_id, + const DocumentKey &document_key, + model::BatchId batch_id) { + std::string result; + WriteTableName(&result, kDocumentMutationsTable); + WriteUserId(&result, user_id); + WriteResourcePath(&result, document_key.path()); + WriteBatchId(&result, batch_id); + WriteTerminator(&result); + return result; +} + +bool LevelDbDocumentMutationKey::Decode(leveldb::Slice key) { + user_id_.clear(); + document_key_ = DocumentKey{}; + batch_id_ = 0; + + return ReadTableNameMatching(&key, kDocumentMutationsTable) && + ReadUserId(&key, &user_id_) && ReadDocumentKey(&key, &document_key_) && + ReadBatchId(&key, &batch_id_) && ReadTerminator(&key); +} + +std::string LevelDbMutationQueueKey::KeyPrefix() { + std::string result; + WriteTableName(&result, kMutationQueuesTable); + return result; +} + +std::string LevelDbMutationQueueKey::Key(absl::string_view user_id) { + std::string result; + WriteTableName(&result, kMutationQueuesTable); + WriteUserId(&result, user_id); + WriteTerminator(&result); + return result; +} + +bool LevelDbMutationQueueKey::Decode(leveldb::Slice key) { + user_id_.clear(); + + return ReadTableNameMatching(&key, kMutationQueuesTable) && + ReadUserId(&key, &user_id_) && ReadTerminator(&key); +} + +std::string LevelDbTargetGlobalKey::Key() { + std::string result; + WriteTableName(&result, kTargetGlobalTable); + WriteTerminator(&result); + return result; +} + +bool LevelDbTargetGlobalKey::Decode(leveldb::Slice key) { + return ReadTableNameMatching(&key, kTargetGlobalTable) && + ReadTerminator(&key); +} + +std::string LevelDbTargetKey::KeyPrefix() { + std::string result; + WriteTableName(&result, kTargetsTable); + return result; +} + +std::string LevelDbTargetKey::Key(model::TargetId target_id) { + std::string result; + WriteTableName(&result, kTargetsTable); + WriteTargetId(&result, target_id); + WriteTerminator(&result); + return result; +} + +bool LevelDbTargetKey::Decode(leveldb::Slice key) { + target_id_ = 0; + return ReadTableNameMatching(&key, kTargetsTable) && + ReadTargetId(&key, &target_id_) && ReadTerminator(&key); +} + +std::string LevelDbQueryTargetKey::KeyPrefix() { + std::string result; + WriteTableName(&result, kQueryTargetsTable); + return result; +} + +std::string LevelDbQueryTargetKey::KeyPrefix(absl::string_view canonical_id) { + std::string result; + WriteTableName(&result, kQueryTargetsTable); + WriteCanonicalId(&result, canonical_id); + return result; +} + +std::string LevelDbQueryTargetKey::Key(absl::string_view canonical_id, + model::TargetId target_id) { + std::string result; + WriteTableName(&result, kQueryTargetsTable); + WriteCanonicalId(&result, canonical_id); + WriteTargetId(&result, target_id); + WriteTerminator(&result); + return result; +} + +bool LevelDbQueryTargetKey::Decode(leveldb::Slice key) { + canonical_id_.clear(); + target_id_ = 0; + + return ReadTableNameMatching(&key, kQueryTargetsTable) && + ReadCanonicalId(&key, &canonical_id_) && + ReadTargetId(&key, &target_id_) && ReadTerminator(&key); +} + +std::string LevelDbTargetDocumentKey::KeyPrefix() { + std::string result; + WriteTableName(&result, kTargetDocumentsTable); + return result; +} + +std::string LevelDbTargetDocumentKey::KeyPrefix(model::TargetId target_id) { + std::string result; + WriteTableName(&result, kTargetDocumentsTable); + WriteTargetId(&result, target_id); + return result; +} + +std::string LevelDbTargetDocumentKey::Key(model::TargetId target_id, + const DocumentKey &document_key) { + std::string result; + WriteTableName(&result, kTargetDocumentsTable); + WriteTargetId(&result, target_id); + WriteResourcePath(&result, document_key.path()); + WriteTerminator(&result); + return result; +} + +bool LevelDbTargetDocumentKey::Decode(leveldb::Slice key) { + target_id_ = 0; + document_key_ = DocumentKey{}; + + return ReadTableNameMatching(&key, kTargetDocumentsTable) && + ReadTargetId(&key, &target_id_) && + ReadDocumentKey(&key, &document_key_) && ReadTerminator(&key); +} + +std::string LevelDbDocumentTargetKey::KeyPrefix() { + std::string result; + WriteTableName(&result, kDocumentTargetsTable); + return result; +} + +std::string LevelDbDocumentTargetKey::KeyPrefix( + const ResourcePath &resource_path) { + std::string result; + WriteTableName(&result, kDocumentTargetsTable); + WriteResourcePath(&result, resource_path); + return result; +} + +std::string LevelDbDocumentTargetKey::Key(const DocumentKey &document_key, + model::TargetId target_id) { + std::string result; + WriteTableName(&result, kDocumentTargetsTable); + WriteResourcePath(&result, document_key.path()); + WriteTargetId(&result, target_id); + WriteTerminator(&result); + return result; +} + +bool LevelDbDocumentTargetKey::Decode(leveldb::Slice key) { + document_key_ = DocumentKey{}; + target_id_ = 0; + + return ReadTableNameMatching(&key, kDocumentTargetsTable) && + ReadDocumentKey(&key, &document_key_) && + ReadTargetId(&key, &target_id_) && ReadTerminator(&key); +} + +std::string LevelDbRemoteDocumentKey::KeyPrefix() { + std::string result; + WriteTableName(&result, kRemoteDocumentsTable); + return result; +} + +std::string LevelDbRemoteDocumentKey::KeyPrefix( + const ResourcePath &resource_path) { + std::string result; + WriteTableName(&result, kRemoteDocumentsTable); + WriteResourcePath(&result, resource_path); + return result; +} + +std::string LevelDbRemoteDocumentKey::Key(const DocumentKey &key) { + std::string result; + WriteTableName(&result, kRemoteDocumentsTable); + WriteResourcePath(&result, key.path()); + WriteTerminator(&result); + return result; +} + +bool LevelDbRemoteDocumentKey::Decode(leveldb::Slice key) { + document_key_ = DocumentKey{}; + + return ReadTableNameMatching(&key, kRemoteDocumentsTable) && + ReadDocumentKey(&key, &document_key_) && ReadTerminator(&key); +} + +} // namespace local +} // namespace firestore +} // namespace firebase diff --git a/Firestore/core/src/firebase/firestore/local/leveldb_key.h b/Firestore/core/src/firebase/firestore/local/leveldb_key.h new file mode 100644 index 0000000..9f78849 --- /dev/null +++ b/Firestore/core/src/firebase/firestore/local/leveldb_key.h @@ -0,0 +1,485 @@ +/* + * Copyright 2018 Google + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_LOCAL_LEVELDB_KEY_H_ +#define FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_LOCAL_LEVELDB_KEY_H_ + +#include + +#include "Firestore/core/src/firebase/firestore/model/document_key.h" +#include "Firestore/core/src/firebase/firestore/model/resource_path.h" +#include "Firestore/core/src/firebase/firestore/model/types.h" +#include "absl/strings/string_view.h" +#include "leveldb/slice.h" + +namespace firebase { +namespace firestore { +namespace local { + +// Utilities for encoding and decoding LevelDB row keys and key prefixes. +// +// LevelDB keys are strings, so all the routines in here operate on strings to +// be able to produce and consume leveldb APIs directly. +// +// All leveldb logical tables should have their keys structures described in +// this file. +// +// mutations: +// - table_name: string = "mutation" +// - user_id: string +// - batch_id: model::BatchId +// +// document_mutations: +// - table_name: string = "document_mutation" +// - user_id: string +// - path: ResourcePath +// - batch_id: model::BatchId +// +// mutation_queues: +// - table_name: string = "mutation_queue" +// - user_id: string +// +// targets: +// - table_name: string = "target" +// - target_id: model::TargetId +// +// target_globals: +// - table_name: string = "target_global" +// +// query_targets: +// - table_name: string = "query_target" +// - canonical_id: string +// - target_id: model::TargetId +// +// target_documents: +// - table_name: string = "target_document" +// - target_id: model::TargetId +// - path: ResourcePath +// +// document_targets: +// - table_name: string = "document_target" +// - path: ResourcePath +// - target_id: model::TargetId +// +// remote_documents: +// - table_name: string = "remote_document" +// - path: ResourcePath + +/** + * Parses the given key and returns a human readable description of its + * contents, suitable for error messages and logging. + */ +std::string Describe(leveldb::Slice key); + +/** A key to a singleton row storing the version of the schema. */ +class LevelDbVersionKey { + public: + /** + * Returns the key pointing to the singleton row storing the schema version. + */ + static std::string Key(); +}; + +/** A key in the mutations table. */ +class LevelDbMutationKey { + public: + /** + * Creates a key prefix that points just before the first key in the table. + */ + static std::string KeyPrefix(); + + /** + * Creates a key prefix that points just before the first key for the given + * user_id. + */ + static std::string KeyPrefix(absl::string_view user_id); + + /** Creates a complete key that points to a specific user_id and batch_id. */ + static std::string Key(absl::string_view user_id, model::BatchId batch_id); + + /** + * Decodes the given complete key, storing the decoded values in this + * instance. + * + * @return true if the key successfully decoded, false otherwise. If false is + * returned, this instance is in an undefined state until the next call to + * `Decode()`. + */ + bool Decode(leveldb::Slice key); + + /** The user that owns the mutation batches. */ + const std::string& user_id() const { + return user_id_; + } + + /** The batch_id of the batch. */ + model::BatchId batch_id() const { + return batch_id_; + } + + private: + // Deliberately uninitialized: will be assigned in Decode + std::string user_id_; + model::BatchId batch_id_; +}; + +/** + * A key in the document mutations index, which stores the batches in which + * documents are mutated. + */ +class LevelDbDocumentMutationKey { + public: + /** + * Creates a key prefix that points just before the first key in the table. + */ + static std::string KeyPrefix(); + + /** + * Creates a key prefix that points just before the first key for the given + * user_id. + */ + static std::string KeyPrefix(absl::string_view user_id); + + /** + * Creates a key prefix that points just before the first key for the user_id + * and resource path. + * + * Note that this uses a ResourcePath rather than an DocumentKey in order to + * allow prefix scans over a collection. However a naive scan over those + * results isn't useful since it would match both immediate children of the + * collection and any subcollections. + */ + static std::string KeyPrefix(absl::string_view user_id, + const model::ResourcePath& resource_path); + + /** + * Creates a complete key that points to a specific user_id, document key, + * and batch_id. + */ + static std::string Key(absl::string_view user_id, + const model::DocumentKey& document_key, + model::BatchId batch_id); + + /** + * Decodes the given complete key, storing the decoded values in this + * instance. + * + * @return true if the key successfully decoded, false otherwise. If false is + * returned, this instance is in an undefined state until the next call to + * `Decode()`. + */ + bool Decode(leveldb::Slice key); + + /** The user that owns the mutation batches. */ + const std::string& user_id() const { + return user_id_; + } + + /** The path to the document, as encoded in the key. */ + const model::DocumentKey& document_key() const { + return document_key_; + } + + /** The batch_id in which the document participates. */ + model::BatchId batch_id() const { + return batch_id_; + } + + private: + // Deliberately uninitialized: will be assigned in Decode + std::string user_id_; + model::DocumentKey document_key_; + model::BatchId batch_id_; +}; + +/** + * A key in the mutation_queues table. + * + * Note that where `mutation_queues` table contains one row about each queue, + * the `mutations` table contains the actual mutation batches themselves. + */ +class LevelDbMutationQueueKey { + public: + /** + * Creates a key prefix that points just before the first key in the table. + */ + static std::string KeyPrefix(); + + /** + * Creates a complete key that points to a specific mutation queue entry for + * the given user_id. + */ + static std::string Key(absl::string_view user_id); + + /** + * Decodes the given complete key, storing the decoded values in this + * instance. + * + * @return true if the key successfully decoded, false otherwise. If false is + * returned, this instance is in an undefined state until the next call to + * `Decode()`. + */ + bool Decode(leveldb::Slice key); + + const std::string& user_id() const { + return user_id_; + } + + private: + // Deliberately uninitialized: will be assigned in Decode + std::string user_id_; +}; + +/** + * A key in the target globals table, a record of global values across all + * targets. + */ +class LevelDbTargetGlobalKey { + public: + /** Creates a key that points to the single target global row. */ + static std::string Key(); + + /** + * Decodes the contents of a target global key, essentially just verifying + * that the key has the correct table name. + */ + bool Decode(leveldb::Slice key); +}; + +/** A key in the targets table. */ +class LevelDbTargetKey { + public: + /** + * Creates a key prefix that points just before the first key in the table. + */ + static std::string KeyPrefix(); + + /** Creates a complete key that points to a specific target, by target_id. */ + static std::string Key(model::TargetId target_id); + + /** + * Decodes the contents of a target key, storing the decoded values in this + * instance. + * + * @return true if the key successfully decoded, false otherwise. If false is + * returned, this instance is in an undefined state until the next call to + * `Decode()`. + */ + bool Decode(leveldb::Slice key); + + model::TargetId target_id() { + return target_id_; + } + + private: + model::TargetId target_id_ = 0; +}; + +/** + * A key in the query targets table, an index of canonical_ids to the targets + * they may match. This is not a unique mapping because canonical_id does not + * promise a unique name for all possible queries. + */ +class LevelDbQueryTargetKey { + public: + /** + * Creates a key that contains just the query targets table prefix and points + * just before the first key. + */ + static std::string KeyPrefix(); + + /** + * Creates a key that points to the first query-target association for a + * canonical_id. + */ + static std::string KeyPrefix(absl::string_view canonical_id); + + /** Creates a key that points to a specific query-target entry. */ + static std::string Key(absl::string_view canonical_id, + model::TargetId target_id); + + /** + * Decodes the contents of a query target key, storing the decoded values in + * this instance. + * + * @return true if the key successfully decoded, false otherwise. If false is + * returned, this instance is in an undefined state until the next call to + * `Decode()`. + */ + bool Decode(leveldb::Slice key); + + /** The canonical_id derived from the query. */ + const std::string& canonical_id() const { + return canonical_id_; + } + + /** The target_id identifying a target. */ + model::TargetId target_id() const { + return target_id_; + } + + private: + // Deliberately uninitialized: will be assigned in Decode + std::string canonical_id_; + model::TargetId target_id_; +}; + +/** + * A key in the target documents table, an index of target_ids to the documents + * they contain. + */ +class LevelDbTargetDocumentKey { + public: + /** + * Creates a key that contains just the target documents table prefix and + * points just before the first key. + */ + static std::string KeyPrefix(); + + /** + * Creates a key that points to the first target-document association for a + * target_id. + */ + static std::string KeyPrefix(model::TargetId target_id); + + /** Creates a key that points to a specific target-document entry. */ + static std::string Key(model::TargetId target_id, + const model::DocumentKey& document_key); + + /** + * Decodes the contents of a target document key, storing the decoded values + * in this instance. + * + * @return true if the key successfully decoded, false otherwise. If false is + * returned, this instance is in an undefined state until the next call to + * `Decode()`. + */ + bool Decode(leveldb::Slice key); + + /** The target_id identifying a target. */ + model::TargetId target_id() { + return target_id_; + } + + /** The path to the document, as encoded in the key. */ + const model::DocumentKey& document_key() { + return document_key_; + } + + private: + // Deliberately uninitialized: will be assigned in Decode + model::TargetId target_id_; + model::DocumentKey document_key_; +}; + +/** + * A key in the document targets table, an index from documents to the targets + * that contain them. + */ +class LevelDbDocumentTargetKey { + public: + /** + * Creates a key that contains just the document targets table prefix and + * points just before the first key. + */ + static std::string KeyPrefix(); + + /** + * Creates a key that points to the first document-target association for + * document. + */ + static std::string KeyPrefix(const model::ResourcePath& resource_path); + + /** Creates a key that points to a specific document-target entry. */ + static std::string Key(const model::DocumentKey& document_key, + model::TargetId target_id); + + /** + * Decodes the contents of a document target key, storing the decoded values + * in this instance. + * + * @return true if the key successfully decoded, false otherwise. If false is + * returned, this instance is in an undefined state until the next call to + * `Decode()`. + */ + bool Decode(leveldb::Slice key); + + /** The target_id identifying a target. */ + model::TargetId target_id() const { + return target_id_; + } + + /** The path to the document, as encoded in the key. */ + const model::DocumentKey& document_key() const { + return document_key_; + } + + private: + // Deliberately uninitialized: will be assigned in Decode + model::TargetId target_id_; + model::DocumentKey document_key_; +}; + +/** A key in the remote documents table. */ +class LevelDbRemoteDocumentKey { + public: + /** + * Creates a key that contains just the remote documents table prefix and + * points just before the first remote document key. + */ + static std::string KeyPrefix(); + + /** + * Creates a complete key that points to a specific document. The document_key + * must have an even number of path segments. + */ + static std::string Key(const model::DocumentKey& document_key); + + /** + * Creates a key prefix that contains a part of a document path. Odd numbers + * of segments create a collection key prefix, while an even number of + * segments create a document key prefix. Note that a document key prefix will + * match the document itself and any documents that exist in its + * subcollections. + */ + static std::string KeyPrefix(const model::ResourcePath& resource_path); + + /** + * Decodes the contents of a remote document key, storing the decoded values + * in this instance. This can only decode complete document paths (i.e. the + * result of Key()). + * + * @return true if the key successfully decoded, false otherwise. If false is + * returned, this instance is in an undefined state until the next call to + * `Decode()`. + */ + bool Decode(leveldb::Slice key); + + /** The path to the document, as encoded in the key. */ + const model::DocumentKey& document_key() const { + return document_key_; + } + + private: + // Deliberately uninitialized: will be assigned in Decode + model::DocumentKey document_key_; +}; + +} // namespace local +} // namespace firestore +} // namespace firebase + +#endif // FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_LOCAL_LEVELDB_KEY_H_ diff --git a/Firestore/core/src/firebase/firestore/local/leveldb_util.h b/Firestore/core/src/firebase/firestore/local/leveldb_util.h new file mode 100644 index 0000000..5738d65 --- /dev/null +++ b/Firestore/core/src/firebase/firestore/local/leveldb_util.h @@ -0,0 +1,43 @@ +/* + * Copyright 2018 Google + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#ifndef FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_LOCAL_LEVELDB_UTIL_H_ +#define FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_LOCAL_LEVELDB_UTIL_H_ + +#include + +#include "absl/strings/string_view.h" +#include "leveldb/slice.h" + +namespace firebase { +namespace firestore { +namespace local { + +/** Creates a Slice from a string_view. */ +inline leveldb::Slice MakeSlice(absl::string_view view) { + return leveldb::Slice{view.data(), view.size()}; +} + +/** Creates a string_view from a Slice. */ +inline absl::string_view MakeStringView(leveldb::Slice slice) { + return absl::string_view{slice.data(), slice.size()}; +} + +} // namespace local +} // namespace firestore +} // namespace firebase + +#endif // FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_LOCAL_LEVELDB_UTIL_H_ diff --git a/Firestore/core/src/firebase/firestore/model/types.h b/Firestore/core/src/firebase/firestore/model/types.h index 4f71829..fc1b196 100644 --- a/Firestore/core/src/firebase/firestore/model/types.h +++ b/Firestore/core/src/firebase/firestore/model/types.h @@ -23,7 +23,17 @@ namespace firebase { namespace firestore { namespace model { -typedef int32_t TargetId; +/** + * BatchId is a locally assigned identifier for a batch of mutations that have + * been applied by the user but have not yet been fully committed at the server. + */ +using BatchId = int32_t; + +/** + * TargetId is a stable numeric identifier assigned for a specific query + * applied. + */ +using TargetId = int32_t; } // namespace model } // namespace firestore diff --git a/Firestore/core/src/firebase/firestore/util/string_util.h b/Firestore/core/src/firebase/firestore/util/string_util.h index 3de177d..96ba0b0 100644 --- a/Firestore/core/src/firebase/firestore/util/string_util.h +++ b/Firestore/core/src/firebase/firestore/util/string_util.h @@ -32,7 +32,7 @@ namespace firebase { namespace firestore { namespace util { -/* +/** * Returns the smallest lexicographically larger string of equal or smaller * length. Returns an empty string if there is no such successor (if the input * is empty or consists entirely of 0xff bytes). @@ -44,7 +44,7 @@ namespace util { */ std::string PrefixSuccessor(absl::string_view prefix); -/* +/** * Returns the immediate lexicographically-following string. This is useful to * turn an inclusive range into something that can be used with Bigtable's * SetLimitRow(): @@ -65,6 +65,11 @@ std::string PrefixSuccessor(absl::string_view prefix); */ std::string ImmediateSuccessor(absl::string_view s); +/** + * Returns true if the given value starts with the given prefix. + */ +bool StartsWith(const std::string &value, const std::string &prefix); + } // namespace util } // namespace firestore } // namespace firebase diff --git a/Firestore/core/test/firebase/firestore/local/CMakeLists.txt b/Firestore/core/test/firebase/firestore/local/CMakeLists.txt new file mode 100644 index 0000000..f52e394 --- /dev/null +++ b/Firestore/core/test/firebase/firestore/local/CMakeLists.txt @@ -0,0 +1,22 @@ +# Copyright 2018 Google +# +# Licensed under the Apache License, Version 2.0 (the "License"); +# you may not use this file except in compliance with the License. +# You may obtain a copy of the License at +# +# http://www.apache.org/licenses/LICENSE-2.0 +# +# Unless required by applicable law or agreed to in writing, software +# distributed under the License is distributed on an "AS IS" BASIS, +# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. +# See the License for the specific language governing permissions and +# limitations under the License. + +cc_test( + firebase_firestore_local_test + SOURCES + leveldb_key_test.cc + DEPENDS + firebase_firestore_local + firebase_firestore_model +) diff --git a/Firestore/core/test/firebase/firestore/local/leveldb_key_test.cc b/Firestore/core/test/firebase/firestore/local/leveldb_key_test.cc new file mode 100644 index 0000000..9032473 --- /dev/null +++ b/Firestore/core/test/firebase/firestore/local/leveldb_key_test.cc @@ -0,0 +1,364 @@ +/* + * Copyright 2018 Google + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include "Firestore/core/src/firebase/firestore/local/leveldb_key.h" + +#include "Firestore/core/src/firebase/firestore/util/string_util.h" + +#include "Firestore/core/test/firebase/firestore/testutil/testutil.h" +#include "absl/strings/match.h" +#include "gtest/gtest.h" + +using firebase::firestore::model::BatchId; +using firebase::firestore::model::DocumentKey; +using firebase::firestore::model::TargetId; + +namespace firebase { +namespace firestore { +namespace local { + +namespace { + +std::string RemoteDocKey(absl::string_view path_string) { + return LevelDbRemoteDocumentKey::Key(testutil::Key(path_string)); +} + +std::string RemoteDocKeyPrefix(absl::string_view path_string) { + return LevelDbRemoteDocumentKey::KeyPrefix(testutil::Resource(path_string)); +} + +std::string DocMutationKey(absl::string_view user_id, + absl::string_view key, + model::BatchId batch_id) { + return LevelDbDocumentMutationKey::Key(user_id, testutil::Key(key), batch_id); +} + +std::string TargetDocKey(TargetId target_id, absl::string_view key) { + return LevelDbTargetDocumentKey::Key(target_id, testutil::Key(key)); +} + +std::string DocTargetKey(absl::string_view key, TargetId target_id) { + return LevelDbDocumentTargetKey::Key(testutil::Key(key), target_id); +} + +} // namespace + +/** + * Asserts that the description for given key is equal to the expected + * description. + * + * @param key A StringView of a textual key + * @param key An NSString that [LevelDbKey descriptionForKey:] is expected to + * produce. + */ +#define AssertExpectedKeyDescription(expected_description, key) \ + ASSERT_EQ((expected_description), Describe(key)) + +TEST(LevelDbMutationKeyTest, Prefixing) { + auto tableKey = LevelDbMutationKey::KeyPrefix(); + auto emptyUserKey = LevelDbMutationKey::KeyPrefix(""); + auto fooUserKey = LevelDbMutationKey::KeyPrefix("foo"); + + auto foo2Key = LevelDbMutationKey::Key("foo", 2); + + ASSERT_TRUE(absl::StartsWith(emptyUserKey, tableKey)); + + // This is critical: prefixes of the a value don't convert into prefixes of + // the key. + ASSERT_TRUE(absl::StartsWith(fooUserKey, tableKey)); + ASSERT_FALSE(absl::StartsWith(fooUserKey, emptyUserKey)); + + // However whole segments in common are prefixes. + ASSERT_TRUE(absl::StartsWith(foo2Key, tableKey)); + ASSERT_TRUE(absl::StartsWith(foo2Key, fooUserKey)); +} + +TEST(LevelDbMutationKeyTest, EncodeDecodeCycle) { + LevelDbMutationKey key; + std::string user("foo"); + + std::vector batch_ids{0, 1, 100, INT_MAX - 1, INT_MAX}; + for (auto batch_id : batch_ids) { + auto encoded = LevelDbMutationKey::Key(user, batch_id); + + bool ok = key.Decode(encoded); + ASSERT_TRUE(ok); + ASSERT_EQ(user, key.user_id()); + ASSERT_EQ(batch_id, key.batch_id()); + } +} + +TEST(LevelDbMutationKeyTest, Description) { + AssertExpectedKeyDescription("[mutation: incomplete key]", + LevelDbMutationKey::KeyPrefix()); + + AssertExpectedKeyDescription("[mutation: user_id=user1 incomplete key]", + LevelDbMutationKey::KeyPrefix("user1")); + + auto key = LevelDbMutationKey::Key("user1", 42); + AssertExpectedKeyDescription("[mutation: user_id=user1 batch_id=42]", key); + + AssertExpectedKeyDescription( + "[mutation: user_id=user1 batch_id=42 invalid " + "key=]", + key + " extra"); + + // Truncate the key so that it's missing its terminator. + key.resize(key.size() - 1); + AssertExpectedKeyDescription( + "[mutation: user_id=user1 batch_id=42 incomplete key]", key); +} + +TEST(LevelDbDocumentMutationKeyTest, Prefixing) { + auto table_key = LevelDbDocumentMutationKey::KeyPrefix(); + auto empty_user_key = LevelDbDocumentMutationKey::KeyPrefix(""); + auto foo_user_key = LevelDbDocumentMutationKey::KeyPrefix("foo"); + + DocumentKey document_key = testutil::Key("foo/bar"); + auto foo2_key = LevelDbDocumentMutationKey::Key("foo", document_key, 2); + + ASSERT_TRUE(absl::StartsWith(empty_user_key, table_key)); + + // While we want a key with whole segments in common be considered a prefix + // it's vital that partial segments in common not be prefixes. + ASSERT_TRUE(absl::StartsWith(foo_user_key, table_key)); + + // Here even though "" is a prefix of "foo", that prefix is within a segment, + // so keys derived from those segments cannot be prefixes of each other. + ASSERT_FALSE(absl::StartsWith(foo_user_key, empty_user_key)); + ASSERT_FALSE(absl::StartsWith(empty_user_key, foo_user_key)); + + // However whole segments in common are prefixes. + ASSERT_TRUE(absl::StartsWith(foo2_key, table_key)); + ASSERT_TRUE(absl::StartsWith(foo2_key, foo_user_key)); +} + +TEST(LevelDbDocumentMutationKeyTest, EncodeDecodeCycle) { + LevelDbDocumentMutationKey key; + std::string user("foo"); + + std::vector document_keys{testutil::Key("a/b"), + testutil::Key("a/b/c/d")}; + + std::vector batch_ids{0, 1, 100, INT_MAX - 1, INT_MAX}; + + for (BatchId batch_id : batch_ids) { + for (auto&& document_key : document_keys) { + auto encoded = + LevelDbDocumentMutationKey::Key(user, document_key, batch_id); + + bool ok = key.Decode(encoded); + ASSERT_TRUE(ok); + ASSERT_EQ(user, key.user_id()); + ASSERT_EQ(document_key, key.document_key()); + ASSERT_EQ(batch_id, key.batch_id()); + } + } +} + +TEST(LevelDbDocumentMutationKeyTest, Ordering) { + // Different user: + ASSERT_LT(DocMutationKey("1", "foo/bar", 0), + DocMutationKey("10", "foo/bar", 0)); + ASSERT_LT(DocMutationKey("1", "foo/bar", 0), + DocMutationKey("2", "foo/bar", 0)); + + // Different paths: + ASSERT_LT(DocMutationKey("1", "foo/bar", 0), + DocMutationKey("1", "foo/baz", 0)); + ASSERT_LT(DocMutationKey("1", "foo/bar", 0), + DocMutationKey("1", "foo/bar2", 0)); + ASSERT_LT(DocMutationKey("1", "foo/bar", 0), + DocMutationKey("1", "foo/bar/suffix/key", 0)); + ASSERT_LT(DocMutationKey("1", "foo/bar/suffix/key", 0), + DocMutationKey("1", "foo/bar2", 0)); + + // Different batch_id: + ASSERT_LT(DocMutationKey("1", "foo/bar", 0), + DocMutationKey("1", "foo/bar", 1)); +} + +TEST(LevelDbDocumentMutationKeyTest, Description) { + AssertExpectedKeyDescription("[document_mutation: incomplete key]", + LevelDbDocumentMutationKey::KeyPrefix()); + + AssertExpectedKeyDescription( + "[document_mutation: user_id=user1 incomplete key]", + LevelDbDocumentMutationKey::KeyPrefix("user1")); + + auto key = LevelDbDocumentMutationKey::KeyPrefix( + "user1", testutil::Resource("foo/bar")); + AssertExpectedKeyDescription( + "[document_mutation: user_id=user1 key=foo/bar incomplete key]", key); + + key = LevelDbDocumentMutationKey::Key("user1", testutil::Key("foo/bar"), 42); + AssertExpectedKeyDescription( + "[document_mutation: user_id=user1 key=foo/bar batch_id=42]", key); +} + +TEST(LevelDbTargetGlobalKeyTest, EncodeDecodeCycle) { + LevelDbTargetGlobalKey key; + + auto encoded = LevelDbTargetGlobalKey::Key(); + bool ok = key.Decode(encoded); + ASSERT_TRUE(ok); +} + +TEST(LevelDbTargetGlobalKeyTest, Description) { + AssertExpectedKeyDescription("[target_global:]", + LevelDbTargetGlobalKey::Key()); +} + +TEST(LevelDbTargetKeyTest, EncodeDecodeCycle) { + LevelDbTargetKey key; + TargetId target_id = 42; + + auto encoded = LevelDbTargetKey::Key(42); + bool ok = key.Decode(encoded); + ASSERT_TRUE(ok); + ASSERT_EQ(target_id, key.target_id()); +} + +TEST(LevelDbTargetKeyTest, Description) { + AssertExpectedKeyDescription("[target: target_id=42]", + LevelDbTargetKey::Key(42)); +} + +TEST(LevelDbQueryTargetKeyTest, EncodeDecodeCycle) { + LevelDbQueryTargetKey key; + std::string canonical_id("foo"); + TargetId target_id = 42; + + auto encoded = LevelDbQueryTargetKey::Key(canonical_id, 42); + bool ok = key.Decode(encoded); + ASSERT_TRUE(ok); + ASSERT_EQ(canonical_id, key.canonical_id()); + ASSERT_EQ(target_id, key.target_id()); +} + +TEST(LevelDbQueryKeyTest, Description) { + AssertExpectedKeyDescription("[query_target: canonical_id=foo target_id=42]", + LevelDbQueryTargetKey::Key("foo", 42)); +} + +TEST(TargetDocumentKeyTest, EncodeDecodeCycle) { + LevelDbTargetDocumentKey key; + + auto encoded = LevelDbTargetDocumentKey::Key(42, testutil::Key("foo/bar")); + bool ok = key.Decode(encoded); + ASSERT_TRUE(ok); + ASSERT_EQ(42, key.target_id()); + ASSERT_EQ(testutil::Key("foo/bar"), key.document_key()); +} + +TEST(TargetDocumentKeyTest, Ordering) { + // Different target_id: + ASSERT_LT(TargetDocKey(1, "foo/bar"), TargetDocKey(2, "foo/bar")); + ASSERT_LT(TargetDocKey(2, "foo/bar"), TargetDocKey(10, "foo/bar")); + ASSERT_LT(TargetDocKey(10, "foo/bar"), TargetDocKey(100, "foo/bar")); + ASSERT_LT(TargetDocKey(42, "foo/bar"), TargetDocKey(100, "foo/bar")); + + // Different paths: + ASSERT_LT(TargetDocKey(1, "foo/bar"), TargetDocKey(1, "foo/baz")); + ASSERT_LT(TargetDocKey(1, "foo/bar"), TargetDocKey(1, "foo/bar2")); + ASSERT_LT(TargetDocKey(1, "foo/bar"), TargetDocKey(1, "foo/bar/suffix/key")); + ASSERT_LT(TargetDocKey(1, "foo/bar/suffix/key"), TargetDocKey(1, "foo/bar2")); +} + +TEST(TargetDocumentKeyTest, Description) { + auto key = LevelDbTargetDocumentKey::Key(42, testutil::Key("foo/bar")); + ASSERT_EQ("[target_document: target_id=42 key=foo/bar]", Describe(key)); +} + +TEST(DocumentTargetKeyTest, EncodeDecodeCycle) { + LevelDbDocumentTargetKey key; + + auto encoded = LevelDbDocumentTargetKey::Key(testutil::Key("foo/bar"), 42); + bool ok = key.Decode(encoded); + ASSERT_TRUE(ok); + ASSERT_EQ(testutil::Key("foo/bar"), key.document_key()); + ASSERT_EQ(42, key.target_id()); +} + +TEST(DocumentTargetKeyTest, Description) { + auto key = LevelDbDocumentTargetKey::Key(testutil::Key("foo/bar"), 42); + ASSERT_EQ("[document_target: key=foo/bar target_id=42]", Describe(key)); +} + +TEST(DocumentTargetKeyTest, Ordering) { + // Different paths: + ASSERT_LT(DocTargetKey("foo/bar", 1), DocTargetKey("foo/baz", 1)); + ASSERT_LT(DocTargetKey("foo/bar", 1), DocTargetKey("foo/bar2", 1)); + ASSERT_LT(DocTargetKey("foo/bar", 1), DocTargetKey("foo/bar/suffix/key", 1)); + ASSERT_LT(DocTargetKey("foo/bar/suffix/key", 1), DocTargetKey("foo/bar2", 1)); + + // Different target_id: + ASSERT_LT(DocTargetKey("foo/bar", 1), DocTargetKey("foo/bar", 2)); + ASSERT_LT(DocTargetKey("foo/bar", 2), DocTargetKey("foo/bar", 10)); + ASSERT_LT(DocTargetKey("foo/bar", 10), DocTargetKey("foo/bar", 100)); + ASSERT_LT(DocTargetKey("foo/bar", 42), DocTargetKey("foo/bar", 100)); +} + +TEST(RemoteDocumentKeyTest, Prefixing) { + auto tableKey = LevelDbRemoteDocumentKey::KeyPrefix(); + + ASSERT_TRUE(absl::StartsWith(RemoteDocKey("foo/bar"), tableKey)); + + // This is critical: foo/bar2 should not contain foo/bar. + ASSERT_FALSE( + absl::StartsWith(RemoteDocKey("foo/bar2"), RemoteDocKey("foo/bar"))); + + // Prefixes must be encoded specially + ASSERT_FALSE(absl::StartsWith(RemoteDocKey("foo/bar/baz/quu"), + RemoteDocKey("foo/bar"))); + ASSERT_TRUE(absl::StartsWith(RemoteDocKey("foo/bar/baz/quu"), + RemoteDocKeyPrefix("foo/bar"))); + ASSERT_TRUE(absl::StartsWith(RemoteDocKeyPrefix("foo/bar/baz/quu"), + RemoteDocKeyPrefix("foo/bar"))); + ASSERT_TRUE(absl::StartsWith(RemoteDocKeyPrefix("foo/bar/baz"), + RemoteDocKeyPrefix("foo/bar"))); + ASSERT_TRUE(absl::StartsWith(RemoteDocKeyPrefix("foo/bar"), + RemoteDocKeyPrefix("foo"))); +} + +TEST(RemoteDocumentKeyTest, Ordering) { + ASSERT_LT(RemoteDocKey("foo/bar"), RemoteDocKey("foo/bar2")); + ASSERT_LT(RemoteDocKey("foo/bar"), RemoteDocKey("foo/bar/suffix/key")); +} + +TEST(RemoteDocumentKeyTest, EncodeDecodeCycle) { + LevelDbRemoteDocumentKey key; + + std::vector paths{"foo/bar", "foo/bar2", "foo/bar/baz/quux"}; + for (auto&& path : paths) { + auto encoded = RemoteDocKey(path); + bool ok = key.Decode(encoded); + ASSERT_TRUE(ok); + ASSERT_EQ(testutil::Key(path), key.document_key()); + } +} + +TEST(RemoteDocumentKeyTest, Description) { + AssertExpectedKeyDescription( + "[remote_document: key=foo/bar/baz/quux]", + LevelDbRemoteDocumentKey::Key(testutil::Key("foo/bar/baz/quux"))); +} + +#undef AssertExpectedKeyDescription + +} // namespace local +} // namespace firestore +} // namespace firebase -- cgit v1.2.3