--- a/toolkit/components/places/PlacesSyncUtils.jsm
+++ b/toolkit/components/places/PlacesSyncUtils.jsm
@@ -26,16 +26,18 @@ XPCOMUtils.defineLazyModuleGetter(this, 
  * 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 { SOURCE_SYNC } = Ci.nsINavBookmarksService;
 
+const MICROSECONDS_PER_SECOND = 1000000;
+
 // These are defined as lazy getters to defer initializing the bookmarks
 // service until it's needed.
 XPCOMUtils.defineLazyGetter(this, "ROOT_SYNC_ID_TO_GUID", () => ({
   menu: PlacesUtils.bookmarks.menuGuid,
   places: PlacesUtils.bookmarks.rootGuid,
   tags: PlacesUtils.bookmarks.tagsGuid,
   toolbar: PlacesUtils.bookmarks.toolbarGuid,
   unfiled: PlacesUtils.bookmarks.unfiledGuid,
@@ -97,19 +99,19 @@ const BookmarkSyncUtils = PlacesSyncUtil
    * Fetches the sync IDs for a folder's children, ordered by their position
    * within the folder.
    */
   fetchChildSyncIds: Task.async(function* (parentSyncId) {
     PlacesUtils.SYNC_BOOKMARK_VALIDATORS.syncId(parentSyncId);
     let parentGuid = BookmarkSyncUtils.syncIdToGuid(parentSyncId);
 
     let db = yield PlacesUtils.promiseDBConnection();
-    let children = yield fetchAllChildren(db, parentGuid);
-    return children.map(child =>
-      BookmarkSyncUtils.guidToSyncId(child.guid)
+    let childGuids = yield fetchChildGuids(db, parentGuid);
+    return childGuids.map(guid =>
+      BookmarkSyncUtils.guidToSyncId(guid)
     );
   }),
 
   /**
    * Reorders a folder's children, based on their order in the array of sync
    * IDs.
    *
    * Sync uses this method to reorder all synced children after applying all
@@ -128,16 +130,101 @@ const BookmarkSyncUtils = PlacesSyncUtil
       return undefined;
     }
     let orderedChildrenGuids = childSyncIds.map(BookmarkSyncUtils.syncIdToGuid);
     return PlacesUtils.bookmarks.reorder(parentGuid, orderedChildrenGuids,
                                          { source: SOURCE_SYNC });
   }),
 
   /**
+   * Returns a changeset containing local bookmark changes since the last sync.
+   * Updates the sync status of all "NEW" bookmarks to "NORMAL", so that Sync
+   * can recover correctly after an interrupted sync.
+   *
+   * @return {Promise} resolved once all items have been fetched.
+   * @resolves to an object containing records for changed bookmarks, keyed by
+   *           the sync ID.
+   * @see pullSyncChanges for the implementation, and markChangesAsSyncing for
+   *      an explanation of why we update the sync status.
+   */
+  pullChanges() {
+    return PlacesUtils.withConnectionWrapper("BookmarkSyncUtils: pullChanges",
+      db => pullSyncChanges(db));
+  },
+
+  /**
+   * Decrements the sync change counter, updates the sync status, and cleans up
+   * tombstones for successfully synced items. Sync calls this method at the
+   * end of each bookmark sync.
+   *
+   * @param changeRecords
+   *        A changeset containing sync change records, as returned by
+   *        `pull{All, New}Changes`.
+   * @return {Promise} resolved once all records have been updated.
+   */
+  pushChanges(changeRecords) {
+    return PlacesUtils.withConnectionWrapper(
+      "BookmarkSyncUtils.pushChanges", Task.async(function* (db) {
+        let skippedCount = 0;
+        let syncedTombstoneGuids = [];
+        let syncedChanges = [];
+
+        for (let syncId in changeRecords) {
+          // Validate change records to catch coding errors.
+          let changeRecord = validateChangeRecord(changeRecords[syncId], {
+            tombstone: { required: true },
+            counter: { required: true },
+            synced: { required: true },
+          });
+
+          // Sync sets the `synced` flag for reconciled or successfully
+          // uploaded items. If upload failed, ignore the change; we'll
+          // try again on the next sync.
+          if (!changeRecord.synced) {
+            skippedCount++;
+            continue;
+          }
+
+          let guid = BookmarkSyncUtils.syncIdToGuid(syncId);
+          if (changeRecord.tombstone) {
+            syncedTombstoneGuids.push(guid);
+          } else {
+            syncedChanges.push([guid, changeRecord]);
+          }
+        }
+
+        if (syncedChanges.length || syncedTombstoneGuids.length) {
+          yield db.executeTransaction(function* () {
+            for (let [guid, changeRecord] of syncedChanges) {
+              // Reduce the change counter and update the sync status for
+              // reconciled and uploaded items. If the bookmark was updated
+              // during the sync, its change counter will still be > 0 for the
+              // next sync.
+              yield db.executeCached(`
+                UPDATE moz_bookmarks
+                SET syncChangeCounter = MAX(syncChangeCounter - :syncChangeDelta, 0),
+                    syncStatus = :syncStatus
+                WHERE guid = :guid`,
+                { guid, syncChangeDelta: changeRecord.counter,
+                  syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NORMAL });
+            }
+
+            yield removeTombstones(db, syncedTombstoneGuids);
+          });
+        }
+
+        BookmarkSyncLog.debug(`pushChanges: Processed change records`,
+                              { skipped: skippedCount,
+                                updated: syncedChanges.length,
+                                tombstones: syncedTombstoneGuids.length });
+      })
+    );
+  },
+
+  /**
    * Removes an item from the database. Options are passed through to
    * PlacesUtils.bookmarks.remove.
    */
   remove: Task.async(function* (syncId, options = {}) {
     let guid = BookmarkSyncUtils.syncIdToGuid(syncId);
     if (guid in ROOT_GUID_TO_SYNC_ID) {
       BookmarkSyncLog.warn(`remove: Refusing to remove root ${syncId}`);
       return null;
@@ -150,16 +237,64 @@ const BookmarkSyncUtils = PlacesSyncUtil
   /**
    * Returns true for sync IDs that are considered roots.
    */
   isRootSyncID(syncID) {
     return ROOT_SYNC_ID_TO_GUID.hasOwnProperty(syncID);
   },
 
   /**
+   * Removes all bookmarks and tombstones from the database. Sync calls this
+   * method when it receives a command from a remote client to wipe all stored
+   * data, or when replacing stored data with remote data on a first sync.
+   *
+   * @return {Promise} resolved once all items have been removed.
+   */
+  wipe: Task.async(function* () {
+    // Remove all children from all roots.
+    yield PlacesUtils.bookmarks.eraseEverything({
+      source: SOURCE_SYNC,
+    });
+    // Remove tombstones and reset change tracking info for the roots.
+    yield BookmarkSyncUtils.reset();
+  }),
+
+  /**
+   * Marks all bookmarks as "NEW" and removes all tombstones. Unlike `wipe`,
+   * this keeps all existing bookmarks, and only clears their sync change
+   * tracking info.
+   *
+   * @return {Promise} resolved once all items have been updated.
+   */
+  reset: Task.async(function* () {
+    return PlacesUtils.withConnectionWrapper(
+      "BookmarkSyncUtils: reset", function(db) {
+        return db.executeTransaction(function* () {
+          // Reset change counters and statuses for all bookmarks.
+          yield db.executeCached(`
+            UPDATE moz_bookmarks
+            SET syncChangeCounter = 1,
+                syncStatus = :syncStatus`,
+            { syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NEW });
+
+          // The orphan anno isn't meaningful when Sync is disconnected.
+          yield db.execute(`
+            DELETE FROM moz_items_annos
+            WHERE anno_attribute_id = (SELECT id FROM moz_anno_attributes
+                                       WHERE name = :orphanAnno)`,
+            { orphanAnno: BookmarkSyncUtils.SYNC_PARENT_ANNO });
+
+          // Drop stale tombstones.
+          yield db.executeCached("DELETE FROM moz_bookmarks_deleted");
+        });
+      }
+    );
+  }),
+
+  /**
    * Changes the GUID of an existing item. This method only allows Places GUIDs
    * because root sync IDs cannot be changed.
    *
    * @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) {
@@ -404,35 +539,36 @@ XPCOMUtils.defineLazyGetter(this, "Bookm
   return Log.repository.getLogger("BookmarkSyncUtils");
 });
 
 function validateSyncBookmarkObject(input, behavior) {
   return PlacesUtils.validateItemProperties(
     PlacesUtils.SYNC_BOOKMARK_VALIDATORS, input, behavior);
 }
 
+// Validates a sync change record as returned by `pullChanges` and passed to
+// `pushChanges`.
+function validateChangeRecord(changeRecord, behavior) {
+  return PlacesUtils.validateItemProperties(
+    PlacesUtils.SYNC_CHANGE_RECORD_VALIDATORS, changeRecord, 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
+    SELECT 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"),
-  }));
+  return rows.map(row => row.getResultByName("guid"));
 });
 
 // A helper for whenever we want to know if a GUID doesn't exist in the places
 // database. Primarily used to detect orphans on incoming records.
 var GUIDMissing = Task.async(function* (guid) {
   try {
     yield PlacesUtils.promiseItemId(guid);
     return false;
@@ -957,24 +1093,31 @@ var tagItem = Task.async(function(item, 
 // but doesn't know about additional livemark properties. We check this to avoid
 // having it throw in case we only pass properties like `{ guid, feedURI }`.
 function shouldUpdateBookmark(bookmarkInfo) {
   return bookmarkInfo.hasOwnProperty("parentGuid") ||
          bookmarkInfo.hasOwnProperty("title") ||
          bookmarkInfo.hasOwnProperty("url");
 }
 
+// Returns the folder ID for `tag`, or `null` if the tag doesn't exist.
 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 });
+  let results = yield db.executeCached(`
+    SELECT id
+    FROM moz_bookmarks
+    WHERE type = :type AND
+          parent = :tagsFolderId AND
+          title = :tag`,
+    { type: PlacesUtils.bookmarks.TYPE_FOLDER,
+      tagsFolderId: PlacesUtils.tagsFolderId, tag });
   return results.length ? results[0].getResultByName("id") : null;
 });
 
+// Returns the folder ID for `tag`, creating one if it doesn't exist.
 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,
@@ -1117,19 +1260,19 @@ var fetchFolderItem = Task.async(functio
 
   let description = yield getAnno(bookmarkItem.guid,
                                   BookmarkSyncUtils.DESCRIPTION_ANNO);
   if (description) {
     item.description = description;
   }
 
   let db = yield PlacesUtils.promiseDBConnection();
-  let children = yield fetchAllChildren(db, bookmarkItem.guid);
-  item.childSyncIds = children.map(child =>
-    BookmarkSyncUtils.guidToSyncId(child.guid)
+  let childGuids = yield fetchChildGuids(db, bookmarkItem.guid);
+  item.childSyncIds = childGuids.map(guid =>
+    BookmarkSyncUtils.guidToSyncId(guid)
   );
 
   return item;
 });
 
 // Creates and returns a Sync bookmark object containing the livemark's
 // description, children (none), feed URI, and site URI.
 var fetchLivemarkItem = Task.async(function* (bookmarkItem) {
@@ -1183,8 +1326,102 @@ var fetchQueryItem = Task.async(function
   let query = yield getAnno(bookmarkItem.guid,
                             BookmarkSyncUtils.SMART_BOOKMARKS_ANNO);
   if (query) {
     item.query = query;
   }
 
   return item;
 });
+
+function addRowToChangeRecords(row, changeRecords) {
+  let syncId = BookmarkSyncUtils.guidToSyncId(row.getResultByName("guid"));
+  let modified = row.getResultByName("modified") / MICROSECONDS_PER_SECOND;
+  changeRecords[syncId] = {
+    modified,
+    counter: row.getResultByName("syncChangeCounter"),
+    status: row.getResultByName("syncStatus"),
+    tombstone: !!row.getResultByName("tombstone"),
+    synced: false,
+  };
+}
+
+/**
+ * Queries the database for synced bookmarks and tombstones, updates the sync
+ * status of all "NEW" bookmarks to "NORMAL", and returns a changeset for the
+ * Sync bookmarks engine.
+ *
+ * @param db
+ *        The Sqlite.jsm connection handle.
+ * @return {Promise} resolved once all items have been fetched.
+ * @resolves to an object containing records for changed bookmarks, keyed by
+ *           the sync ID.
+ */
+var pullSyncChanges = Task.async(function* (db) {
+  let changeRecords = {};
+
+  yield db.executeCached(`
+    WITH RECURSIVE
+    syncedItems(id, guid, modified, syncChangeCounter, syncStatus) AS (
+      SELECT b.id, b.guid, b.lastModified, b.syncChangeCounter, b.syncStatus
+       FROM moz_bookmarks b
+       WHERE b.guid IN ('menu________', 'toolbar_____', 'unfiled_____',
+                        'mobile______')
+      UNION ALL
+      SELECT b.id, b.guid, b.lastModified, b.syncChangeCounter, b.syncStatus
+      FROM moz_bookmarks b
+      JOIN syncedItems s ON b.parent = s.id
+    )
+    SELECT guid, modified, syncChangeCounter, syncStatus, 0 AS tombstone
+    FROM syncedItems
+    WHERE syncChangeCounter >= 1
+    UNION ALL
+    SELECT guid, dateRemoved AS modified, 1 AS syncChangeCounter,
+           :deletedSyncStatus, 1 AS tombstone
+    FROM moz_bookmarks_deleted`,
+    { deletedSyncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NORMAL },
+    row => addRowToChangeRecords(row, changeRecords));
+
+  yield markChangesAsSyncing(db, changeRecords);
+
+  return changeRecords;
+});
+
+/**
+ * Updates the sync status on all "NEW" and "UNKNOWN" bookmarks to "NORMAL".
+ *
+ * We do this when pulling changes instead of in `pushChanges` to make sure
+ * we write tombstones if a new item is deleted after an interrupted sync. (For
+ * example, if a "NEW" record is uploaded or reconciled, then the app is closed
+ * before Sync calls `pushChanges`).
+ */
+function markChangesAsSyncing(db, changeRecords) {
+  let unsyncedGuids = [];
+  for (let syncId in changeRecords) {
+    if (changeRecords[syncId].tombstone) {
+      continue;
+    }
+    if (changeRecords[syncId].status ==
+        PlacesUtils.bookmarks.SYNC_STATUS.NORMAL) {
+      continue;
+    }
+    let guid = BookmarkSyncUtils.syncIdToGuid(syncId);
+    unsyncedGuids.push(JSON.stringify(guid));
+  }
+  if (!unsyncedGuids.length) {
+    return Promise.resolve();
+  }
+  return db.execute(`
+    UPDATE moz_bookmarks
+    SET syncStatus = :syncStatus
+    WHERE guid IN (${unsyncedGuids.join(",")})`,
+    { syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NORMAL });
+}
+
+// Removes tombstones for successfully synced items.
+var removeTombstones = Task.async(function* (db, guids) {
+  if (!guids.length) {
+    return Promise.resolve();
+  }
+  return db.execute(`
+    DELETE FROM moz_bookmarks_deleted
+    WHERE guid IN (${guids.map(guid => JSON.stringify(guid)).join(",")})`);
+});

--- a/toolkit/components/places/PlacesUtils.jsm
+++ b/toolkit/components/places/PlacesUtils.jsm
@@ -288,16 +288,28 @@ const SYNC_BOOKMARK_VALIDATORS = Object.
   description: simpleValidateFunc(v => v === null || typeof v == "string"),
   loadInSidebar: simpleValidateFunc(v => v === true || v === false),
   feed: v => v === null ? v : BOOKMARK_VALIDATORS.url(v),
   site: v => v === null ? v : BOOKMARK_VALIDATORS.url(v),
   title: BOOKMARK_VALIDATORS.title,
   url: BOOKMARK_VALIDATORS.url,
 });
 
+// Sync change records are passed between `PlacesSyncUtils` and the Sync
+// bookmarks engine, and are used to update an item's sync status and change
+// counter at the end of a sync.
+const SYNC_CHANGE_RECORD_VALIDATORS = Object.freeze({
+  modified: simpleValidateFunc(v => typeof v == "number" && v >= 0),
+  counter: simpleValidateFunc(v => typeof v == "number" && v >= 0),
+  status: simpleValidateFunc(v => typeof v == "number" &&
+                                  Object.values(PlacesUtils.bookmarks.SYNC_STATUS).includes(v)),
+  tombstone: simpleValidateFunc(v => v === true || v === false),
+  synced: simpleValidateFunc(v => v === true || v === false),
+});
+
 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)
@@ -560,16 +572,17 @@ this.PlacesUtils = {
     }
     if (required.size > 0)
       throw new Error(`The following properties were expected: ${[...required].join(", ")}`);
     return normalizedInput;
   },
 
   BOOKMARK_VALIDATORS,
   SYNC_BOOKMARK_VALIDATORS,
+  SYNC_CHANGE_RECORD_VALIDATORS,
 
   QueryInterface: XPCOMUtils.generateQI([
     Ci.nsIObserver
   , Ci.nsITransactionListener
   ]),
 
   _shutdownFunctions: [],
   registerShutdownFunction: function PU_registerShutdownFunction(aFunc)

new file mode 100755
--- /dev/null
+++ b/toolkit/components/places/tests/unit/sync_utils_bookmarks.html
@@ -0,0 +1,18 @@
+<!DOCTYPE NETSCAPE-Bookmark-file-1>
+<!-- This is an automatically generated file.
+     It will be read and overwritten.
+     DO NOT EDIT! -->
+<META HTTP-EQUIV="Content-Type" CONTENT="text/html; charset=UTF-8">
+<TITLE>Bookmarks</TITLE>
+<H1>Bookmarks Menu</H1>
+
+<DL><p>
+    <DT><A HREF="https://www.mozilla.org/" ADD_DATE="1471365662" LAST_MODIFIED="1471366005" LAST_CHARSET="UTF-8">Mozilla</A>
+    <DD>Mozilla home
+    <DT><H3 ADD_DATE="1449080379" LAST_MODIFIED="1471366005" PERSONAL_TOOLBAR_FOLDER="true">Bookmarks Toolbar</H3>
+    <DD>Add bookmarks to this folder to see them displayed on the Bookmarks Toolbar
+    <DL><p>
+        <DT><A HREF="https://www.mozilla.org/en-US/firefox/" ADD_DATE="1471365681" LAST_MODIFIED="1471366005" SHORTCUTURL="fx" LAST_CHARSET="UTF-8" TAGS="browser">Firefox</A>
+        <DD>Firefox home
+    </DL><p>
+</DL>

new file mode 100755
--- /dev/null
+++ b/toolkit/components/places/tests/unit/sync_utils_bookmarks.json
@@ -0,0 +1,80 @@
+{
+  "guid": "root________",
+  "title": "",
+  "index": 0,
+  "dateAdded": 1449080379324000,
+  "lastModified": 1471365727344000,
+  "id": 1,
+  "type": "text/x-moz-place-container",
+  "root": "placesRoot",
+  "children": [{
+    "guid": "menu________",
+    "title": "Bookmarks Menu",
+    "index": 0,
+    "dateAdded": 1449080379324000,
+    "lastModified": 1471365683893000,
+    "id": 2,
+    "type": "text/x-moz-place-container",
+    "root": "bookmarksMenuFolder",
+    "children": [{
+      "guid": "NnvGl3CRA4hC",
+      "title": "Mozilla",
+      "index": 0,
+      "dateAdded": 1471365662585000,
+      "lastModified": 1471365667573000,
+      "id": 6,
+      "charset": "UTF-8",
+      "annos": [{
+        "name": "bookmarkProperties/description",
+        "flags": 0,
+        "expires": 4,
+        "value": "Mozilla home"
+      }],
+      "type": "text/x-moz-place",
+      "uri": "https://www.mozilla.org/"
+    }]
+  }, {
+    "guid": "toolbar_____",
+    "title": "Bookmarks Toolbar",
+    "index": 1,
+    "dateAdded": 1449080379324000,
+    "lastModified": 1471365683893000,
+    "id": 3,
+    "annos": [{
+      "name": "bookmarkProperties/description",
+      "flags": 0,
+      "expires": 4,
+      "value": "Add bookmarks to this folder to see them displayed on the Bookmarks Toolbar"
+    }],
+    "type": "text/x-moz-place-container",
+    "root": "toolbarFolder",
+    "children": [{
+      "guid": "APzP8MupzA8l",
+      "title": "Firefox",
+      "index": 0,
+      "dateAdded": 1471365681801000,
+      "lastModified": 1471365687887000,
+      "id": 7,
+      "charset": "UTF-8",
+      "tags": "browser",
+      "annos": [{
+        "name": "bookmarkProperties/description",
+        "flags": 0,
+        "expires": 4,
+        "value": "Firefox home"
+      }],
+      "type": "text/x-moz-place",
+      "uri": "https://www.mozilla.org/en-US/firefox/",
+      "keyword": "fx"
+    }]
+  }, {
+    "guid": "unfiled_____",
+    "title": "Other Bookmarks",
+    "index": 3,
+    "dateAdded": 1449080379324000,
+    "lastModified": 1471365629626000,
+    "id": 5,
+    "type": "text/x-moz-place-container",
+    "root": "unfiledBookmarksFolder"
+  }]
+}
\ No newline at end of file

--- a/toolkit/components/places/tests/unit/test_sync_utils.js
+++ b/toolkit/components/places/tests/unit/test_sync_utils.js
@@ -1,8 +1,9 @@
+Cu.import("resource://gre/modules/ObjectUtils.jsm");
 Cu.import("resource://gre/modules/PlacesSyncUtils.jsm");
 const {
   // `fetchGuidsWithAnno` isn't exported, but we can still access it here via a
   // backstage pass.
   fetchGuidsWithAnno,
 } = Cu.import("resource://gre/modules/PlacesSyncUtils.jsm");
 Cu.import("resource://testing-common/httpd.js");
 Cu.importGlobalProperties(["crypto", "URLSearchParams"]);
@@ -108,16 +109,73 @@ var populateTree = Task.async(function* 
   return guids;
 });
 
 var syncIdToId = Task.async(function* syncIdToId(syncId) {
   let guid = yield PlacesSyncUtils.bookmarks.syncIdToGuid(syncId);
   return PlacesUtils.promiseItemId(guid);
 });
 
+var moveSyncedBookmarksToUnsyncedParent = Task.async(function* () {
+  do_print("Insert synced bookmarks");
+  let syncedGuids = yield populateTree(PlacesUtils.bookmarks.menuGuid, {
+    kind: "folder",
+    title: "folder",
+    children: [{
+      kind: "bookmark",
+      title: "childBmk",
+      url: "https://example.org",
+    }],
+  }, {
+    kind: "bookmark",
+    title: "topBmk",
+    url: "https://example.com",
+  });
+  // Pretend we've synced each bookmark at least once.
+  yield PlacesTestUtils.setBookmarkSyncFields(...Object.values(syncedGuids).map(
+    guid => ({ guid, syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NORMAL })
+  ));
+
+  do_print("Make new folder");
+  let unsyncedFolder = yield PlacesUtils.bookmarks.insert({
+    type: PlacesUtils.bookmarks.TYPE_FOLDER,
+    parentGuid: PlacesUtils.bookmarks.menuGuid,
+    title: "unsyncedFolder",
+  });
+
+  do_print("Move synced bookmarks into unsynced new folder");
+  for (let guid of Object.values(syncedGuids)) {
+    yield PlacesUtils.bookmarks.update({
+      guid,
+      parentGuid: unsyncedFolder.guid,
+      index: PlacesUtils.bookmarks.DEFAULT_INDEX,
+    });
+  }
+
+  return { syncedGuids, unsyncedFolder };
+});
+
+var setChangesSynced = Task.async(function* (changes) {
+  for (let syncId in changes) {
+    changes[syncId].synced = true;
+  }
+  yield PlacesSyncUtils.bookmarks.pushChanges(changes);
+});
+
+var ignoreChangedRoots = Task.async(function* () {
+  let changes = yield PlacesSyncUtils.bookmarks.pullChanges();
+  let expectedRoots = ["menu", "mobile", "toolbar", "unfiled"];
+  if (!ObjectUtils.deepEqual(Object.keys(changes).sort(), expectedRoots)) {
+    // Make sure the previous test cleaned up.
+    throw new Error(`Unexpected changes at start of test: ${
+      JSON.stringify(changes)}`);
+  }
+  yield setChangesSynced(changes);
+});
+
 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",
@@ -159,16 +217,17 @@ add_task(function* test_order() {
       makeGuid(), guids.siblingFolder, makeGuid()]);
     let childSyncIds = yield PlacesSyncUtils.bookmarks.fetchChildSyncIds(
       PlacesUtils.bookmarks.menuGuid);
     deepEqual(childSyncIds, [guids.childBmk, guids.siblingBmk, guids.siblingSep,
       guids.siblingFolder], "Nonexistent children should be ignored");
   }
 
   yield PlacesUtils.bookmarks.eraseEverything();
+  yield PlacesSyncUtils.bookmarks.reset();
 });
 
 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()),
@@ -201,16 +260,17 @@ add_task(function* test_order_roots() {
     PlacesUtils.bookmarks.rootGuid);
   yield PlacesSyncUtils.bookmarks.order(PlacesUtils.bookmarks.rootGuid,
     shuffle(oldOrder));
   let newOrder = yield PlacesSyncUtils.bookmarks.fetchChildSyncIds(
     PlacesUtils.bookmarks.rootGuid);
   deepEqual(oldOrder, newOrder, "Should ignore attempts to reorder roots");
 
   yield PlacesUtils.bookmarks.eraseEverything();
+  yield PlacesSyncUtils.bookmarks.reset();
 });
 
 add_task(function* test_update_tags() {
   do_print("Insert item without tags");
   let item = yield PlacesSyncUtils.bookmarks.insert({
     kind: "bookmark",
     url: "https://mozilla.org",
     syncId: makeGuid(),
@@ -259,16 +319,152 @@ add_task(function* test_update_tags() {
       tags: null,
     });
     deepEqual(updatedItem.tags, [], "Should return empty tag array");
     assertURLHasTags("https://mozilla.org", [],
       "Should remove all existing tags");
   }
 
   yield PlacesUtils.bookmarks.eraseEverything();
+  yield PlacesSyncUtils.bookmarks.reset();
+});
+
+add_task(function* test_pullChanges_tags() {
+  yield ignoreChangedRoots();
+
+  do_print("Insert untagged items with same URL");
+  let firstItem = yield PlacesSyncUtils.bookmarks.insert({
+    kind: "bookmark",
+    syncId: makeGuid(),
+    parentSyncId: "menu",
+    url: "https://example.org",
+  });
+  let secondItem = yield PlacesSyncUtils.bookmarks.insert({
+    kind: "bookmark",
+    syncId: makeGuid(),
+    parentSyncId: "menu",
+    url: "https://example.org",
+  });
+  let untaggedItem = yield PlacesSyncUtils.bookmarks.insert({
+    kind: "bookmark",
+    syncId: makeGuid(),
+    parentSyncId: "menu",
+    url: "https://bugzilla.org",
+  });
+  let taggedItem = yield PlacesSyncUtils.bookmarks.insert({
+    kind: "bookmark",
+    syncId: makeGuid(),
+    parentSyncId: "menu",
+    url: "https://mozilla.org",
+  });
+
+  do_print("Create tag");
+  PlacesUtils.tagging.tagURI(uri("https://example.org"), ["taggy"]);
+  let tagFolderId = PlacesUtils.bookmarks.getIdForItemAt(
+    PlacesUtils.tagsFolderId, 0);
+  let tagFolderGuid = yield PlacesUtils.promiseItemGuid(tagFolderId);
+
+  do_print("Tagged bookmarks should be in changeset");
+  {
+    let changes = yield PlacesSyncUtils.bookmarks.pullChanges();
+    deepEqual(Object.keys(changes).sort(),
+      [firstItem.syncId, secondItem.syncId].sort(),
+      "Should include tagged bookmarks in changeset");
+    yield setChangesSynced(changes);
+  }
+
+  do_print("Change tag case");
+  {
+    PlacesUtils.tagging.tagURI(uri("https://mozilla.org"), ["TaGgY"]);
+    let changes = yield PlacesSyncUtils.bookmarks.pullChanges();
+    deepEqual(Object.keys(changes).sort(),
+      [firstItem.syncId, secondItem.syncId, taggedItem.syncId].sort(),
+      "Should include tagged bookmarks after changing case");
+    assertTagForURLs("TaGgY", ["https://example.org/", "https://mozilla.org/"],
+      "Should add tag for new URL");
+    yield setChangesSynced(changes);
+  }
+
+  // These tests change a tag item directly, without going through the tagging
+  // service. This behavior isn't supported, but the tagging service registers
+  // an observer to handle these cases, so we make sure we handle them
+  // correctly.
+
+  do_print("Rename tag folder using Bookmarks.setItemTitle");
+  {
+    PlacesUtils.bookmarks.setItemTitle(tagFolderId, "sneaky");
+    deepEqual(PlacesUtils.tagging.allTags, ["sneaky"],
+      "Tagging service should update cache with new title");
+    let changes = yield PlacesSyncUtils.bookmarks.pullChanges();
+    deepEqual(Object.keys(changes).sort(),
+      [firstItem.syncId, secondItem.syncId].sort(),
+      "Should include tagged bookmarks after renaming tag folder");
+    yield setChangesSynced(changes);
+  }
+
+  do_print("Rename tag folder using Bookmarks.update");
+  {
+    yield PlacesUtils.bookmarks.update({
+      guid: tagFolderGuid,
+      title: "tricky",
+    });
+    deepEqual(PlacesUtils.tagging.allTags, ["tricky"],
+      "Tagging service should update cache after updating tag folder");
+    let changes = yield PlacesSyncUtils.bookmarks.pullChanges();
+    deepEqual(Object.keys(changes).sort(),
+      [firstItem.syncId, secondItem.syncId].sort(),
+      "Should include tagged bookmarks after updating tag folder");
+    yield setChangesSynced(changes);
+  }
+
+  do_print("Change tag entry URI using Bookmarks.changeBookmarkURI");
+  {
+    let tagId = PlacesUtils.bookmarks.getIdForItemAt(tagFolderId, 0);
+    PlacesUtils.bookmarks.changeBookmarkURI(tagId, uri("https://bugzilla.org"));
+    let changes = yield PlacesSyncUtils.bookmarks.pullChanges();
+    deepEqual(Object.keys(changes).sort(),
+      [firstItem.syncId, secondItem.syncId, untaggedItem.syncId].sort(),
+      "Should include tagged bookmarks after changing tag entry URI");
+    assertTagForURLs("tricky", ["https://bugzilla.org/", "https://mozilla.org/"],
+      "Should remove tag entry for old URI");
+    yield setChangesSynced(changes);
+  }
+
+  do_print("Change tag entry URL using Bookmarks.update");
+  {
+    let tagGuid = yield PlacesUtils.promiseItemGuid(
+      PlacesUtils.bookmarks.getIdForItemAt(tagFolderId, 0));
+    yield PlacesUtils.bookmarks.update({
+      guid: tagGuid,
+      url: "https://example.com",
+    });
+    let changes = yield PlacesSyncUtils.bookmarks.pullChanges();
+    deepEqual(Object.keys(changes).sort(),
+      [untaggedItem.syncId].sort(),
+      "Should include tagged bookmarks after changing tag entry URL");
+    assertTagForURLs("tricky", ["https://example.com/", "https://mozilla.org/"],
+      "Should remove tag entry for old URL");
+    yield setChangesSynced(changes);
+  }
+
+  do_print("Remove all tag folders");
+  {
+    deepEqual(PlacesUtils.tagging.allTags, ["tricky"], "Should have existing tags");
+
+    PlacesUtils.bookmarks.removeFolderChildren(PlacesUtils.tagsFolderId);
+    let changes = yield PlacesSyncUtils.bookmarks.pullChanges();
+    deepEqual(Object.keys(changes).sort(), [taggedItem.syncId].sort(),
+      "Should include tagged bookmarks after removing all tags");
+
+    deepEqual(PlacesUtils.tagging.allTags, [], "Should remove all tags from tag service");
+    yield setChangesSynced(changes);
+  }
+
+  yield PlacesUtils.bookmarks.eraseEverything();
+  yield PlacesSyncUtils.bookmarks.reset();
 });
 
 add_task(function* test_update_keyword() {
   do_print("Insert item without keyword");
   let item = yield PlacesSyncUtils.bookmarks.insert({
     kind: "bookmark",
     parentSyncId: "menu",
     url: "https://mozilla.org",
@@ -327,16 +523,17 @@ add_task(function* test_update_keyword()
     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();
+  yield PlacesSyncUtils.bookmarks.reset();
 });
 
 add_task(function* test_update_annos() {
   let guids = yield populateTree(PlacesUtils.bookmarks.menuGuid, {
     kind: "folder",
     title: "folder",
   }, {
     kind: "bookmark",
@@ -389,16 +586,17 @@ add_task(function* test_update_annos() {
     });
     ok(!updatedItem.loadInSidebar, "Should not return cleared sidebar anno");
     let id = yield syncIdToId(updatedItem.syncId);
     ok(!PlacesUtils.annotations.itemHasAnnotation(id, LOAD_IN_SIDEBAR_ANNO),
       "Should clear sidebar anno for existing bookmark");
   }
 
   yield PlacesUtils.bookmarks.eraseEverything();
+  yield PlacesSyncUtils.bookmarks.reset();
 });
 
 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({
       syncId: "menu",
@@ -412,16 +610,17 @@ add_task(function* test_update_move_root
 
   do_print("Try reparenting root");
   yield rejects(PlacesSyncUtils.bookmarks.update({
     syncId: "menu",
     parentSyncId: "toolbar",
   }));
 
   yield PlacesUtils.bookmarks.eraseEverything();
+  yield PlacesSyncUtils.bookmarks.reset();
 });
 
 add_task(function* test_insert() {
   do_print("Insert bookmark");
   {
     let item = yield PlacesSyncUtils.bookmarks.insert({
       kind: "bookmark",
       syncId: makeGuid(),
@@ -468,16 +667,17 @@ add_task(function* test_insert() {
       parentSyncId: "menu",
     });
     let { type } = yield PlacesUtils.bookmarks.fetch({ guid: item.syncId });
     equal(type, PlacesUtils.bookmarks.TYPE_SEPARATOR,
       "Separator should have correct type");
   }
 
   yield PlacesUtils.bookmarks.eraseEverything();
+  yield PlacesSyncUtils.bookmarks.reset();
 });
 
 add_task(function* test_insert_livemark() {
   let { site, stopServer } = makeLivemarkServer();
 
   try {
     do_print("Insert livemark with feed URL");
     {
@@ -518,16 +718,17 @@ add_task(function* test_insert_livemark(
       });
       ok(!livemark, "Should not insert livemark as child of livemark");
     }
   } finally {
     yield stopServer();
   }
 
   yield PlacesUtils.bookmarks.eraseEverything();
+  yield PlacesSyncUtils.bookmarks.reset();
 });
 
 add_task(function* test_update_livemark() {
   let { site, stopServer } = makeLivemarkServer();
   let feedURI = uri(site + "/feed/1");
 
   try {
     // We shouldn't reinsert the livemark if the URLs are the same.
@@ -702,16 +903,17 @@ add_task(function* test_update_livemark(
       equal(livemark.guid, folder.syncId,
         "Livemark should have same GUID as replaced folder");
     }
   } finally {
     yield stopServer();
   }
 
   yield PlacesUtils.bookmarks.eraseEverything();
+  yield PlacesSyncUtils.bookmarks.reset();
 });
 
 add_task(function* test_insert_tags() {
   yield Promise.all([{
     kind: "bookmark",
     url: "https://example.com",
     syncId: makeGuid(),
     parentSyncId: "menu",
@@ -737,16 +939,17 @@ add_task(function* test_insert_tags() {
   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();
+  yield PlacesSyncUtils.bookmarks.reset();
 });
 
 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",
     syncId: makeGuid(),
@@ -769,17 +972,22 @@ add_task(function* test_insert_tags_whit
   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");
 
+  PlacesUtils.tagging.untagURI(uri("https://example.org"), ["untrimmed", "taggy"]);
+  PlacesUtils.tagging.untagURI(uri("https://example.net"), ["taggy"]);
+  deepEqual(PlacesUtils.tagging.allTags, [], "Should clean up all tags");
+
   yield PlacesUtils.bookmarks.eraseEverything();
+  yield PlacesSyncUtils.bookmarks.reset();
 });
 
 add_task(function* test_insert_keyword() {
   do_print("Insert item with new keyword");
   {
     yield PlacesSyncUtils.bookmarks.insert({
       kind: "bookmark",
       parentSyncId: "menu",
@@ -802,16 +1010,17 @@ add_task(function* test_insert_keyword()
       syncId: 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();
+  yield PlacesSyncUtils.bookmarks.reset();
 });
 
 add_task(function* test_insert_annos() {
   do_print("Bookmark with description");
   let descBmk = yield PlacesSyncUtils.bookmarks.insert({
     kind: "bookmark",
     url: "https://example.com",
     syncId: makeGuid(),
@@ -868,16 +1077,17 @@ add_task(function* test_insert_annos() {
     ok(!noSidebarBmk.loadInSidebar,
       "Should not return sidebar anno for new bookmark");
     let id = yield syncIdToId(noSidebarBmk.syncId);
     ok(!PlacesUtils.annotations.itemHasAnnotation(id, LOAD_IN_SIDEBAR_ANNO),
       "Should not set sidebar anno for new bookmark");
   }
 
   yield PlacesUtils.bookmarks.eraseEverything();
+  yield PlacesSyncUtils.bookmarks.reset();
 });
 
 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");
@@ -932,19 +1142,22 @@ add_task(function* test_insert_tag_query
   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();
+  yield PlacesSyncUtils.bookmarks.reset();
 });
 
 add_task(function* test_insert_orphans() {
+  yield ignoreChangedRoots();
+
   let grandParentGuid = makeGuid();
   let parentGuid = makeGuid();
   let childGuid = makeGuid();
   let childId;
 
   do_print("Insert an orphaned child");
   {
     let child = yield PlacesSyncUtils.bookmarks.insert({
@@ -988,16 +1201,17 @@ add_task(function* test_insert_orphans()
       "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();
+  yield PlacesSyncUtils.bookmarks.reset();
 });
 
 add_task(function* test_move_orphans() {
   let nonexistentSyncId = makeGuid();
   let fxBmk = yield PlacesSyncUtils.bookmarks.insert({
     kind: "bookmark",
     syncId: makeGuid(),
     parentSyncId: nonexistentSyncId,
@@ -1038,16 +1252,17 @@ add_task(function* test_move_orphans() {
       PlacesUtils.bookmarks.DEFAULT_INDEX);
     let orphanGuids = yield fetchGuidsWithAnno(SYNC_PARENT_ANNO,
       nonexistentSyncId);
     deepEqual(orphanGuids, [],
       "Should remove orphan annos from moved bookmark");
   }
 
   yield PlacesUtils.bookmarks.eraseEverything();
+  yield PlacesSyncUtils.bookmarks.reset();
 });
 
 add_task(function* test_reorder_orphans() {
   let nonexistentSyncId = makeGuid();
   let fxBmk = yield PlacesSyncUtils.bookmarks.insert({
     kind: "bookmark",
     syncId: makeGuid(),
     parentSyncId: nonexistentSyncId,
@@ -1083,16 +1298,17 @@ add_task(function* test_reorder_orphans(
       [tbBmk.syncId, fxBmk.syncId]);
     let orphanGuids = yield fetchGuidsWithAnno(SYNC_PARENT_ANNO,
       nonexistentSyncId);
     deepEqual(orphanGuids, [mozBmk.syncId],
       "Should remove orphan annos from explicitly reordered bookmarks");
   }
 
   yield PlacesUtils.bookmarks.eraseEverything();
+  yield PlacesSyncUtils.bookmarks.reset();
 });
 
 add_task(function* test_set_orphan_indices() {
   let nonexistentSyncId = makeGuid();
   let fxBmk = yield PlacesSyncUtils.bookmarks.insert({
     kind: "bookmark",
     syncId: makeGuid(),
     parentSyncId: nonexistentSyncId,
@@ -1116,23 +1332,25 @@ add_task(function* test_set_orphan_indic
   do_print("Set synced orphan indices");
   {
     let fxId = yield syncIdToId(fxBmk.syncId);
     let tbId = yield syncIdToId(tbBmk.syncId);
     PlacesUtils.bookmarks.runInBatchMode(_ => {
       PlacesUtils.bookmarks.setItemIndex(fxId, 1);
       PlacesUtils.bookmarks.setItemIndex(tbId, 0);
     }, null);
+    yield PlacesTestUtils.promiseAsyncUpdates();
     let orphanGuids = yield fetchGuidsWithAnno(SYNC_PARENT_ANNO,
       nonexistentSyncId);
     deepEqual(orphanGuids, [],
       "Should remove orphan annos after updating indices");
   }
 
   yield PlacesUtils.bookmarks.eraseEverything();
+  yield PlacesSyncUtils.bookmarks.reset();
 });
 
 add_task(function* test_unsynced_orphans() {
   let nonexistentSyncId = makeGuid();
   let newBmk = yield PlacesSyncUtils.bookmarks.insert({
     kind: "bookmark",
     syncId: makeGuid(),
     parentSyncId: nonexistentSyncId,
@@ -1169,16 +1387,17 @@ add_task(function* test_unsynced_orphans
       [newBmk.syncId]);
     let orphanGuids = yield fetchGuidsWithAnno(SYNC_PARENT_ANNO,
       nonexistentSyncId);
     deepEqual(orphanGuids, [],
       "Should remove orphan annos from reordered unsynced bookmarks");
   }
 
   yield PlacesUtils.bookmarks.eraseEverything();
+  yield PlacesSyncUtils.bookmarks.reset();
 });
 
 add_task(function* test_fetch() {
   let folder = yield PlacesSyncUtils.bookmarks.insert({
     syncId: makeGuid(),
     parentSyncId: "menu",
     kind: "folder",
     description: "Folder description",
@@ -1282,16 +1501,17 @@ add_task(function* test_fetch() {
     let item = yield PlacesSyncUtils.bookmarks.fetch(smartBmk.syncId);
     deepEqual(Object.keys(item).sort(), ["syncId", "kind", "parentSyncId",
       "url", "title", "query", "parentTitle"].sort(),
       "Should include smart bookmark-specific properties");
     equal(item.query, "BookmarksToolbar", "Should return query name for smart bookmarks");
   }
 
   yield PlacesUtils.bookmarks.eraseEverything();
+  yield PlacesSyncUtils.bookmarks.reset();
 });
 
 add_task(function* test_fetch_livemark() {
   let { site, stopServer } = makeLivemarkServer();
 
   try {
     do_print("Create livemark");
     let livemark = yield PlacesUtils.livemarks.addLivemark({
@@ -1311,9 +1531,458 @@ add_task(function* test_fetch_livemark()
     equal(item.description, "Livemark description", "Should return description");
     equal(item.feed.href, site + "/feed/1", "Should return feed URL");
     equal(item.site.href, site + "/", "Should return site URL");
   } finally {
     yield stopServer();
   }
 
   yield PlacesUtils.bookmarks.eraseEverything();
+  yield PlacesSyncUtils.bookmarks.reset();
 });
+
+add_task(function* test_pullChanges_new_parent() {
+  yield ignoreChangedRoots();
+
+  let { syncedGuids, unsyncedFolder } = yield moveSyncedBookmarksToUnsyncedParent();
+
+  do_print("Unsynced parent and synced items should be tracked");
+  let changes = yield PlacesSyncUtils.bookmarks.pullChanges();
+  deepEqual(Object.keys(changes).sort(),
+    [syncedGuids.folder, syncedGuids.topBmk, syncedGuids.childBmk,
+      unsyncedFolder.guid, "menu"].sort(),
+    "Should return change records for moved items and new parent"
+  );
+
+  yield PlacesUtils.bookmarks.eraseEverything();
+  yield PlacesSyncUtils.bookmarks.reset();
+});
+
+add_task(function* test_pullChanges_deleted_folder() {
+  yield ignoreChangedRoots();
+
+  let { syncedGuids, unsyncedFolder } = yield moveSyncedBookmarksToUnsyncedParent();
+
+  do_print("Remove unsynced new folder");
+  yield PlacesUtils.bookmarks.remove(unsyncedFolder.guid);
+
+  do_print("Deleted synced items should be tracked; unsynced folder should not");
+  let changes = yield PlacesSyncUtils.bookmarks.pullChanges();
+  deepEqual(Object.keys(changes).sort(),
+    [syncedGuids.folder, syncedGuids.topBmk, syncedGuids.childBmk,
+      "menu"].sort(),
+    "Should return change records for all deleted items"
+  );
+  for (let guid of Object.values(syncedGuids)) {
+    strictEqual(changes[guid].tombstone, true,
+      `Tombstone flag should be set for deleted item ${guid}`);
+    equal(changes[guid].counter, 1,
+      `Change counter should be 1 for deleted item ${guid}`);
+    equal(changes[guid].status, PlacesUtils.bookmarks.SYNC_STATUS.NORMAL,
+      `Sync status should be normal for deleted item ${guid}`);
+  }
+
+  yield PlacesUtils.bookmarks.eraseEverything();
+  yield PlacesSyncUtils.bookmarks.reset();
+});
+
+add_task(function* test_pullChanges_import_html() {
+  yield ignoreChangedRoots();
+
+  do_print("Add unsynced bookmark");
+  let unsyncedBmk = yield PlacesUtils.bookmarks.insert({
+    type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+    parentGuid: PlacesUtils.bookmarks.menuGuid,
+    url: "https://example.com",
+  });
+
+  {
+    let fields = yield PlacesTestUtils.fetchBookmarkSyncFields(
+      unsyncedBmk.guid);
+    ok(fields.every(field =>
+      field.syncStatus == PlacesUtils.bookmarks.SYNC_STATUS.NEW
+    ), "Unsynced bookmark statuses should match");
+  }
+
+  do_print("Import new bookmarks from HTML");
+  let { path } = do_get_file("./sync_utils_bookmarks.html");
+  yield BookmarkHTMLUtils.importFromFile(path, false);
+
+  // Bookmarks.html doesn't store GUIDs, so we need to look these up.
+  let mozBmk = yield PlacesUtils.bookmarks.fetch({
+    url: "https://www.mozilla.org/",
+  });
+  let fxBmk = yield PlacesUtils.bookmarks.fetch({
+    url: "https://www.mozilla.org/en-US/firefox/",
+  });
+  // All Bookmarks.html bookmarks are stored under the menu. For toolbar
+  // bookmarks, this means they're imported into a "Bookmarks Toolbar"
+  // subfolder under the menu, instead of the real toolbar root.
+  let toolbarSubfolder = (yield PlacesUtils.bookmarks.search({
+    title: "Bookmarks Toolbar",
+  })).find(item => item.guid != PlacesUtils.bookmarks.toolbarGuid);
+  let importedFields = yield PlacesTestUtils.fetchBookmarkSyncFields(
+    mozBmk.guid, fxBmk.guid, toolbarSubfolder.guid);
+  ok(importedFields.every(field =>
+    field.syncStatus == PlacesUtils.bookmarks.SYNC_STATUS.NEW
+  ), "Sync statuses should match for HTML imports");
+
+  do_print("Fetch new HTML imports");
+  {
+    let changes = yield PlacesSyncUtils.bookmarks.pullChanges();
+    deepEqual(Object.keys(changes).sort(), [mozBmk.guid, fxBmk.guid,
+      toolbarSubfolder.guid, "menu",
+      unsyncedBmk.guid].sort(),
+      "Should return new GUIDs imported from HTML file"
+    );
+    let fields = yield PlacesTestUtils.fetchBookmarkSyncFields(
+      unsyncedBmk.guid, mozBmk.guid, fxBmk.guid, toolbarSubfolder.guid);
+    ok(fields.every(field =>
+      field.syncStatus == PlacesUtils.bookmarks.SYNC_STATUS.NORMAL
+    ), "Pulling new imports should update sync statuses");
+  }
+
+  yield PlacesUtils.bookmarks.eraseEverything();
+  yield PlacesSyncUtils.bookmarks.reset();
+});
+
+add_task(function* test_pullChanges_import_json() {
+  yield ignoreChangedRoots();
+
+  do_print("Add synced folder");
+  let syncedFolder = yield PlacesUtils.bookmarks.insert({
+    type: PlacesUtils.bookmarks.TYPE_FOLDER,
+    parentGuid: PlacesUtils.bookmarks.menuGuid,
+    title: "syncedFolder",
+  });
+  yield PlacesTestUtils.setBookmarkSyncFields({
+    guid: syncedFolder.guid,
+    syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NORMAL,
+  });
+
+  do_print("Import new bookmarks from JSON");
+  let { path } = do_get_file("./sync_utils_bookmarks.json");
+  yield BookmarkJSONUtils.importFromFile(path, false);
+  {
+    let fields = yield PlacesTestUtils.fetchBookmarkSyncFields(
+      syncedFolder.guid, "NnvGl3CRA4hC", "APzP8MupzA8l");
+    deepEqual(fields.map(field => field.syncStatus), [
+      PlacesUtils.bookmarks.SYNC_STATUS.NORMAL,
+      PlacesUtils.bookmarks.SYNC_STATUS.NEW,
+      PlacesUtils.bookmarks.SYNC_STATUS.NEW,
+    ], "Sync statuses should match for JSON imports");
+  }
+
+  do_print("Fetch new JSON imports");
+  {
+    let changes = yield PlacesSyncUtils.bookmarks.pullChanges();
+    deepEqual(Object.keys(changes).sort(), ["NnvGl3CRA4hC", "APzP8MupzA8l",
+      "menu", "toolbar", syncedFolder.guid].sort(),
+      "Should return items imported from JSON backup"
+    );
+    let fields = yield PlacesTestUtils.fetchBookmarkSyncFields(
+      syncedFolder.guid, "NnvGl3CRA4hC", "APzP8MupzA8l");
+    ok(fields.every(field =>
+      field.syncStatus == PlacesUtils.bookmarks.SYNC_STATUS.NORMAL
+    ), "Pulling new imports should update sync statuses");
+  }
+
+  yield PlacesUtils.bookmarks.eraseEverything();
+  yield PlacesSyncUtils.bookmarks.reset();
+});
+
+add_task(function* test_pullChanges_restore_json_tracked() {
+  yield ignoreChangedRoots();
+
+  let unsyncedBmk = yield PlacesUtils.bookmarks.insert({
+    type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
+    parentGuid: PlacesUtils.bookmarks.menuGuid,
+    url: "https://example.com",
+  });
+  do_print(`Unsynced bookmark GUID: ${unsyncedBmk.guid}`);
+  let syncedFolder = yield PlacesUtils.bookmarks.insert({
+    type: PlacesUtils.bookmarks.TYPE_FOLDER,
+    parentGuid: PlacesUtils.bookmarks.menuGuid,
+    title: "syncedFolder",
+  });
+  do_print(`Synced folder GUID: ${syncedFolder.guid}`);
+  yield PlacesTestUtils.setBookmarkSyncFields({
+    guid: syncedFolder.guid,
+    syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NORMAL,
+  });
+  {
+    let fields = yield PlacesTestUtils.fetchBookmarkSyncFields(
+      unsyncedBmk.guid, syncedFolder.guid);
+    deepEqual(fields.map(field => field.syncStatus), [
+      PlacesUtils.bookmarks.SYNC_STATUS.NEW,
+      PlacesUtils.bookmarks.SYNC_STATUS.NORMAL,
+    ], "Sync statuses should match before restoring from JSON");
+  }
+
+  do_print("Restore from JSON, replacing existing items");
+  let { path } = do_get_file("./sync_utils_bookmarks.json");
+  yield BookmarkJSONUtils.importFromFile(path, true);
+  {
+    let fields = yield PlacesTestUtils.fetchBookmarkSyncFields(
+      "NnvGl3CRA4hC", "APzP8MupzA8l");
+    ok(fields.every(field =>
+      field.syncStatus == PlacesUtils.bookmarks.SYNC_STATUS.UNKNOWN
+    ), "All bookmarks should be UNKNOWN after restoring from JSON");
+  }
+
+  do_print("Fetch new items restored from JSON");
+  {
+    let changes = yield PlacesSyncUtils.bookmarks.pullChanges();
+    deepEqual(Object.keys(changes).sort(), [
+      "menu",
+      "toolbar",
+      "unfiled",
+      "mobile",
+      syncedFolder.guid, // Tombstone.
+      "NnvGl3CRA4hC",
+      "APzP8MupzA8l",
+    ].sort(), "Should restore items from JSON backup");
+
+    let fields = yield PlacesTestUtils.fetchBookmarkSyncFields(
+      PlacesUtils.bookmarks.menuGuid, PlacesUtils.bookmarks.toolbarGuid,
+      PlacesUtils.bookmarks.unfiledGuid, "NnvGl3CRA4hC", "APzP8MupzA8l");
+    ok(fields.every(field =>
+      field.syncStatus == PlacesUtils.bookmarks.SYNC_STATUS.NORMAL
+    ), "NEW and UNKNOWN roots should be NORMAL after pulling restored JSON backup");
+
+    strictEqual(changes[syncedFolder.guid].tombstone, true,
+      `Should include tombstone for overwritten synced bookmark ${
+      syncedFolder.guid}`);
+  }
+
+  yield PlacesUtils.bookmarks.eraseEverything();
+  yield PlacesSyncUtils.bookmarks.reset();
+});
+
+add_task(function* test_pullChanges_custom_roots() {
+  yield ignoreChangedRoots();
+
+  do_print("Append items to Places root");
+  let unsyncedGuids = yield populateTree(PlacesUtils.bookmarks.rootGuid, {
+    kind: "folder",
+    title: "rootFolder",
+    children: [{
+      kind: "bookmark",
+      title: "childBmk",
+      url: "https://example.com",
+    }, {
+      kind: "folder",
+      title: "childFolder",
+      children: [{
+        kind: "bookmark",
+        title: "grandChildBmk",
+        url: "https://example.org",
+      }],
+    }],
+  }, {
+    kind: "bookmark",
+    title: "rootBmk",
+    url: "https://example.net",
+  });
+
+  do_print("Append items to menu");
+  let syncedGuids = yield populateTree(PlacesUtils.bookmarks.menuGuid, {
+    kind: "folder",
+    title: "childFolder",
+    children: [{
+      kind: "bookmark",
+      title: "grandChildBmk",
+      url: "https://example.info",
+    }],
+  });
+
+  {
+    let newChanges = yield PlacesSyncUtils.bookmarks.pullChanges();
+    deepEqual(Object.keys(newChanges).sort(), ["menu", syncedGuids.childFolder,
+      syncedGuids.grandChildBmk].sort(),
+      "Pulling changes should ignore custom roots");
+    yield setChangesSynced(newChanges);
+  }
+
+  do_print("Append sibling to custom root");
+  {
+    let unsyncedSibling = yield PlacesUtils.bookmarks.insert({
+      parentGuid: unsyncedGuids.rootFolder,
+      url: "https://example.club",
+    });
+    let changes = yield PlacesSyncUtils.bookmarks.pullChanges();
+    deepEqual(changes, {}, `Pulling changes should ignore unsynced sibling ${
+      unsyncedSibling.guid}`);
+  }
+
+  do_print("Clear custom root using old API");
+  {
+    let unsyncedRootId = yield PlacesUtils.promiseItemId(unsyncedGuids.rootFolder);
+    PlacesUtils.bookmarks.removeFolderChildren(unsyncedRootId);
+    let changes = yield PlacesSyncUtils.bookmarks.pullChanges();
+    deepEqual(changes, {}, "Clearing custom root should not write tombstones for children");
+  }
+
+  do_print("Remove custom root");
+  {
+    yield PlacesUtils.bookmarks.remove(unsyncedGuids.rootFolder);
+    let changes = yield PlacesSyncUtils.bookmarks.pullChanges();
+    deepEqual(changes, {}, "Removing custom root should not write tombstone");
+  }
+
+  do_print("Append sibling to menu");
+  {
+    let syncedSibling = yield PlacesUtils.bookmarks.insert({
+      parentGuid: PlacesUtils.bookmarks.menuGuid,
+      url: "https://example.ninja",
+    });
+    let changes = yield PlacesSyncUtils.bookmarks.pullChanges();
+    deepEqual(Object.keys(changes).sort(), ["menu", syncedSibling.guid].sort(),
+      "Pulling changes should track synced sibling and parent");
+    yield setChangesSynced(changes);
+  }
+
+  yield PlacesUtils.bookmarks.eraseEverything();
+  yield PlacesSyncUtils.bookmarks.reset();
+});
+
+add_task(function* test_pushChanges() {
+  yield ignoreChangedRoots();
+
+  do_print("Populate test bookmarks");
+  let guids = yield populateTree(PlacesUtils.bookmarks.menuGuid, {
+    kind: "bookmark",
+    title: "unknownBmk",
+    url: "https://example.org",
+  }, {
+    kind: "bookmark",
+    title: "syncedBmk",
+    url: "https://example.com",
+  }, {
+    kind: "bookmark",
+    title: "newBmk",
+    url: "https://example.info",
+  }, {
+    kind: "bookmark",
+    title: "deletedBmk",
+    url: "https://example.edu",
+  }, {
+    kind: "bookmark",
+    title: "unchangedBmk",
+    url: "https://example.systems",
+  });
+
+  do_print("Update sync statuses");
+  yield PlacesTestUtils.setBookmarkSyncFields({
+    guid: guids.syncedBmk,
+    syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NORMAL,
+  }, {
+    guid: guids.unknownBmk,
+    syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.UNKNOWN,
+  }, {
+    guid: guids.deletedBmk,
+    syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NORMAL,
+  }, {
+    guid: guids.unchangedBmk,
+    syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NORMAL,
+    syncChangeCounter: 0,
+  });
+
+  do_print("Change synced bookmark; should bump change counter");
+  yield PlacesUtils.bookmarks.update({
+    guid: guids.syncedBmk,
+    url: "https://example.ninja",
+  });
+
+  do_print("Remove synced bookmark");
+  {
+    yield PlacesUtils.bookmarks.remove(guids.deletedBmk);
+    let tombstones = yield PlacesTestUtils.fetchSyncTombstones();
+    ok(tombstones.some(({ guid }) => guid == guids.deletedBmk),
+      "Should write tombstone for deleted synced bookmark");
+  }
+
+  do_print("Pull changes");
+  let changes = yield PlacesSyncUtils.bookmarks.pullChanges();
+  {
+    let actualChanges = Object.entries(changes).map(([syncId, change]) => ({
+      syncId,
+      syncChangeCounter: change.counter,
+    }));
+    let expectedChanges = [{
+      syncId: guids.unknownBmk,
+      syncChangeCounter: 1,
+    }, {
+      // Parent of changed bookmarks.
+      syncId: "menu",
+      syncChangeCounter: 6,
+    }, {
+      syncId: guids.syncedBmk,
+      syncChangeCounter: 2,
+    }, {
+      syncId: guids.newBmk,
+      syncChangeCounter: 1,
+    }, {
+      syncId: guids.deletedBmk,
+      syncChangeCounter: 1,
+    }];
+    deepEqual(sortBy(actualChanges, "syncId"), sortBy(expectedChanges, "syncId"),
+      "Should return deleted, new, and unknown bookmarks"
+    );
+  }
+
+  do_print("Modify changed bookmark to bump its counter");
+  yield PlacesUtils.bookmarks.update({
+    guid: guids.newBmk,
+    url: "https://example.club",
+  });
+
+  do_print("Mark some bookmarks as synced");
+  for (let title of ["unknownBmk", "newBmk", "deletedBmk"]) {
+    let guid = guids[title];
+    strictEqual(changes[guid].synced, false,
+      "All bookmarks should not be marked as synced yet");
+    changes[guid].synced = true;
+  }
+
+  yield PlacesSyncUtils.bookmarks.pushChanges(changes);
+
+  {
+    let fields = yield PlacesTestUtils.fetchBookmarkSyncFields(
+      guids.newBmk, guids.unknownBmk);
+    ok(fields.every(field =>
+      field.syncStatus == PlacesUtils.bookmarks.SYNC_STATUS.NORMAL
+    ), "Should update sync statuses for synced bookmarks");
+  }
+
+  {
+    let tombstones = yield PlacesTestUtils.fetchSyncTombstones();
+    ok(!tombstones.some(({ guid }) => guid == guids.deletedBmk),
+      "Should remove tombstone after syncing");
+
+    let syncFields = yield PlacesTestUtils.fetchBookmarkSyncFields(
+      guids.unknownBmk, guids.syncedBmk, guids.newBmk);
+    {
+      let info = syncFields.find(field => field.guid == guids.unknownBmk);
+      equal(info.syncStatus, PlacesUtils.bookmarks.SYNC_STATUS.NORMAL,
+        "Syncing an UNKNOWN bookmark should set its sync status to NORMAL");
+      strictEqual(info.syncChangeCounter, 0,
+        "Syncing an UNKNOWN bookmark should reduce its change counter");
+    }
+    {
+      let info = syncFields.find(field => field.guid == guids.syncedBmk);
+      equal(info.syncStatus, PlacesUtils.bookmarks.SYNC_STATUS.NORMAL,
+        "Syncing a NORMAL bookmark should not update its sync status");
+      equal(info.syncChangeCounter, 2,
+        "Should not reduce counter for NORMAL bookmark not marked as synced");
+    }
+    {
+      let info = syncFields.find(field => field.guid == guids.newBmk);
+      equal(info.syncStatus, PlacesUtils.bookmarks.SYNC_STATUS.NORMAL,
+        "Syncing a NEW bookmark should update its sync status");
+      strictEqual(info.syncChangeCounter, 1,
+        "Updating new bookmark after pulling changes should bump change counter");
+    }
+  }
+
+  yield PlacesUtils.bookmarks.eraseEverything();
+  yield PlacesSyncUtils.bookmarks.reset();
+});

--- a/toolkit/components/places/tests/unit/xpcshell.ini
+++ b/toolkit/components/places/tests/unit/xpcshell.ini
@@ -14,16 +14,18 @@ support-files =
   mobile_bookmarks_folder_import.json
   mobile_bookmarks_folder_merge.json
   mobile_bookmarks_multiple_folders.json
   mobile_bookmarks_root_import.json
   mobile_bookmarks_root_merge.json
   nsDummyObserver.js
   nsDummyObserver.manifest
   places.sparse.sqlite
+  sync_utils_bookmarks.html
+  sync_utils_bookmarks.json
 
 [test_000_frecency.js]
 [test_317472.js]
 # Bug 676989: test hangs consistently on Android
 skip-if = os == "android"
 [test_331487.js]
 [test_384370.js]
 [test_385397.js]