Merge the hash prefixes from the old store and the additions in the partial

components/safe_browsing_db/v4_store_unittest.cc

 // Copyright 2016 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "base/files/file_util.h"
 #include "base/files/scoped_temp_dir.h"
 #include "base/memory/ptr_util.h"
 #include "base/run_loop.h"
 #include "base/test/test_simple_task_runner.h"
 #include "base/time/time.h"
@@ skipping 123 matching lines @@
   list_update_response->set_response_type(ListUpdateResponse::FULL_UPDATE);
   list_update_response->set_new_client_state("test_client_state");
   EXPECT_EQ(WRITE_SUCCESS, V4Store(task_runner_, store_path_)
                                .WriteToDisk(std::move(list_update_response)));
 
   std::unique_ptr<V4Store> read_store(new V4Store(task_runner_, store_path_));
   EXPECT_EQ(READ_SUCCESS, read_store->ReadFromDisk());
   EXPECT_EQ("test_client_state", read_store->state_);
 }
 
+TEST_F(V4StoreTest, TestAddUnlumpedHashesWithInvalidAddition) {
+  HashPrefixMap prefix_map;
+  MergeUpdateResult result = V4Store::AddUnlumpedHashes(5, "a", &prefix_map);
+  EXPECT_EQ(ADDITIONS_SIZE_UNEXPECTED_FAILURE, result);
+  EXPECT_TRUE(prefix_map.empty());
+}
+
+TEST_F(V4StoreTest, TestAddUnlumpedHashesWithEmptyString) {
+  HashPrefixMap prefix_map;
+  MergeUpdateResult result = V4Store::AddUnlumpedHashes(5, "", &prefix_map);
+  EXPECT_EQ(MERGE_SUCCESS, result);
+  EXPECT_TRUE(prefix_map.empty());
+}
+
+TEST_F(V4StoreTest, TestAddUnlumpedHashes) {
+  HashPrefixMap prefix_map;
+  EXPECT_EQ(MERGE_SUCCESS,
+            V4Store::AddUnlumpedHashes(5, "abcde5432100000-----", &prefix_map));
+  EXPECT_EQ(1u, prefix_map.size());
+  HashPrefixes& hash_prefixes = prefix_map[5];
+  EXPECT_EQ(4u, hash_prefixes.size());
+
+  EXPECT_EQ("abcde", std::string(hash_prefixes[0].get()));
+  EXPECT_EQ("54321", std::string(hash_prefixes[1].get()));
+  EXPECT_EQ("00000", std::string(hash_prefixes[2].get()));
+  EXPECT_EQ("-----", std::string(hash_prefixes[3].get()));
+
+  EXPECT_EQ(MERGE_SUCCESS,
+            V4Store::AddUnlumpedHashes(4, "abcde5432100000-----", &prefix_map));
+  EXPECT_EQ(2u, prefix_map.size());
+  HashPrefixes& hash_prefixes_of_length_4 = prefix_map[4];
+  EXPECT_EQ(5u, hash_prefixes_of_length_4.size());
+  EXPECT_EQ("abcd", std::string(hash_prefixes_of_length_4[0].get()));
+  EXPECT_EQ("e543", std::string(hash_prefixes_of_length_4[1].get()));
+  EXPECT_EQ("2100", std::string(hash_prefixes_of_length_4[2].get()));
+  EXPECT_EQ("000-", std::string(hash_prefixes_of_length_4[3].get()));
+  EXPECT_EQ("----", std::string(hash_prefixes_of_length_4[4].get()));
+}
+
+TEST_F(V4StoreTest, TestGetNextSmallestPrefixSizeWithEmptyPrefixMap) {
+  HashPrefixMap prefix_map;
+  CounterMap counter_map = V4Store::GetInitializedCounterMap(prefix_map);
+
+  PrefixSize prefix_size;
+  EXPECT_FALSE(V4Store::GetNextSmallestPrefixSize(prefix_map, counter_map,
+                                                  &prefix_size));
+}
+
+TEST_F(V4StoreTest, TestGetNextSmallestPrefixSize) {
+  HashPrefixMap prefix_map;
+  V4Store::AddUnlumpedHashes(5, "-----0000054321abcde", &prefix_map);
+  V4Store::AddUnlumpedHashes(4, "-----0000054321abcde", &prefix_map);
+  CounterMap counter_map = V4Store::GetInitializedCounterMap(prefix_map);
+
+  PrefixSize prefix_size;
+  EXPECT_TRUE(V4Store::GetNextSmallestPrefixSize(prefix_map, counter_map,
+                                                 &prefix_size));
+  EXPECT_EQ(4u, prefix_size);

[Nathan Parker, 2016/07/11 18:09:58]

Is this testing that "----" < "-----"?  

[vakh (use Gerrit instead), 2016/07/12 07:34:19]

Yes, and more importantly that the order is as expected.

+}
+
+TEST_F(V4StoreTest, TestGetNextUnmergedPrefix) {
+  HashPrefixMap prefix_map;
+  V4Store::AddUnlumpedHashes(5, "-----0000054321abcde", &prefix_map);
+  V4Store::AddUnlumpedHashes(4, "-----0000054321abcde", &prefix_map);
+  CounterMap counter_map = V4Store::GetInitializedCounterMap(prefix_map);
+
+  PrefixSize prefix_size;
+  EXPECT_TRUE(V4Store::GetNextSmallestPrefixSize(prefix_map, counter_map,
+                                                 &prefix_size));
+  const HashPrefix& prefix = V4Store::GetNextUnmergedPrefixForSize(
+      prefix_size, prefix_map, counter_map);
+  std::string prefix_str = std::string(prefix.get(), prefix_size);
+  EXPECT_EQ("----", prefix_str);
+}
+
+TEST_F(V4StoreTest, TestMergeUpdates) {
+  HashPrefixMap prefix_map_old;
+  V4Store::AddUnlumpedHashes(4, "abcdefgh", &prefix_map_old);
+  V4Store::AddUnlumpedHashes(5, "54321abcde", &prefix_map_old);
+  HashPrefixMap prefix_map_additions;
+  V4Store::AddUnlumpedHashes(4, "----1111bbbb", &prefix_map_additions);
+  V4Store::AddUnlumpedHashes(5, "22222bcdef", &prefix_map_additions);
+
+  std::unique_ptr<V4Store> store(new V4Store(task_runner_, store_path_));
+  store->MergeUpdate(prefix_map_old, prefix_map_additions);
+  const HashPrefixMap& prefix_map = store->hash_prefix_map_;
+  EXPECT_EQ(2u, prefix_map.size());
+  const HashPrefixes& hash_prefixes_of_length_4 = prefix_map.at(4);
+  EXPECT_EQ(5u, hash_prefixes_of_length_4.size());
+  EXPECT_EQ("----", std::string(hash_prefixes_of_length_4[0].get()));
+  EXPECT_EQ("1111", std::string(hash_prefixes_of_length_4[1].get()));
+  EXPECT_EQ("abcd", std::string(hash_prefixes_of_length_4[2].get()));
+  EXPECT_EQ("bbbb", std::string(hash_prefixes_of_length_4[3].get()));
+  EXPECT_EQ("efgh", std::string(hash_prefixes_of_length_4[4].get()));
+
+  const HashPrefixes& hash_prefixes_of_length_5 = prefix_map.at(5);
+  EXPECT_EQ(4u, hash_prefixes_of_length_5.size());
+  EXPECT_EQ("22222", std::string(hash_prefixes_of_length_5[0].get()));
+  EXPECT_EQ("54321", std::string(hash_prefixes_of_length_5[1].get()));
+  EXPECT_EQ("abcde", std::string(hash_prefixes_of_length_5[2].get()));
+  EXPECT_EQ("bcdef", std::string(hash_prefixes_of_length_5[3].get()));
+}

[Nathan Parker, 2016/07/11 18:09:58]

We should test all the branches of the merge code.  Some more cases:

1) old or additions has zero hashes of a particular size
2) old list runs out (merges the lexigraphically last element) first
3) additions list runs out first
4) additions has an identical entry.  This shouldn't happen, but we should have
some defined behavior for it.

+
 }  // namespace safe_browsing