1324503 - Sync reordered my bookmarks toolbar

Status: RESOLVED FIXED

(Firefox :: Sync, defect)

Description

[Lina Butler [:lina]]

Over the weekend, Sync reordered my toolbar. The new order appears random (the 1st, 2nd, and 3rd bookmarks are now the 18th, 19th, and 20th; but the 4th is now the 8th), though all folders precede bookmarks.

I wonder if the sync was interrupted after downloading new bookmarks, but before `_orderChildren` finished. We advance `lastSync` in http://searchfox.org/mozilla-central/rev/a6a339991dbc650bab3aefe939cd0e5ac302274a/services/sync/modules/engines.js#1211-1213,1250-1252, but reorder children after (http://searchfox.org/mozilla-central/rev/a6a339991dbc650bab3aefe939cd0e5ac302274a/services/sync/modules/engines/bookmarks.js#527,533).

Our "sort index" also gives more weight to folders, which might explain why the folders come first (http://searchfox.org/mozilla-central/rev/a6a339991dbc650bab3aefe939cd0e5ac302274a/services/sync/modules/engines/bookmarks.js#822-824).

I noticed this after adding a new bookmark to the toolbar, so I think Sync now sees this as the "correct" ordering. (I also have no validation errors, so at least the server is consistent).

Comment 1

[Lina Butler [:lina]]

Needs some investigation. Can we reproduce reliably?

Comment 2

[Lina Butler [:lina]]

I noticed something interesting:

1. On my work laptop, I added a bookmark to the toolbar while offline (waiting in the airport), and moved it to the first position.
2. The next day, on my personal laptop, I removed a different bookmark from the toolbar, and synced. I think I also added one or two bookmarks to the menu.
3. This morning, I turned on my work laptop again, opened Firefox, and synced.

Sync applied the deletion and uploaded the new bookmark (good), but moved the bookmark I added in (1) to the last position in the toolbar. I think this is because the toolbar record on the server is newer, thanks to (2), but doesn't include bookmark (1).

Unlike comment 0, this didn't move any of the other items in the toolbar. But I wonder if we can trigger reordering by adding items to the same folder while Sync is offline, or hasn't started yet.

Some other thoughts:

* My menu looks funny, too. Toward the end, there are two separators next to each other, followed by "Recently Bookmarked" and some more bookmarks I added last month. Thom said on IRC he saw separators that shouldn't be there in his toolbar; I wonder if this is the same thing.

> <tcsc> oh dang just got hit by bug 1324503
> <tcsc> and it inserted a couple separators that weren't there before...

* I haven't synced my work PC in a while, and it might even have the original toolbar and menu (before December 19th). Something to try would be to add a bookmark to its toolbar and menu, sync, and see what it does with the new bookmarks that I've added on my laptops.

Comment 3

[Mark Hammond [:markh] [:mhammond]]

(In reply to Kit Cambridge [:kitcambridge] from comment #2)
> Sync applied the deletion and uploaded the new bookmark (good), but moved
> the bookmark I added in (1) to the last position in the toolbar. I think
> this is because the toolbar record on the server is newer, thanks to (2),
> but doesn't include bookmark (1).

Yes, this is 100% reproducible, and yes, the problem is that we call PlacesUtils.bookmarks.reorder() with the list of children as known by the server (which doesn't yet know about (1)). reorder() documents that "missing entries will be appended", which is what we are seeing.

This seems tricky to get right - in general though, we can probably be certain that if we are calling .reorder() with a list of child GUIDs and that list excludes items *currently* in that folder, we are sure (*) to screw the order up - and that if the folder isn't marked locally as needing upload, something bad has gone wrong (ie, either the client or server is in a bad state). IOW, we probably need a smarter merge of child order and must guarantee that if the list of children locally isn't exactly the incoming list from the server, we force the folder as requiring upload.

(*) What's complicated here is a deletion when the parent record is seen first - ie, the server's list of children may exclude a current item because a deletion for that item is coming in a future record in this same sync.

What's possibly worse is that we only track the children to reorder in memory, meaning that an interrupted sync may also cause problems here - ie:
* incoming record with ordered children - we apply all the records correctly parented, but not yet ordered.
* sync is interrupted before we reorder - the order on this client is different than the server. IIUC, the order locally is likely to be the order in which the new item records were applied.
* later the parent is flagged as modified (eg, due to a new bookmark etc) and the current "arbitrary" order is re-uploaded to the server.

This could possibly be solved by moving back to an annotation to flag folders needing reorder. 2-phase application will also help, but I'm not sure it makes sense to wait for that. Thoughts?

> * My menu looks funny, too. Toward the end, there are two separators next to
> each other, followed by "Recently Bookmarked" and some more bookmarks I
> added last month. Thom said on IRC he saw separators that shouldn't be there
> in his toolbar; I wonder if this is the same thing.

That certainly is odd - the hypothesis above wouldn't explain how items end up in the wrong parent (which I'm guessing is what must have happened here)

Comment 4

[Mark Hammond [:markh] [:mhammond]]

huh - it seems that reorder behaviour is already on release. I'm not sure if that's good (ie, less likely to be a recent regression) or bad (uh-oh!) :)

Comment 5

[Kanchan Kumari QA]

I am seeing this issue at my end too. Bookmarks arrangement is out of order and it syncs with same(wrong)order on other device too.

Comment 6

[Thom Chiovoloni [:tcsc] (ex-moco)]

Attachment: Bug 1324503 - Avoid reordering bookmark folders unnecessarially during sync

This makes two changes:

1. when possible, we avoid reordering all-together.
2. when we must reorder, we fall back to the current order for items that we
   don't have a specified order for (previously this was unspecified).

Review commit: https://reviewboard.mozilla.org/r/106638/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/106638/

Comment 7

[Thom Chiovoloni [:tcsc] (ex-moco)]

To be clear, this patch only addresses the wrong ordering within a folder (which AFAICT we just don't do right at all). 

Wrong parent or weird separator issues aren't fixed by this patch (and probably deserve a separate bug...).

(Feel free to review also mark, but seeing as it's mostly PSU changes, seemed like kit was the right reviewer.)

Comment 8

[Lina Butler [:lina]]

Comment on attachment 8829594 [details]
Bug 1324503 - Avoid reordering bookmark folders unnecessarially during sync

https://reviewboard.mozilla.org/r/106638/#review107692

Looks good! A couple of nits, which you're welcome to ignore, and a general question to make sure I'm understanding the patch correctly.

::: toolkit/components/places/Bookmarks.jsm:1299
(Diff revision 1)
>          let guid = orderedChildrenGuids[i];
>          guidIndices.set(guid, i);
>        }
>  
> +      let needReorder = true;
> +      if (options.tryPreserveCurrentOrder) {

Just to make sure I understand...

* If we have a child that's not in `orderedChildrenGuids`, we won't add it to `requestedChildIndices`, either. But, as long as the order of the surrounding children matches, `requestedChildIndices[i - 1] > requestedChildIndices[i]` will always be false, and we'll keep those bookmarks in their current positions.

* If we have a GUID in `orderedChildrenGuids` that doesn't exist, that's still OK. It won't exist in `children`, but we'll preserve the order of surrounding bookmarks that do exist, as before.

* If they're the same, we don't need to do anything; `requestedChildIndices[i - 1] > requestedChildIndices[i]` will be true for all children.

Is that accurate?

::: toolkit/components/places/Bookmarks.jsm:1305
(Diff revision 1)
> +        // If we got an incomplete list but everything we have is in the right
> +        // order, do nothing.
> +        let requestedChildIndices = [];
> +        for (let child of children) {
> +          let index = guidIndices.get(child.guid);
> +          if (index != null) {

Femto-nit: I'd prefer `guidIndices.has(child.guid)`.

::: toolkit/components/places/Bookmarks.jsm:1313
(Diff revision 1)
> +        }
> +        if (requestedChildIndices.length) {
> +          needReorder = false;
> +          for (let i = 1; i < requestedChildIndices.length && !needReorder; ++i) {
> +            if (requestedChildIndices[i - 1] > requestedChildIndices[i]) {
> +              needReorder = true;

Femto-nit: I'd prefer a `break` here, instead of `!needReorder` in the loop condition.

::: toolkit/components/places/Bookmarks.jsm:1318
(Diff revision 1)
> +              needReorder = true;
> +            }
> +          }
> +        }
> +      }
> +      if (needReorder) {

If we don't need to reorder, can we return early and avoid the `UPDATE` queries entirely?

::: toolkit/components/places/PlacesSyncUtils.jsm:226
(Diff revision 1)
>        // first sync.
>        return undefined;
>      }
>      let orderedChildrenGuids = childSyncIds.map(BookmarkSyncUtils.syncIdToGuid);
>      return PlacesUtils.bookmarks.reorder(parentGuid, orderedChildrenGuids,
> -                                         { source: SOURCE_SYNC });
> +                                         { source: SOURCE_SYNC, tryPreserveCurrentOrder });

Do you anticipate we'll want to call `order` with `tryPreserveCurrentOrder = false`? If not, might as well pass `true` here and drop the extra argument. `order` is a thin wrapper around `reorder` as it is.

Comment 9

[Mark Hammond [:markh] [:mhammond]]

Comment on attachment 8829594 [details]
Bug 1324503 - Avoid reordering bookmark folders unnecessarially during sync

https://reviewboard.mozilla.org/r/106638/#review107702

I haven't looked too closely at this, but it might make sense to have Mak give it a review too. I expect he would like some tests specifically for Bookmarks.jsm (rather than only indirectly testing this vua PSU) and I'm also wondering if we should have tests for some of the scenarios listed in earlier comments (eg, what happens if we see the parent as incoming and referencing a child that is yet to be processed, but is still incoming in this sync?)

Comment 10

[Mark Hammond [:markh] [:mhammond]]

Comment on attachment 8829594 [details]
Bug 1324503 - Avoid reordering bookmark folders unnecessarially during sync

https://reviewboard.mozilla.org/r/106638/#review107702

huh - reviewboard says "Review flag cleared" - which seems strange and I hope I didn't clobber Kit's r+ - that wasn't my intention.

Comment 11

[Marco Bonardo [:mak] (Away Apr 25 - May 5)]

Comment on attachment 8829594 [details]
Bug 1324503 - Avoid reordering bookmark folders unnecessarially during sync

https://reviewboard.mozilla.org/r/106638/#review108320

Let's make tryPreserveCurrentOrder the default behavior or reorder, and remove the option.
It should not make a big difference, in general a consumer should pass the whole list of guids, the "append" case is there just in case of a new bookmark coming at the "wrong" time.
The case where one could pass a list or guids that are already in order, but incomplete, is rare enough, likely only hitting use-cases like Sync, where any consumer would want the same.
Moreover we save I/O.

And yes, please add test cases specific for Bookmarks.jsm to toolkit/components/places/tests/bookmarks/test_bookmarks_reorder.js
It's possible after changing the default some existing test may need a fix, or maybe we don't have a test covering this specific case yet.

Comment 12

[Thom Chiovoloni [:tcsc] (ex-moco)]

Comment on attachment 8829594 [details]
Bug 1324503 - Avoid reordering bookmark folders unnecessarially during sync

https://reviewboard.mozilla.org/r/106638/#review107692

> Just to make sure I understand...
> 
> * If we have a child that's not in `orderedChildrenGuids`, we won't add it to `requestedChildIndices`, either. But, as long as the order of the surrounding children matches, `requestedChildIndices[i - 1] > requestedChildIndices[i]` will always be false, and we'll keep those bookmarks in their current positions.
> 
> * If we have a GUID in `orderedChildrenGuids` that doesn't exist, that's still OK. It won't exist in `children`, but we'll preserve the order of surrounding bookmarks that do exist, as before.
> 
> * If they're the same, we don't need to do anything; `requestedChildIndices[i - 1] > requestedChildIndices[i]` will be true for all children.
> 
> Is that accurate?

Yes, that all sounds right.

> Femto-nit: I'd prefer `guidIndices.has(child.guid)`.

I did it this way to avoid two lookups into guidIndices, which is probably a pointless microoptimization that only hurts readability, so I changed it.

> Femto-nit: I'd prefer a `break` here, instead of `!needReorder` in the loop condition.

Hmm, well, we still need `needReorder`, so it might be a wash, but ok.

> If we don't need to reorder, can we return early and avoid the `UPDATE` queries entirely?

I think so, but wasn't sure.

Comment 13

[Thom Chiovoloni [:tcsc] (ex-moco)]

Comment on attachment 8829594 [details]
Bug 1324503 - Avoid reordering bookmark folders unnecessarially during sync

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/106638/diff/1-2/

Comment 14

[Marco Bonardo [:mak] (Away Apr 25 - May 5)]

Comment on attachment 8829594 [details]
Bug 1324503 - Avoid reordering bookmark folders unnecessarially during sync

https://reviewboard.mozilla.org/r/106638/#review108904

It looks great, thank you for looking into this.

::: toolkit/components/places/tests/bookmarks/test_bookmarks_reorder.js:103
(Diff revision 2)
> +    }
> +  }
> +
> +  {
> +    // Try a partial sorting by passing 2 entries out of order
> -  // The unspecified entries should retain the original order.
> +    // The unspecified entries should retain the original order.

while here please change the comment to:
"The unspecified entries should be appended and retain the original order."

Comment 15

[Thom Chiovoloni [:tcsc] (ex-moco)]

Comment on attachment 8829594 [details]
Bug 1324503 - Avoid reordering bookmark folders unnecessarially during sync

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/106638/diff/2-3/

Comment 16

[Thom Chiovoloni [:tcsc] (ex-moco)]

Comment on attachment 8829594 [details]
Bug 1324503 - Avoid reordering bookmark folders unnecessarially during sync

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/106638/diff/3-4/

Comment 17

[Thom Chiovoloni [:tcsc] (ex-moco)]

Mak: turns out we can't skip all of the database work in this case. We at least need to clear the orphan annos for sync, and AFAICT we might need to do the moz_bookmarks_reorder_trigger code, but I'm not sure. Kit says we probably don't, but I should ask you. Thoughts?

Comment 18

[Marco Bonardo [:mak] (Away Apr 25 - May 5)]

(In reply to Thom Chiovoloni [:tcsc] from comment #17)
> Mak: turns out we can't skip all of the database work in this case. We at
> least need to clear the orphan annos for sync, and AFAICT we might need to
> do the moz_bookmarks_reorder_trigger code, but I'm not sure. Kit says we
> probably don't, but I should ask you. Thoughts?

I'm not sure I understand, so eventually please clarify to me why you think we would need to. If needReorder is false, we don't touch anything in the database, so we cannot have items with a negative position to fix, that is what the trigger is for. Basically, since the previous UPDATE doesn't run, there's nothing for the trigger to fix, thus running the trigger code looks pointless to me.

Regarding the orphan annos removal, it's something that you know better than me, off-hand looks like you should do that, but please check that with Kit.

Comment 19

[Thom Chiovoloni [:tcsc] (ex-moco)]

Mak: To handle the case referred to by the comment "Update position of items that could have been inserted in the meanwhile". It would make sense to me that we don't need to handle it, but it seemed to be worth asking about.

I'm confident we need to clean up the orphans, we start failing tests and confusing sync if we don't.

Comment 20

[Thom Chiovoloni [:tcsc] (ex-moco)]

Comment on attachment 8829594 [details]
Bug 1324503 - Avoid reordering bookmark folders unnecessarially during sync

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/106638/diff/4-5/

Comment 21

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/6b4c738bb0d8
Avoid reordering bookmark folders unnecessarially during sync r=kitcambridge,mak

Comment 22

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/6b4c738bb0d8

Comment 23

[Thom Chiovoloni [:tcsc] (ex-moco)]

Still a bug, sadly. Reopening and clearing priority/assignee so it ends up in our triage.

Comment 24

[Lina Butler [:lina]]

We'll file a follow-up bug for throwing away a folder's order when the local timestamp is newer. Thom's patch in bug 1349703 should also fix this for roots.