Right now it's possible for bookmarks to end up with a parent ID that doesn't point to a folder in the database. If my hypothesis is correct, that allowed Bug 718194 to occur. There should be a self-referential foreign key constraint on the parent column.

Related: in LocalBrowserDB.java: private long mMobileFolderId; … private long getMobileBookmarksFolderId(ContentResolver cr) { if (mMobileFolderId >= 0) return mMobileFolderId; This value can be stale. If Fennec is running, and Sync deletes the mobile bookmarks folder (perhaps because you did on the desktop), then Fennec will happily continue to add new bookmarks into a folder that doesn't exist. This would be caught by a DB-level constraint.

And a problem we're going to have to address: The browser DB's ID column is an autoincrementing integer. Fennec assumes that the "mobile" folder has parent 0. That's fine; treat it as a sentinel. Sync can't assume that any folders exist, so we have to do this: if (guid.equals("mobile")) { Log.i(LOG_TAG, "No mobile folder. Inserting one."); mobileRoot = insertSpecialFolder("mobile", 0); } else if (guid.equals("places")) { // This is awkward. desktopRoot = insertSpecialFolder("places", mobileRoot); } The "places" folder lives under the "mobile" folder. That's OK, because there should be no bookmarks inside the "places" folder (only special folders), but we'll need to make sure that this gets hidden from view, or even resolved entirely by ensuring that "places" is ID 0, created at database creation time. (I wish I'd made this assertion two months ago. Oh well.)

Richard, is this what you were thinking?

Comment on attachment 594841 [details] [diff] [review] patch Review of attachment 594841 [details] [diff] [review]: ----------------------------------------------------------------- Yes, but per IRC discussion it'll be unsafe to do this now. It needs to be introduced during a migration, and the Fennec and Sync code need to be safe wrt the constraint first.

(In reply to Richard Newman [:rnewman] from comment #1) > Related: in LocalBrowserDB.java: > > private long mMobileFolderId; > > … > > private long getMobileBookmarksFolderId(ContentResolver cr) { > if (mMobileFolderId >= 0) > return mMobileFolderId; > > > This value can be stale. If Fennec is running, and Sync deletes the mobile > bookmarks folder (perhaps because you did on the desktop), then Fennec will > happily continue to add new bookmarks into a folder that doesn't exist. This > would be caught by a DB-level constraint. On IRC, we talked about solving this problem by ensuring we never delete the mobile root. Are you changing the way sync merges mobile folders so that it just puts bookmarks in our mobile folder? And how would we deal with this case of a user deleting the mobile bookmarks folder on desktop? Just empty the folder in fennec? (In reply to Richard Newman [:rnewman] from comment #2) > The "places" folder lives under the "mobile" folder. That's OK, because > there should be no bookmarks inside the "places" folder (only special > folders), but we'll need to make sure that this gets hidden from view, or > even resolved entirely by ensuring that "places" is ID 0, created at > database creation time. The current way I implemented the bookmarks UI in bug 716918, we don't need to worry about hiding the "places" folder from view, since I'm just querying non-folder children of the mobile folder to populate the "Mobile Bookmarks" section, then sticking all other bookmarks in a "Desktop Bookmarks" section. I agree we'll have to be careful around this when we implement a more powerful bookmarks UI, but I don't think it's something we need to worry about for shipping beta (and if we're addressing this in the future, we can do a database migration to ensure that "places" is ID 0).

(In reply to Margaret Leibovic [:margaret] from comment #5) > On IRC, we talked about solving this problem by ensuring we never delete the > mobile root. Are you changing the way sync merges mobile folders so that it > just puts bookmarks in our mobile folder? I already fixed the merging mechanism in terms of preserving the Android DB ID, but the whole storing for merging is quite complicated because of children. (Isn't that always the way?) > And how would we deal with this > case of a user deleting the mobile bookmarks folder on desktop? Just empty > the folder in fennec? I plan to refuse to delete roots, yes. Individual item deletion will occur on a per-record basis. > The current way I implemented the bookmarks UI in bug 716918, we don't need > to worry about hiding the "places" folder from view, since I'm just querying > non-folder children of the mobile folder to populate the "Mobile Bookmarks" > section, then sticking all other bookmarks in a "Desktop Bookmarks" section. Ah, so you'll ignore (or dump into Desktop Bookmarks) any folders that XUL Fennec users created in their bookmarks? Fine by me for beta. > I agree we'll have to be careful around this when we implement a more > powerful bookmarks UI, but I don't think it's something we need to worry > about for shipping beta (and if we're addressing this in the future, we can > do a database migration to ensure that "places" is ID 0). Agreed.

I haven't tested this, but this is my first attempt at a patch to update the children of deleted folders. This patch is dumb because it does multiple update queries instead of one, so that needs fixing, but hopefully it's on the right track.

I'm passing this back to Lucas, since he knows more about this code. I just picked it up in the hopes of finishing it before he could get to it, but alas, I had lots of trouble!

About the foreign key constraint, I just saw that Eclair ships with a SQLite version that doesn't support foreign keys (3.5.9). I guess I'll have especial case that for Android >= 2.2.

(In reply to Lucas Rocha (:lucasr) from comment #10) > About the foreign key constraint, I just saw that Eclair ships with a SQLite > version that doesn't support foreign keys (3.5.9). I guess I'll have > especial case that for Android >= 2.2. Aren't we using our own sqlite library now? (See Bug 704682.) If not, perhaps we should -- speeeeeeeeed!

Comment on attachment 595414 [details] [diff] [review] Handle orphan bookmarks in case a folder is incorrectly removed Review of attachment 595414 [details] [diff] [review]: ----------------------------------------------------------------- In the right direction, but needs some tweaks. ::: mobile/android/base/db/BrowserProvider.java.in @@ +1040,5 @@ > + folderCursor = db.query(TABLE_BOOKMARKS, > + new String[] { Bookmarks._ID }, > + Bookmarks.GUID + " = ?", > + new String[] { Bookmarks.UNFILED_FOLDER_GUID }, > + null, null, null); Perhaps it's time for static final String[] ID_COLUMNS = new String[] { Bookmarks._ID }; private long guidToID(String guid) { Cursor c = db.query(TABLE_BOOKMARKS, ID_COLUMNS, Bookmarks.GUID + " = ?", new String[] { guid }, null, null, null): try { if (c == null || !c.moveToFirst()) return -1; return c.getLong(c.getColumnIndex(Bookmarks._ID)); } finally { if (c != null) { c.close(); } } } or the Long-returning version so we can return null…? @@ +1092,5 @@ > + childrenSelection.append(" OR "); > + > + childrenSelection.append(Bookmarks.PARENT); > + childrenSelection.append(" = "); > + childrenSelection.append(oldParentId); I'd also add the constraint here AND IS_DELETED = 0; That is, we don't mind deleted bookmarks living in a deleted folder. We only want to move orphan bookmarks that otherwise are alive, because their parent's deletion renders them unreachable from the UI. When we move these living children, we also need to bump their modified time, reset their position to most-negative-long, and bump the new parent folder's modified time. The old -- dead -- parent's modified time will be bumped by deletion anyway. Note that this doesn't apply to isCallerSync() -- in that case we're actually *really really* going to delete the folder, so *all* of its children need to be moved. But only the living children should cause timestamps (theirs and parents) to be bumped. Note that expiration of dead bookmark folders will need to trigger this method, too, which implies that the "is Sync" part should be through a boolean parameter, not URI introspection. Sorry for the pile of complexity.

Sorry not to have got to the reviews on this yet, Lucas; I'm flying tomorrow, so today's been a bit hectic. They're first in my queue.

Comment on attachment 596086 [details] [diff] [review] (4/4) Add a foreign key to bookmarks table and sanitize special folders Review of attachment 596086 [details] [diff] [review]: ----------------------------------------------------------------- ::: mobile/android/base/db/BrowserProvider.java.in @@ +406,2 @@ > // Set the parent to 0, which sync assumes is the root > values.put(Bookmarks.PARENT, Bookmarks.FIXED_ROOT_ID); I'm delighted to know that this works for the root! @@ +420,5 @@ > if (updated == 0) > db.insert(TABLE_BOOKMARKS, Bookmarks.GUID, values); > } > > + private void insertBookmarkFolder(SQLiteDatabase db, int folderId) { I think this should be "migrateBookmarkFolder", no? "insert" has quite mild connotations :) @@ +450,5 @@ > + // We're using a null projection in the query which > + // means we're getting all columns from the table. > + // It's safe to simply transform the row into the > + // values to be inserted on the new table. > + DatabaseUtils.cursorRowToContentValues(c, values); Doesn't this insert bookmarks with the wrong parent? Temp table: mobile = 1, 0 foo = 2, 1 bar = 3, 2 New table: places = 0, 0 mobile = 1, 0 menu = 2, 0 unfiled = 3, 0 ... Your cursor hits 'bar', which has parent 2. You turn that into a ContentValues, then call insert on line 459. Now you have 'bar' in the 'menu' folder, not in 'foo'. Am I misreading? My guess is that you should be adding an else… @@ +453,5 @@ > + // values to be inserted on the new table. > + DatabaseUtils.cursorRowToContentValues(c, values); > + > + if (values.getAsLong(Bookmarks.PARENT) == null) > + values.put(Bookmarks.PARENT, Bookmarks.FIXED_ROOT_ID); … here, setting PARENT to folderId. But see next comment, too. @@ +455,5 @@ > + > + if (values.getAsLong(Bookmarks.PARENT) == null) > + values.put(Bookmarks.PARENT, Bookmarks.FIXED_ROOT_ID); > + > + db.insert(TABLE_BOOKMARKS, Bookmarks.URL, values); I think this needs a slight tweak: if the bookmark isn't a special folder, its parent shouldn't be the root. It should probably be "mobile". The root should only contain special folders. @@ +459,5 @@ > + db.insert(TABLE_BOOKMARKS, Bookmarks.URL, values); > + > + Integer isFolder = values.getAsInteger(Bookmarks.IS_FOLDER); > + if (isFolder != null && isFolder == 1) > + insertBookmarkFolder(db, values.getAsInteger(Bookmarks._ID)); Is there a limit to the number of concurrent cursors we can have? You're recursing here, which means you could end up with as many cursors as the user has bookmark hierarchy levels… Perhaps use a little queue, filling it here with IDs to recurse into, and walking it once you've closed the cursor? That way you only have the outermost cursor on TMP, inserts into the destination table for bookmarks, and more work to do later. @@ +504,5 @@ > + // database schema version. > + for (int v = oldVersion + 1; v <= newVersion; v++) { > + switch(v) { > + case 2: > + upgradeDatabaseFrom1to2(db); Add some logging here?

Oh, and one more point, which I don't think you've addressed in part 4: special folders in the temporary table could be anywhere, and you'll only know them by GUID. Oh, and they'll be children of the mobile bookmarks folder. It seems like as you're walking you need to spot special GUIDs, avoid creating those folders, and put their children under the correct pre-created folder…

Comment on attachment 596086 [details] [diff] [review] (4/4) Add a foreign key to bookmarks table and sanitize special folders >diff --git a/mobile/android/base/db/BrowserProvider.java.in b/mobile/android/base/db/BrowserProvider.java.in >+ createOrUpdateSpecialFolder(db, Bookmarks.TAGS_FOLDER_GUID, >+ R.string.bookmarks_folder_tags, 3); What goes in this TAGS_FOLDER_GUID folder? Is it bookmarks that are tagged? Can't those also appear in other folders? Also, I thought we didn't sync tags, so I'm concerned about what the UI for this would look like. I guess we could always make a special case to not show this folder in the UI.

(In reply to Margaret Leibovic [:margaret] from comment #20) > Comment on attachment 596086 [details] [diff] [review] > (4/4) Add a foreign key to bookmarks table and sanitize special folders > > >diff --git a/mobile/android/base/db/BrowserProvider.java.in b/mobile/android/base/db/BrowserProvider.java.in > > >+ createOrUpdateSpecialFolder(db, Bookmarks.TAGS_FOLDER_GUID, > >+ R.string.bookmarks_folder_tags, 3); > > What goes in this TAGS_FOLDER_GUID folder? Is it bookmarks that are tagged? > Can't those also appear in other folders? Also, I thought we didn't sync > tags, so I'm concerned about what the UI for this would look like. I guess > we could always make a special case to not show this folder in the UI. Sync needs that to avoid losing data I think. But we won't use it in Fennec so it's ok to simply filter this folder out in our UI.

(In reply to Richard Newman [:rnewman] from comment #18) > Comment on attachment 596086 [details] [diff] [review] > (4/4) Add a foreign key to bookmarks table and sanitize special folders > > Review of attachment 596086 [details] [diff] [review]: > ----------------------------------------------------------------- > > ::: mobile/android/base/db/BrowserProvider.java.in > @@ +406,2 @@ > > // Set the parent to 0, which sync assumes is the root > > values.put(Bookmarks.PARENT, Bookmarks.FIXED_ROOT_ID); > > I'm delighted to know that this works for the root! > > @@ +420,5 @@ > > if (updated == 0) > > db.insert(TABLE_BOOKMARKS, Bookmarks.GUID, values); > > } > > > > + private void insertBookmarkFolder(SQLiteDatabase db, int folderId) { > > I think this should be "migrateBookmarkFolder", no? "insert" has quite mild > connotations :) Agree. Done. > @@ +450,5 @@ > > + // We're using a null projection in the query which > > + // means we're getting all columns from the table. > > + // It's safe to simply transform the row into the > > + // values to be inserted on the new table. > > + DatabaseUtils.cursorRowToContentValues(c, values); > > Doesn't this insert bookmarks with the wrong parent? > > Temp table: > > mobile = 1, 0 > foo = 2, 1 > bar = 3, 2 > > New table: > > places = 0, 0 > mobile = 1, 0 > menu = 2, 0 > unfiled = 3, 0 > ... > > Your cursor hits 'bar', which has parent 2. You turn that into a > ContentValues, then call insert on line 459. Now you have 'bar' in the > 'menu' folder, not in 'foo'. > > Am I misreading? > > My guess is that you should be adding an else… Note that the special folders are only created/updated *after* all folders/bookmarks are migrated from tmp table to the new bookmarks table. Also note that we update existing special folders based on GUID, not id. This means that the parent ids from the tmp table will still point to the expected folders. In your example, foo and bar would still have ids 2 and 3 (respectively) in the new bookmarks table. We don't force specific ids on special folders (except for the root folder which has a fixed id = 0). > @@ +453,5 @@ > > + // values to be inserted on the new table. > > + DatabaseUtils.cursorRowToContentValues(c, values); > > + > > + if (values.getAsLong(Bookmarks.PARENT) == null) > > + values.put(Bookmarks.PARENT, Bookmarks.FIXED_ROOT_ID); > > … here, setting PARENT to folderId. But see next comment, too. Wouldn't this be redundant? The query here already does "WHERE PARENT = folderId" so the PARENT is either NULL or same as folderId. > @@ +455,5 @@ > > + > > + if (values.getAsLong(Bookmarks.PARENT) == null) > > + values.put(Bookmarks.PARENT, Bookmarks.FIXED_ROOT_ID); > > + > > + db.insert(TABLE_BOOKMARKS, Bookmarks.URL, values); > > I think this needs a slight tweak: if the bookmark isn't a special folder, > its parent shouldn't be the root. It should probably be "mobile". The root > should only contain special folders. I can do that but I wonder in which cases we'd have something like this in the database? Or are you just being paranoid here? :-P > @@ +459,5 @@ > > + db.insert(TABLE_BOOKMARKS, Bookmarks.URL, values); > > + > > + Integer isFolder = values.getAsInteger(Bookmarks.IS_FOLDER); > > + if (isFolder != null && isFolder == 1) > > + insertBookmarkFolder(db, values.getAsInteger(Bookmarks._ID)); > > Is there a limit to the number of concurrent cursors we can have? You're > recursing here, which means you could end up with as many cursors as the > user has bookmark hierarchy levels… > > Perhaps use a little queue, filling it here with IDs to recurse into, and > walking it once you've closed the cursor? That way you only have the > outermost cursor on TMP, inserts into the destination table for bookmarks, > and more work to do later. Good point. Let me try that. > @@ +504,5 @@ > > + // database schema version. > > + for (int v = oldVersion + 1; v <= newVersion; v++) { > > + switch(v) { > > + case 2: > > + upgradeDatabaseFrom1to2(db); > > Add some logging here? I will.

(In reply to Lucas Rocha (:lucasr) from comment #22) > Note that the special folders are only created/updated *after* all > folders/bookmarks are migrated from tmp table to the new bookmarks table. Apart from places, which is created first, but I see your point. I think there's still an issue, though: out-of-order insertion. If you're not mapping all folder IDs (only special folders), then you're relying on every folder being inserted at the same index. That means you need to process in ID order, which of course isn't parent-safe. Example: GUID ID ================== mobile/ 1 foo/ 2 baz/ 3 noo 5 bar 4 You process mobile's children, creating auto-indexed IDs: foo = 2 bar = 3 and adding foo to subfolders. Then you migrate foo: baz = 4 Add baz to subfolders. Process baz's children: migrate noo, which has existing parent 3. That's no longer the ID of baz. Insertion will fail or be incorrect. You need to preserve those ID mappings during insertion. The alternative in this situation is to recurse, but I could come up with another sequence of bookmarks that will break that, too. Am I crazy (do I need another cup of coffee?)? > > I think this needs a slight tweak: if the bookmark isn't a special folder, > > its parent shouldn't be the root. It should probably be "mobile". The root > > should only contain special folders. > > I can do that but I wonder in which cases we'd have something like this in > the database? Or are you just being paranoid here? :-P There's an element of paranoia to be sure, but if you're including that null-handling clause, I think it should do something sane :D No code -- either Places or Margaret's UI code -- expects anything but special folders under the Places root.

Comment on attachment 597432 [details] [diff] [review] Add a foreign key to bookmarks table and sanitize special folders Review of attachment 597432 [details] [diff] [review]: ----------------------------------------------------------------- One more pass at this… ::: mobile/android/base/db/BrowserProvider.java.in @@ +265,5 @@ > Bookmarks.DATE_MODIFIED + " INTEGER," + > Bookmarks.GUID + " TEXT," + > + Bookmarks.IS_DELETED + " INTEGER NOT NULL DEFAULT 0, " + > + "FOREIGN KEY (" + Bookmarks.PARENT + ") REFERENCES " + > + TABLE_BOOKMARKS + "(" + Bookmarks._ID + ")" + Does this need to be conditionalized on Android version? (Or are we always using our version of SQLite?) @@ +352,5 @@ > + R.string.bookmarks_folder_places, 0); > + > + createOrUpdateAllSpecialFolders(db); > + > + // FIXME: Create default bookmarks here File a bug, note the bug number. @@ +401,5 @@ > + } > + } > + > + private boolean isSpecialFolder(ContentValues values) { > + String guid = values.getAsString(Bookmarks.GUID); Add a null check here, short-circuit return. @@ +478,5 @@ > + > + if (isRootFolder && !isSpecialFolder(values)) { > + invalidSpecialEntries.add(values); > + continue; > + } Why not simply skip the PARENT = NULL part of the selection query, and do all of those *last*? You're guaranteed not to encounter any by starting from the root, right? So: migrate(root) SELECT id WHERE PARENT = null; foreach: migrate(id) into unfiled or mobile @@ +556,5 @@ > + for (int v = oldVersion + 1; v <= newVersion; v++) { > + switch(v) { > + case 2: > + upgradeDatabaseFrom1to2(db); > + break; Indenting.

(In reply to Richard Newman [:rnewman] from comment #25) > Comment on attachment 597432 [details] [diff] [review] > Add a foreign key to bookmarks table and sanitize special folders > > Review of attachment 597432 [details] [diff] [review]: > ----------------------------------------------------------------- > > One more pass at this… > > ::: mobile/android/base/db/BrowserProvider.java.in > @@ +265,5 @@ > > Bookmarks.DATE_MODIFIED + " INTEGER," + > > Bookmarks.GUID + " TEXT," + > > + Bookmarks.IS_DELETED + " INTEGER NOT NULL DEFAULT 0, " + > > + "FOREIGN KEY (" + Bookmarks.PARENT + ") REFERENCES " + > > + TABLE_BOOKMARKS + "(" + Bookmarks._ID + ")" + > > Does this need to be conditionalized on Android version? (Or are we always > using our version of SQLite?) Yes, needs to be skipped on Android < 2.2. Done. > @@ +352,5 @@ > > + R.string.bookmarks_folder_places, 0); > > + > > + createOrUpdateAllSpecialFolders(db); > > + > > + // FIXME: Create default bookmarks here > > File a bug, note the bug number. Filed bug 728224 and added a reference in this comment. > @@ +401,5 @@ > > + } > > + } > > + > > + private boolean isSpecialFolder(ContentValues values) { > > + String guid = values.getAsString(Bookmarks.GUID); > > Add a null check here, short-circuit return. Done. > @@ +478,5 @@ > > + > > + if (isRootFolder && !isSpecialFolder(values)) { > > + invalidSpecialEntries.add(values); > > + continue; > > + } > > Why not simply skip the PARENT = NULL part of the selection query, and do > all of those *last*? You're guaranteed not to encounter any by starting from > the root, right? PARENT = NULL is used here specifically to set the parent of the mobile folder for all our users. We used to create the mobile folder with PARENT = NULL and we have to fix that in this migration otherwise mobile bookmarks will not be migrated here. I added a safer check before setting PARENT = FIXED_ROOT_ID. > @@ +556,5 @@ > > + for (int v = oldVersion + 1; v <= newVersion; v++) { > > + switch(v) { > > + case 2: > > + upgradeDatabaseFrom1to2(db); > > + break; > > Indenting. Fixed.

(In reply to Lucas Rocha (:lucasr) from comment #26) > > Why not simply skip the PARENT = NULL part of the selection query, and do > > all of those *last*? You're guaranteed not to encounter any by starting from > > the root, right? > > PARENT = NULL is used here specifically to set the parent of the mobile > folder for all our users. We used to create the mobile folder with PARENT = > NULL and we have to fix that in this migration otherwise mobile bookmarks > will not be migrated here. I added a safer check before setting PARENT = > FIXED_ROOT_ID. My point was not that you didn't need the clause at all. I was trying to suggest that rather than selecting children of the root, and un-parented nodes, you split those into two phases; by doing so you avoid the need for invalidSpecialEntries entirely, because you'll never encounter one of those invalid entries by walking all valid children. Then finish up by querying for unparented nodes, and walk those exactly the same way, but pretend that they were found as children of mobile. Make sense?

(In reply to Richard Newman [:rnewman] from comment #28) > (In reply to Lucas Rocha (:lucasr) from comment #26) > > > > Why not simply skip the PARENT = NULL part of the selection query, and do > > > all of those *last*? You're guaranteed not to encounter any by starting from > > > the root, right? > > > > PARENT = NULL is used here specifically to set the parent of the mobile > > folder for all our users. We used to create the mobile folder with PARENT = > > NULL and we have to fix that in this migration otherwise mobile bookmarks > > will not be migrated here. I added a safer check before setting PARENT = > > FIXED_ROOT_ID. > > My point was not that you didn't need the clause at all. I was trying to > suggest that rather than selecting children of the root, and un-parented > nodes, you split those into two phases; by doing so you avoid the need for > invalidSpecialEntries entirely, because you'll never encounter one of those > invalid entries by walking all valid children. > > Then finish up by querying for unparented nodes, and walk those exactly the > same way, but pretend that they were found as children of mobile. > > Make sense? But the existing entries with PARENT = null will probably include the mobile folder itself. This is not about any mobile folder's children.

(In reply to Richard Newman [:rnewman] from comment #28) > My point was not that you didn't need the clause at all. I was trying to > suggest that rather than selecting children of the root, and un-parented > nodes, you split those into two phases; by doing so you avoid the need for > invalidSpecialEntries entirely, because you'll never encounter one of those > invalid entries by walking all valid children. One more thing: the invalidSpecialEntries are not about PARENT = NULL. They are about ensuring that only special folders (mobile, unfiled, menu, toolbar, etc) are under the root folder.

Pushed: http://hg.mozilla.org/integration/mozilla-inbound/rev/2094fc0fc224 http://hg.mozilla.org/integration/mozilla-inbound/rev/06b31e6330c6 http://hg.mozilla.org/integration/mozilla-inbound/rev/0ffb3b233fce http://hg.mozilla.org/integration/mozilla-inbound/rev/14f791dbb579 I haven't pushed the patch to handle orphaned bookmark children. I'll work on it on a follow-up bug (see bug 728928) to avoid block this bug from being closed.

Awesome, thanks Lucas!

https://hg.mozilla.org/mozilla-central/rev/2094fc0fc224 https://hg.mozilla.org/mozilla-central/rev/06b31e6330c6 https://hg.mozilla.org/mozilla-central/rev/0ffb3b233fce https://hg.mozilla.org/mozilla-central/rev/14f791dbb579