Bug 1274108 - Add a `PlacesSyncUtils` module. r=markh draft
authorKit Cambridge <kcambridge@mozilla.com>
Wed, 10 Aug 2016 12:54:45 -0700
changeset 399699 cabb31bd5a3d3438c1d7e357568733a55843757f
parent 399698 233ab21b64b5d5e9f2f16ea2d4cfb4c8b293c5c4
child 399700 5f9cdef7c48dc0b79506f74257dbfc5d4484d1ff
push id25947
push userbmo:kcambridge@mozilla.com
push dateThu, 11 Aug 2016 21:53:22 +0000
reviewersmarkh
bugs1274108
milestone51.0a1
Bug 1274108 - Add a `PlacesSyncUtils` module. r=markh MozReview-Commit-ID: LTVr3si0zrB
services/sync/modules/policies.js
toolkit/components/places/Bookmarks.jsm
toolkit/components/places/PlacesSyncUtils.jsm
toolkit/components/places/PlacesUtils.jsm
toolkit/components/places/moz.build
toolkit/components/places/tests/unit/livemark.xml
toolkit/components/places/tests/unit/test_sync_utils.js
toolkit/components/places/tests/unit/xpcshell.ini
--- a/services/sync/modules/policies.js
+++ b/services/sync/modules/policies.js
@@ -567,16 +567,17 @@ ErrorHandler.prototype = {
     this._log.level = Log.Level[Svc.Prefs.get("log.logger.service.main")];
 
     let root = Log.repository.getLogger("Sync");
     root.level = Log.Level[Svc.Prefs.get("log.rootLogger")];
 
     let logs = ["Sync", "FirefoxAccounts", "Hawk", "Common.TokenServerClient",
                 "Sync.SyncMigration", "browserwindow.syncui",
                 "Services.Common.RESTRequest", "Services.Common.RESTRequest",
+                "BookmarkSyncUtils"
                ];
 
     this._logManager = new LogManager(Svc.Prefs, logs, "sync");
   },
 
   observe: function observe(subject, topic, data) {
     this._log.trace("Handling " + topic);
     switch(topic) {
--- a/toolkit/components/places/Bookmarks.jsm
+++ b/toolkit/components/places/Bookmarks.jsm
@@ -72,20 +72,18 @@ XPCOMUtils.defineLazyModuleGetter(this, 
 XPCOMUtils.defineLazyModuleGetter(this, "Promise",
                                   "resource://gre/modules/Promise.jsm");
 XPCOMUtils.defineLazyModuleGetter(this, "Task",
                                   "resource://gre/modules/Task.jsm");
 XPCOMUtils.defineLazyModuleGetter(this, "Sqlite",
                                   "resource://gre/modules/Sqlite.jsm");
 XPCOMUtils.defineLazyModuleGetter(this, "PlacesUtils",
                                   "resource://gre/modules/PlacesUtils.jsm");
-
-// Imposed to limit database size.
-const DB_URL_LENGTH_MAX = 65536;
-const DB_TITLE_LENGTH_MAX = 4096;
+XPCOMUtils.defineLazyModuleGetter(this, "PlacesSyncUtils",
+                                  "resource://gre/modules/PlacesSyncUtils.jsm");
 
 const MATCH_ANYWHERE_UNMODIFIED = Ci.mozIPlacesAutoComplete.MATCH_ANYWHERE_UNMODIFIED;
 const BEHAVIOR_BOOKMARK = Ci.mozIPlacesAutoComplete.BEHAVIOR_BOOKMARK;
 
 var Bookmarks = Object.freeze({
   /**
    * Item's type constants.
    * These should stay consistent with nsINavBookmarksService.idl
@@ -657,17 +655,17 @@ var Bookmarks = Object.freeze({
    */
   reorder(parentGuid, orderedChildrenGuids) {
     let info = { guid: parentGuid };
     info = validateBookmarkObject(info, { guid: { required: true } });
 
     if (!Array.isArray(orderedChildrenGuids) || !orderedChildrenGuids.length)
       throw new Error("Must provide a sorted array of children GUIDs.");
     try {
-      orderedChildrenGuids.forEach(VALIDATORS.guid);
+      orderedChildrenGuids.forEach(PlacesUtils.BOOKMARK_VALIDATORS.guid);
     } catch (ex) {
       throw new Error("Invalid GUID found in the sorted children array.");
     }
 
     return Task.spawn(function* () {
       let parent = yield fetchBookmark(info);
       if (!parent || parent.type != this.TYPE_FOLDER)
         throw new Error("No folder found for the provided GUID.");
@@ -1270,127 +1268,19 @@ function rowsToItemsArray(rows) {
                                                         configurable: true });
       }
     }
 
     return item;
   });
 }
 
-/**
- * Executes a boolean validate function, throwing if it returns false.
- *
- * @param boolValidateFn
- *        A boolean validate function.
- * @return the input value.
- * @throws if input doesn't pass the validate function.
- */
-function simpleValidateFunc(boolValidateFn) {
-  return (v, input) => {
-    if (!boolValidateFn(v, input))
-      throw new Error("Invalid value");
-    return v;
-  };
-}
-
-/**
- * List of validators, one per each known property.
- * Validators must throw if the property value is invalid and return a fixed up
- * version of the value, if needed.
- */
-const VALIDATORS = Object.freeze({
-  guid: simpleValidateFunc(v => typeof(v) == "string" &&
-                                PlacesUtils.isValidGuid(v)),
-  parentGuid: simpleValidateFunc(v => typeof(v) == "string" &&
-                                      /^[a-zA-Z0-9\-_]{12}$/.test(v)),
-  index: simpleValidateFunc(v => Number.isInteger(v) &&
-                                 v >= Bookmarks.DEFAULT_INDEX),
-  dateAdded: simpleValidateFunc(v => v.constructor.name == "Date"),
-  lastModified: simpleValidateFunc(v => v.constructor.name == "Date"),
-  type: simpleValidateFunc(v => Number.isInteger(v) &&
-                                [ Bookmarks.TYPE_BOOKMARK
-                                , Bookmarks.TYPE_FOLDER
-                                , Bookmarks.TYPE_SEPARATOR ].includes(v)),
-  title: v => {
-    simpleValidateFunc(val => val === null || typeof(val) == "string").call(this, v);
-    if (!v)
-      return null;
-    return v.slice(0, DB_TITLE_LENGTH_MAX);
-  },
-  url: v => {
-    simpleValidateFunc(val => (typeof(val) == "string" && val.length <= DB_URL_LENGTH_MAX) ||
-                              (val instanceof Ci.nsIURI && val.spec.length <= DB_URL_LENGTH_MAX) ||
-                              (val instanceof URL && val.href.length <= DB_URL_LENGTH_MAX)
-                      ).call(this, v);
-    if (typeof(v) === "string")
-      return new URL(v);
-    if (v instanceof Ci.nsIURI)
-      return new URL(v.spec);
-    return v;
-  }
-});
-
-/**
- * Checks validity of a bookmark object, filling up default values for optional
- * properties.
- *
- * @param input (object)
- *        The bookmark object to validate.
- * @param behavior (object) [optional]
- *        Object defining special behavior for some of the properties.
- *        The following behaviors may be optionally set:
- *         - requiredIf: if the provided condition is satisfied, then this
- *                       property is required.
- *         - validIf: if the provided condition is not satisfied, then this
- *                    property is invalid.
- *         - defaultValue: an undefined property should default to this value.
- *
- * @return a validated and normalized bookmark-item.
- * @throws if the object contains invalid data.
- * @note any unknown properties are pass-through.
- */
-function validateBookmarkObject(input, behavior={}) {
-  if (!input)
-    throw new Error("Input should be a valid object");
-  let normalizedInput = {};
-  let required = new Set();
-  for (let prop in behavior) {
-    if (behavior[prop].hasOwnProperty("required") && behavior[prop].required) {
-      required.add(prop);
-    }
-    if (behavior[prop].hasOwnProperty("requiredIf") && behavior[prop].requiredIf(input)) {
-      required.add(prop);
-    }
-    if (behavior[prop].hasOwnProperty("validIf") && input[prop] !== undefined &&
-        !behavior[prop].validIf(input)) {
-      throw new Error(`Invalid value for property '${prop}': ${input[prop]}`);
-    }
-    if (behavior[prop].hasOwnProperty("defaultValue") && input[prop] === undefined) {
-      input[prop] = behavior[prop].defaultValue;
-    }
-  }
-
-  for (let prop in input) {
-    if (required.has(prop)) {
-      required.delete(prop);
-    } else if (input[prop] === undefined) {
-      // Skip undefined properties that are not required.
-      continue;
-    }
-    if (VALIDATORS.hasOwnProperty(prop)) {
-      try {
-        normalizedInput[prop] = VALIDATORS[prop](input[prop], input);
-      } catch (ex) {
-        throw new Error(`Invalid value for property '${prop}': ${input[prop]}`);
-      }
-    }
-  }
-  if (required.size > 0)
-    throw new Error(`The following properties were expected: ${[...required].join(", ")}`);
-  return normalizedInput;
+function validateBookmarkObject(input, behavior) {
+  return PlacesUtils.validateItemProperties(
+    PlacesUtils.BOOKMARK_VALIDATORS, input, behavior);
 }
 
 /**
  * Updates frecency for a list of URLs.
  *
  * @param db
  *        the Sqlite.jsm connection handle.
  * @param urls
new file mode 100644
--- /dev/null
+++ b/toolkit/components/places/PlacesSyncUtils.jsm
@@ -0,0 +1,923 @@
+/* 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.EXPORTED_SYMBOLS = ["PlacesSyncUtils"];
+
+const { classes: Cc, interfaces: Ci, results: Cr, utils: Cu } = Components;
+
+Cu.importGlobalProperties(["URL", "URLSearchParams"]);
+
+Cu.import("resource://gre/modules/XPCOMUtils.jsm");
+
+XPCOMUtils.defineLazyModuleGetter(this, "Log",
+                                  "resource://gre/modules/Log.jsm");
+XPCOMUtils.defineLazyModuleGetter(this, "PlacesUtils",
+                                  "resource://gre/modules/PlacesUtils.jsm");
+XPCOMUtils.defineLazyModuleGetter(this, "Preferences",
+                                  "resource://gre/modules/Preferences.jsm");
+XPCOMUtils.defineLazyModuleGetter(this, "Task",
+                                  "resource://gre/modules/Task.jsm");
+
+/**
+ * This module exports functions for Sync to use when applying remote
+ * records. The calls are similar to those in `Bookmarks.jsm` and
+ * `nsINavBookmarksService`, with special handling for smart bookmarks,
+ * tags, keywords, synced annotations, and missing parents.
+ */
+var PlacesSyncUtils = {};
+
+const SMART_BOOKMARKS_ANNO = "Places/SmartBookmark";
+const DESCRIPTION_ANNO = "bookmarkProperties/description";
+const SIDEBAR_ANNO = "bookmarkProperties/loadInSidebar";
+const PARENT_ANNO = "sync/parent";
+
+const BookmarkSyncUtils = PlacesSyncUtils.bookmarks = Object.freeze({
+  KINDS: {
+    BOOKMARK: "bookmark",
+    // Microsummaries were removed from Places in bug 524091. For now, Sync
+    // treats them identically to bookmarks. Bug 745410 tracks removing them
+    // entirely.
+    MICROSUMMARY: "microsummary",
+    QUERY: "query",
+    FOLDER: "folder",
+    LIVEMARK: "livemark",
+    SEPARATOR: "separator",
+  },
+
+  /**
+   * Fetches a folder's children, ordered by their position within the folder.
+   * Children without a GUID will be assigned one.
+   */
+  fetchChildGuids: Task.async(function* (parentGuid) {
+    PlacesUtils.SYNC_BOOKMARK_VALIDATORS.guid(parentGuid);
+
+    let db = yield PlacesUtils.promiseDBConnection();
+    let children = yield fetchAllChildren(db, parentGuid);
+    let childGuids = [];
+    let guidsToSet = new Map();
+    for (let child of children) {
+      let guid = child.guid;
+      if (!PlacesUtils.isValidGuid(guid)) {
+        // Give the child a GUID if it doesn't have one. This shouldn't happen,
+        // but the old bookmarks engine code does this, so we'll match its
+        // behavior until we're sure this can be removed.
+        guid = yield generateGuid(db);
+        BookmarkSyncLog.warn(`fetchChildGuids: Assigning ${
+          guid} to item without GUID ${child.id}`);
+        guidsToSet.set(child.id, guid);
+      }
+      childGuids.push(guid);
+    }
+    if (guidsToSet.size > 0) {
+      yield setGuids(guidsToSet);
+    }
+    return childGuids;
+  }),
+
+  /**
+   * Reorders a folder's children, based on their order in the array of GUIDs.
+   * This method is similar to `Bookmarks.reorder`, but leaves missing entries
+   * in place instead of moving them to the end of the folder.
+   *
+   * Sync uses this method to reorder all synced children after applying all
+   * incoming records.
+   *
+   */
+  order: Task.async(function* (parentGuid, childGuids) {
+    PlacesUtils.SYNC_BOOKMARK_VALIDATORS.guid(parentGuid);
+    for (let guid of childGuids) {
+      PlacesUtils.SYNC_BOOKMARK_VALIDATORS.guid(guid);
+    }
+
+    if (parentGuid == PlacesUtils.bookmarks.rootGuid) {
+      // Reordering roots doesn't make sense, but Sync will do this on the
+      // first sync.
+      return Promise.resolve();
+    }
+    return PlacesUtils.withConnectionWrapper("BookmarkSyncUtils: order",
+      Task.async(function* (db) {
+        let children;
+
+        yield db.executeTransaction(function* () {
+          children = yield fetchAllChildren(db, parentGuid);
+          if (!children.length) {
+            return;
+          }
+          for (let child of children) {
+            // Note the current index for notifying observers. This can
+            // be removed once we switch to `reorder`.
+            child.oldIndex = child.index;
+          }
+
+          // Reorder the list, ignoring missing children.
+          let delta = 0;
+          for (let i = 0; i < childGuids.length; ++i) {
+            let guid = childGuids[i];
+            let child = findChildByGuid(children, guid);
+            if (!child) {
+              delta++;
+              BookmarkSyncLog.trace(`order: Ignoring missing child ${guid}`);
+              continue;
+            }
+            let newIndex = i - delta;
+            updateChildIndex(children, child, newIndex);
+          }
+          children.sort((a, b) => a.index - b.index);
+
+          // Update positions. We use a custom query instead of
+          // `PlacesUtils.bookmarks.reorder` because `reorder` introduces holes
+          // (bug 1293365). Once it's fixed, we can uncomment this code and
+          // remove the transaction, query, and observer notification code.
+
+          /*
+          let orderedChildrenGuids = children.map(({ guid }) => guid);
+          yield PlacesUtils.bookmarks.reorder(parentGuid, orderedChildrenGuids);
+          */
+
+          yield db.executeCached(`WITH sorting(g, p) AS (
+            VALUES ${children.map(
+              (child, i) => `("${child.guid}", ${i})`
+            ).join()}
+          ) UPDATE moz_bookmarks SET position = (
+            SELECT p FROM sorting WHERE g = guid
+          ) WHERE parent = (
+            SELECT id FROM moz_bookmarks WHERE guid = :parentGuid
+          )`,
+          { parentGuid });
+        });
+
+        // Notify observers.
+        let observers = PlacesUtils.bookmarks.getObservers();
+        for (let child of children) {
+          notify(observers, "onItemMoved", [ child.id, child.parentId,
+                                             child.oldIndex, child.parentId,
+                                             child.index, child.type,
+                                             child.guid, parentGuid,
+                                             parentGuid ]);
+        }
+      })
+    );
+  }),
+
+  /**
+   * Removes an item from the database.
+   */
+  remove: Task.async(function* (guid) {
+    return PlacesUtils.bookmarks.remove(guid);
+  }),
+
+  /**
+   * Removes a folder's children. This is a temporary method that can be
+   * replaced by `eraseEverything` once Places supports the Sync-specific
+   * mobile root.
+   */
+  clear: Task.async(function* (folderGuid) {
+    let folderId = yield PlacesUtils.promiseItemId(folderGuid);
+    PlacesUtils.bookmarks.removeFolderChildren(folderId);
+  }),
+
+  /**
+   * Ensures an item with the |itemId| has a GUID, assigning one if necessary.
+   * We should never have a bookmark without a GUID, but the old Sync bookmarks
+   * engine code does this, so we'll match its behavior until we're sure it's
+   * not needed.
+   *
+   * This method can be removed and replaced with `PlacesUtils.promiseItemGuid`
+   * once bug 1294291 lands.
+   *
+   * @return {Promise} resolved once the GUID has been updated.
+   * @resolves to the existing or new GUID.
+   * @rejects if the item does not exist.
+   */
+  ensureGuidForId: Task.async(function* (itemId) {
+    let guid;
+    try {
+      // Use the existing GUID if it exists. `promiseItemGuid` caches the GUID
+      // as a side effect, and throws if it's invalid.
+      guid = yield PlacesUtils.promiseItemGuid(itemId);
+    } catch (ex) {
+      BookmarkSyncLog.warn(`ensureGuidForId: Error fetching GUID for ${
+        itemId}`, ex);
+      if (!isInvalidCachedGuidError(ex)) {
+        throw ex;
+      }
+      // Give the item a GUID if it doesn't have one.
+      guid = yield PlacesUtils.withConnectionWrapper(
+        "BookmarkSyncUtils: ensureGuidForId", Task.async(function* (db) {
+          let guid = yield generateGuid(db);
+          BookmarkSyncLog.warn(`ensureGuidForId: Assigning ${
+            guid} to item without GUID ${itemId}`);
+          return setGuid(db, itemId, guid);
+        })
+      );
+
+    }
+    return guid;
+  }),
+
+  /**
+   * Changes the GUID of an existing item.
+   *
+   * @return {Promise} resolved once the GUID has been changed.
+   * @resolves to the new GUID.
+   * @rejects if the old GUID does not exist.
+   */
+  changeGuid: Task.async(function* (oldGuid, newGuid) {
+    PlacesUtils.SYNC_BOOKMARK_VALIDATORS.guid(oldGuid);
+
+    let itemId = yield PlacesUtils.promiseItemId(oldGuid);
+    if (PlacesUtils.isRootItem(itemId)) {
+      throw new Error(`Cannot change GUID of Places root ${oldGuid}`);
+    }
+    return PlacesUtils.withConnectionWrapper("BookmarkSyncUtils: changeGuid",
+      db => setGuid(db, itemId, newGuid));
+  }),
+
+  /**
+   * Updates a bookmark with synced properties. Only Sync should call this
+   * method; other callers should use `Bookmarks.update`.
+   *
+   * The following properties are supported:
+   *  - kind: Optional.
+   *  - guid: Required.
+   *  - parentGuid: Optional; reparents the bookmark if specified.
+   *  - title: Optional.
+   *  - url: Optional.
+   *  - tags: Optional; replaces all existing tags.
+   *  - keyword: Optional.
+   *  - description: Optional.
+   *  - loadInSidebar: Optional.
+   *  - query: Optional.
+   *
+   * @param info
+   *        object representing a bookmark-item, as defined above.
+   *
+   * @return {Promise} resolved when the update is complete.
+   * @resolves to an object representing the updated bookmark.
+   * @rejects if it's not possible to update the given bookmark.
+   * @throws if the arguments are invalid.
+   */
+  update: Task.async(function* (info) {
+    let updateInfo = validateSyncBookmarkObject(info,
+      { guid: { required: true }
+      , type: { validIf: () => false }
+      , index: { validIf: () => false }
+      });
+
+    return updateSyncBookmark(updateInfo);
+  }),
+
+  /**
+   * Inserts a synced bookmark into the tree. Only Sync should call this
+   * method; other callers should use `Bookmarks.insert`.
+   *
+   * The following properties are supported:
+   *  - kind: Required.
+   *  - guid: Required.
+   *  - parentGuid: Required.
+   *  - url: Required for bookmarks.
+   *  - query: A smart bookmark query string, optional.
+   *  - tags: An optional array of tag strings.
+   *  - keyword: An optional keyword string.
+   *  - description: An optional description string.
+   *  - loadInSidebar: An optional boolean; defaults to false.
+   *
+   * Sync doesn't set the index, since it appends and reorders children
+   * after applying all incoming items.
+   *
+   * @param info
+   *        object representing a synced bookmark.
+   *
+   * @return {Promise} resolved when the creation is complete.
+   * @resolves to an object representing the created bookmark.
+   * @rejects if it's not possible to create the requested bookmark.
+   * @throws if the arguments are invalid.
+   */
+  insert: Task.async(function* (info) {
+    let insertInfo = validateNewBookmark(info);
+    return insertSyncBookmark(insertInfo);
+  }),
+});
+
+XPCOMUtils.defineLazyGetter(this, "BookmarkSyncLog", () => {
+  return Log.repository.getLogger("BookmarkSyncUtils");
+});
+
+function validateSyncBookmarkObject(input, behavior) {
+  return PlacesUtils.validateItemProperties(
+    PlacesUtils.SYNC_BOOKMARK_VALIDATORS, input, behavior);
+}
+
+// Similar to the private `fetchBookmarksByParent` implementation in
+// `Bookmarks.jsm`.
+var fetchAllChildren = Task.async(function* (db, parentGuid) {
+  let rows = yield db.executeCached(`
+    SELECT id, parent, position, type, guid
+    FROM moz_bookmarks
+    WHERE parent = (
+      SELECT id FROM moz_bookmarks WHERE guid = :parentGuid
+    )
+    ORDER BY position`,
+    { parentGuid }
+  );
+  return rows.map(row => ({
+    id: row.getResultByName("id"),
+    parentId: row.getResultByName("parent"),
+    index: row.getResultByName("position"),
+    type: row.getResultByName("type"),
+    guid: row.getResultByName("guid"),
+  }));
+});
+
+function findChildByGuid(children, guid) {
+  return children.find(child => child.guid == guid);
+}
+
+function findChildByIndex(children, index) {
+  return children.find(child => child.index == index);
+}
+
+// Sets a child record's index and updates its sibling's indices.
+function updateChildIndex(children, child, newIndex) {
+  let siblings = [];
+  let lowIndex = Math.min(child.index, newIndex);
+  let highIndex = Math.max(child.index, newIndex);
+  for (; lowIndex < highIndex; ++lowIndex) {
+    let sibling = findChildByIndex(children, lowIndex);
+    siblings.push(sibling);
+  }
+
+  let sign = newIndex < child.index ? +1 : -1;
+  for (let sibling of siblings) {
+    sibling.index += sign;
+  }
+  child.index = newIndex;
+}
+
+/**
+ * Sends a bookmarks notification through the given observers.
+ *
+ * @param observers
+ *        array of nsINavBookmarkObserver objects.
+ * @param notification
+ *        the notification name.
+ * @param args
+ *        array of arguments to pass to the notification.
+ */
+function notify(observers, notification, args) {
+  for (let observer of observers) {
+    try {
+      observer[notification](...args);
+    } catch (ex) {}
+  }
+}
+
+function isInvalidCachedGuidError(error) {
+  return error && error.message ==
+    "Trying to update the GUIDs cache with an invalid GUID";
+}
+
+// Tag queries use a `place:` URL that refers to the tag folder ID. When we
+// apply a synced tag query from a remote client, we need to update the URL to
+// point to the local tag folder.
+var updateTagQueryFolder = Task.async(function* (item) {
+  if (item.kind != BookmarkSyncUtils.KINDS.QUERY || !item.folder || !item.url ||
+      item.url.protocol != "place:") {
+    return item;
+  }
+
+  let params = new URLSearchParams(item.url.pathname);
+  let type = +params.get("type");
+
+  if (type != Ci.nsINavHistoryQueryOptions.RESULTS_AS_TAG_CONTENTS) {
+    return item;
+  }
+
+  let id = yield getOrCreateTagFolder(item.folder);
+  BookmarkSyncLog.debug(`updateTagQueryFolder: Tag query folder: ${
+    item.folder} = ${id}`);
+
+  // Rewrite the query to reference the new ID.
+  params.set("folder", id);
+  item.url = new URL(item.url.protocol + params);
+
+  return item;
+});
+
+var annotateOrphan = Task.async(function* (item, requestedParentGuid) {
+  let itemId = yield PlacesUtils.promiseItemId(item.guid);
+  PlacesUtils.annotations.setItemAnnotation(itemId,
+    PARENT_ANNO, requestedParentGuid, 0,
+    PlacesUtils.annotations.EXPIRE_NEVER);
+});
+
+var reparentOrphans = Task.async(function* (item) {
+  if (item.type != PlacesUtils.bookmarks.TYPE_FOLDER) {
+    return;
+  }
+  let orphanIds = findAnnoItems(PARENT_ANNO, item.guid);
+  // The annotations API returns item IDs, but the asynchronous bookmarks
+  // API uses GUIDs. We can remove the `promiseItemGuid` calls and parallel
+  // arrays once we implement a GUID-aware annotations API.
+  let orphanGuids = yield Promise.all(orphanIds.map(id =>
+    PlacesUtils.promiseItemGuid(id)));
+  BookmarkSyncLog.debug(`reparentOrphans: Reparenting ${
+    JSON.stringify(orphanGuids)} to ${item.guid}`);
+  for (let i = 0; i < orphanGuids.length; ++i) {
+    let isReparented = false;
+    try {
+      // Reparenting can fail if we have a corrupted or incomplete tree
+      // where an item's parent is one of its descendants.
+      BookmarkSyncLog.trace(`reparentOrphans: Attempting to move item ${
+        orphanGuids[i]} to new parent ${item.guid}`);
+      yield PlacesUtils.bookmarks.update({
+        guid: orphanGuids[i],
+        parentGuid: item.guid,
+        index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+      });
+      isReparented = true;
+    } catch (ex) {
+      BookmarkSyncLog.error(`reparentOrphans: Failed to reparent item ${
+        orphanGuids[i]} to ${item.guid}`, ex);
+    }
+    if (isReparented) {
+      // Remove the annotation once we've reparented the item.
+      PlacesUtils.annotations.removeItemAnnotation(orphanIds[i],
+        PARENT_ANNO);
+    }
+  }
+});
+
+// Inserts a synced bookmark into the database.
+var insertSyncBookmark = Task.async(function* (insertInfo) {
+  let requestedParentGuid = insertInfo.parentGuid;
+  let parent = yield PlacesUtils.bookmarks.fetch(requestedParentGuid);
+
+  // Default to "unfiled" for new bookmarks if the parent doesn't exist.
+  if (parent) {
+    BookmarkSyncLog.debug(`insertSyncBookmark: Item ${
+      insertInfo.guid} is not an orphan`);
+  } else {
+    BookmarkSyncLog.debug(`insertSyncBookmark: Item ${
+      insertInfo.guid} is an orphan: parent ${
+      requestedParentGuid} doesn't exist; reparenting to unfiled`);
+    insertInfo.parentGuid = PlacesUtils.bookmarks.unfiledGuid;
+  }
+
+  // If we're inserting a tag query, make sure the tag exists and fix the
+  // folder ID to refer to the local tag folder.
+  insertInfo = yield updateTagQueryFolder(insertInfo);
+
+  let newItem;
+  if (insertInfo.kind == BookmarkSyncUtils.KINDS.LIVEMARK) {
+    newItem = yield insertSyncLivemark(parent, insertInfo);
+  } else {
+    let item = yield PlacesUtils.bookmarks.insert(insertInfo);
+    let newId = yield PlacesUtils.promiseItemId(item.guid);
+    newItem = yield insertBookmarkMetadata(newId, item, insertInfo);
+  }
+
+  if (!newItem) {
+    return null;
+  }
+
+  // If the item is an orphan, annotate it with its real parent ID.
+  if (!parent) {
+    yield annotateOrphan(newItem, requestedParentGuid);
+  }
+
+  // Reparent all orphans that expect this folder as the parent.
+  yield reparentOrphans(newItem);
+
+  return newItem;
+});
+
+// Inserts a synced livemark.
+var insertSyncLivemark = Task.async(function* (requestedParent, insertInfo) {
+  let parentId = yield PlacesUtils.promiseItemId(insertInfo.parentGuid);
+  let parentIsLivemark = PlacesUtils.annotations.itemHasAnnotation(parentId,
+    PlacesUtils.LMANNO_FEEDURI);
+  if (parentIsLivemark) {
+    // A livemark can't be a descendant of another livemark.
+    BookmarkSyncLog.debug(`insertSyncLivemark: Invalid parent ${
+      insertInfo.parentGuid}; skipping livemark record ${insertInfo.guid}`);
+    return null;
+  }
+
+  let feedURI = PlacesUtils.toURI(insertInfo.feed);
+  let siteURI = insertInfo.site ? PlacesUtils.toURI(insertInfo.site) : null;
+  let item = yield PlacesUtils.livemarks.addLivemark({
+    title: insertInfo.title,
+    parentGuid: insertInfo.parentGuid,
+    index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+    feedURI,
+    siteURI,
+    guid: insertInfo.guid,
+  });
+
+  return insertBookmarkMetadata(item.id, item, insertInfo);
+});
+
+// Sets annotations, keywords, and tags on a new synced bookmark.
+var insertBookmarkMetadata = Task.async(function* (itemId, item, insertInfo) {
+  if (insertInfo.query) {
+    PlacesUtils.annotations.setItemAnnotation(itemId,
+      SMART_BOOKMARKS_ANNO, insertInfo.query, 0,
+      PlacesUtils.annotations.EXPIRE_NEVER);
+    item.query = insertInfo.query;
+  }
+
+  try {
+    item.tags = yield tagItem(item, insertInfo.tags);
+  } catch (ex) {
+    BookmarkSyncLog.warn(`insertBookmarkMetadata: Error tagging item ${
+      item.guid}`, ex);
+  }
+
+  if (insertInfo.keyword) {
+    yield PlacesUtils.keywords.insert({
+      keyword: insertInfo.keyword,
+      url: item.url.href,
+    });
+    item.keyword = insertInfo.keyword;
+  }
+
+  if (insertInfo.description) {
+    PlacesUtils.annotations.setItemAnnotation(itemId,
+      DESCRIPTION_ANNO, insertInfo.description, 0,
+      PlacesUtils.annotations.EXPIRE_NEVER);
+    item.description = insertInfo.description;
+  }
+
+  if (insertInfo.loadInSidebar) {
+    PlacesUtils.annotations.setItemAnnotation(itemId,
+      SIDEBAR_ANNO, insertInfo.loadInSidebar, 0,
+      PlacesUtils.annotations.EXPIRE_NEVER);
+    item.loadInSidebar = insertInfo.loadInSidebar;
+  }
+
+  return item;
+});
+
+// Determines the Sync record kind for an existing bookmark.
+var getKindForItem = Task.async(function* (item) {
+  switch (item.type) {
+    case PlacesUtils.bookmarks.TYPE_FOLDER: {
+      let itemId = yield PlacesUtils.promiseItemId(item.guid);
+      let isLivemark = PlacesUtils.annotations.itemHasAnnotation(itemId,
+        PlacesUtils.LMANNO_FEEDURI);
+      return isLivemark ? BookmarkSyncUtils.KINDS.LIVEMARK :
+                          BookmarkSyncUtils.KINDS.FOLDER;
+    }
+    case PlacesUtils.bookmarks.TYPE_BOOKMARK:
+      return item.url.protocol == "place:" ?
+             BookmarkSyncUtils.KINDS.QUERY :
+             BookmarkSyncUtils.KINDS.BOOKMARK;
+
+    case PlacesUtils.bookmarks.TYPE_SEPARATOR:
+      return BookmarkSyncUtils.KINDS.SEPARATOR;
+  }
+  return null;
+});
+
+// Returns the `nsINavBookmarksService` bookmark type constant for a Sync
+// record kind.
+function getTypeForKind(kind) {
+  switch (kind) {
+    case BookmarkSyncUtils.KINDS.BOOKMARK:
+    case BookmarkSyncUtils.KINDS.MICROSUMMARY:
+    case BookmarkSyncUtils.KINDS.QUERY:
+      return PlacesUtils.bookmarks.TYPE_BOOKMARK;
+
+    case BookmarkSyncUtils.KINDS.FOLDER:
+    case BookmarkSyncUtils.KINDS.LIVEMARK:
+      return PlacesUtils.bookmarks.TYPE_FOLDER;
+
+    case BookmarkSyncUtils.KINDS.SEPARATOR:
+      return PlacesUtils.bookmarks.TYPE_SEPARATOR;
+  }
+  throw new Error(`Unknown bookmark kind: ${kind}`);
+}
+
+// Determines if a livemark should be reinserted. Returns true if `updateInfo`
+// specifies different feed or site URLs; false otherwise.
+var shouldReinsertLivemark = Task.async(function* (updateInfo) {
+  let hasFeed = updateInfo.hasOwnProperty("feed");
+  let hasSite = updateInfo.hasOwnProperty("site");
+  if (!hasFeed && !hasSite) {
+    return false;
+  }
+  let livemark = yield PlacesUtils.livemarks.getLivemark({
+    guid: updateInfo.guid,
+  });
+  if (hasFeed) {
+    let feedURI = PlacesUtils.toURI(updateInfo.feed);
+    if (!livemark.feedURI.equals(feedURI)) {
+      return true;
+    }
+  }
+  if (hasSite) {
+    if (!updateInfo.site) {
+      return !!livemark.siteURI;
+    }
+    let siteURI = PlacesUtils.toURI(updateInfo.site);
+    if (!livemark.siteURI || !siteURI.equals(livemark.siteURI)) {
+      return true;
+    }
+  }
+  return false;
+});
+
+var updateSyncBookmark = Task.async(function* (updateInfo) {
+  let oldItem = yield PlacesUtils.bookmarks.fetch(updateInfo.guid);
+  if (!oldItem) {
+    throw new Error(`Bookmark with GUID ${updateInfo.guid} does not exist`);
+  }
+
+  let shouldReinsert = false;
+  let oldKind = yield getKindForItem(oldItem);
+  if (updateInfo.hasOwnProperty("kind") && updateInfo.kind != oldKind) {
+    // If the item's aren't the same kind, we can't update the record;
+    // we must remove and reinsert.
+    shouldReinsert = true;
+    BookmarkSyncLog.warn(`updateSyncBookmark: Local ${
+      oldItem.guid} kind = (${oldKind}); remote ${
+      updateInfo.guid} kind = ${updateInfo.kind}. Deleting and recreating`);
+  } else if (oldKind == BookmarkSyncUtils.KINDS.LIVEMARK) {
+    // Similarly, if we're changing a livemark's site or feed URL, we need to
+    // reinsert.
+    shouldReinsert = yield shouldReinsertLivemark(updateInfo);
+    if (shouldReinsert) {
+      BookmarkSyncLog.debug(`updateSyncBookmark: Local ${
+        oldItem.guid} and remote ${
+        updateInfo.guid} livemarks have different URLs`);
+    }
+  }
+  if (shouldReinsert) {
+    delete updateInfo.source;
+    let newItem = validateNewBookmark(updateInfo);
+    yield PlacesUtils.bookmarks.remove(oldItem.guid);
+    // A reinsertion likely indicates a confused client, since there aren't
+    // public APIs for changing livemark URLs or an item's kind (e.g., turning
+    // a folder into a separator while preserving its annos and position).
+    // This might be a good case to repair later; for now, we assume Sync has
+    // passed a complete record for the new item, and don't try to merge
+    // `oldItem` with `updateInfo`.
+    return insertSyncBookmark(newItem);
+  }
+
+  let isOrphan = false, requestedParentGuid;
+  if (updateInfo.hasOwnProperty("parentGuid")) {
+    requestedParentGuid = updateInfo.parentGuid;
+    if (requestedParentGuid != oldItem.parentGuid) {
+      let oldId = yield PlacesUtils.promiseItemId(oldItem.guid);
+      if (PlacesUtils.isRootItem(oldId)) {
+        throw new Error(`Cannot move Places root ${oldId}`);
+      }
+      let parent = yield PlacesUtils.bookmarks.fetch(requestedParentGuid);
+      if (parent) {
+        BookmarkSyncLog.debug(`updateSyncBookmark: Item ${
+          updateInfo.guid} is not an orphan`);
+      } else {
+        // Don't move the item if the new parent doesn't exist. Instead, mark
+        // the item as an orphan. We'll annotate it with its real parent after
+        // updating.
+        BookmarkSyncLog.trace(`updateSyncBookmark: Item ${
+          updateInfo.guid} is an orphan: could not find parent ${
+          requestedParentGuid}`);
+        isOrphan = true;
+        delete updateInfo.parentGuid;
+      }
+      // If we're reparenting the item, pass the default index so that
+      // `PlacesUtils.bookmarks.update` doesn't throw. Sync will reorder
+      // children at the end of the sync.
+      updateInfo.index = PlacesUtils.bookmarks.DEFAULT_INDEX;
+    } else {
+      // `PlacesUtils.bookmarks.update` requires us to specify an index if we
+      // pass a parent, so we remove the parent if it's the same.
+      delete updateInfo.parentGuid;
+    }
+  }
+
+  updateInfo = yield updateTagQueryFolder(updateInfo);
+
+  let newItem = shouldUpdateBookmark(updateInfo) ?
+                yield PlacesUtils.bookmarks.update(updateInfo) : oldItem;
+  let itemId = yield PlacesUtils.promiseItemId(newItem.guid);
+
+  newItem = yield updateBookmarkMetadata(itemId, oldItem, newItem, updateInfo);
+
+  // If the item is an orphan, annotate it with its real parent ID.
+  if (isOrphan) {
+    yield annotateOrphan(newItem, requestedParentGuid);
+  }
+
+  // Reparent all orphans that expect this folder as the parent.
+  yield reparentOrphans(newItem);
+
+  return newItem;
+});
+
+var updateBookmarkMetadata = Task.async(function* (itemId, oldItem, newItem, updateInfo) {
+  try {
+    newItem.tags = yield tagItem(newItem, updateInfo.tags);
+  } catch (ex) {
+    BookmarkSyncLog.warn(`updateBookmarkMetadata: Error tagging item ${
+      newItem.guid}`, ex);
+  }
+
+  if (updateInfo.hasOwnProperty("keyword")) {
+    // Unconditionally remove the old keyword.
+    let entry = yield PlacesUtils.keywords.fetch({
+      url: oldItem.url.href,
+    });
+    if (entry) {
+      yield PlacesUtils.keywords.remove(entry.keyword);
+    }
+    if (updateInfo.keyword) {
+      yield PlacesUtils.keywords.insert({
+        keyword: updateInfo.keyword,
+        url: newItem.url.href,
+      });
+    }
+    newItem.keyword = updateInfo.keyword;
+  }
+
+  if (updateInfo.hasOwnProperty("description")) {
+    if (updateInfo.description) {
+      PlacesUtils.annotations.setItemAnnotation(itemId,
+        DESCRIPTION_ANNO, updateInfo.description, 0,
+        PlacesUtils.annotations.EXPIRE_NEVER);
+    } else {
+      PlacesUtils.annotations.removeItemAnnotation(itemId,
+        DESCRIPTION_ANNO);
+    }
+    newItem.description = updateInfo.description;
+  }
+
+  if (updateInfo.hasOwnProperty("loadInSidebar")) {
+    if (updateInfo.loadInSidebar) {
+      PlacesUtils.annotations.setItemAnnotation(itemId,
+        SIDEBAR_ANNO, updateInfo.loadInSidebar, 0,
+        PlacesUtils.annotations.EXPIRE_NEVER);
+    } else {
+      PlacesUtils.annotations.removeItemAnnotation(itemId,
+        SIDEBAR_ANNO);
+    }
+    newItem.loadInSidebar = updateInfo.loadInSidebar;
+  }
+
+  if (updateInfo.hasOwnProperty("query")) {
+    PlacesUtils.annotations.setItemAnnotation(itemId,
+      SMART_BOOKMARKS_ANNO, updateInfo.query, 0,
+      PlacesUtils.annotations.EXPIRE_NEVER);
+    newItem.query = updateInfo.query;
+  }
+
+  return newItem;
+});
+
+function generateGuid(db) {
+  return db.executeCached("SELECT GENERATE_GUID() AS guid").then(rows =>
+    rows[0].getResultByName("guid"));
+}
+
+function setGuids(guids) {
+  return PlacesUtils.withConnectionWrapper("BookmarkSyncUtils: setGuids",
+    db => db.executeTransaction(function* () {
+      let promises = [];
+      for (let [itemId, newGuid] of guids) {
+        promises.push(setGuid(db, itemId, newGuid));
+      }
+      return Promise.all(promises);
+    })
+  );
+}
+
+var setGuid = Task.async(function* (db, itemId, newGuid) {
+  yield db.executeCached(`UPDATE moz_bookmarks SET guid = :newGuid
+    WHERE id = :itemId`, { newGuid, itemId });
+  PlacesUtils.invalidateCachedGuidFor(itemId);
+  return newGuid;
+});
+
+function validateNewBookmark(info) {
+  let insertInfo = validateSyncBookmarkObject(info,
+    { kind: { required: true }
+    // Explicitly prevent callers from passing types.
+    , type: { validIf: () => false }
+    // Because Sync applies bookmarks as it receives them, it doesn't pass
+    // an index. Instead, Sync calls `BookmarkSyncUtils.order` at the end of
+    // the sync, which orders children according to their placement in the
+    // `BookmarkFolder::children` array.
+    , index: { validIf: () => false }
+    , guid: { required: true }
+    , url: { requiredIf: b => [ BookmarkSyncUtils.KINDS.BOOKMARK
+                              , BookmarkSyncUtils.KINDS.MICROSUMMARY
+                              , BookmarkSyncUtils.KINDS.QUERY ].includes(b.kind)
+           , validIf: b => [ BookmarkSyncUtils.KINDS.BOOKMARK
+                           , BookmarkSyncUtils.KINDS.MICROSUMMARY
+                           , BookmarkSyncUtils.KINDS.QUERY ].includes(b.kind) }
+    , parentGuid: { required: true }
+    , title: { validIf: b => [ BookmarkSyncUtils.KINDS.BOOKMARK
+                             , BookmarkSyncUtils.KINDS.MICROSUMMARY
+                             , BookmarkSyncUtils.KINDS.QUERY
+                             , BookmarkSyncUtils.KINDS.FOLDER
+                             , BookmarkSyncUtils.KINDS.LIVEMARK ].includes(b.kind) }
+    , query: { validIf: b => b.kind == BookmarkSyncUtils.KINDS.QUERY }
+    , folder: { validIf: b => b.kind == BookmarkSyncUtils.KINDS.QUERY }
+    , tags: { validIf: b => [ BookmarkSyncUtils.KINDS.BOOKMARK
+                            , BookmarkSyncUtils.KINDS.MICROSUMMARY
+                            , BookmarkSyncUtils.KINDS.QUERY ].includes(b.kind) }
+    , keyword: { validIf: b => [ BookmarkSyncUtils.KINDS.BOOKMARK
+                               , BookmarkSyncUtils.KINDS.MICROSUMMARY
+                               , BookmarkSyncUtils.KINDS.QUERY ].includes(b.kind) }
+    , description: { validIf: b => [ BookmarkSyncUtils.KINDS.BOOKMARK
+                                   , BookmarkSyncUtils.KINDS.MICROSUMMARY
+                                   , BookmarkSyncUtils.KINDS.QUERY
+                                   , BookmarkSyncUtils.KINDS.FOLDER
+                                   , BookmarkSyncUtils.KINDS.LIVEMARK ].includes(b.kind) }
+    , loadInSidebar: { validIf: b => [ BookmarkSyncUtils.KINDS.BOOKMARK
+                                     , BookmarkSyncUtils.KINDS.MICROSUMMARY ].includes(b.kind) }
+    , feed: { requiredIf: b => b.kind == BookmarkSyncUtils.KINDS.LIVEMARK
+            , validIf: b => b.kind == BookmarkSyncUtils.KINDS.LIVEMARK }
+    , site: { validIf: b => b.kind == BookmarkSyncUtils.KINDS.LIVEMARK }
+    });
+
+  // Sync doesn't track modification times, so use the default.
+  let time = new Date();
+  insertInfo.dateAdded = insertInfo.lastModified = time;
+
+  insertInfo.type = getTypeForKind(insertInfo.kind);
+
+  return insertInfo;
+}
+
+function findAnnoItems(anno, val) {
+  let annos = PlacesUtils.annotations;
+  return annos.getItemsWithAnnotation(anno, {}).filter(id =>
+    annos.getItemAnnotation(id, anno) == val);
+}
+
+var tagItem = Task.async(function (item, tags) {
+  if (!item.url) {
+    return [];
+  }
+
+  // Remove leading and trailing whitespace, then filter out empty tags.
+  let newTags = tags.map(tag => tag.trim()).filter(Boolean);
+
+  // Removing the last tagged item will also remove the tag. To preserve
+  // tag IDs, we temporarily tag a dummy URI, ensuring the tags exist.
+  let dummyURI = PlacesUtils.toURI("about:weave#BStore_tagURI");
+  let bookmarkURI = PlacesUtils.toURI(item.url.href);
+  PlacesUtils.tagging.tagURI(dummyURI, newTags);
+  PlacesUtils.tagging.untagURI(bookmarkURI, null);
+  PlacesUtils.tagging.tagURI(bookmarkURI, newTags);
+  PlacesUtils.tagging.untagURI(dummyURI, null);
+
+  return newTags;
+});
+
+// `PlacesUtils.bookmarks.update` checks if we've supplied enough properties,
+// but doesn't know about additional Sync record properties. We check this to
+// avoid having it throw in case we only pass Sync-specific properties, like
+// `{ guid, tags }`.
+function shouldUpdateBookmark(updateInfo) {
+  let propsToUpdate = 0;
+  for (let prop in PlacesUtils.BOOKMARK_VALIDATORS) {
+    if (!updateInfo.hasOwnProperty(prop)) {
+      continue;
+    }
+    // We should have at least one more property, in addition to `guid`.
+    if (++propsToUpdate >= 2) {
+      return true;
+    }
+  }
+  return false;
+}
+
+var getTagFolder = Task.async(function* (tag) {
+  let db = yield PlacesUtils.promiseDBConnection();
+  let results = yield db.executeCached(`SELECT id FROM moz_bookmarks
+    WHERE parent = :tagsFolder AND title = :tag LIMIT 1`,
+    { tagsFolder: PlacesUtils.bookmarks.tagsFolder, tag });
+  return results.length ? results[0].getResultByName("id") : null;
+});
+
+var getOrCreateTagFolder = Task.async(function* (tag) {
+  let id = yield getTagFolder(tag);
+  if (id) {
+    return id;
+  }
+  // Create the tag if it doesn't exist.
+  let item = yield PlacesUtils.bookmarks.insert({
+    type: PlacesUtils.bookmarks.TYPE_FOLDER,
+    parentGuid: PlacesUtils.bookmarks.tagsGuid,
+    title: tag,
+  });
+  return PlacesUtils.promiseItemId(item.guid);
+});
--- a/toolkit/components/places/PlacesUtils.jsm
+++ b/toolkit/components/places/PlacesUtils.jsm
@@ -46,16 +46,18 @@ XPCOMUtils.defineLazyModuleGetter(this, 
 XPCOMUtils.defineLazyModuleGetter(this, "Deprecated",
                                   "resource://gre/modules/Deprecated.jsm");
 XPCOMUtils.defineLazyModuleGetter(this, "Bookmarks",
                                   "resource://gre/modules/Bookmarks.jsm");
 XPCOMUtils.defineLazyModuleGetter(this, "History",
                                   "resource://gre/modules/History.jsm");
 XPCOMUtils.defineLazyModuleGetter(this, "AsyncShutdown",
                                   "resource://gre/modules/AsyncShutdown.jsm");
+XPCOMUtils.defineLazyModuleGetter(this, "PlacesSyncUtils",
+                                  "resource://gre/modules/PlacesSyncUtils.jsm");
 
 // The minimum amount of transactions before starting a batch. Usually we do
 // do incremental updates, a batch will cause views to completely
 // refresh instead.
 const MIN_TRANSACTIONS_FOR_BATCH = 5;
 
 // On Mac OSX, the transferable system converts "\r\n" to "\n\n", where
 // we really just want "\n". On other platforms, the transferable system
@@ -206,16 +208,87 @@ function serializeNode(aNode, aIsLivemar
       throw new Error("Unexpected node type");
 
     data.type = PlacesUtils.TYPE_X_MOZ_PLACE_SEPARATOR;
   }
 
   return JSON.stringify(data);
 }
 
+// Imposed to limit database size.
+const DB_URL_LENGTH_MAX = 65536;
+const DB_TITLE_LENGTH_MAX = 4096;
+
+/**
+ * List of bookmark object validators, one per each known property.
+ * Validators must throw if the property value is invalid and return a fixed up
+ * version of the value, if needed.
+ */
+const BOOKMARK_VALIDATORS = Object.freeze({
+  guid: simpleValidateFunc(v => PlacesUtils.isValidGuid(v)),
+  parentGuid: simpleValidateFunc(v => typeof(v) == "string" &&
+                                      /^[a-zA-Z0-9\-_]{12}$/.test(v)),
+  index: simpleValidateFunc(v => Number.isInteger(v) &&
+                                 v >= PlacesUtils.bookmarks.DEFAULT_INDEX),
+  dateAdded: simpleValidateFunc(v => v.constructor.name == "Date"),
+  lastModified: simpleValidateFunc(v => v.constructor.name == "Date"),
+  type: simpleValidateFunc(v => Number.isInteger(v) &&
+                                [ PlacesUtils.bookmarks.TYPE_BOOKMARK
+                                , PlacesUtils.bookmarks.TYPE_FOLDER
+                                , PlacesUtils.bookmarks.TYPE_SEPARATOR ].includes(v)),
+  title: v => {
+    simpleValidateFunc(val => val === null || typeof(val) == "string").call(this, v);
+    if (!v)
+      return null;
+    return v.slice(0, DB_TITLE_LENGTH_MAX);
+  },
+  url: v => {
+    simpleValidateFunc(val => (typeof(val) == "string" && val.length <= DB_URL_LENGTH_MAX) ||
+                              (val instanceof Ci.nsIURI && val.spec.length <= DB_URL_LENGTH_MAX) ||
+                              (val instanceof URL && val.href.length <= DB_URL_LENGTH_MAX)
+                      ).call(this, v);
+    if (typeof(v) === "string")
+      return new URL(v);
+    if (v instanceof Ci.nsIURI)
+      return new URL(v.spec);
+    return v;
+  }
+});
+
+// Sync bookmark records can contain additional properties.
+const SYNC_BOOKMARK_VALIDATORS = Object.freeze(Object.assign({
+  // Sync uses kinds instead of types, which distinguish between livemarks
+  // and smart bookmarks.
+  kind: simpleValidateFunc(v => typeof v == "string" &&
+                                Object.values(PlacesSyncUtils.bookmarks.KINDS).includes(v)),
+  query: simpleValidateFunc(v => v === null || (typeof v == "string" && v)),
+  folder: simpleValidateFunc(v => typeof v == "string" && v &&
+                                  v.length <= Ci.nsITaggingService.MAX_TAG_LENGTH),
+  tags: v => {
+    if (v === null) {
+      return [];
+    }
+    if (!Array.isArray(v)) {
+      throw new Error("Invalid tag array");
+    }
+    for (let tag of v) {
+      if (typeof tag != "string" || !tag ||
+          tag.length > Ci.nsITaggingService.MAX_TAG_LENGTH) {
+        throw new Error(`Invalid tag: ${tag}`);
+      }
+    }
+    return v;
+  },
+  keyword: simpleValidateFunc(v => v === null || typeof v == "string"),
+  description: simpleValidateFunc(v => v === null || typeof v == "string"),
+  loadInSidebar: simpleValidateFunc(v => v === true || v === false),
+  feed: BOOKMARK_VALIDATORS.url,
+  site: v => v === null ? v : BOOKMARK_VALIDATORS.url(v),
+}, BOOKMARK_VALIDATORS));
+
 this.PlacesUtils = {
   // Place entries that are containers, e.g. bookmark folders or queries.
   TYPE_X_MOZ_PLACE_CONTAINER: "text/x-moz-place-container",
   // Place entries that are bookmark separators.
   TYPE_X_MOZ_PLACE_SEPARATOR: "text/x-moz-place-separator",
   // Place entries that are not containers or separators
   TYPE_X_MOZ_PLACE: "text/x-moz-place",
   // Place entries in shortcut url format (url\ntitle)
@@ -262,17 +335,18 @@ this.PlacesUtils = {
 
   /**
    * Is a string a valid GUID?
    *
    * @param guid: (String)
    * @return (Boolean)
    */
   isValidGuid(guid) {
-    return (/^[a-zA-Z0-9\-_]{12}$/.test(guid));
+    return typeof guid == "string" && guid &&
+           (/^[a-zA-Z0-9\-_]{12}$/.test(guid));
   },
 
   /**
    * Converts a string or n URL object to an nsIURI.
    *
    * @param url (URL) or (String)
    *        the URL to convert.
    * @return nsIURI for the given URL.
@@ -403,16 +477,85 @@ this.PlacesUtils = {
   nodeAncestors: function* PU_nodeAncestors(aNode) {
     let node = aNode.parent;
     while (node) {
       yield node;
       node = node.parent;
     }
   },
 
+  /**
+   * Checks validity of an object, filling up default values for optional
+   * properties.
+   *
+   * @param validators (object)
+   *        An object containing input validators. Keys should be field names;
+   *        values should be validation functions.
+   * @param props (object)
+   *        The object to validate.
+   * @param behavior (object) [optional]
+   *        Object defining special behavior for some of the properties.
+   *        The following behaviors may be optionally set:
+   *         - requiredIf: if the provided condition is satisfied, then this
+   *                       property is required.
+   *         - validIf: if the provided condition is not satisfied, then this
+   *                    property is invalid.
+   *         - defaultValue: an undefined property should default to this value.
+   *
+   * @return a validated and normalized item.
+   * @throws if the object contains invalid data.
+   * @note any unknown properties are pass-through.
+   */
+  validateItemProperties(validators, props, behavior={}) {
+    if (!props)
+      throw new Error("Input should be a valid object");
+    // Make a shallow copy of `props` to avoid mutating the original object
+    // when filling in defaults.
+    let input = Object.assign({}, props);
+    let normalizedInput = {};
+    let required = new Set();
+    for (let prop in behavior) {
+      if (behavior[prop].hasOwnProperty("required") && behavior[prop].required) {
+        required.add(prop);
+      }
+      if (behavior[prop].hasOwnProperty("requiredIf") && behavior[prop].requiredIf(input)) {
+        required.add(prop);
+      }
+      if (behavior[prop].hasOwnProperty("validIf") && input[prop] !== undefined &&
+          !behavior[prop].validIf(input)) {
+        throw new Error(`Invalid value for property '${prop}': ${input[prop]}`);
+      }
+      if (behavior[prop].hasOwnProperty("defaultValue") && input[prop] === undefined) {
+        input[prop] = behavior[prop].defaultValue;
+      }
+    }
+
+    for (let prop in input) {
+      if (required.has(prop)) {
+        required.delete(prop);
+      } else if (input[prop] === undefined) {
+        // Skip undefined properties that are not required.
+        continue;
+      }
+      if (validators.hasOwnProperty(prop)) {
+        try {
+          normalizedInput[prop] = validators[prop](input[prop], input);
+        } catch (ex) {
+          throw new Error(`Invalid value for property '${prop}': ${input[prop]}`);
+        }
+      }
+    }
+    if (required.size > 0)
+      throw new Error(`The following properties were expected: ${[...required].join(", ")}`);
+    return normalizedInput;
+  },
+
+  BOOKMARK_VALIDATORS,
+  SYNC_BOOKMARK_VALIDATORS,
+
   QueryInterface: XPCOMUtils.generateQI([
     Ci.nsIObserver
   , Ci.nsITransactionListener
   ]),
 
   _shutdownFunctions: [],
   registerShutdownFunction: function PU_registerShutdownFunction(aFunc)
   {
@@ -3606,8 +3749,24 @@ PlacesUntagURITransaction.prototype = {
     PlacesUtils.tagging.untagURI(this.item.uri, this.item.tags);
   },
 
   undoTransaction: function UTUTXN_undoTransaction()
   {
     PlacesUtils.tagging.tagURI(this.item.uri, this.item.tags);
   }
 };
+
+/**
+ * Executes a boolean validate function, throwing if it returns false.
+ *
+ * @param boolValidateFn
+ *        A boolean validate function.
+ * @return the input value.
+ * @throws if input doesn't pass the validate function.
+ */
+function simpleValidateFunc(boolValidateFn) {
+  return (v, input) => {
+    if (!boolValidateFn(v, input))
+      throw new Error("Invalid value");
+    return v;
+  };
+}
--- a/toolkit/components/places/moz.build
+++ b/toolkit/components/places/moz.build
@@ -64,16 +64,17 @@ if CONFIG['MOZ_PLACES']:
         'ClusterLib.js',
         'ColorAnalyzer_worker.js',
         'ColorConversion.js',
         'History.jsm',
         'PlacesBackups.jsm',
         'PlacesDBUtils.jsm',
         'PlacesRemoteTabsAutocompleteProvider.jsm',
         'PlacesSearchAutocompleteProvider.jsm',
+        'PlacesSyncUtils.jsm',
         'PlacesTransactions.jsm',
         'PlacesUtils.jsm',
     ]
 
     EXTRA_COMPONENTS += [
         'ColorAnalyzer.js',
         'nsLivemarkService.js',
         'nsPlacesExpiration.js',
new file mode 100644
--- /dev/null
+++ b/toolkit/components/places/tests/unit/livemark.xml
@@ -0,0 +1,17 @@
+<?xml version="1.0" encoding="utf-8"?>
+<feed xmlns="http://www.w3.org/2005/Atom">
+  <title>Livemark Feed</title>
+  <link href="https://example.com/"/>
+  <updated>2016-08-09T19:51:45.147Z</updated>
+  <author>
+    <name>John Doe</name>
+  </author>
+  <id>urn:uuid:e7947414-6ee0-4009-ae75-8b0ad3c6894b</id>
+  <entry>
+    <title>Some awesome article</title>
+    <link href="https://example.com/some-article"/>
+    <id>urn:uuid:d72ce019-0a56-4a0b-ac03-f66117d78141</id>
+    <updated>2016-08-09T19:57:22.178Z</updated>
+    <summary>My great article summary.</summary>
+  </entry>
+</feed>
new file mode 100644
--- /dev/null
+++ b/toolkit/components/places/tests/unit/test_sync_utils.js
@@ -0,0 +1,1093 @@
+Cu.import("resource://gre/modules/PlacesSyncUtils.jsm");
+Cu.import("resource://testing-common/httpd.js");
+Cu.importGlobalProperties(["crypto", "URLSearchParams"]);
+
+const DESCRIPTION_ANNO = "bookmarkProperties/description";
+const LOAD_IN_SIDEBAR_ANNO = "bookmarkProperties/loadInSidebar";
+const SYNC_PARENT_ANNO = "sync/parent";
+
+function makeGuid() {
+  return ChromeUtils.base64URLEncode(crypto.getRandomValues(new Uint8Array(9)), {
+    pad: false,
+  });
+}
+
+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;
+}
+
+function compareAscending(a, b) {
+  if (a > b) {
+    return 1;
+  }
+  if (a < b) {
+    return -1;
+  }
+  return 0;
+}
+
+function assertTagForURLs(tag, urls, message) {
+  let taggedURLs = PlacesUtils.tagging.getURIsForTag(tag).map(uri => uri.spec);
+  deepEqual(taggedURLs.sort(compareAscending), urls.sort(compareAscending), message);
+}
+
+function assertURLHasTags(url, tags, message) {
+  let actualTags = PlacesUtils.tagging.getTagsForURI(uri(url));
+  deepEqual(actualTags.sort(compareAscending), tags, message);
+}
+
+var populateTree = Task.async(function* populate(parentGuid, ...items) {
+  let guids = {};
+
+  for (let index = 0; index < items.length; index++) {
+    let item = items[index];
+    let guid = makeGuid();
+
+    switch (item.kind) {
+      case "bookmark":
+      case "query":
+        yield PlacesUtils.bookmarks.insert({
+          type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+          url: item.url,
+          title: item.title,
+          parentGuid, guid, index,
+        });
+        break;
+
+      case "separator":
+        yield PlacesUtils.bookmarks.insert({
+          type: PlacesUtils.bookmarks.TYPE_SEPARATOR,
+          parentGuid, guid,
+        });
+        break;
+
+      case "folder":
+        yield PlacesUtils.bookmarks.insert({
+          type: PlacesUtils.bookmarks.TYPE_FOLDER,
+          title: item.title,
+          parentGuid, guid,
+        });
+        if (item.children) {
+          Object.assign(guids, yield* populate(guid, ...item.children));
+        }
+        break;
+
+      default:
+        throw new Error(`Unsupported item type: ${item.type}`);
+    }
+
+    if (item.exclude) {
+      let itemId = yield PlacesUtils.promiseItemId(guid);
+      PlacesUtils.annotations.setItemAnnotation(
+        itemId, PlacesUtils.EXCLUDE_FROM_BACKUP_ANNO, "Don't back this up", 0,
+        PlacesUtils.annotations.EXPIRE_NEVER);
+    }
+
+    guids[item.title] = guid;
+  }
+
+  return guids;
+});
+
+function* insertWithoutGuid(info) {
+  let item = yield PlacesUtils.bookmarks.insert(info);
+  let id = yield PlacesUtils.promiseItemId(item.guid);
+
+  // All Places methods ensure we specify a valid GUID, so we insert
+  // an item and remove its GUID by modifying the DB directly.
+  yield PlacesUtils.withConnectionWrapper(
+    "test_sync_utils: insertWithoutGuid", db => db.executeCached(
+      `UPDATE moz_bookmarks SET guid = NULL WHERE guid = :guid`,
+      { guid: item.guid }
+    )
+  );
+  PlacesUtils.invalidateCachedGuidFor(id);
+
+  return { id, item };
+}
+
+add_task(function* test_order() {
+  do_print("Insert some bookmarks");
+  let guids = yield populateTree(PlacesUtils.bookmarks.menuGuid, {
+    kind: "bookmark",
+    title: "childBmk",
+    url: "http://getfirefox.com",
+  }, {
+    kind: "bookmark",
+    title: "siblingBmk",
+    url: "http://getthunderbird.com",
+  }, {
+    kind: "folder",
+    title: "siblingFolder",
+  }, {
+    kind: "separator",
+    title: "siblingSep",
+  });
+
+  do_print("Reorder inserted bookmarks");
+  {
+    let order = [guids.siblingFolder, guids.siblingSep, guids.childBmk,
+      guids.siblingBmk];
+    yield PlacesSyncUtils.bookmarks.order(PlacesUtils.bookmarks.menuGuid, order);
+    let childGuids = yield PlacesSyncUtils.bookmarks.fetchChildGuids(PlacesUtils.bookmarks.menuGuid);
+    deepEqual(childGuids, order, "New bookmarks should be reordered according to array");
+  }
+
+  do_print("Reorder with unspecified children");
+  {
+    yield PlacesSyncUtils.bookmarks.order(PlacesUtils.bookmarks.menuGuid, [
+      guids.siblingSep, guids.siblingBmk,
+    ]);
+    let childGuids = yield PlacesSyncUtils.bookmarks.fetchChildGuids(
+      PlacesUtils.bookmarks.menuGuid);
+    deepEqual(childGuids, [guids.siblingSep, guids.siblingBmk,
+      guids.siblingFolder, guids.childBmk],
+      "Unordered children should be moved to end");
+  }
+
+  do_print("Reorder with nonexistent children");
+  {
+    yield PlacesSyncUtils.bookmarks.order(PlacesUtils.bookmarks.menuGuid, [
+      guids.childBmk, makeGuid(), guids.siblingBmk, guids.siblingSep,
+      makeGuid(), guids.siblingFolder, makeGuid()]);
+    let childGuids = yield PlacesSyncUtils.bookmarks.fetchChildGuids(
+      PlacesUtils.bookmarks.menuGuid);
+    deepEqual(childGuids, [guids.childBmk, guids.siblingBmk, guids.siblingSep,
+      guids.siblingFolder], "Nonexistent children should be ignored");
+  }
+
+  yield PlacesUtils.bookmarks.eraseEverything();
+});
+
+add_task(function* test_fetchChildGuids_ensure_guids() {
+  let firstWithGuid = yield PlacesUtils.bookmarks.insert({
+    parentGuid: PlacesUtils.bookmarks.menuGuid,
+    type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+    url: "https://mozilla.org",
+  });
+
+  let { item: secondWithoutGuid } = yield* insertWithoutGuid({
+    parentGuid: PlacesUtils.bookmarks.menuGuid,
+    type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+    url: "https://example.com",
+  });
+
+  let thirdWithGuid = yield PlacesUtils.bookmarks.insert({
+    parentGuid: PlacesUtils.bookmarks.menuGuid,
+    type: PlacesUtils.bookmarks.TYPE_FOLDER,
+  });
+
+  do_print("Children without a GUID should be assigned one");
+  let childGuids = yield PlacesSyncUtils.bookmarks.fetchChildGuids(
+    PlacesUtils.bookmarks.menuGuid);
+  equal(childGuids.length, 3, "Should include all children");
+  equal(childGuids[0], firstWithGuid.guid,
+    "Should include first child GUID");
+  notEqual(childGuids[1], secondWithoutGuid.guid,
+    "Should assign new GUID to second child");
+  equal(childGuids[2], thirdWithGuid.guid,
+    "Should include third child GUID");
+
+  yield PlacesUtils.bookmarks.eraseEverything();
+});
+
+add_task(function* test_ensureGuidForId_invalid() {
+  yield rejects(PlacesSyncUtils.bookmarks.ensureGuidForId(-1),
+    "Should reject invalid item IDs");
+
+  let item = yield PlacesUtils.bookmarks.insert({
+    parentGuid: PlacesUtils.bookmarks.menuGuid,
+    type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+    url: "https://mozilla.org",
+  });
+  let id = yield PlacesUtils.promiseItemId(item.guid);
+  yield PlacesUtils.bookmarks.remove(item);
+  yield rejects(PlacesSyncUtils.bookmarks.ensureGuidForId(id),
+    "Should reject nonexistent item IDs");
+});
+
+add_task(function* test_ensureGuidForId() {
+  do_print("Item with GUID");
+  {
+    let item = yield PlacesUtils.bookmarks.insert({
+      parentGuid: PlacesUtils.bookmarks.menuGuid,
+      type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+      url: "https://mozilla.org",
+    });
+    let id = yield PlacesUtils.promiseItemId(item.guid);
+    let guid = yield PlacesSyncUtils.bookmarks.ensureGuidForId(id);
+    equal(guid, item.guid, "Should return GUID if one exists");
+  }
+
+  do_print("Item without GUID");
+  {
+    let { id, item } = yield* insertWithoutGuid({
+      parentGuid: PlacesUtils.bookmarks.menuGuid,
+      type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+      url: "https://example.com",
+    });
+    let guid = yield PlacesSyncUtils.bookmarks.ensureGuidForId(id);
+    notEqual(guid, item.guid, "Should assign new GUID to item without one");
+    equal(yield PlacesUtils.promiseItemGuid(id), guid,
+      "Should map ID to new GUID");
+    equal(yield PlacesUtils.promiseItemId(guid), id,
+      "Should map new GUID to ID");
+  }
+
+  yield PlacesUtils.bookmarks.eraseEverything();
+});
+
+add_task(function* test_changeGuid_invalid() {
+  yield rejects(PlacesSyncUtils.bookmarks.changeGuid(makeGuid()),
+    "Should require a new GUID");
+  yield rejects(PlacesSyncUtils.bookmarks.changeGuid(makeGuid(), "!@#$"),
+    "Should reject invalid GUIDs");
+  yield rejects(PlacesSyncUtils.bookmarks.changeGuid(makeGuid(), makeGuid()),
+    "Should reject nonexistent item GUIDs");
+  yield rejects(
+    PlacesSyncUtils.bookmarks.changeGuid(PlacesUtils.bookmarks.menuGuid,
+      makeGuid()),
+    "Should reject roots");
+});
+
+add_task(function* test_changeGuid() {
+  let item = yield PlacesUtils.bookmarks.insert({
+    parentGuid: PlacesUtils.bookmarks.menuGuid,
+    type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+    url: "https://mozilla.org",
+  });
+  let id = yield PlacesUtils.promiseItemId(item.guid);
+
+  let newGuid = makeGuid();
+  let result = yield PlacesSyncUtils.bookmarks.changeGuid(item.guid, newGuid);
+  equal(result, newGuid, "Should return new GUID");
+
+  equal(yield PlacesUtils.promiseItemId(newGuid), id, "Should map ID to new GUID");
+  yield rejects(PlacesUtils.promiseItemId(item.guid), "Should not map ID to old GUID");
+  equal(yield PlacesUtils.promiseItemGuid(id), newGuid, "Should map new GUID to ID");
+});
+
+add_task(function* test_order_roots() {
+  let oldOrder = yield PlacesSyncUtils.bookmarks.fetchChildGuids(
+    PlacesUtils.bookmarks.rootGuid);
+  yield PlacesSyncUtils.bookmarks.order(PlacesUtils.bookmarks.rootGuid,
+    shuffle(oldOrder));
+  let newOrder = yield PlacesSyncUtils.bookmarks.fetchChildGuids(
+    PlacesUtils.bookmarks.rootGuid);
+  deepEqual(oldOrder, newOrder, "Should ignore attempts to reorder roots");
+
+  yield PlacesUtils.bookmarks.eraseEverything();
+});
+
+add_task(function* test_update_tags() {
+  do_print("Insert item without tags");
+  let item = yield PlacesSyncUtils.bookmarks.insert({
+    kind: "bookmark",
+    url: "https://mozilla.org",
+    guid: makeGuid(),
+    parentGuid: PlacesUtils.bookmarks.menuGuid,
+  });
+
+  do_print("Add tags");
+  {
+    let updatedItem = yield PlacesSyncUtils.bookmarks.update({
+      guid: item.guid,
+      tags: ["foo", "bar"],
+    });
+    deepEqual(updatedItem.tags, ["foo", "bar"], "Should return new tags");
+    assertURLHasTags("https://mozilla.org", ["bar", "foo"],
+      "Should set new tags for URL");
+  }
+
+  do_print("Add new tag, remove existing tag");
+  {
+    let updatedItem = yield PlacesSyncUtils.bookmarks.update({
+      guid: item.guid,
+      tags: ["foo", "baz"],
+    });
+    deepEqual(updatedItem.tags, ["foo", "baz"], "Should return updated tags");
+    assertURLHasTags("https://mozilla.org", ["baz", "foo"],
+      "Should update tags for URL");
+    assertTagForURLs("bar", [], "Should remove existing tag");
+  }
+
+  do_print("Tags with whitespace");
+  {
+    let updatedItem = yield PlacesSyncUtils.bookmarks.update({
+      guid: item.guid,
+      tags: [" leading", "trailing ", " baz ", " "],
+    });
+    deepEqual(updatedItem.tags, ["leading", "trailing", "baz"],
+      "Should return filtered tags");
+    assertURLHasTags("https://mozilla.org", ["baz", "leading", "trailing"],
+      "Should trim whitespace and filter blank tags");
+  }
+
+  do_print("Remove all tags");
+  {
+    let updatedItem = yield PlacesSyncUtils.bookmarks.update({
+      guid: item.guid,
+      tags: null,
+    });
+    deepEqual(updatedItem.tags, [], "Should return empty tag array");
+    assertURLHasTags("https://mozilla.org", [],
+      "Should remove all existing tags");
+  }
+
+  yield PlacesUtils.bookmarks.eraseEverything();
+});
+
+add_task(function* test_update_keyword() {
+  do_print("Insert item without keyword");
+  let item = yield PlacesSyncUtils.bookmarks.insert({
+    kind: "bookmark",
+    parentGuid: PlacesUtils.bookmarks.menuGuid,
+    url: "https://mozilla.org",
+    guid: makeGuid(),
+  });
+
+  do_print("Add item keyword");
+  {
+    let updatedItem = yield PlacesSyncUtils.bookmarks.update({
+      guid: item.guid,
+      keyword: "moz",
+    });
+    equal(updatedItem.keyword, "moz", "Should return new keyword");
+    let entryByKeyword = yield PlacesUtils.keywords.fetch("moz");
+    equal(entryByKeyword.url.href, "https://mozilla.org/",
+      "Should set new keyword for URL");
+    let entryByURL = yield PlacesUtils.keywords.fetch({
+      url: "https://mozilla.org",
+    });
+    equal(entryByURL.keyword, "moz", "Looking up URL should return new keyword");
+  }
+
+  do_print("Change item keyword");
+  {
+    let updatedItem = yield PlacesSyncUtils.bookmarks.update({
+      guid: item.guid,
+      keyword: "m",
+    });
+    equal(updatedItem.keyword, "m", "Should return updated keyword");
+    let newEntry = yield PlacesUtils.keywords.fetch("m");
+    equal(newEntry.url.href, "https://mozilla.org/", "Should update keyword for URL");
+    let oldEntry = yield PlacesUtils.keywords.fetch("moz");
+    ok(!oldEntry, "Should remove old keyword");
+  }
+
+  do_print("Remove existing keyword");
+  {
+    let updatedItem = yield PlacesSyncUtils.bookmarks.update({
+      guid: item.guid,
+      keyword: null,
+    });
+    ok(!updatedItem.keyword,
+      "Should not include removed keyword in properties");
+    let entry = yield PlacesUtils.keywords.fetch({
+      url: "https://mozilla.org",
+    });
+    ok(!entry, "Should remove new keyword from URL");
+  }
+
+  do_print("Remove keyword for item without keyword");
+  {
+    yield PlacesSyncUtils.bookmarks.update({
+      guid: item.guid,
+      keyword: null,
+    });
+    let entry = yield PlacesUtils.keywords.fetch({
+      url: "https://mozilla.org",
+    });
+    ok(!entry,
+      "Removing keyword for URL without existing keyword should succeed");
+  }
+
+  yield PlacesUtils.bookmarks.eraseEverything();
+});
+
+add_task(function* test_update_annos() {
+  let guids = yield populateTree(PlacesUtils.bookmarks.menuGuid, {
+    kind: "folder",
+    title: "folder",
+    description: "Folder description",
+  }, {
+    kind: "bookmark",
+    title: "bmk",
+    url: "https://example.com",
+    description: "Bookmark description",
+    loadInSidebar: true,
+  });
+
+  do_print("Add folder description");
+  {
+    let updatedItem = yield PlacesSyncUtils.bookmarks.update({
+      guid: guids.folder,
+      description: "Folder description",
+    });
+    equal(updatedItem.description, "Folder description",
+      "Should return new description");
+    let id = yield PlacesUtils.promiseItemId(updatedItem.guid);
+    equal(PlacesUtils.annotations.getItemAnnotation(id, DESCRIPTION_ANNO),
+      "Folder description", "Should set description anno");
+  }
+
+  do_print("Clear folder description");
+  {
+    let updatedItem = yield PlacesSyncUtils.bookmarks.update({
+      guid: guids.folder,
+      description: null,
+    });
+    ok(!updatedItem.description, "Should not return cleared description");
+    let id = yield PlacesUtils.promiseItemId(updatedItem.guid);
+    ok(!PlacesUtils.annotations.itemHasAnnotation(id, DESCRIPTION_ANNO),
+      "Should remove description anno");
+  }
+
+  do_print("Add bookmark sidebar anno");
+  {
+    let updatedItem = yield PlacesSyncUtils.bookmarks.update({
+      guid: guids.bmk,
+      loadInSidebar: true,
+    });
+    ok(updatedItem.loadInSidebar, "Should return sidebar anno");
+    let id = yield PlacesUtils.promiseItemId(updatedItem.guid);
+    ok(PlacesUtils.annotations.itemHasAnnotation(id, LOAD_IN_SIDEBAR_ANNO),
+      "Should set sidebar anno for existing bookmark");
+  }
+
+  do_print("Clear bookmark sidebar anno");
+  {
+    let updatedItem = yield PlacesSyncUtils.bookmarks.update({
+      guid: guids.bmk,
+      loadInSidebar: false,
+    });
+    ok(!updatedItem.loadInSidebar, "Should not return cleared sidebar anno");
+    let id = yield PlacesUtils.promiseItemId(updatedItem.guid);
+    ok(!PlacesUtils.annotations.itemHasAnnotation(id, LOAD_IN_SIDEBAR_ANNO),
+      "Should clear sidebar anno for existing bookmark");
+  }
+
+  yield PlacesUtils.bookmarks.eraseEverything();
+});
+
+add_task(function* test_update_move_root() {
+  do_print("Move root to same parent");
+  {
+    // This should be a no-op.
+    let sameRoot = yield PlacesSyncUtils.bookmarks.update({
+      guid: PlacesUtils.bookmarks.menuGuid,
+      parentGuid: PlacesUtils.bookmarks.rootGuid,
+    });
+    equal(sameRoot.guid, PlacesUtils.bookmarks.menuGuid,
+      "Menu root GUID should not change");
+    equal(sameRoot.parentGuid, PlacesUtils.bookmarks.rootGuid,
+      "Parent Places root GUID should not change");
+  }
+
+  do_print("Try reparenting root");
+  yield rejects(PlacesSyncUtils.bookmarks.update({
+    guid: PlacesUtils.bookmarks.menuGuid,
+    parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+  }));
+
+  yield PlacesUtils.bookmarks.eraseEverything();
+});
+
+add_task(function* test_insert() {
+  do_print("Insert bookmark");
+  {
+    let item = yield PlacesSyncUtils.bookmarks.insert({
+      kind: "bookmark",
+      guid: makeGuid(),
+      parentGuid: PlacesUtils.bookmarks.menuGuid,
+      url: "https://example.org",
+    });
+    equal(item.type, PlacesUtils.bookmarks.TYPE_BOOKMARK,
+      "Bookmark should have correct type");
+  }
+
+  do_print("Insert query");
+  {
+    let item = yield PlacesSyncUtils.bookmarks.insert({
+      kind: "query",
+      guid: makeGuid(),
+      parentGuid: PlacesUtils.bookmarks.menuGuid,
+      url: "place:terms=term&folder=TOOLBAR&queryType=1",
+      folder: "Saved search",
+    });
+    equal(item.type, PlacesUtils.bookmarks.TYPE_BOOKMARK,
+      "Queries should be stored as bookmarks");
+  }
+
+  do_print("Insert folder");
+  {
+    let item = yield PlacesSyncUtils.bookmarks.insert({
+      kind: "folder",
+      guid: makeGuid(),
+      parentGuid: PlacesUtils.bookmarks.menuGuid,
+      title: "New folder",
+    });
+    equal(item.type, PlacesUtils.bookmarks.TYPE_FOLDER,
+      "Folder should have correct type");
+  }
+
+  do_print("Insert separator");
+  {
+    let item = yield PlacesSyncUtils.bookmarks.insert({
+      kind: "separator",
+      guid: makeGuid(),
+      parentGuid: PlacesUtils.bookmarks.menuGuid,
+    });
+    equal(item.type, PlacesUtils.bookmarks.TYPE_SEPARATOR,
+      "Separator should have correct type");
+  }
+
+  yield PlacesUtils.bookmarks.eraseEverything();
+});
+
+add_task(function* test_insert_livemark() {
+  let { server, site, stopServer } = makeLivemarkServer();
+
+  try {
+    do_print("Insert livemark with feed URL");
+    {
+      let livemark = yield PlacesSyncUtils.bookmarks.insert({
+        kind: "livemark",
+        guid: makeGuid(),
+        feed: site + "/feed/1",
+        parentGuid: PlacesUtils.bookmarks.menuGuid,
+      });
+      let bmk = yield PlacesUtils.bookmarks.fetch({
+        guid: livemark.guid,
+      })
+      equal(bmk.type, PlacesUtils.bookmarks.TYPE_FOLDER,
+        "Livemarks should be stored as folders");
+    }
+
+    let livemarkGuid;
+    do_print("Insert livemark with site and feed URLs");
+    {
+      let livemark = yield PlacesSyncUtils.bookmarks.insert({
+        kind: "livemark",
+        guid: makeGuid(),
+        site,
+        feed: site + "/feed/1",
+        parentGuid: PlacesUtils.bookmarks.menuGuid,
+      });
+      livemarkGuid = livemark.guid;
+
+    }
+
+    do_print("Try inserting livemark into livemark");
+    {
+      let livemark = yield PlacesSyncUtils.bookmarks.insert({
+        kind: "livemark",
+        guid: makeGuid(),
+        site,
+        feed: site + "/feed/1",
+        parentGuid: livemarkGuid,
+      });
+      ok(!livemark, "Should not insert livemark as child of livemark");
+    }
+  } finally {
+    yield stopServer();
+  }
+
+  yield PlacesUtils.bookmarks.eraseEverything();
+});
+
+add_task(function* test_update_livemark() {
+  let { server, site, stopServer } = makeLivemarkServer();
+  let feedURI = uri(site + "/feed/1");
+
+  try {
+    // We shouldn't reinsert the livemark if the URLs are the same.
+    do_print("Update livemark with same URLs");
+    {
+      let livemark = yield PlacesUtils.livemarks.addLivemark({
+        parentGuid: PlacesUtils.bookmarks.menuGuid,
+        feedURI,
+        siteURI: uri(site),
+        index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+      });
+
+      yield PlacesSyncUtils.bookmarks.update({
+        guid: livemark.guid,
+        feed: feedURI,
+      });
+      // `nsLivemarkService` returns references to `Livemark` instances, so we
+      // can compare them with `==` to make sure they haven't been replaced.
+      equal(yield PlacesUtils.livemarks.getLivemark({
+        guid: livemark.guid,
+      }), livemark, "Livemark with same feed URL should not be replaced");
+
+      yield PlacesSyncUtils.bookmarks.update({
+        guid: livemark.guid,
+        site,
+      });
+      equal(yield PlacesUtils.livemarks.getLivemark({
+        guid: livemark.guid,
+      }), livemark, "Livemark with same site URL should not be replaced");
+
+      yield PlacesSyncUtils.bookmarks.update({
+        guid: livemark.guid,
+        feed: feedURI,
+        site,
+      });
+      equal(yield PlacesUtils.livemarks.getLivemark({
+        guid: livemark.guid,
+      }), livemark, "Livemark with same feed and site URLs should not be replaced");
+    }
+
+    do_print("Change livemark feed URL");
+    {
+      let livemark = yield PlacesUtils.livemarks.addLivemark({
+        parentGuid: PlacesUtils.bookmarks.menuGuid,
+        feedURI,
+        index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+      });
+
+      // Since we're reinserting, we need to pass all properties required
+      // for a new livemark. `update` won't merge the old and new ones.
+      yield rejects(PlacesSyncUtils.bookmarks.update({
+        guid: livemark.guid,
+        feed: site + "/feed/2",
+      }), "Reinserting livemark with changed feed URL requires full record");
+
+      let newLivemark = yield PlacesSyncUtils.bookmarks.update({
+        kind: "livemark",
+        parentGuid: PlacesUtils.bookmarks.menuGuid,
+        guid: livemark.guid,
+        feed: site + "/feed/2",
+      });
+      equal(newLivemark.guid, livemark.guid,
+        "GUIDs should match for reinserted livemark with changed feed URL");
+      equal(newLivemark.feedURI.spec, site + "/feed/2",
+        "Reinserted livemark should have changed feed URI");
+    }
+
+    do_print("Add livemark site URL");
+    {
+      let livemark = yield PlacesUtils.livemarks.addLivemark({
+        parentGuid: PlacesUtils.bookmarks.menuGuid,
+        feedURI,
+      });
+      ok(livemark.feedURI.equals(feedURI), "Livemark feed URI should match");
+      ok(!livemark.siteURI, "Livemark should not have site URI");
+
+      yield rejects(PlacesSyncUtils.bookmarks.update({
+        guid: livemark.guid,
+        site,
+      }), "Reinserting livemark with new site URL requires full record");
+
+      let newLivemark = yield PlacesSyncUtils.bookmarks.update({
+        kind: "livemark",
+        parentGuid: PlacesUtils.bookmarks.menuGuid,
+        guid: livemark.guid,
+        feed: feedURI,
+        site,
+      });
+      notEqual(newLivemark, livemark,
+        "Livemark with new site URL should replace old livemark");
+      equal(newLivemark.guid, livemark.guid,
+        "GUIDs should match for reinserted livemark with new site URL");
+      equal(newLivemark.siteURI.spec, site + "/",
+        "Reinserted livemark should have new site URI");
+      ok(newLivemark.feedURI.equals(feedURI),
+        "Reinserted livemark with new site URL should have same feed URI");
+    }
+
+    do_print("Remove livemark site URL");
+    {
+      let livemark = yield PlacesUtils.livemarks.addLivemark({
+        parentGuid: PlacesUtils.bookmarks.menuGuid,
+        feedURI,
+        siteURI: uri(site),
+        index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+      });
+
+      yield rejects(PlacesSyncUtils.bookmarks.update({
+        guid: livemark.guid,
+        site: null,
+      }), "Reinserting livemark witout site URL requires full record");
+
+      let newLivemark = yield PlacesSyncUtils.bookmarks.update({
+        kind: "livemark",
+        parentGuid: PlacesUtils.bookmarks.menuGuid,
+        guid: livemark.guid,
+        feed: feedURI,
+        site: null,
+      });
+      notEqual(newLivemark, livemark,
+        "Livemark without site URL should replace old livemark");
+      equal(newLivemark.guid, livemark.guid,
+        "GUIDs should match for reinserted livemark without site URL");
+      ok(!newLivemark.siteURI, "Reinserted livemark should not have site URI");
+    }
+
+    do_print("Change livemark site URL");
+    {
+      let livemark = yield PlacesUtils.livemarks.addLivemark({
+        parentGuid: PlacesUtils.bookmarks.menuGuid,
+        feedURI,
+        siteURI: uri(site),
+        index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+      });
+
+      yield rejects(PlacesSyncUtils.bookmarks.update({
+        guid: livemark.guid,
+        site: site + "/new",
+      }), "Reinserting livemark with changed site URL requires full record");
+
+      let newLivemark = yield PlacesSyncUtils.bookmarks.update({
+        kind: "livemark",
+        parentGuid: PlacesUtils.bookmarks.menuGuid,
+        guid: livemark.guid,
+        feed:feedURI,
+        site: site + "/new",
+      });
+      notEqual(newLivemark, livemark,
+        "Livemark with changed site URL should replace old livemark");
+      equal(newLivemark.guid, livemark.guid,
+        "GUIDs should match for reinserted livemark with changed site URL");
+      equal(newLivemark.siteURI.spec, site + "/new",
+        "Reinserted livemark should have changed site URI");
+    }
+
+    // Livemarks are stored as folders, but have different kinds. We should
+    // remove the folder and insert a livemark with the same GUID instead of
+    // trying to update the folder in-place.
+    do_print("Replace folder with livemark");
+    {
+      let folder = yield PlacesUtils.bookmarks.insert({
+        type: PlacesUtils.bookmarks.TYPE_FOLDER,
+        parentGuid: PlacesUtils.bookmarks.menuGuid,
+        title: "Plain folder",
+      });
+      let livemark = yield PlacesSyncUtils.bookmarks.update({
+        kind: "livemark",
+        parentGuid: PlacesUtils.bookmarks.menuGuid,
+        guid: folder.guid,
+        feed: feedURI,
+      });
+      equal(livemark.guid, folder.guid,
+        "Livemark should have same GUID as replaced folder");
+    }
+  } finally {
+    yield stopServer();
+  }
+
+  yield PlacesUtils.bookmarks.eraseEverything();
+});
+
+add_task(function* test_insert_tags() {
+  let newItems = yield Promise.all([{
+    kind: "bookmark",
+    url: "https://example.com",
+    guid: makeGuid(),
+    parentGuid: PlacesUtils.bookmarks.menuGuid,
+    tags: ["foo", "bar"],
+  }, {
+    kind: "bookmark",
+    url: "https://example.org",
+    guid: makeGuid(),
+    parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+    tags: ["foo", "baz"],
+  }, {
+    kind: "query",
+    url: "place:queryType=1&sort=12&maxResults=10",
+    guid: makeGuid(),
+    parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+    folder: "bar",
+    tags: ["baz", "qux"],
+    title: "bar",
+  }].map(info => PlacesSyncUtils.bookmarks.insert(info)));
+
+  assertTagForURLs("foo", ["https://example.com/", "https://example.org/"],
+    "2 URLs with new tag");
+  assertTagForURLs("bar", ["https://example.com/"], "1 URL with existing tag");
+  assertTagForURLs("baz", ["https://example.org/",
+    "place:queryType=1&sort=12&maxResults=10"],
+    "Should support tagging URLs and tag queries");
+  assertTagForURLs("qux", ["place:queryType=1&sort=12&maxResults=10"],
+    "Should support tagging tag queries");
+
+  yield PlacesUtils.bookmarks.eraseEverything();
+});
+
+add_task(function* test_insert_tags_whitespace() {
+  do_print("Untrimmed and blank tags");
+  let taggedBlanks = yield PlacesSyncUtils.bookmarks.insert({
+    kind: "bookmark",
+    url: "https://example.org",
+    guid: makeGuid(),
+    parentGuid: PlacesUtils.bookmarks.menuGuid,
+    tags: [" untrimmed ", " ", "taggy"],
+  });
+  deepEqual(taggedBlanks.tags, ["untrimmed", "taggy"],
+    "Should not return empty tags");
+  assertURLHasTags("https://example.org/", ["taggy", "untrimmed"],
+    "Should set trimmed tags and ignore dupes");
+
+  do_print("Dupe tags");
+  let taggedDupes = yield PlacesSyncUtils.bookmarks.insert({
+    kind: "bookmark",
+    url: "https://example.net",
+    guid: makeGuid(),
+    parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+    tags: [" taggy", "taggy ", " taggy ", "taggy"],
+  });
+  deepEqual(taggedDupes.tags, ["taggy", "taggy", "taggy", "taggy"],
+    "Should return trimmed and dupe tags");
+  assertURLHasTags("https://example.net/", ["taggy"],
+    "Should ignore dupes when setting tags");
+
+  assertTagForURLs("taggy", ["https://example.net/", "https://example.org/"],
+    "Should exclude falsy tags");
+
+  yield PlacesUtils.bookmarks.eraseEverything();
+});
+
+add_task(function* test_insert_keyword() {
+  do_print("Insert item with new keyword");
+  {
+    let bookmark = yield PlacesSyncUtils.bookmarks.insert({
+      kind: "bookmark",
+      parentGuid: PlacesUtils.bookmarks.menuGuid,
+      url: "https://example.com",
+      keyword: "moz",
+      guid: makeGuid(),
+    });
+    let entry = yield PlacesUtils.keywords.fetch("moz");
+    equal(entry.url.href, "https://example.com/",
+      "Should add keyword for item");
+  }
+
+  do_print("Insert item with existing keyword");
+  {
+    let bookmark = yield PlacesSyncUtils.bookmarks.insert({
+      kind: "bookmark",
+      parentGuid: PlacesUtils.bookmarks.menuGuid,
+      url: "https://mozilla.org",
+      keyword: "moz",
+      guid: makeGuid(),
+    });
+    let entry = yield PlacesUtils.keywords.fetch("moz");
+    equal(entry.url.href, "https://mozilla.org/",
+      "Should reassign keyword to new item");
+  }
+
+  yield PlacesUtils.bookmarks.eraseEverything();
+});
+
+add_task(function* test_insert_annos() {
+  do_print("Bookmark with description");
+  let descBmk = yield PlacesSyncUtils.bookmarks.insert({
+    kind: "bookmark",
+    url: "https://example.com",
+    guid: makeGuid(),
+    parentGuid: PlacesUtils.bookmarks.menuGuid,
+    description: "Bookmark description",
+  });
+  {
+    equal(descBmk.description, "Bookmark description",
+      "Should return new bookmark description");
+    let id = yield PlacesUtils.promiseItemId(descBmk.guid);
+    equal(PlacesUtils.annotations.getItemAnnotation(id, DESCRIPTION_ANNO),
+      "Bookmark description", "Should set new bookmark description");
+  }
+
+  do_print("Folder with description");
+  let descFolder = yield PlacesSyncUtils.bookmarks.insert({
+    kind: "folder",
+    guid: makeGuid(),
+    parentGuid: PlacesUtils.bookmarks.menuGuid,
+    description: "Folder description",
+  });
+  {
+    equal(descFolder.description, "Folder description",
+      "Should return new folder description");
+    let id = yield PlacesUtils.promiseItemId(descFolder.guid);
+    equal(PlacesUtils.annotations.getItemAnnotation(id, DESCRIPTION_ANNO),
+      "Folder description", "Should set new folder description");
+  }
+
+  do_print("Bookmark with sidebar anno");
+  let sidebarBmk = yield PlacesSyncUtils.bookmarks.insert({
+    kind: "bookmark",
+    url: "https://example.com",
+    guid: makeGuid(),
+    parentGuid: PlacesUtils.bookmarks.menuGuid,
+    loadInSidebar: true,
+  });
+  {
+    ok(sidebarBmk.loadInSidebar, "Should return sidebar anno for new bookmark");
+    let id = yield PlacesUtils.promiseItemId(sidebarBmk.guid);
+    ok(PlacesUtils.annotations.itemHasAnnotation(id, LOAD_IN_SIDEBAR_ANNO),
+      "Should set sidebar anno for new bookmark");
+  }
+
+  do_print("Bookmark without sidebar anno");
+  let noSidebarBmk = yield PlacesSyncUtils.bookmarks.insert({
+    kind: "bookmark",
+    url: "https://example.org",
+    guid: makeGuid(),
+    parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+    loadInSidebar: false,
+  });
+  {
+    ok(!noSidebarBmk.loadInSidebar,
+      "Should not return sidebar anno for new bookmark");
+    let id = yield PlacesUtils.promiseItemId(noSidebarBmk.guid);
+    ok(!PlacesUtils.annotations.itemHasAnnotation(id, LOAD_IN_SIDEBAR_ANNO),
+      "Should not set sidebar anno for new bookmark");
+  }
+
+  yield PlacesUtils.bookmarks.eraseEverything();
+});
+
+add_task(function* test_insert_tag_query() {
+  let tagFolder = -1;
+
+  do_print("Insert tag query for new tag");
+  {
+    deepEqual(PlacesUtils.tagging.allTags, [], "New tag should not exist yet");
+    let query = yield PlacesSyncUtils.bookmarks.insert({
+      kind: "query",
+      guid: makeGuid(),
+      parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+      url: "place:type=7&folder=90",
+      folder: "taggy",
+      title: "Tagged stuff",
+    });
+    notEqual(query.url.href, "place:type=7&folder=90",
+      "Tag query URL for new tag should differ");
+
+    [, tagFolder] = /\bfolder=(\d+)\b/.exec(query.url.pathname);
+    ok(tagFolder > 0, "New tag query URL should contain valid folder");
+    deepEqual(PlacesUtils.tagging.allTags, ["taggy"], "New tag should exist");
+  }
+
+  do_print("Insert tag query for existing tag");
+  {
+    let url = "place:type=7&folder=90&maxResults=15";
+    let query = yield PlacesSyncUtils.bookmarks.insert({
+      kind: "query",
+      url,
+      folder: "taggy",
+      title: "Sorted and tagged",
+      guid: makeGuid(),
+      parentGuid: PlacesUtils.bookmarks.menuGuid,
+    });
+    notEqual(query.url.href, url, "Tag query URL for existing tag should differ");
+    let params = new URLSearchParams(query.url.pathname);
+    equal(params.get("type"), "7", "Should preserve query type");
+    equal(params.get("maxResults"), "15", "Should preserve additional params");
+    equal(params.get("folder"), tagFolder, "Should update tag folder");
+    deepEqual(PlacesUtils.tagging.allTags, ["taggy"], "Should not duplicate existing tags");
+  }
+
+  do_print("Use the public tagging API to ensure we added the tag correctly");
+  {
+    let bookmark = yield PlacesUtils.bookmarks.insert({
+      parentGuid: PlacesUtils.bookmarks.menuGuid,
+      type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+      url: "https://mozilla.org",
+      title: "Mozilla",
+    });
+    PlacesUtils.tagging.tagURI(uri("https://mozilla.org"), ["taggy"]);
+    assertURLHasTags("https://mozilla.org/", ["taggy"],
+      "Should set tags using the tagging API");
+  }
+
+  do_print("Removing the tag should clean up the tag folder");
+  {
+    PlacesUtils.tagging.untagURI(uri("https://mozilla.org"), null);
+    deepEqual(PlacesUtils.tagging.allTags, [],
+      "Should remove tag folder once last item is untagged");
+  }
+
+  yield PlacesUtils.bookmarks.eraseEverything();
+});
+
+add_task(function* test_insert_orphans() {
+  let grandParentGuid = makeGuid();
+  let parentGuid = makeGuid();
+  let childGuid = makeGuid();
+  let childId;
+
+  do_print("Insert an orphaned child");
+  {
+    let child = yield PlacesSyncUtils.bookmarks.insert({
+      kind: "bookmark",
+      parentGuid,
+      guid: childGuid,
+      url: "https://mozilla.org",
+    });
+    equal(child.guid, childGuid,
+      "Should insert orphan with requested GUID");
+    equal(child.parentGuid, PlacesUtils.bookmarks.unfiledGuid,
+      "Should reparent orphan to unfiled");
+
+    childId = yield PlacesUtils.promiseItemId(childGuid);
+    equal(PlacesUtils.annotations.getItemAnnotation(childId, SYNC_PARENT_ANNO),
+      parentGuid, "Should set anno to missing parent GUID");
+  }
+
+  do_print("Insert the grandparent");
+  {
+    let grandParent = yield PlacesSyncUtils.bookmarks.insert({
+      kind: "folder",
+      parentGuid: PlacesUtils.bookmarks.menuGuid,
+      guid: grandParentGuid,
+    });
+    equal(PlacesUtils.annotations.getItemAnnotation(childId, SYNC_PARENT_ANNO),
+      parentGuid, "Child should still have orphan anno");
+  }
+
+  // Note that only `PlacesSyncUtils` reparents orphans, though Sync adds an
+  // observer that removes the orphan anno if the orphan is manually moved.
+  do_print("Insert the missing parent");
+  {
+    let parent = yield PlacesSyncUtils.bookmarks.insert({
+      kind: "folder",
+      parentGuid: grandParentGuid,
+      guid: parentGuid,
+    });
+    equal(parent.guid, parentGuid, "Should insert parent with requested GUID");
+    equal(parent.parentGuid, grandParentGuid,
+      "Parent should be child of grandparent");
+    ok(!PlacesUtils.annotations.itemHasAnnotation(childId, SYNC_PARENT_ANNO),
+      "Orphan anno should be removed after reparenting");
+
+    let child = yield PlacesUtils.bookmarks.fetch({ guid: childGuid });
+    equal(child.parentGuid, parentGuid,
+      "Should reparent child after inserting missing parent");
+  }
+
+  yield PlacesUtils.bookmarks.eraseEverything();
+});
--- a/toolkit/components/places/tests/unit/xpcshell.ini
+++ b/toolkit/components/places/tests/unit/xpcshell.ini
@@ -5,16 +5,17 @@ firefox-appdir = browser
 skip-if = toolkit == 'android' || toolkit == 'gonk'
 support-files =
   bookmarks.corrupt.html
   bookmarks.json
   bookmarks.preplaces.html
   bookmarks_html_singleframe.html
   bug476292.sqlite
   default.sqlite
+  livemark.xml
   nsDummyObserver.js
   nsDummyObserver.manifest
   places.sparse.sqlite
 
 [test_000_frecency.js]
 [test_317472.js]
 # Bug 676989: test hangs consistently on Android
 skip-if = os == "android"
@@ -137,16 +138,17 @@ skip-if = os == "android"
 [test_promiseBookmarksTree.js]
 # Bug 676989: test hangs consistently on Android
 skip-if = os == "android"
 [test_resolveNullBookmarkTitles.js]
 [test_result_sort.js]
 [test_resultsAsVisit_details.js]
 [test_sql_guid_functions.js]
 [test_svg_favicon.js]
+[test_sync_utils.js]
 [test_tag_autocomplete_search.js]
 [test_tagging.js]
 [test_telemetry.js]
 [test_update_frecency_after_delete.js]
 # Bug 676989: test hangs consistently on Android
 skip-if = os == "android"
 [test_utils_backups_create.js]
 [test_utils_getURLsForContainerNode.js]