Add dictionary comparing functions and unit tests

Add dictionary comparing functions to DictionaryValue and unit tests

TEST=none
BUG=none

Committed: http://src.chromium.org/viewvc/chrome?view=rev&revision=54879

[danno, 2010-08-02 15:00:56]

Please review

[Mattias Nissler (ping if slow), 2010-08-02 15:39:24]

Looks pretty good, I've put notes on stuff I think could be improved.

http://codereview.chromium.org/3035045/diff/17001/18001
File base/values.cc (right):

http://codereview.chromium.org/3035045/diff/17001/18001#newcode725
base/values.cc:725: if (!other) {
Put a comment saying that we recursively add all paths from the |this|
dictionary, since they are not in |other|.

http://codereview.chromium.org/3035045/diff/17001/18001#newcode738
base/values.cc:738: } else {
Maybe a comment here as well? I liked the comment you had in your original code.

http://codereview.chromium.org/3035045/diff/17001/18001#newcode746
base/values.cc:746: std::map<std::wstring, Value*>::const_iterator key_iterator
= NULL;
Why not just grab the key name directly like this:

const std::wstring& key_name

http://codereview.chromium.org/3035045/diff/17001/18001#newcode747
base/values.cc:747: bool should_add_path = true;
I'd prefer to rename this to reflect its semantics, i.e. something like
subtree_differs.

http://codereview.chromium.org/3035045/diff/17001/18001#newcode779
base/values.cc:779: }
Have you tried to swap the above nested conditionals? I imagine the code to be
more clear if you check for the type in the outer conditional, and you can share
a recursion_this assignment, but your call.

Also, you can use IsType(Value::TYPE_DICTIONARY). Doesn't help readability a
lot, but maybe a little ;)

http://codereview.chromium.org/3035045/diff/17001/18002
File base/values.h (right):

http://codereview.chromium.org/3035045/diff/17001/18002#newcode323
base/values.h:323: // Path strings are in ascending lexigraphical order in the
generated vector.
... are _placed_ in ...

http://codereview.chromium.org/3035045/diff/17001/18002#newcode324
base/values.h:324: // |different_paths| is cleared before added any paths.
Please also mention how you handle path prefixes, i.e. is value equality also
checked for inner nodes?

http://codereview.chromium.org/3035045/diff/17001/18002#newcode361
base/values.h:361: // false.
Seems like having the comment twice is not very useful, maybe refer to the other
function and just mention the additional API?

No matter what you decide to do, please do mention what |path_prefix| is used
for.

http://codereview.chromium.org/3035045/diff/17001/18003
File base/values_unittest.cc (right):

http://codereview.chromium.org/3035045/diff/17001/18003#newcode8
base/values_unittest.cc:8: #include "base/stl_util-inl.h"
What is this included needed for?

http://codereview.chromium.org/3035045/diff/17001/18003#newcode654
base/values_unittest.cc:654: dict1->GetDifferingPaths(dict2.get(),
&differing_paths);
I think this and the below code would greatly benefit from a helper function
that takes the two dictionaries and an array of wstrings and does the checking.

http://codereview.chromium.org/3035045/diff/17001/18003#newcode683
base/values_unittest.cc:683: differing_paths.end(), L"segment4.segment5") !=
differing_paths.end());
Does this block stating add 670 add any additional coverage over what you
already checked in 659-668?

http://codereview.chromium.org/3035045/diff/17001/18003#newcode686
base/values_unittest.cc:686: // GetDifferingPaths
Is the linebreak really needed?

Btw. If you have the checking helper, you can check the commutative property for
all inputs, no need for the following three then.

http://codereview.chromium.org/3035045/diff/17001/18003#newcode769
base/values_unittest.cc:769: // Test a deep dictionary structure.
Does that actually improve coverage?

http://codereview.chromium.org/3035045/diff/17001/18003#newcode800
base/values_unittest.cc:800: // For code coverage completeness.
Ok, so you might want to state in the comment what exactly makes it more
complete.

http://codereview.chromium.org/3035045/diff/17001/18003#newcode818
base/values_unittest.cc:818: differing_paths.end(), L"s1.s2") !=
differing_paths.end());
And here is code duplication for reversing the arguments again. Can we have that
helper?

[danno, 2010-08-02 16:48:40]

Addressed feedback

http://codereview.chromium.org/3035045/diff/17001/18001
File base/values.cc (right):

http://codereview.chromium.org/3035045/diff/17001/18001#newcode725
base/values.cc:725: if (!other) {
On 2010/08/02 15:39:24, mnissler wrote:
> Put a comment saying that we recursively add all paths from the |this|
> dictionary, since they are not in |other|.

Done.

http://codereview.chromium.org/3035045/diff/17001/18001#newcode738
base/values.cc:738: } else {
On 2010/08/02 15:39:24, mnissler wrote:
> Maybe a comment here as well? I liked the comment you had in your original
code.

Done.

http://codereview.chromium.org/3035045/diff/17001/18001#newcode746
base/values.cc:746: std::map<std::wstring, Value*>::const_iterator key_iterator
= NULL;
Done, but not convinced this makes the code more readable.
On 2010/08/02 15:39:24, mnissler wrote:
> Why not just grab the key name directly like this:
> 
> const std::wstring& key_name

http://codereview.chromium.org/3035045/diff/17001/18001#newcode747
base/values.cc:747: bool should_add_path = true;
On 2010/08/02 15:39:24, mnissler wrote:
> I'd prefer to rename this to reflect its semantics, i.e. something like
> subtree_differs.

Done.

http://codereview.chromium.org/3035045/diff/17001/18001#newcode779
base/values.cc:779: }
On 2010/08/02 15:39:24, mnissler wrote:
> Have you tried to swap the above nested conditionals? I imagine the code to be
> more clear if you check for the type in the outer conditional, and you can
share
> a recursion_this assignment, but your call.
> 
> Also, you can use IsType(Value::TYPE_DICTIONARY). Doesn't help readability a
> lot, but maybe a little ;)

Done.

http://codereview.chromium.org/3035045/diff/17001/18002
File base/values.h (right):

http://codereview.chromium.org/3035045/diff/17001/18002#newcode323
base/values.h:323: // Path strings are in ascending lexigraphical order in the
generated vector.
On 2010/08/02 15:39:24, mnissler wrote:
> ... are _placed_ in ...

Done.

http://codereview.chromium.org/3035045/diff/17001/18002#newcode324
base/values.h:324: // |different_paths| is cleared before added any paths.
I don't understand what you're getting at. What do path prefixes have to do with
inner nodes? How value equality is handled is explicitly described in the
comment: "These are paths ... that are present in both dictionaries but differ
in value."
On 2010/08/02 15:39:24, mnissler wrote:
> Please also mention how you handle path prefixes, i.e. is value equality also
> checked for inner nodes?

http://codereview.chromium.org/3035045/diff/17001/18002#newcode361
base/values.h:361: // false.
On 2010/08/02 15:39:24, mnissler wrote:
> Seems like having the comment twice is not very useful, maybe refer to the
other
> function and just mention the additional API?
> 
> No matter what you decide to do, please do mention what |path_prefix| is used
> for.

Done.

http://codereview.chromium.org/3035045/diff/17001/18003
File base/values_unittest.cc (right):

http://codereview.chromium.org/3035045/diff/17001/18003#newcode8
base/values_unittest.cc:8: #include "base/stl_util-inl.h"
On 2010/08/02 15:39:24, mnissler wrote:
> What is this included needed for?

Done.

http://codereview.chromium.org/3035045/diff/17001/18003#newcode654
base/values_unittest.cc:654: dict1->GetDifferingPaths(dict2.get(),
&differing_paths);
On 2010/08/02 15:39:24, mnissler wrote:
> I think this and the below code would greatly benefit from a helper function
> that takes the two dictionaries and an array of wstrings and does the
checking.

Done.

http://codereview.chromium.org/3035045/diff/17001/18003#newcode683
base/values_unittest.cc:683: differing_paths.end(), L"segment4.segment5") !=
differing_paths.end());
yes.
On 2010/08/02 15:39:24, mnissler wrote:
> Does this block stating add 670 add any additional coverage over what you
> already checked in 659-668?

http://codereview.chromium.org/3035045/diff/17001/18003#newcode686
base/values_unittest.cc:686: // GetDifferingPaths
On 2010/08/02 15:39:24, mnissler wrote:
> Is the linebreak really needed?
> 
> Btw. If you have the checking helper, you can check the commutative property
for
> all inputs, no need for the following three then.

Done.

http://codereview.chromium.org/3035045/diff/17001/18003#newcode769
base/values_unittest.cc:769: // Test a deep dictionary structure.
yes.
On 2010/08/02 15:39:24, mnissler wrote:
> Does that actually improve coverage?

http://codereview.chromium.org/3035045/diff/17001/18003#newcode800
base/values_unittest.cc:800: // For code coverage completeness.
Um, why? I'll add a comment, but it seems a little silly: Make sure that all
branches that were not covered are executed.
On 2010/08/02 15:39:24, mnissler wrote:
> Ok, so you might want to state in the comment what exactly makes it more
> complete.

http://codereview.chromium.org/3035045/diff/17001/18003#newcode818
base/values_unittest.cc:818: differing_paths.end(), L"s1.s2") !=
differing_paths.end());
On 2010/08/02 15:39:24, mnissler wrote:
> And here is code duplication for reversing the arguments again. Can we have
that
> helper?

Done.

[Paweł Hajdan Jr., 2010-08-02 17:49:41]

Drive-by with minor test comments.

http://codereview.chromium.org/3035045/diff/27001/25004
File base/values_unittest.cc (right):

http://codereview.chromium.org/3035045/diff/27001/25004#newcode24
base/values_unittest.cc:24: EXPECT_TRUE(differing_paths.size() ==
expected_paths_count);
nit: EXPECT_EQ, please.

http://codereview.chromium.org/3035045/diff/27001/25004#newcode31
base/values_unittest.cc:31: EXPECT_TRUE(differing_paths.size() ==
expected_paths_count);
nit: EXPECT_EQ

[Mattias Nissler (ping if slow), 2010-08-02 18:10:07]

LGTM with nits. Probably also needs rebasing, see trybots.

On 2010/08/02 17:49:41, Paweł Hajdan Jr. wrote:
> Drive-by with minor test comments.
> 
> http://codereview.chromium.org/3035045/diff/27001/25004
> File base/values_unittest.cc (right):
> 
> http://codereview.chromium.org/3035045/diff/27001/25004#newcode24
> base/values_unittest.cc:24: EXPECT_TRUE(differing_paths.size() ==
> expected_paths_count);
> nit: EXPECT_EQ, please.
> 
> http://codereview.chromium.org/3035045/diff/27001/25004#newcode31
> base/values_unittest.cc:31: EXPECT_TRUE(differing_paths.size() ==
> expected_paths_count);
> nit: EXPECT_EQ

[Mattias Nissler (ping if slow), 2010-08-02 18:12:25]

Comment should have gone here, sorry. Again: LGTM with nits. Probably also needs
rebasing, see trybots.

http://codereview.chromium.org/3035045/diff/17001/18002
File base/values.h (right):

http://codereview.chromium.org/3035045/diff/17001/18002#newcode324
base/values.h:324: // |different_paths| is cleared before added any paths.
On 2010/08/02 16:48:41, danno wrote:
> I don't understand what you're getting at. What do path prefixes have to do
with
> inner nodes? How value equality is handled is explicitly described in the
> comment: "These are paths ... that are present in both dictionaries but differ
> in value."

OK, that was what I meant, I agree it's covered by the comment.

> On 2010/08/02 15:39:24, mnissler wrote:
> > Please also mention how you handle path prefixes, i.e. is value equality
also
> > checked for inner nodes?
> 
>

http://codereview.chromium.org/3035045/diff/17001/18003
File base/values_unittest.cc (right):

http://codereview.chromium.org/3035045/diff/17001/18003#newcode800
base/values_unittest.cc:800: // For code coverage completeness.
Well, when reading this I wondered what cases you cover here that you don't have
covered above. Seems you thought about it, wrote the test and put the comment,
so I thought it'd be nice if you shared your train of thoughts with the reader
:)

On 2010/08/02 16:48:41, danno wrote:
> Um, why? I'll add a comment, but it seems a little silly: Make sure that all
> branches that were not covered are executed.
> On 2010/08/02 15:39:24, mnissler wrote:
> > Ok, so you might want to state in the comment what exactly makes it more
> > complete.
> 
>

http://codereview.chromium.org/3035045/diff/27001/25002
File base/values.cc (right):

http://codereview.chromium.org/3035045/diff/27001/25002#newcode743
base/values.cc:743: // and recursing over dictionaries.
Your English is definitely better than mine, so please disregard if not
appropriate, but I feel it should say "recurse"

http://codereview.chromium.org/3035045/diff/27001/25002#newcode755
base/values.cc:755: current_other->first : current_this->first);
Oh, what I intended was to declare the reference here and then initialize it in
each branch. I agree that what you have now isn't more readable.

http://codereview.chromium.org/3035045/diff/27001/25003
File base/values.h (right):

http://codereview.chromium.org/3035045/diff/27001/25003#newcode359
base/values.h:359: // the current one are concatted and passed through to deeper
calls in
concatenated

http://codereview.chromium.org/3035045/diff/27001/25004
File base/values_unittest.cc (right):

http://codereview.chromium.org/3035045/diff/27001/25004#newcode19
base/values_unittest.cc:19: size_t expected_paths_count) {
Can't you just use

std::vector expected_paths_vector(expected_paths, expected_paths +
expected_paths_count);

here and then check for EXPECT_EQ(expected_paths_vector, differing_paths)?

[danno, 2010-08-03 13:36:39]

The changes were big enough that I'd like you to take one more look, Mattias.

http://codereview.chromium.org/3035045/diff/27001/25002
File base/values.cc (right):

http://codereview.chromium.org/3035045/diff/27001/25002#newcode743
base/values.cc:743: // and recursing over dictionaries.
I think it is correct, since it should match "adding", since it is describing
what is happening during the iterating. However, I changed the phrasing entirely
to avoid the problem altogether.

On 2010/08/02 18:12:25, mnissler wrote:
> Your English is definitely better than mine, so please disregard if not
> appropriate, but I feel it should say "recurse

http://codereview.chromium.org/3035045/diff/27001/25003
File base/values.h (right):

http://codereview.chromium.org/3035045/diff/27001/25003#newcode359
base/values.h:359: // the current one are concatted and passed through to deeper
calls in
On 2010/08/02 18:12:25, mnissler wrote:
> concatenated

Done.

http://codereview.chromium.org/3035045/diff/27001/25003#newcode359
base/values.h:359: // the current one are concatted and passed through to deeper
calls in
On 2010/08/02 18:12:25, mnissler wrote:
> concatenated

Done.

http://codereview.chromium.org/3035045/diff/27001/25004
File base/values_unittest.cc (right):

http://codereview.chromium.org/3035045/diff/27001/25004#newcode19
base/values_unittest.cc:19: size_t expected_paths_count) {
I don't think so, since you need to initialize the wstrings individually when
building the vector. But as discussed, there's a solution by using equals from
<algorithm> that works well and even found a bug :-)

On 2010/08/02 18:12:25, mnissler wrote:
> Can't you just use
> 
> std::vector expected_paths_vector(expected_paths, expected_paths +
> expected_paths_count);
> 
> here and then check for EXPECT_EQ(expected_paths_vector, differing_paths)?

http://codereview.chromium.org/3035045/diff/27001/25004#newcode24
base/values_unittest.cc:24: EXPECT_TRUE(differing_paths.size() ==
expected_paths_count);
On 2010/08/02 17:49:41, Paweł Hajdan Jr. wrote:
> nit: EXPECT_EQ, please.

Done.

http://codereview.chromium.org/3035045/diff/27001/25004#newcode31
base/values_unittest.cc:31: EXPECT_TRUE(differing_paths.size() ==
expected_paths_count);
On 2010/08/02 17:49:41, Paweł Hajdan Jr. wrote:
> nit: EXPECT_EQ

Done.

[Mattias Nissler (ping if slow), 2010-08-03 15:17:48]

LGTM, only two spelling nits. Understanding the dictionary comparison logic is
still quite complex, but I don't know a better way myself.

http://codereview.chromium.org/3035045/diff/26002/38001
File base/values.cc (right):

http://codereview.chromium.org/3035045/diff/26002/38001#newcode953
base/values.cc:953: // In order to maintain lexical sotring order, directory
s/sotring/sorting/

http://codereview.chromium.org/3035045/diff/26002/38001#newcode954
base/values.cc:954: // paths are pushed "optimistically" assuming that thier
subtree will
s/thier/their/