Port FSTLevelDBKey to C++ (#937)

11 files changed, 1744 insertions, 5 deletions

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 = "<group>"; };
 		5492E0C52021557E00B64F25 /* FSTWatchChangeTests.mm */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.objcpp; path = FSTWatchChangeTests.mm; sourceTree = "<group>"; };
 		5495EB022040E90200EBA509 /* CodableGeoPointTests.swift */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.swift; path = CodableGeoPointTests.swift; sourceTree = "<group>"; };
+		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 = "<group>"; };
 		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 = "<group>"; };
 		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 = "<group>"; };
@@ -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 = "<group>";
 		};
+		54995F70205B6E1A004EFFA0 /* local */ = {
+			isa = PBXGroup;
+			children = (
+				54995F6E205B6E12004EFFA0 /* leveldb_key_test.cc */,
+			);
+			name = local;
+			sourceTree = "<group>";
+		};
 		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 <Foundation/Foundation.h>
 
+#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 <utility>
+#include <vector>
+
+#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<ComponentLabel>(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<int32_t>(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<std::string> 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<int>(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 <string>
+
+#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 <string>
+
+#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<BatchId> 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=<hW11dGF0aW9uAAGNdXNlcjEAAYqqgCBleHRyYQ==>]",
+      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<DocumentKey> document_keys{testutil::Key("a/b"),
+                                         testutil::Key("a/b/c/d")};
+
+  std::vector<BatchId> 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<std::string> 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