1343365 - Tree-aware bookmark merging

Status: RESOLVED INCOMPLETE

(Firefox for Android Graveyard :: Android Sync, defect, P5)

Description

[Kanchan Kumari QA]

Attachment: ValidationError

Pre-requisite: about sync addon is installed

STR:
1. Sign in to Sync with a new or existing Firefox Account on desktop
2. Create large number of bookmarks (~3000) in nested bookmark hierarchy: a top-level folder containing some bookmarks, and child folders with grandchildren.
3. Sign in to sync on other devices (mobile or another OS)
4. Import bookmarks/nested folder from another browser on Desktop (Step 1 device)

Expected: There is no validation error in about:sync

Actual: Validation error for nested bookmarks i.e. Child record IjsQX4zhn4Bi appears as a child in multiple parents

Attached is validation and error log file

Comment 1

[Kanchan Kumari QA]

Attachment: error-sync-1488310064641.txt

Comment 2

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

Thanks Kanchan, one of us will look at the logs to try and see what's going on here, but we know that a bookmark restore causes issues. Copying Thom who is doing some work around this currently.

Comment 3

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

I haven't been able to replicate this, despite trying fairly hard.

Just to check, how many bookmarks were imported from the other browser?

Comment 4

[Kanchan Kumari QA]

It was ~400 bookmarks.

Comment 5

[Lina Butler [:lina]]

Kanchan, do you still have the bookmarks file that you imported? Could you attach it to this bug, please?

Comment 6

[Kanchan Kumari QA]

Sorry Kit! Bookmarks I used were my personal bookmarks from other browsers. I will try reproducing this issue again with new created bookmarks, whenever I get bandwidth.

Comment 7

[Lina Butler [:lina]]

From triage: Mark will take a look at this and see if he can reproduce.

Comment 8

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

I think we have a real bug here, but it's very complicated to work out what it is exactly :(

Let's get the (relatively) easy stuff out the way first :)

Of the 2 attachments:
* The "error log" is only an error because it has the line:

> FirefoxAccounts	ERROR	Background refresh of profile failed, bumping _cachedAt: {"name":"FxAccountsProfileClientError","code":304,"errno":997,"error":"PARSE_ERROR","message":null}
1

which is totally unrelated to this, but worrying :/ eoger, any thoughts on that? (build ID is 20170228, so it shouldn't be bug 1333431)

Otherwise, it doesn't hold any clues as to this problem...

* The .json attachment <is complicated - I'll add more on this tomorrow>

(In reply to Kanchan Kumari QA from comment #0)
> 2. Create large number of bookmarks (~3000) in nested bookmark hierarchy: a
> top-level folder containing some bookmarks, and child folders with
> grandchildren.

Do you still have the script you used for this? Somehow the "title" of the bookmarks menu has been changed to "str-0" too, which seems odd.

> 3. Sign in to sync on other devices (mobile or another OS)

Can you remember if you actually used Android here? It would be great if you can try and repro this using just desktop.

> 4. Import bookmarks/nested folder from another browser on Desktop (Step 1
> device)

Was that an "import" or a "restore"? Import is really dumb, and blindly creates duplicates (which is what I suspect happened). I believe Sync has then got quite upset de-duping. (Even though "import" is dumb, we should still handle it sanely)

(In reply to Kanchan Kumari QA from comment #6)
> Sorry Kit! Bookmarks I used were my personal bookmarks from other browsers.
> I will try reproducing this issue again with new created bookmarks, whenever
> I get bandwidth.

That seems a little odd, as I can't see any such bookmarks in the export - everything appears generated. Is it possible you did something like "run the script, export as HTML, sync, on another device import as HTML" or something? That would go some way to explaining things, but either way, it would be awesome of you can try and reproduce this again, taking particular note about whether Android is involved each time as it may make a difference.

Thanks!

Comment 9

[Edouard Oger [:eoger]]

This error log might be old Mark, because this error message was removed 2 months ago in bug 1332993 [0].

[0] https://hg.mozilla.org/mozilla-central/rev/d7c0d2ef9e10#l1.71

Comment 10

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

(In reply to Edouard Oger [:eoger] from comment #9)
> This error log might be old Mark, because this error message was removed 2
> months ago in bug 1332993 [0].

Right, this log is 53, which would have been Aurora when the bug was filed - and 53 looks like it missed those tweaks - but they aren't real bugs, so that all seems fine, thanks!

Comment 11

[Kanchan Kumari QA]

(In reply to Mark Hammond [:markh] from comment #8)

> Do you still have the script you used for this? Somehow the "title" of the
> bookmarks menu has been changed to "str-0" too, which seems odd.
> 

Script for creating large number of bookmarks: https://gist.github.com/kitcambridge/ae61d4e8ce54db74d18379c5d8393258


> > 3. Sign in to sync on other devices (mobile or another OS)
> 
> Can you remember if you actually used Android here? It would be great if you
> can try and repro this using just desktop.
> 

I remember, I used Android mobile here. I will try duplicating this issue using just desktop.


> > 4. Import bookmarks/nested folder from another browser on Desktop (Step 1
> > device)
> 
> Was that an "import" or a "restore"? Import is really dumb, and blindly
> creates duplicates (which is what I suspect happened). I believe Sync has
> then got quite upset de-duping. (Even though "import" is dumb, we should
> still handle it sanely)

It was an "import".


> Is it possible you did something like "run the
> script, export as HTML, sync, on another device import as HTML" or
> something? 

As I remember, for this bug I did run the script to create bookmarks and sync on other device but didn't export & import bookmarks as HTML. 

I will definitely try reproducing this issue and post my findings here. Thanks!

Comment 12

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

(In reply to Kanchan Kumari QA from comment #11)
> I will definitely try reproducing this issue and post my findings here.

Thanks Kanchan, but there's no need - I can reliably reproduce this now. It's almost exactly as you stated:

* On a clean desktop profile, run https://gist.github.com/kitcambridge/ae61d4e8ce54db74d18379c5d8393258, create FxA account, sync, exit.
* On a clean Fennec profile, sign into sync, wait for sync to complete, exit.
* Restart desktop, sync. Validation reports "Child record ZXxpeKbo716z appears as a child in multiple parents:" multiple times.

Looking at desktop logs:
> Outgoing: { id: ahxpIrd_xSz7  index: 1000000  modified: undefined  ttl: undefined  payload: {"id":"ahxpIrd_xSz7","type":"folder","parentid":"iWbf11H1-LYP","parentName":"Folder 1-2","title":"Folder 2-0","children":["G2sdR9MeIHzt","nWv1VgQ5-f3D","AcjNrETZcYtb","72n9xHWdSAze","ZXxpeKbo716z","2f0KNBoxo9_m"]}  collection: bookmarks }
> Outgoing: { id: ZXxpeKbo716z  index: 1000000  modified: undefined  ttl: undefined  payload: {"id":"ZXxpeKbo716z","type":"folder","parentid":"ahxpIrd_xSz7","parentName":"Folder 2-0","title":"Folder 3-1","children":["QKm9syatPrJ1","tWYs6dIlhoqT","H-5W4Wx5Wr3b"],"hasDupe":true}  collection: bookmarks }

That's the parent followed by the problem child record.

Next time desktop runs, logs are:
> Incoming: { id: Y1OK8Zxnc61I  index: 1000000  modified: 1491396156.11  ttl: undefined  payload: {"id":"Y1OK8Zxnc61I","children":["9EwCSDKXEI43","gHXCyhA7B7BB","ZXxpeKbo716z"],"parentid":"9_XXvCpIno8D","title":"Folder 2-0","type":"folder","parentName":"Folder 1-0"}  collection: bookmarks }
(and no other reference to ZXxpeKbo716z)

So suddenly Y1OK8Zxnc61I is the new parent, and the child record hasn't been updated.

It's still not clear why (eg, Y1OK8Zxnc61I does appear in the outgoing log), but for now I'm happy to have a reliable STR and assuming this is the same root problem tracked by bug 1353641.

Comment 13

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

Kit's script creates a bookmark tree like:

Bookmarks Menu
  +- Folder 1-0
  +    +- Folder 2-0
  +    +     +- Bookmark 2-1
  +    +- Folder 2-1
  +          +- Bookmark 2-1
  +- Folder 1-1
  +    +- Folder 2-0
  +    +     +- Bookmark 2-1
  +    +- Folder 2-1
            etc

Note how the bookmark and folder names are duplicated. For one example problem bookmark, when Desktop wrote it the path from the root is:

menu -> "Folder 1-0" -> "Folder 2-0" -> "Bookmark 2-2"

when re-reads it after an Android sync, the path from the root is:

menu -> "Folder 1-2" -> Folder 2-0" -> "Bookmark 2-2"

In all cases, the name of the parent folder is the same in both cases - it's just that the wrong parent of that name is being used, and the parent record *is not* updated (hence the validator complains)

I'm sure this is an edge-case given how the folders/bookmarks are named, but it might be one that highlights other real issues.

(Note also that you can reproduce this via https://gist.github.com/kitcambridge/ae61d4e8ce54db74d18379c5d8393258 and changing all the top-level constants to 3 - larger still reproduces but creates more bookmarks. Any less doesn't reproduce.

Comment 14

[Lina Butler [:lina]]

Attachment: guidMap.patch

Here's a test with a GUID map for that tree. (I also changed the map to use object literal instead of `String` objects, to make it easier to check `hasDupe`).

As Richard and I discussed on IRC, "Folder 2-0" is not duped, because it has different parent names ("Folder 1-0" vs. "Folder 1-1"), but its children are. Whether this is actually correct is another story... ;-)

Comment 15

[:Grisha Kruglov]

While processing incoming bookmark records, we're looking for local dupes by comparing records against a map of "record strings" built from the current state of the bookmarks table. For each local record, we compute a "record string", and create a recordString->guid mapping. We also attempt to keep this map "up-to-date" as we insert new records.

The culprit in this particular case is the recordString itself. For a bookmark record of 'type' bookmark, it is 'bParentTitle/https://bookmark.uri:BookmarkTitle'

And of course, this will produce results described in Comment 13, depending on the insertion order.

Comment 16

[:Grisha Kruglov]

The current "find a local dupe" logic also falls on its face if a local parent has been renamed. This wasn't possible in the past, but it is now.

The obvious 80% solution here is to change how we build record strings - replace parentTitle with parentGuid. Record GUIDs are fairly stable if something less-than-usual doesn't happen, so I expect this should be good enough for most syncing scenarios. It won't work if a parent GUID changes - say, we're merging data from two accounts, and GUIDs are all going to be different. At this point, we're also more likely to encounter a change in the parent GUID - our first attempt to find a local dupe is to just look it up by an incoming GUID, so that must have failed for us to be attempting a more elaborate "search by record string". Another explanation for a missing GUID is that we're performing "a first sync" - and so it's important we don't falsely dupe against an unrelated record.

Another approach, which largely follows the current logic, is to include a traversal of the tree in the recordString. E.g. parentTitle+parentParentTitle etc. This will include pretty significant changes to how we flow records, however - currently they're processed one by one. However, we now do have a full remote buffer in memory before we start flowing records, so we could bolt-on an additional processing step which will perform such traversal and pre-build the record strings for incoming records before we start processing them individually.

This, however, also falls flat on its face in light of user's ability to rename folders.

I think the smallest most useful step we can take is the "80%" solution - s/parentTitle/parentGUID in the record string - with a fallback onto the current faulty approach. This change should make cases such as Comment 13 actually work correctly when they're encountered during a first sync.

Comment 17

[Richard Newman [:rnewman]]

> The obvious 80% solution here is to change how we build record strings -
> replace parentTitle with parentGuid. Record GUIDs are fairly stable if
> something less-than-usual doesn't happen, so I expect this should be good
> enough for most syncing scenarios. It won't work if a parent GUID changes -
> say, we're merging data from two accounts, and GUIDs are all going to be
> different.

Searching by parent GUID will only work for two records created in the same folder (including in a root). As you note, it won't work for 'zipping' together two trees.

Going down this path leads to a stack of other hacks.

Take a look at Bug 747699, if you haven't already. I think it's a clearer statement of what you're trying to do here -- separating the idea of _finding the destination folder_ from _looking for a duplicate_.


> This, however, also falls flat on its face in light of user's ability to
> rename folders.

More importantly, using a complete path fails when you consider folder moves. If locally we build a path Mobile/Foo/Bar/Baz, and we see a record that moves Bar into Toolbar, our map is going to be wrong (particularly if the remote client then creates a new folder Mobile/Foo/Bar/ !).

Comment 18

[:Grisha Kruglov]

(In reply to Richard Newman [:rnewman] from comment #17)
> Searching by parent GUID will only work for two records created in the same folder (including in a root).

Created, or "currently in" the same folder. This feels like an improvement over the current situation.

> Take a look at Bug 747699, if you haven't already. I think it's a clearer
> statement of what you're trying to do here -- separating the idea of
> _finding the destination folder_ from _looking for a duplicate_.

Right, that's a nice distinction. The two problems are quite similar in that in both cases we have a unique and non-unique (user-modifiable) identifiers, possibility of false positives and false negatives, etc.

Comment 19

[:Grisha Kruglov]

Without drastically altering how we process incoming records, it's hard to see how we can do anything resembling "correct" when it comes to the various edge cases, but perhaps we can get to "good enough"; that's yet to be seen.

Performing a search for destination by a parent GUID introduces its own set of problems. If a remote record was moved, we expect to see the moved record and its parent folder (with an updated children list) in the set of incoming records. If we look for the new destination by a GUID - and find it locally - we will treat the moved record as a new record (unless the same move was performed locally, but I'll omit that case for now). We'll insert the record into its destination folder, and we're now left with a local duplicate which points to the previous folder. At the end of the bookmark sync, we'll iterate through local children of any processed folders, look for mismatches between server and local child lists, and consider any local children missing from the server list as "locally added". We'll then end up uploading our duplicate record in order to "correct" the server.

I think this is going to be the behaviour in the "match parent by GUID" case. Say, we start with the following structure shared on local device and server:

parentA
- childA
- childB
parentB
- {empty}

We then make a remote change, moving childB:

parentA
- childA
parentB
- childB

This will trigger an upload of parentA, parentB and childB records. After applying these records, and will end up with the following structure, which we'll end up uploading after the merge:

parentA
- childA
- childB
parentB
- childB

Following example in Comment 13, let's say the tree below is present on desktop.

Bookmarks Menu
  +- Folder 1-0
  +    +- Folder 2-0
  +    +     +- Bookmark 2-1
  +    +- Folder 2-1
  +          +- Bookmark 2-1
  +- Folder 1-1
  +    +- Folder 2-0
  +    +     +- Bookmark 2-1
  +    +- Folder 2-1

This structure should apply correctly on Android if we lookup items by parent GUIDs, without re-parenting issues. But, moves will be treated somewhat incorrectly.

Consider moving Folder 1-0/Folder 2-0/Bookmark 2-1 to Folder 1-0/Folder 2-1/Bookmark 2-1 on desktop, such that the new tree is:

Bookmarks Menu
  +- Folder 1-0
  +    +- Folder 2-0
  +    +- Folder 2-1
  +          +- Bookmark 2-1
  +    +     +- Bookmark 2-1
  +- Folder 1-1
  +    +- Folder 2-0
  +    +     +- Bookmark 2-1
  +    +- Folder 2-1

Desktop should upload Folder 1-0/Folder 2-0, Folder 1-0/Folder 2-1 and Folder 1-0/Folder 2-1/Bookmark 2-1. After this applies on Android, we'll end up with this tree:

Bookmarks Menu
  +- Folder 1-0
  +    +- Folder 2-0
  +    +     +- Bookmark 2-1 (we'll see that there's Bookmark 2-1 locally pointing to Folder 2-0, will consider it as added and re-upload) 
  +    +- Folder 2-1
  +          +- Bookmark 2-1 (we'll dupe an incoming record against an already present one)
  +- Folder 1-1
  +    +- Folder 2-0
  +    +     +- Bookmark 2-1
  +    +- Folder 2-1

... as if undoing the move.

We could improve upon this exact situation if the logic which looks for "locally added" records after incoming records have applied is altered. If we keep track of inserted records (e.g. Bookmark 2-1 moved or "reconciled" in the new folder), and while processing the so-called "locally added" records (e.g. Bookmark 2-1 which remained locally in the old folder), and we check if any locally added dupe against the list of inserted/reconciled, we can consider these as garbage records and throw them away.

I think that small change should make these few cases resolve correctly - trees should apply and moves should work more-or-less as expected. It's almost certain I'm missing some (important?) cases though.

Comment 20

[:Grisha Kruglov]

rnewman helpfully pointed out that parts of the above example won't actually apply here. If the trees are in general agreement (local vs remote), we're able to do all of this work just via GUIDs, not via content reconciliation.

Comment 21

[:Grisha Kruglov]

Coming back to this, here's what I think is a reasonable plan of attack that doesn't involve too many changes and re-uses some of the primitives currently in place, as well as the "one-by-one" flow of records."

The goal is to end up with two distinct actions:
- looking for a destination folder
- looking for a duplicate within the determined destination folder

As records are processed, we figure out a coherent structure - looking for a correct parent for each incoming record, either from a set of incoming records or those already in the db. De-duplication is performed once all records have been processed and the structure is in place, at the time of insertion.

For simplicity, record insertion is deferred until we have processed all of the incoming records.

As bookmark records are processed, one by one, place them into one of three buckets:
- known local parent (KLP)
--> parent is already present in the local db
- unknown local parent, known remote (ULPKR)
--> parent not present in local db, but we saw it in the set of incoming records
- unknown local parent, unknown remote (ULPUR)
--> parent not present in local db, and we didn't see it (yet, hopefully) in incoming records

Once all of the incoming records have been processed, ideally we'll end-up with two non-empty buckets: KLP and ULPKR. If we still have any records in ULPUR, we set their parent to "unfilled", thus moving them over to KLP.

We then process records in KLP. Folders are inserted w/o question (allowing duplicates), and for other records we perform content-based reconciliation (as we do now, but within their correct parent).

As we insert records in KLP, we can start emptying ULPKR by moving records into KLP.

Do this until all records in KLP have been processed, and ULPKR is not changing. There should be nothing left in ULPKR if all went well.

We should be able to perform all of these operations in a single transaction. SQLite's isolation rules help: uncommitted changes on the same connection are always visible to subsequent SELECTs.

We should be able to minimize amount of individual SQL operations by being smart about how we group our inserts and updates - however, that isn't strictly necessary, as our current behaviour is already very non-optimal, and isn't a bottleneck.

Life would be simpler if 'bookmarks.parent' column was a GUID instead of a local ID: we wouldn't need to maintain guid->androidID maps, and would be able to process KLP and ULPKR in one go. Consider either migrating the bookmarks table (costly and potentially prohibitive, as it would involve a lot of copying), or introduce a new "bookmark_structure" table, similar to what iOS has. Again, not a necessary requirement for this work to succeed.

This approach should work for trees which are in general agreement, and should generally handle moves and renames in a predictable fashion. E.g. cases such as Comment 13 and Bug 1430487 will be handled well.

For trees which are not of the same origin - e.g. merging two devices that evolved on entirely separate timelines - this approach will result in folder duplication. Trees won't be "zipped", but neither will we corrupt them as we do now. It'll be up to the user to resolve any resulting duplication. We can iteratively improve upon this behaviour, by introducing content-based reconciliation step to folder insertion. Given how relatively rare this should be, I think this is acceptable. It lets us have our simple 90% solution which works for majority of cases, and not loose data for the remaining 10%.

Comment 22

[:Grisha Kruglov]

What do you folks think of Comment 21? Did I miss some reason for why this approach wouldn't work, and isn't a reasonable evolution of what Android currently does?

Comment 23

[:Grisha Kruglov]

Re-phrased, the difference from the current approach is to focus on maintaining correct tree structure at the code of possible duplication in certain cases. Implementation details are inconsequential, and will fall out similarly given the constraints (need to ensure parents are inserted fist, etc) - largely, Comment 21 describes what BookmarksInsertionManager does currently.

Comment 24

[:Grisha Kruglov]

code=cost*

Comment 25

[Richard Newman [:rnewman]]

(In reply to :Grisha Kruglov from comment #21)

> For simplicity, record insertion is deferred until we have processed all of
> the incoming records.

That is: you split handling of incoming bookmarks into four phases:

1. Buffering
2. Finding parents
3. Finding duplicates
4. Application.

iterating through 2-3 as needed. (Or do you iterate through 2-4?)


> As bookmark records are processed, one by one, place them into one of three
> buckets:
> - known local parent (KLP)
> --> parent is already present in the local db

… by GUID, you mean?


> We then process records in KLP. Folders are inserted w/o question (allowing
> duplicates)

I believe that for correct merging to occur you need to find duplicate folders. At this point you also need to respect hasDupe.


> Do this until all records in KLP have been processed, and ULPKR is not
> changing. There should be nothing left in ULPKR if all went well.

Your simplification here is that you've eliminated recursive 'stitching' by not processing folders.

I suspect there's some additional thought needed for moves/deletions of folders, but that's achievable.

Remember also that you need to track anything that needs to be (re)uploaded.

> For trees which are not of the same origin - e.g. merging two devices that
> evolved on entirely separate timelines - this approach will result in folder
> duplication. Trees won't be "zipped", but neither will we corrupt them as we
> do now. It'll be up to the user to resolve any resulting duplication.

I'm not sure this is an acceptable user experience, though it's a reasonable first milestone during development.

Consider the set of default folders ("Mozilla Firefox", for example) on the Bookmarks Toolbar, or users who have imported bookmarks from Chrome and thus have the same tree on different machines with different GUIDs.

I think your outlined approach will easily zip trees: you know that every tree has its roots in known GUIDs ("mobile______" etc.), so you will never have empty KLP with a non-empty UL, and you know the parent of each incoming record, so you have the context required to do content-based reconciling of folders. If an incoming folder is in KLP, but is new, then _content reconcile it_. Job done, no?

Your KLP/ULPKR split is essentially a recasting of a top-down tree walk as a generational/iterative model.

Comment 27

[:Grisha Kruglov]

Renaming this bug to better reflect the ongoing work.

Comment 28

[Firefox Bug Husbandry Bot]

Re-triaging per https://bugzilla.mozilla.org/show_bug.cgi?id=1473195

Needinfo :susheel if you think this bug should be re-triaged.

Comment 29

[Andrei Bodea[:andrei]]

This is still reproducible on the latest Nightly build.
Device: Samsung Galaxy Note 9(Android 8.1.0).

Comment 30

[BMO Automation]

We have completed our launch of our new Firefox on Android. The development of the new versions use GitHub for issue tracking. If the bug report still reproduces in a current version of [Firefox on Android nightly](https://play.google.com/store/apps/details?id=org.mozilla.fenix) an issue can be reported at the [Fenix GitHub project](https://github.com/mozilla-mobile/fenix/). If you want to discuss your report please use [Mozilla's chat](https://wiki.mozilla.org/Matrix#Connect_to_Matrix) server https://chat.mozilla.org and join the [#fenix](https://chat.mozilla.org/#/room/#fenix:mozilla.org) channel.