new file mode 100644
--- /dev/null
+++ b/services/sync/modules/bookmark_buffer.js
@@ -0,0 +1,3244 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+"use strict";
+
+/**
+ * This file implements a bookmark buffer that stores incoming synced bookmarks
+ * in SQLite, a merger that produces a complete tree from a local tree and a
+ * remote tree, and a reconciler that writes the merged tree back to Places.
+ *
+ * Let's start with an overview of the different classes, and how they fit
+ * together.
+ *
+ * - `BookmarkBuffer` sets up the database, stages downloaded records, attaches
+ * to Places, and applies the staged records. During application, we fetch the
+ * local and remote `BookmarkTree`s, merge the two trees into a single
+ * `MergedBookmarkTree`, and update Places to match. Merging and application
+ * happen in a single transaction, so applying the merged tree won't collide
+ * with local changes.
+ *
+ * - A `BookmarkTree` is a well-formed tree with many `BookmarkNode`s. Nodes can
+ * represent real items in the buffer or Places, or virtual items that we
+ * insert to make tree walking easier.
+ *
+ * - A `MergedBookmarkTree` has many `MergedBookmarkNode`s. Merged nodes are
+ * constructed from a local node, a remote node, and a `MergeState` that
+ * indicates which node to prefer when updating Places.
+ *
+ * - `{insert, update}PlacesItem` examines the merge state of each item, and
+ * either keeps the complete `local` state, takes the complete `remote` state
+ * without conflicts, or applies a `new` state and flags the item for
+ * reupload. Note that we update Places and flag items *before* uploading,
+ * while iOS updates the mirror *after* a successful upload. This simplifies
+ * our implementation, though we lose the ability to replay merges: if the
+ * upload is interrupted, the next sync won't be able to distinguish between
+ * `new` states from the previous sync, and local changes. Since this is how
+ * Desktop behaved before we had structured application, that's OK. In the
+ * future, we can make this more like iOS.
+ *
+ * - `BookmarkObserverNotifications` records all changes made to Places during
+ * the merge, then dispatches `nsINavBookmarkObserver` notifications once
+ * the transaction commits and the database is consistent again. Places uses
+ * these notifications to update the UI and internal caches. Some observers,
+ * like `nsNavBookmarks::OnItemAnnotationSet`, start new transactions and
+ * query Places, so we can't notify them as we're applying changes.
+ *
+ * - After application, we discard the buffer, create records for the changed
+ * items in Places, and upload the records to the server. We don't buffer
+ * outgoing records yet (bug 1359200), so it's still possible to change
+ * bookmarks during the sync and upload inconsistent data.
+ */
+
+this.EXPORTED_SYMBOLS = [
+ "BookmarkConsistencyError",
+ "BookmarkBuffer",
+ "BookmarkMergeState",
+ "BookmarkLocation",
+ "BookmarkNode",
+ "BookmarkTree",
+ "MergedBookmarkTree",
+ "MergedBookmarkNode",
+ "BookmarkMerger",
+ "BookmarkContent",
+ "BookmarkStorage",
+ "BookmarkObserverNotifications",
+];
+
+const { utils: Cu, interfaces: Ci } = Components;
+
+Cu.importGlobalProperties(["URL"]);
+
+Cu.import("resource://gre/modules/Services.jsm");
+Cu.import("resource://gre/modules/XPCOMUtils.jsm");
+
+XPCOMUtils.defineLazyModuleGetters(this, {
+ AsyncResource: "resource://services-sync/resource.js",
+ AsyncShutdown: "resource://gre/modules/AsyncShutdown.jsm",
+ Log: "resource://gre/modules/Log.jsm",
+ PlacesSyncUtils: "resource://gre/modules/PlacesSyncUtils.jsm",
+ PlacesUtils: "resource://gre/modules/PlacesUtils.jsm",
+ Sqlite: "resource://gre/modules/Sqlite.jsm",
+});
+
+XPCOMUtils.defineLazyGetter(this, "BookmarkBufferLog", () =>
+ Log.repository.getLogger("Sync.Engine.Bookmarks.Buffer")
+);
+
+const KIND_VIRTUAL_FOLDER = -1;
+const KIND_VIRTUAL_ITEM = -2;
+
+const KIND_BOOKMARK = 1;
+const KIND_QUERY = 2;
+const KIND_FOLDER = 3;
+const KIND_LIVEMARK = 4;
+const KIND_SEPARATOR = 5;
+
+// Keep in sync with PlacesUtils.
+const DB_URL_LENGTH_MAX = 65536;
+const DB_TITLE_LENGTH_MAX = 4096;
+
+class BookmarkConsistencyError extends Error {}
+
+/**
+ * A buffer temporarily stores incoming Sync bookmark records in a separate
+ * SQLite database.
+ *
+ * The buffer schema is a hybrid of how Sync and Places represent bookmarks.
+ * The `value` table contains item attributes (title, kind, description,
+ * URL, etc.), while the `structure` table stores parent-child relationships and
+ * position. This is similar to how iOS encodes "value" and "structure" state,
+ * though we handle these differently when merging. See `BookmarkMerger` for
+ * details.
+ *
+ * There's no guarantee that the remote state is consistent. We might be missing
+ * parents or children, or a bookmark and its parent might disagree about where
+ * it belongs. We do what we can to make the remote state into a mergeable tree.
+ * If the parent and child disagree, we take the last parent we see. We ignore
+ * missing children, and reparent bookmarks without parents to "unfiled". When
+ * we eventually see the missing items, either during a subsequent sync or as
+ * part of repair, we can fix up the local tree.
+ *
+ * We keep the buffer around for as long as it takes to download all records.
+ * If a sync is interrupted, we resume downloading based on the timestamp of the
+ * most recent record. If the server changes in the meantime, we replace the
+ * buffered records with new ones.
+ */
+class BookmarkBuffer {
+ constructor(db, { finalizeAt = AsyncShutdown.profileBeforeChange } = {}) {
+ this.db = db;
+ this.finalizeAt = finalizeAt;
+ this.finalizeBound = () => this.finalize();
+ this.finalizeAt.addBlocker("BookmarkBuffer: finalize", this.finalizeBound);
+ }
+
+ // Sets up the database connection and upgrades to the newest schema version.
+ static async open(schemaVersion, options) {
+ let db = await Sqlite.openConnection(options);
+ await db.executeBeforeShutdown("BookmarkBuffer: open", async function(db) {
+ await db.execute(`PRAGMA foreign_keys = ON`);
+ let currentSchemaVersion = await db.getSchemaVersion();
+ if (currentSchemaVersion != schemaVersion) {
+ await db.executeTransaction(() =>
+ migrateSchema(db, currentSchemaVersion, schemaVersion)
+ );
+ }
+ });
+ return new BookmarkBuffer(db, options);
+ }
+
+ // Stores a bookmark record in the buffer. Rejects if the record is invalid.
+ async store(record) {
+ ensureValidRecord(record);
+ let remoteAge = determineRemoteAge(this.currentRemoteTime(), record);
+
+ await this.db.executeBeforeShutdown("BookmarkBuffer: store", function(db) {
+ switch (record.type) {
+ case "bookmark":
+ BookmarkBufferLog.trace("Storing bookmark in buffer", record);
+ return storeBookmark(db, remoteAge, record);
+
+ case "query":
+ BookmarkBufferLog.trace("Storing query in buffer", record);
+ return storeQuery(db, remoteAge, record);
+
+ case "folder":
+ BookmarkBufferLog.trace("Storing folder in buffer", record);
+ return storeFolder(db, remoteAge, record);
+
+ case "livemark":
+ BookmarkBufferLog.trace("Storing livemark in buffer", record);
+ return storeLivemark(db, remoteAge, record);
+
+ case "separator":
+ BookmarkBufferLog.trace("Storing separator in buffer", record);
+ return storeSeparator(db, remoteAge, record);
+
+ default:
+ if (record.deleted) {
+ BookmarkBufferLog.trace("Storing tombstone in buffer", record);
+ return storeTombstone(db, remoteAge, record);
+ }
+ }
+ throw new TypeError("Can't store unknown Sync record type: " +
+ record.type);
+ });
+ }
+
+ // Applies the buffered bookmark records to Places, resolving merge conflicts
+ // and de-duping local items.
+ async apply() {
+ let placesDB = PlacesUtils.history.QueryInterface(Ci.nsPIPlacesDatabase);
+ let placesPath = placesDB.DBConnection.databaseFile.path;
+
+ await this.db.executeBeforeShutdown("BookmarkBuffer: apply", async function(db) {
+ await db.execute(`ATTACH :placesPath AS places`, { placesPath });
+ try {
+ await apply(db);
+ } finally {
+ await db.execute(`DETACH places`);
+ }
+ });
+ }
+
+ // Exposed for testing.
+ currentRemoteTime() {
+ return AsyncResource.serverTime;
+ }
+
+ async finalize() {
+ if (!this.finalizePromise) {
+ this.finalizePromise = (async () => {
+ await this.db.close();
+ this.finalizeAt.removeBlocker(this.finalizeBound);
+ })();
+ }
+ return this.finalizePromise;
+ }
+}
+
+// Upgrades an older schema to the current version, or creates fresh tables
+// for a new database. Downgrading from a newer profile to an older profile
+// will roll back the schema version, so we'll run the migration logic again
+// on the next upgrade.
+async function migrateSchema(db, currentSchemaVersion, maxSchemaVersion) {
+ let databaseInitialized = currentSchemaVersion > 0;
+ if (!databaseInitialized) {
+ await createBufferTables(db);
+ }
+ // TODO: Add future migration logic here.
+ await db.setSchemaVersion(maxSchemaVersion);
+}
+
+async function createBufferTables(db) {
+ await db.execute(`CREATE TABLE value(
+ id INTEGER PRIMARY KEY,
+ guid TEXT UNIQUE NOT NULL,
+ expectedParentGuid TEXT NOT NULL,
+ age INTEGER NOT NULL DEFAULT 0,
+ kind INTEGER NOT NULL DEFAULT -1,
+ dateAdded INTEGER NOT NULL DEFAULT 0,
+ title TEXT,
+ url TEXT,
+ keyword TEXT,
+ description TEXT,
+ loadInSidebar BOOLEAN,
+ smartBookmarkName TEXT,
+ tagFolderName TEXT,
+ feedURL TEXT,
+ siteURL TEXT
+ )`);
+
+ await db.execute(`CREATE TABLE structure(
+ guid TEXT PRIMARY KEY,
+ parentGuid TEXT NOT NULL REFERENCES value(guid) ON DELETE CASCADE,
+ position INTEGER NOT NULL
+ )`);
+
+ await db.execute(`CREATE TABLE tags(
+ itemId INTEGER NOT NULL REFERENCES value(id) ON DELETE CASCADE,
+ tag TEXT NOT NULL
+ )`);
+
+ await db.execute(`CREATE TABLE tombstones(
+ guid TEXT PRIMARY KEY,
+ age INTEGER NOT NULL
+ )`);
+
+}
+
+async function storeBookmark(db, remoteAge, record) {
+ let dateAdded = PlacesSyncUtils.bookmarks.ratchetTimestampBackwards(
+ record.dateAdded, +record.modified * 1000);
+
+ let url = formatRecordURL(record.bmkUri);
+
+ let guid = ensureValidGuid(record.id);
+ let expectedParentGuid = ensureValidGuid(record.parentid);
+ let title = formatRecordTitle(record.title);
+
+ // A keyword should only be associated with one URL, but it's possible for the
+ // server to contain incomplete data due to a partial write. We ignore this
+ // for now.
+ let keyword = record.keyword ? record.keyword.trim().toLowerCase() : null;
+
+ await db.executeCached(`
+ INSERT INTO value(guid, expectedParentGuid, age, kind, dateAdded, title,
+ url, keyword, description, loadInSidebar)
+ VALUES(:guid, :expectedParentGuid, :remoteAge, :kind, :dateAdded,
+ NULLIF(:title, ""), :url, :keyword, :description, :loadInSidebar)`,
+ { guid, expectedParentGuid, remoteAge, kind: KIND_BOOKMARK, dateAdded,
+ title, url: url.href, keyword, description: record.description,
+ loadInSidebar: record.loadInSidebar });
+
+ if (record.tags) {
+ for (let rawTag of record.tags) {
+ // Remove leading and trailing whitespace; ignore empty tags.
+ let tag = rawTag.trim();
+ if (!tag) {
+ continue;
+ }
+ await db.executeCached(`
+ INSERT INTO tags(itemId, tag)
+ SELECT id, :tag FROM value WHERE guid = :guid`,
+ { tag, guid });
+ }
+ }
+}
+
+async function storeQuery(db, remoteAge, record) {
+ let dateAdded = PlacesSyncUtils.bookmarks.ratchetTimestampBackwards(
+ record.dateAdded, +record.modified * 1000);
+
+ let guid = ensureValidGuid(record.id);
+ let expectedParentGuid = ensureValidGuid(record.parentid);
+
+ let url = formatRecordURL(record.bmkUri);
+ let title = formatRecordTitle(record.title);
+ let smartBookmarkName = null;
+ if (record.queryId) {
+ smartBookmarkName = record.queryId;
+ }
+ let tagFolderName = null;
+ if (record.folderName) {
+ tagFolderName = record.folderName.trim();
+ }
+
+ await db.executeCached(`
+ INSERT INTO value(guid, expectedParentGuid, age, kind, dateAdded, title,
+ url, description, smartBookmarkName, tagFolderName)
+ VALUES(:guid, :expectedParentGuid, :remoteAge, :kind, :dateAdded,
+ NULLIF(:title, ""), :url, :description, :smartBookmarkName,
+ :tagFolderName)`,
+ { guid, expectedParentGuid, remoteAge, kind: KIND_QUERY, dateAdded, title,
+ url: url.href, description: record.description, smartBookmarkName,
+ tagFolderName });
+}
+
+async function storeFolder(db, remoteAge, record) {
+ let dateAdded = PlacesSyncUtils.bookmarks.ratchetTimestampBackwards(
+ record.dateAdded, +record.modified * 1000);
+
+ let guid = ensureValidGuid(record.id);
+ let expectedParentGuid = ensureValidGuid(record.parentid);
+
+ let title = formatRecordTitle(record.title);
+
+ await db.executeCached(`
+ INSERT INTO value(guid, expectedParentGuid, age, kind, dateAdded, title,
+ description)
+ VALUES(:guid, :expectedParentGuid, :remoteAge, :kind, :dateAdded,
+ NULLIF(:title, ""), :description)`,
+ { guid, expectedParentGuid, remoteAge, kind: KIND_FOLDER, dateAdded, title,
+ description: record.description });
+
+ let children = record.children;
+ if (children) {
+ for (let position = 0; position < children.length; position++) {
+ await db.executeCached(`
+ INSERT INTO structure(guid, parentGuid, position)
+ VALUES(:childGuid, :parentGuid, :position)`,
+ { childGuid: children[position], parentGuid: guid, position });
+ }
+ }
+}
+
+async function storeLivemark(db, remoteAge, record) {
+ let dateAdded = PlacesSyncUtils.bookmarks.ratchetTimestampBackwards(
+ record.dateAdded, +record.modified * 1000);
+
+ let guid = ensureValidGuid(record.id);
+ let expectedParentGuid = ensureValidGuid(record.parentid);
+
+ let title = formatRecordTitle(record.title);
+ let feedURL = formatRecordURL(record.feedUri);
+ let siteURLString = typeof record.siteUri == "string" ?
+ formatRecordURL(record.siteUri).href :
+ null;
+
+ await db.executeCached(`
+ INSERT INTO value(guid, expectedParentGuid, age, kind, dateAdded, title,
+ description, feedURL, siteURL)
+ VALUES(:guid, :expectedParentGuid, :remoteAge, :kind, :dateAdded,
+ NULLIF(:title, ""), :description, :feedURL, :siteURL)`,
+ { guid, expectedParentGuid, remoteAge, kind: KIND_LIVEMARK, dateAdded,
+ title, description: record.description, feedURL: feedURL.href,
+ siteURL: siteURLString });
+}
+
+async function storeSeparator(db, remoteAge, record) {
+ let dateAdded = PlacesSyncUtils.bookmarks.ratchetTimestampBackwards(
+ record.dateAdded, +record.modified * 1000);
+
+ let guid = ensureValidGuid(record.id);
+ let expectedParentGuid = ensureValidGuid(record.parentid);
+
+ await db.executeCached(`
+ INSERT INTO value(guid, expectedParentGuid, age, kind, dateAdded)
+ VALUES(:guid, :expectedParentGuid, :remoteAge, :kind, :dateAdded)`,
+ { guid, expectedParentGuid, remoteAge, kind: KIND_SEPARATOR, dateAdded });
+}
+
+async function storeTombstone(db, remoteAge, record) {
+ let guid = ensureValidGuid(record.id);
+
+ await db.executeCached(`
+ INSERT INTO tombstones(guid, age)
+ VALUES(:guid, :remoteAge)`,
+ { guid, remoteAge });
+}
+
+/**
+ * Builds a complete merged tree from a complete local tree and a partial
+ * remote tree, resolving conflicts and relocating orphans, then applies
+ * the merged tree back to Places.
+ */
+async function apply(db) {
+ let storage = new BookmarkStorage(db);
+ let observersToNotify = new BookmarkObserverNotifications(storage);
+ let mergedTree = new MergedBookmarkTree();
+
+ await db.executeTransaction(async () => {
+ // TODO(kitcambridge): Periodically yield to check if we're shutting down,
+ // and throw to roll back the transaction. We can try merging again after
+ // the browser restarts.
+
+ // Build a tree from the buffer contents, with virtual folders linking items
+ // to the local tree.
+ let remoteTree = await storage.fetchRemoteTree();
+ BookmarkBufferLog.trace("Populated remote tree from buffer", remoteTree);
+
+ // Build a fully rooted local tree from what's currently in Places.
+ let localTree = await storage.fetchLocalTree();
+ if (!localTree.isFullyRooted()) {
+ // Should never happen. The local tree must be complete.
+ throw new BookmarkConsistencyError("Local tree not fully rooted");
+ }
+ BookmarkBufferLog.trace("Populated local tree from Places", localTree);
+
+ // Build a complete merged tree.
+ let merger = new BookmarkMerger(storage, localTree, remoteTree,
+ mergedTree);
+ await merger.merge();
+ if (BookmarkBufferLog.level <= Log.Level.Trace) {
+ let newTree = mergedTree.toBookmarkTree();
+ BookmarkBufferLog.trace("Built new merged tree", newTree);
+ }
+
+ // The merged tree should know about all items mentioned in the local and
+ // remote trees. Otherwise, it's incomplete; we'll corrupt Places or lose
+ // data on the server if we try to apply it.
+ if (!mergedTree.subsumes(localTree)) {
+ throw new BookmarkConsistencyError(
+ "Merged tree doesn't contain all items from local tree");
+ }
+ if (!mergedTree.subsumes(remoteTree)) {
+ throw new BookmarkConsistencyError(
+ "Merged tree doesn't contain all items from remote tree");
+ }
+
+ // Walk the merged tree and apply changes to Places.
+ for (let nodeInfo of mergedTree.walk()) {
+ await applyMergedNode(storage, observersToNotify, localTree, nodeInfo);
+ }
+
+ // Drop remotely deleted items. We could also do this before applying,
+ // since accepted remote deletions don't exist in the merged tree and
+ // we'll never query the local tree for their content.
+ for (let guid of mergedTree.deleteLocally) {
+ // Record observer notifications first, because we need to pass the removed
+ // item's info to the observer.
+ await observersToNotify.noteItemRemoved(guid);
+ await storage.delete(guid);
+ }
+
+ // Drop applied records from the buffer.
+ for (let guid of mergedTree.allGuids) {
+ await db.executeCached(`DELETE FROM value WHERE guid = :guid`, { guid });
+ }
+ });
+
+ // 6. Whew! Now notify all observers about the work we did.
+ await observersToNotify.notifyAll();
+}
+
+/**
+ * Recursively applies merged nodes to Places.
+ */
+async function applyMergedNode(storage, observersToNotify, localTree,
+ { newLocation, mergedNode }) {
+ let localNode = mergedNode.localNode;
+ if (localNode) {
+ let oldLocation = localTree.getLocation(localNode.guid);
+ if (!oldLocation) {
+ // Should never happen. Local nodes can't be virtual.
+ throw new BookmarkConsistencyError(`Local node ${localNode} missing ` +
+ `location`);
+ }
+ await updatePlacesItem(storage, observersToNotify, oldLocation,
+ newLocation, mergedNode);
+ } else {
+ await insertPlacesItem(storage, observersToNotify, newLocation,
+ mergedNode);
+ }
+
+ // Recursively apply merged children.
+ for (let childNodeInfo of mergedNode.walk()) {
+ await applyMergedNode(storage, observersToNotify, localTree,
+ childNodeInfo);
+ }
+}
+
+// Inserts a new remote node into Places. This function translates between
+// how Sync and Places represent bookmarks, rewrites tag queries, and sets
+// special annotations for descriptions, smart bookmarks, and livemarks.
+async function insertPlacesItem(storage, observersToNotify, location, mergedNode) {
+ let resolvedNode = mergedNode.resolveNode();
+ let content = await storage.fetchRemoteContent(resolvedNode.guid);
+
+ // Rewrite tag queries to point to the correct local tag folder, and
+ // insert the new URL into `moz_places`.
+ if (content.url) {
+ let tagFolderInfo = await storage.maybeRewriteTagQuery(content);
+ if (tagFolderInfo && tagFolderInfo.created) {
+ await observersToNotify.noteItemAdded(tagFolderInfo.guid);
+ }
+
+ await storage.maybeInsertPlace(content.url);
+
+ await updateKeyword(storage, observersToNotify, content.url,
+ content.keyword);
+ await updateTags(storage, observersToNotify, content.url);
+ }
+
+ await storage.insert(mergedNode.guid, location.parentGuid, location.position,
+ content.getPlacesType(), content.title, content.url,
+ content.dateAdded, mergedNode.getSyncChangeDelta(),
+ PlacesUtils.bookmarks.SYNC_STATUS.NORMAL);
+ await observersToNotify.noteItemAdded(mergedNode.guid);
+
+ let annoInfos = content.getAnnoInfos();
+ for (let info of annoInfos) {
+ if (!info.value) {
+ // The item doesn't exist locally, so we don't need to remove
+ // annotations that aren't explicitly set.
+ continue;
+ }
+ await storage.setAnno(mergedNode.guid, info);
+ observersToNotify.noteAnnoSet(mergedNode.guid, info.name);
+ }
+}
+
+async function updatePlacesItem(storage, observersToNotify, oldLocation,
+ newLocation, mergedNode) {
+ let columnsToUpdate = new Map();
+ let changesToNotify = new Map();
+
+ let localNode = mergedNode.localNode;
+ if (!localNode) {
+ // Should never happen. Use `insertPlacesItem` to insert new items.
+ throw new TypeError(`Can't update item ${mergedNode} without local node`);
+ }
+
+ // The GUID will be different if we deduped a NEW local item to an
+ // incoming remote item.
+ if (localNode.guid != mergedNode.guid) {
+ columnsToUpdate.set("newGuid", {
+ value: mergedNode.guid,
+ fragment: `guid = :newGuid`,
+ });
+ changesToNotify.set("guid", mergedNode.guid);
+ }
+
+ // Update the sync status to reflect that the item exists on the server.
+ if (localNode.syncStatus != PlacesUtils.bookmarks.SYNC_STATUS.NORMAL) {
+ columnsToUpdate.set("syncStatus", {
+ value: PlacesUtils.bookmarks.SYNC_STATUS.NORMAL,
+ });
+ }
+
+ if (oldLocation.position != newLocation.position) {
+ // Since the merged tree is complete, we update the position without
+ // moving any siblings out of the way. This means we may have multiple
+ // bookmarks in the same position until we finish merging and the
+ // transaction commits. However, once we're done, positions should be
+ // unique and without holes.
+ columnsToUpdate.set("position", { value: newLocation.position });
+ changesToNotify.set("position", newLocation.position);
+ }
+
+ if (oldLocation.parentGuid != newLocation.parentGuid) {
+ // Since we apply parents before children, the new parent should
+ // always exist.
+ columnsToUpdate.set("parentGuid", {
+ value: newLocation.parentGuid,
+ fragment: `parent = (SELECT id FROM moz_bookmarks
+ WHERE guid = :parentGuid)`,
+ });
+ changesToNotify.set("parentGuid", newLocation.parentGuid);
+ }
+
+ if (mergedNode.hasRemoteContent()) {
+ if (!mergedNode.remoteNode) {
+ // Should never happen. If we have remote content, we must have a remote
+ // node.
+ throw new BookmarkConsistencyError(`Can't update content for ` +
+ `${mergedNode} without remote node`);
+ }
+
+ let content = await storage.fetchRemoteContent(mergedNode.remoteNode.guid);
+ let placesType = content.getPlacesType();
+
+ if (placesType == PlacesUtils.bookmarks.TYPE_BOOKMARK ||
+ placesType == PlacesUtils.bookmarks.TYPE_FOLDER) {
+ columnsToUpdate.set("title", { value: content.title });
+ changesToNotify.set("title", content.title);
+ }
+
+ if (content.url) {
+ // Rewrite tag queries to point to the correct local tag folder before
+ // adding the new URL.
+ let tagFolderInfo = await storage.maybeRewriteTagQuery(content);
+ if (tagFolderInfo && tagFolderInfo.created) {
+ await observersToNotify.noteItemAdded(tagFolderInfo.guid);
+ }
+
+ await storage.maybeInsertPlace(content.url);
+
+ await updateKeyword(storage, observersToNotify, content.url,
+ content.keyword);
+ await updateTags(storage, observersToNotify, content.url);
+
+ let placeId = await storage.fetchLocalPlaceId(content.url);
+
+ columnsToUpdate.set("fk", { value: placeId });
+ changesToNotify.set("url", content.url);
+ }
+
+ // Update or remove annotations.
+ let annoInfos = content.getAnnoInfos();
+ for (let info of annoInfos) {
+ if (info.value) {
+ await storage.setAnno(localNode.guid, info);
+ observersToNotify.noteAnnoSet(mergedNode.guid, info.name);
+ } else {
+ await storage.removeAnno(localNode.guid, info.name);
+ observersToNotify.noteAnnoRemoved(mergedNode.guid, info.name);
+ }
+ }
+ }
+
+ if (!columnsToUpdate.size) {
+ return;
+ }
+
+ let lastModified = PlacesUtils.toPRTime(new Date());
+ columnsToUpdate.set("lastModified", { value: lastModified });
+
+ let syncChangeDelta = mergedNode.getSyncChangeDelta();
+ if (syncChangeDelta) {
+ columnsToUpdate.set("syncChangeDelta", {
+ value: syncChangeDelta,
+ fragment: "syncChangeCounter = syncChangeCounter + :syncChangeDelta",
+ });
+ }
+
+ // Record observer notifications before updating Places, so that we capture
+ // the old values.
+ await observersToNotify.noteItemChanged(mergedNode.guid, localNode.guid,
+ changesToNotify);
+ await storage.update(localNode.guid, columnsToUpdate);
+}
+
+
+async function updateKeyword(storage, observersToNotify, url, newKeyword) {
+ let keywordRows = await storage.fetchLocalKeywordsForURL(url);
+ for (let row of keywordRows) {
+ let existingKeyword = row.getResultByName("keyword");
+ await storage.removeLocalKeyword(url, existingKeyword);
+ observersToNotify.noteKeywordRemoved(url);
+ }
+
+ if (!newKeyword) {
+ return;
+ }
+
+ let urlRows = await storage.fetchLocalURLsForKeyword(newKeyword);
+ for (let row of urlRows) {
+ let existingURL = new URL(row.getResultByName("url"));
+ await storage.removeLocalKeyword(existingURL, newKeyword);
+ observersToNotify.noteKeywordRemoved(existingURL);
+ }
+
+ await storage.insertLocalKeyword(url, newKeyword);
+ observersToNotify.noteKeywordSet(url, newKeyword);
+}
+
+async function updateTags(storage, observersToNotify, url) {
+ let newTags = new Set();
+ let newTagRows = await storage.fetchRemoteTagsForURL(url);
+ for (let tagRow of newTagRows) {
+ let tagName = tagRow.getResultByName("tagName");
+ newTags.add(tagName);
+ }
+
+ // Remove all existing tags, except ones that we don't need to change because
+ // they're already set on the incoming bookmark.
+ let existingTags = new Set();
+ let existingTagRows = await storage.fetchLocalTagsForURL(url);
+ for (let tagRow of existingTagRows) {
+ let tagName = tagRow.getResultByName("tagName");
+ if (newTags.has(tagName)) {
+ existingTags.add(tagName);
+ continue;
+ }
+ let tagGuid = tagRow.getResultByName("tagGuid");
+ await observersToNotify.noteItemRemoved(tagGuid);
+ await storage.delete(tagGuid);
+ }
+
+ // Set new tags.
+ for (let tagName of newTags) {
+ if (existingTags.has(tagName)) {
+ continue;
+ }
+
+ // Create the tag folder, if one doesn't already exist.
+ let tagFolderInfo = await storage.getOrCreateTagFolder(tagName);
+ if (tagFolderInfo.created) {
+ await observersToNotify.noteItemAdded(tagFolderInfo.guid);
+ }
+
+ // Tag the URL.
+ let tagGuid = PlacesUtils.history.makeGuid();
+ await storage.insert(tagGuid, tagFolderInfo.guid, -1,
+ PlacesUtils.bookmarks.TYPE_BOOKMARK, /* title */ null,
+ url);
+ await observersToNotify.noteItemAdded(tagGuid);
+ }
+}
+
+function ensureValidRecord(record) {
+ // TODO(kitcambridge): More comprehensive validation.
+ let syncId = record.id;
+ if (!syncId || typeof syncId != "string") {
+ throw new Error(`Missing or invalid bookmark ID: ${syncId}`);
+ }
+ if (record.deleted) {
+ return;
+ }
+ let parentSyncId = record.parentid;
+ if (!parentSyncId || typeof parentSyncId != "string") {
+ throw new Error(`Missing parent sync ID for bookmark ${syncId}`);
+ }
+}
+
+// Calculates and returns the age of an incoming record on the server. This
+// should not be affected by client clock skew; however, we do compare local and
+// remote ages when resolving merge conflicts. Handling this skew is tracked in
+// bug 721181.
+function determineRemoteAge(currentRemoteTime, record) {
+ let remoteAge = currentRemoteTime - record.modified || 0;
+ return Math.max(remoteAge, 0);
+}
+
+// Validates and truncates a record's title.
+function formatRecordTitle(rawTitle) {
+ if (typeof rawTitle != "string" || !rawTitle) {
+ return null;
+ }
+ return rawTitle.slice(0, DB_TITLE_LENGTH_MAX);
+}
+
+// Validates and canonicalizes a bookmark record's URL.
+function formatRecordURL(rawURL) {
+ if (typeof rawURL != "string") {
+ throw new TypeError(`Expected URL string in record`);
+ }
+ if (rawURL.length > DB_URL_LENGTH_MAX) {
+ throw new TypeError(`Record URL too long`);
+ }
+ return new URL(rawURL);
+}
+
+function ensureValidGuid(syncId) {
+ let guid = PlacesSyncUtils.bookmarks.syncIdToGuid(syncId);
+ if (!PlacesUtils.isValidGuid(guid)) {
+ throw new TypeError(`${syncId} is not a valid GUID`);
+ }
+ return guid;
+}
+
+/**
+ * The merge state indicates which node we should prefer when reconciling
+ * with Places. iOS separates this into "value state" and "structure state",
+ * but, since Places doesn't make that distinction, we use a single "merge
+ * state" instead. iOS also has an "unchanged" state that takes the mirror
+ * node, which we omit since we don't have a mirror.
+ *
+ * Recall that a merged node may point to a local node, remote node, or
+ * both.
+ *
+ * - `BookmarkMergeState.local` means no changes: we keep the local location
+ * and content info. This could mean that the item doesn't exist on the
+ * server yet, or that it has newer local changes that we should upload. It's
+ * an error for a merged node to have a "local" merge state without a local
+ * node; resolving the node asserts this.
+ *
+ * - `BookmarkMergeState.remote` means we update Places with new location and
+ * content info from the buffer. The item might not exist locally yet, or
+ * might have newer remote changes that we should apply. As with "local", a
+ * merged node can't have a "remote" merge state without a remote node.
+ *
+ * - `BookmarkMergeState.new` is like `remote`, but holds a synthesized node
+ * that overrides local and remote. We still update Places with new content
+ * info from the buffer, but the location info is different. This happens
+ * when we move new local items out of a remotely deleted folder, or new
+ * remote items out of a locally deleted folder. Applying a "new" merged node
+ * also bumps its change counter, so that the merged structure is reuploaded
+ * to the server on the next sync.
+ */
+class BookmarkMergeState {
+ constructor(type, newNode = null) {
+ this.type = type;
+ this.newNode = newNode;
+ }
+
+ static new(newNode) {
+ return new BookmarkMergeState("new", newNode);
+ }
+
+ toString() {
+ return this.newNode ? `${this.type} (${
+ this.newNode})` : this.type;
+ }
+}
+
+BookmarkMergeState.local = new BookmarkMergeState("local");
+BookmarkMergeState.remote = new BookmarkMergeState("remote");
+
+/**
+ * Holds the location information for a local or remote bookmark node. This
+ * is similar to the "structure state" concept on iOS, but not quite. We call
+ * it "location info" to avoid confusion: unlike iOS, we conflate value and
+ * structure, and we don't merge structure changes separately.
+ */
+class BookmarkLocation {
+ constructor(parentGuid, position) {
+ this.parentGuid = parentGuid;
+ this.position = position;
+ }
+
+ hasSamePosition(otherLocation) {
+ if (this.position < 0 || otherLocation.position < 0) {
+ return false;
+ }
+ return this.position == otherLocation.position;
+ }
+}
+
+/**
+ * A node in a local or remote bookmark tree. Nodes are lightweight: they carry
+ * enough information for the merger to resolve trivial conflicts without
+ * querying the buffer or Places for the complete content info.
+ *
+ * There are 7 kinds of nodes: one for each Sync record kind, plus virtual
+ * folders and items. They're virtual because we create them in memory; they're
+ * not stored in the buffer or Places.
+ *
+ * A virtual folder is usually the topmost folder in a tree or subtree, without
+ * location or content. In a remote tree, virtual folders link new children of
+ * an existing parent, and children with content-only changes, to the complete
+ * local tree. Virtual folders are incomplete: we likely don't have all their
+ * children, and we don't know the child order.
+ *
+ * A local tree, which is always complete, should have exactly one virtual
+ * folder: the Places root, from which the four syncable roots descend.
+ *
+ * A virtual item node has location, but no content: we know its parent and
+ * position, but not its age, kind, title, URL, etc. In a remote tree, a virtual
+ * item's parent exists in both `value` and `structure`, but the virtual item
+ * only exists in `structure`.
+ *
+ * A local tree should never have virtual leaves.
+ */
+class BookmarkNode {
+ constructor(guid, age, kind, syncChangeCounter, syncStatus) {
+ this.guid = guid;
+ this.kind = kind;
+ this.age = Math.max(age, 0);
+ this.syncChangeCounter = syncChangeCounter;
+ this.syncStatus = syncStatus;
+ this.children = [];
+ }
+
+ static virtualFolder(guid) {
+ let syncStatus = PlacesUtils.bookmarks.SYNC_STATUS.UNKNOWN;
+ return new BookmarkNode(guid, 0, KIND_VIRTUAL_FOLDER, 0, syncStatus);
+ }
+
+ static virtualItem(guid) {
+ let syncStatus = PlacesUtils.bookmarks.SYNC_STATUS.UNKNOWN;
+ return new BookmarkNode(guid, 0, KIND_VIRTUAL_ITEM, 0, syncStatus);
+ }
+
+ // Creates a bookmark node from a Places row.
+ static fromLocalRow(row) {
+ let guid = row.getResultByName("guid");
+
+ // Note that this doesn't account for local clock skew.
+ let lastModified = row.getResultByName("lastModified");
+ let age = Date.now() - lastModified / 1000;
+
+ let kind = row.getResultByName("kind");
+ let syncChangeCounter = row.getResultByName("syncChangeCounter");
+ let syncStatus = row.getResultByName("syncStatus");
+
+ return new BookmarkNode(guid, age, kind, syncChangeCounter, syncStatus);
+ }
+
+ // Creates a bookmark node from an incoming buffer row.
+ static fromRemoteRow(row) {
+ let guid = row.getResultByName("guid");
+ let age = row.getResultByName("age");
+ let kind = row.getResultByName("kind");
+
+ // We always flag remote items as changed; otherwise, we wouldn't have
+ // downloaded them and they wouldn't exist in the buffer. Similarly, remote
+ // items are already syncing by definition, and thus shouldn't be duped
+ // to other remote items.
+ let syncChangeCounter = 1;
+ let syncStatus = PlacesUtils.bookmarks.SYNC_STATUS.NORMAL;
+
+ return new BookmarkNode(guid, age, kind, syncChangeCounter, syncStatus);
+ }
+
+ isRoot() {
+ return this.guid == PlacesUtils.bookmarks.rootGuid ||
+ this.guid == PlacesUtils.bookmarks.tagsGuid ||
+ this.guid == PlacesUtils.bookmarks.menuGuid ||
+ this.guid == PlacesUtils.bookmarks.toolbarGuid ||
+ this.guid == PlacesUtils.bookmarks.unfiledGuid ||
+ this.guid == PlacesUtils.bookmarks.mobileGuid;
+ }
+
+ isVirtual() {
+ return this.kind == KIND_VIRTUAL_FOLDER ||
+ this.kind == KIND_VIRTUAL_ITEM;
+ }
+
+ isVirtualRoot() {
+ return this.guid == PlacesUtils.bookmarks.rootGuid &&
+ this.kind == KIND_VIRTUAL_FOLDER;
+ }
+
+ isFolder() {
+ return this.kind == KIND_VIRTUAL_FOLDER ||
+ this.kind == KIND_FOLDER;
+ }
+
+ newerThan(otherNode) {
+ return this.age < otherNode.age;
+ }
+
+ /**
+ * Indicates if the node's structure or value state has changed. This is
+ * `true` for local nodes with a positive change counter, and always `true`
+ * for remote nodes.
+ */
+ isChanged() {
+ return this.syncChangeCounter > 0;
+ }
+
+ /**
+ * Indicates whether the node can dupe to another node with a different
+ * GUID and similar content. This is `true` for local nodes that haven't
+ * been uploaded to the server yet, and always `false` for remote and
+ * virtual nodes.
+ */
+ canDupe() {
+ return this.syncStatus == PlacesUtils.bookmarks.SYNC_STATUS.NEW;
+ }
+
+ hasSameChildren(otherNode) {
+ if (!this.isFolder()) {
+ throw new TypeError(`Can't compare children of non-folder node ${this}`);
+ }
+ if (!otherNode.isFolder()) {
+ throw new TypeError("Can't compare children of non-folder node " +
+ otherNode);
+ }
+ if (this.isVirtual() || otherNode.isVirtual()) {
+ // Comparing the children of virtual roots doesn't make sense, since
+ // they're incomplete.
+ return false;
+ }
+ if (this.children.length != otherNode.children.length) {
+ return false;
+ }
+ for (let position = 0; position < this.children.length; position++) {
+ let child = this.children[position];
+ let otherChild = otherNode.children[position];
+ if (child.guid != otherChild.guid) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ toString() {
+ return `${this.guid} (${this.kind})`;
+ }
+}
+
+/**
+ * A complete or partial bookmark tree with tombstones.
+ */
+class BookmarkTree {
+ constructor() {
+ this.byGuid = new Map();
+ this.locations = new WeakMap();
+ this.orphanParentGuids = new WeakMap();
+ this.deletedGuids = new Set();
+ }
+
+ // Creates a tree containing the Places root.
+ static rooted() {
+ let tree = new BookmarkTree();
+ let root = BookmarkNode.virtualFolder(PlacesUtils.bookmarks.rootGuid);
+ tree.insertRoot(root);
+ return tree;
+ }
+
+ has(guid) {
+ return this.byGuid.has(guid);
+ }
+
+ /**
+ * Indicates if the tree contains all items and their parents, up to the four
+ * syncable roots: menu, toolbar, unfiled, and mobile. This is always `true`
+ * for local trees, and likely `false` for remote trees except for the first
+ * sync.
+ */
+ isFullyRooted() {
+ for (let node of this.byGuid.values()) {
+ if (node.isVirtualRoot()) {
+ continue;
+ }
+ if (node.isVirtual()) {
+ return false;
+ }
+ }
+ return true;
+ }
+
+ isDeleted(guid) {
+ return this.deletedGuids.has(guid);
+ }
+
+ getByGuid(guid) {
+ return this.byGuid.get(guid);
+ }
+
+ getParent(childGuid) {
+ let structureInfo = this.getLocation(childGuid);
+ return structureInfo ? this.byGuid.get(structureInfo.parentGuid) : null;
+ }
+
+ getLocation(guid) {
+ let node = this.byGuid.get(guid);
+ if (!node) {
+ return null;
+ }
+ return this.locations.get(node);
+ }
+
+ /**
+ * Inserts a root to the tree. Roots must not already exist in the tree, and
+ * must be virtual folders.
+ */
+ insertRoot(rootNode) {
+ if (rootNode.kind != KIND_VIRTUAL_FOLDER) {
+ throw new TypeError(`Root node ${rootNode} is not a virtual folder`);
+ }
+ let existingNode = this.byGuid.get(rootNode.guid);
+ if (existingNode) {
+ throw new TypeError(`Can't replace node ${existingNode} with root ` +
+ rootNode);
+ }
+ this.byGuid.set(rootNode.guid, rootNode);
+ }
+
+ /**
+ * Inserts a non-root node into the tree. The node must not already exist in
+ * the tree, and the node's parent must be a folder or virtual folder.
+ */
+ insert(parentGuid, node) {
+ let existingNode = this.byGuid.get(node.guid);
+ if (existingNode) {
+ throw new TypeError(`Can't replace node ${existingNode} with node ` +
+ node);
+ }
+
+ let parentNode = this.byGuid.get(parentGuid);
+ if (!parentNode) {
+ throw new TypeError(`Tree missing parent ${parentGuid} for node ${node}`);
+ }
+ if (!parentNode.isFolder()) {
+ throw new TypeError(`Can't add node ${node} to non-folder ${parentNode}`);
+ }
+ parentNode.children.push(node);
+
+ let position = parentNode.children.length - 1;
+ let location = new BookmarkLocation(parentGuid, position);
+ this.locations.set(node, location);
+
+ this.byGuid.set(node.guid, node);
+ }
+
+ noteOrphan(guid, expectedParentGuid) {
+ let node = this.byGuid.get(guid);
+ if (!node) {
+ throw new TypeError(`Can't mark nonexistent node ${guid} as orphan`);
+ }
+ this.orphanParentGuids.set(node, expectedParentGuid);
+ }
+
+ isOrphan(guid) {
+ return this.orphanParentGuids.has(guid);
+ }
+
+ noteDeleted(guid) {
+ this.deletedGuids.add(guid);
+ }
+
+ *roots() {
+ for (let [, node] of this.byGuid) {
+ let location = this.locations.get(node);
+ if (!location) {
+ // Roots don't have location info.
+ yield node;
+ }
+ }
+ }
+
+ *guids() {
+ for (let [guid, node] of this.byGuid) {
+ if (node.isVirtualRoot()) {
+ continue;
+ }
+ yield guid;
+ }
+ for (let guid of this.deletedGuids) {
+ yield guid;
+ }
+ }
+
+ toJSON() {
+ let roots = Array.from(this.roots());
+ let deleted = Array.from(this.deletedGuids);
+ return { roots, deleted };
+ }
+}
+
+/**
+ * A complete, consistent tree that contains merged nodes for all items seen
+ * locally and remotely.
+ */
+class MergedBookmarkTree {
+ constructor() {
+ this.allGuids = new Set();
+ this.deleteLocally = new Set();
+ this.deleteRemotely = new Set();
+ this.mergedRoots = [];
+ }
+
+ insertRoot(mergedNode) {
+ this.mergedRoots.push(mergedNode);
+ }
+
+ toBookmarkTree() {
+ let tree = BookmarkTree.rooted();
+ for (let mergedRootNode of this.mergedRoots) {
+ let rootNode = mergedRootNode.toBookmarkNode();
+ tree.insert(PlacesUtils.bookmarks.rootGuid, rootNode);
+ }
+ return tree;
+ }
+
+ /**
+ * Walks the children of the merged roots. Yields a `{ newLocation,
+ * mergedNode }` tuple for each child.
+ */
+ *walk() {
+ for (let mergedRootNode of this.mergedRoots) {
+ yield* mergedRootNode.walk();
+ }
+ }
+
+ exists(guid) {
+ return this.allGuids.has(guid) ||
+ this.deleteLocally.has(guid) ||
+ this.deleteRemotely.has(guid);
+ }
+
+ subsumes(tree) {
+ for (let guid of tree.guids()) {
+ if (!this.exists(guid)) {
+ return false;
+ }
+ }
+ return true;
+ }
+}
+
+/**
+ * A node in a merged bookmark tree. Holds the local node, remote node,
+ * unordered merged children, and a merge state indicating which side to
+ * prefer when applying the node to Places.
+ */
+class MergedBookmarkNode {
+ constructor(guid, localNode, remoteNode, mergeState) {
+ this.guid = guid;
+ this.localNode = localNode;
+ this.remoteNode = remoteNode;
+ this.mergeState = mergeState;
+ this.mergedChildren = [];
+ }
+
+ /**
+ * Orders a merged folder node's children.
+ *
+ * Ordering solves two issues with our merge strategy for folders that exist
+ * locally and remotely. Recall that we walk remote children before local, and
+ * that we insert virtual parent folders for items with content-only changes.
+ * This means:
+ *
+ * - Adding new items to a folder remotely and reordering that folder's
+ * children locally discards the new local order, since we first walk the
+ * remote children in their original order.
+ * - For content-only changes, walking the remote children of a virtual folder
+ * moves the changed items to the beginning of the folder, followed by the
+ * local items that don't exist remotely.
+ *
+ * Ordering takes the newer child list, then appends remaining items from
+ * the older list, and relocated orphans that don't exist in either list.
+ * Virtual remote folders always lose to non-virtual local folders.
+ *
+ * @returns {Boolean}
+ * `true` if the children were reordered; `false` if they're already
+ * in the correct order.
+ */
+ orderChildren() {
+ // Decide which child list is newer. If the node only exists on one side,
+ // its children are already in order.
+ let newerChildList;
+ let olderChildList;
+ switch (this.mergeState.type) {
+ case "local":
+ if (!this.localNode) {
+ throw new BookmarkConsistencyError(`Can't take newer local child ` +
+ `order for ${this} without ` +
+ `local node`);
+ }
+ if (!this.remoteNode) {
+ BookmarkBufferLog.trace("Taking complete local child order " +
+ "for ${mergedNode}", { mergedNode: this });
+ return false;
+ }
+ newerChildList = this.localNode.children;
+ if (!this.remoteNode.isVirtual()) {
+ // Virtual folders are incomplete, so their child order is
+ // meaningless. Use the local order only, and append relocated
+ // orphans to the end.
+ olderChildList = this.remoteNode.children;
+ }
+ break;
+
+ case "remote":
+ if (!this.remoteNode) {
+ throw new BookmarkConsistencyError(`Can't take newer remote child ` +
+ `order for ${this} without ` +
+ `remote node`);
+ }
+ if (!this.localNode) {
+ BookmarkBufferLog.trace("Taking complete remote child order " +
+ "for ${mergedNode}", { mergedNode: this });
+ return false;
+ }
+ // No need to check if `remoteNode` is virtual here, since we always use
+ // the local merge state.
+ newerChildList = this.remoteNode.children;
+ olderChildList = this.localNode.children;
+ break;
+
+ default:
+ // Assume the children of a new merged folder node are already in order.
+ return false;
+ }
+
+ let positions = new Map();
+
+ BookmarkBufferLog.trace("Ordering merged children of ${mergedNode}, " +
+ "using ${newerChildList} as base",
+ { mergedNode: this, newerChildList });
+
+ // Record the positions of all children in the newer list. Note that
+ // moved or deleted items might appear in both lists. That's fine: they
+ // don't appear in the merged child list, so sorting will ignore them.
+ for (let position = 0; position < newerChildList.length; position++) {
+ let newChildNode = newerChildList[position];
+ positions.set(newChildNode.guid, position);
+ }
+
+ // Append remaining children from the older list. This preserves the
+ // order of the remaining children relative to each other, but not relative
+ // to the children that appear in the newer list.
+ let remainingItemPosition = positions.size;
+ if (olderChildList) {
+ for (let oldChildNode of olderChildList) {
+ if (positions.has(oldChildNode.guid)) {
+ continue;
+ }
+ positions.set(oldChildNode.guid, remainingItemPosition);
+ remainingItemPosition++;
+ }
+ }
+
+ // Finally, append any relocated orphans that don't appear in either list.
+ for (let mergedChildNode of this.mergedChildren) {
+ if (positions.has(mergedChildNode.guid)) {
+ continue;
+ }
+ positions.set(mergedChildNode.guid, remainingItemPosition);
+ remainingItemPosition++;
+ }
+
+ this.mergedChildren.sort((a, b) => {
+ return positions.get(a.guid) < positions.get(b.guid) ? -1 : 1;
+ });
+
+ return true;
+ }
+
+ resolveNode() {
+ let resolvedNode;
+ switch (this.mergeState.type) {
+ case "local":
+ if (!this.localNode) {
+ throw new BookmarkConsistencyError(`Can't resolve ${this} without ` +
+ `local node`);
+ }
+ resolvedNode = this.localNode;
+ break;
+
+ case "remote":
+ if (!this.remoteNode) {
+ throw new BookmarkConsistencyError(`Can't resolve ${this} without ` +
+ `remote node`);
+ }
+ resolvedNode = this.remoteNode;
+ break;
+
+ case "new": {
+ resolvedNode = this.mergeState.newNode;
+ if (!resolvedNode) {
+ throw new BookmarkConsistencyError(`Can't resolve ${this} without ` +
+ `new node`);
+ }
+ break;
+ }
+
+ default:
+ throw new TypeError(`Can't resolve node with unknown merge state: ` +
+ this.mergeState);
+ }
+ if (resolvedNode.isVirtual()) {
+ // Should never happen. Local nodes can't be virtual, and we'll never
+ // take a remote or new virtual node.
+ throw new BookmarkConsistencyError(`Can't resolve ${this} to virtual ` +
+ `node ${resolvedNode}`);
+ }
+ return resolvedNode;
+ }
+
+ getSyncChangeDelta() {
+ switch (this.mergeState.type) {
+ case "local":
+ // The item is unchanged, so we don't need to bump its change counter.
+ return 0;
+
+ case "remote": {
+ if (!this.remoteNode) {
+ throw new BookmarkConsistencyError(`Can't determine sync change ` +
+ `delta for ${this} without ` +
+ `remote node`);
+ }
+ // If we're taking the remote state, the item doesn't need to be
+ // reuploaded, so reduce its change counter to zero.
+ let syncChangeCounter = this.remoteNode.syncChangeCounter;
+ return syncChangeCounter > 0 ? -syncChangeCounter : 0;
+ }
+
+ case "new":
+ // If we're taking a new merge state, the synthesized node doesn't
+ // match what's currently on the server, so bump its change counter to
+ // ensure it's reuploaded.
+ return 1;
+ }
+ throw new TypeError(`Can't determine sync change delta with unknown ` +
+ `merge state: ${this.mergeState}`);
+ }
+
+ hasRemoteContent() {
+ switch (this.mergeState.type) {
+ case "local":
+ // Keeping complete local state, so no need to fetch remote item content
+ // from the buffer or update Places.
+ return false;
+
+ case "new":
+ // Taking new merge state. Only update the local item with new remote
+ // content if we have a non-virtual remote node.
+ return this.remoteNode ? !this.remoteNode.isVirtual() : false;
+
+ case "remote":
+ // Taking complete remote state, so we must have remote content.
+ return true;
+ }
+ throw new TypeError(`Can't determine remote content with unknown merge ` +
+ `state: ${this.mergeState}`);
+ }
+
+ /**
+ * Yields a `{ newLocation, mergedNode }` tuple for each merged child.
+ */
+ *walk() {
+ for (let position = 0; position < this.mergedChildren.length; position++) {
+ let newLocation = new BookmarkLocation(this.guid, position);
+ let mergedChildNode = this.mergedChildren[position];
+ yield { newLocation, mergedNode: mergedChildNode };
+ }
+ }
+
+ toBookmarkNode() {
+ let resolvedNode = this.resolveNode();
+ if (!resolvedNode.isFolder()) {
+ return resolvedNode;
+ }
+
+ let node = new BookmarkNode(this.guid, resolvedNode.age,
+ resolvedNode.kind, resolvedNode.syncChangeCounter,
+ resolvedNode.syncStatus);
+
+ for (let mergedChildNode of this.mergedChildren) {
+ node.children.push(mergedChildNode.toBookmarkNode());
+ }
+ return node;
+ }
+
+ toString() {
+ return this.guid;
+ }
+}
+
+/**
+ * A two-way merger that produces a complete merged tree from a complete local
+ * tree and a likely incomplete remote tree with changes since the last sync.
+ *
+ * This is ported almost directly from iOS. On iOS, the `ThreeWayMerger` takes a
+ * complete "mirror" tree with the server state after the last sync, and two
+ * incomplete trees with local and remote changes since the last sync: "local"
+ * and "buffer", respectively. Overlaying buffer onto mirror gives us the
+ * current server state; overlaying local onto mirror gives us the complete
+ * local state.
+ *
+ * On Desktop, our `localTree` is the union of mirror and local, and our
+ * `remoteTree` is buffer. All items with change counter = 0 roughly map to
+ * mirror nodes, and items with change counter > 0 map to local nodes.
+ *
+ * Unlike iOS, we can only do two-way merges, since we don't store the shared
+ * parent. Also, our merger doesn't distinguish between structure and value
+ * changes, since we don't record that state: the change counter notes *that*
+ * a bookmark changed, but not *how*. This implies that we can do the wrong
+ * thing for merge conflicts that iOS handles correctly.
+ *
+ * Fortunately, most of our users don't organize their bookmarks into deeply
+ * nested hierarchies, or make conflicting changes on multiple devices
+ * simultaneously. Changing Places to record structure and value changes, and
+ * store shared parents for changed bookmarks, means rethinking the entire
+ * storage schema. A simpler two-way tree merge strikes a good balance between
+ * correctness and complexity.
+ */
+class BookmarkMerger {
+ constructor(storage, localTree, remoteTree, mergedTree) {
+ this.storage = storage;
+ this.localTree = localTree;
+ this.remoteTree = remoteTree;
+ this.mergedTree = mergedTree;
+ }
+
+ async merge() {
+ // Starting at the roots, walk and merge each node. We expect all roots to
+ // exist locally, since the local tree is complete. The root may not exist
+ // remotely if it's unmodified, but that's fine: we'll take the local node
+ // in that case.
+ let rootNode = this.localTree.getByGuid(PlacesUtils.bookmarks.rootGuid);
+ for (let localRoot of rootNode.children) {
+ let remoteRoot = this.remoteTree.getByGuid(localRoot.guid);
+ let mergedNode = await this.mergeNode(localRoot.guid, localRoot,
+ remoteRoot);
+ this.mergedTree.insertRoot(mergedNode);
+ }
+
+ // Take remaining local and remote tombstones.
+ for (let guid of this.localTree.deletedGuids) {
+ if (!this.mergedTree.exists(guid)) {
+ this.mergedTree.deleteRemotely.add(guid);
+ }
+ }
+ for (let guid of this.remoteTree.deletedGuids) {
+ if (!this.mergedTree.exists(guid)) {
+ this.mergedTree.deleteLocally.add(guid);
+ }
+ }
+ }
+
+ /**
+ * Merges two nodes, recursively walking folders.
+ *
+ * @param {String} guid
+ * The GUID to use for the merged node.
+ * @param {BookmarkNode?} localNode
+ * The local node. May be `null` if the node only exists remotely,
+ * but may not be a virtual node.
+ * @param {BookmarkNode?} remoteNode
+ * The remote node. May be `null` if the node only exists locally,
+ * and may be virtual.
+ * @returns {MergedBookmarkNode}
+ * The merged node, with merged folder children.
+ */
+ async mergeNode(mergedGuid, localNode, remoteNode) {
+ this.mergedTree.allGuids.add(mergedGuid);
+
+ if (localNode) {
+ // The node exists locally.
+ if (localNode.guid != mergedGuid) {
+ // We deduped a NEW local item to a remote item.
+ this.mergedTree.allGuids.add(localNode.guid);
+ }
+ if (remoteNode) {
+ if (!remoteNode.isVirtual()) {
+ // The node exists locally and remotely, so we do a two-way merge.
+ BookmarkBufferLog.trace("Item ${mergedGuid} exists locally as " +
+ "${localNode} and remotely as " +
+ "${remoteNode}; merging",
+ { mergedGuid, localNode, remoteNode });
+ let mergedNode = await this.twoWayMerge(mergedGuid, localNode,
+ remoteNode);
+ return mergedNode;
+ }
+ // The local node exists remotely, but it's virtual, so we don't know
+ // its value or structure. Fall back to the local state.
+ BookmarkBufferLog.trace("Item ${mergedGuid} exists locally as " +
+ "${localNode} and remotely as virtual node " +
+ "${remoteNode}; taking local state",
+ { mergedGuid, localNode, remoteNode });
+ } else {
+ // The local node doesn't exist remotely at all.
+ BookmarkBufferLog.trace("Item ${mergedGuid} only exists locally as " +
+ "${localNode}; taking local state",
+ { mergedGuid, localNode });
+ }
+ let mergedNode = new MergedBookmarkNode(mergedGuid, localNode, remoteNode,
+ BookmarkMergeState.local);
+ if (localNode.isFolder()) {
+ // The local folder doesn't exist in the remote tree, but its children
+ // might, so we still need to recursively walk and merge them. This
+ // method will change the merge state from "local" to "new" if any
+ // children were moved or deleted.
+ await this.mergeChildListsIntoMergedNode(mergedNode, localNode, remoteNode);
+ }
+ return mergedNode;
+ }
+
+ if (remoteNode) {
+ // The node only exists remotely, so we take the remote state.
+ if (remoteNode.isVirtual()) {
+ // We can't supply the missing content from the local tree.
+ // TODO(kitcambridge): This will throw if we upload a parent, but not
+ // its children. Consider moving the node's children to `unfiled` if
+ // it's a folder, or skipping if it's an item.
+ throw new BookmarkConsistencyError(`Can't take remote-only node ` +
+ `${remoteNode} without content`);
+ }
+ let mergedNode = new MergedBookmarkNode(mergedGuid, null, remoteNode,
+ BookmarkMergeState.remote);
+ if (remoteNode.isFolder()) {
+ // As above, a remote folder's children might still exist locally, so we
+ // need to merge them and update the merge state from "remote" to "new"
+ // if any children were moved or deleted.
+ await this.mergeChildListsIntoMergedNode(mergedNode, null, remoteNode);
+ }
+ return mergedNode;
+ }
+
+ // Should never happen. We need to have at least one node for a two-way
+ // merge.
+ throw new BookmarkConsistencyError("Can't merge two nonexistent nodes");
+ }
+
+ /**
+ * Merges two nodes that exist locally and remotely.
+ *
+ * @param {String} mergedGuid
+ * The GUID to use for the merged node.
+ * @param {BookmarkNode} localNode
+ * The existing local node. May not be a virtual node.
+ * @param {BookmarkNode} remoteNode
+ * The existing remote node. May not be a virtual node.
+ * @returns {MergedBookmarkNode}
+ * The merged node, with merged folder children.
+ */
+ async twoWayMerge(mergedGuid, localNode, remoteNode) {
+ if (localNode.isVirtual()) {
+ // Should never happen. Local nodes can't be virtual.
+ throw new BookmarkConsistencyError(`Can't two-way merge virtual local ` +
+ `node ${localNode}`);
+ }
+ if (remoteNode.isVirtual()) {
+ // Should never happen. We always take the local state if the remote node
+ // is virtual.
+ throw new BookmarkConsistencyError(`Can't two-way merge virtual remote ` +
+ `node ${localNode}`);
+ }
+
+ let mergeState = await this.resolveTwoWayValueConflict(mergedGuid, localNode, remoteNode);
+ BookmarkBufferLog.trace("Merge state for ${mergedGuid} is ${mergeState}",
+ { mergedGuid, mergeState });
+
+ let mergedNode = new MergedBookmarkNode(mergedGuid, localNode, remoteNode,
+ mergeState);
+
+ let localIsFolder = localNode.isFolder();
+ let remoteIsFolder = remoteNode.isFolder();
+
+ if (!localIsFolder && !remoteIsFolder) {
+ // Merging two non-folders, so no children to walk.
+ BookmarkBufferLog.trace("${mergedGuid} not folder; taking merge state " +
+ "without merging children", { mergedGuid });
+ return mergedNode;
+ }
+
+ if (localIsFolder && remoteIsFolder) {
+ // Merging two folders, so we need to walk their children to make sure we
+ // handle moves and deletions.
+ BookmarkBufferLog.trace("${mergedGuid} is folder; need to walk children",
+ { mergedGuid });
+ await this.mergeChildListsIntoMergedNode(mergedNode, localNode,
+ remoteNode);
+ return mergedNode;
+ }
+
+ throw new BookmarkConsistencyError("Can't merge folder and non-folder");
+ }
+
+ /**
+ * Determines the merge state for a node that exists locally and remotely.
+ *
+ * @param {String} mergedGuid
+ * The GUID of the merged node. This is the same as the remote GUID,
+ * and usually the same as the local GUID. The local GUID may be
+ * different if we're duping a local item to a remote item.
+ * @param {String} localNode
+ * The local bookmark node.
+ * @param {BookmarkNode} remoteNode
+ * The remote bookmark node.
+ * @returns {BookmarkMergeState}
+ * The two-way merge state.
+ */
+ async resolveTwoWayValueConflict(mergedGuid, localNode, remoteNode) {
+ if (localNode.isRoot()) {
+ // Roots are immutable, so we always take the local state.
+ return BookmarkMergeState.local;
+ }
+
+ if (localNode.isVirtual()) {
+ // Should never happen. Local nodes can't be virtual.
+ throw new BookmarkConsistencyError(`Can't resolve conflicts for ` +
+ `virtual local node ${localNode}`);
+ }
+
+ if (remoteNode.isVirtual()) {
+ // The node exists remotely, but doesn't know its content, so fall back
+ // to local.
+ return BookmarkMergeState.local;
+ }
+
+ if (!localNode.isChanged()) {
+ // The node exists locally and remotely, and has a remote value, but is
+ // unchanged locally. Take the remote unconditionally.
+ return BookmarkMergeState.remote;
+ }
+
+ // At this point, we know the item changed locally and remotely. We could
+ // query the buffer and Places to determine if the content matches, as iOS
+ // does, and avoid comparing timestamps. However, that's a complicated,
+ // expensive check that requires joining `moz_bookmarks`, `moz_items_annos`,
+ // and `moz_places` to the buffer. It's also unlikely to tell us anything
+ // new, since other clients typically don't upload unchanged records. For
+ // that reason, we skip the content check and use the timestamp to decide
+ // which record is newer.
+ return localNode.newerThan(remoteNode) ?
+ BookmarkMergeState.local :
+ BookmarkMergeState.remote;
+ }
+
+ /**
+ * Merges a remote child node into a merged folder node.
+ *
+ * @param {MergedBookmarkNode} mergedNode
+ * The merged folder node.
+ * @param {BookmarkNode} remoteParentNode
+ * The remote folder node.
+ * @param {BookmarkNode} remoteChildNode
+ * The remote child node.
+ * @returns {Boolean}
+ * `true` if the child was locally moved or deleted; `false`
+ * otherwise.
+ */
+ async mergeRemoteChildIntoMergedNode(mergedNode, remoteParentNode,
+ remoteChildNode) {
+ if (this.mergedTree.allGuids.has(remoteChildNode.guid)) {
+ BookmarkBufferLog.trace("Remote child ${remoteChildNode} already " +
+ "seen in another folder and merged",
+ { remoteChildNode });
+ return false;
+ }
+
+ BookmarkBufferLog.trace("Merging remote child ${remoteChildNode} of " +
+ "${remoteParentNode} into ${mergedNode}",
+ { remoteChildNode, remoteParentNode,
+ mergedNode });
+
+ // Make sure the remote child isn't locally deleted. If it is, we need
+ // to move all descendants that aren't also remotely deleted to the
+ // merged node. This handles the case where a user deletes a folder
+ // on this device, and adds a bookmark to the same folder on another
+ // device. We want to keep the folder deleted, but we also don't want
+ // to lose the new bookmark, so we move the bookmark to the deleted
+ // folder's parent.
+ let locallyDeleted = await this.checkForLocalDeletionOfRemoteNode(
+ mergedNode, remoteChildNode);
+ if (locallyDeleted) {
+ return true;
+ }
+
+ // The remote child isn't locally deleted. Does it exist in the local tree?
+ let localChildNode = this.localTree.getByGuid(remoteChildNode.guid);
+ if (!localChildNode) {
+ // Remote child doesn't exist locally, either. Try to find a content
+ // match in the containing folder, and dedupe the local item if we can.
+ BookmarkBufferLog.trace("${remoteChildNode} doesn't exist locally; " +
+ "looking for content match", { remoteChildNode });
+
+ let localChildNodeByContent = await this.findLocalNodeMatchingRemoteNode(
+ mergedNode, remoteChildNode);
+
+ let mergedChildNode = await this.mergeNode(remoteChildNode.guid,
+ localChildNodeByContent,
+ remoteChildNode);
+ mergedNode.mergedChildren.push(mergedChildNode);
+ return false;
+ }
+
+ // Otherwise, the remote child exists in the local tree. Did it move?
+ let localParentNode = this.localTree.getParent(localChildNode.guid);
+ if (!localParentNode) {
+ // Should never happen. The local tree must be complete.
+ throw new BookmarkConsistencyError(`Local tree missing parent ` +
+ `for ${localChildNode}`);
+ }
+
+ if (localParentNode.guid == mergedNode.guid) {
+ // Remote child didn't move locally, so merge now.
+ BookmarkBufferLog.trace("${localChildNode} not moved from " +
+ "${localParentNode}", { localChildNode,
+ localParentNode });
+ let mergedChildNode = await this.mergeNode(remoteChildNode.guid,
+ localChildNode,
+ remoteChildNode);
+ mergedNode.mergedChildren.push(mergedChildNode);
+ return false;
+ }
+
+ BookmarkBufferLog.trace("${remoteChildNode} exists locally in " +
+ "${localParentNode} and remotely in " +
+ "${remoteParentNode}", { remoteChildNode,
+ localParentNode,
+ remoteParentNode });
+
+ // Remote child was moved into different folders locally and remotely. Use
+ // the modification times to decide where to keep the child.
+ let latestLocalAge = Math.min(localChildNode.age,
+ localParentNode.age);
+ let latestRemoteAge = Math.min(remoteChildNode.age,
+ remoteParentNode.age);
+
+ if (latestLocalAge < latestRemoteAge) {
+ // Local move is younger, so we ignore the remote move. We'll
+ // merge the child later, when we walk its new local parent.
+ BookmarkBufferLog.trace("Ignoring remote move for " +
+ "${remoteChildNode} to ${remoteParentNode}; " +
+ "local move to ${localParentNode} is newer",
+ { remoteChildNode, remoteParentNode,
+ localParentNode });
+ return true;
+ }
+
+ // Otherwise, the remote move is younger, so we ignore the local move
+ // and merge the child now.
+ BookmarkBufferLog.trace("Taking remote move for ${remoteChildNode} " +
+ "to ${remoteParentNode}; local move to " +
+ "${localParentNode} is older",
+ { remoteChildNode, remoteParentNode,
+ localParentNode });
+
+ let mergedChildNode = await this.mergeNode(remoteChildNode.guid,
+ localChildNode,
+ remoteChildNode);
+ mergedNode.mergedChildren.push(mergedChildNode);
+ return false;
+ }
+
+ /**
+ * Merges a local child node into a merged folder node.
+ *
+ * @param {MergedBookmarkNode} mergedNode
+ * The merged folder node.
+ * @param {BookmarkNode} localParentNode
+ * The local folder node.
+ * @param {BookmarkNode} localChildNode
+ * The local child node.
+ * @returns {Boolean}
+ * `true` if the child doesn't exist remotely or was locally moved;
+ * `false` otherwise.
+ */
+ async mergeLocalChildIntoMergedNode(mergedNode, localParentNode, localChildNode) {
+ if (this.mergedTree.allGuids.has(localChildNode.guid)) {
+ // We already merged the child when we walked another folder.
+ BookmarkBufferLog.trace("Local child ${localChildNode} already " +
+ "seen in another folder and merged",
+ { localChildNode });
+ return false;
+ }
+
+ BookmarkBufferLog.trace("Merging local child ${localChildNode} into " +
+ "${mergedNode}", { localChildNode, mergedNode });
+
+ // Now, we know we haven't seen the local child before, and it's not in
+ // this folder on the server. Check if the child is remotely deleted.
+ // If so, we need to move any new local descendants to the merged node,
+ // just as we did for new remote descendants of locally deleted parents.
+ let remotelyDeleted = await this.checkForRemoteDeletionOfLocalNode(
+ mergedNode, localChildNode);
+ if (remotelyDeleted) {
+ return false;
+ }
+
+ // At this point, we know the local child isn't deleted. See if it
+ // exists in the remote tree.
+ let remoteChildNode = this.remoteTree.getByGuid(localChildNode.guid);
+ if (!remoteChildNode) {
+ // The local child doesn't exist remotely, but we still need to walk
+ // its children.
+ let mergedChildNode = await this.mergeNode(localChildNode.guid,
+ localChildNode,
+ null);
+ mergedNode.mergedChildren.push(mergedChildNode);
+ return true;
+ }
+
+ // The local child exists remotely. It must have moved; otherwise, we
+ // would have seen it when we walked the remote children.
+ let remoteParentNode = this.remoteTree.getParent(remoteChildNode.guid);
+ if (!remoteParentNode) {
+ // If the new remote parent is a virtual folder, the child must be
+ // an orphan. Merge now.
+ let mergedChildNode = await this.mergeNode(localChildNode.guid,
+ localChildNode,
+ remoteChildNode);
+ mergedNode.mergedChildren.push(mergedChildNode);
+ return true;
+ }
+
+ if (remoteParentNode.guid == mergedNode.guid) {
+ // Should never happen. If the local child didn't move, we would
+ // have seen it when we walked the remote children.
+ throw new BookmarkConsistencyError(`Remote node ${remoteChildNode} ` +
+ `didn't move from ` +
+ remoteParentNode);
+ }
+
+ let latestLocalAge = Math.min(localChildNode.age, localParentNode.age);
+ let latestRemoteAge = Math.min(remoteChildNode.age, remoteParentNode.age);
+
+ if (latestRemoteAge < latestLocalAge) {
+ // Remote move is younger.
+ return false;
+ }
+
+ BookmarkBufferLog.trace("Local move for ${localChildNode} is " +
+ "younger; ignoring remote move",
+ { localChildNode });
+
+ let mergedChildNode = await this.mergeNode(localChildNode.guid,
+ localChildNode,
+ remoteChildNode);
+ mergedNode.mergedChildren.push(mergedChildNode);
+ return true;
+ }
+
+ /**
+ * Recursively merges the children of a local folder node and a matching
+ * remote folder node.
+ *
+ * @param {MergedBookmarkNode} mergedNode
+ * The merged folder state. This method mutates the merged node to
+ * append merged children, and change the node's merge state to
+ * "new" if needed.
+ * @param {BookmarkNode?} localNode
+ * The local folder node. May be `null` if the folder only exists
+ * remotely.
+ * @param {BookmarkNode?} remoteNode
+ * The remote folder node. May be `null` if the folder only exists
+ * locally.
+ */
+ async mergeChildListsIntoMergedNode(mergedNode, localNode, remoteNode) {
+ let seenInRemoteFolder = new Set();
+ let mergeStateChanged = false;
+
+ BookmarkBufferLog.trace("Merging remote children for folders " +
+ "${localNode} and ${remoteNode} into ${mergedNode}",
+ { localNode, remoteNode, mergedNode });
+
+ // Walk and merge remote children first.
+ if (remoteNode) {
+ for (let remoteChildNode of remoteNode.children) {
+ seenInRemoteFolder.add(remoteChildNode.guid);
+
+ let remoteChildrenChanged = await this.mergeRemoteChildIntoMergedNode(
+ mergedNode, remoteNode, remoteChildNode);
+ if (remoteChildrenChanged) {
+ mergeStateChanged = true;
+ }
+ }
+ }
+
+ BookmarkBufferLog.trace("Merging local children for folders " +
+ "${localNode} and ${remoteNode} into ${mergedNode}",
+ { localNode, remoteNode, mergedNode });
+
+ // Now walk and merge any local children that we haven't already merged.
+ if (localNode) {
+ for (let localChildNode of localNode.children) {
+ if (seenInRemoteFolder.has(localChildNode.guid)) {
+ // We already merged the child when we walked the remote children of
+ // this folder.
+ continue;
+ }
+
+ let remoteChildrenChanged = await this.mergeLocalChildIntoMergedNode(
+ mergedNode, localNode, localChildNode);
+ if (remoteChildrenChanged) {
+ mergeStateChanged = true;
+ }
+ }
+ }
+
+ let childrenReordered = mergedNode.orderChildren();
+ if (childrenReordered) {
+ mergeStateChanged = true;
+ }
+
+ // Update the merge state if we moved children orphaned on one side by a
+ // deletion on the other side, if we kept newer locally moved children,
+ // or if the child order changed. We already updated the merge state of the
+ // orphans, but we also need to flag the containing folder so that it's
+ // reuploaded to the server along with the new children.
+ if (mergeStateChanged) {
+ let newNode = mergedNode.toBookmarkNode();
+ mergedNode.mergeState = BookmarkMergeState.new(newNode);
+ }
+ }
+
+ /**
+ * Walks a locally deleted remote node's children, reparenting any children
+ * that aren't also deleted remotely to the merged node. Returns `true` if
+ * `remoteNode` is deleted locally; `false` if `remoteNode` is not deleted or
+ * doesn't exist locally.
+ *
+ * This is the inverse of `checkForRemoteDeletionOfLocalNode`.
+ */
+ async checkForLocalDeletionOfRemoteNode(mergedNode, remoteNode) {
+ if (!this.localTree.isDeleted(remoteNode.guid)) {
+ return false;
+ }
+
+ BookmarkBufferLog.trace("${remoteNode} deleted locally", { remoteNode });
+ this.mergedTree.deleteRemotely.add(remoteNode.guid);
+
+ let mergedOrphanNodes = await this.processRemoteOrphansForNode(mergedNode,
+ remoteNode);
+ this.relocateOrphansTo(mergedNode, mergedOrphanNodes);
+
+ return true;
+ }
+
+ /**
+ * Walks a remotely deleted local node's children, reparenting any children
+ * that aren't also deleted locally to the merged node. Returns `true` if
+ * `localNode` is deleted remotely; `false` if `localNode` is not deleted or
+ * doesn't exist locally.
+ *
+ * This is the inverse of `checkForLocalDeletionOfRemoteNode`.
+ */
+ async checkForRemoteDeletionOfLocalNode(mergedNode, localNode) {
+ if (!this.remoteTree.isDeleted(localNode.guid)) {
+ return false;
+ }
+
+ BookmarkBufferLog.trace("${localNode} deleted remotely", { localNode });
+ this.mergedTree.deleteLocally.add(localNode.guid);
+
+ let mergedOrphanNodes = await this.processLocalOrphansForNode(mergedNode,
+ localNode);
+ this.relocateOrphansTo(mergedNode, mergedOrphanNodes);
+
+ return true;
+ }
+
+ /**
+ * Recursively merges all remote children of a locally deleted folder that
+ * haven't also been deleted remotely. This can happen if the user adds a
+ * bookmark to a folder on another device, and deletes that folder locally.
+ * This is the inverse of `processLocalOrphansForNode`.
+ */
+ async processRemoteOrphansForNode(mergedNode, remoteNode) {
+ let remoteOrphanNodes = [];
+
+ for (let remoteChildNode of remoteNode.children) {
+ let locallyDeleted = await this.checkForLocalDeletionOfRemoteNode(
+ mergedNode, remoteChildNode);
+ if (locallyDeleted) {
+ // The remote child doesn't exist locally, or is also deleted locally,
+ // so we can safely delete its parent.
+ continue;
+ }
+ remoteOrphanNodes.push(remoteChildNode);
+ }
+
+ let mergedOrphanNodes = [];
+ for (let remoteOrphanNode of remoteOrphanNodes) {
+ let localOrphanNode = this.localTree.getByGuid(remoteOrphanNode.guid);
+ let mergedOrphanNode = await this.mergeNode(remoteOrphanNode.guid,
+ localOrphanNode,
+ remoteOrphanNode);
+ mergedOrphanNodes.push(mergedOrphanNode);
+ }
+
+ return mergedOrphanNodes;
+ }
+
+ /**
+ * Recursively merges all local children of a remotely deleted folder that
+ * haven't also been deleted locally. This is the inverse of
+ * `processRemoteOrphansForNode`.
+ */
+ async processLocalOrphansForNode(mergedNode, localNode) {
+ if (!localNode.isFolder()) {
+ // The local node isn't a folder, so it won't have orphans.
+ return [];
+ }
+
+ let localOrphanNodes = [];
+ for (let localChildNode of localNode.children) {
+ let remotelyDeleted = await this.checkForRemoteDeletionOfLocalNode(mergedNode, localChildNode);
+ if (remotelyDeleted) {
+ // The local child doesn't exist or is also deleted on the server, so we
+ // can safely delete its parent without orphaning any local children.
+ continue;
+ }
+ localOrphanNodes.push(localChildNode);
+ }
+
+ let mergedOrphanNodes = [];
+ for (let localOrphanNode of localOrphanNodes) {
+ let remoteOrphanNode = this.remoteTree.getByGuid(localOrphanNode.guid);
+ let mergedNode = await this.mergeNode(localOrphanNode.guid, localOrphanNode, remoteOrphanNode);
+ mergedOrphanNodes.push(mergedNode);
+ }
+
+ return mergedOrphanNodes;
+ }
+
+ /**
+ * Moves a list of merged orphan nodes to the closest surviving ancestor.
+ * Changes the merge state of the moved orphans to "new", so that we
+ * reupload them along with their new parent on the next sync.
+ *
+ * @param {MergedBookmarkNode} mergedNode
+ * @param {Array[MergedBookmarkNode]} mergedOrphanNodes
+ */
+ relocateOrphansTo(mergedNode, mergedOrphanNodes) {
+ for (let mergedOrphanNode of mergedOrphanNodes) {
+ let newNode = mergedOrphanNode.toBookmarkNode();
+ mergedOrphanNode.mergeState = BookmarkMergeState.new(newNode);
+ mergedNode.mergedChildren.push(mergedOrphanNode);
+ }
+ }
+
+ /**
+ * Finds a local node with a different GUID that matches the content of a
+ * remote node. This is used to dedupe local items that haven't been uploaded
+ * to remote items that don't exist locally.
+ *
+ * @param {MergedBookmarkNode} mergedNode
+ * The merged folder node.
+ * @param {BookmarkNode} remoteChildNode
+ * The remote child node.
+ * @returns {BookmarkNode?}
+ * A matching local child node, or `null` if there are no matching
+ * local items.
+ */
+ async findLocalNodeMatchingRemoteNode(mergedNode, remoteChildNode) {
+ let localParentNode = mergedNode.localNode;
+ if (!localParentNode) {
+ BookmarkBufferLog.trace("Merged node ${mergedNode} doesn't exist " +
+ "locally; no potential dupes for " +
+ "${remoteChildNode}", { mergedNode,
+ remoteChildNode });
+ return null;
+ }
+ if (remoteChildNode.isVirtual()) {
+ return null;
+ }
+
+ let localCandidateNodes = [];
+ for (let localCandidate of localParentNode.children) {
+ if (this.mergedTree.allGuids.has(localCandidate.guid)) {
+ BookmarkBufferLog.trace("Not deduping ${localCandidate}; already " +
+ "seen in another folder", { localCandidate });
+ continue;
+ }
+ if (!localCandidate.canDupe()) {
+ BookmarkBufferLog.trace("Not deduping ${localCandidate}; already " +
+ "uploaded", { localCandidate });
+ continue;
+ }
+ let remoteCandidate = this.remoteTree.getByGuid(localCandidate.guid);
+ if (remoteCandidate) {
+ BookmarkBufferLog.trace("Not deduping ${localCandidate}; already " +
+ "exists remotely", { localCandidate });
+ continue;
+ }
+ if (this.remoteTree.isDeleted(localCandidate.guid)) {
+ BookmarkBufferLog.trace("Not deduping ${localCandidate}; deleted on " +
+ "server", { localCandidate });
+ continue;
+ }
+ let location = this.localTree.getLocation(localCandidate.guid);
+ let candidate = { location, node: localCandidate };
+ localCandidateNodes.push(candidate);
+ }
+
+ if (!localCandidateNodes.length) {
+ BookmarkBufferLog.trace("No potential dupes for ${remoteChildNode} in " +
+ "${localParentNode}", { remoteChildNode,
+ localParentNode });
+ return null;
+ }
+
+ BookmarkBufferLog.trace("Found potential dupes for ${remoteChildNode} in " +
+ "${localParentNode}: ${localCandidateNodes}",
+ { remoteChildNode, localParentNode,
+ localCandidateNodes });
+
+ let remoteLocation = this.remoteTree.getLocation(remoteChildNode.guid);
+ let remoteContent = await this.storage.fetchRemoteContent(
+ remoteChildNode.guid);
+ let dupeGuid = await this.storage.findLocalDupeGuid(localCandidateNodes,
+ remoteLocation,
+ remoteContent);
+ if (!dupeGuid) {
+ BookmarkBufferLog.trace("No matching dupes for ${remoteChildNode} in " +
+ "${localParentNode}", { remoteChildNode,
+ localParentNode });
+ return null;
+ }
+
+ let newLocalNode = this.localTree.getByGuid(dupeGuid);
+ if (!newLocalNode) {
+ // Should never happen. `findLocalDupeGuid` returns existing nodes.
+ throw new BookmarkConsistencyError(`Local dupe ${dupeGuid} doesn't ` +
+ `exist in local tree`);
+ }
+
+ BookmarkBufferLog.trace("Deduping ${newLocalNode} to ${remoteChildNode}",
+ { newLocalNode, remoteChildNode });
+ return newLocalNode;
+ }
+}
+
+class BookmarkContent {
+ constructor(kind, dateAdded, title, url, keyword, description, loadInSidebar,
+ smartBookmarkName, tagFolderName, feedURL, siteURL) {
+ this.kind = kind;
+ this.dateAdded = dateAdded > 0 ? new Date(dateAdded) : new Date();
+ this.title = title;
+ this.url = url ? new URL(url) : null;
+ this.keyword = keyword;
+ this.description = description;
+ this.loadInSidebar = loadInSidebar;
+ this.smartBookmarkName = smartBookmarkName;
+ this.tagFolderName = tagFolderName;
+ this.feedURL = feedURL;
+ this.siteURL = siteURL;
+ }
+
+ static fromRow(row) {
+ let kind = row.getResultByName("kind");
+ let dateAdded = row.getResultByName("dateAdded");
+ let title = row.getResultByName("title");
+ let url = row.getResultByName("url");
+ let keyword = row.getResultByName("keyword");
+ let description = row.getResultByName("description");
+ let loadInSidebar = row.getResultByName("loadInSidebar");
+ let smartBookmarkName = row.getResultByName("smartBookmarkName");
+ let tagFolderName = row.getResultByName("tagFolderName");
+ let feedURL = row.getResultByName("feedURL");
+ let siteURL = row.getResultByName("siteURL");
+ return new BookmarkContent(kind, dateAdded, title, url, keyword,
+ description, loadInSidebar, smartBookmarkName,
+ tagFolderName, feedURL, siteURL);
+ }
+
+ getTagQueryParams() {
+ if (this.kind != KIND_QUERY || !this.tagFolderName || !this.url) {
+ return null;
+ }
+ if (this.url.protocol != "place:") {
+ return null;
+ }
+ let params = new URLSearchParams(this.url.pathname);
+ let type = +params.get("type");
+ if (type != Ci.nsINavHistoryQueryOptions.RESULTS_AS_TAG_CONTENTS) {
+ return null;
+ }
+ return params;
+ }
+
+ getPlacesType() {
+ switch (this.kind) {
+ case KIND_BOOKMARK:
+ case KIND_QUERY:
+ return PlacesUtils.bookmarks.TYPE_BOOKMARK;
+
+ case KIND_FOLDER:
+ case KIND_LIVEMARK:
+ return PlacesUtils.bookmarks.TYPE_FOLDER;
+
+ case KIND_SEPARATOR:
+ return PlacesUtils.bookmarks.TYPE_SEPARATOR;
+ }
+ throw new TypeError(`Unknown bookmark kind: ${this.kind}`);
+ }
+
+ // Notes the description, load in sidebar, smart bookmark name, livemark feed
+ // URL, and site URL to set on the item. Not all annotations apply to all
+ // types, but we validated this when we inserted the item into the buffer.
+ getAnnoInfos() {
+ return [{
+ name: PlacesSyncUtils.bookmarks.DESCRIPTION_ANNO,
+ type: PlacesUtils.annotations.TYPE_STRING,
+ value: this.description,
+ }, {
+ name: PlacesSyncUtils.bookmarks.SIDEBAR_ANNO,
+ type: PlacesUtils.annotations.TYPE_INT32,
+ value: this.loadInSidebar,
+ }, {
+ name: PlacesSyncUtils.bookmarks.SMART_BOOKMARKS_ANNO,
+ type: PlacesUtils.annotations.TYPE_STRING,
+ value: this.smartBookmarkName,
+ }, {
+ name: PlacesUtils.LMANNO_FEEDURI,
+ type: PlacesUtils.annotations.TYPE_STRING,
+ value: this.feedURL,
+ }, {
+ name: PlacesUtils.LMANNO_SITEURI,
+ type: PlacesUtils.annotations.TYPE_STRING,
+ value: this.siteURL,
+ }];
+ }
+
+ toJSON() {
+ // TODO(kitcambridge): More specific representations for each kind.
+ return {
+ kind: this.kind,
+ title: this.title,
+ tagFolderName: this.tagFolderName,
+ url: this.url ? this.url.href : null,
+ description: this.description,
+ loadInSidebar: this.loadInSidebar,
+ smartBookmarkName: this.smartBookmarkName,
+ feedURL: this.feedURL,
+ siteURL: this.siteURL,
+ dateAdded: this.dateAdded,
+ };
+ }
+}
+
+class BookmarkStorage {
+ constructor(db) {
+ this.db = db;
+ }
+
+ /**
+ * Builds a fully rooted, consistent tree from the items and tombstones in
+ * Places. We include non-syncable items because they might already exist on
+ * the server, even though we'll never reupload them.
+ */
+ async fetchLocalTree() {
+ let localTree = BookmarkTree.rooted();
+
+ // This unsightly query collects all descendants and maps their Places types
+ // to the Sync record kinds. We start with the roots, and work our way down.
+ let nodeRows = await this.db.execute(`
+ WITH RECURSIVE
+ syncedItems(id, level) AS (
+ SELECT b.id, 0 AS level FROM moz_bookmarks b
+ WHERE b.guid = :rootGuid
+ UNION ALL
+ SELECT b.id, s.level + 1 AS level FROM moz_bookmarks b
+ JOIN syncedItems s ON s.id = b.parent
+ )
+ SELECT b.id, b.guid, p.guid AS parentGuid, (CASE b.type
+ /* Map Places item types to Sync record kinds. */
+ WHEN :bookmarkType THEN (
+ CASE WHEN EXISTS(
+ /* Queries are bookmarks with a smart bookmark annotation. */
+ SELECT 1 FROM moz_items_annos a
+ JOIN moz_anno_attributes n ON n.id = a.anno_attribute_id
+ WHERE a.item_id = b.id AND
+ n.name = :smartBookmarkAnno
+ )
+ THEN :queryKind
+ ELSE :bookmarkKind
+ END
+ )
+ WHEN :folderType THEN (
+ CASE WHEN EXISTS(
+ /* Livemarks are folders with a site URL annotation. */
+ SELECT 1 FROM moz_items_annos a
+ JOIN moz_anno_attributes n ON n.id = a.anno_attribute_id
+ WHERE a.item_id = b.id AND
+ n.name = :livemarkAnno
+ )
+ THEN :livemarkKind
+ ELSE :folderKind
+ END
+ )
+ WHEN :separatorType THEN :separatorKind
+ ELSE :virtualItemKind
+ END
+ ) AS kind, b.lastModified, b.syncChangeCounter, b.syncStatus, (
+ SELECT a.content FROM moz_items_annos a
+ JOIN moz_anno_attributes n ON n.id = a.anno_attribute_id
+ WHERE a.item_id = b.id AND
+ n.name = :orphanAnno) AS expectedParentGuid
+ FROM moz_bookmarks b
+ JOIN moz_bookmarks p ON p.id = b.parent
+ JOIN syncedItems s ON s.id = b.id
+ ORDER BY s.level, b.parent, b.position`,
+ { rootGuid: PlacesUtils.bookmarks.rootGuid,
+ bookmarkType: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+ smartBookmarkAnno: PlacesSyncUtils.bookmarks.SMART_BOOKMARKS_ANNO,
+ queryKind: KIND_QUERY,
+ bookmarkKind: KIND_BOOKMARK,
+ folderType: PlacesUtils.bookmarks.TYPE_FOLDER,
+ livemarkAnno: PlacesUtils.LMANNO_FEEDURI,
+ livemarkKind: KIND_LIVEMARK,
+ folderKind: KIND_FOLDER,
+ separatorType: PlacesUtils.bookmarks.TYPE_SEPARATOR,
+ separatorKind: KIND_SEPARATOR,
+ virtualItemKind: KIND_VIRTUAL_ITEM,
+ orphanAnno: PlacesSyncUtils.bookmarks.SYNC_PARENT_ANNO });
+
+ for (let row of nodeRows) {
+ let parentGuid = row.getResultByName("parentGuid");
+ let node = BookmarkNode.fromLocalRow(row);
+ localTree.insert(parentGuid, node);
+
+ let expectedParentGuid = row.getResultByName("expectedParentGuid");
+ if (expectedParentGuid) {
+ // TODO(kitcambridge): Handle orphans when merging, then remove annos
+ // from merged orphans when applying.
+ localTree.noteOrphan(node.guid, expectedParentGuid);
+ }
+ }
+
+ // Note tombstones for locally deleted items.
+ let tombstoneRows = await this.db.execute(`
+ SELECT guid FROM moz_bookmarks_deleted`);
+
+ for (let row of tombstoneRows) {
+ let guid = row.getResultByName("guid");
+ localTree.noteDeleted(guid);
+ }
+
+ return localTree;
+ }
+
+ /**
+ * Builds a tree from the items in the incoming buffer. We start at the tops,
+ * which exist in `value` but not `structure`, and work our way down. Parents
+ * precede children, and children are ordered by their positions relative to
+ * their siblings. It's expected that the buffer doesn't contain a fully
+ * rooted tree.
+ *
+ * All rows in `structure` should have corresponding rows in `value`, but rows
+ * in `value` might not exist in `structure`. It's easier to explain with some
+ * examples:
+ *
+ * - Reordering the children in a folder A uploads A, but not its parent or
+ * children. A appears in `value` only, and A's children appear in
+ * `structure` only.
+ * - Moving an item B from folder C to folder D uploads B, C, and D, but not
+ * C's parent, D's parent, or any of B's siblings. B, C and D appear in
+ * `value`. C and D's children, including B, appear in `value` and
+ * `structure`.
+ * - Renaming a non-folder item E only uploads E, not its parent. E appears
+ * in `value` only.
+ * - Renaming a folder G only uploads G. G appears in `value` only. However,
+ * since folders also carry their children, G's children appear in
+ * `structure` only.
+ *
+ * We represent roots and missing parents as virtual folders, and missing
+ * children of known folders as virtual items. During merging, we use the
+ * local tree to supply the missing content. If the node doesn't exist
+ * locally, either, the item is likely an orphan created by a partial upload.
+ */
+ async fetchRemoteTree() {
+ // Check the buffer to make sure we can build a tree.
+ await this.validateBuffer();
+
+ let remoteTree = new BookmarkTree();
+
+ let rootRows = await this.db.execute(`
+ WITH
+ localStructure(guid, parentGuid) AS (
+ SELECT b.guid, p.guid
+ FROM moz_bookmarks b
+ JOIN moz_bookmarks p ON p.id = b.parent
+ UNION ALL
+ SELECT guid, parentGuid
+ FROM moz_bookmarks_deleted
+ ),
+ tops(guid, parentGuid) AS (
+ /* Remote tops don't have structure. They might represent value-only
+ changes, in which case they exist locally, or partial uploads. For
+ partial uploads, we fall back to the top's expected parent, and
+ "unfiled" if the expected parent doesn't exist locally, either. */
+ SELECT v.guid, COALESCE(lt.parentGuid, lep.guid, :unfiledGuid)
+ FROM value v
+ LEFT JOIN structure s ON s.guid = v.guid
+ LEFT JOIN localStructure lt ON lt.guid = v.guid
+ LEFT JOIN localStructure lep ON lep.guid = v.expectedParentGuid
+ WHERE s.guid IS NULL
+ )
+ /* Exclude parents with remote structure, since they're not tops:
+ we'll see them when we walk remote children. */
+ SELECT t.guid AS guid, t.parentGuid AS parentGuid
+ FROM tops t
+ LEFT JOIN structure s ON s.guid = t.parentGuid
+ WHERE s.guid IS NULL`,
+ { unfiledGuid: PlacesUtils.bookmarks.unfiledGuid });
+
+ for (let row of rootRows) {
+ let guid = row.getResultByName("guid");
+ let parentGuid = row.getResultByName("parentGuid");
+
+ BookmarkBufferLog.trace("Remote top ${guid} has parent ${parentGuid}",
+ { guid, parentGuid });
+
+ if (!remoteTree.has(parentGuid)) {
+ let virtualParentNode = BookmarkNode.virtualFolder(parentGuid);
+ remoteTree.insertRoot(virtualParentNode);
+ }
+
+ await this.insertNodeIntoRemoteTree(remoteTree, parentGuid, guid);
+ }
+
+ // Note tombstones for remotely deleted items.
+ let tombstoneRows = await this.db.execute(`
+ SELECT guid FROM tombstones`);
+
+ for (let row of tombstoneRows) {
+ let guid = row.getResultByName("guid");
+ remoteTree.noteDeleted(guid);
+ }
+
+ return remoteTree;
+ }
+
+ async insertNodeIntoRemoteTree(remoteTree, parentGuid, guid) {
+ let nodeRows = await this.db.executeCached(`
+ SELECT guid, age, kind FROM value
+ WHERE guid = :guid`,
+ { guid });
+
+ if (nodeRows.length) {
+ // The node has content info. Insert it into the remote tree, and
+ // recursively walk its children if it's a folder.
+ let node = BookmarkNode.fromRemoteRow(nodeRows[0]);
+ remoteTree.insert(parentGuid, node);
+
+ if (node.isFolder()) {
+ let childRows = await this.fetchRemoteChildRows(node.guid);
+ for (let row of childRows) {
+ let childGuid = row.getResultByName("guid");
+ await this.insertNodeIntoRemoteTree(remoteTree, node.guid, childGuid);
+ }
+ }
+
+ return;
+ }
+
+ // No content info, so either a virtual folder or virtual item.
+ let childRows = await this.fetchRemoteChildRows(guid);
+ if (childRows.length) {
+ // The node has children, so insert a virtual folder and walk the
+ // children.
+ let virtualFolderNode = BookmarkNode.virtualFolder(guid);
+ remoteTree.insert(parentGuid, virtualFolderNode);
+
+ for (let row of childRows) {
+ let childGuid = row.getResultByName("guid");
+ await this.insertNodeIntoRemoteTree(remoteTree, virtualFolderNode.guid,
+ childGuid);
+ }
+
+ return;
+ }
+
+ // No children, either, so it's a generic virtual item. It might still be
+ // a folder locally; we just don't know anything about it remotely.
+ let virtualItemNode = BookmarkNode.virtualItem(guid);
+ remoteTree.insert(parentGuid, virtualItemNode);
+ }
+
+ async fetchRemoteChildRows(folderGuid) {
+ // Return children in order. `position = -1` orders children with unknown
+ // positions last.
+ let childRows = await this.db.executeCached(`
+ SELECT guid FROM structure
+ WHERE parentGuid = :folderGuid
+ ORDER BY position`,
+ { folderGuid });
+ return childRows;
+ }
+
+ async findLocalDupeGuid(localCandidateNodes, remoteLocation, remoteContent) {
+ for (let { location: localLocation, node } of localCandidateNodes) {
+ if (node.kind != remoteContent.kind) {
+ continue;
+ }
+ switch (node.kind) {
+ case KIND_BOOKMARK: {
+ let localRows = await this.db.executeCached(`
+ SELECT IFNULL(b.title, "") AS title, h.url
+ FROM moz_bookmarks b
+ JOIN moz_places h ON h.id = b.fk
+ WHERE b.guid = :guid AND
+ b.type = :bookmarkType`,
+ { guid: node.guid,
+ bookmarkType: PlacesUtils.bookmarks.TYPE_BOOKMARK });
+ if (!localRows.length) {
+ // Should never happen.
+ throw new BookmarkConsistencyError(`Local candidate bookmark ` +
+ `${node} doesn't exist`);
+ }
+ let localRow = localRows[0];
+
+ let title = localRow.getResultByName("title");
+ let url = localRow.getResultByName("url");
+
+ if (title == remoteContent.title &&
+ url == remoteContent.url.href) {
+ return node.guid;
+ }
+ continue;
+ }
+
+ case KIND_QUERY: {
+ let localRows = await this.db.executeCached(`
+ SELECT a.content AS smartBookmarkName
+ FROM moz_items_annos a
+ JOIN moz_anno_attributes n ON n.id = a.anno_attribute_id
+ JOIN moz_bookmarks b ON b.id = a.item_id
+ WHERE b.guid = :guid AND
+ b.type = :bookmarkType AND
+ n.name = :smartBookmarkAnno`,
+ { guid: node.guid,
+ bookmarkType: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+ smartBookmarkAnno: PlacesSyncUtils.bookmarks.SMART_BOOKMARKS_ANNO });
+ if (!localRows.length) {
+ // Should never happen.
+ throw new BookmarkConsistencyError(`Local candidate query ` +
+ `${node} doesn't exist`);
+ }
+ let localRow = localRows[0];
+ let smartBookmarkName = localRow.getResultByName("smartBookmarkName");
+ if (smartBookmarkName == remoteContent.smartBookmarkName) {
+ return node.guid;
+ }
+ continue;
+ }
+
+ case KIND_FOLDER:
+ case KIND_LIVEMARK: {
+ let localRows = await this.db.executeCached(`
+ SELECT IFNULL(b.title, "") AS title
+ FROM moz_bookmarks b
+ WHERE b.guid = :guid AND
+ b.type = :folderType`,
+ { guid: node.guid,
+ folderType: PlacesUtils.bookmarks.TYPE_FOLDER });
+ if (!localRows.length) {
+ // Should never happen.
+ throw new BookmarkConsistencyError(`Local candidate folder ` +
+ `${node} doesn't exist`);
+ }
+ let localRow = localRows[0];
+ let title = localRow.getResultByName("title");
+ if (title == remoteContent.title) {
+ return node.guid;
+ }
+ continue;
+ }
+
+ case KIND_SEPARATOR:
+ if (localLocation.hasSamePosition(remoteLocation)) {
+ return node.guid;
+ }
+ continue;
+
+ default:
+ throw new TypeError(`Unknown candidate kind: ${node.kind}`);
+ }
+ }
+ return null;
+ }
+
+ async fetchRemoteContent(guid) {
+ let rows = await this.db.executeCached(`
+ SELECT kind, dateAdded, IFNULL(title, "") AS title, url, keyword,
+ description, IFNULL(loadInSidebar, 0) AS loadInSidebar,
+ smartBookmarkName, tagFolderName, feedURL, siteURL
+ FROM value
+ WHERE guid = :guid`,
+ { guid });
+ if (!rows.length) {
+ throw new BookmarkConsistencyError(`Remote item ${guid} doesn't exist`);
+ }
+
+ return BookmarkContent.fromRow(rows[0]);
+ }
+
+ async fetchLocalKeywordsForURL(url) {
+ let rows = await this.db.executeCached(`
+ SELECT k.keyword
+ FROM moz_keywords k
+ JOIN moz_places h ON h.id = k.place_id
+ WHERE h.url_hash = :urlHash AND
+ h.url = :url`,
+ { urlHash: PlacesUtils.history.hashURL(url.href),
+ url: url.href });
+ return rows;
+ }
+
+ async fetchLocalURLsForKeyword(keyword) {
+ let rows = await this.db.executeCached(`
+ SELECT h.url
+ FROM moz_places h
+ JOIN moz_keywords k ON k.place_id = h.id
+ WHERE k.keyword = :keyword`,
+ { keyword });
+ return rows;
+ }
+
+ async insertLocalKeyword(url, keyword) {
+ await this.db.executeCached(`
+ INSERT INTO moz_keywords(keyword, place_id)
+ SELECT :keyword, id FROM moz_places
+ WHERE url_hash = :urlHash AND
+ url = :url`,
+ { keyword, urlHash: PlacesUtils.history.hashURL(url.href),
+ url: url.href });
+ }
+
+ async removeLocalKeyword(url, keyword) {
+ // Drop the keyword.
+ await this.db.executeCached(`
+ DELETE FROM moz_keywords WHERE keyword = :keyword`,
+ { keyword });
+
+ // Bump the change counter for the affected URLs.
+ await this.db.executeCached(`
+ UPDATE moz_bookmarks SET
+ syncChangeCounter = syncChangeCounter + 1
+ WHERE fk = (SELECT id FROM moz_places
+ WHERE url_hash = :urlHash AND
+ url = :url)`,
+ { urlHash: PlacesUtils.history.hashURL(url.href),
+ url: url.href });
+ }
+
+ async fetchLocalTagsForURL(url) {
+ let tagRows = await this.db.executeCached(`
+ SELECT b.guid AS tagGuid, p.title AS tagName
+ FROM moz_bookmarks b
+ JOIN moz_places h ON h.id = b.fk
+ JOIN moz_bookmarks p ON p.id = b.parent
+ JOIN moz_bookmarks g ON g.id = p.parent
+ WHERE g.guid = :tagsGuid AND
+ h.url_hash = :urlHash AND
+ h.url = :url`,
+ { tagsGuid: PlacesUtils.bookmarks.tagsGuid,
+ urlHash: PlacesUtils.history.hashURL(url.href),
+ url: url.href });
+ return tagRows;
+ }
+
+ async fetchRemoteTagsForURL(url) {
+ let tagRows = await this.db.executeCached(`
+ SELECT t.tag AS tagName FROM tags t
+ JOIN value c ON c.id = t.itemId
+ WHERE c.url = :url`,
+ { url: url.href });
+ return tagRows;
+ }
+
+ async getOrCreateTagFolder(tagName) {
+ let tagFolderRows = await this.db.executeCached(`
+ SELECT b.id, b.guid FROM moz_bookmarks b
+ JOIN moz_bookmarks p ON p.id = b.parent
+ WHERE p.guid = :tagsGuid AND
+ b.title = :tagName`,
+ { tagsGuid: PlacesUtils.bookmarks.tagsGuid,
+ tagName });
+ if (tagFolderRows.length) {
+ let id = tagFolderRows[0].getResultByName("id");
+ let guid = tagFolderRows[0].getResultByName("guid");
+ return { id, guid, created: false };
+ }
+ let guid = PlacesUtils.history.makeGuid();
+ await this.insert(guid, PlacesUtils.bookmarks.tagsGuid, -1,
+ PlacesUtils.bookmarks.TYPE_FOLDER,
+ tagName);
+ let id = await this.fetchItemId(guid);
+ return { id, guid, created: true };
+ }
+
+ // Rewrites tag queries to point to the local tag folder.
+ async maybeRewriteTagQuery(content) {
+ if (!content.url) {
+ return null;
+ }
+ let tagQueryParams = content.getTagQueryParams();
+ if (!tagQueryParams) {
+ return null;
+ }
+
+ let tagFolderInfo = await this.getOrCreateTagFolder(content.tagFolderName);
+ tagQueryParams.set("folder", tagFolderInfo.id);
+ content.url = new URL("place:" + tagFolderInfo.id);
+
+ return tagFolderInfo;
+ }
+
+ async maybeInsertPlace(url) {
+ await this.db.executeCached(`
+ INSERT OR IGNORE INTO moz_places(url, url_hash, rev_host, hidden,
+ frecency, guid)
+ SELECT :url, :urlHash, :revHost, 0, (CASE SUBSTR(:url, 1, 6)
+ WHEN 'place:' THEN 0
+ ELSE -1
+ END
+ ), IFNULL((SELECT guid FROM moz_places
+ WHERE url_hash = :urlHash AND
+ url = :url), :guid)`,
+ { url: url.href, urlHash: PlacesUtils.history.hashURL(url.href),
+ revHost: PlacesUtils.getReversedHost(url),
+ guid: PlacesUtils.history.makeGuid() });
+ }
+
+ async fetchLocalPlaceId(url) {
+ let placeIdRows = await this.db.executeCached(`
+ SELECT id FROM moz_places
+ WHERE url_hash = :urlHash AND
+ url = :url`,
+ { urlHash: PlacesUtils.history.hashURL(url.href),
+ url: url.href });
+ if (!placeIdRows.length) {
+ throw new TypeError(`Can't fetch ID for nonexistent Place ${url}`);
+ }
+ return placeIdRows[0].getResultByName("id");
+ }
+
+ async insert(guid, parentGuid, position, type, title = null, url = null,
+ dateAdded = new Date(), syncChangeCounter = 1,
+ syncStatus = PlacesUtils.bookmarks.SYNC_STATUS.NEW) {
+
+ await this.db.executeCached(`
+ INSERT INTO moz_bookmarks(guid, fk, type, parent, position,
+ title, dateAdded, lastModified,
+ syncChangeCounter, syncStatus)
+ VALUES(:guid, (CASE WHEN :url IS NULL
+ THEN NULL
+ ELSE (SELECT id FROM moz_places
+ WHERE url_hash = :urlHash AND
+ url = :url)
+ END),
+ :type, (SELECT id FROM moz_bookmarks
+ WHERE guid = :parentGuid),
+ (CASE :position
+ WHEN -1 THEN (SELECT COUNT(*) FROM moz_bookmarks b
+ JOIN moz_bookmarks p ON p.id = b.parent
+ WHERE p.guid = :parentGuid)
+ ELSE :position
+ END), NULLIF(:title, ""), :dateAdded, :lastModified,
+ :syncChangeCounter, :syncStatus)`,
+ { guid, urlHash: url ? PlacesUtils.history.hashURL(url.href) : null,
+ url: url ? url.href : null, type, parentGuid, position, title,
+ dateAdded: PlacesUtils.toPRTime(dateAdded),
+ lastModified: PlacesUtils.toPRTime(new Date()),
+ syncChangeCounter, syncStatus });
+ }
+
+ async update(guid, columnsToUpdate) {
+ let fragments = [];
+ let params = { guid };
+ for (let [name, column] of columnsToUpdate) {
+ fragments.push("fragment" in column ? column.fragment :
+ `${name} = :${name}`);
+ params[name] = column.value;
+ }
+
+ await this.db.executeCached(`
+ UPDATE moz_bookmarks SET
+ ${fragments.join(", ")}
+ WHERE guid = :guid`,
+ params);
+ }
+
+ async delete(guid) {
+ await this.db.executeCached(`
+ DELETE FROM moz_bookmarks
+ WHERE guid = :guid`,
+ { guid });
+ }
+
+ async setAnno(guid, info) {
+ await this.db.executeCached(`
+ INSERT OR IGNORE INTO moz_anno_attributes(name)
+ VALUES(:name)`,
+ { name: info.name });
+
+ let annoId = null;
+ let lastModified = PlacesUtils.toPRTime(new Date());
+ let dateAdded = lastModified;
+
+ let existingAnnoRows = await this.db.executeCached(`
+ SELECT a.id, a.dateAdded
+ FROM moz_items_annos a
+ JOIN moz_anno_attributes n ON n.id = a.anno_attribute_id
+ JOIN moz_bookmarks b ON b.id = a.item_id
+ WHERE b.guid = :guid AND
+ n.name = :name`,
+ { guid, name: info.name });
+
+ if (existingAnnoRows.length) {
+ annoId = existingAnnoRows[0].getResultByName("id");
+ dateAdded = existingAnnoRows[0].getResultByName("dateAdded");
+ }
+
+ await this.db.executeCached(`
+ INSERT OR REPLACE INTO moz_items_annos(id, item_id, anno_attribute_id,
+ content, flags, expiration,
+ type, dateAdded, lastModified)
+ VALUES(:annoId, (SELECT id FROM moz_bookmarks WHERE guid = :guid),
+ (SELECT id FROM moz_anno_attributes WHERE name = :name),
+ :value, 0, :expiration, :type, :dateAdded, :lastModified)`,
+ { annoId, guid, name: info.name, value: info.value,
+ expiration: PlacesUtils.annotations.EXPIRE_NEVER,
+ type: info.type, dateAdded, lastModified });
+ }
+
+ async removeAnno(guid, name) {
+ await this.db.executeCached(`
+ DELETE FROM moz_items_annos
+ WHERE anno_attribute_id = (SELECT name FROM moz_anno_attributes
+ WHERE name = :name) AND
+ item_id = (SELECT id FROM moz_bookmarks
+ WHERE guid = :guid)`,
+ { name, guid });
+ }
+
+ // Fetches info about an item to pass to the different
+ // `nsINavBookmarkObserver` methods.
+ async fetchItemObserverRow(guid) {
+ let rows = await this.db.executeCached(`
+ SELECT b.id, b.lastModified, b.type, p.id AS parentId,
+ b.guid, p.guid AS parentGuid, b.title, h.url, b.position,
+ b.dateAdded
+ FROM moz_bookmarks b
+ JOIN moz_bookmarks p ON p.id = b.parent
+ LEFT JOIN moz_places h ON h.id = b.fk
+ WHERE b.guid = :guid`,
+ { guid });
+ if (!rows.length) {
+ throw new TypeError(`Can't fetch info for nonexistent item ${guid}`);
+ }
+ return rows[0];
+ }
+
+ // Fetches the ID for a GUID, throwing if the GUID doesn't exist in Places.
+ // This reimplements `PlacesUtils.promiseItemId`, which we can't use because
+ // we're calling `fetchItemId` within a transaction.
+ async fetchItemId(guid) {
+ let itemIdRows = await this.db.executeCached(`
+ SELECT id FROM moz_bookmarks
+ WHERE guid = :guid`,
+ { guid });
+ if (!itemIdRows.length) {
+ throw new TypeError(`Can't fetch ID for nonexistent item ${guid}`);
+ }
+ return itemIdRows[0].getResultByName("id");
+ }
+
+ async fetchItemsByURL(url) {
+ let itemRows = await this.db.executeCached(`
+ SELECT b.id, b.lastModified, b.type, p.id AS parentId,
+ b.guid, p.guid AS parentGuid
+ FROM moz_bookmarks b
+ JOIN moz_bookmarks p ON p.id = b.parent
+ JOIN moz_places h ON h.id = b.fk
+ WHERE b.type = :bookmarkType AND
+ h.url_hash = :urlHash AND
+ h.url = :url`,
+ { bookmarkType: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+ urlHash: PlacesUtils.history.hashURL(url.href),
+ url: url.href });
+
+ return itemRows;
+ }
+
+ /**
+ * Ensures the buffer contents are internally correct. This check only
+ * verifies that we *stored* the records correctly, not that the records
+ * actually form a consistent tree.
+ */
+ async validateBuffer() {
+ // Each `parentGuid` in `structure` must reference a folder in `value`.
+ let missingParentsRows = await this.db.execute(`
+ SELECT COUNT(*) AS missingParentsCount
+ FROM structure s
+ LEFT JOIN value v ON v.guid = s.parentGuid
+ WHERE v.guid IS NULL`);
+ let missingParentsCount = missingParentsRows[0].getResultByName(
+ "missingParentsCount");
+ if (missingParentsCount > 0) {
+ throw new BookmarkConsistencyError(`Buffer contains ${
+ missingParentsCount} child(ren) without parent`);
+ }
+
+ // All parents must be folders.
+ let nonFolderParentsRows = await this.db.execute(`
+ SELECT COUNT(*) AS nonFolderParentsCount
+ FROM value c
+ JOIN structure l ON l.parentGuid = c.guid
+ WHERE c.kind <> :folderKind`,
+ { folderKind: KIND_FOLDER });
+ let nonFolderParentsCount = nonFolderParentsRows[0].getResultByName(
+ "nonFolderParentsCount");
+ if (nonFolderParentsCount > 0) {
+ throw new BookmarkConsistencyError(`Buffer contains ${
+ nonFolderParentsCount} item(s) with non-folder parent`);
+ }
+ }
+}
+
+/**
+ * Records bookmark and annotation observer notifications for all changes made
+ * during the merge, then fires the notifications after the merge is done.
+ *
+ * Recording bookmark additions, changes, and deletions is fairly expensive,
+ * because we need to query Places for the old state: observer notifications
+ * require a lot of information that we don't have in memory. We could make
+ * this more efficient by fetching and storing the information when we first
+ * build the local tree, but the notification system is due for an overhaul in
+ * bug 1340498, anyway.
+ *
+ * Annotation observers don't require the extra context, so they're cheap to
+ * record and fire.
+ */
+class BookmarkObserverNotifications {
+ constructor(storage) {
+ this.storage = storage;
+ this.keywordNotifications = [];
+ this.bookmarkNotifications = [];
+ this.annoNotifications = [];
+ }
+
+ /**
+ * Fires all recorded observer notifications. This is fairly expensive, because
+ * we need to query Places for almost every change: observer notifications
+ * require a lot of context that we don't have in memory. Bug 1340498 covers
+ * redesigning observers to remove these limitations.
+ */
+ async notifyAll() {
+ this.notifyBookmarkObservers();
+ await this.notifyAnnoObservers();
+ await this.notifyKeywordObservers();
+ }
+
+ noteKeywordSet(url, keyword) {
+ this.keywordNotifications.push({ url, keyword });
+ }
+
+ noteKeywordRemoved(url) {
+ this.keywordNotifications.push({ url, keyword: "" });
+ }
+
+ async noteItemAdded(guid) {
+ let itemRow = await this.storage.fetchItemObserverRow(guid);
+
+ let id = itemRow.getResultByName("id");
+ let parentId = itemRow.getResultByName("parentId");
+ let position = itemRow.getResultByName("position");
+ let type = itemRow.getResultByName("type");
+ let url = itemRow.getResultByName("url");
+ let title = itemRow.getResultByName("title");
+ let dateAdded = itemRow.getResultByName("dateAdded");
+ let parentGuid = itemRow.getResultByName("parentGuid");
+
+ let uri = url ? Services.io.newURI(url) : null;
+
+ this.bookmarkNotifications.push({
+ notification: "onItemAdded",
+ args: [id, parentId, position, type, uri, title, dateAdded, guid,
+ parentGuid, PlacesUtils.bookmarks.SOURCES.SYNC],
+ });
+ }
+
+ async noteItemChanged(mergedGuid, localGuid, changes) {
+ if (!changes.size) {
+ return;
+ }
+
+ let itemRow = await this.storage.fetchItemObserverRow(localGuid);
+
+ for (let [property, newValue] of changes) {
+ let id = itemRow.getResultByName("id");
+ let type = itemRow.getResultByName("type");
+ let parentId = itemRow.getResultByName("parentId");
+ let parentGuid = itemRow.getResultByName("parentGuid");
+
+ switch (property) {
+ case "guid": {
+ let oldGuid = itemRow.getResultByName("guid");
+ let lastModified = itemRow.getResultByName("lastModified");
+
+ this.bookmarkNotifications.push({
+ notification: "onItemChanged",
+ args: [id, "guid", /* isAnnotationProperty */ false, newValue,
+ lastModified, type, parentId, mergedGuid, parentGuid, oldGuid,
+ PlacesUtils.bookmarks.SOURCES.SYNC],
+ });
+ break;
+ }
+
+ case "position": {
+ let oldPosition = itemRow.getResultByName("position");
+
+ this.bookmarkNotifications.push({
+ notification: "onItemMoved",
+ args: [id, parentId, oldPosition, /* newParentId */ parentId,
+ newValue, type, mergedGuid, /* oldParentGuid */ parentGuid,
+ /* newParentGuid */ parentGuid,
+ PlacesUtils.bookmarks.SOURCES.SYNC],
+ });
+ break;
+ }
+
+ case "parentGuid": {
+ let newParentId = await this.storage.fetchItemId(newValue);
+ let position = itemRow.getResultByName("position");
+
+ this.bookmarkNotifications.push({
+ notification: "onItemMoved",
+ args: [id, parentId, /* oldPosition */ position, newParentId,
+ /* newPosition */ position, type, mergedGuid,
+ /* oldParentGuid */ parentGuid, newValue,
+ PlacesUtils.bookmarks.SOURCES.SYNC],
+ });
+ break;
+ }
+
+ case "title": {
+ let oldTitle = itemRow.getResultByName("title");
+ let lastModified = itemRow.getResultByName("lastModified");
+
+ this.bookmarkNotifications.push({
+ notification: "onItemChanged",
+ args: [id, "title", /* isAnnotationProperty */ false, newValue,
+ lastModified, type, parentId, mergedGuid, parentGuid, oldTitle,
+ PlacesUtils.bookmarks.SOURCES.SYNC],
+ });
+ break;
+ }
+
+ case "url": {
+ let oldURL = itemRow.getResultByName("url");
+ let lastModified = itemRow.getResultByName("lastModified");
+
+ this.bookmarkNotifications.push({
+ notification: "onItemChanged",
+ args: [id, "uri", /* isAnnotationProperty */ false, newValue.href,
+ lastModified, type, parentId, mergedGuid, parentGuid, oldURL,
+ PlacesUtils.bookmarks.SOURCES.SYNC],
+ });
+ break;
+ }
+
+ default:
+ throw new TypeError(`Unknown property ${property} changed for ` +
+ `local item ${localGuid}`);
+ }
+ }
+ }
+
+ async noteItemRemoved(guid) {
+ let itemRow = await this.storage.fetchItemObserverRow(guid);
+
+ let id = itemRow.getResultByName("id");
+ let parentId = itemRow.getResultByName("parentId");
+ let position = itemRow.getResultByName("position");
+ let type = itemRow.getResultByName("type");
+ let url = itemRow.getResultByName("url");
+ let parentGuid = itemRow.getResultByName("parentGuid");
+
+ let uri = url ? Services.io.newURI(url) : null;
+
+ this.bookmarkNotifications.push({
+ notification: "onItemRemoved",
+ args: [id, parentId, position, type, uri, guid, parentGuid,
+ PlacesUtils.bookmarks.SOURCES.SYNC],
+ });
+ }
+
+ noteAnnoSet(guid, name) {
+ this.annoNotifications.push({ type: "set", guid, name });
+ }
+
+ noteAnnoRemoved(guid, name) {
+ this.annoNotifications.push({ type: "removed", guid, name });
+ }
+
+ notifyBookmarkObservers() {
+ let observers = PlacesUtils.bookmarks.getObservers();
+ for (let observer of observers) {
+ this.notifyObserver(observer, "onBeginUpdateBatch");
+ for (let { notification, args } of this.bookmarkNotifications) {
+ this.notifyObserver(observer, notification, args);
+ }
+ this.notifyObserver(observer, "onEndUpdateBatch");
+ }
+ }
+
+ async notifyAnnoObservers() {
+ let observers = PlacesUtils.annotations.getObservers();
+ for (let observer of observers) {
+ for (let { type, guid, name } of this.annoNotifications) {
+ let id = await this.storage.fetchItemId(guid);
+ switch (type) {
+ case "set":
+ this.notifyObserver(observer, "onItemAnnotationSet", [
+ id, name, PlacesUtils.bookmarks.SOURCES.SYNC]);
+ break;
+
+ case "removed":
+ this.notifyObserver(observer, "onItemAnnotationRemoved", [
+ id, name, PlacesUtils.bookmarks.SOURCES.SYNC]);
+ break;
+
+ default:
+ throw new TypeError("Unknown annotation observer notification " +
+ "type " + type);
+ }
+ }
+ }
+ }
+
+ async notifyKeywordObservers() {
+ let observers = PlacesUtils.bookmarks.getObservers();
+ for (let { url, keyword } of this.keywordNotifications) {
+ let itemRows = await this.storage.fetchItemsByURL(url);
+ for (let row of itemRows) {
+ let id = row.getResultByName("id");
+ let lastModified = row.getResultByName("lastModified");
+ let type = row.getResultByName("type");
+ let parentId = row.getResultByName("parentId");
+ let guid = row.getResultByName("guid");
+ let parentGuid = row.getResultByName("parentGuid");
+
+ for (let observer of observers) {
+ this.notifyObserver(observer, "onBeginUpdateBatch");
+ this.notifyObserver(observer, "onItemChanged", [id, "keyword",
+ /* isAnnotationProperty */ false, keyword, lastModified, type,
+ parentId, guid, parentGuid, /* oldValue */ url.href,
+ PlacesUtils.bookmarks.SOURCES.SYNC]);
+ this.notifyObserver(observer, "onEndUpdateBatch");
+ }
+ }
+ }
+ }
+
+ notifyObserver(observer, notification, args = []) {
+ try {
+ observer[notification](...args);
+ } catch (ex) {}
+ }
+}
new file mode 100644
--- /dev/null
+++ b/services/sync/tests/unit/test_bookmark_buffer.js
@@ -0,0 +1,1362 @@
+/* global BookmarkBuffer */
+
+Cu.import("resource://gre/modules/osfile.jsm");
+Cu.import("resource://gre/modules/PlacesUtils.jsm");
+Cu.import("resource://gre/modules/PlacesSyncUtils.jsm");
+Cu.import("resource://services-sync/bookmark_buffer.js");
+Cu.import("resource://services-sync/engines/bookmarks.js");
+
+function run_test() {
+ let bufLog = Log.repository.getLogger("Sync.Engine.Bookmarks.Buffer");
+ bufLog.level = Log.Level.All;
+
+ let sqliteLog = Log.repository.getLogger("Sqlite");
+ sqliteLog.level = Log.Level.All;
+
+ let formatter = new Log.BasicFormatter();
+ let appender = new Log.DumpAppender(formatter);
+ appender.level = Log.Level.Fatal;
+
+ for (let log of [bufLog, sqliteLog]) {
+ log.addAppender(appender);
+ }
+
+ run_next_test();
+}
+
+function makeLivemarkServer() {
+ let server = new HttpServer();
+ server.registerPrefixHandler("/feed/", do_get_file("./livemark.xml"));
+ server.start(-1);
+ return {
+ server,
+ get site() {
+ let { identity } = server;
+ let host = identity.primaryHost.includes(":") ?
+ `[${identity.primaryHost}]` : identity.primaryHost;
+ return `${identity.primaryScheme}://${host}:${identity.primaryPort}`;
+ },
+ stopServer() {
+ return new Promise(resolve => server.stop(resolve));
+ },
+ };
+}
+
+function shuffle(array) {
+ let results = [];
+ for (let i = 0; i < array.length; ++i) {
+ let randomIndex = Math.floor(Math.random() * (i + 1));
+ results[i] = results[randomIndex];
+ results[randomIndex] = array[i];
+ }
+ return results;
+}
+
+async function openBuffer(name) {
+ let path = OS.Path.join(OS.Constants.Path.profileDir, `${name}_buf.sqlite`);
+ let buf = await BookmarkBuffer.open(1, { path });
+ return buf;
+}
+
+function makeBookmark(guid, { parentSyncId, title, url, description,
+ loadInSidebar, tags, keyword,
+ parentTitle } = {}) {
+ let record = new Bookmark("bookmarks", guid, "bookmark");
+ record.parentid = parentSyncId;
+ record.title = title;
+ record.bmkUri = url;
+ record.description = description;
+ record.loadInSidebar = loadInSidebar;
+ record.tags = tags;
+ record.keyword = keyword;
+ record.parentName = parentTitle;
+ return record;
+}
+
+function makeQuery(guid, { parentSyncId, title, url, smartBookmarkName = null,
+ tagFolderName = null } = {}) {
+ let record = new BookmarkQuery("bookmarks", guid);
+ record.parentid = parentSyncId;
+ record.title = title;
+ record.bmkUri = url;
+ record.queryId = smartBookmarkName;
+ record.folderName = tagFolderName;
+ return record;
+}
+
+function makeFolder(guid, { parentSyncId, title, description, children } = {}) {
+ let record = new BookmarkFolder("bookmarks", guid, "folder");
+ record.parentid = parentSyncId;
+ record.title = title;
+ record.description = description;
+ record.children = children;
+ return record;
+}
+
+function makeLivemark(guid, { parentSyncId, title, description, feedURI = null,
+ siteURI = null } = {}) {
+ let record = new Livemark("bookmarks", guid);
+ record.parentid = parentSyncId;
+ record.title = title;
+ record.description = description;
+ record.feedUri = feedURI;
+ record.siteUri = siteURI;
+ return record;
+}
+
+function makeSeparator(guid, { parentSyncId } = {}) {
+ let record = new BookmarkSeparator("bookmarks", guid);
+ record.parentid = parentSyncId;
+ return record;
+}
+
+function makeTombstone(guid) {
+ let record = new PlacesItem("bookmarks", guid);
+ record.deleted = true;
+ return record;
+}
+
+// A debugging helper that dumps the contents of an array of rows.
+function dumpRows(rows) {
+ let results = [];
+ for (let row of rows) {
+ let numColumns = row.numEntries;
+ let rowValues = [];
+ for (let i = 0; i < numColumns; ++i) {
+ switch (row.getTypeOfIndex(i)) {
+ case Ci.mozIStorageValueArray.VALUE_TYPE_NULL:
+ rowValues.push("NULL");
+ break;
+ case Ci.mozIStorageValueArray.VALUE_TYPE_INTEGER:
+ rowValues.push(row.getInt64(i));
+ break;
+ case Ci.mozIStorageValueArray.VALUE_TYPE_FLOAT:
+ rowValues.push(row.getDouble(i));
+ break;
+ case Ci.mozIStorageValueArray.VALUE_TYPE_TEXT:
+ rowValues.push(JSON.stringify(row.getString(i)));
+ break;
+ }
+ }
+ results.push(rowValues.join("\t"));
+ }
+ results.push("\n");
+ dump(results.join("\n"));
+}
+
+async function dumpBufferTable(buf, table) {
+ let rows = await buf.db.execute(`SELECT * FROM ${table}`);
+ do_print(`${table} contains ${rows.length} rows`);
+ dumpRows(rows);
+}
+
+add_task(async function test_apply() {
+ let buf = await openBuffer("apply");
+
+ do_print(`Insert existing bookmark to update`);
+ let mozBmk = await PlacesUtils.bookmarks.insert({
+ guid: "mozBmk______",
+ parentGuid: PlacesUtils.bookmarks.menuGuid,
+ url: "https://mozilla.org",
+ title: "Mozilla",
+ });
+
+ do_print("Tag existing bookmark with tags to replace");
+ PlacesUtils.tagging.tagURI(Services.io.newURI(mozBmk.url.href),
+ ["moz", "dot", "org"]);
+
+ do_print("Insert new bookmark to upload");
+ let bzBmk = await PlacesUtils.bookmarks.insert({
+ guid: "bzBmk_______",
+ parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+ url: "https://bugzilla.mozilla.org",
+ title: "Bugzilla",
+ });
+
+ do_print("Tag new bookmark");
+ PlacesUtils.tagging.tagURI(Services.io.newURI(bzBmk.url.href),
+ ["new", "tag"]);
+
+ do_print(`Insert bookmarks and folder into buffer`);
+ let remoteRecords = [
+ makeBookmark("fxBmk_______", {
+ title: "Get Firefox",
+ url: "http://getfirefox.com",
+ parentSyncId: "toolbar",
+ tags: ["taggy", "browsers"],
+ }),
+ makeFolder("tFolder_____", {
+ title: "Folder",
+ children: ["tbBmk_______"],
+ parentSyncId: "toolbar",
+ }),
+ makeBookmark("tbBmk_______", {
+ title: "Get Thunderbird",
+ url: "http://getthunderbird.com",
+ parentSyncId: "tFolder_____",
+ keyword: "tb",
+ }),
+ makeBookmark("mozBmk______", {
+ title: "Mozilla home page",
+ url: "https://mozilla.org",
+ parentSyncId: "menu",
+ tags: ["browsers"],
+ }),
+ makeFolder("toolbar", {
+ title: "Bookmarks Toolbar",
+ children: ["fxBmk_______", "tFolder_____"],
+ parentSyncId: "places",
+ }),
+ ];
+ for (let record of shuffle(remoteRecords)) {
+ await buf.store(record);
+ }
+
+ do_print(`Apply buffered bookmarks to Places`);
+ await buf.apply();
+
+ let fxBmk = await PlacesUtils.bookmarks.fetch("fxBmk_______");
+ ok(fxBmk, "New Firefox bookmark should exist");
+ equal(fxBmk.parentGuid, PlacesUtils.bookmarks.toolbarGuid,
+ "Should add Firefox bookmark to toolbar");
+ let fxTags = PlacesUtils.tagging.getTagsForURI(
+ Utils.makeURI("http://getfirefox.com"));
+ deepEqual(fxTags.sort(), ["browsers", "taggy"],
+ "Should tag new Firefox bookmark");
+
+ let folder = await PlacesUtils.bookmarks.fetch("tFolder_____");
+ ok(folder, "New folder should exist");
+ equal(folder.parentGuid, PlacesUtils.bookmarks.toolbarGuid,
+ "Should add new folder to toolbar");
+
+ let tbBmk = await PlacesUtils.bookmarks.fetch("tbBmk_______");
+ ok(tbBmk, "Should insert Thunderbird child bookmark");
+ equal(tbBmk.parentGuid, folder.guid,
+ "Should add Thunderbird bookmark to new folder");
+ let keywordInfo = await PlacesUtils.keywords.fetch("tb");
+ equal(keywordInfo.url.href, "http://getthunderbird.com/",
+ "Should set keyword for Thunderbird bookmark");
+
+ let updatedBmk = await PlacesUtils.bookmarks.fetch("mozBmk______");
+ equal(updatedBmk.title, "Mozilla home page",
+ "Should rename Mozilla bookmark");
+ equal(updatedBmk.parentGuid, PlacesUtils.bookmarks.menuGuid,
+ "Should not move Mozilla bookmark");
+
+ await buf.finalize();
+ await PlacesUtils.bookmarks.eraseEverything();
+ await PlacesSyncUtils.bookmarks.reset();
+});
+
+add_task(async function test_move() {
+ let buf = await openBuffer("move");
+
+ await PlacesUtils.bookmarks.insertTree({
+ guid: PlacesUtils.bookmarks.menuGuid,
+ source: PlacesUtils.bookmarks.SOURCES.SYNC,
+ children: [{
+ guid: "devFolder___",
+ type: PlacesUtils.bookmarks.TYPE_FOLDER,
+ title: "Dev",
+ children: [{
+ guid: "mdnBmk______",
+ title: "MDN",
+ url: "https://developer.mozilla.org",
+ }, {
+ type: PlacesUtils.bookmarks.TYPE_FOLDER,
+ guid: "mozFolder___",
+ title: "Mozilla",
+ children: [{
+ guid: "fxBmk_______",
+ title: "Get Firefox!",
+ url: "http://getfirefox.com/",
+ }, {
+ guid: "nightlyBmk__",
+ title: "Nightly",
+ url: "https://nightly.mozilla.org",
+ }],
+ }, {
+ guid: "wmBmk_______",
+ title: "Webmaker",
+ url: "https://webmaker.org",
+ }],
+ }, {
+ guid: "bzBmk_______",
+ title: "Bugzilla",
+ url: "https://bugzilla.mozilla.org",
+ }]
+ });
+
+ let remoteRecords = [
+ makeFolder("unfiled", {
+ title: "Other Bookmarks",
+ parentSyncId: "places",
+ children: ["mozFolder___"],
+ }),
+ makeFolder("toolbar", {
+ title: "Bookmarks Toolbar",
+ parentSyncId: "places",
+ children: ["devFolder___"],
+ }),
+
+ // Moving to toolbar.
+ makeFolder("devFolder___", {
+ title: "Dev",
+ children: ["bzBmk_______", "wmBmk_______"],
+ parentSyncId: "toolbar",
+ }),
+
+ // Moving to "Mozilla".
+ makeBookmark("mdnBmk______", {
+ title: "MDN",
+ url: "https://developer.mozilla.org",
+ parentSyncId: "mozFolder___",
+ }),
+
+ // Rearranging children and moving to unfiled.
+ makeFolder("mozFolder___", {
+ title: "Mozilla",
+ children: ["nightlyBmk__", "mdnBmk______", "fxBmk_______"],
+ parentSyncId: "unfiled",
+ }),
+
+ makeBookmark("fxBmk_______", {
+ title: "Get Firefox!",
+ url: "http://getfirefox.com/",
+ parentSyncId: "mozFolder___",
+ }),
+
+ makeBookmark("nightlyBmk__", {
+ title: "Nightly",
+ url: "https://nightly.mozilla.org",
+ parentSyncId: "mozFolder___",
+ }),
+
+ makeBookmark("wmBmk_______", {
+ title: "Webmaker",
+ url: "https://webmaker.org",
+ parentSyncId: "devFolder___",
+ }),
+
+ makeBookmark("bzBmk_______", {
+ title: "Bugzilla",
+ url: "https://bugzilla.mozilla.org",
+ parentSyncId: "devFolder___"
+ }),
+ ];
+ for (let record of shuffle(remoteRecords)) {
+ await buf.store(record);
+ }
+
+ do_print(`Apply buffered bookmarks to Places`);
+ await buf.apply();
+
+ await assertBookmarksTreeMatches("", [{
+ guid: PlacesUtils.bookmarks.menuGuid,
+ index: 0,
+ }, {
+ guid: PlacesUtils.bookmarks.toolbarGuid,
+ index: 1,
+ children: [{
+ guid: "devFolder___",
+ index: 0,
+ children: [{
+ guid: "bzBmk_______",
+ index: 0,
+ }, {
+ guid: "wmBmk_______",
+ index: 1,
+ }],
+ }],
+ }, {
+ guid: PlacesUtils.bookmarks.unfiledGuid,
+ index: 3,
+ children: [{
+ guid: "mozFolder___",
+ index: 0,
+ children: [{
+ guid: "nightlyBmk__",
+ index: 0,
+ }, {
+ guid: "mdnBmk______",
+ index: 1,
+ }, {
+ guid: "fxBmk_______",
+ index: 2,
+ }],
+ }],
+ }, {
+ guid: PlacesUtils.bookmarks.mobileGuid,
+ index: 4,
+ }], "Should move and reorder bookmarks to match remote");
+
+ await buf.finalize();
+ await PlacesUtils.bookmarks.eraseEverything();
+ await PlacesSyncUtils.bookmarks.reset();
+});
+
+add_task(async function test_complex_orphaning() {
+ let buf = await openBuffer("complex_orphaning");
+
+ // On iOS, the mirror exists as a separate table. On Desktop, we have a
+ // shadow mirror of synced local bookmarks without new changes.
+ do_print("Set up mirror: ((Toolbar > A > B) (Menu > G > C > D))");
+ await PlacesUtils.bookmarks.insertTree({
+ guid: PlacesUtils.bookmarks.toolbarGuid,
+ source: PlacesUtils.bookmarks.SOURCES.SYNC,
+ children: [{
+ guid: "folderAAAAAA",
+ type: PlacesUtils.bookmarks.TYPE_FOLDER,
+ title: "A",
+ children: [{
+ guid: "folderBBBBBB",
+ type: PlacesUtils.bookmarks.TYPE_FOLDER,
+ title: "B",
+ }],
+ }],
+ });
+ await PlacesUtils.bookmarks.insertTree({
+ guid: PlacesUtils.bookmarks.menuGuid,
+ source: PlacesUtils.bookmarks.SOURCES.SYNC,
+ children: [{
+ guid: "folderGGGGGG",
+ type: PlacesUtils.bookmarks.TYPE_FOLDER,
+ title: "G",
+ children: [{
+ guid: "folderCCCCCC",
+ type: PlacesUtils.bookmarks.TYPE_FOLDER,
+ title: "C",
+ children: [{
+ guid: "folderDDDDDD",
+ type: PlacesUtils.bookmarks.TYPE_FOLDER,
+ title: "D",
+ }],
+ }],
+ }],
+ });
+
+ do_print("Make local changes: delete D, add B > E");
+ await PlacesUtils.bookmarks.remove("folderDDDDDD");
+ await PlacesUtils.bookmarks.insert({
+ guid: "bookmarkEEEE",
+ parentGuid: "folderBBBBBB",
+ title: "E",
+ url: "http://example.com/e",
+ });
+
+ do_print("Set up buffer: delete B, add D > F");
+ let remoteRecords = [
+ makeTombstone("folderBBBBBB"),
+ makeFolder("folderAAAAAA", {
+ title: "A",
+ children: [],
+ parentSyncId: "toolbar",
+ }),
+ makeFolder("folderDDDDDD", {
+ title: "D",
+ children: ["bookmarkFFFF"],
+ parentSyncId: "folderCCCCCC",
+ }),
+ makeBookmark("bookmarkFFFF", {
+ title: "F",
+ url: "http://example.com/f",
+ parentSyncId: "folderDDDDDD",
+ parentTitle: "Parent folder",
+ }),
+ ];
+ for (let record of shuffle(remoteRecords)) {
+ await buf.store(record);
+ }
+
+ do_print("Apply buffer");
+ await buf.apply();
+
+ await assertBookmarksTreeMatches("", [{
+ guid: PlacesUtils.bookmarks.menuGuid,
+ index: 0,
+ children: [{
+ guid: "folderGGGGGG",
+ index: 0,
+ children: [{
+ guid: "folderCCCCCC",
+ index: 0,
+ children: [{
+ // D was deleted, so F moved to C, the closest surviving parent.
+ guid: "bookmarkFFFF",
+ index: 0,
+ }],
+ }],
+ }],
+ }, {
+ guid: PlacesUtils.bookmarks.toolbarGuid,
+ index: 1,
+ children: [{
+ guid: "folderAAAAAA",
+ index: 0,
+ children: [{
+ // B was deleted, so E moved to A.
+ guid: "bookmarkEEEE",
+ index: 0,
+ }],
+ }],
+ }, {
+ guid: PlacesUtils.bookmarks.unfiledGuid,
+ index: 3,
+ }, {
+ guid: PlacesUtils.bookmarks.mobileGuid,
+ index: 4,
+ }], "Should move orphans to closest surviving parent");
+
+ await buf.finalize();
+ await PlacesUtils.bookmarks.eraseEverything();
+ await PlacesSyncUtils.bookmarks.reset();
+});
+
+add_task(async function test_complex_move_with_additions() {
+ let buf = await openBuffer("complex_move_with_additions");
+
+ do_print("Set up mirror: Menu > A > (B C)");
+ await PlacesUtils.bookmarks.insertTree({
+ guid: PlacesUtils.bookmarks.menuGuid,
+ source: PlacesUtils.bookmarks.SOURCES.SYNC,
+ children: [{
+ guid: "folderAAAAAA",
+ type: PlacesUtils.bookmarks.TYPE_FOLDER,
+ title: "A",
+ children: [{
+ guid: "bookmarkBBBB",
+ url: "http://example.com/b",
+ title: "B",
+ }, {
+ guid: "bookmarkCCCC",
+ url: "http://example.com/c",
+ title: "C",
+ }],
+ }],
+ });
+
+ do_print("Make local change: Menu > A > (B C D)")
+ await PlacesUtils.bookmarks.insert({
+ guid: "folderDDDDDD",
+ parentGuid: "folderAAAAAA",
+ title: "D (local)",
+ url: "http://example.com/d",
+ });
+
+ do_print("Set up buffer: ((Menu > C) (Toolbar > A > (B E)))");
+ let remoteRecords = [
+ makeFolder("menu", {
+ title: "Bookmarks Menu",
+ children: ["bookmarkCCCC"],
+ parentSyncId: "places",
+ }),
+ makeFolder("toolbar", {
+ title: "Bookmarks Toolbar",
+ children: ["folderAAAAAA"],
+ parentSyncId: "places",
+ }),
+ makeFolder("folderAAAAAA", {
+ title: "A",
+ children: ["bookmarkBBBB", "bookmarkEEEE"],
+ parentSyncId: "toolbar",
+ }),
+ makeBookmark("bookmarkCCCC", {
+ title: "C",
+ url: "http://example.com/c",
+ parentSyncId: "menu",
+ }),
+ makeBookmark("bookmarkEEEE", {
+ title: "E",
+ url: "http://example.com/e",
+ parentSyncId: "folderAAAAAA",
+ }),
+ ];
+ for (let record of shuffle(remoteRecords)) {
+ await buf.store(record);
+ }
+
+ do_print("Apply buffer");
+ await buf.apply();
+
+ await assertBookmarksTreeMatches("", [{
+ guid: PlacesUtils.bookmarks.menuGuid,
+ index: 0,
+ children: [{
+ guid: "bookmarkCCCC",
+ index: 0,
+ }],
+ }, {
+ guid: PlacesUtils.bookmarks.toolbarGuid,
+ index: 1,
+ children: [{
+ // We can guarantee child order (B E D), since we always walk remote
+ // children first, and the remote folder A record is newer than the local
+ // folder. If the local folder were newer, the order would be (D B E).
+ guid: "folderAAAAAA",
+ index: 0,
+ children: [{
+ guid: "bookmarkBBBB",
+ index: 0,
+ }, {
+ guid: "bookmarkEEEE",
+ index: 1,
+ }, {
+ guid: "folderDDDDDD",
+ index: 2,
+ }],
+ }],
+ }, {
+ guid: PlacesUtils.bookmarks.unfiledGuid,
+ index: 3,
+ }, {
+ guid: PlacesUtils.bookmarks.mobileGuid,
+ index: 4,
+ }], "Should take remote order and preserve local children");
+
+ await buf.finalize();
+ await PlacesUtils.bookmarks.eraseEverything();
+ await PlacesSyncUtils.bookmarks.reset();
+});
+
+add_task(async function test_value_only_changes() {
+ let buf = await openBuffer("value_only_changes");
+
+ do_print("Set up mirror");
+ await PlacesUtils.bookmarks.insertTree({
+ guid: PlacesUtils.bookmarks.menuGuid,
+ source: PlacesUtils.bookmarks.SOURCES.SYNC,
+ children: [{
+ guid: "folderAAAAAA",
+ type: PlacesUtils.bookmarks.TYPE_FOLDER,
+ title: "A",
+ children: [{
+ guid: "bookmarkBBBB",
+ url: "http://example.com/b",
+ title: "B",
+ }, {
+ guid: "bookmarkCCCC",
+ url: "http://example.com/c",
+ title: "C",
+ }, {
+ guid: "folderJJJJJJ",
+ type: PlacesUtils.bookmarks.TYPE_FOLDER,
+ title: "J",
+ children: [{
+ guid: "bookmarkKKKK",
+ url: "http://example.com/k",
+ title: "K",
+ }],
+ }, {
+ guid: "bookmarkDDDD",
+ url: "http://example.com/d",
+ title: "D",
+ }, {
+ guid: "bookmarkEEEE",
+ url: "http://example.com/e",
+ title: "E",
+ }],
+ }, {
+ guid: "folderFFFFFF",
+ type: PlacesUtils.bookmarks.TYPE_FOLDER,
+ title: "F",
+ children: [{
+ guid: "bookmarkGGGG",
+ url: "http://example.com/g",
+ title: "G",
+ }, {
+ guid: "folderHHHHHH",
+ type: PlacesUtils.bookmarks.TYPE_FOLDER,
+ title: "H",
+ children: [{
+ guid: "bookmarkIIII",
+ url: "http://example.com/i",
+ title: "I",
+ }],
+ }],
+ }],
+ });
+
+ do_print("Set up buffer");
+ let remoteRecords = [
+ makeBookmark("bookmarkCCCC", {
+ title: "C (remote)",
+ url: "http://example.com/c-remote",
+ parentSyncId: "folderAAAAAA",
+ }),
+ makeBookmark("bookmarkEEEE", {
+ title: "E (remote)",
+ url: "http://example.com/e-remote",
+ parentSyncId: "folderAAAAAA",
+ }),
+ makeBookmark("bookmarkIIII", {
+ title: "I (remote)",
+ url: "http://example.com/i-remote",
+ parentSyncId: "folderHHHHHH",
+ }),
+ makeFolder("folderFFFFFF", {
+ title: "F (remote)",
+ children: ["bookmarkGGGG", "folderHHHHHH"],
+ parentSyncId: "menu",
+ }),
+ ];
+ for (let record of shuffle(remoteRecords)) {
+ await buf.store(record);
+ }
+
+ do_print("Apply buffer");
+ await buf.apply();
+
+ await assertBookmarksTreeMatches("", [{
+ guid: PlacesUtils.bookmarks.menuGuid,
+ index: 0,
+ children: [{
+ guid: "folderAAAAAA",
+ index: 0,
+ children: [{
+ guid: "bookmarkBBBB",
+ index: 0,
+ }, {
+ guid: "bookmarkCCCC",
+ index: 1,
+ }, {
+ guid: "folderJJJJJJ",
+ index: 2,
+ children: [{
+ guid: "bookmarkKKKK",
+ index: 0,
+ }],
+ }, {
+ guid: "bookmarkDDDD",
+ index: 3,
+ }, {
+ guid: "bookmarkEEEE",
+ index: 4,
+ }],
+ }, {
+ guid: "folderFFFFFF",
+ index: 1,
+ children: [{
+ guid: "bookmarkGGGG",
+ index: 0,
+ }, {
+ guid: "folderHHHHHH",
+ index: 1,
+ children: [{
+ guid: "bookmarkIIII",
+ index: 0,
+ }],
+ }],
+ }],
+ }, {
+ guid: PlacesUtils.bookmarks.toolbarGuid,
+ index: 1,
+ }, {
+ guid: PlacesUtils.bookmarks.unfiledGuid,
+ index: 3,
+ }, {
+ guid: PlacesUtils.bookmarks.mobileGuid,
+ index: 4,
+ }], "Should not change structure for value-only changes");
+
+ await buf.finalize();
+ await PlacesUtils.bookmarks.eraseEverything();
+ await PlacesSyncUtils.bookmarks.reset();
+});
+
+add_task(async function test_move_into_orphaned() {
+ let buf = await openBuffer("move_into_orphaned");
+
+ do_print("Set up mirror: Menu > (A B (C > (D (E > F))))");
+ await PlacesUtils.bookmarks.insertTree({
+ guid: PlacesUtils.bookmarks.menuGuid,
+ source: PlacesUtils.bookmarks.SOURCES.SYNC,
+ children: [{
+ guid: "bookmarkAAAA",
+ url: "http://example.com/a",
+ title: "A",
+ }, {
+ guid: "bookmarkBBBB",
+ url: "http://example.com/b",
+ title: "B",
+ }, {
+ guid: "folderCCCCCC",
+ type: PlacesUtils.bookmarks.TYPE_FOLDER,
+ title: "C",
+ children: [{
+ guid: "bookmarkDDDD",
+ title: "D",
+ url: "http://example.com/d",
+ }, {
+ guid: "folderEEEEEE",
+ type: PlacesUtils.bookmarks.TYPE_FOLDER,
+ title: "E",
+ children: [{
+ guid: "bookmarkFFFF",
+ title: "F",
+ url: "http://example.com/f",
+ }],
+ }],
+ }],
+ });
+
+ do_print("Make local changes: delete D, add E > I");
+ await PlacesUtils.bookmarks.remove("bookmarkDDDD");
+ await PlacesUtils.bookmarks.insert({
+ guid: "bookmarkIIII",
+ parentGuid: "folderEEEEEE",
+ title: "I (local)",
+ url: "http://example.com/i",
+ });
+
+ // G doesn't exist on the server.
+ do_print("Set up buffer: ([G] > A (C > (D H E))), (C > H)");
+ let remoteRecords = [
+ makeBookmark("bookmarkAAAA", {
+ title: "A",
+ url: "http://example.com/a",
+ parentSyncId: "folderGGGGGG",
+ }),
+ makeFolder("folderCCCCCC", {
+ title: "C",
+ children: ["bookmarkDDDD", "bookmarkHHHH", "folderEEEEEE"],
+ parentSyncId: "folderGGGGGG",
+ }),
+ makeBookmark("bookmarkHHHH", {
+ title: "H (remote)",
+ url: "http://example.com/h",
+ parentSyncId: "folderCCCCCC",
+ })
+ ];
+ for (let record of shuffle(remoteRecords)) {
+ await buf.store(record);
+ }
+
+ do_print("Apply buffer");
+ await buf.apply();
+
+ await assertBookmarksTreeMatches("", [{
+ guid: PlacesUtils.bookmarks.menuGuid,
+ index: 0,
+ children: [{
+ // A remains in its original place, since we don't use the `parentid`,
+ // and we don't have a record for G.
+ guid: "bookmarkAAAA",
+ index: 0,
+ }, {
+ guid: "bookmarkBBBB",
+ index: 1,
+ }, {
+ // C exists on the server, so we take its children and order. D was
+ // deleted locally, and doesn't exist remotely. C is also a child of
+ // G, but we don't have a record for it on the server.
+ guid: "folderCCCCCC",
+ index: 2,
+ children: [{
+ guid: "bookmarkHHHH",
+ index: 0,
+ }, {
+ guid: "folderEEEEEE",
+ index: 1,
+ children: [{
+ guid: "bookmarkFFFF",
+ index: 0,
+ }, {
+ guid: "bookmarkIIII",
+ index: 1,
+ }],
+ }],
+ }],
+ }, {
+ guid: PlacesUtils.bookmarks.toolbarGuid,
+ index: 1,
+ }, {
+ guid: PlacesUtils.bookmarks.unfiledGuid,
+ index: 3,
+ }, {
+ guid: PlacesUtils.bookmarks.mobileGuid,
+ index: 4,
+ }], "Should treat local tree as canonical if server is missing new parent");
+
+ await buf.finalize();
+ await PlacesUtils.bookmarks.eraseEverything();
+ await PlacesSyncUtils.bookmarks.reset();
+});
+
+add_task(async function test_new_orphan_with_local_parent() {
+ let buf = await openBuffer("new_orphan_with_local_parent");
+
+ do_print("Set up mirror: A > (B D)");
+ await PlacesUtils.bookmarks.insertTree({
+ guid: PlacesUtils.bookmarks.menuGuid,
+ source: PlacesUtils.bookmarks.SOURCES.SYNC,
+ children: [{
+ guid: "folderAAAAAA",
+ type: PlacesUtils.bookmarks.TYPE_FOLDER,
+ title: "A",
+ children: [{
+ guid: "bookmarkBBBB",
+ url: "http://example.com/b",
+ title: "B",
+ }, {
+ guid: "bookmarkEEEE",
+ url: "http://example.com/e",
+ title: "E",
+ }],
+ }],
+ });
+
+ // Simulate a partial write by another device that uploaded only B and C. A
+ // exists locally, so we can move B and C into the correct folder, but not
+ // the correct positions.
+ do_print("Set up buffer with orphans: [A] > (C D)");
+ let remoteRecords = [
+ makeBookmark("bookmarkCCCC", {
+ title: "C (remote)",
+ url: "http://example.com/c-remote",
+ parentSyncId: "folderAAAAAA",
+ }),
+ makeBookmark("bookmarkDDDD", {
+ title: "D (remote)",
+ url: "http://example.com/d-remote",
+ parentSyncId: "folderAAAAAA",
+ }),
+ ];
+ for (let record of shuffle(remoteRecords)) {
+ await buf.store(record);
+ }
+
+ do_print("Apply buffer");
+ await buf.apply();
+
+ // Since we don't have a record for A, we don't know the order of the new
+ // children: either (B C D) or (B D C) are acceptable.
+ let nodeA = await PlacesUtils.promiseBookmarksTree("folderAAAAAA");
+ let childrenA = bookmarkNodesToInfos(nodeA.children);
+ let expectedChildrenA = [{
+ guid: "bookmarkBBBB",
+ index: 0,
+ }, {
+ guid: "bookmarkEEEE",
+ index: 1,
+ }];
+ if (childrenA[2].guid == "bookmarkCCCC") {
+ expectedChildrenA.push({
+ guid: "bookmarkCCCC",
+ index: 2,
+ }, {
+ guid: "bookmarkDDDD",
+ index: 3,
+ });
+ } else if (childrenA[2].guid == "bookmarkDDDD") {
+ expectedChildrenA.push({
+ guid: "bookmarkDDDD",
+ index: 2,
+ }, {
+ guid: "bookmarkCCCC",
+ index: 3,
+ });
+ } else {
+ ok(false, `Unexpected child order for known local folder A: ${
+ JSON.stringify(childrenA)}`);
+ }
+ deepEqual(childrenA, expectedChildrenA, "(B E) should precede (C D)");
+
+ // The partial uploader returns and uploads A.
+ do_print("Add A to buffer");
+ await buf.store(makeFolder("folderAAAAAA", {
+ title: "A",
+ children: ["bookmarkCCCC", "bookmarkDDDD", "bookmarkEEEE", "bookmarkBBBB"],
+ parentSyncId: "menu",
+ }));
+
+ do_print("Apply buffer with A");
+ await buf.apply();
+
+ await assertBookmarksTreeMatches("folderAAAAAA", [{
+ guid: "bookmarkCCCC",
+ index: 0,
+ }, {
+ guid: "bookmarkDDDD",
+ index: 1,
+ }, {
+ guid: "bookmarkEEEE",
+ index: 2,
+ }, {
+ guid: "bookmarkBBBB",
+ index: 3,
+ }], "Should update child positions once A exists in buffer");
+
+ await buf.finalize();
+ await PlacesUtils.bookmarks.eraseEverything();
+ await PlacesSyncUtils.bookmarks.reset();
+});
+
+add_task(async function test_new_orphan_without_local_parent() {
+ let buf = await openBuffer("new_orphan_without_local_parent");
+
+ // A doesn't exist locally, so we move the bookmarks into "unfiled" without
+ // reuploading. When the partial uploader returns and uploads A, we'll
+ // move the bookmarks to the correct folder.
+ do_print("Set up buffer with [A] > (B C D)");
+ let remoteRecords = [
+ makeBookmark("bookmarkBBBB", {
+ title: "B (remote)",
+ url: "http://example.com/b-remote",
+ parentSyncId: "folderAAAAAA",
+ }),
+ makeBookmark("bookmarkCCCC", {
+ title: "C (remote)",
+ url: "http://example.com/c-remote",
+ parentSyncId: "folderAAAAAA",
+ }),
+ makeBookmark("bookmarkDDDD", {
+ title: "D (remote)",
+ url: "http://example.com/d-remote",
+ parentSyncId: "folderAAAAAA",
+ }),
+ ];
+ for (let record of shuffle(remoteRecords)) {
+ await buf.store(record);
+ }
+
+ await buf.apply();
+
+ let nodeUnfiled = await PlacesUtils.promiseBookmarksTree(
+ PlacesUtils.bookmarks.unfiledGuid);
+ let childrenUnfiled = bookmarkNodesToInfos(nodeUnfiled.children);
+ deepEqual(childrenUnfiled.map(info => info.guid).sort(),
+ ["bookmarkBBBB", "bookmarkCCCC", "bookmarkDDDD"]);
+
+ // Make sure the indices are contiguous.
+ for (let index = 0; index < childrenUnfiled.length; index++) {
+ let info = childrenUnfiled[index];
+ equal(info.index, index, `Orphan ${
+ info.guid} should have correct position`);
+ }
+
+ // A is an orphan because we don't have E locally, but we should move
+ // (B C D) into A.
+ do_print("Add [E] > A to buffer");
+ await buf.store(makeFolder("folderAAAAAA", {
+ title: "A",
+ children: ["bookmarkDDDD", "bookmarkCCCC", "bookmarkBBBB"],
+ parentSyncId: "folderEEEEEE",
+ }));
+
+ await buf.apply();
+
+ await assertBookmarksTreeMatches(PlacesUtils.bookmarks.unfiledGuid, [{
+ guid: "folderAAAAAA",
+ index: 0,
+ children: [{
+ guid: "bookmarkDDDD",
+ index: 0,
+ }, {
+ guid: "bookmarkCCCC",
+ index: 1,
+ }, {
+ guid: "bookmarkBBBB",
+ index: 2,
+ }],
+ }]);
+
+ do_print("Add E to buffer");
+ await buf.store(makeFolder("folderEEEEEE", {
+ title: "E",
+ children: ["folderAAAAAA"],
+ parentSyncId: "menu",
+ }));
+
+ await buf.apply();
+
+ await assertBookmarksTreeMatches("", [{
+ guid: PlacesUtils.bookmarks.menuGuid,
+ index: 0,
+ children: [{
+ guid: "folderEEEEEE",
+ index: 0,
+ children: [{
+ guid: "folderAAAAAA",
+ index: 0,
+ children: [{
+ guid: "bookmarkDDDD",
+ index: 0,
+ }, {
+ guid: "bookmarkCCCC",
+ index: 1,
+ }, {
+ guid: "bookmarkBBBB",
+ index: 2,
+ }],
+ }],
+ }],
+ }, {
+ guid: PlacesUtils.bookmarks.toolbarGuid,
+ index: 1,
+ }, {
+ guid: PlacesUtils.bookmarks.unfiledGuid,
+ index: 3,
+ }, {
+ guid: PlacesUtils.bookmarks.mobileGuid,
+ index: 4,
+ }], "Should form complete tree after applying E");
+
+ await buf.finalize();
+ await PlacesUtils.bookmarks.eraseEverything();
+ await PlacesSyncUtils.bookmarks.reset();
+});
+
+add_task(async function test_duping() {
+ let buf = await openBuffer("duping");
+
+ do_print("Set up mirror");
+ await PlacesUtils.bookmarks.insertTree({
+ guid: PlacesUtils.bookmarks.menuGuid,
+ source: PlacesUtils.bookmarks.SOURCES.SYNC,
+ children: [{
+ // Shouldn't dupe to `folderA11111` because its sync status is "NORMAL".
+ guid: "folderAAAAAA",
+ type: PlacesUtils.bookmarks.TYPE_FOLDER,
+ title: "A",
+ children: [{
+ // Shouldn't dupe to `bookmarkG111`.
+ guid: "bookmarkGGGG",
+ url: "http://example.com/g",
+ title: "G",
+ }],
+ }],
+ });
+
+ do_print("Insert local dupes");
+ await PlacesUtils.bookmarks.insertTree({
+ guid: PlacesUtils.bookmarks.menuGuid,
+ children: [{
+ // Should dupe to `folderB11111`.
+ guid: "folderBBBBBB",
+ type: PlacesUtils.bookmarks.TYPE_FOLDER,
+ title: "B",
+ children: [{
+ // Should dupe to `bookmarkC222`.
+ guid: "bookmarkC111",
+ url: "http://example.com/c",
+ title: "C",
+ }, {
+ // Should dupe to `separatorF11` because the positions are the same.
+ guid: "separatorFFF",
+ type: PlacesUtils.bookmarks.TYPE_SEPARATOR,
+ }],
+ }, {
+ // Shouldn't dupe to `bookmarkC222` because the parents are different.
+ guid: "bookmarkCCCC",
+ url: "http://example.com/c",
+ title: "C",
+ }, {
+ // Shouldn't dupe to `separatorE11`, because the positions are different.
+ guid: "separatorEEE",
+ type: PlacesUtils.bookmarks.TYPE_SEPARATOR,
+ }, {
+ // Should dupe to `queryD111111`.
+ guid: "queryDDDDDDD",
+ url: "place:sort=8&maxResults=10",
+ title: "Most Visited",
+ annos: [{
+ name: PlacesSyncUtils.bookmarks.SMART_BOOKMARKS_ANNO,
+ value: "MostVisited",
+ }],
+ }],
+ });
+ // Not a candidate for `bookmarkH111` because we didn't dupe `folderAAAAAA`.
+ await PlacesUtils.bookmarks.insert({
+ parentGuid: "folderAAAAAA",
+ guid: "bookmarkHHHH",
+ url: "http://example.com/h",
+ title: "H",
+ });
+
+ do_print("Set up buffer");
+ let remoteRecords = [
+ makeFolder("menu", {
+ title: "Bookmarks Menu",
+ children: ["folderB11111", "folderA11111", "separatorE11", "queryD111111"],
+ parentSyncId: "places",
+ }),
+ makeFolder("folderB11111", {
+ title: "B",
+ children: ["bookmarkC222", "separatorF11"],
+ parentSyncId: "menu",
+ }),
+ makeBookmark("bookmarkC222", {
+ url: "http://example.com/c",
+ title: "C",
+ parentSyncId: "folderB11111",
+ }),
+ makeSeparator("separatorF11", {
+ parentSyncId: "folderB11111",
+ }),
+ makeFolder("folderA11111", {
+ title: "A",
+ children: ["bookmarkG111"],
+ parentSyncId: "menu",
+ }),
+ makeBookmark("bookmarkG111", {
+ url: "http://example.com/g",
+ title: "G",
+ parentSyncId: "folderA11111",
+ }),
+ makeSeparator("separatorE11", {
+ parentSyncId: "menu",
+ }),
+ makeQuery("queryD111111", {
+ url: "place:maxResults=10&sort=8",
+ title: "Most Visited",
+ smartBookmarkName: "MostVisited",
+ parentSyncId: "menu",
+ }),
+ ];
+ for (let record of shuffle(remoteRecords)) {
+ await buf.store(record);
+ }
+
+ do_print("Apply buffer");
+ await buf.apply();
+
+ await assertBookmarksTreeMatches(PlacesUtils.bookmarks.menuGuid, [{
+ guid: "folderAAAAAA",
+ index: 0,
+ children: [{
+ guid: "bookmarkGGGG",
+ index: 0,
+ }, {
+ guid: "bookmarkHHHH",
+ index: 1,
+ }],
+ }, {
+ guid: "bookmarkCCCC",
+ index: 1,
+ }, {
+ guid: "separatorEEE",
+ index: 2,
+ }, {
+ guid: "folderB11111",
+ index: 3,
+ children: [{
+ guid: "bookmarkC222",
+ index: 0,
+ }, {
+ guid: "separatorF11",
+ index: 1,
+ }],
+ }, {
+ guid: "folderA11111",
+ index: 4,
+ children: [{
+ guid: "bookmarkG111",
+ index: 0,
+ }],
+ }, {
+ guid: "separatorE11",
+ index: 5,
+ }, {
+ guid: "queryD111111",
+ index: 6,
+ }], "Should dedupe matching NEW bookmarks");
+
+ await buf.finalize();
+ await PlacesUtils.bookmarks.eraseEverything();
+ await PlacesSyncUtils.bookmarks.reset();
+});
+
+add_task(async function test_livemarks() {
+ let { site, stopServer } = makeLivemarkServer();
+
+ try {
+ let buf = await openBuffer("livemarks");
+
+ do_print("Set up mirror");
+ await PlacesUtils.bookmarks.insertTree({
+ guid: PlacesUtils.bookmarks.menuGuid,
+ source: PlacesUtils.bookmarks.SOURCES.SYNC,
+ children: [{
+ guid: "livemarkAAAA",
+ type: PlacesUtils.bookmarks.TYPE_FOLDER,
+ title: "A",
+ annos: [{
+ name: PlacesUtils.LMANNO_FEEDURI,
+ value: site + "/feed/a",
+ }],
+ }],
+ });
+
+ do_print("Make local changes");
+ await PlacesUtils.livemarks.addLivemark({
+ parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+ guid: "livemarkBBBB",
+ title: "B",
+ feedURI: Services.io.newURI(site + "/feed/b"),
+ });
+
+ do_print("Set up buffer");
+ let remoteRecords = [
+ makeLivemark("livemarkAAAA", {
+ title: "A (remote)",
+ feedURI: site + "/feed/a-remote",
+ parentSyncId: "menu",
+ }),
+ makeFolder("toolbar", {
+ title: "Bookmarks Toolbar",
+ children: ["livemarkCCCC", "livemarkB111"],
+ parentSyncId: "places",
+ }),
+ makeLivemark("livemarkCCCC", {
+ title: "C (remote)",
+ feedURI: site + "/feed/c-remote",
+ parentSyncId: "toolbar",
+ }),
+ makeLivemark("livemarkB111", {
+ title: "B",
+ feedURI: site + "/feed/b",
+ parentSyncId: "toolbar",
+ }),
+ ];
+ for (let record of shuffle(remoteRecords)) {
+ await buf.store(record);
+ }
+
+ do_print("Apply buffer");
+ await buf.apply();
+
+ // TODO(kitcambridge): The livemarks service should listen for
+ // `onItemAnnotation{Set, Removed}` and update the livemarks map.
+ await assertBookmarksTreeMatches("", [{
+ guid: PlacesUtils.bookmarks.menuGuid,
+ index: 0,
+ children: [{
+ guid: "livemarkAAAA",
+ index: 0,
+ }],
+ }, {
+ guid: PlacesUtils.bookmarks.toolbarGuid,
+ index: 1,
+ children: [{
+ guid: "livemarkCCCC",
+ index: 0,
+ }, {
+ guid: "livemarkB111",
+ index: 1,
+ }],
+ }, {
+ guid: PlacesUtils.bookmarks.unfiledGuid,
+ index: 3,
+ }, {
+ guid: PlacesUtils.bookmarks.mobileGuid,
+ index: 4,
+ }]);
+
+ await buf.finalize();
+ } finally {
+ await stopServer();
+ }
+
+ await PlacesUtils.bookmarks.eraseEverything();
+ await PlacesSyncUtils.bookmarks.reset();
+});