Bug 1343103 - (1/3) WIP DONOTLAND Implement tombstone support in places draft
authorThom Chiovoloni <tchiovoloni@mozilla.com>
Fri, 02 Mar 2018 14:51:23 -0800
changeset 785892 f4a512c3c04a77b2e20dedb03b245df70887a65f
parent 782895 6276ec7ebbf33e3484997b189f20fc1511534187
child 785893 0457437ed18c8ed7ad49cfdb07fc633dd747a363
push id107354
push userbmo:tchiovoloni@mozilla.com
push dateFri, 20 Apr 2018 20:14:41 +0000
bugs1343103
milestone61.0a1
Bug 1343103 - (1/3) WIP DONOTLAND Implement tombstone support in places MozReview-Commit-ID: JwN1AZjzWah
services/sync/modules/bookmark_repair.js
services/sync/modules/bookmark_validator.js
services/sync/tests/tps/all_tests.json
services/sync/tests/tps/test_bookmark_server_wipe_fresh.js
services/sync/tests/tps/test_bookmark_server_wipe_stale.js
services/sync/tests/unit/test_bookmark_duping.js
services/sync/tests/unit/test_bookmark_engine.js
services/sync/tests/unit/test_bookmark_repair.js
services/sync/tests/unit/test_bookmark_smart_bookmarks.js
services/sync/tests/unit/test_bookmark_tombstones.js
services/sync/tests/unit/test_bookmark_tracker.js
services/sync/tests/unit/test_bookmark_validator.js
services/sync/tests/unit/test_engine_changes_during_sync.js
services/sync/tests/unit/xpcshell.ini
services/sync/tps/extensions/tps/resource/modules/bookmarks.jsm
services/sync/tps/extensions/tps/resource/tps.jsm
toolkit/components/places/BookmarkJSONUtils.jsm
toolkit/components/places/Bookmarks.jsm
toolkit/components/places/Database.cpp
toolkit/components/places/Database.h
toolkit/components/places/PlacesSyncUtils.jsm
toolkit/components/places/nsNavBookmarks.cpp
toolkit/components/places/nsNavBookmarks.h
toolkit/components/places/nsPlacesTables.h
toolkit/components/places/tests/PlacesTestUtils.jsm
toolkit/components/places/tests/bookmarks/test_sync_fields.js
toolkit/components/places/tests/head_common.js
toolkit/components/places/tests/sync/test_sync_utils.js
--- a/services/sync/modules/bookmark_repair.js
+++ b/services/sync/modules/bookmark_repair.js
@@ -173,35 +173,60 @@ class BookmarkRepairRequestor extends Co
       }
       ids.add(child);
     }
 
     return ids;
   }
 
   _countServerOnlyFixableProblems(validationInfo) {
-    const fixableProblems = ["clientMissing", "serverMissing", "serverDeleted"];
+    const fixableProblems = [
+      "clientMissing",
+      "serverMissing",
+      "clientDeleted",
+      "serverDeleted",
+      "clientMissingTombstones",
+      "serverMissingTombstones",
+    ];
     return fixableProblems.reduce((numProblems, problemLabel) => {
       return numProblems + validationInfo.problems[problemLabel].length;
     }, 0);
   }
 
   tryServerOnlyRepairs(validationInfo) {
     if (this._countServerOnlyFixableProblems(validationInfo) == 0) {
       return false;
     }
     let engine = this.service.engineManager.get("bookmarks");
+
     for (let id of validationInfo.problems.serverMissing) {
       engine.addForWeakUpload(id);
     }
-    engine.toFetch = Utils.setAddAll(
-      Utils.setAddAll(engine.toFetch,
-                      validationInfo.problems.clientMissing),
-      validationInfo.problems.serverDeleted
-    );
+
+    for (let id of validationInfo.problems.serverMissingTombstones) {
+      engine.addForWeakUpload(id, { forceTombstone: true });
+    }
+    for (let id of validationInfo.problems.clientDeleted) {
+      engine.addForWeakUpload(id, { forceTombstone: true });
+      if (validationInfo.serverRecords && validationInfo.clientRecords) {
+        // If we have the record's parent, upload it too to keep its children in
+        // sync (we can't rely on this to happen automatically like for local
+        // records, since the local record is a tombstone).
+        let serverRecord = validationInfo.serverRecords.find(r => r.id == id);
+        let parent = validationInfo.clientRecords.find(r => r.id == serverRecord.parentid);
+        if (parent) {
+          engine.addForWeakUpload(serverRecord.parentid);
+        }
+      }
+    }
+    let toFetch = engine.toFetch;
+    toFetch = Utils.setAddAll(toFetch, validationInfo.problems.clientMissing);
+    toFetch = Utils.setAddAll(toFetch, validationInfo.problems.serverDeleted);
+    toFetch = Utils.setAddAll(toFetch, validationInfo.problems.clientMissingTombstones);
+    engine.toFetch = toFetch;
     return true;
   }
 
   /* See if the repairer is willing and able to begin a repair process given
      the specified validation information.
      Returns true if a repair was started and false otherwise.
   */
   async startRepairs(validationInfo, flowID) {
@@ -632,17 +657,16 @@ class BookmarkRepairResponder extends Co
     let toUpload = new Set(); // items we will upload.
     let toDelete = new Set(); // items we will delete.
 
     let requested = new Set(request.ids);
 
     let engine = this.service.engineManager.get("bookmarks");
     // Determine every item that may be impacted by the requested IDs - eg,
     // this may include children if a requested ID is a folder.
-    // Turn an array of { recordId, syncable } into a map of recordId -> syncable.
     let repairable = await PlacesSyncUtils.bookmarks.fetchRecordIdsForRepair(request.ids);
     if (repairable.length == 0) {
       // server will get upset if we request an empty set, and we can't do
       // anything in that case, so bail now.
       return { toUpload, toDelete };
     }
 
     // which of these items exist on the server?
@@ -662,33 +686,33 @@ class BookmarkRepairResponder extends Co
     let existRemotely = new Set(itemsResponse.obj);
     // We need to be careful about handing the requested items:
     // * If the item exists locally but isn't in the tree of items we sync
     //   (eg, it might be a left-pane item or similar, we write a tombstone.
     // * If the item exists locally as a folder, we upload the folder and any
     //   children which don't exist on the server. (Note that we assume the
     //   parents *do* exist)
     // Bug 1343101 covers additional issues we might repair in the future.
-    for (let { recordId: id, syncable } of repairable) {
+    for (let { recordId: id, tombstone } of repairable) {
       if (requested.has(id)) {
-        if (syncable) {
+        if (!tombstone) {
           log.debug(`repair request to upload item '${id}' which exists locally; uploading`);
           toUpload.add(id);
         } else {
           // explicitly requested and not syncable, so tombstone.
           log.debug(`repair request to upload item '${id}' but it isn't under a syncable root; writing a tombstone`);
           toDelete.add(id);
         }
-      // The item wasn't explicitly requested - only upload if it is syncable
+      // The item wasn't explicitly requested - only upload if it's not a tombstone
       // and doesn't exist on the server.
-      } else if (syncable && !existRemotely.has(id)) {
+      } else if (!tombstone && !existRemotely.has(id)) {
         log.debug(`repair request found related item '${id}' which isn't on the server; uploading`);
         toUpload.add(id);
-      } else if (!syncable && existRemotely.has(id)) {
-        log.debug(`repair request found non-syncable related item '${id}' on the server; writing a tombstone`);
+      } else if (tombstone && existRemotely.has(id)) {
+        log.debug(`repair request found tombstone related item '${id}' on the server`);
         toDelete.add(id);
       } else {
         log.debug(`repair request found related item '${id}' which we will not upload; ignoring`);
       }
     }
     return { toUpload, toDelete };
   }
 
--- a/services/sync/modules/bookmark_validator.js
+++ b/services/sync/modules/bookmark_validator.js
@@ -70,17 +70,17 @@ function areURLsEqual(a, b) {
   for (let key of bKeys) {
     if (!aKeys.has(key)) {
       return false;
     }
   }
   return true;
 }
 
-const BOOKMARK_VALIDATOR_VERSION = 1;
+const BOOKMARK_VALIDATOR_VERSION = 2;
 
 /**
  * Result of bookmark validation. Contains the following fields which describe
  * server-side problems unless otherwise specified.
  *
  * - missingIDs (number): # of objects with missing ids
  * - duplicates (array of ids): ids seen more than once
  * - parentChildMismatches (array of {parent: parentid, child: childid}):
@@ -107,16 +107,24 @@ const BOOKMARK_VALIDATOR_VERSION = 1;
  *   aren't folders
  * - rootOnServer (boolean): true if the root came from the server
  * - badClientRoots (array of ids): Contains any client-side root ids where
  *   the root is missing or isn't a (direct) child of the places root.
  *
  * - clientMissing: Array of ids on the server missing from the client
  * - serverMissing: Array of ids on the client missing from the server
  * - serverDeleted: Array of ids on the client that the server had marked as deleted.
+ * - clientDeleted: Array of local tombstones that point to non-deleted records
+ *   on the server.
+ * - serverMissingTombstones: Array of local tombstone ids that the server has
+ *   nothing for (if the server has a non-tombstone instead this is `clientDeleted`)
+ * - clientMissingTombstones: Array of tombstones on the server that the client
+ *   has no data for.
+ * - clientTombstoneConflicts: Array of ids that the client has both tombstones
+ *   and non-tombstones for.
  * - serverUnexpected: Array of ids that appear on the server but shouldn't
  *   because the client attempts to never upload them.
  * - differences: Array of {id: string, differences: string array} recording
  *   the non-structural properties that are differente between the client and server
  * - structuralDifferences: As above, but contains the items where the differences were
  *   structural, that is, they contained childGUIDs or parentid
  */
 class BookmarkProblemData {
@@ -136,16 +144,20 @@ class BookmarkProblemData {
     this.childrenOnNonFolder = [];
     this.duplicateChildren = [];
     this.parentNotFolder = [];
 
     this.badClientRoots = [];
     this.clientMissing = [];
     this.serverMissing = [];
     this.serverDeleted = [];
+    this.clientDeleted = [];
+    this.serverMissingTombstones = [];
+    this.clientMissingTombstones = [];
+    this.clientTombstoneConflicts = [];
     this.serverUnexpected = [];
     this.differences = [];
     this.structuralDifferences = [];
   }
 
   /**
    * Convert ("difference", [{ differences: ["tags", "name"] }, { differences: ["name"] }]) into
    * [{ name: "difference:tags", count: 1}, { name: "difference:name", count: 2 }], etc.
@@ -194,16 +206,20 @@ class BookmarkProblemData {
       { name: "orphans", count: this.orphans.length },
       { name: "missingChildren", count: this.missingChildren.length },
       { name: "deletedChildren", count: this.deletedChildren.length },
       { name: "multipleParents", count: this.multipleParents.length },
       { name: "deletedParents", count: this.deletedParents.length },
       { name: "childrenOnNonFolder", count: this.childrenOnNonFolder.length },
       { name: "duplicateChildren", count: this.duplicateChildren.length },
       { name: "parentNotFolder", count: this.parentNotFolder.length },
+      { name: "clientDeleted", count: this.clientDeleted.length },
+      { name: "serverMissingTombstones", count: this.serverMissingTombstones.length },
+      { name: "clientMissingTombstones", count: this.clientMissingTombstones.length },
+      { name: "clientTombstoneConflicts", count: this.clientTombstoneConflicts.length },
     ];
     if (full) {
       let structural = this._summarizeDifferences("sdiff", this.structuralDifferences);
       result.push.apply(result, structural);
     }
     return result;
   }
 }
@@ -754,25 +770,31 @@ class BookmarkValidator {
       deletedRecords: data.deletedRecords,
       records: data.liveRecords,
       problemData: data.problemData,
       root: data.root,
     };
   }
 
   // Perform client-side sanity checking that doesn't involve server data
-  async _validateClient(problemData, clientRecords) {
+  async _validateClient(problemData, clientRecords, clientGraveyardSet) {
     problemData.clientCycles = await detectCycles(clientRecords);
     for (let rootGUID of SYNCED_ROOTS) {
       let record = clientRecords.find(record =>
         record.guid === rootGUID);
       if (!record || record.parentid !== "places") {
         problemData.badClientRoots.push(rootGUID);
       }
     }
+    for (let record of clientRecords) {
+      await this.maybeYield();
+      if (clientGraveyardSet.has(record.id)) {
+        problemData.clientTombstoneConflicts.push(record.id);
+      }
+    }
   }
 
   async _computeUnifiedRecordMap(serverRecords, clientRecords) {
     let allRecords = new Map();
     for (let sr of serverRecords) {
       await this.maybeYield();
       if (sr.fake) {
         continue;
@@ -787,22 +809,65 @@ class BookmarkValidator {
         allRecords.set(cr.id, {client: cr, server: null});
       } else {
         unified.client = cr;
       }
     }
     return allRecords;
   }
 
-  _recordMissing(problems, id, clientRecord, serverRecord, serverTombstones) {
+  // Like `new Set(collection.map(x => mapper(x)))` but yields to the event loop
+  async _asyncNewSet(collection, mapper = x => x) {
+    let set = new Set();
+    for (let item of collection) {
+      await this.maybeYield();
+      set.add(mapper(item));
+    }
+    return set;
+  }
+
+  async _checkGraveyards(problemData, unified, serverGraveyard, clientGraveyard) {
+    let server = await this._asyncNewSet(serverGraveyard, record => record.id);
+    let client = await this._asyncNewSet(clientGraveyard);
+
+    for (let id of server) {
+      await this.maybeYield();
+      if (!client.has(id)) {
+        let actualRecord = unified.get(id);
+        if (actualRecord && actualRecord.client) {
+          // Should report in problemData.serverDeleted
+          continue;
+        }
+        problemData.clientMissingTombstones.push(id);
+      }
+    }
+    for (let id of client) {
+      await this.maybeYield();
+      if (!server.has(id)) {
+        let actualRecord = unified.get(id);
+        if (actualRecord && actualRecord.server) {
+          // Should report in problemData.clientDeleted
+          continue;
+        }
+        problemData.serverMissingTombstones.push(id);
+      }
+    }
+    return { server, client };
+  }
+
+  _recordMissing(problems, id, clientRecord, serverRecord, deletions) {
     if (!clientRecord && serverRecord) {
-      problems.clientMissing.push(id);
+      if (deletions.client.has(id)) {
+        problems.clientDeleted.push(id);
+      } else {
+        problems.clientMissing.push(id);
+      }
     }
     if (!serverRecord && clientRecord) {
-      if (serverTombstones.has(id)) {
+      if (deletions.server.has(id)) {
         problems.serverDeleted.push(id);
       } else if (!clientRecord.ignored && clientRecord.id != "places") {
         problems.serverMissing.push(id);
       }
     }
   }
 
   _compareRecords(client, server) {
@@ -889,34 +954,36 @@ class BookmarkValidator {
    *
    * Returns the same data as described in the inspectServerRecords comment,
    * with the following additional fields.
    * - clientRecords: an array of client records in a similar format to
    *   the .records (ie, server records) entry.
    * - problemData is the same as for inspectServerRecords, except all properties
    *   will be filled out.
    */
-  async compareServerWithClient(serverRecords, clientTree) {
+  async compareServerWithClient(serverRecords, clientTree, clientGraveyard = []) {
     let clientRecords = await this.createClientRecordsFromTree(clientTree);
     let inspectionInfo = await this.inspectServerRecords(serverRecords);
     inspectionInfo.clientRecords = clientRecords;
 
     // Mainly do this to remove deleted items and normalize child guids.
     serverRecords = inspectionInfo.records;
     let problemData = inspectionInfo.problemData;
 
-    await this._validateClient(problemData, clientRecords);
-
     let allRecords = await this._computeUnifiedRecordMap(serverRecords, clientRecords);
 
-    let serverDeleted = new Set(inspectionInfo.deletedRecords.map(r => r.id));
+    let deletions = await this._checkGraveyards(
+      problemData, allRecords, inspectionInfo.deletedRecords, clientGraveyard);
+
+    await this._validateClient(problemData, clientRecords, deletions.client);
+
     for (let [id, {client, server}] of allRecords) {
       await this.maybeYield();
       if (!client || !server) {
-        this._recordMissing(problemData, id, client, server, serverDeleted);
+        this._recordMissing(problemData, id, client, server, deletions);
         continue;
       }
       if (server && client && client.ignored) {
         problemData.serverUnexpected.push(id);
       }
       let { differences, structuralDifferences } = this._compareRecords(client, server);
 
       if (differences.length) {
@@ -948,31 +1015,34 @@ class BookmarkValidator {
     return cleartexts;
   }
 
   async validate(engine) {
     let start = Date.now();
     let clientTree = await PlacesUtils.promiseBookmarksTree("", {
       includeItemIds: true
     });
+    let graveyard = await PlacesSyncUtils.bookmarks.promiseAllTombstones();
     let serverState = await this._getServerState(engine);
     let serverRecordCount = serverState.length;
-    let result = await this.compareServerWithClient(serverState, clientTree);
+    let result = await this.compareServerWithClient(serverState, clientTree, graveyard);
     let end = Date.now();
     let duration = end - start;
 
     engine._log.debug(`Validated bookmarks in ${duration}ms`);
     engine._log.debug(`Problem summary`);
     for (let { name, count } of result.problemData.getSummary()) {
       engine._log.debug(`  ${name}: ${count}`);
     }
 
     return {
       duration,
       version: this.version,
       problems: result.problemData,
-      recordCount: serverRecordCount
+      recordCount: serverRecordCount,
+      serverRecords: result.records,
+      clientRecords: result.clientRecords,
     };
   }
 
 }
 
 BookmarkValidator.prototype.version = BOOKMARK_VALIDATOR_VERSION;
--- a/services/sync/tests/tps/all_tests.json
+++ b/services/sync/tests/tps/all_tests.json
@@ -1,9 +1,11 @@
 { "tests": [
+    "test_bookmark_server_wipe_stale.js",
+    "test_bookmark_server_wipe_fresh.js",
     "test_bookmark_conflict.js",
     "test_sync.js",
     "test_prefs.js",
     "test_tabs.js",
     "test_passwords.js",
     "test_history.js",
     "test_formdata.js",
     "test_bug530717.js",
new file mode 100644
--- /dev/null
+++ b/services/sync/tests/tps/test_bookmark_server_wipe_fresh.js
@@ -0,0 +1,81 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+EnableEngines(["bookmarks"]);
+
+var phases = { "phase1": "profile1",
+               "phase2": "profile2",
+               "phase3": "profile3",
+               "phase4": "profile2",
+               "phase5": "profile1",
+               "phase6": "profile3" };
+
+var bookmarksInitial = {
+  "menu": [
+    { uri: "http://www.example.com/0", title: "Page 0" },
+    { uri: "http://www.example.com/1", title: "Page 1" },
+    { uri: "http://www.example.com/2", title: "Page 2" },
+    { uri: "http://www.example.com/3", title: "Page 3" }
+  ],
+};
+
+var bookmarksToDelete = {
+  "menu": [
+    { uri: "http://www.example.com/2", title: "Page 2" }
+  ],
+};
+
+var bookmarksFinal = {
+  "menu": [
+    { uri: "http://www.example.com/0", title: "Page 0" },
+    { uri: "http://www.example.com/1", title: "Page 1" },
+    { uri: "http://www.example.com/3", title: "Page 3" }
+  ],
+};
+
+// profile 1: Add bookmarks and sync them
+Phase("phase1", [
+  [Bookmarks.add, bookmarksInitial],
+  [Bookmarks.verify, bookmarksInitial],
+  [Sync],
+  [Bookmarks.verify, bookmarksInitial],
+]);
+
+// profile 2: delete some, and sync.
+Phase("phase2", [
+  [Sync],
+  [Bookmarks.verify, bookmarksInitial],
+  [Bookmarks.delete, bookmarksToDelete],
+  [Bookmarks.verifyNot, bookmarksToDelete],
+  [Bookmarks.verify, bookmarksFinal],
+  [Sync],
+]);
+
+// profile 3: sync and ensure we have the "final" bookmarks.
+Phase("phase3", [
+  [Sync],
+  [Bookmarks.verify, bookmarksFinal],
+]);
+
+// profile 2: wipe server, and sync, to simulate a node reassignment where an
+// up to date client is the uploader.
+Phase("phase4", [
+  [WipeServer],
+  [Sync],
+  [Bookmarks.verify, bookmarksFinal],
+]);
+
+// profile 1 (stale profile). Come back and sync. Ensure we've deleted the items
+// that should be gone.
+Phase("phase5", [
+  [Sync],
+  [Bookmarks.verify, bookmarksFinal],
+  [Bookmarks.verifyNot, bookmarksToDelete],
+]);
+
+// profile 3: sync again. We should not revive items from profile1.
+Phase("phase6", [
+  [Sync],
+  [Bookmarks.verify, bookmarksFinal],
+  [Bookmarks.verifyNot, bookmarksToDelete],
+]);
new file mode 100644
--- /dev/null
+++ b/services/sync/tests/tps/test_bookmark_server_wipe_stale.js
@@ -0,0 +1,82 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+EnableEngines(["bookmarks"]);
+
+var phases = { "phase1": "profile1",
+               "phase2": "profile2",
+               "phase3": "profile3",
+               "phase4": "profile1",
+               "phase5": "profile3",
+               "phase6": "profile1" };
+
+var bookmarksInitial = {
+  "menu": [
+    { uri: "http://www.example.com/0", title: "Page 0" },
+    { uri: "http://www.example.com/1", title: "Page 1" },
+    { uri: "http://www.example.com/2", title: "Page 2" },
+    { uri: "http://www.example.com/3", title: "Page 3" }
+  ],
+};
+
+var bookmarksToDelete = {
+  "menu": [
+    { uri: "http://www.example.com/2", title: "Page 2" }
+  ],
+};
+
+var bookmarksFinal = {
+  "menu": [
+    { uri: "http://www.example.com/0", title: "Page 0" },
+    { uri: "http://www.example.com/1", title: "Page 1" },
+    { uri: "http://www.example.com/3", title: "Page 3" }
+  ],
+};
+
+// profile 1: Add bookmarks and sync them
+Phase("phase1", [
+  [Bookmarks.add, bookmarksInitial],
+  [Bookmarks.verify, bookmarksInitial],
+  [Sync],
+  [Bookmarks.verify, bookmarksInitial],
+]);
+
+// profile 2: delete some, and sync. (This profile isn't used after this point,
+// to ensure that we don't only persist tombstones generated locally)
+Phase("phase2", [
+  [Sync],
+  [Bookmarks.verify, bookmarksInitial],
+  [Bookmarks.delete, bookmarksToDelete],
+  [Bookmarks.verifyNot, bookmarksToDelete],
+  [Bookmarks.verify, bookmarksFinal],
+  [Sync],
+]);
+
+// profile 3: sync and ensure we have the "final" bookmarks. (we should also have
+// the tombstones from profile 2).
+Phase("phase3", [
+  [Sync],
+  [Bookmarks.verify, bookmarksFinal],
+]);
+
+// profile 1: sync with wipeRemote, to simulate a node reassignment where an
+// old client is the uploader.
+Phase("phase4", [
+  [WipeServer],
+  [Sync],
+  [Bookmarks.verify, bookmarksInitial],
+]);
+
+// profile 3: sync again. We should not ressurect items from profile1.
+Phase("phase5", [
+  [Sync],
+  [Bookmarks.verify, bookmarksFinal],
+  [Bookmarks.verifyNot, bookmarksToDelete],
+]);
+
+// profile 1: sync again, and ensure we apply the tombstones from profile 3
+Phase("phase6", [
+  [Sync],
+  [Bookmarks.verify, bookmarksFinal],
+  [Bookmarks.verifyNot, bookmarksToDelete],
+]);
--- a/services/sync/tests/unit/test_bookmark_duping.js
+++ b/services/sync/tests/unit/test_bookmark_duping.js
@@ -30,17 +30,17 @@ async function sharedSetup() {
 }
 
 async function cleanup(engine, server) {
   await engine._tracker.stop();
   let promiseStartOver = promiseOneObserver("weave:service:start-over:finish");
   await Service.startOver();
   await promiseStartOver;
   await promiseStopServer(server);
-  await bms.eraseEverything();
+  await bms.eraseEverything({ source: bms.SOURCES.SYNC });
   await engine.resetClient();
   await engine.finalize();
 }
 
 async function recordIdToId(recordId) {
   let guid = PlacesSyncUtils.bookmarks.recordIdToGuid(recordId);
   return PlacesUtils.promiseItemId(guid);
 }
--- a/services/sync/tests/unit/test_bookmark_engine.js
+++ b/services/sync/tests/unit/test_bookmark_engine.js
@@ -121,17 +121,16 @@ add_bookmark_test(async function test_de
       "Should apply new bookmark");
 
     deepEqual(collection.keys().sort(), ["menu", "mobile", "toolbar", "unfiled", newBmk.id].sort(),
       "Should remove Places root and reading list items from server; upload local roots");
   } finally {
     await cleanup(engine, server);
   }
 });
-
 add_task(async function bad_record_allIDs() {
   let server = new SyncServer();
   server.start();
   await SyncTestingInfrastructure(server);
 
   _("Ensure that bad Places queries don't cause an error in getAllIDs.");
   let badRecord = await PlacesUtils.bookmarks.insert({
     parentGuid: PlacesUtils.bookmarks.toolbarGuid,
@@ -143,17 +142,19 @@ add_task(async function bad_record_allID
   _("Fetching all IDs.");
   let all = await fetchAllRecordIds();
 
   _("All IDs: " + JSON.stringify([...all]));
   Assert.ok(all.has("menu"));
   Assert.ok(all.has("toolbar"));
 
   _("Clean up.");
-  await PlacesUtils.bookmarks.eraseEverything();
+  await PlacesUtils.bookmarks.eraseEverything({
+    source: PlacesUtils.bookmarks.SOURCES.SYNC
+  });
   await PlacesSyncUtils.bookmarks.reset();
   await promiseStopServer(server);
 });
 
 add_bookmark_test(async function test_processIncoming_error_orderChildren(engine) {
   _("Ensure that _orderChildren() is called even when _processIncoming() throws an error.");
 
   let store  = engine._store;
--- a/services/sync/tests/unit/test_bookmark_repair.js
+++ b/services/sync/tests/unit/test_bookmark_repair.js
@@ -140,21 +140,22 @@ add_task(async function test_bookmark_re
         key: row.getResultByName("key"),
         value: row.getResultByName("value"),
       });
     }
 
     _(`Delete ${bookmarkInfo.guid} locally and on server`);
     // Now we will reach into the server and hard-delete the bookmark
     user.collection("bookmarks").remove(bookmarkInfo.guid);
-    // And delete the bookmark, but cheat by telling places that Sync did
-    // it, so we don't end up with a tombstone.
+    // And delete the bookmark, tell places we did it to avoid marking the parent,
     await PlacesUtils.bookmarks.remove(bookmarkInfo.guid, {
       source: PlacesUtils.bookmarks.SOURCE_SYNC,
     });
+    // and erase the remaining traces by deleting it's tombstone.
+    await PlacesTestUtils.clearSyncTombstones([bookmarkInfo.guid]);
     deepEqual((await PlacesSyncUtils.bookmarks.pullChanges()), {},
       `Should not upload tombstone for ${bookmarkInfo.guid}`);
 
     // Remove the bookmark from the mirror, too.
     let itemRows = await buf.db.execute(`
       SELECT guid, kind, title, urlId
       FROM items
       WHERE guid = :guid`,
@@ -295,16 +296,18 @@ add_task(async function test_bookmark_re
 
     _("Pretend to be initial client again");
     Service.clientsEngine = clientsEngine;
 
     _("Restore incomplete Places database and prefs");
     await PlacesUtils.bookmarks.remove(bookmarkInfo.guid, {
       source: PlacesUtils.bookmarks.SOURCE_SYNC,
     });
+    await PlacesTestUtils.clearSyncTombstones([bookmarkInfo.guid]);
+
     await buf.db.execute(`DELETE FROM items WHERE guid = :guid`,
                          { guid: bookmarkInfo.guid });
     await buf.db.execute(`
       REPLACE INTO meta(key, value)
       VALUES(:key, :value)`,
       metaInfos);
     restoreInitialRepairState();
     ok(Services.prefs.prefHasUserValue("services.sync.repairs.bookmarks.state"),
@@ -389,24 +392,31 @@ add_task(async function test_repair_clie
     equal(clientsEngine.stats.numClients, 2);
     await validationPromise;
 
     // Delete the bookmark localy, but cheat by telling places that Sync did
     // it, so Sync still thinks we have it.
     await PlacesUtils.bookmarks.remove(bookmarkInfo.guid, {
       source: PlacesUtils.bookmarks.SOURCE_SYNC,
     });
+
+    await PlacesTestUtils.clearSyncTombstones([bookmarkInfo.guid]);
+
     // Delete the bookmark from the mirror, too.
     let buf = await bookmarksEngine._store.ensureOpenMirror();
     await buf.db.execute(`DELETE FROM items WHERE guid = :guid`,
                          { guid: bookmarkInfo.guid });
 
     // Ensure we won't upload a tombstone for the removed bookmark.
     Assert.deepEqual((await PlacesSyncUtils.bookmarks.pullChanges()), {});
     // Ensure the bookmark no longer exists in Places.
+
+    // sanity check we aren't going to sync this removal.
+    Assert.deepEqual((await bookmarksEngine.pullNewChanges()), {});
+    // sanity check that the bookmark is not there anymore
     Assert.equal(null, await PlacesUtils.bookmarks.fetch(bookmarkInfo.guid));
 
     // sync again - we should have a few problems...
     _("Syncing again.");
     validationPromise = promiseValidationDone([
       {"name": "clientMissing", "count": 1},
       {"name": "structuralDifferences", "count": 1},
     ]);
@@ -552,8 +562,106 @@ add_task(async function test_repair_serv
     await Service.sync();
 
     // And the client deleted our bookmark
     Assert.ok(!(await PlacesUtils.bookmarks.fetch(bookmarkInfo.guid)));
   } finally {
     await cleanup(server);
   }
 });
+
+add_task(async function test_repair_client_deleted() {
+  enableValidationPrefs();
+
+  await Service.engineManager.unregister("bookmarks");
+  await Service.engineManager.register(BookmarksEngine);
+  bookmarksEngine = Service.engineManager.get("bookmarks");
+
+  let server = await serverForFoo(bookmarksEngine);
+  await SyncTestingInfrastructure(server);
+  let coll = server.user("foo").collection("bookmarks");
+  let remoteID = Utils.makeGUID();
+  try {
+
+    let folder = await PlacesUtils.bookmarks.insert({
+      parentGuid: PlacesUtils.bookmarks.toolbarGuid,
+      type: PlacesUtils.bookmarks.TYPE_FOLDER,
+      title: "title 1",
+    });
+
+    await Service.sync();
+
+    ok(!!coll.wbo(folder.guid));
+
+    server.insertWBO("foo", "clients", new ServerWBO(remoteID, encryptPayload({
+      id: remoteID,
+      name: "Remote client",
+      type: "desktop",
+      commands: [],
+      version: "54",
+      protocols: ["1.5"],
+    }), Date.now() / 1000));
+
+    let guid = Utils.makeGUID();
+
+    let remoteItem = new Bookmark("bookmarks", guid);
+    remoteItem.bmkUri = "https://example.com";
+    remoteItem.title = "bookmark";
+    remoteItem.parentid = folder.guid;
+
+    const pastDate = (Date.now() - 60000) / 1000;
+    coll.insert(guid, encryptPayload(remoteItem.cleartext), pastDate);
+
+    coll.updateRecord(folder.guid, record => {
+      record.title = "title 2";
+      record.children.push(guid);
+    });
+
+    await PlacesTestUtils.insertSyncTombstone(guid);
+
+    let validationPromise = promiseValidationDone([
+      { name: "clientDeleted", count: 1 },
+      { name: "differences", count: 1 },
+      { name: "structuralDifferences", count: 1 },
+    ]);
+
+    _("Syncing.");
+    await Service.sync();
+
+    await validationPromise;
+
+    // We shouldn't have started a repair with our second client.
+    equal((await clientsEngine.getClientCommands(remoteID)).length, 0);
+
+    ok(!coll.cleartext(guid).deleted,
+       "Server record should not have been uploaded");
+
+    equal((await PlacesUtils.bookmarks.fetch(folder.guid)).title, "title 1",
+          "Should not have remote folder's sneakily updated title");
+
+    // Trigger a sync (will upload the missing items)
+    validationPromise = promiseValidationDone([]);
+    await Service.sync();
+    await validationPromise;
+
+    equal((await PlacesUtils.bookmarks.fetch(folder.guid)).title, "title 1",
+          "Should not have redownloaded remote folder");
+
+    ok(!await PlacesUtils.bookmarks.fetch(guid),
+       "Should not have resurrected the record");
+    ok(await PlacesSyncUtils.bookmarks.isTombstone(guid),
+       "Should still have the record's tombstone");
+
+    ok(coll.cleartext(guid).deleted,
+       "Should have uploaded a tombstone to the server");
+    // should reupload the parent
+    let remoteFolder = coll.cleartext(folder.guid);
+
+    // We changed it behind it's back so that we could ensure that it didn't
+    // download the corrupted record in this process.
+    equal(remoteFolder.title, "title 1", "Should have clobbered remote title");
+    ok(!remoteFolder.children.includes(guid),
+      "Should have reuploaded the remote folder's children");
+
+  } finally {
+    await cleanup(server);
+  }
+});
--- a/services/sync/tests/unit/test_bookmark_smart_bookmarks.js
+++ b/services/sync/tests/unit/test_bookmark_smart_bookmarks.js
@@ -46,17 +46,19 @@ add_task(async function setup() {
 
 // Verify that Places smart bookmarks have their annotation uploaded and
 // handled locally.
 add_task(async function test_annotation_uploaded() {
   let server = await serverForFoo(engine);
   await SyncTestingInfrastructure(server);
 
   _("Cleaning up existing items.");
-  await PlacesUtils.bookmarks.eraseEverything();
+  await PlacesUtils.bookmarks.eraseEverything({
+    source: PlacesUtils.bookmarks.SOURCES.SYNC
+  });
 
   let startCount = smartBookmarkCount();
 
   _("Start count is " + startCount);
 
   _("Create a smart bookmark in the toolbar.");
   let url = "place:sort=" +
             Ci.nsINavHistoryQueryOptions.SORT_BY_VISITCOUNT_DESCENDING +
new file mode 100644
--- /dev/null
+++ b/services/sync/tests/unit/test_bookmark_tombstones.js
@@ -0,0 +1,122 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+ChromeUtils.import("resource://services-common/utils.js");
+ChromeUtils.import("resource://services-sync/engines.js");
+ChromeUtils.import("resource://services-sync/engines/bookmarks.js");
+ChromeUtils.import("resource://services-sync/service.js");
+ChromeUtils.import("resource://services-sync/util.js");
+ChromeUtils.import("resource://gre/modules/PlacesSyncUtils.jsm");
+
+add_task(async function initialize() {
+  await Service.engineManager.unregister("bookmarks");
+
+  enableValidationPrefs();
+  initTestLogging("Trace");
+  generateNewKeys(Service.collectionKeys);
+
+  Log.repository.getLogger("Sync.Engine.Bookmarks").level = Log.Level.Trace;
+  Log.repository.getLogger("Sync.Engine.Clients").level = Log.Level.Trace;
+  Log.repository.getLogger("Sqlite").level = Log.Level.Info; // less noisy
+  let bsu = Log.repository.getLogger("BookmarkSyncUtil");
+
+  let appender = new Log.DumpAppender();
+  bsu.ownAppenders = [appender];
+  bsu.updateAppenders();
+  bsu.level = Log.Level.Trace;
+  appender.level = Log.Level.Trace;
+});
+
+async function setup() {
+  let engine = new BookmarksEngine(Service);
+  await engine.initialize();
+  let server = await serverForFoo(engine);
+  await SyncTestingInfrastructure(server);
+  let collection = server.user("foo").collection("bookmarks");
+  let store = engine._store;
+  Svc.Obs.notify("weave:engine:start-tracking"); // We skip usual startup...
+  return { engine, server, collection, store };
+}
+
+async function shutdown(server, engine) {
+  await engine.wipeClient();
+  await engine.finalize();
+  await promiseStopServer(server);
+}
+
+function makeTombstone(id = Utils.makeGUID()) {
+  return Object.assign(new PlacesItem("bookmarks", id), { deleted: true });
+}
+
+let counter = 0;
+function makeBookmark(info) {
+  ++counter;
+  let defaultInfo = {
+    bmkUri: `https://www.example.com/${counter}`,
+    title: `example ${counter}`,
+    parentid: "toolbar",
+    parentName: "Other Bookmarks",
+  };
+  return Object.assign(new Bookmark("bookmarks", info.id || Utils.makeGUID()), defaultInfo, info);
+}
+
+add_task(async function test_general() {
+  let { engine, server, collection } = await setup();
+  try {
+    await sync_engine_and_validate_telem(engine, false);
+    _("Insert tombstones");
+    let {id: id0} = collection.insertRecord(makeTombstone());
+    let {id: id1} = collection.insertRecord(makeTombstone());
+    let {id: id2} = collection.insertRecord(makeTombstone());
+
+    await sync_engine_and_validate_telem(engine, false);
+
+    _("Make sure they're synced and not removed from the server");
+
+    let tombstones = await PlacesSyncUtils.bookmarks.promiseAllTombstones();
+
+    deepEqual([id0, id1, id2].sort(), tombstones.sort());
+    ok(collection.cleartext(id0).deleted);
+    ok(collection.cleartext(id1).deleted);
+    ok(collection.cleartext(id2).deleted);
+
+    _("Clobber one of the tombstones");
+    collection.insertRecord(makeBookmark({id: id0}));
+    collection.updateRecord("toolbar", record => {
+      record.children.push(id0);
+    }, Date.now() / 1000);
+
+    _("And add a new non-tombstone remote bookmark");
+    let {id: id3} = collection.insertRecord(
+      makeBookmark({ parentid: "menu", title: "69105" }));
+
+    collection.updateRecord("menu", record => {
+      record.children.push(id3);
+    }, Date.now() / 1000);
+    engine.lastSync = Date.now() / 1000 - 30;
+
+    await sync_engine_and_validate_telem(engine, false);
+
+    ok(await engine._isStoredTombstone(id0), "Shouldn't revive record");
+
+    ok(collection.cleartext(id0).deleted, "Should reupload tombstone");
+
+    ok(!(await PlacesSyncUtils.bookmarks.fetchChildRecordIds("toolbar")).includes(id0),
+       "Parent shouldn't have the zombie locally");
+
+    ok(!collection.cleartext("toolbar").children.includes(id0),
+       "Parent shouldn't have the zombie remotely");
+
+    ok((await PlacesSyncUtils.bookmarks.fetchChildRecordIds("menu")).includes(id3),
+       "Should the apply updated parent without issue");
+
+    equal((await PlacesUtils.bookmarks.fetch(id3)).title, "69105",
+          "Should have successfully applied the remote recod");
+
+    ok(collection.cleartext("menu").children.includes(id3),
+       "Shouldn't have touched the unconflicted server record");
+
+  } finally {
+    await shutdown(server, engine);
+  }
+});
--- a/services/sync/tests/unit/test_bookmark_tracker.js
+++ b/services/sync/tests/unit/test_bookmark_tracker.js
@@ -64,16 +64,19 @@ function promiseSpinningly(promise) {
 
 
 async function cleanup() {
   await engine.setLastSync(0);
   engine._needWeakUpload.clear();
   await store.wipe();
   await resetTracker();
   await tracker.stop();
+  await PlacesUtils.bookmarks.eraseEverything({
+    source: PlacesUtils.bookmarks.SOURCES.SYNC
+  });
 }
 
 // startTracking is a signal that the test wants to notice things that happen
 // after this is called (ie, things already tracked should be discarded.)
 async function startTracking() {
   engine._tracker.start();
   await PlacesTestUtils.markBookmarksAsSynced();
 }
@@ -894,16 +897,17 @@ add_task(async function test_onLivemarkD
     _("Insert a livemark");
     let livemark = await PlacesUtils.livemarks.addLivemark({
       parentGuid: PlacesUtils.bookmarks.menuGuid,
       feedURI: CommonUtils.makeURI("http://localhost:0"),
     });
     livemark.terminate();
 
     await startTracking();
+    await PlacesTestUtils.markBookmarksAsSynced();
 
     _("Remove a livemark");
     await PlacesUtils.livemarks.removeLivemark({
       guid: livemark.guid,
     });
 
     await verifyTrackedItems(["menu", livemark.guid]);
     Assert.equal(tracker.score, SCORE_INCREMENT_XLARGE);
--- a/services/sync/tests/unit/test_bookmark_validator.js
+++ b/services/sync/tests/unit/test_bookmark_validator.js
@@ -9,19 +9,19 @@ function run_test() {
   run_next_test();
 }
 
 async function inspectServerRecords(data) {
   let validator = new BookmarkValidator();
   return validator.inspectServerRecords(data);
 }
 
-async function compareServerWithClient(server, client) {
+async function compareServerWithClient(server, client, clientTombstones = []) {
   let validator = new BookmarkValidator();
-  return validator.compareServerWithClient(server, client);
+  return validator.compareServerWithClient(server, client, clientTombstones);
 }
 
 add_task(async function test_isr_rootOnServer() {
   let c = await inspectServerRecords([{
     id: "places",
     type: "folder",
     children: [],
   }]);
@@ -231,16 +231,130 @@ add_task(async function test_cswc_differ
     server[2].type = "bookmark";
     let c = (await compareServerWithClient(server, client)).problemData;
     equal(c.clientMissing.length, 0);
     equal(c.serverMissing.length, 0);
     deepEqual(c.differences, [{id: "cccccccccccc", differences: ["type"]}]);
   }
 });
 
+add_task(async function test_cswc_tombstones_basic() {
+  // Check that we don't report errors when nobody has any tombstones
+  {
+    let {server, client} = getDummyServerAndClient();
+    let c = (await compareServerWithClient(server, client, [])).problemData;
+    deepEqual(c.serverMissingTombstones, []);
+    deepEqual(c.clientMissingTombstones, []);
+    deepEqual(c.clientTombstoneConflicts, []);
+  }
+
+  // Check that we don't report errors when they both have the same tombstones
+  {
+    let {server, client} = getDummyServerAndClient();
+    let id = "12344321aaaa";
+    server.push({id, type: "item", deleted: true});
+    let c = (await compareServerWithClient(server, client, [id])).problemData;
+    deepEqual(c.serverMissingTombstones, []);
+    deepEqual(c.clientMissingTombstones, []);
+    deepEqual(c.clientTombstoneConflicts, []);
+    deepEqual(c.serverMissing, []);
+    deepEqual(c.clientMissing, []);
+    deepEqual(c.serverDeleted, []);
+    deepEqual(c.clientDeleted, []);
+  }
+
+  // Check that we report missing tombstones correctly
+  {
+    let {server, client} = getDummyServerAndClient();
+    let serverTombstoneID = "12344321aaaa";
+    server.push({id: serverTombstoneID, type: "item", deleted: true});
+    let clientTombstoneID = "43211234bbbb";
+    let c = (await compareServerWithClient(server, client, [
+      clientTombstoneID
+    ])).problemData;
+    deepEqual(c.serverMissingTombstones, [clientTombstoneID]);
+    deepEqual(c.clientMissingTombstones, [serverTombstoneID]);
+    deepEqual(c.clientTombstoneConflicts, []);
+    deepEqual(c.serverMissing, []);
+    deepEqual(c.clientMissing, []);
+    deepEqual(c.serverDeleted, []);
+    deepEqual(c.clientDeleted, []);
+  }
+});
+
+add_task(async function test_cswc_tombstones_clientDeleted_vs_serverMT() {
+  const getData = () => {
+    let {server, client} = getDummyServerAndClient();
+    let {guid} = client.children[0].children.pop();
+    equal(guid, server[server.length - 1].id); // sanity check
+    return {id: guid, server, client};
+  };
+  {
+    let {id, server, client} = getData();
+    let c = (await compareServerWithClient(server, client, [id])).problemData;
+    deepEqual(c.clientMissingTombstones, []);
+    deepEqual(c.serverMissingTombstones, []);
+    deepEqual(c.serverMissing, []);
+    deepEqual(c.clientMissing, []);
+    deepEqual(c.serverDeleted, []);
+    deepEqual(c.clientDeleted, [id]);
+  }
+  {
+    let {id, server, client} = getData();
+    server.pop();
+    let c = (await compareServerWithClient(server, client, [id])).problemData;
+    deepEqual(c.clientMissingTombstones, []);
+    deepEqual(c.serverMissingTombstones, [id]);
+    deepEqual(c.serverMissing, []);
+    deepEqual(c.clientMissing, []);
+    deepEqual(c.serverDeleted, []);
+    deepEqual(c.clientDeleted, []);
+  }
+});
+
+add_task(async function test_cswc_tombstones_serverDeleted_vs_clientMT() {
+  const getData = () => {
+    let {server, client} = getDummyServerAndClient();
+    let {id} = server.pop();
+    equal(id, client.children[0].children[1].guid); // sanity check
+    server.push({ id, type: "item", deleted: true });
+    return {id, server, client};
+  };
+  {
+    let {id, server, client} = getData();
+    let c = (await compareServerWithClient(server, client, [])).problemData;
+    deepEqual(c.clientMissingTombstones, []);
+    deepEqual(c.serverMissingTombstones, []);
+    deepEqual(c.clientTombstoneConflicts, []);
+    deepEqual(c.serverMissing, []);
+    deepEqual(c.clientMissing, []);
+    deepEqual(c.serverDeleted, [id]);
+    deepEqual(c.clientDeleted, []);
+  }
+  {
+    let {id, server, client} = getData();
+    client.children[0].children.pop();
+    let c = (await compareServerWithClient(server, client, [])).problemData;
+    deepEqual(c.clientMissingTombstones, [id]);
+    deepEqual(c.serverMissingTombstones, []);
+    deepEqual(c.clientTombstoneConflicts, []);
+    deepEqual(c.serverMissing, []);
+    deepEqual(c.clientMissing, []);
+    deepEqual(c.serverDeleted, []);
+    deepEqual(c.clientDeleted, []);
+  }
+});
+
+add_task(async function test_cswc_tombstone_conflict() {
+  let {server, client} = getDummyServerAndClient();
+  let id = "bbbbbbbbbbbb";
+  let c = (await compareServerWithClient(server, client, [id])).problemData;
+  deepEqual(c.clientTombstoneConflicts, [id]);
+});
+
 add_task(async function test_cswc_differentURLs() {
   let {server, client} = getDummyServerAndClient();
   client.children[0].children.push({
     guid: "dddddddddddd",
     title: "Tag query",
     "type": "text/x-moz-place",
     "uri": "place:type=7&folder=80",
   }, {
@@ -383,23 +497,26 @@ add_task(async function test_cswc_client
 
 async function validationPing(server, client, duration) {
   let pingPromise = wait_for_ping(() => {}, true); // Allow "failing" pings, since having validation info indicates failure.
   // fake this entirely
   Svc.Obs.notify("weave:service:sync:start");
   Svc.Obs.notify("weave:engine:sync:start", null, "bookmarks");
   Svc.Obs.notify("weave:engine:sync:finish", null, "bookmarks");
   let validator = new BookmarkValidator();
-  let {problemData} = await validator.compareServerWithClient(server, client);
+  let {problemData, records, clientRecords} =
+      await validator.compareServerWithClient(server, client);
   let data = {
     // We fake duration and version just so that we can verify they"re passed through.
     duration,
     version: validator.version,
     recordCount: server.length,
     problems: problemData,
+    serverRecords: records,
+    clientRecords
   };
   Svc.Obs.notify("weave:engine:validate:finish", data, "bookmarks");
   Svc.Obs.notify("weave:service:sync:finish");
   return pingPromise;
 }
 
 add_task(async function test_telemetry_integration() {
   let {server, client} = getDummyServerAndClient();
--- a/services/sync/tests/unit/test_engine_changes_during_sync.js
+++ b/services/sync/tests/unit/test_engine_changes_during_sync.js
@@ -265,16 +265,18 @@ add_task(async function test_forms_chang
 });
 
 add_task(async function test_bookmark_change_during_sync() {
   _("Ensure that we track bookmark changes made during a sync.");
 
   enableValidationPrefs();
 
   let engine = Service.engineManager.get("bookmarks");
+  await engine.resetClient();
+
   let server = await serverForEnginesWithKeys({"foo": "password"}, [engine]);
   await SyncTestingInfrastructure(server);
 
   // Already-tracked bookmarks that shouldn't be uploaded during the first sync.
   let bzBmk = await PlacesUtils.bookmarks.insert({
     parentGuid: PlacesUtils.bookmarks.menuGuid,
     url: "https://bugzilla.mozilla.org/",
     title: "Bugzilla",
--- a/services/sync/tests/unit/xpcshell.ini
+++ b/services/sync/tests/unit/xpcshell.ini
@@ -135,16 +135,17 @@ tags = addons
 [test_bookmark_duping.js]
 run-sequentially = Frequent timeouts, bug 1395148
 [test_bookmark_engine.js]
 [test_bookmark_invalid.js]
 [test_bookmark_livemarks.js]
 [test_bookmark_order.js]
 [test_bookmark_places_query_rewriting.js]
 [test_bookmark_record.js]
+[test_bookmark_tombstones.js]
 [test_bookmark_repair.js]
 skip-if = release_or_beta
 run-sequentially = Frequent timeouts, bug 1395148
 [test_bookmark_repair_requestor.js]
 # Repair is enabled only on Aurora and Nightly
 skip-if = release_or_beta
 [test_bookmark_repair_responder.js]
 skip-if = release_or_beta
--- a/services/sync/tps/extensions/tps/resource/modules/bookmarks.jsm
+++ b/services/sync/tps/extensions/tps/resource/modules/bookmarks.jsm
@@ -13,17 +13,19 @@ var EXPORTED_SYMBOLS = ["PlacesItem", "B
 ChromeUtils.import("resource://gre/modules/PlacesBackups.jsm");
 ChromeUtils.import("resource://gre/modules/PlacesSyncUtils.jsm");
 ChromeUtils.import("resource://gre/modules/PlacesUtils.jsm");
 ChromeUtils.import("resource://gre/modules/Services.jsm");
 ChromeUtils.import("resource://tps/logger.jsm");
 
 async function DumpBookmarks() {
   let [bookmarks, ] = await PlacesBackups.getBookmarksTree();
-  Logger.logInfo("Dumping Bookmarks...\n" + JSON.stringify(bookmarks, undefined, 2) + "\n\n");
+  let tombstones = await PlacesSyncUtils.bookmarks.promiseAllTombstones();
+  Logger.logInfo("Dumping Bookmarks...\n" + JSON.stringify(bookmarks, undefined, 2) + "\n");
+  Logger.logInfo("Tombstones...\n" + JSON.stringify(tombstones, undefined, 2) + "\n\n");
 }
 
 /**
  * extend, causes a child object to inherit from a parent
  */
 function extend(child, supertype) {
    child.prototype.__proto__ = supertype.prototype;
 }
--- a/services/sync/tps/extensions/tps/resource/tps.jsm
+++ b/services/sync/tps/extensions/tps/resource/tps.jsm
@@ -56,16 +56,18 @@ XPCOMUtils.defineLazyGetter(this, "fileP
 });
 
 XPCOMUtils.defineLazyGetter(this, "gTextDecoder", () => {
   return new TextDecoder();
 });
 
 ChromeUtils.defineModuleGetter(this, "NetUtil",
                                "resource://gre/modules/NetUtil.jsm");
+ChromeUtils.defineModuleGetter(this, "PlacesSyncUtils",
+                               "resource://gre/modules/PlacesSyncUtils.jsm");
 
 // Options for wiping data during a sync
 const SYNC_RESET_CLIENT = "resetClient";
 const SYNC_WIPE_CLIENT  = "wipeClient";
 const SYNC_WIPE_REMOTE  = "wipeRemote";
 
 // Actions a test can perform
 const ACTION_ADD                = "add";
@@ -694,17 +696,19 @@ var TPS = {
       let clientTree = await (PlacesUtils.promiseBookmarksTree("", {
         includeItemIds: true
       }));
       let serverRecords = await getServerBookmarkState();
       // We can't wait until catch to stringify this, since at that point it will have cycles.
       serverRecordDumpStr = JSON.stringify(serverRecords);
 
       let validator = new BookmarkValidator();
-      let {problemData} = await validator.compareServerWithClient(serverRecords, clientTree);
+      let clientTombstones = await PlacesSyncUtils.bookmarks.promiseAllTombstones();
+      let {problemData} = await validator.compareServerWithClient(
+        serverRecords, clientTree, clientTombstones);
 
       for (let {name, count} of problemData.getSummary()) {
         // Exclude mobile showing up on the server hackily so that we don't
         // report it every time, see bug 1273234 and 1274394 for more information.
         if (name === "serverUnexpected" && problemData.serverUnexpected.includes("mobile")) {
           --count;
         }
         if (count) {
--- a/toolkit/components/places/BookmarkJSONUtils.jsm
+++ b/toolkit/components/places/BookmarkJSONUtils.jsm
@@ -241,17 +241,20 @@ BookmarkImporter.prototype = {
     }
 
     // Change to nodes[0].children as we don't import the root, and also filter
     // out any obsolete "tagsFolder" sections.
     nodes = nodes[0].children.filter(node => !node.root || node.root != "tagsFolder");
 
     // If we're replacing, then erase existing bookmarks first.
     if (this._replace) {
-      await PlacesUtils.bookmarks.eraseEverything({ source: this._source });
+      await PlacesUtils.bookmarks.eraseEverything({
+        source: this._source,
+        removeTombstones: true,
+      });
     }
 
     let folderIdToGuidMap = {};
     let searchGuids = [];
 
     // Now do some cleanup on the imported nodes so that the various guids
     // match what we need for insertTree, and we also have mappings of folders
     // so we can repair any searches after inserting the bookmarks (see bug 824502).
--- a/toolkit/components/places/Bookmarks.jsm
+++ b/toolkit/components/places/Bookmarks.jsm
@@ -892,25 +892,30 @@ var Bookmarks = Object.freeze({
    * Removes ALL bookmarks, resetting the bookmarks storage to an empty tree.
    *
    * Note that roots are preserved, only their children will be removed.
    *
    * @param {Object} [options={}]
    *        Additional options. Currently supports the following properties:
    *         - source: The change source, forwarded to all bookmark observers.
    *           Defaults to nsINavBookmarksService::SOURCE_DEFAULT.
+   *         - removeTombstones: Force removal (or preservation) of tombstones,
+   *           regardless of source (by default we remove tombstones iff
+   *           the source is SOURCES.SYNC).
    *
    * @return {Promise} resolved when the removal is complete.
    * @resolves once the removal is complete.
    */
   eraseEverything(options = {}) {
     if (!options.source) {
       options.source = Bookmarks.SOURCES.DEFAULT;
     }
-
+    if (!("removeTombstones" in options)) {
+      options.removeTombstones = options.source === Bookmarks.SOURCES.SYNC;
+    }
     return PlacesUtils.withConnectionWrapper("Bookmarks.jsm: eraseEverything",
       async function(db) {
         let urls;
 
         await db.executeTransaction(async function() {
           urls = await removeFoldersContents(db, Bookmarks.userContentRoots, options);
           const time = PlacesUtils.toPRTime(new Date());
           const syncChangeDelta =
@@ -919,16 +924,19 @@ var Bookmarks = Object.freeze({
             await db.executeCached(
               `UPDATE moz_bookmarks SET lastModified = :time,
                                         syncChangeCounter = syncChangeCounter + :syncChangeDelta
                WHERE id IN (SELECT id FROM moz_bookmarks WHERE guid = :folderGuid )
               `, { folderGuid, time, syncChangeDelta });
           }
 
           await PlacesSyncUtils.bookmarks.resetSyncMetadata(db, options.source);
+          if (options.removeTombstones) {
+            await db.executeCached(`DELETE FROM moz_bookmarks_deleted`);
+          }
         });
 
         // We don't wait for the frecency calculation.
         if (urls && urls.length) {
           await PlacesUtils.keywords.eraseEverything();
           updateFrecency(db, urls, true).catch(Cu.reportError);
         }
       }
@@ -1950,17 +1958,17 @@ function removeBookmarks(items, options)
       }
 
       for (let guid of parentGuids) {
         // Mark all affected parents as changed.
         await setAncestorsLastModified(db, guid, new Date(), syncChangeDelta);
       }
 
       // Write tombstones for the removed items.
-      await insertTombstones(db, items, syncChangeDelta);
+      await insertTombstones(db, items, options.source);
     });
 
     // Update the frecencies outside of the transaction, excluding tags, so that
     // the updates can progress in the background.
     urls = urls.concat(items.filter(item => {
       let isUntagging = item._grandParentId == PlacesUtils.tagsFolderId;
       return !isUntagging && "url" in item;
     }).map(item => item.url));
@@ -2379,17 +2387,17 @@ async function(db, folderGuids, options)
          UNION ALL
          SELECT id FROM moz_bookmarks
          JOIN descendants ON parent = did
        )
        DELETE FROM moz_bookmarks WHERE id IN descendants`, { folderGuid });
   }
 
   // Write tombstones for removed items.
-  await insertTombstones(db, itemsRemoved, syncChangeDelta);
+  await insertTombstones(db, itemsRemoved, options.source);
 
   // Bump the change counter for all tagged bookmarks when removing tag
   // folders.
   await addSyncChangesForRemovedTagFolders(db, itemsRemoved, syncChangeDelta);
 
   // Cleanup orphans.
   await removeOrphanAnnotations(db);
 
@@ -2469,37 +2477,42 @@ async function maybeInsertManyPlaces(db,
        maybeguid: PlacesUtils.history.makeGuid(),
      })));
   await db.executeCached("DELETE FROM moz_updatehostsinsert_temp");
 }
 
 // Indicates whether we should write a tombstone for an item that has been
 // uploaded to the server. We ignore "NEW" and "UNKNOWN" items: "NEW" items
 // haven't been uploaded yet, and "UNKNOWN" items need a full reconciliation
-// with the server.
+// with the server. Unfortunately ignoring UNKNOWN leads to a case where we'll
+// drop a deletion (e.g. resurrect an item), for a sync user who deletes an item
+// between , but the alternative is that we store them, in which case we'll end
+// up storing tombstones on every deletion for non-sync users who have gone
+// through a bookmark restore.
 function needsTombstone(item) {
   return item._syncStatus == Bookmarks.SYNC_STATUS.NORMAL;
 }
 
 // Inserts tombstones for removed synced items.
-function insertTombstones(db, itemsRemoved, syncChangeDelta) {
-  if (!syncChangeDelta) {
+function insertTombstones(db, itemsRemoved, source) {
+  let syncStatus =
+    PlacesSyncUtils.bookmarks.determineTombstoneSyncStatus(source);
+  if (syncStatus < 1) {
     return Promise.resolve();
   }
   let syncedItems = itemsRemoved.filter(needsTombstone);
   if (!syncedItems.length) {
     return Promise.resolve();
   }
   let dateRemoved = PlacesUtils.toPRTime(Date.now());
-  let valuesTable = syncedItems.map(item => `(
-    ${JSON.stringify(item.guid)},
-    ${dateRemoved}
-  )`).join(",");
+  let valuesTable = syncedItems.map(item =>
+    `(${JSON.stringify(item.guid)}, ${dateRemoved}, ${syncStatus})`
+  ).join(",");
   return db.execute(`
-    INSERT INTO moz_bookmarks_deleted (guid, dateRemoved)
+    INSERT OR IGNORE INTO moz_bookmarks_deleted (guid, dateRemoved, syncStatus)
     VALUES ${valuesTable}`
   );
 }
 
 // Bumps the change counter for all bookmarks with URLs referenced in removed
 // tag folders.
 var addSyncChangesForRemovedTagFolders = async function(db, itemsRemoved, syncChangeDelta) {
   if (!syncChangeDelta) {
--- a/toolkit/components/places/Database.cpp
+++ b/toolkit/components/places/Database.cpp
@@ -1211,16 +1211,22 @@ Database::InitSchema(bool* aDatabaseMigr
         NS_ENSURE_SUCCESS(rv, rv);
       }
 
       if (currentSchemaVersion < 41) {
         rv = MigrateV41Up();
         NS_ENSURE_SUCCESS(rv, rv);
       }
 
+      if (currentSchemaVersion < 42) {
+        rv = MigrateV42Up();
+        NS_ENSURE_SUCCESS(rv, rv);
+      }
+
+
       // Firefox 58 uses schema version 41.
 
       if (currentSchemaVersion < 42) {
         rv = MigrateV42Up();
         NS_ENSURE_SUCCESS(rv, rv);
       }
 
       if (currentSchemaVersion < 43) {
@@ -1247,16 +1253,23 @@ Database::InitSchema(bool* aDatabaseMigr
 
       if (currentSchemaVersion < 47) {
         rv = MigrateV47Up();
         NS_ENSURE_SUCCESS(rv, rv);
       }
 
       // Firefox 61 uses schema version 47.
 
+      if (currentSchemaVersion < 48) {
+        rv = MigrateV48Up();
+        NS_ENSURE_SUCCESS(rv, rv);
+      }
+
+      // Firefox 62 uses schema version 48
+
       // Schema Upgrades must add migration code here.
       // >>> IMPORTANT! <<<
       // NEVER MIX UP SYNC AND ASYNC EXECUTION IN MIGRATORS, YOU MAY LOCK THE
       // CONNECTION AND CAUSE FURTHER STEPS TO FAIL.
       // In case, set a bool and do the async work in the ScopeExit guard just
       // before the migration steps.
     }
   }
@@ -2169,16 +2182,35 @@ Database::MigrateV47Up() {
         "AND url = 'place:excludeItems=1' "
     ") "
   ));
   NS_ENSURE_SUCCESS(rv, rv);
   return NS_OK;
 }
 
 nsresult
+Database::MigrateV48Up() {
+  MOZ_ASSERT(NS_IsMainThread());
+  // Add a sync status column for bookmark tombstones.
+  nsCOMPtr<mozIStorageStatement> tombstoneSyncStatusStmt;
+  nsresult rv = mMainConn->CreateStatement(NS_LITERAL_CSTRING(
+    "SELECT syncStatus FROM moz_bookmarks_deleted"
+  ), getter_AddRefs(tombstoneSyncStatusStmt));
+  if (NS_FAILED(rv)) {
+    rv = mMainConn->ExecuteSimpleSQL(NS_LITERAL_CSTRING(
+      "ALTER TABLE moz_bookmarks_deleted "
+      "ADD COLUMN syncStatus INTEGER DEFAULT 0 NOT NULL"
+    ));
+    NS_ENSURE_SUCCESS(rv, rv);
+  }
+
+  return NS_OK;
+}
+
+nsresult
 Database::GetItemsWithAnno(const nsACString& aAnnoName, int32_t aItemType,
                            nsTArray<int64_t>& aItemIds)
 {
   nsCOMPtr<mozIStorageStatement> stmt;
   nsresult rv = mMainConn->CreateStatement(NS_LITERAL_CSTRING(
     "SELECT b.id FROM moz_items_annos a "
     "JOIN moz_anno_attributes n ON n.id = a.anno_attribute_id "
     "JOIN moz_bookmarks b ON b.id = a.item_id "
--- a/toolkit/components/places/Database.h
+++ b/toolkit/components/places/Database.h
@@ -14,17 +14,17 @@
 #include "mozilla/storage/StatementCache.h"
 #include "mozilla/Attributes.h"
 #include "nsIEventTarget.h"
 #include "Shutdown.h"
 #include "nsCategoryCache.h"
 
 // This is the schema version. Update it at any schema change and add a
 // corresponding migrateVxx method below.
-#define DATABASE_SCHEMA_VERSION 47
+#define DATABASE_SCHEMA_VERSION 48
 
 // Fired after Places inited.
 #define TOPIC_PLACES_INIT_COMPLETE "places-init-complete"
 // This topic is received when the profile is about to be lost.  Places does
 // initial shutdown work and notifies TOPIC_PLACES_SHUTDOWN to all listeners.
 // Any shutdown work that requires the Places APIs should happen here.
 #define TOPIC_PROFILE_CHANGE_TEARDOWN "profile-change-teardown"
 // Fired when Places is shutting down.  Any code should stop accessing Places
@@ -303,16 +303,17 @@ protected:
   nsresult MigrateV40Up();
   nsresult MigrateV41Up();
   nsresult MigrateV42Up();
   nsresult MigrateV43Up();
   nsresult MigrateV44Up();
   nsresult MigrateV45Up();
   nsresult MigrateV46Up();
   nsresult MigrateV47Up();
+  nsresult MigrateV48Up();
 
   nsresult UpdateBookmarkRootTitles();
 
   friend class ConnectionShutdownBlocker;
 
   int64_t CreateMobileRoot();
   nsresult GetItemsWithAnno(const nsACString& aAnnoName, int32_t aItemType,
                             nsTArray<int64_t>& aItemIds);
--- a/toolkit/components/places/PlacesSyncUtils.jsm
+++ b/toolkit/components/places/PlacesSyncUtils.jsm
@@ -527,32 +527,32 @@ const BookmarkSyncUtils = PlacesSyncUtil
   },
 
   /**
    * Resets Sync metadata for bookmarks in Places. This function behaves
    * differently depending on the change source, and may be called from
    * `PlacesSyncUtils.bookmarks.reset` or
    * `PlacesUtils.bookmarks.eraseEverything`.
    *
-   * - RESTORE: The user is restoring from a backup. Drop the sync ID, last
-   *   sync time, and tombstones; reset sync statuses for remaining items to
-   *   "NEW"; then set a flag to wipe the server and all other clients. On the
-   *   next sync, we'll replace their bookmarks with ours.
+   * - RESTORE: The user is restoring from a backup. Drop the sync ID, last and
+   *   sync time; reset sync statuses for remaining items to "NEW"; then set a
+   *   flag to wipe the server and all other clients. On the next sync, we'll
+   *   replace their bookmarks with ours.
    *
    * - RESTORE_ON_STARTUP: Places is automatically restoring from a backup to
    *   recover from a corrupt database. The sync ID, last sync time, and
    *   tombstones don't exist, since we don't back them up; reset sync statuses
    *   for the roots to "UNKNOWN"; but don't wipe the server. On the next sync,
    *   we'll merge the restored bookmarks with the ones on the server.
    *
    * - SYNC: Either another client told us to erase our bookmarks
    *   (`PlacesSyncUtils.bookmarks.wipe`), or the user disconnected Sync
    *   (`PlacesSyncUtils.bookmarks.reset`). In both cases, drop the existing
-   *   sync ID, last sync time, and tombstones; reset sync statuses for
-   *   remaining items to "NEW"; and don't wipe the server.
+   *   sync ID, and last sync time; reset sync statuses for remaining items to
+   *   "NEW"; and don't wipe the server.
    *
    * @param db
    *        the Sqlite.jsm connection handle.
    * @param source
    *        the change source constant.
    */
   async resetSyncMetadata(db, source) {
     if (![ PlacesUtils.bookmarks.SOURCES.RESTORE,
@@ -612,55 +612,61 @@ const BookmarkSyncUtils = PlacesSyncUtil
         return childGuids.map(guid =>
           BookmarkSyncUtils.guidToRecordId(guid)
         );
       }
     );
   },
 
   /**
-   * Returns an array of `{ recordId, syncable }` tuples for all items in
+   * Returns an array of `{ recordId, tombstone }` tuples for all items in
    * `requestedRecordIds`. If any requested ID is a folder, all its descendants
    * will be included. Ancestors of non-syncable items are not included; if
    * any are missing on the server, the requesting client will need to make
    * another repair request.
    *
    * Sync calls this method to respond to incoming bookmark repair requests
    * and upload items that are missing on the server.
    */
   fetchRecordIdsForRepair(requestedRecordIds) {
     let requestedGuids = requestedRecordIds.map(BookmarkSyncUtils.recordIdToGuid);
     return PlacesUtils.withConnectionWrapper(
       "BookmarkSyncUtils: fetchRecordIdsForRepair", async function(db) {
         let rows = await db.executeCached(`
           WITH RECURSIVE
+          requestedGuids(guid) AS (
+            VALUES ${requestedGuids.map(guid => `(${JSON.stringify(guid)})`).join(",")}
+          ),
           syncedItems(id) AS (
             SELECT b.id FROM moz_bookmarks b
             WHERE b.guid IN ('menu________', 'toolbar_____', 'unfiled_____',
                              'mobile______')
             UNION ALL
             SELECT b.id FROM moz_bookmarks b
             JOIN syncedItems s ON b.parent = s.id
           ),
           descendants(id) AS (
             SELECT b.id FROM moz_bookmarks b
-            WHERE b.guid IN (${requestedGuids.map(guid => JSON.stringify(guid)).join(",")})
+            JOIN requestedGuids r ON r.guid = b.guid
             UNION ALL
             SELECT b.id FROM moz_bookmarks b
             JOIN descendants d ON d.id = b.parent
           )
-          SELECT b.guid, s.id NOT NULL AS syncable
+          SELECT b.guid, s.id IS NULL AS tombstone
           FROM descendants d
           JOIN moz_bookmarks b ON b.id = d.id
           LEFT JOIN syncedItems s ON s.id = d.id
+          UNION ALL
+          SELECT t.guid, 1 AS tombstone FROM moz_bookmarks_deleted t
+          JOIN requestedGuids r ON r.guid = t.guid
           `);
         return rows.map(row => {
           let recordId = BookmarkSyncUtils.guidToRecordId(row.getResultByName("guid"));
-          let syncable = !!row.getResultByName("syncable");
-          return { recordId, syncable };
+          let tombstone = !!row.getResultByName("tombstone");
+          return { recordId, tombstone };
         });
       }
     );
   },
 
   /**
    * Migrates an array of `{ recordId, modified }` tuples from the old JSON-based
    * tracker to the new sync change counter. `modified` is when the change was
@@ -694,17 +700,19 @@ const BookmarkSyncUtils = PlacesSyncUtil
               JOIN syncedItems s ON b.parent = s.id
             )
             UPDATE moz_bookmarks SET
               syncStatus = :syncStatus,
               syncChangeCounter = 0
             WHERE id IN syncedItems`,
             { syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NORMAL });
 
-          await db.executeCached(`DELETE FROM moz_bookmarks_deleted`);
+          await db.executeCached(`
+            UPDATE moz_bookmarks_deleted
+            SET syncStatus = ${PlacesUtils.bookmarks.SYNC_STATUS.NORMAL}`);
 
           await db.executeCached(`CREATE TEMP TABLE moz_bookmarks_tracked (
             guid TEXT PRIMARY KEY,
             time INTEGER
           )`);
 
           try {
             for (let { recordId, modified } of entries) {
@@ -734,22 +742,23 @@ const BookmarkSyncUtils = PlacesSyncUtil
                      b.syncChangeCounter + 1, b.syncStatus
               FROM moz_bookmarks b
               JOIN moz_bookmarks_tracked t ON b.guid = t.guid`);
 
             // Insert tombstones for nonexistent tracked items, using the most
             // recent deletion date for more accurate reconciliation. We assume
             // the tracked item belongs to a synced root.
             await db.executeCached(`
-              INSERT OR REPLACE INTO moz_bookmarks_deleted (guid, dateRemoved)
+              INSERT OR REPLACE INTO moz_bookmarks_deleted (guid, dateRemoved, syncStatus)
               SELECT t.guid, MAX(IFNULL((SELECT dateRemoved FROM moz_bookmarks_deleted
-                                         WHERE guid = t.guid), 0), t.time)
+                                         WHERE guid = t.guid), 0), t.time), :syncStatus
               FROM moz_bookmarks_tracked t
               LEFT JOIN moz_bookmarks b ON t.guid = b.guid
-              WHERE b.guid IS NULL`);
+              WHERE b.guid IS NULL`,
+              { syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NEW });
           } finally {
             await db.executeCached(`DROP TABLE moz_bookmarks_tracked`);
           }
         });
       }
     );
   },
 
@@ -798,18 +807,20 @@ const BookmarkSyncUtils = PlacesSyncUtil
             FROM moz_bookmarks b
             JOIN syncedItems s ON b.parent = s.id
           ),
           changedItems(guid) AS (
             SELECT guid FROM syncedItems
             WHERE syncChangeCounter >= 1
             UNION ALL
             SELECT guid FROM moz_bookmarks_deleted
+            WHERE syncStatus <> :syncStatus
           )
-          SELECT EXISTS(SELECT guid FROM changedItems) AS haveChanges`);
+          SELECT EXISTS(SELECT guid FROM changedItems) AS haveChanges`,
+          { syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NORMAL });
         return !!rows[0].getResultByName("haveChanges");
       }
     );
   },
 
   /**
    * Returns a changeset containing local bookmark changes since the last sync.
    *
@@ -851,17 +862,17 @@ const BookmarkSyncUtils = PlacesSyncUtil
    * @return {Promise} resolved once all records have been updated.
    */
   pushChanges(changeRecords) {
     return PlacesUtils.withConnectionWrapper(
       "BookmarkSyncUtils: pushChanges", async function(db) {
         let skippedCount = 0;
         let weakCount = 0;
         let updateParams = [];
-        let tombstoneGuidsToRemove = [];
+        let syncedTombstoneGuids = [];
 
         for (let recordId in changeRecords) {
           // Validate change records to catch coding errors.
           let changeRecord = validateChangeRecord(
             "BookmarkSyncUtils: pushChanges",
             changeRecords[recordId], {
               tombstone: { required: true },
               counter: { required: true },
@@ -880,53 +891,67 @@ const BookmarkSyncUtils = PlacesSyncUtil
           // try again on the next sync.
           if (!changeRecord.synced) {
             skippedCount++;
             continue;
           }
 
           let guid = BookmarkSyncUtils.recordIdToGuid(recordId);
           if (changeRecord.tombstone) {
-            tombstoneGuidsToRemove.push(guid);
+            if (changeRecord.status != PlacesUtils.bookmarks.SYNC_STATUS.NORMAL) {
+              // Ignore already-synced tombstones.
+              syncedTombstoneGuids.push(guid);
+            }
           } else {
             updateParams.push({
               guid,
               syncChangeDelta: changeRecord.counter,
               syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NORMAL,
             });
           }
         }
 
         // 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.
-        if (updateParams.length || tombstoneGuidsToRemove.length) {
+        if (updateParams.length || syncedTombstoneGuids.length) {
           await db.executeTransaction(async function() {
             if (updateParams.length) {
               await db.executeCached(`
                 UPDATE moz_bookmarks
                 SET syncChangeCounter = MAX(syncChangeCounter - :syncChangeDelta, 0),
                     syncStatus = :syncStatus
                 WHERE guid = :guid`,
                 updateParams);
               // and if there are *both* bookmarks and tombstones for these
               // items, we nuke the tombstones.
               // This should be unlikely, but bad if it happens.
               let dupedGuids = updateParams.map(({ guid }) => guid);
               await removeUndeletedTombstones(db, dupedGuids);
             }
-            await removeTombstones(db, tombstoneGuidsToRemove);
+            // Mark all synced tombstones as such.
+            if (syncedTombstoneGuids.length) {
+              let guidStrings = syncedTombstoneGuids.map(guid => JSON.stringify(guid));
+
+              await db.executeCached(`
+                UPDATE moz_bookmarks_deleted
+                SET syncStatus = :syncStatus
+                WHERE guid IN (${guidStrings.join(",")})`,
+                { syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NORMAL }
+              );
+            }
           });
         }
 
         BookmarkSyncLog.debug(`pushChanges: Processed change records`,
                               { weak: weakCount,
                                 skipped: skippedCount,
-                                updated: updateParams.length });
+                                updated: updateParams.length,
+                                tombstonesUpdated: syncedTombstoneGuids.length });
       }
     );
   },
 
   /**
    * Removes items from the database. Sync buffers incoming tombstones, and
    * calls this method to apply them at the end of each sync. Deletion
    * happens in three steps:
@@ -948,50 +973,58 @@ const BookmarkSyncUtils = PlacesSyncUtil
   remove(recordIds) {
     if (!recordIds.length) {
       return null;
     }
 
     return PlacesUtils.withConnectionWrapper("BookmarkSyncUtils: remove",
       async function(db) {
         let folderGuids = [];
+        let tombstones = [];
         for (let recordId of recordIds) {
           if (recordId in ROOT_RECORD_ID_TO_GUID) {
             BookmarkSyncLog.warn(`remove: Refusing to remove root ${recordId}`);
             continue;
           }
           let guid = BookmarkSyncUtils.recordIdToGuid(recordId);
           let bookmarkItem = await PlacesUtils.bookmarks.fetch(guid);
           if (!bookmarkItem) {
-            BookmarkSyncLog.trace(`remove: Item ${guid} already removed`);
+            BookmarkSyncLog.trace(`remove: Item ${guid} doesn't exist or is already removed`);
+            tombstones.push(recordId);
             continue;
           }
           let kind = await getKindForItem(db, bookmarkItem);
           if (kind == BookmarkSyncUtils.KINDS.FOLDER) {
             folderGuids.push(bookmarkItem.guid);
             continue;
           }
           let wasRemoved = await deleteSyncedAtom(bookmarkItem);
           if (wasRemoved) {
-             BookmarkSyncLog.trace(`remove: Removed item ${guid} with ` +
-                                   `kind ${kind}`);
+            tombstones.push(recordId);
+            BookmarkSyncLog.trace(`remove: Removed item ${guid} with ` +
+                                  `kind ${kind}`);
           }
         }
 
         for (let guid of folderGuids) {
           let bookmarkItem = await PlacesUtils.bookmarks.fetch(guid);
           if (!bookmarkItem) {
+            tombstones.push(guid);
             BookmarkSyncLog.trace(`remove: Folder ${guid} already removed`);
             continue;
           }
           let wasRemoved = await deleteSyncedFolder(db, bookmarkItem);
           if (wasRemoved) {
+            tombstones.push(guid);
             BookmarkSyncLog.trace(`remove: Removed folder ${bookmarkItem.guid}`);
           }
         }
+        if (tombstones.length) {
+          await insertTombstonesIfMissing(db, tombstones);
+        }
 
         // TODO (Bug 1313890): Refactor the bookmarks engine to pull change records
         // before uploading, instead of returning records to merge into the engine's
         // initial changeset.
         return pullSyncChanges(db);
       }
     );
   },
@@ -1051,19 +1084,18 @@ const BookmarkSyncUtils = PlacesSyncUtil
    */
   wipe() {
     return PlacesUtils.bookmarks.eraseEverything({
       source: SOURCE_SYNC,
     });
   },
 
   /**
-   * Marks all bookmarks as "NEW" and removes all tombstones. Unlike `wipe`,
-   * this keeps all existing bookmarks, and only clears their sync change
-   * tracking info.
+   * Marks all bookmarks and tombstones as "NEW". 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() {
     return PlacesUtils.withConnectionWrapper(
       "BookmarkSyncUtils: reset", function(db) {
         return db.executeTransaction(async function() {
           await BookmarkSyncUtils.resetSyncMetadata(db, SOURCE_SYNC);
@@ -1101,16 +1133,31 @@ const BookmarkSyncUtils = PlacesSyncUtil
     return PlacesUtils.withConnectionWrapper("BookmarkSyncUtils: dedupe", db =>
       dedupeSyncBookmark(db, BookmarkSyncUtils.recordIdToGuid(localRecordId),
                          BookmarkSyncUtils.recordIdToGuid(remoteRecordId),
                          BookmarkSyncUtils.recordIdToGuid(remoteParentRecordId))
     );
   },
 
   /**
+   * Returns the sync status for a tombstone based on the change source, or -1
+   * if the tombstone shouldn't be inserted.
+   */
+  determineTombstoneSyncStatus(source) {
+    if (source == PlacesUtils.bookmarks.SOURCES.SYNC) {
+      return PlacesUtils.bookmarks.SYNC_STATUS.NORMAL;
+    }
+    let syncChangeDelta = BookmarkSyncUtils.determineSyncChangeDelta(source);
+    if (syncChangeDelta) {
+      return PlacesUtils.bookmarks.SYNC_STATUS.NEW;
+    }
+    return -1;
+  },
+
+  /**
    * 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.
@@ -1344,16 +1391,82 @@ const BookmarkSyncUtils = PlacesSyncUtil
   /**
    * Fetches an array of GUIDs for items that have an annotation set with the
    * given value.
    */
   async fetchGuidsWithAnno(anno, val) {
     let db = await PlacesUtils.promiseDBConnection();
     return fetchGuidsWithAnno(db, anno, val);
   },
+
+  /**
+   * Does `recordId` refer to a bookmark or a tombstone?
+   */
+  async isBookmarkOrTombstone(recordId) {
+    PlacesUtils.SYNC_BOOKMARK_VALIDATORS.recordId(recordId);
+    let guid = BookmarkSyncUtils.recordIdToGuid(recordId);
+    let db = await PlacesUtils.promiseDBConnection();
+    let result = await db.executeCached(`
+      SELECT 1 FROM moz_bookmarks WHERE guid = :guid
+      UNION ALL
+      SELECT 1 FROM moz_bookmarks_deleted WHERE guid = :guid
+      `, { guid });
+    return result.length != 0;
+  },
+
+  async touchTombstone(recordId) {
+    PlacesUtils.SYNC_BOOKMARK_VALIDATORS.recordId(recordId);
+    return PlacesUtils.withConnectionWrapper("BookmarkSyncUtils: touchTombstone",
+                                             async db => {
+      let guid = BookmarkSyncUtils.recordIdToGuid(recordId);
+
+      await db.executeCached(`
+        UPDATE moz_bookmarks_deleted
+        SET syncStatus = :syncStatus
+        WHERE guid = :guid`,
+        { guid, syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NEW });
+      // Fabricate a change row to avoid needing to call pullSyncChanges
+      return {
+        [recordId]: {
+          modified: await tombstoneDateRemoved(db, guid),
+          counter: 1,
+          status: PlacesUtils.bookmarks.SYNC_STATUS.NEW,
+          tombstone: true,
+          synced: false
+        }
+      };
+    });
+  },
+
+  /**
+   * Returns true if the record is a tombstone. Otherwise, false.
+   */
+  async isTombstone(recordId) {
+    PlacesUtils.SYNC_BOOKMARK_VALIDATORS.recordId(recordId);
+    let guid = BookmarkSyncUtils.recordIdToGuid(recordId);
+    let db = await PlacesUtils.promiseDBConnection();
+    let result = await tombstoneDateRemoved(db, guid);
+    return result >= 0;
+  },
+
+  /**
+   * Fetch the set of all tombstones. Or, at least their `guid`s at least.
+   * Used for validation.
+   */
+  async promiseAllTombstones() {
+    let db = await PlacesUtils.promiseDBConnection();
+    let rows = await db.executeCached(`
+      SELECT guid FROM moz_bookmarks_deleted
+    `);
+    // guidToRecordId shouldn't make a difference (it's an error to have
+    // tombstones for any records where it might matter), but the caller
+    // might be/often is the bookmark validator.
+    return rows.map(row =>
+      BookmarkSyncUtils.guidToRecordId(row.getResultByName("guid")));
+  },
 });
 
 XPCOMUtils.defineLazyGetter(this, "HistorySyncLog", () => {
   return Log.repository.getLogger("Sync.Engine.History.HistorySyncUtils");
 });
 
 XPCOMUtils.defineLazyGetter(this, "BookmarkSyncLog", () => {
   // Use a sub-log of the bookmarks engine, so setting the level for that
@@ -1939,18 +2052,22 @@ function tagItem(item, tags) {
 
   // Remove leading and trailing whitespace, then filter out empty tags.
   let newTags = tags ? 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);
-  if (newTags && newTags.length > 0)
-    PlacesUtils.tagging.tagURI(dummyURI, newTags, SOURCE_SYNC);
+  if (newTags && newTags.length > 0) {
+    // Don't pass the real source since that causes it to be created with
+    // NORMAL status. This would make us leave a tombstone around when we
+    // remove it.
+    PlacesUtils.tagging.tagURI(dummyURI, newTags);
+  }
   PlacesUtils.tagging.untagURI(bookmarkURI, null, SOURCE_SYNC);
   if (newTags && newTags.length > 0)
     PlacesUtils.tagging.tagURI(bookmarkURI, newTags, SOURCE_SYNC);
   PlacesUtils.tagging.untagURI(dummyURI, null, SOURCE_SYNC);
 
   return newTags;
 }
 
@@ -2172,16 +2289,30 @@ async function fetchQueryItem(db, bookma
                             BookmarkSyncUtils.SMART_BOOKMARKS_ANNO);
   if (query) {
     item.query = query;
   }
 
   return item;
 }
 
+async function tombstoneDateRemoved(db, guid) {
+  let rows = await db.executeCached(`
+    SELECT dateRemoved
+    FROM moz_bookmarks_deleted
+    WHERE guid = :guid`,
+    { guid }
+  );
+  if (!rows.length) {
+    return -1;
+  }
+  let removedPRTime = rows[0].getResultByName("dateRemoved");
+  return removedPRTime / MICROSECONDS_PER_SECOND;
+}
+
 function addRowToChangeRecords(row, changeRecords) {
   let guid = row.getResultByName("guid");
   if (!guid) {
     throw new Error(`Changed item missing GUID`);
   }
   let isTombstone = !!row.getResultByName("tombstone");
   let recordId = BookmarkSyncUtils.guidToRecordId(guid);
   if (recordId in changeRecords) {
@@ -2242,19 +2373,20 @@ var pullSyncChanges = async function(db)
       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 });
+           syncStatus, 1 AS tombstone
+    FROM moz_bookmarks_deleted
+    WHERE syncStatus <> :syncStatus`,
+    { syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NORMAL });
   for (let row of rows) {
     addRowToChangeRecords(row, changeRecords);
   }
 
   return changeRecords;
 };
 
 var touchSyncBookmark = async function(db, bookmarkItem) {
@@ -2299,18 +2431,16 @@ var dedupeSyncBookmark = async function(
 
   let localParentGuid = rows[0].getResultByName("parentGuid");
   let sameParent = localParentGuid == remoteParentGuid;
   let modified = PlacesUtils.toPRTime(Date.now());
 
   await db.executeTransaction(async function() {
     // Change the item's old GUID to the new remote GUID. This will throw a
     // constraint error if the remote GUID already exists locally.
-    BookmarkSyncLog.debug("dedupeSyncBookmark: Switching local GUID " +
-                          localGuid + " to incoming GUID " + remoteGuid);
     await db.executeCached(`UPDATE moz_bookmarks
       SET guid = :remoteGuid
       WHERE id = :localId`,
       { remoteGuid, localId });
     PlacesUtils.invalidateCachedGuidFor(localId);
 
     // And mark the parent as being modified. Given we de-dupe based on the
     // parent *name* it's possible the item having its GUID changed has a
@@ -2339,19 +2469,19 @@ var dedupeSyncBookmark = async function(
         { remoteParentGuid });
     }
 
     // The local, duplicate ID is always deleted on the server - but for
     // bookmarks it is a logical delete.
     let localSyncStatus = rows[0].getResultByName("syncStatus");
     if (localSyncStatus == PlacesUtils.bookmarks.SYNC_STATUS.NORMAL) {
       await db.executeCached(`
-        INSERT INTO moz_bookmarks_deleted (guid, dateRemoved)
-        VALUES (:localGuid, :modified)`,
-        { localGuid, modified });
+        INSERT INTO moz_bookmarks_deleted (guid, dateRemoved, syncStatus)
+        VALUES (:localGuid, :modified, :status)`,
+        { localGuid, modified, status: PlacesUtils.bookmarks.SYNC_STATUS.NEW });
     }
   });
 
   let observers = PlacesUtils.bookmarks.getObservers();
   notify(observers, "onItemChanged", [ localId, "guid", false,
                                        remoteGuid,
                                        modified,
                                        bookmarkType,
@@ -2386,17 +2516,17 @@ async function deleteSyncedFolder(db, bo
   // to the parent of the folder we're about to delete.
   let childGuids = await fetchChildGuids(db, bookmarkItem.guid);
   if (!childGuids.length) {
     // No children -- just delete the folder.
     return deleteSyncedAtom(bookmarkItem);
   }
 
   if (BookmarkSyncLog.level <= Log.Level.Trace) {
-    BookmarkSyncLog.trace(
+    BookmarkSyncLog.debug(
       `deleteSyncedFolder: Moving ${JSON.stringify(childGuids)} children of ` +
       `"${bookmarkItem.guid}" to grandparent
       "${BookmarkSyncUtils.guidToRecordId(bookmarkItem.parentGuid)}" before ` +
       `deletion`);
   }
 
   // Move children out of the parent and into the grandparent
   for (let guid of childGuids) {
@@ -2428,41 +2558,61 @@ async function deleteSyncedFolder(db, bo
     // We failed, probably because someone added something to this folder
     // between when we got the children and now (or the database is corrupt,
     // or something else happened...) This is unlikely, but possible. To
     // avoid corruption in this case, we need to reupload the record to the
     // server.
     //
     // (Ideally this whole operation would be done in a transaction, and this
     // wouldn't be possible).
-    BookmarkSyncLog.trace(`deleteSyncedFolder: Error removing parent ` +
+    BookmarkSyncLog.warn(`deleteSyncedFolder: Error removing parent ` +
                           `${bookmarkItem.guid} after reparenting children`, e);
     return false;
   }
 
   return true;
 }
 
 // Removes a synced bookmark or empty folder from the database.
 var deleteSyncedAtom = async function(bookmarkItem) {
   try {
     await PlacesUtils.bookmarks.remove(bookmarkItem.guid, {
       preventRemovalOfNonEmptyFolders: true,
       source: SOURCE_SYNC,
     });
   } catch (ex) {
     // Likely already removed.
-    BookmarkSyncLog.trace(`deleteSyncedAtom: Error removing ` +
+    BookmarkSyncLog.warn(`deleteSyncedAtom: Error removing ` +
                           bookmarkItem.guid, ex);
     return false;
   }
 
   return true;
 };
 
+async function insertTombstonesIfMissing(db, tombstoneGuids) {
+  if (tombstoneGuids.length == 0) {
+    return;
+  }
+  await db.execute(`
+    WITH just_deleted(guid) AS (
+      VALUES ${tombstoneGuids.map(guid => `(${JSON.stringify(guid)})`).join(",")}
+    )
+    INSERT OR REPLACE INTO moz_bookmarks_deleted (guid, dateRemoved, syncStatus)
+      SELECT d.guid,
+             IFNULL((SELECT dateRemoved FROM moz_bookmarks_deleted
+                     WHERE guid = d.guid), :date),
+             :syncStatus
+      FROM just_deleted d
+      LEFT JOIN moz_bookmarks b ON d.guid = b.guid
+      WHERE b.guid IS NULL`,
+      { date: PlacesUtils.toPRTime(Date.now()),
+        syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NORMAL });
+}
+
 /**
  * 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`).
  */
@@ -2485,30 +2635,16 @@ function markChangesAsSyncing(db, change
   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.
- *
- * @return {Promise}
- */
-var removeTombstones = 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(",")})`);
-};
-
-/**
  * Removes tombstones for successfully synced items where the specified GUID
  * exists in *both* the bookmarks and tombstones tables.
  *
  * @return {Promise}
  */
 var removeUndeletedTombstones = function(db, guids) {
   if (!guids.length) {
     return Promise.resolve();
@@ -2551,28 +2687,31 @@ async function setBookmarksSyncId(db, ne
   await PlacesUtils.metadata.setWithConnection(db,
     BookmarkSyncUtils.SYNC_ID_META_KEY, newSyncId);
 
   await PlacesUtils.metadata.deleteWithConnection(db,
     BookmarkSyncUtils.LAST_SYNC_META_KEY,
     BookmarkSyncUtils.WIPE_REMOTE_META_KEY);
 }
 
-// Bumps the change counter and sets the given sync status for all bookmarks,
-// removes all orphan annos, and drops stale tombstones.
+// Bumps the change counter and sets the given sync status for all bookmarks and
+// tombstones, and removes all orphan annos
 async function resetAllSyncStatuses(db, syncStatus) {
   await db.execute(`
     UPDATE moz_bookmarks
     SET syncChangeCounter = 1,
         syncStatus = :syncStatus`,
     { syncStatus });
 
+  await db.execute(`
+    UPDATE moz_bookmarks_deleted
+    SET syncStatus = :syncStatus`,
+    { syncStatus });
+
   // The orphan anno isn't meaningful after a restore, disconnect, or node
   // reassignment.
   await 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.
-  await db.execute("DELETE FROM moz_bookmarks_deleted");
 }
--- a/toolkit/components/places/nsNavBookmarks.cpp
+++ b/toolkit/components/places/nsNavBookmarks.cpp
@@ -141,16 +141,28 @@ DetermineInitialSyncStatus(uint16_t aSou
     return nsINavBookmarksService::SYNC_STATUS_NORMAL;
   }
   if (aSource == nsINavBookmarksService::SOURCE_RESTORE_ON_STARTUP) {
     return nsINavBookmarksService::SYNC_STATUS_UNKNOWN;
   }
   return nsINavBookmarksService::SYNC_STATUS_NEW;
 }
 
+inline int32_t
+DetermineTombstoneSyncStatus(uint16_t aSource) {
+  if (aSource == nsINavBookmarksService::SOURCE_SYNC) {
+    return nsINavBookmarksService::SYNC_STATUS_NORMAL;
+  }
+  int32_t syncChangeDelta = DetermineSyncChangeDelta(aSource);
+  if (syncChangeDelta) {
+    return nsINavBookmarksService::SYNC_STATUS_NEW;
+  }
+  return -1;
+}
+
 // Indicates whether an item has been uploaded to the server and
 // needs a tombstone on deletion.
 inline bool
 NeedsTombstone(const BookmarkData& aBookmark) {
   return aBookmark.syncStatus == nsINavBookmarksService::SYNC_STATUS_NORMAL;
 }
 
 } // namespace
@@ -712,18 +724,19 @@ nsNavBookmarks::RemoveItem(int64_t aItem
     rv = AdjustIndices(bookmark.parentId,
                        bookmark.position + 1, INT32_MAX, -1);
     NS_ENSURE_SUCCESS(rv, rv);
   }
 
   int64_t syncChangeDelta = DetermineSyncChangeDelta(aSource);
 
   // Add a tombstone for synced items.
-  if (syncChangeDelta) {
-    rv = InsertTombstone(bookmark);
+  int32_t tombstoneSyncStatus = DetermineTombstoneSyncStatus(aSource);
+  if (tombstoneSyncStatus > -1) {
+    rv = InsertTombstone(bookmark, tombstoneSyncStatus);
     NS_ENSURE_SUCCESS(rv, rv);
   }
 
   bookmark.lastModified = RoundedPRNow();
   rv = SetItemDateInternal(LAST_MODIFIED, syncChangeDelta,
                            bookmark.parentId, bookmark.lastModified);
   NS_ENSURE_SUCCESS(rv, rv);
 
@@ -1010,18 +1023,18 @@ nsNavBookmarks::RemoveFolderChildren(int
   NS_ENSURE_SUCCESS(rv, rv);
 
   // Set the lastModified date.
   rv = SetItemDateInternal(LAST_MODIFIED, syncChangeDelta, folder.id,
                            RoundedPRNow());
   NS_ENSURE_SUCCESS(rv, rv);
 
   int64_t tagsRootId = TagsRootId();
-
-  if (syncChangeDelta) {
+  int32_t tombstoneSyncStatus = DetermineTombstoneSyncStatus(aSource);
+  if (tombstoneSyncStatus > -1) {
     nsTArray<TombstoneData> tombstones(folderChildrenArray.Length());
     PRTime dateRemoved = RoundedPRNow();
 
     for (uint32_t i = 0; i < folderChildrenArray.Length(); ++i) {
       BookmarkData& child = folderChildrenArray[i];
       if (NeedsTombstone(child)) {
         // Write tombstones for synced children.
         TombstoneData childTombstone = {child.guid, dateRemoved};
@@ -1030,18 +1043,17 @@ nsNavBookmarks::RemoveFolderChildren(int
       bool isUntagging = child.grandParentId == tagsRootId;
       if (isUntagging) {
         // Bump the change counter for all tagged bookmarks when removing a tag
         // folder.
         rv = AddSyncChangesForBookmarksWithURL(child.url, syncChangeDelta);
         NS_ENSURE_SUCCESS(rv, rv);
       }
     }
-
-    rv = InsertTombstones(tombstones);
+    rv = InsertTombstones(tombstones, tombstoneSyncStatus);
     NS_ENSURE_SUCCESS(rv, rv);
   }
 
   rv = transaction.Commit();
   NS_ENSURE_SUCCESS(rv, rv);
 
   // Call observers in reverse order to serve children before their parent.
   for (int32_t i = folderChildrenArray.Length() - 1; i >= 0; --i) {
@@ -1339,68 +1351,78 @@ nsNavBookmarks::AddSyncChangesForBookmar
   rv = statement->Execute();
   NS_ENSURE_SUCCESS(rv, rv);
 
   return NS_OK;
 }
 
 
 nsresult
-nsNavBookmarks::InsertTombstone(const BookmarkData& aBookmark)
+nsNavBookmarks::InsertTombstone(const BookmarkData& aBookmark,
+                                int32_t aSyncStatus)
 {
   if (!NeedsTombstone(aBookmark)) {
     return NS_OK;
   }
   nsCOMPtr<mozIStorageStatement> stmt = mDB->GetStatement(
-    "INSERT INTO moz_bookmarks_deleted (guid, dateRemoved) "
-    "VALUES (:guid, :date_removed)"
+    "INSERT INTO moz_bookmarks_deleted (guid, dateRemoved, syncStatus) "
+    "VALUES (:guid, :date_removed, :sync_status)"
   );
   NS_ENSURE_STATE(stmt);
   mozStorageStatementScoper scoper(stmt);
 
   nsresult rv = stmt->BindUTF8StringByName(NS_LITERAL_CSTRING("guid"),
                                            aBookmark.guid);
   NS_ENSURE_SUCCESS(rv, rv);
   rv = stmt->BindInt64ByName(NS_LITERAL_CSTRING("date_removed"),
                              RoundedPRNow());
   NS_ENSURE_SUCCESS(rv, rv);
 
+  rv = stmt->BindInt32ByName(NS_LITERAL_CSTRING("sync_status"),
+                             aSyncStatus);
+  NS_ENSURE_SUCCESS(rv, rv);
+
   rv = stmt->Execute();
   NS_ENSURE_SUCCESS(rv, rv);
 
   return NS_OK;
 }
 
 
 nsresult
-nsNavBookmarks::InsertTombstones(const nsTArray<TombstoneData>& aTombstones)
+nsNavBookmarks::InsertTombstones(const nsTArray<TombstoneData>& aTombstones,
+                                 int32_t aSyncStatus)
 {
   if (aTombstones.IsEmpty()) {
     return NS_OK;
   }
 
   size_t maxRowsPerChunk = SQLITE_MAX_VARIABLE_NUMBER / 2;
   for (uint32_t startIndex = 0; startIndex < aTombstones.Length(); startIndex += maxRowsPerChunk) {
     size_t rowsPerChunk = std::min(maxRowsPerChunk, aTombstones.Length() - startIndex);
 
     // Build a query to insert all tombstones in a single statement, chunking to
     // avoid the SQLite bound parameter limit.
     nsAutoCString tombstonesToInsert;
-    tombstonesToInsert.AppendLiteral("VALUES (?, ?)");
+    tombstonesToInsert.AppendLiteral("VALUES (?, ?, ");
+    tombstonesToInsert.AppendInt(aSyncStatus);
+    tombstonesToInsert.Append(')');
     for (uint32_t i = 1; i < rowsPerChunk; ++i) {
-      tombstonesToInsert.AppendLiteral(", (?, ?)");
+      tombstonesToInsert.AppendLiteral(", (?, ?, ");
+      tombstonesToInsert.AppendInt(aSyncStatus);
+      tombstonesToInsert.Append(')');
     }
 #ifdef DEBUG
     MOZ_ASSERT(tombstonesToInsert.CountChar('?') == rowsPerChunk * 2,
-               "Expected one binding param per column for each tombstone");
+               "Expected two binding params per column for each tombstone");
 #endif
 
     nsCOMPtr<mozIStorageStatement> stmt = mDB->GetStatement(
       NS_LITERAL_CSTRING("INSERT INTO moz_bookmarks_deleted "
-        "(guid, dateRemoved) ") +
+        "(guid, dateRemoved, syncStatus) ") +
       tombstonesToInsert
     );
     NS_ENSURE_STATE(stmt);
     mozStorageStatementScoper scoper(stmt);
 
     uint32_t paramIndex = 0;
     nsresult rv;
     for (uint32_t i = 0; i < rowsPerChunk; ++i) {
--- a/toolkit/components/places/nsNavBookmarks.h
+++ b/toolkit/components/places/nsNavBookmarks.h
@@ -263,20 +263,21 @@ private:
                                              int64_t aSyncChangeDelta);
 
   // Bumps the change counter for all bookmarked URLs within |aFolderId|. This
   // is used to update tagged bookmarks when changing or removing a tag folder.
   nsresult AddSyncChangesForBookmarksInFolder(int64_t aFolderId,
                                               int64_t aSyncChangeDelta);
 
   // Inserts a tombstone for a removed synced item.
-  nsresult InsertTombstone(const BookmarkData& aBookmark);
+  nsresult InsertTombstone(const BookmarkData& aBookmark, int32_t aSyncStatus);
 
   // Inserts tombstones for removed synced items.
-  nsresult InsertTombstones(const nsTArray<TombstoneData>& aTombstones);
+  nsresult InsertTombstones(const nsTArray<TombstoneData>& aTombstones,
+                            int32_t aSyncStatus);
 
   // Removes a stale synced bookmark tombstone.
   nsresult RemoveTombstone(const nsACString& aGUID);
 
   nsresult SetItemTitleInternal(BookmarkData& aBookmark,
                                 const nsACString& aTitle,
                                 int64_t aSyncChangeDelta);
 
--- a/toolkit/components/places/nsPlacesTables.h
+++ b/toolkit/components/places/nsPlacesTables.h
@@ -110,25 +110,28 @@
        made during a sync, and queue them for the next sync. Changes made by
        Sync don't bump the counter, to avoid sync loops. If Sync is
        disconnected, we'll reset the counter to 1 for all bookmarks.
     */ \
     ", syncChangeCounter INTEGER NOT NULL DEFAULT 1" \
   ")" \
 )
 
-// This table stores tombstones for bookmarks with SYNC_STATUS_NORMAL. We
-// upload tombstones during a sync, and delete them from this table on success.
-// If Sync is disconnected, we'll delete all stored tombstones. If Sync is
-// never set up, we'll never write new tombstones, since all bookmarks will stay
-// in SYNC_STATUS_NEW.
+// This table stores tombstones for bookmarks deleted on other devices, and
+// local bookmarks with SYNC_STATUS_NORMAL. Each tombstone has its own sync
+// status: SYNC_STATUS_NEW if it hasn't been synced yet, and SYNC_STATUS_NORMAL
+// for remote and synced local tombstones. If Sync is disconnected, bookmarks
+// are restored, or the bookmark sync id changes, we'll reset the status of all
+// tombstones to SYNC_STATUS_UNKNOWN. If Sync is never set up, we'll never write
+// new tombstones, since all bookmarks will stay in SYNC_STATUS_NEW.
 #define CREATE_MOZ_BOOKMARKS_DELETED NS_LITERAL_CSTRING( \
   "CREATE TABLE moz_bookmarks_deleted (" \
     "  guid TEXT PRIMARY KEY" \
     ", dateRemoved INTEGER NOT NULL DEFAULT 0" \
+    ", syncStatus INTEGER NOT NULL DEFAULT 0" \
   ")" \
 )
 
 #define CREATE_MOZ_KEYWORDS NS_LITERAL_CSTRING( \
   "CREATE TABLE moz_keywords (" \
     "  id INTEGER PRIMARY KEY AUTOINCREMENT" \
     ", keyword TEXT UNIQUE" \
     ", place_id INTEGER" \
--- a/toolkit/components/places/tests/PlacesTestUtils.jsm
+++ b/toolkit/components/places/tests/PlacesTestUtils.jsm
@@ -7,16 +7,18 @@ var EXPORTED_SYMBOLS = [
 Cu.importGlobalProperties(["URL"]);
 
 ChromeUtils.import("resource://gre/modules/XPCOMUtils.jsm");
 ChromeUtils.import("resource://gre/modules/Services.jsm");
 ChromeUtils.defineModuleGetter(this, "PlacesUtils",
                                "resource://gre/modules/PlacesUtils.jsm");
 ChromeUtils.defineModuleGetter(this, "TestUtils",
                                "resource://testing-common/TestUtils.jsm");
+ChromeUtils.defineModuleGetter(this, "PlacesSyncUtils",
+                               "resource://gre/modules/PlacesSyncUtils.jsm");
 
 var PlacesTestUtils = Object.freeze({
   /**
    * Asynchronously adds visits to a page.
    *
    * @param aPlaceInfo
    *        Can be an nsIURI, in such a case a single LINK visit will be added.
    *        Otherwise can be an object describing the visit to add, or an array
@@ -235,17 +237,20 @@ var PlacesTestUtils = Object.freeze({
              SELECT b.id FROM moz_bookmarks b
              JOIN syncedItems s ON b.parent = s.id
            )
            UPDATE moz_bookmarks
            SET syncChangeCounter = 0,
                syncStatus = :syncStatus
            WHERE id IN syncedItems`,
           { syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NORMAL });
-        await db.executeCached("DELETE FROM moz_bookmarks_deleted");
+        await db.executeCached(
+          `UPDATE moz_bookmarks_deleted
+           SET syncStatus = :syncStatus`,
+          { syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NORMAL });
       });
     });
   },
 
   /**
    * Sets sync fields for multiple bookmarks.
    * @param aStatusInfos
    *        One or more objects with the following properties:
@@ -303,25 +308,58 @@ var PlacesTestUtils = Object.freeze({
       });
     }
     return results;
   },
 
   async fetchSyncTombstones() {
     let db = await PlacesUtils.promiseDBConnection();
     let rows = await db.executeCached(`
-      SELECT guid, dateRemoved
+      SELECT guid, dateRemoved, syncStatus
       FROM moz_bookmarks_deleted
       ORDER BY guid`);
     return rows.map(row => ({
       guid: row.getResultByName("guid"),
       dateRemoved: PlacesUtils.toDate(row.getResultByName("dateRemoved")),
+      syncStatus: row.getResultByName("syncStatus"),
     }));
   },
 
+  /**
+   * Delete the provided array of ids from the tombstones table directly.
+   */
+  async clearSyncTombstones(ids) {
+    if (ids.length == 0) {
+      return;
+    }
+    await PlacesUtils.withConnectionWrapper("PlacesTestUtils.clearSyncTombstones", async db => {
+      let guidStrings = ids.map(id => JSON.stringify(
+        PlacesSyncUtils.bookmarks.recordIdToGuid(id)));
+      await db.execute(`DELETE FROM moz_bookmarks_deleted
+                        WHERE guid in (${guidStrings.join(",")})`);
+    });
+  },
+
+  /**
+   * Inserts `guid` as a tombstone with status `syncStatus`. `guid` must not
+   * exist in moz_bookmarks or moz_bookmarks_deleted.
+   */
+  async insertSyncTombstone(guid, syncStatus = PlacesUtils.bookmarks.SYNC_STATUS.NORMAL) {
+    if (await PlacesSyncUtils.bookmarks.isBookmarkOrTombstone(guid)) {
+      throw new Error("insertSyncTombstone should only be used with fresh guids");
+    }
+    await PlacesUtils.withConnectionWrapper("PlacesTestUtils.insertSyncTombstone", async db => {
+      await db.executeCached(`
+        INSERT INTO moz_bookmarks_deleted (guid, dateRemoved, syncStatus)
+        VALUES (:guid, :dateRemoved, :syncStatus)`,
+        { guid, syncStatus, dateRemoved: PlacesUtils.toPRTime(Date.now()) });
+      return guid;
+    });
+  },
+
   waitForNotification(notification, conditionFn = () => true, type = "bookmarks") {
     let iface = type == "bookmarks" ? Ci.nsINavBookmarkObserver
                                     : Ci.nsINavHistoryObserver;
     return new Promise(resolve => {
       let proxifiedObserver = new Proxy({}, {
         get: (target, name) => {
           if (name == "QueryInterface")
             return XPCOMUtils.generateQI([iface]);
--- a/toolkit/components/places/tests/bookmarks/test_sync_fields.js
+++ b/toolkit/components/places/tests/bookmarks/test_sync_fields.js
@@ -1,8 +1,10 @@
+ChromeUtils.import("resource://gre/modules/PlacesSyncUtils.jsm");
+
 // Tracks a set of bookmark guids and their syncChangeCounter field and
 // provides a simple way for the test to check the correct fields had the
 // counter incremented.
 class CounterTracker {
   constructor() {
     this.tracked = new Map();
   }
 
@@ -58,37 +60,37 @@ async function checkSyncFields(guid, exp
 
 // Common test cases for sync field changes.
 class TestCases {
   async run() {
     info("Test 1: inserts, updates, tags, and keywords");
     try {
       await this.testChanges();
     } finally {
-      info("Reset sync fields after test 1");
-      await PlacesTestUtils.markBookmarksAsSynced();
+      info("Wipe bookmarks after test 1");
+      await PlacesSyncUtils.bookmarks.wipe();
     }
 
     if (("moveItem" in this) && ("reorder" in this)) {
       info("Test 2: reparenting");
       try {
         await this.testReparenting();
       } finally {
-        info("Reset sync fields after test 2");
-        await PlacesTestUtils.markBookmarksAsSynced();
+        info("Wipe bookmarks after test 2");
+        await PlacesSyncUtils.bookmarks.wipe();
       }
     }
 
     if ("insertSeparator" in this) {
       info("Test 3: separators");
       try {
         await this.testSeparators();
       } finally {
-        info("Reset sync fields after test 3");
-        await PlacesTestUtils.markBookmarksAsSynced();
+        info("Wipe bookmarks after test 3");
+        await PlacesSyncUtils.bookmarks.wipe();
       }
     }
   }
 
   async testChanges() {
     let testUri = NetUtil.newURI("http://test.mozilla.org");
 
     let guid = await this.insertBookmark(PlacesUtils.bookmarks.unfiledGuid,
--- a/toolkit/components/places/tests/head_common.js
+++ b/toolkit/components/places/tests/head_common.js
@@ -1,14 +1,14 @@
 /* -*- indent-tabs-mode: nil; js-indent-level: 2 -*-
  * 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/. */
 
-const CURRENT_SCHEMA_VERSION = 47;
+const CURRENT_SCHEMA_VERSION = 48;
 const FIRST_UPGRADABLE_SCHEMA_VERSION = 30;
 
 const NS_APP_USER_PROFILE_50_DIR = "ProfD";
 
 // Shortcuts to transitions type.
 const TRANSITION_LINK = Ci.nsINavHistoryService.TRANSITION_LINK;
 const TRANSITION_TYPED = Ci.nsINavHistoryService.TRANSITION_TYPED;
 const TRANSITION_BOOKMARK = Ci.nsINavHistoryService.TRANSITION_BOOKMARK;
--- a/toolkit/components/places/tests/sync/test_sync_utils.js
+++ b/toolkit/components/places/tests/sync/test_sync_utils.js
@@ -407,18 +407,17 @@ add_task(async function test_order() {
       guids.childBmk, makeGuid(), guids.siblingBmk, guids.siblingSep,
       makeGuid(), guids.siblingFolder, makeGuid()]);
     let childRecordIds = await PlacesSyncUtils.bookmarks.fetchChildRecordIds(
       PlacesUtils.bookmarks.menuGuid);
     deepEqual(childRecordIds, [guids.childBmk, guids.siblingBmk, guids.siblingSep,
       guids.siblingFolder], "Nonexistent children should be ignored");
   }
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async function test_dedupe() {
   await ignoreChangedRoots();
 
   let parentFolder = await PlacesSyncUtils.bookmarks.insert({
     kind: "folder",
     recordId: makeGuid(),
@@ -529,31 +528,29 @@ add_task(async function test_dedupe() {
       "Change counter for every bookmark should be 1");
 
     equal(await PlacesUtils.promiseItemId(newRemoteRecordId), localId,
       "De-duping with nonexistent remote parent should cache new sync ID");
 
     await setChangesSynced(changes);
   }
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async function test_order_roots() {
   let oldOrder = await PlacesSyncUtils.bookmarks.fetchChildRecordIds(
     PlacesUtils.bookmarks.rootGuid);
   await PlacesSyncUtils.bookmarks.order(PlacesUtils.bookmarks.rootGuid,
     shuffle(oldOrder));
   let newOrder = await PlacesSyncUtils.bookmarks.fetchChildRecordIds(
     PlacesUtils.bookmarks.rootGuid);
   deepEqual(oldOrder, newOrder, "Should ignore attempts to reorder roots");
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async function test_update_tags() {
   info("Insert item without tags");
   let item = await PlacesSyncUtils.bookmarks.insert({
     kind: "bookmark",
     url: "https://mozilla.org",
     recordId: makeGuid(),
@@ -601,18 +598,17 @@ add_task(async function test_update_tags
       recordId: item.recordId,
       tags: null,
     });
     deepEqual(updatedItem.tags, [], "Should return empty tag array");
     assertURLHasTags("https://mozilla.org", [],
       "Should remove all existing tags");
   }
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async function test_pullChanges_tags() {
   await ignoreChangedRoots();
 
   info("Insert untagged items with same URL");
   let firstItem = await PlacesSyncUtils.bookmarks.insert({
     kind: "bookmark",
@@ -724,18 +720,17 @@ add_task(async function test_pullChanges
     deepEqual(Object.keys(changes).sort(),
       [untaggedItem.recordId].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");
     await setChangesSynced(changes);
   }
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async function test_update_keyword() {
   info("Insert item without keyword");
   let item = await PlacesSyncUtils.bookmarks.insert({
     kind: "bookmark",
     parentRecordId: "menu",
     url: "https://mozilla.org",
@@ -877,18 +872,17 @@ add_task(async function test_update_keyw
     let updatedItem2 = await PlacesSyncUtils.bookmarks.update({
       recordId: item2.recordId,
       keyword: "test5",
     });
     equal(updatedItem2.keyword, "test5", "New update succeeds");
   }
 
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async function test_conflicting_keywords() {
   await ignoreChangedRoots();
 
   info("Insert bookmark with new keyword");
   let tbBmk = await PlacesSyncUtils.bookmarks.insert({
     kind: "bookmark",
@@ -959,18 +953,17 @@ add_task(async function test_conflicting
     let changes = await PlacesSyncUtils.bookmarks.pullChanges();
     deepEqual(Object.keys(changes).sort(), [
       tbBmk.recordId,
       dupeTbBmk.recordId,
     ].sort(), "Should bump change counter for bookmarks with updated keyword");
     await setChangesSynced(changes);
   }
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async function test_update_annos() {
   let guids = await populateTree(PlacesUtils.bookmarks.menuGuid, {
     kind: "folder",
     title: "folder",
   }, {
     kind: "bookmark",
@@ -1022,18 +1015,17 @@ add_task(async function test_update_anno
       loadInSidebar: false,
     });
     ok(!updatedItem.loadInSidebar, "Should not return cleared sidebar anno");
     let id = await recordIdToId(updatedItem.recordId);
     ok(!PlacesUtils.annotations.itemHasAnnotation(id, LOAD_IN_SIDEBAR_ANNO),
       "Should clear sidebar anno for existing bookmark");
   }
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async function test_update_move_root() {
   info("Move root to same parent");
   {
     // This should be a no-op.
     let sameRoot = await PlacesSyncUtils.bookmarks.update({
       recordId: "menu",
@@ -1046,18 +1038,17 @@ add_task(async function test_update_move
   }
 
   info("Try reparenting root");
   await Assert.rejects(PlacesSyncUtils.bookmarks.update({
     recordId: "menu",
     parentRecordId: "toolbar",
   }));
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async function test_insert() {
   info("Insert bookmark");
   {
     let item = await PlacesSyncUtils.bookmarks.insert({
       kind: "bookmark",
       recordId: makeGuid(),
@@ -1103,18 +1094,17 @@ add_task(async function test_insert() {
       recordId: makeGuid(),
       parentRecordId: "menu",
     });
     let { type } = await PlacesUtils.bookmarks.fetch({ guid: item.recordId });
     equal(type, PlacesUtils.bookmarks.TYPE_SEPARATOR,
       "Separator should have correct type");
   }
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async function test_insert_livemark() {
   let { site, stopServer } = makeLivemarkServer();
 
   try {
     info("Insert livemark with feed URL");
     {
@@ -1154,18 +1144,17 @@ add_task(async function test_insert_live
         parentRecordId: livemarkRecordId,
       });
       ok(!livemark, "Should not insert livemark as child of livemark");
     }
   } finally {
     await stopServer();
   }
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async 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.
@@ -1339,18 +1328,17 @@ add_task(async function test_update_live
       });
       equal(livemark.guid, folder.recordId,
         "Livemark should have same GUID as replaced folder");
     }
   } finally {
     await stopServer();
   }
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async function test_insert_tags() {
   await Promise.all([{
     kind: "bookmark",
     url: "https://example.com",
     recordId: makeGuid(),
     parentRecordId: "menu",
@@ -1375,18 +1363,17 @@ add_task(async function test_insert_tags
     "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");
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async function test_insert_tags_whitespace() {
   info("Untrimmed and blank tags");
   let taggedBlanks = await PlacesSyncUtils.bookmarks.insert({
     kind: "bookmark",
     url: "https://example.org",
     recordId: makeGuid(),
@@ -1413,18 +1400,17 @@ add_task(async function test_insert_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");
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async function test_insert_keyword() {
   info("Insert item with new keyword");
   {
     await PlacesSyncUtils.bookmarks.insert({
       kind: "bookmark",
       parentRecordId: "menu",
@@ -1446,18 +1432,17 @@ add_task(async function test_insert_keyw
       keyword: "moz",
       recordId: makeGuid(),
     });
     let entry = await PlacesUtils.keywords.fetch("moz");
     equal(entry.url.href, "https://mozilla.org/",
       "Should reassign keyword to new item");
   }
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async function test_insert_annos() {
   info("Bookmark with description");
   let descBmk = await PlacesSyncUtils.bookmarks.insert({
     kind: "bookmark",
     url: "https://example.com",
     recordId: makeGuid(),
@@ -1513,18 +1498,17 @@ add_task(async function test_insert_anno
   {
     ok(!noSidebarBmk.loadInSidebar,
       "Should not return sidebar anno for new bookmark");
     let id = await recordIdToId(noSidebarBmk.recordId);
     ok(!PlacesUtils.annotations.itemHasAnnotation(id, LOAD_IN_SIDEBAR_ANNO),
       "Should not set sidebar anno for new bookmark");
   }
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async function test_insert_tag_query() {
   info("Use the public tagging API to ensure we added the tag correctly");
   await PlacesUtils.bookmarks.insert({
     parentGuid: PlacesUtils.bookmarks.menuGuid,
     type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
     url: "https://mozilla.org",
@@ -1574,18 +1558,17 @@ add_task(async function test_insert_tag_
 
 
 
   info("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");
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async function test_insert_orphans() {
   await ignoreChangedRoots();
 
   let grandParentGuid = makeGuid();
   let parentGuid = makeGuid();
   let childGuid = makeGuid();
@@ -1631,18 +1614,17 @@ add_task(async function test_insert_orph
     ok(!PlacesUtils.annotations.itemHasAnnotation(childId, SYNC_PARENT_ANNO),
       "Orphan anno should be removed after reparenting");
 
     let child = await PlacesUtils.bookmarks.fetch({ guid: childGuid });
     equal(child.parentGuid, parentGuid,
       "Should reparent child after inserting missing parent");
   }
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async function test_move_orphans() {
   let nonexistentRecordId = makeGuid();
   let fxBmk = await PlacesSyncUtils.bookmarks.insert({
     kind: "bookmark",
     recordId: makeGuid(),
     parentRecordId: nonexistentRecordId,
@@ -1671,18 +1653,17 @@ add_task(async function test_move_orphan
       index: PlacesUtils.bookmarks.DEFAULT_INDEX,
     });
     let orphanGuids = await PlacesSyncUtils.bookmarks.fetchGuidsWithAnno(
       SYNC_PARENT_ANNO, nonexistentRecordId);
     deepEqual(orphanGuids, [tbBmk.recordId],
       "Should remove orphan annos from updated bookmark");
   }
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async function test_reorder_orphans() {
   let nonexistentRecordId = makeGuid();
   let fxBmk = await PlacesSyncUtils.bookmarks.insert({
     kind: "bookmark",
     recordId: makeGuid(),
     parentRecordId: nonexistentRecordId,
@@ -1717,18 +1698,17 @@ add_task(async function test_reorder_orp
     await PlacesUtils.bookmarks.reorder(PlacesUtils.bookmarks.unfiledGuid,
       [tbBmk.recordId, fxBmk.recordId]);
     let orphanGuids = await PlacesSyncUtils.bookmarks.fetchGuidsWithAnno(
       SYNC_PARENT_ANNO, nonexistentRecordId);
     deepEqual(orphanGuids, [mozBmk.recordId],
       "Should remove orphan annos from explicitly reordered bookmarks");
   }
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async function test_set_orphan_indices() {
   let nonexistentRecordId = makeGuid();
   let fxBmk = await PlacesSyncUtils.bookmarks.insert({
     kind: "bookmark",
     recordId: makeGuid(),
     parentRecordId: nonexistentRecordId,
@@ -1744,18 +1724,17 @@ add_task(async function test_set_orphan_
   info("Verify synced orphan annos match");
   {
     let orphanGuids = await PlacesSyncUtils.bookmarks.fetchGuidsWithAnno(
       SYNC_PARENT_ANNO, nonexistentRecordId);
     deepEqual(orphanGuids.sort(), [fxBmk.recordId, tbBmk.recordId].sort(),
       "Orphaned bookmarks should match before changing indices");
   }
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async function test_unsynced_orphans() {
   let nonexistentRecordId = makeGuid();
   let newBmk = await PlacesSyncUtils.bookmarks.insert({
     kind: "bookmark",
     recordId: makeGuid(),
     parentRecordId: nonexistentRecordId,
@@ -1794,18 +1773,17 @@ add_task(async function test_unsynced_or
     await PlacesUtils.bookmarks.reorder(PlacesUtils.bookmarks.unfiledGuid,
       [newBmk.recordId]);
     let orphanGuids = await PlacesSyncUtils.bookmarks.fetchGuidsWithAnno(
       SYNC_PARENT_ANNO, nonexistentRecordId);
     deepEqual(orphanGuids, [],
       "Should remove orphan annos from reordered unsynced bookmarks");
   }
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async function test_fetch() {
   let folder = await PlacesSyncUtils.bookmarks.insert({
     recordId: makeGuid(),
     parentRecordId: "menu",
     kind: "folder",
     description: "Folder description",
@@ -1912,18 +1890,17 @@ add_task(async function test_fetch() {
   {
     let item = await PlacesSyncUtils.bookmarks.fetch(smartBmk.recordId);
     deepEqual(Object.keys(item).sort(), ["recordId", "kind", "parentRecordId",
       "url", "title", "query", "parentTitle", "dateAdded"].sort(),
       "Should include smart bookmark-specific properties");
     equal(item.query, "BookmarksToolbar", "Should return query name for smart bookmarks");
   }
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async function test_fetch_livemark() {
   let { site, stopServer } = makeLivemarkServer();
 
   try {
     info("Create livemark");
     let livemark = await PlacesUtils.livemarks.addLivemark({
@@ -1943,35 +1920,33 @@ add_task(async function test_fetch_livem
     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");
     strictEqual(item.title, "", "Should include livemark title even if empty");
   } finally {
     await stopServer();
   }
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async function test_pullChanges_new_parent() {
   await ignoreChangedRoots();
 
   let { syncedGuids, unsyncedFolder } = await moveSyncedBookmarksToUnsyncedParent();
 
   info("Unsynced parent and synced items should be tracked");
   let changes = await 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"
   );
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async function test_pullChanges_deleted_folder() {
   await ignoreChangedRoots();
 
   let { syncedGuids, unsyncedFolder } = await moveSyncedBookmarksToUnsyncedParent();
 
   info("Remove unsynced new folder");
@@ -1984,22 +1959,21 @@ add_task(async function test_pullChanges
       "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}`);
+    equal(changes[guid].status, PlacesUtils.bookmarks.SYNC_STATUS.NEW,
+      `Sync status should be new for deleted item ${guid}`);
   }
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async function test_pullChanges_import_html() {
   await ignoreChangedRoots();
 
   info("Add unsynced bookmark");
   let unsyncedBmk = await PlacesUtils.bookmarks.insert({
     type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
@@ -2054,18 +2028,17 @@ add_task(async function test_pullChanges
   info("Mark new HTML imports as syncing");
   await PlacesSyncUtils.bookmarks.markChangesAsSyncing(newChanges);
   let normalFields = await PlacesTestUtils.fetchBookmarkSyncFields(
     unsyncedBmk.guid, mozBmk.guid, fxBmk.guid, toolbarSubfolder.guid);
   ok(normalFields.every(field =>
     field.syncStatus == PlacesUtils.bookmarks.SYNC_STATUS.NORMAL
   ), "Marking new HTML imports as syncing should update their statuses");
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async function test_pullChanges_import_json() {
   await ignoreChangedRoots();
 
   info("Add synced folder");
   let syncedFolder = await PlacesUtils.bookmarks.insert({
     type: PlacesUtils.bookmarks.TYPE_FOLDER,
@@ -2107,18 +2080,17 @@ add_task(async function test_pullChanges
   info("Mark new JSON imports as syncing");
   await PlacesSyncUtils.bookmarks.markChangesAsSyncing(newChanges);
   let normalFields = await PlacesTestUtils.fetchBookmarkSyncFields(
     syncedFolder.guid, "NnvGl3CRA4hC", "APzP8MupzA8l");
   ok(normalFields.every(field =>
     field.syncStatus == PlacesUtils.bookmarks.SYNC_STATUS.NORMAL
   ), "Marking new JSON imports as syncing should update their statuses");
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async function test_pullChanges_restore_json_tracked() {
   await ignoreChangedRoots();
 
   let unsyncedBmk = await PlacesUtils.bookmarks.insert({
     type: PlacesUtils.bookmarks.TYPE_BOOKMARK,
     parentGuid: PlacesUtils.bookmarks.menuGuid,
@@ -2181,20 +2153,23 @@ add_task(async function test_pullChanges
 
     await PlacesSyncUtils.bookmarks.markChangesAsSyncing(changes);
     let normalFields = await PlacesTestUtils.fetchBookmarkSyncFields(
       PlacesUtils.bookmarks.menuGuid, PlacesUtils.bookmarks.toolbarGuid,
       PlacesUtils.bookmarks.unfiledGuid, "NnvGl3CRA4hC", "APzP8MupzA8l");
     ok(normalFields.every(field =>
       field.syncStatus == PlacesUtils.bookmarks.SYNC_STATUS.NORMAL
     ), "Roots and NEW items restored from JSON backup should be marked as NORMAL");
+
+    strictEqual(changes[syncedFolder.guid].tombstone, true,
+      `Should include tombstone for overwritten synced bookmark ${
+      syncedFolder.guid}`);
   }
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async function test_pullChanges_tombstones() {
   await ignoreChangedRoots();
 
   info("Insert new bookmarks");
   await PlacesUtils.bookmarks.insertTree({
     guid: PlacesUtils.bookmarks.menuGuid,
@@ -2228,18 +2203,17 @@ add_task(async function test_pullChanges
     "Should not report B as deleted");
 
   await setChangesSynced(changes);
 
   let newChanges = await PlacesSyncUtils.bookmarks.pullChanges();
   deepEqual(newChanges, {},
     "Should not return changes after marking undeleted items as synced");
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async function test_pushChanges() {
   await ignoreChangedRoots();
 
   info("Populate test bookmarks");
   let guids = await populateTree(PlacesUtils.bookmarks.menuGuid, {
     kind: "bookmark",
@@ -2343,18 +2317,19 @@ add_task(async function test_pushChanges
       guids.newBmk, guids.unknownBmk);
     ok(fields.every(field =>
       field.syncStatus == PlacesUtils.bookmarks.SYNC_STATUS.NORMAL
     ), "Should update sync statuses for synced bookmarks");
   }
 
   {
     let tombstones = await PlacesTestUtils.fetchSyncTombstones();
-    ok(!tombstones.some(({ guid }) => guid == guids.deletedBmk),
-      "Should remove tombstone after syncing");
+    let tombstone = tombstones.find(({ guid }) => guid == guids.deletedBmk);
+    equal(tombstone.syncStatus, PlacesUtils.bookmarks.SYNC_STATUS.NORMAL,
+      "Should mark tombstone as synced");
 
     let syncFields = await 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,
@@ -2371,18 +2346,17 @@ add_task(async function test_pushChanges
       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");
     }
   }
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async function test_changes_between_pull_and_push() {
   await ignoreChangedRoots();
 
   info("Populate test bookmarks");
   let guids = await populateTree(PlacesUtils.bookmarks.menuGuid, {
     kind: "bookmark",
@@ -2473,18 +2447,17 @@ add_task(async function test_touch() {
     deepEqual(Object.keys(changes).sort(), [livemark.recordId, "unfiled"].sort(),
       "Should return change records for revived livemark and parent");
     equal(changes[livemark.recordId].counter, 1,
       "Change counter for revived livemark should be 1");
   } finally {
     await stopServer();
   }
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async function test_separator() {
   await ignoreChangedRoots();
 
   await PlacesSyncUtils.bookmarks.insert({
     kind: "bookmark",
     parentRecordId: "menu",
@@ -2540,18 +2513,17 @@ add_task(async function test_separator()
   await setChangesSynced(changes);
 
   info("Move a separator around directly using update");
   await PlacesUtils.bookmarks.update({ guid: separatorGuid, index: 2 });
   changes = await PlacesSyncUtils.bookmarks.pullChanges();
   deepEqual(Object.keys(changes).sort(),
     [separator.recordId, "menu"].sort());
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async function test_remove() {
   await ignoreChangedRoots();
 
   info("Insert subtree for removal");
   let parentFolder = await PlacesSyncUtils.bookmarks.insert({
     kind: "folder",
@@ -2604,18 +2576,17 @@ add_task(async function test_remove() {
    * to determine the order. This is already enough of an edge case that
    * occasionally reuploading the closest living ancestor is the simplest
    * solution.
    */
   let changes = await PlacesSyncUtils.bookmarks.pullChanges();
   deepEqual(Object.keys(changes), ["menu"],
     "Should track closest living ancestor of removed subtree");
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async function test_remove_partial() {
   await ignoreChangedRoots();
 
   info("Insert subtree for partial removal");
   let parentFolder = await PlacesSyncUtils.bookmarks.insert({
     kind: "folder",
@@ -2721,18 +2692,17 @@ add_task(async function test_remove_part
     // `grandChildFolder` *before* `childFolder`. After this step,
     // `grandChildFolder` is deleted and `childFolder`'s children are
     // `[grandChildSiblingBmk, greatGrandChildPrevSiblingBmk,
     // greatGrandChildNextSiblingBmk]`.
     greatGrandChildPrevSiblingBmk.recordId,
     greatGrandChildNextSiblingBmk.recordId,
   ], "Should move descendants to closest living ancestor");
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async function test_migrateOldTrackerEntries() {
   let timerPrecision = Preferences.get("privacy.reduceTimerPrecision");
   Preferences.set("privacy.reduceTimerPrecision", false);
 
   registerCleanupFunction(function() {
     Preferences.set("privacy.reduceTimerPrecision", timerPrecision);
@@ -2792,20 +2762,20 @@ add_task(async function test_migrateOldT
     equal(field.syncStatus, PlacesUtils.bookmarks.SYNC_STATUS.NORMAL,
       `Should set sync status for ${field.guid} to NORMAL`);
   }
 
   let tombstones = await PlacesTestUtils.fetchSyncTombstones();
   deepEqual(tombstones, [{
     guid: tombstoneRecordId,
     dateRemoved: new Date(1479162463976),
+    syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NEW,
   }], "Should write tombstone for nonexistent migrated item");
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async function test_ensureMobileQuery() {
   info("Ensure we correctly set the showMobileBookmarks preference");
   const mobilePref = "browser.bookmarks.showMobileBookmarks";
   Services.prefs.clearUserPref(mobilePref);
 
   await PlacesUtils.bookmarks.insert({
@@ -2830,18 +2800,17 @@ add_task(async function test_ensureMobil
   await PlacesUtils.bookmarks.remove("bookmarkAAAA");
   await PlacesUtils.bookmarks.remove("bookmarkBBBB");
 
   await PlacesSyncUtils.bookmarks.ensureMobileQuery();
 
   Assert.ok(!Services.prefs.getBoolPref(mobilePref),
             "Pref should be false where there are no bookmarks in the folder.");
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async function test_remove_stale_tombstones() {
   info("Insert and delete synced bookmark");
   {
     await PlacesUtils.bookmarks.insert({
       guid: "bookmarkAAAA",
       parentGuid: PlacesUtils.bookmarks.toolbarGuid,
@@ -2905,18 +2874,17 @@ add_task(async function test_remove_stal
         title: "C",
       }],
     });
     let tombstones = await PlacesTestUtils.fetchSyncTombstones();
     deepEqual(tombstones.map(({ guid }) => guid).sort(), [],
       "Should remove tombstones after reinserting tree");
   }
 
-  await PlacesUtils.bookmarks.eraseEverything();
-  await PlacesSyncUtils.bookmarks.reset();
+  await PlacesSyncUtils.bookmarks.wipe();
 });
 
 add_task(async function test_bookmarks_resetSyncId() {
   let syncId = await PlacesSyncUtils.bookmarks.getSyncId();
   strictEqual(syncId, "", "Should start with empty bookmarks sync ID");
 
   // Add a tree with a NORMAL bookmark (A), tombstone (B), NEW bookmark (C),
   // and UNKNOWN bookmark (D).