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

Add method to check whether a hash prefix exists for a full hash in a V4Store

Overall design document: https://goto.google.com/design-doc-v4store

This CL does the following:
1. Get the full hash that needs to be checked.
2. Iterate over the hash prefix map:
   Key: prefix size (call it 'n'),
   Value: Concatenated list of sorted hash prefixes of size 'n' (call it 'l').
3. Get the hash prefix of size 'n' from the full hash.
4. Binary search for this hash prefix in 'l'.

BUG=543161
Committed: https://crrev.com/3f60e959d55033a90ed38f890a4fe17d092d7e5b
Cr-Commit-Position: refs/heads/master@{#406508}

[vakh (use Gerrit instead), 2016-07-19 07:16:58]

The CQ bit was checked by vakh@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-07-19 07:17:10]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[vakh (use Gerrit instead), 2016-07-19 07:22:21]

vakh@chromium.org changed reviewers:
+ nparker@chromium.org

[commit-bot: I haz the power, 2016-07-19 07:52:07]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-07-19 07:52:08]

Dry run: Try jobs failed on following builders:
  linux_chromium_asan_rel_ng on master.tryserver.chromium.linux (JOB_FAILED,
http://build.chromium.org/p/tryserver.chromium.linux/builders/linux_chromium_...)

[vakh (use Gerrit instead), 2016-07-19 18:11:54]

Return matching hash prefix. Add comments. Lint.

[vakh (use Gerrit instead), 2016-07-19 18:11:56]

The CQ bit was checked by vakh@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-07-19 18:12:19]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[vakh (use Gerrit instead), 2016-07-19 18:26:05]

Add comments.

[vakh (use Gerrit instead), 2016-07-19 18:26:07]

The CQ bit was checked by vakh@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-07-19 18:26:29]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[vakh (use Gerrit instead), 2016-07-19 18:46:27]

s/ContainsFullHash/GetMatchingHashPrefix

[vakh (use Gerrit instead), 2016-07-19 18:46:29]

The CQ bit was checked by vakh@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-07-19 18:47:52]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-07-19 19:48:56]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-07-19 19:48:57]

Dry run: This issue passed the CQ dry run.

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

https://codereview.chromium.org/2164523002/diff/60001/components/safe_browsin...
File components/safe_browsing_db/v4_store.cc (right):

https://codereview.chromium.org/2164523002/diff/60001/components/safe_browsin...
components/safe_browsing_db/v4_store.cc:433: const HashPrefix& hash_prefix =
full_hash.substr(0, prefix_size);
This is a reference to a temporary... I'm not sure about the lifetime of that
here.  Might be safer to make it a non-reference, since there has to be a copy
anyway.

https://codereview.chromium.org/2164523002/diff/60001/components/safe_browsin...
components/safe_browsing_db/v4_store.cc:450: const PrefixSize& prefix_size =
hash_prefix.length();
no need for reference, since it's just as cheap (cheaper, actually) to copy the
length than it is to copy a ptr to the length.  And this is a reference to a
temporary.

https://codereview.chromium.org/2164523002/diff/60001/components/safe_browsin...
components/safe_browsing_db/v4_store.cc:454: HashPrefix mid_prefix =
HashPrefix(mid, mid + prefix_size);
This is making a copy, which I suppose would copy about log2(num_hashes) of the
prefixes.  To avoid it, you could switch to StringPiece.  I still thing
HashPrefix could be a StringPiece in most cases.

https://codereview.chromium.org/2164523002/diff/60001/components/safe_browsin...
components/safe_browsing_db/v4_store.cc:458: if (hash_prefix < mid_prefix) {
You can avoid iterating over both strings twice (in most cases) by using
std::string::compare(..). It'll return <, =, or > 0 with at most one pass over
the strings.

In fact... it allows you to compare against a part of a string, which avoids the
copying above.

https://codereview.chromium.org/2164523002/diff/60001/components/safe_browsin...
File components/safe_browsing_db/v4_store.h (right):

https://codereview.chromium.org/2164523002/diff/60001/components/safe_browsin...
components/safe_browsing_db/v4_store.h:42: typedef HashPrefix FullHash;
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.

https://codereview.chromium.org/2164523002/diff/60001/components/safe_browsin...
components/safe_browsing_db/v4_store.h:223:
TestReadFullResponseWithInvalidHashPrefixMap);
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.

https://codereview.chromium.org/2164523002/diff/60001/components/safe_browsin...
File components/safe_browsing_db/v4_store_unittest.cc (right):

https://codereview.chromium.org/2164523002/diff/60001/components/safe_browsin...
components/safe_browsing_db/v4_store_unittest.cc:536:
EXPECT_TRUE(V4Store::HashPrefixMatches(hash_prefix, std::begin(hash_prefixes),
nit: These many-short-tests could fit well into one larger test with a comment
separating each.  That would help avoid the friend-clutter in the .h.

https://codereview.chromium.org/2164523002/diff/60001/components/safe_browsin...
components/safe_browsing_db/v4_store_unittest.cc:613:
EXPECT_TRUE(store.GetMatchingHashPrefix(full_hash).empty());
How about a test that has no matching prefix?

Question: If there is a match against two different sized prefixes, which one
should be returned?  Right now it's not defined, since it's an undordered map. 
Should we return the longest match?  We could accomplish that by making it an
ordered map and then traversing it backwards.  Or maybe it doesn't matter, and
it should never happen.

[vakh (use Gerrit instead), 2016-07-20 00:24:39]

nparker@ feedback: Remove some refs. Use std::string::compare.

[vakh (use Gerrit instead), 2016-07-20 00:24:41]

The CQ bit was checked by vakh@chromium.org to run a CQ dry run

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

https://codereview.chromium.org/2164523002/diff/60001/components/safe_browsin...
File components/safe_browsing_db/v4_store.cc (right):

https://codereview.chromium.org/2164523002/diff/60001/components/safe_browsin...
components/safe_browsing_db/v4_store.cc:433: const HashPrefix& hash_prefix =
full_hash.substr(0, prefix_size);
On 2016/07/19 23:01:31, Nathan Parker wrote:
> This is a reference to a temporary... I'm not sure about the lifetime of that
> here.  Might be safer to make it a non-reference, since there has to be a copy
> anyway.

Done.

https://codereview.chromium.org/2164523002/diff/60001/components/safe_browsin...
components/safe_browsing_db/v4_store.cc:450: const PrefixSize& prefix_size =
hash_prefix.length();
On 2016/07/19 23:01:31, Nathan Parker wrote:
> no need for reference, since it's just as cheap (cheaper, actually) to copy
the
> length than it is to copy a ptr to the length.  And this is a reference to a
> temporary.

Done.

https://codereview.chromium.org/2164523002/diff/60001/components/safe_browsin...
components/safe_browsing_db/v4_store.cc:454: HashPrefix mid_prefix =
HashPrefix(mid, mid + prefix_size);
On 2016/07/19 23:01:31, Nathan Parker wrote:
> This is making a copy, which I suppose would copy about log2(num_hashes) of
the
> prefixes.  To avoid it, you could switch to StringPiece.  I still thing
> HashPrefix could be a StringPiece in most cases.

It copies exactly prefix_size bytes.

https://codereview.chromium.org/2164523002/diff/60001/components/safe_browsin...
components/safe_browsing_db/v4_store.cc:458: if (hash_prefix < mid_prefix) {
On 2016/07/19 23:01:31, Nathan Parker wrote:
> You can avoid iterating over both strings twice (in most cases) by using
> std::string::compare(..). It'll return <, =, or > 0 with at most one pass over
> the strings.
> 
> In fact... it allows you to compare against a part of a string, which avoids
the
> copying above.

Done.

https://codereview.chromium.org/2164523002/diff/60001/components/safe_browsin...
File components/safe_browsing_db/v4_store.h (right):

https://codereview.chromium.org/2164523002/diff/60001/components/safe_browsin...
components/safe_browsing_db/v4_store.h:42: typedef HashPrefix FullHash;
On 2016/07/19 23:01:31, Nathan Parker wrote:
> 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.

Yes, but makes following the code much easier.

https://codereview.chromium.org/2164523002/diff/60001/components/safe_browsin...
components/safe_browsing_db/v4_store.h:223:
TestReadFullResponseWithInvalidHashPrefixMap);
On 2016/07/19 23:01:31, Nathan Parker wrote:
> 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.

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

https://codereview.chromium.org/2164523002/diff/60001/components/safe_browsin...
File components/safe_browsing_db/v4_store_unittest.cc (right):

https://codereview.chromium.org/2164523002/diff/60001/components/safe_browsin...
components/safe_browsing_db/v4_store_unittest.cc:536:
EXPECT_TRUE(V4Store::HashPrefixMatches(hash_prefix, std::begin(hash_prefixes),
On 2016/07/19 23:01:31, Nathan Parker wrote:
> nit: These many-short-tests could fit well into one larger test with a comment
> separating each.  That would help avoid the friend-clutter in the .h.

IIRC, during my Noogler orientation this came up and the recommendation  was
that multiple short tests are usually better because the failing test name gives
a good indication of what is causing the failure.

The friend clutter can be avoided using friend class.

https://codereview.chromium.org/2164523002/diff/60001/components/safe_browsin...
components/safe_browsing_db/v4_store_unittest.cc:613:
EXPECT_TRUE(store.GetMatchingHashPrefix(full_hash).empty());
On 2016/07/19 23:01:31, Nathan Parker wrote:
> How about a test that has no matching prefix?
> 

This test. The name has "DoesNot" which may be hard to catch. I could change the
name to make it clearer.

> Question: If there is a match against two different sized prefixes, which one
> should be returned?  Right now it's not defined, since it's an undordered map.

> Should we return the longest match?  We could accomplish that by making it an
> ordered map and then traversing it backwards.  Or maybe it doesn't matter, and
> it should never happen.

That should never happen.

[commit-bot: I haz the power, 2016-07-20 00:25:24]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[vakh (use Gerrit instead), 2016-07-20 00:35:05]

Description was changed from

==========
Add method to check whether a hash prefix exists for a full hash in a V4Store

Overall design document: https://goto.google.com/design-doc-v4store

This CL does the following:
1. Get the full hash that needs to be checked.
2. Iterate over the hash prefix map:
   Key: prefix size (call it 'n'),
   Value: Concatenated list of sorted hash prefixes of size 'n' (call it 'l').
3. Get the hash prefix of size 'n' from the full hash.
4. Binary search for this hash prefix in 'l'.

BUG=543161
==========

to

==========
Add method to check whether a hash prefix exists for a full hash in a V4Store

Overall design document: https://goto.google.com/design-doc-v4store

This CL does the following:
1. Get the full hash that needs to be checked.
2. Iterate over the hash prefix map:
   Key: prefix size (call it 'n'),
   Value: Concatenated list of sorted hash prefixes of size 'n' (call it 'l').
3. Get the hash prefix of size 'n' from the full hash.
4. Binary search for this hash prefix in 'l'.

BUG=543161
==========

[Nathan Parker, 2016-07-20 00:36:47]

lgtm

https://codereview.chromium.org/2164523002/diff/60001/components/safe_browsin...
File components/safe_browsing_db/v4_store_unittest.cc (right):

https://codereview.chromium.org/2164523002/diff/60001/components/safe_browsin...
components/safe_browsing_db/v4_store_unittest.cc:613:
EXPECT_TRUE(store.GetMatchingHashPrefix(full_hash).empty());
On 2016/07/20 00:24:52, vakh wrote:
> On 2016/07/19 23:01:31, Nathan Parker wrote:
> > How about a test that has no matching prefix?
> > 
> 
> This test. The name has "DoesNot" which may be hard to catch. I could change
the
> name to make it clearer.
> 
> > Question: If there is a match against two different sized prefixes, which
one
> > should be returned?  Right now it's not defined, since it's an undordered
map.
> 
> > Should we return the longest match?  We could accomplish that by making it
an
> > ordered map and then traversing it backwards.  Or maybe it doesn't matter,
and
> > it should never happen.
> 
> That should never happen.

ok, maybe we could add a comment in the code that says what happens if it did
("we pick one of the hashes, and which one is undefined").

https://codereview.chromium.org/2164523002/diff/80001/components/safe_browsin...
File components/safe_browsing_db/v4_store.cc (right):

https://codereview.chromium.org/2164523002/diff/80001/components/safe_browsin...
components/safe_browsing_db/v4_store.cc:459: if (result < 0) {
nit: put elses on none of these or all of them.

[commit-bot: I haz the power, 2016-07-20 01:46:09]

The CQ bit was unchecked by commit-bot@chromium.org

[commit-bot: I haz the power, 2016-07-20 01:46:10]

Dry run: This issue passed the CQ dry run.

[vakh (use Gerrit instead), 2016-07-20 06:10:45]

Add comment about what happens if there are more than one hash prefixes that
match a given full hash

[vakh (use Gerrit instead), 2016-07-20 06:10:48]

The CQ bit was checked by vakh@chromium.org to run a CQ dry run

[commit-bot: I haz the power, 2016-07-20 06:10:58]

Dry run: CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[vakh (use Gerrit instead), 2016-07-20 06:12:04]

https://codereview.chromium.org/2164523002/diff/60001/components/safe_browsin...
File components/safe_browsing_db/v4_store_unittest.cc (right):

https://codereview.chromium.org/2164523002/diff/60001/components/safe_browsin...
components/safe_browsing_db/v4_store_unittest.cc:613:
EXPECT_TRUE(store.GetMatchingHashPrefix(full_hash).empty());
On 2016/07/20 00:36:47, Nathan Parker wrote:
> On 2016/07/20 00:24:52, vakh wrote:
> > On 2016/07/19 23:01:31, Nathan Parker wrote:
> > > How about a test that has no matching prefix?
> > > 
> > 
> > This test. The name has "DoesNot" which may be hard to catch. I could change
> the
> > name to make it clearer.
> > 
> > > Question: If there is a match against two different sized prefixes, which
> one
> > > should be returned?  Right now it's not defined, since it's an undordered
> map.
> > 
> > > Should we return the longest match?  We could accomplish that by making it
> an
> > > ordered map and then traversing it backwards.  Or maybe it doesn't matter,
> and
> > > it should never happen.
> > 
> > That should never happen.
> 
> ok, maybe we could add a comment in the code that says what happens if it did
> ("we pick one of the hashes, and which one is undefined").  

Done.

https://codereview.chromium.org/2164523002/diff/80001/components/safe_browsin...
File components/safe_browsing_db/v4_store.cc (right):

https://codereview.chromium.org/2164523002/diff/80001/components/safe_browsin...
components/safe_browsing_db/v4_store.cc:459: if (result < 0) {
On 2016/07/20 00:36:47, Nathan Parker wrote:
> nit: put elses on none of these or all of them.

Done.

[vakh (use Gerrit instead), 2016-07-20 06:12:37]

The CQ bit was checked by vakh@chromium.org

[vakh (use Gerrit instead), 2016-07-20 06:12:38]

The patchset sent to the CQ was uploaded after l-g-t-m from nparker@chromium.org
Link to the patchset: https://codereview.chromium.org/2164523002/#ps100001
(title: "Add comment about what happens if there are more than one hash prefixes
that match a given full hash")

[commit-bot: I haz the power, 2016-07-20 06:12:45]

CQ is trying da patch. Follow status at
 
https://chromium-cq-status.appspot.com/v2/patch-status/codereview.chromium.or...

[commit-bot: I haz the power, 2016-07-20 07:00:23]

Description was changed from

==========
Add method to check whether a hash prefix exists for a full hash in a V4Store

Overall design document: https://goto.google.com/design-doc-v4store

This CL does the following:
1. Get the full hash that needs to be checked.
2. Iterate over the hash prefix map:
   Key: prefix size (call it 'n'),
   Value: Concatenated list of sorted hash prefixes of size 'n' (call it 'l').
3. Get the hash prefix of size 'n' from the full hash.
4. Binary search for this hash prefix in 'l'.

BUG=543161
==========

to

==========
Add method to check whether a hash prefix exists for a full hash in a V4Store

Overall design document: https://goto.google.com/design-doc-v4store

This CL does the following:
1. Get the full hash that needs to be checked.
2. Iterate over the hash prefix map:
   Key: prefix size (call it 'n'),
   Value: Concatenated list of sorted hash prefixes of size 'n' (call it 'l').
3. Get the hash prefix of size 'n' from the full hash.
4. Binary search for this hash prefix in 'l'.

BUG=543161
==========

[commit-bot: I haz the power, 2016-07-20 07:00:24]

Committed patchset #6 (id:100001)

[commit-bot: I haz the power, 2016-07-20 07:00:28]

CQ bit was unchecked.

[commit-bot: I haz the power, 2016-07-20 07:03:20]

Description was changed from

==========
Add method to check whether a hash prefix exists for a full hash in a V4Store

Overall design document: https://goto.google.com/design-doc-v4store

This CL does the following:
1. Get the full hash that needs to be checked.
2. Iterate over the hash prefix map:
   Key: prefix size (call it 'n'),
   Value: Concatenated list of sorted hash prefixes of size 'n' (call it 'l').
3. Get the hash prefix of size 'n' from the full hash.
4. Binary search for this hash prefix in 'l'.

BUG=543161
==========

to

==========
Add method to check whether a hash prefix exists for a full hash in a V4Store

Overall design document: https://goto.google.com/design-doc-v4store

This CL does the following:
1. Get the full hash that needs to be checked.
2. Iterate over the hash prefix map:
   Key: prefix size (call it 'n'),
   Value: Concatenated list of sorted hash prefixes of size 'n' (call it 'l').
3. Get the hash prefix of size 'n' from the full hash.
4. Binary search for this hash prefix in 'l'.

BUG=543161

Committed: https://crrev.com/3f60e959d55033a90ed38f890a4fe17d092d7e5b
Cr-Commit-Position: refs/heads/master@{#406508}
==========

[commit-bot: I haz the power, 2016-07-20 07:03:21]

Patchset 6 (id:??) landed as
https://crrev.com/3f60e959d55033a90ed38f890a4fe17d092d7e5b
Cr-Commit-Position: refs/heads/master@{#406508}