implement `TargetIdGenerator` in C++ for Firestore (#701)

* implement `TargetIdGenerator`

* address changes

8 files changed, 310 insertions, 0 deletions

diff --git a/Firestore/Example/Firestore.xcodeproj/project.pbxproj b/Firestore/Example/Firestore.xcodeproj/project.pbxproj
index 155b4f2..7bc57fc 100644
--- a/Firestore/Example/Firestore.xcodeproj/project.pbxproj
+++ b/Firestore/Example/Firestore.xcodeproj/project.pbxproj
@@ -65,6 +65,7 @@
 		71719F9F1E33DC2100824A3D /* LaunchScreen.storyboard in Resources */ = {isa = PBXBuildFile; fileRef = 71719F9D1E33DC2100824A3D /* LaunchScreen.storyboard */; };
 		873B8AEB1B1F5CCA007FD442 /* Main.storyboard in Resources */ = {isa = PBXBuildFile; fileRef = 873B8AEA1B1F5CCA007FD442 /* Main.storyboard */; };
 		AB356EF7200EA5EB0089B766 /* field_value_test.cc in Sources */ = {isa = PBXBuildFile; fileRef = AB356EF6200EA5EB0089B766 /* field_value_test.cc */; };
+		AB380CFB2019388600D97691 /* target_id_generator_test.cc in Sources */ = {isa = PBXBuildFile; fileRef = AB380CF82019382300D97691 /* target_id_generator_test.cc */; };
 		AB380CFE201A2F4500D97691 /* string_util_test.cc in Sources */ = {isa = PBXBuildFile; fileRef = AB380CFC201A2EE200D97691 /* string_util_test.cc */; };
 		AB382F7C1FE02A1F007CA955 /* FIRDocumentReferenceTests.m in Sources */ = {isa = PBXBuildFile; fileRef = AB382F7B1FE02A1F007CA955 /* FIRDocumentReferenceTests.m */; };
 		AB382F7E1FE03059007CA955 /* FIRFieldPathTests.m in Sources */ = {isa = PBXBuildFile; fileRef = AB382F7D1FE03059007CA955 /* FIRFieldPathTests.m */; };
@@ -249,6 +250,7 @@
 		9D52E67EE96AA7E5D6F69748 /* Pods-Firestore_IntegrationTests.debug.xcconfig */ = {isa = PBXFileReference; includeInIndex = 1; lastKnownFileType = text.xcconfig; name = "Pods-Firestore_IntegrationTests.debug.xcconfig"; path = "Pods/Target Support Files/Pods-Firestore_IntegrationTests/Pods-Firestore_IntegrationTests.debug.xcconfig"; sourceTree = "<group>"; };
 		9EF477AD4B2B643FD320867A /* Pods-Firestore_Example.debug.xcconfig */ = {isa = PBXFileReference; includeInIndex = 1; lastKnownFileType = text.xcconfig; name = "Pods-Firestore_Example.debug.xcconfig"; path = "Pods/Target Support Files/Pods-Firestore_Example/Pods-Firestore_Example.debug.xcconfig"; sourceTree = "<group>"; };
 		AB356EF6200EA5EB0089B766 /* field_value_test.cc */ = {isa = PBXFileReference; lastKnownFileType = sourcecode.cpp.cpp; path = field_value_test.cc; sourceTree = "<group>"; };
+		AB380CF82019382300D97691 /* target_id_generator_test.cc */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; path = target_id_generator_test.cc; sourceTree = "<group>"; };
 		AB380CFC201A2EE200D97691 /* string_util_test.cc */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.cpp.cpp; name = string_util_test.cc; path = ../../core/test/firebase/firestore/util/string_util_test.cc; sourceTree = "<group>"; };
 		AB382F7B1FE02A1F007CA955 /* FIRDocumentReferenceTests.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; path = FIRDocumentReferenceTests.m; sourceTree = "<group>"; };
 		AB382F7D1FE03059007CA955 /* FIRFieldPathTests.m */ = {isa = PBXFileReference; fileEncoding = 4; lastKnownFileType = sourcecode.c.objc; path = FIRFieldPathTests.m; sourceTree = "<group>"; };
@@ -416,6 +418,7 @@
 		54764FAC1FAA0C390085E60A /* GoogleTests */ = {
 			isa = PBXGroup;
 			children = (
+				AB380CF7201937B800D97691 /* core */,
 				AB356EF5200E9D1A0089B766 /* model */,
 				54764FAD1FAA0C650085E60A /* Port */,
 				54740A561FC913EB00713A1A /* util */,
@@ -559,6 +562,15 @@
 			path = ../../core/test/firebase/firestore/model;
 			sourceTree = "<group>";
 		};
+		AB380CF7201937B800D97691 /* core */ = {
+			isa = PBXGroup;
+			children = (
+				AB380CF82019382300D97691 /* target_id_generator_test.cc */,
+			);
+			name = core;
+			path = ../../core/test/firebase/firestore/core;
+			sourceTree = "<group>";
+		};
 		DE0761E51F2FE611003233AF /* SwiftBuildTest */ = {
 			isa = PBXGroup;
 			children = (
@@ -1227,6 +1239,7 @@
 				DE51B1EB1F0D490D0013853F /* FSTWriteGroupTests.mm in Sources */,
 				54C2294F1FECABAE007D065B /* log_test.cc in Sources */,
 				DE51B2011F0D493E0013853F /* FSTHelpers.m in Sources */,
+				AB380CFB2019388600D97691 /* target_id_generator_test.cc in Sources */,
 				DE51B1F61F0D491B0013853F /* FSTSerializerBetaTests.m in Sources */,
 				DE51B1F01F0D49140013853F /* FSTFieldValueTests.m in Sources */,
 				AB9945281FE2DE0C00DFC1E6 /* FIRSnapshotMetadataTests.m in Sources */,
diff --git a/Firestore/core/CMakeLists.txt b/Firestore/core/CMakeLists.txt
index f023446..f143a71 100644
--- a/Firestore/core/CMakeLists.txt
+++ b/Firestore/core/CMakeLists.txt
@@ -13,11 +13,13 @@
 # limitations under the License.
 
 add_subdirectory(src/firebase/firestore)
+add_subdirectory(src/firebase/firestore/core)
 add_subdirectory(src/firebase/firestore/model)
 add_subdirectory(src/firebase/firestore/remote)
 add_subdirectory(src/firebase/firestore/util)
 
 add_subdirectory(test/firebase/firestore)
+add_subdirectory(test/firebase/firestore/core)
 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/core/CMakeLists.txt b/Firestore/core/src/firebase/firestore/core/CMakeLists.txt
new file mode 100644
index 0000000..a62985c
--- /dev/null
+++ b/Firestore/core/src/firebase/firestore/core/CMakeLists.txt
@@ -0,0 +1,20 @@
+# 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_core
+  SOURCES
+    target_id_generator.cc
+    target_id_generator.h
+)
diff --git a/Firestore/core/src/firebase/firestore/core/target_id_generator.cc b/Firestore/core/src/firebase/firestore/core/target_id_generator.cc
new file mode 100644
index 0000000..6d23d64
--- /dev/null
+++ b/Firestore/core/src/firebase/firestore/core/target_id_generator.cc
@@ -0,0 +1,62 @@
+/*
+ * 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/core/target_id_generator.h"
+
+namespace firebase {
+namespace firestore {
+namespace core {
+
+TargetIdGenerator::TargetIdGenerator(const TargetIdGenerator& value)
+    : generator_id_(value.generator_id_), previous_id_(value.previous_id_) {
+}
+
+TargetIdGenerator::TargetIdGenerator(TargetIdGeneratorId generator_id,
+                                     TargetId after)
+    : generator_id_(generator_id) {
+  const TargetId after_without_generator = (after >> kReservedBits)
+                                           << kReservedBits;
+  const TargetId after_generator = after - after_without_generator;
+  const TargetId generator = static_cast<TargetId>(generator_id);
+  if (after_generator >= generator) {
+    // For example, if:
+    //   self.generatorID = 0b0000
+    //   after = 0b1011
+    //   afterGenerator = 0b0001
+    // Then:
+    //   previous = 0b1010
+    //   next = 0b1100
+    previous_id_ = after_without_generator | generator;
+  } else {
+    // For example, if:
+    //   self.generatorID = 0b0001
+    //   after = 0b1010
+    //   afterGenerator = 0b0000
+    // Then:
+    //   previous = 0b1001
+    //   next = 0b1011
+    previous_id_ = (after_without_generator | generator) - (1 << kReservedBits);
+  }
+}
+
+TargetId TargetIdGenerator::NextId() {
+  previous_id_ += 1 << kReservedBits;
+  return previous_id_;
+}
+
+}  // namespace core
+}  // namespace firestore
+}  // namespace firebase
diff --git a/Firestore/core/src/firebase/firestore/core/target_id_generator.h b/Firestore/core/src/firebase/firestore/core/target_id_generator.h
new file mode 100644
index 0000000..345f141
--- /dev/null
+++ b/Firestore/core/src/firebase/firestore/core/target_id_generator.h
@@ -0,0 +1,80 @@
+/*
+ * 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_CORE_TARGET_ID_GENERATOR_H_
+#define FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_CORE_TARGET_ID_GENERATOR_H_
+
+#include "Firestore/core/src/firebase/firestore/core/types.h"
+
+namespace firebase {
+namespace firestore {
+namespace core {
+
+/** The set of all valid generators. */
+enum class TargetIdGeneratorId { LocalStore = 0, SyncEngine = 1 };
+
+/**
+ * Generates monotonically increasing integer IDs. There are separate generators
+ * for different scopes. While these generators will operate independently of
+ * each other, they are scoped, such that no two generators will ever produce
+ * the same ID. This is useful, because sometimes the backend may group IDs from
+ * separate parts of the client into the same ID space.
+ *
+ * Not thread-safe.
+ */
+class TargetIdGenerator {
+ public:
+  TargetIdGenerator(const TargetIdGenerator& value);
+
+  /**
+   * Creates and returns the TargetIdGenerator for the local store.
+   *
+   * @param after An ID to start at. Every call to NextId returns a larger id.
+   * @return An instance of TargetIdGenerator.
+   */
+  static TargetIdGenerator LocalStoreTargetIdGenerator(TargetId after) {
+    return TargetIdGenerator(TargetIdGeneratorId::LocalStore, after);
+  }
+
+  /**
+   * Creates and returns the TargetIdGenerator for the sync engine.
+   *
+   * @param after An ID to start at. Every call to NextId returns a larger id.
+   * @return An instance of TargetIdGenerator.
+   */
+  static TargetIdGenerator SyncEngineTargetIdGenerator(TargetId after) {
+    return TargetIdGenerator(TargetIdGeneratorId::SyncEngine, after);
+  }
+
+  TargetIdGeneratorId generator_id() {
+    return generator_id_;
+  }
+
+  TargetId NextId();
+
+ private:
+  TargetIdGenerator(TargetIdGeneratorId generator_id, TargetId after);
+  TargetIdGeneratorId generator_id_;
+  TargetId previous_id_;
+
+  static const int kReservedBits = 1;
+};
+
+}  // namespace core
+}  // namespace firestore
+}  // namespace firebase
+
+#endif  // FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_CORE_TARGET_ID_GENERATOR_H_
diff --git a/Firestore/core/src/firebase/firestore/core/types.h b/Firestore/core/src/firebase/firestore/core/types.h
new file mode 100644
index 0000000..65c2b8c
--- /dev/null
+++ b/Firestore/core/src/firebase/firestore/core/types.h
@@ -0,0 +1,32 @@
+/*
+ * 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_CORE_TYPES_H_
+#define FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_CORE_TYPES_H_
+
+#include <stdint.h>
+
+namespace firebase {
+namespace firestore {
+namespace core {
+
+typedef int32_t TargetId;
+
+}  // namespace core
+}  // namespace firestore
+}  // namespace firebase
+
+#endif  // FIRESTORE_CORE_SRC_FIREBASE_FIRESTORE_CORE_TYPES_H_
diff --git a/Firestore/core/test/firebase/firestore/core/CMakeLists.txt b/Firestore/core/test/firebase/firestore/core/CMakeLists.txt
new file mode 100644
index 0000000..34993aa
--- /dev/null
+++ b/Firestore/core/test/firebase/firestore/core/CMakeLists.txt
@@ -0,0 +1,21 @@
+# 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_core_test
+  SOURCES
+    target_id_generator_test.cc
+  DEPENDS
+    firebase_firestore_core
+)
diff --git a/Firestore/core/test/firebase/firestore/core/target_id_generator_test.cc b/Firestore/core/test/firebase/firestore/core/target_id_generator_test.cc
new file mode 100644
index 0000000..c98bfd3
--- /dev/null
+++ b/Firestore/core/test/firebase/firestore/core/target_id_generator_test.cc
@@ -0,0 +1,80 @@
+/*
+ * 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/core/target_id_generator.h"
+
+#include "gtest/gtest.h"
+
+namespace firebase {
+namespace firestore {
+namespace core {
+
+TEST(TargetIdGenerator, Constructor) {
+  TargetIdGenerator local_store_generator =
+      TargetIdGenerator::LocalStoreTargetIdGenerator(0);
+  TargetIdGenerator sync_engine_generator =
+      TargetIdGenerator::SyncEngineTargetIdGenerator(0);
+  EXPECT_EQ(TargetIdGeneratorId::LocalStore,
+            local_store_generator.generator_id());
+  EXPECT_EQ(2, local_store_generator.NextId());
+  EXPECT_EQ(TargetIdGeneratorId::SyncEngine,
+            sync_engine_generator.generator_id());
+  EXPECT_EQ(1, sync_engine_generator.NextId());
+}
+
+TEST(TargetIdGenerator, SkipPast) {
+  EXPECT_EQ(1, TargetIdGenerator::SyncEngineTargetIdGenerator(-1).NextId());
+  EXPECT_EQ(3, TargetIdGenerator::SyncEngineTargetIdGenerator(2).NextId());
+  EXPECT_EQ(5, TargetIdGenerator::SyncEngineTargetIdGenerator(4).NextId());
+
+  for (int i = 4; i < 12; ++i) {
+    TargetIdGenerator a = TargetIdGenerator::LocalStoreTargetIdGenerator(i);
+    TargetIdGenerator b = TargetIdGenerator::SyncEngineTargetIdGenerator(i);
+    EXPECT_EQ(i + 2 & ~1, a.NextId());
+    EXPECT_EQ(i + 1 | 1, b.NextId());
+  }
+
+  EXPECT_EQ(13, TargetIdGenerator::SyncEngineTargetIdGenerator(12).NextId());
+  EXPECT_EQ(24, TargetIdGenerator::LocalStoreTargetIdGenerator(22).NextId());
+}
+
+TEST(TargetIdGenerator, Increment) {
+  TargetIdGenerator a = TargetIdGenerator::LocalStoreTargetIdGenerator(0);
+  EXPECT_EQ(2, a.NextId());
+  EXPECT_EQ(4, a.NextId());
+  EXPECT_EQ(6, a.NextId());
+
+  TargetIdGenerator b = TargetIdGenerator::LocalStoreTargetIdGenerator(46);
+  EXPECT_EQ(48, b.NextId());
+  EXPECT_EQ(50, b.NextId());
+  EXPECT_EQ(52, b.NextId());
+  EXPECT_EQ(54, b.NextId());
+
+  TargetIdGenerator c = TargetIdGenerator::SyncEngineTargetIdGenerator(0);
+  EXPECT_EQ(1, c.NextId());
+  EXPECT_EQ(3, c.NextId());
+  EXPECT_EQ(5, c.NextId());
+
+  TargetIdGenerator d = TargetIdGenerator::SyncEngineTargetIdGenerator(46);
+  EXPECT_EQ(47, d.NextId());
+  EXPECT_EQ(49, d.NextId());
+  EXPECT_EQ(51, d.NextId());
+  EXPECT_EQ(53, d.NextId());
+}
+
+}  //  namespace core
+}  //  namespace firestore
+}  //  namespace firebase