Make some improvements to sync model associator:...

Make some improvements to sync model associator:
- Fail the load assocications if there the total number of
  nodes in the bookmark model and the sync model don't match
  (issue: 25542)
- Add a bookmark id index and use that during load assocications
  instead of calling BookmarkModel::GetNodeByID since the latter
  traverses the entier tree in DFS order until it finds the node
  with the given ID.
- Add a unit test that would exercise the new model associator
  load associations behavior.

BUG=25542
TEST=Unit test added.


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

[tim (not reviewing), 2009-10-27 21:46:54]

http://codereview.chromium.org/337037/diff/1/2
File chrome/browser/sync/glue/model_associator.cc (right):

http://codereview.chromium.org/337037/diff/1/2#newcode133
Line 133: typedef std::map<int64, const BookmarkNode*> BookmarkIdMap;
I would use a base::hash_map here, since you only need to optimize for insert &
lookup (afaict), and lookup would be O(1) instead of O(lgn).

http://codereview.chromium.org/337037/diff/1/2#newcode509
Line 509: id_index.AddAll(model->GetBookmarkBarNode());
This really hurts the complexity benefits of LoadAssociations v
BuildAssociations, doesn't it? Would it be hard to somehow keep this count in
the BookmarkModel? It seems like if it needs to read in all the nodes from the
JSON file, it could count how many times it created a node, and keep that up to
date afterwards.  It's a bit of work to implement, I admit.

Also, might this index be useful at all to BuildAssociations (the
BookmarkNodeFinder)? If so, we could compute it before calling LoadAssociations.

[Munjal (Google), 2009-10-28 19:50:54]

http://codereview.chromium.org/337037/diff/1/2
File chrome/browser/sync/glue/model_associator.cc (right):

http://codereview.chromium.org/337037/diff/1/2#newcode133
Line 133: typedef std::map<int64, const BookmarkNode*> BookmarkIdMap;
On 2009/10/27 21:46:56, timsteele wrote:
> I would use a base::hash_map here, since you only need to optimize for insert
&
> lookup (afaict), and lookup would be O(1) instead of O(lgn).

Done.

http://codereview.chromium.org/337037/diff/1/2#newcode509
Line 509: id_index.AddAll(model->GetBookmarkBarNode());
On 2009/10/27 21:46:56, timsteele wrote:
> This really hurts the complexity benefits of LoadAssociations v
> BuildAssociations, doesn't it? Would it be hard to somehow keep this count in
> the BookmarkModel? It seems like if it needs to read in all the nodes from the
> JSON file, it could count how many times it created a node, and keep that up
to
> date afterwards.  It's a bit of work to implement, I admit.
> 
> Also, might this index be useful at all to BuildAssociations (the
> BookmarkNodeFinder)? If so, we could compute it before calling
LoadAssociations.

As we talked about this yesterday and today, and after following up with Scott,
we decided that we should keep the bookmark id index here, and not in the
bookmark model. Once we fix the TODO of keeping bookmark node pointers in the ID
maps instead of IDs, we won't need to call GetNodeByID and hence keeping the ID
index in bookmark model forever is not needed.

[tim (not reviewing), 2009-10-28 22:12:29]

LGTM with nits addressed.

+cc sky in case he has thoughts/concerns about the following

I think what you've got here works just fine. The only other possible
improvement I came up with is if it would be possible for the BookmarkCodec (or
whatever entity parses the JSON file) to just track how many actual nodes it
parsed when it loaded the file at startup.  This count wouldn't have to be kept
up to date in the BookmarkModel. It would get set at the start, and never change
after. But we could query it from here, and it would suffice for our purposes.

http://codereview.chromium.org/337037/diff/5002/6002
File chrome/browser/sync/glue/model_associator.cc (right):

http://codereview.chromium.org/337037/diff/5002/6002#newcode118
Line 118: public:
nit- indent

http://codereview.chromium.org/337037/diff/5002/6002#newcode150
Line 150: for (int i = 0; i < node->GetChildCount(); ++i) {
nit- you don't use squiggles for the other one-line control/condition statements
in here, please choose one of the two for consistency.

http://codereview.chromium.org/337037/diff/5002/6002#newcode206
Line 206: // bookmark node pointers in our ID maps to avoid finding node by IDs.
can we file a bug to track and reference here?

http://codereview.chromium.org/337037/diff/5002/6003
File chrome/browser/sync/profile_sync_service_unittest.cc (right):

http://codereview.chromium.org/337037/diff/5002/6003#newcode1253
Line 1253: // Now restart the sync service. This time it should use the
persistent
Wait, use the persisted associations, or rebuild?

[Munjal (Google), 2009-10-28 22:27:37]

http://codereview.chromium.org/337037/diff/5002/6002
File chrome/browser/sync/glue/model_associator.cc (right):

http://codereview.chromium.org/337037/diff/5002/6002#newcode118
Line 118: public:
On 2009/10/28 22:12:29, timsteele wrote:
> nit- indent

Done.

http://codereview.chromium.org/337037/diff/5002/6002#newcode150
Line 150: for (int i = 0; i < node->GetChildCount(); ++i) {
On 2009/10/28 22:12:29, timsteele wrote:
> nit- you don't use squiggles for the other one-line control/condition
statements
> in here, please choose one of the two for consistency.

Done.

http://codereview.chromium.org/337037/diff/5002/6002#newcode206
Line 206: // bookmark node pointers in our ID maps to avoid finding node by IDs.
On 2009/10/28 22:12:29, timsteele wrote:
> can we file a bug to track and reference here?

Done.

http://codereview.chromium.org/337037/diff/5002/6003
File chrome/browser/sync/profile_sync_service_unittest.cc (right):

http://codereview.chromium.org/337037/diff/5002/6003#newcode1253
Line 1253: // Now restart the sync service. This time it should use the
persistent
On 2009/10/28 22:12:29, timsteele wrote:
> Wait, use the persisted associations, or rebuild?

Done.

[Munjal (Google), 2009-10-28 22:31:47]

On Wed, Oct 28, 2009 at 3:12 PM, <tim@chromium.org> wrote:

> LGTM with nits addressed.
>
> +cc sky in case he has thoughts/concerns about the following
>
> I think what you've got here works just fine. The only other possible
> improvement I came up with is if it would be possible for the BookmarkCodec
> (or
> whatever entity parses the JSON file) to just track how many actual nodes
> it
> parsed when it loaded the file at startup.  This count wouldn't have to be
> kept
> up to date in the BookmarkModel. It would get set at the start, and never
> change
> after. But we could query it from here, and it would suffice for our
> purposes.
>
>
I probably didn't clarify well in person yesterday that this is not needed
and doesn't improve anything because we now already build an ID index and
hence querying the size of the hash map of that index gives us the number of
nodes.

If we didn't need the ID index, then such a change might help, but we do
need ID index.


> http://codereview.chromium.org/337037/diff/5002/6002
>
> File chrome/browser/sync/glue/model_associator.cc (right):
>
> http://codereview.chromium.org/337037/diff/5002/6002#newcode118
> Line 118: public:
> nit- indent
>
> http://codereview.chromium.org/337037/diff/5002/6002#newcode150
> Line 150: for (int i = 0; i < node->GetChildCount(); ++i) {
> nit- you don't use squiggles for the other one-line control/condition
> statements in here, please choose one of the two for consistency.
>
> http://codereview.chromium.org/337037/diff/5002/6002#newcode206
> Line 206: // bookmark node pointers in our ID maps to avoid finding node
> by IDs.
> can we file a bug to track and reference here?
>
> http://codereview.chromium.org/337037/diff/5002/6003
> File chrome/browser/sync/profile_sync_service_unittest.cc (right):
>
> http://codereview.chromium.org/337037/diff/5002/6003#newcode1253
> Line 1253: // Now restart the sync service. This time it should use the
> persistent
> Wait, use the persisted associations, or rebuild?
>
>
> http://codereview.chromium.org/337037
>