PVer4: V4Store: Check whether a hash prefix exists for a full hash

components/safe_browsing_db/v4_store.h

 // 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.
 
 #ifndef COMPONENTS_SAFE_BROWSING_DB_V4_STORE_H_
 #define COMPONENTS_SAFE_BROWSING_DB_V4_STORE_H_
 
 #include "base/files/file_path.h"
 #include "base/memory/ref_counted.h"
 #include "base/sequenced_task_runner.h"
@@ skipping 20 matching lines @@
 // Stores the list of sorted hash prefixes, by size.
 // For instance: {4: ["abcd", "bcde", "cdef", "gggg"], 5: ["fffff"]}
 typedef base::hash_map<PrefixSize, HashPrefixes> HashPrefixMap;
 
 // Stores the iterator to the last element merged from the HashPrefixMap for a
 // given prefix size.
 // For instance: {4:iter(3), 5:iter(1)} means that we have already merged
 // 3 hash prefixes of length 4, and 1 hash prefix of length 5.
 typedef base::hash_map<PrefixSize, HashPrefixes::const_iterator> IteratorMap;
 
+// A full SHA256 hash.
+typedef HashPrefix FullHash;

[Nathan Parker, 2016/07/19 23:01:31]

comment: This is basically just a notation in the code, rather than an
enforceable type safety, ya?  I think you could pass a FullHash to a function
that was expecting a HashPrefix.

[vakh (use Gerrit instead), 2016/07/20 00:24:52]

Yes, but makes following the code much easier.

+
 // Enumerate different failure events while parsing the file read from disk for
 // histogramming purposes.  DO NOT CHANGE THE ORDERING OF THESE VALUES.
 enum StoreReadResult {
   // No errors.
   READ_SUCCESS = 0,
 
   // Reserved for errors in parsing this enum.
   UNEXPECTED_READ_FAILURE = 1,
 
   // The contents of the file could not be read.
   FILE_UNREADABLE_FAILURE = 2,
 
   // The file was found to be empty.
   FILE_EMPTY_FAILURE = 3,
 
   // The contents of the file could not be interpreted as a valid
   // V4StoreFileFormat proto.
   PROTO_PARSING_FAILURE = 4,
 
   // The magic number didn't match. We're most likely trying to read a file
-  // that doesn't contain hash-prefixes.
+  // that doesn't contain hash prefixes.
   UNEXPECTED_MAGIC_NUMBER_FAILURE = 5,
 
   // The version of the file is different from expected and Chromium doesn't
   // know how to interpret this version of the file.
   FILE_VERSION_INCOMPATIBLE_FAILURE = 6,
 
   // The rest of the file could not be parsed as a ListUpdateResponse protobuf.
   // This can happen if the machine crashed before the file was fully written to
   // disk or if there was disk corruption.
   HASH_PREFIX_INFO_MISSING_FAILURE = 7,
@@ skipping 85 matching lines @@
   virtual ~V4Store();
 
   const std::string& state() const { return state_; }
 
   const base::FilePath& store_path() const { return store_path_; }
 
   void ApplyUpdate(std::unique_ptr<ListUpdateResponse> response,
                    const scoped_refptr<base::SingleThreadTaskRunner>&,
                    UpdatedStoreReadyCallback);
 
+  // If a hash prefix in this store matches |full_hash|, returns that hash
+  // prefix; otherwise returns an empty hash prefix.
+  HashPrefix GetMatchingHashPrefix(const FullHash& full_hash);
+
   std::string DebugString() const;
 
   // Reads the store file from disk and populates the in-memory representation
   // of the hash prefixes.
   void Initialize();
 
   // Reset internal state and delete the backing file.
   virtual bool Reset();
 
  private:
@@ skipping 29 matching lines @@
   FRIEND_TEST_ALL_PREFIXES(V4StoreTest, TestMergeUpdatesRemovesFirstElement);
   FRIEND_TEST_ALL_PREFIXES(V4StoreTest, TestMergeUpdatesRemovesMiddleElement);
   FRIEND_TEST_ALL_PREFIXES(V4StoreTest, TestMergeUpdatesRemovesLastElement);
   FRIEND_TEST_ALL_PREFIXES(V4StoreTest,
                            TestMergeUpdatesRemovesWhenOldHasDifferentSizes);
   FRIEND_TEST_ALL_PREFIXES(V4StoreTest,
                            TestMergeUpdatesRemovesMultipleAcrossDifferentSizes);
   FRIEND_TEST_ALL_PREFIXES(V4StoreTest,
                            TestReadFullResponseWithValidHashPrefixMap);
   FRIEND_TEST_ALL_PREFIXES(V4StoreTest,
                            TestReadFullResponseWithInvalidHashPrefixMap);

[Nathan Parker, 2016/07/19 23:01:31]

Do all of these really need to be friends?  I wonder if there's a way to not
have to specify all of them.  Either try to use public methods (a good
practice), or you could make things protected and then derive a class from this
in the test code to export the stuff you need.

It's not really important, but it'd reduce clutter.

Ah here's an idea: Put all the static functions in a " namespace internal {..}"
that implies to others that they shouldn't use these, but allows you to still
test against them.

[vakh (use Gerrit instead), 2016/07/20 00:24:52]

Friend class?
Style guide allows it and specifically calls this usecase out:
https://google.github.io/styleguide/cppguide.html#Friends

+  FRIEND_TEST_ALL_PREFIXES(V4StoreTest, TestHashPrefixExistsAtTheBeginning);
+  FRIEND_TEST_ALL_PREFIXES(V4StoreTest, TestHashPrefixExistsInTheMiddle);
+  FRIEND_TEST_ALL_PREFIXES(V4StoreTest, TestHashPrefixExistsAtTheEnd);
+  FRIEND_TEST_ALL_PREFIXES(V4StoreTest,
+                           TestHashPrefixExistsAtTheBeginningOfEven);
+  FRIEND_TEST_ALL_PREFIXES(V4StoreTest, TestHashPrefixExistsAtTheEndOfEven);
+  FRIEND_TEST_ALL_PREFIXES(V4StoreTest,
+                           TestHashPrefixDoesNotExistInConcatenatedList);
+  FRIEND_TEST_ALL_PREFIXES(V4StoreTest, TestFullHashExistsInMapWithSingleSize);
+  FRIEND_TEST_ALL_PREFIXES(V4StoreTest,
+                           TestFullHashExistsInMapWithDifferentSizes);
+  FRIEND_TEST_ALL_PREFIXES(V4StoreTest,
+                           TestHashPrefixExistsInMapWithSingleSize);
+  FRIEND_TEST_ALL_PREFIXES(V4StoreTest,
+                           TestHashPrefixExistsInMapWithDifferentSizes);
+  FRIEND_TEST_ALL_PREFIXES(V4StoreTest,
+                           TestHashPrefixDoesNotExistInMapWithDifferentSizes);
 
   // If |prefix_size| is within expected range, and |raw_hashes| is not invalid,
   // then it sets |raw_hashes| as the value at key |prefix_size| in
   // |additions_map|
   static ApplyUpdateResult AddUnlumpedHashes(PrefixSize prefix_size,
                                              const std::string& raw_hashes,
                                              HashPrefixMap* additions_map);
 
   // Get the next unmerged hash prefix in dictionary order from
   // |hash_prefix_map|. |iterator_map| is used to determine which hash prefixes
   // have been merged already. Returns true if there are any unmerged hash
   // prefixes in the list.
   static bool GetNextSmallestUnmergedPrefix(
       const HashPrefixMap& hash_prefix_map,
       const IteratorMap& iterator_map,
       HashPrefix* smallest_hash_prefix);
 
+  // Returns true if |hash_prefix| exists between |begin| and |end| iterators.
+  static bool HashPrefixMatches(const HashPrefix& hash_prefix,
+                                const HashPrefixes::const_iterator& begin,
+                                const HashPrefixes::const_iterator& end);
+
   // For each key in |hash_prefix_map|, sets the iterator at that key
   // |iterator_map| to hash_prefix_map[key].begin().
   static void InitializeIteratorMap(const HashPrefixMap& hash_prefix_map,
                                     IteratorMap* iterator_map);
 
   // Reserve the appropriate string size so that the string size of the merged
   // list is exact. This ignores the space that would otherwise be released by
   // deletions specified in the update because it is non-trivial to calculate
   // those deletions upfront. This isn't so bad since deletions are supposed to
   // be small and infrequent.
@@ skipping 28 matching lines @@
   const base::FilePath store_path_;
   HashPrefixMap hash_prefix_map_;
   const scoped_refptr<base::SequencedTaskRunner> task_runner_;
 };
 
 std::ostream& operator<<(std::ostream& os, const V4Store& store);
 
 }  // namespace safe_browsing
 
 #endif  // COMPONENTS_SAFE_BROWSING_DB_V4_STORE_H_