Bug 1258127 - Bookmarks and annotations service updates to support tracking Sync changes. draft
authorKit Cambridge <kcambridge@mozilla.com>
Fri, 08 Jul 2016 16:35:57 -0700
changeset 385682 d54b995201aaba7fe9f3695129c0c0f5a003b5a8
parent 385681 0326dd303822903f70fa18dbbdf142a4e106b55c
child 385683 2e76a78e6c7d49e90f65bb04b9741b545424a26f
push id22578
push userkcambridge@mozilla.com
push dateSat, 09 Jul 2016 00:28:28 +0000
bugs1258127
milestone50.0a1
Bug 1258127 - Bookmarks and annotations service updates to support tracking Sync changes. MozReview-Commit-ID: JsCRwnmgw09
toolkit/components/places/Bookmarks.jsm
toolkit/components/places/PlacesUtils.jsm
toolkit/components/places/nsAnnotationService.cpp
toolkit/components/places/nsINavBookmarksService.idl
toolkit/components/places/nsINavHistoryService.idl
toolkit/components/places/nsNavBookmarks.cpp
toolkit/components/places/nsNavBookmarks.h
toolkit/components/places/tests/unit/test_sync_fields.js
toolkit/components/places/tests/unit/xpcshell.ini
--- a/toolkit/components/places/Bookmarks.jsm
+++ b/toolkit/components/places/Bookmarks.jsm
@@ -92,16 +92,24 @@ var Bookmarks = Object.freeze({
    * Item's type constants.
    * These should stay consistent with nsINavBookmarksService.idl
    */
   TYPE_BOOKMARK: 1,
   TYPE_FOLDER: 2,
   TYPE_SEPARATOR: 3,
 
   /**
+   * Sync status constants.
+   * These should stay consistent with nsINavBookmarksService.idl
+   */
+  SYNC_STATUS_UNKNOWN: 0,
+  SYNC_STATUS_NEW: 1,
+  SYNC_STATUS_NORMAL: 2,
+
+  /**
    * Default index used to append a bookmark-item at the end of a folder.
    * This should stay consistent with nsINavBookmarksService.idl
    */
   DEFAULT_INDEX: -1,
 
   /**
    * Special GUIDs associated with bookmark roots.
    * It's guaranteed that the roots will always have these guids.
@@ -448,18 +456,21 @@ var Bookmarks = Object.freeze({
    */
   eraseEverything: function() {
     return PlacesUtils.withConnectionWrapper("Bookmarks.jsm: eraseEverything",
       db => db.executeTransaction(function* () {
         const folderGuids = [this.toolbarGuid, this.menuGuid, this.unfiledGuid];
         yield removeFoldersContents(db, folderGuids);
         const time = PlacesUtils.toPRTime(new Date());
         for (let folderGuid of folderGuids) {
+          // This method isn't called by `PlacesSyncUtils`, so we can increment
+          // the change counter unconditionally.
           yield db.executeCached(
-            `UPDATE moz_bookmarks SET lastModified = :time
+            `UPDATE moz_bookmarks
+             SET lastModified = :time, syncChangeCounter = syncChangeCounter + 1
              WHERE id IN (SELECT id FROM moz_bookmarks WHERE guid = :folderGuid )
             `, { folderGuid, time });
         }
       }.bind(this))
     );
   },
 
   /**
@@ -790,58 +801,97 @@ function updateBookmark(info, item, newP
 
     let tuples = new Map();
     if (info.hasOwnProperty("lastModified"))
       tuples.set("lastModified", { value: PlacesUtils.toPRTime(info.lastModified) });
     if (info.hasOwnProperty("title"))
       tuples.set("title", { value: info.title });
 
     yield db.executeTransaction(function* () {
+      let isTagging = item._grandParentId == PlacesUtils.tagsFolderId;
+      let isTagOrTagFolder = isTagging ||
+                             item._parentId == PlacesUtils.tagsFolderId;
+      let syncChangeDelta = getSyncChangeDelta(info);
+
       if (info.hasOwnProperty("url")) {
         // Ensure a page exists in moz_places for this URL.
         yield maybeInsertPlace(db, info.url);
         // Update tuples for the update query.
         tuples.set("url", { value: info.url.href
                           , fragment: "fk = (SELECT id FROM moz_places WHERE url_hash = hash(:url) AND url = :url)" });
       }
 
       if (newParent) {
         // For simplicity, update the index regardless.
         let newIndex = info.hasOwnProperty("index") ? info.index : item.index;
         tuples.set("position", { value: newIndex });
 
+        let ancestorsSyncChangeDelta = isTagOrTagFolder ? 0 : syncChangeDelta;
+
         if (newParent.guid == item.parentGuid) {
           // Moving inside the original container.
           // When moving "up", add 1 to each index in the interval.
           // Otherwise when moving down, we subtract 1.
           let sign = newIndex < item.index ? +1 : -1;
           yield db.executeCached(
             `UPDATE moz_bookmarks SET position = position + :sign
              WHERE parent = :newParentId
                AND position BETWEEN :lowIndex AND :highIndex
             `, { sign: sign, newParentId: newParent._id,
                  lowIndex: Math.min(item.index, newIndex),
                  highIndex: Math.max(item.index, newIndex) });
+          // If we're repositioning, only the parent gets a sync change.
+          if (!isTagOrTagFolder && syncChangeDelta > 0) {
+            yield db.executeCached(
+              `UPDATE moz_bookmarks SET syncChangeCounter = syncChangeCounter + :syncChangeDelta
+               WHERE id = :newParentId
+              `, { newParentId: newParent._id, syncChangeDelta });
+          }
         } else {
           // Moving across different containers.
           tuples.set("parent", { value: newParent._id} );
           yield db.executeCached(
             `UPDATE moz_bookmarks SET position = position + :sign
              WHERE parent = :oldParentId
                AND position >= :oldIndex
             `, { sign: -1, oldParentId: item._parentId, oldIndex: item.index });
           yield db.executeCached(
             `UPDATE moz_bookmarks SET position = position + :sign
              WHERE parent = :newParentId
                AND position >= :newIndex
             `, { sign: +1, newParentId: newParent._id, newIndex: newIndex });
+          // If we're reparenting, both parents and the child get sync changes.
+          // We only handle the parents here; the `UPDATE` statement below
+          // handles the `syncChangeDelta` tuple entry.
+          if (!isTagOrTagFolder && syncChangeDelta > 0) {
+            tuples.set("syncChangeDelta", { value: syncChangeDelta
+                                          , fragment: "syncChangeCounter = syncChangeCounter + :syncChangeDelta" });
+            yield db.executeCached(
+              `UPDATE moz_bookmarks SET syncChangeCounter = syncChangeCounter + :syncChangeDelta
+               WHERE guid IN ( :newParentGuid, :oldParentGuid )
+              `, { newParentGuid: newParent.guid, oldParentGuid: item.parentGuid,
+                   syncChangeDelta });
+          }
 
-          yield setAncestorsLastModified(db, item.parentGuid, info.lastModified);
+          yield setAncestorsLastModified(db, item.parentGuid, info.lastModified,
+                                         ancestorsSyncChangeDelta);
         }
-        yield setAncestorsLastModified(db, newParent.guid, info.lastModified);
+        yield setAncestorsLastModified(db, newParent.guid, info.lastModified,
+                                       ancestorsSyncChangeDelta);
+      } else if (syncChangeDelta > 0) {
+        if (isTagging) {
+          // If we're updating a tag, bump the sync change counter for all
+          // tagged URLs instead of the tag item.
+          let url = info.hasOwnProperty("url") ? info.url : item.url;
+          yield addTagSyncChange(db, url, syncChangeDelta);
+        } else if (!isTagOrTagFolder) {
+          // Otherwise, bump the counter for the item.
+          tuples.set("syncChangeDelta", { value: syncChangeDelta
+                                        , fragment: "syncChangeCounter = syncChangeCounter + :syncChangeDelta" });
+        }
       }
 
       yield db.executeCached(
         `UPDATE moz_bookmarks
          SET ${Array.from(tuples.keys()).map(v => tuples.get(v).fragment || `${v} = :${v}`).join(", ")}
          WHERE guid = :guid
         `, Object.assign({ guid: info.guid },
                          [...tuples.entries()].reduce((p, c) => { p[c[0]] = c[1].value; return p; }, {})));
@@ -873,46 +923,64 @@ function insertBookmark(item, parent) {
   return PlacesUtils.withConnectionWrapper("Bookmarks.jsm: insertBookmark",
     Task.async(function*(db) {
 
     // If a guid was not provided, generate one, so we won't need to fetch the
     // bookmark just after having created it.
     if (!item.hasOwnProperty("guid"))
       item.guid = (yield db.executeCached("SELECT GENERATE_GUID() AS guid"))[0].getResultByName("guid");
 
+    let isTagging = parent._parentId == PlacesUtils.tagsFolderId;
+
     yield db.executeTransaction(function* transaction() {
       if (item.type == Bookmarks.TYPE_BOOKMARK) {
         // Ensure a page exists in moz_places for this URL.
         // The IGNORE conflict can trigger on `guid`.
         yield maybeInsertPlace(db, item.url);
       }
 
       // Adjust indices.
       yield db.executeCached(
         `UPDATE moz_bookmarks SET position = position + 1
          WHERE parent = :parent
          AND position >= :index
         `, { parent: parent._id, index: item.index });
 
+      // If we're inserting a tag with a URL, bump the change counter of the
+      // items with that URL instead of the tag item or its ancestors.
+      let isTagOrTagFolder = isTagging ||
+                             parent._id == PlacesUtils.tagsFolderId;
+      let syncChangeDelta = getSyncChangeDelta(item);
+      let itemSyncChangeCounter = isTagOrTagFolder ? 0 : syncChangeDelta;
+
       // Insert the bookmark into the database.
       yield db.executeCached(
         `INSERT INTO moz_bookmarks (fk, type, parent, position, title,
-                                    dateAdded, lastModified, guid)
+                                    dateAdded, lastModified, guid,
+                                    syncChangeCounter, syncStatus)
          VALUES ((SELECT id FROM moz_places WHERE url_hash = hash(:url) AND url = :url), :type, :parent,
-                 :index, :title, :date_added, :last_modified, :guid)
+                 :index, :title, :date_added, :last_modified, :guid, :syncChangeCounter,
+                 :syncStatus)
         `, { url: item.hasOwnProperty("url") ? item.url.href : "nonexistent",
              type: item.type, parent: parent._id, index: item.index,
              title: item.title, date_added: PlacesUtils.toPRTime(item.dateAdded),
-             last_modified: PlacesUtils.toPRTime(item.lastModified), guid: item.guid });
+             last_modified: PlacesUtils.toPRTime(item.lastModified), guid: item.guid,
+             // Don't increment the change counter or track insertions by Sync.
+             syncChangeCounter: itemSyncChangeCounter,
+             syncStatus: getSyncStatus(item) });
 
-      yield setAncestorsLastModified(db, item.parentGuid, item.dateAdded);
+      if (isTagging) {
+        yield addTagSyncChange(db, item.url, syncChangeDelta);
+      }
+
+      yield setAncestorsLastModified(db, item.parentGuid, item.dateAdded,
+                                     itemSyncChangeCounter);
     });
 
     // If not a tag recalculate frecency...
-    let isTagging = parent._parentId == PlacesUtils.tagsFolderId;
     if (item.type == Bookmarks.TYPE_BOOKMARK && !isTagging) {
       // ...though we don't wait for the calculation.
       updateFrecency(db, [item.url]).then(null, Cu.reportError);
     }
 
     // Don't return an empty title to the caller.
     if (item.hasOwnProperty("title") && item.title === null)
       delete item.title;
@@ -949,17 +1017,17 @@ function queryBookmarks(info) {
   return PlacesUtils.withConnectionWrapper("Bookmarks.jsm: queryBookmarks",
     Task.async(function*(db) {
 
     // _id, _childCount, _grandParentId and _parentId fields
     // are required to be in the result by the converting function
     // hence setting them to NULL
     let rows = yield db.executeCached(
       `SELECT b.guid, IFNULL(p.guid, "") AS parentGuid, b.position AS 'index',
-              b.dateAdded, b.lastModified, b.type, b.title,
+              b.dateAdded, b.lastModified, b.syncStatus, b.type, b.title,
               h.url AS url, b.parent, p.parent,
               NULL AS _id,
               NULL AS _childCount,
               NULL AS _grandParentId,
               NULL AS _parentId
        FROM moz_bookmarks b
        LEFT JOIN moz_bookmarks p ON p.id = b.parent
        LEFT JOIN moz_places h ON h.id = b.fk
@@ -976,17 +1044,17 @@ function queryBookmarks(info) {
 
 function fetchBookmark(info) {
   return PlacesUtils.withConnectionWrapper("Bookmarks.jsm: fetchBookmark",
     Task.async(function*(db) {
 
     let rows = yield db.executeCached(
       `SELECT b.guid, IFNULL(p.guid, "") AS parentGuid, b.position AS 'index',
               b.dateAdded, b.lastModified, b.type, b.title, h.url AS url,
-              b.id AS _id, b.parent AS _parentId,
+              b.id AS _id, b.parent AS _parentId, b.syncStatus,
               (SELECT count(*) FROM moz_bookmarks WHERE parent = b.id) AS _childCount,
               p.parent AS _grandParentId
        FROM moz_bookmarks b
        LEFT JOIN moz_bookmarks p ON p.id = b.parent
        LEFT JOIN moz_places h ON h.id = b.fk
        WHERE b.guid = :guid
       `, { guid: info.guid });
 
@@ -997,17 +1065,17 @@ function fetchBookmark(info) {
 function fetchBookmarkByPosition(info) {
   return PlacesUtils.withConnectionWrapper("Bookmarks.jsm: fetchBookmarkByPosition",
     Task.async(function*(db) {
     let index = info.index == Bookmarks.DEFAULT_INDEX ? null : info.index;
 
     let rows = yield db.executeCached(
       `SELECT b.guid, IFNULL(p.guid, "") AS parentGuid, b.position AS 'index',
               b.dateAdded, b.lastModified, b.type, b.title, h.url AS url,
-              b.id AS _id, b.parent AS _parentId,
+              b.id AS _id, b.parent AS _parentId, b.syncStatus,
               (SELECT count(*) FROM moz_bookmarks WHERE parent = b.id) AS _childCount,
               p.parent AS _grandParentId
        FROM moz_bookmarks b
        LEFT JOIN moz_bookmarks p ON p.id = b.parent
        LEFT JOIN moz_places h ON h.id = b.fk
        WHERE p.guid = :parentGuid
        AND b.position = IFNULL(:index, (SELECT count(*) - 1
                                         FROM moz_bookmarks
@@ -1021,17 +1089,17 @@ function fetchBookmarkByPosition(info) {
 function fetchBookmarksByURL(info) {
   return PlacesUtils.withConnectionWrapper("Bookmarks.jsm: fetchBookmarksByURL",
     Task.async(function*(db) {
 
     let rows = yield db.executeCached(
       `/* do not warn (bug no): not worth to add an index */
        SELECT b.guid, IFNULL(p.guid, "") AS parentGuid, b.position AS 'index',
               b.dateAdded, b.lastModified, b.type, b.title, h.url AS url,
-              b.id AS _id, b.parent AS _parentId,
+              b.id AS _id, b.parent AS _parentId, b.syncStatus,
               (SELECT count(*) FROM moz_bookmarks WHERE parent = b.id) AS _childCount,
               p.parent AS _grandParentId
        FROM moz_bookmarks b
        LEFT JOIN moz_bookmarks p ON p.id = b.parent
        LEFT JOIN moz_places h ON h.id = b.fk
        WHERE h.url_hash = hash(:url) AND h.url = :url
        AND _grandParentId <> :tags_folder
        ORDER BY b.lastModified DESC
@@ -1044,16 +1112,17 @@ function fetchBookmarksByURL(info) {
 
 function fetchRecentBookmarks(numberOfItems) {
   return PlacesUtils.withConnectionWrapper("Bookmarks.jsm: fetchRecentBookmarks",
     Task.async(function*(db) {
 
     let rows = yield db.executeCached(
       `SELECT b.guid, IFNULL(p.guid, "") AS parentGuid, b.position AS 'index',
               b.dateAdded, b.lastModified, b.type, b.title, h.url AS url,
+              b.syncStatus,
               NULL AS _id, NULL AS _parentId, NULL AS _childCount, NULL AS _grandParentId
        FROM moz_bookmarks b
        LEFT JOIN moz_bookmarks p ON p.id = b.parent
        LEFT JOIN moz_places h ON h.id = b.fk
        WHERE p.parent <> :tags_folder
        ORDER BY b.dateAdded DESC, b.ROWID DESC
        LIMIT :numberOfItems
       `, { tags_folder: PlacesUtils.tagsFolderId, numberOfItems });
@@ -1064,17 +1133,17 @@ function fetchRecentBookmarks(numberOfIt
 
 function fetchBookmarksByParent(info) {
   return PlacesUtils.withConnectionWrapper("Bookmarks.jsm: fetchBookmarksByParent",
     Task.async(function*(db) {
 
     let rows = yield db.executeCached(
       `SELECT b.guid, IFNULL(p.guid, "") AS parentGuid, b.position AS 'index',
               b.dateAdded, b.lastModified, b.type, b.title, h.url AS url,
-              b.id AS _id, b.parent AS _parentId,
+              b.id AS _id, b.parent AS _parentId, b.syncStatus,
               (SELECT count(*) FROM moz_bookmarks WHERE parent = b.id) AS _childCount,
               p.parent AS _grandParentId
        FROM moz_bookmarks b
        LEFT JOIN moz_bookmarks p ON p.id = b.parent
        LEFT JOIN moz_places h ON h.id = b.fk
        WHERE p.guid = :parentGuid
        ORDER BY b.position ASC
       `, { parentGuid: info.parentGuid });
@@ -1108,23 +1177,44 @@ function removeBookmark(info, item, opti
         // set lastModified to an unexpected value.
         yield removeAnnotationsForItem(db, item._id);
       }
 
       // Remove the bookmark from the database.
       yield db.executeCached(
         `DELETE FROM moz_bookmarks WHERE guid = :guid`, { guid: item.guid });
 
-      // Fix indices in the parent.
+      // Fix indices in the parent and mark it as having a sync change.
       yield db.executeCached(
-        `UPDATE moz_bookmarks SET position = position - 1 WHERE
-         parent = :parentId AND position > :index
+        `UPDATE moz_bookmarks
+         SET position = position - 1
+         WHERE parent = :parentId AND position > :index
         `, { parentId: item._parentId, index: item.index });
 
-      yield setAncestorsLastModified(db, item.parentGuid, new Date());
+      let isTagOrTagFolder = isUntagging ||
+                             item._parentId == PlacesUtils.tagsFolderId;
+      let syncChangeDelta = getSyncChangeDelta(info);
+      if (syncChangeDelta > 0) {
+        if (isUntagging) {
+          // If we're removing a tag, increment the change counter for all
+          // former tagged items.
+          yield addTagSyncChange(db, item.url, syncChangeDelta);
+        } else if (!isTagOrTagFolder) {
+          // Otherwise, only mark the parent as having a change.
+          yield db.executeCached(
+            `UPDATE moz_bookmarks
+             SET syncChangeCounter = syncChangeCounter + :syncChangeDelta
+             WHERE guid = :parentGuid
+            `, { parentGuid: info.parentGuid, syncChangeDelta });
+        }
+      }
+
+      let ancestorsSyncChangeDelta = isTagOrTagFolder ? 0 : syncChangeDelta;
+      yield setAncestorsLastModified(db, item.parentGuid, new Date(),
+                                     ancestorsSyncChangeDelta);
     });
 
     // If not a tag recalculate frecency...
     if (item.type == Bookmarks.TYPE_BOOKMARK && !isUntagging) {
       // ...though we don't wait for the calculation.
       updateFrecency(db, [item.url]).then(null, Cu.reportError);
     }
 
@@ -1171,16 +1261,24 @@ function reorderChildren(parent, ordered
                                   ELSE count(a.g) - 1
                   END
            FROM sorting a
            JOIN sorting b ON b.p <= a.p
            WHERE a.g = guid
              AND parent = :parentId
         )`, { parentId: parent._id});
 
+      // Flag the parent as having a change. This function isn't called by
+      // `PlacesSyncUtils`, so we can increment the change counter
+      // unconditionally.
+      yield db.execute(
+        `UPDATE moz_bookmarks SET syncChangeCounter = syncChangeCounter + 1
+         WHERE id = :parentId
+         `, {parentId: parent._id });
+
       // Update position of items that could have been inserted in the meanwhile.
       // Since this can happen rarely and it's only done for schema coherence
       // resonds, we won't notify about these changes.
       yield db.executeCached(
         `CREATE TEMP TRIGGER moz_bookmarks_reorder_trigger
            AFTER UPDATE OF position ON moz_bookmarks
            WHEN NEW.position = -1
          BEGIN
@@ -1258,17 +1356,17 @@ function removeSameValueProperties(dest,
  *
  * @param rows
  *        the array of mozIStorageRow objects.
  * @return an array of bookmark objects.
  */
 function rowsToItemsArray(rows) {
   return rows.map(row => {
     let item = {};
-    for (let prop of ["guid", "index", "type"]) {
+    for (let prop of ["guid", "index", "type", "syncStatus"]) {
       item[prop] = row.getResultByName(prop);
     }
     for (let prop of ["dateAdded", "lastModified"]) {
       item[prop] = PlacesUtils.toDate(row.getResultByName(prop));
     }
     for (let prop of ["title", "parentGuid", "url" ]) {
       let val = row.getResultByName(prop);
       if (val)
@@ -1413,30 +1511,40 @@ var removeAnnotationsForItem = Task.asyn
  *        the Sqlite.jsm connection handle.
  * @param folderGuid
  *        the GUID of the folder whose ancestors should be updated.
  * @param time
  *        a Date object to use for the update.
  *
  * @note the folder itself is also updated.
  */
-var setAncestorsLastModified = Task.async(function* (db, folderGuid, time) {
+var setAncestorsLastModified = Task.async(function* (db, folderGuid, time, syncChangeDelta) {
   yield db.executeCached(
     `WITH RECURSIVE
      ancestors(aid) AS (
        SELECT id FROM moz_bookmarks WHERE guid = :guid
        UNION ALL
        SELECT parent FROM moz_bookmarks
        JOIN ancestors ON id = aid
        WHERE type = :type
      )
-     UPDATE moz_bookmarks SET lastModified = :time
+     UPDATE moz_bookmarks
+     SET lastModified = :time
      WHERE id IN ancestors
     `, { guid: folderGuid, type: Bookmarks.TYPE_FOLDER,
          time: PlacesUtils.toPRTime(time) });
+
+  // Only increment the parent's change counter.
+  if (syncChangeDelta > 0) {
+    yield db.executeCached(
+      `UPDATE moz_bookmarks
+       SET syncChangeCounter = syncChangeCounter + :syncChangeDelta
+       WHERE guid = :guid
+      `, { guid: folderGuid, syncChangeDelta });
+  }
 });
 
 /**
  * Remove all descendants of one or more bookmark folders.
  *
  * @param db
  *        the Sqlite.jsm connection handle.
  * @param folderGuids
@@ -1453,18 +1561,18 @@ Task.async(function* (db, folderGuids) {
          JOIN moz_bookmarks p ON b.parent = p.id
          WHERE p.guid = :folderGuid
          UNION ALL
          SELECT id FROM moz_bookmarks
          JOIN descendants ON parent = did
        )
        SELECT b.id AS _id, b.parent AS _parentId, b.position AS 'index',
               b.type, url, b.guid, p.guid AS parentGuid, b.dateAdded,
-              b.lastModified, b.title, p.parent AS _grandParentId,
-              NULL AS _childCount
+              b.lastModified, b.title, b.syncStatus,
+              p.parent AS _grandParentId, NULL AS _childCount
        FROM moz_bookmarks b
        JOIN moz_bookmarks p ON p.id = b.parent
        LEFT JOIN moz_places h ON b.fk = h.id
        WHERE b.id IN descendants`, { folderGuid });
 
     itemsRemoved = itemsRemoved.concat(rowsToItemsArray(rows));
 
     yield db.executeCached(
@@ -1526,8 +1634,34 @@ function maybeInsertPlace(db, url) {
     `INSERT OR IGNORE INTO moz_places (url, url_hash, rev_host, hidden, frecency, guid)
      VALUES (:url, hash(:url), :rev_host, 0, :frecency,
              IFNULL((SELECT guid FROM moz_places WHERE url_hash = hash(:url) AND url = :url),
                     GENERATE_GUID()))
     `, { url: url.href,
          rev_host: PlacesUtils.getReversedHost(url),
          frecency: url.protocol == "place:" ? 0 : -1 });
 }
+
+function getSyncChangeDelta(item) {
+  return item.source == Ci.nsINavBookmarksService.SOURCE_SYNC ? 0 : 1;
+}
+
+function getSyncStatus(item) {
+  return item.source == Ci.nsINavBookmarksService.SOURCE_SYNC ?
+         Bookmarks.SYNC_STATUS_NORMAL :
+         Bookmarks.SYNC_STATUS_NEW;
+}
+
+var addTagSyncChange = Task.async(function* (db, url, syncChangeDelta) {
+  yield db.executeCached(
+    `UPDATE moz_bookmarks
+     SET syncChangeCounter = syncChangeCounter + :syncChangeDelta
+     WHERE guid IN (
+      SELECT b.guid
+      FROM moz_bookmarks b
+      LEFT JOIN moz_bookmarks p ON p.id = b.parent
+      LEFT JOIN moz_places h ON h.id = b.fk
+      WHERE h.url_hash = hash(:url) AND h.url = :url
+      AND p.parent <> :tagsFolderId
+    )
+    `, { syncChangeDelta, url: url.href,
+         tagsFolderId: PlacesUtils.tagsFolderId });
+});
--- a/toolkit/components/places/PlacesUtils.jsm
+++ b/toolkit/components/places/PlacesUtils.jsm
@@ -1680,17 +1680,17 @@ this.PlacesUtils = {
       let item = {};
       let copyProps = (...props) => {
         for (let prop of props) {
           let val = aRow.getResultByName(prop);
           if (val !== null)
             item[prop] = val;
         }
       };
-      copyProps("guid", "title", "index", "dateAdded", "lastModified");
+      copyProps("guid", "title", "index", "dateAdded", "lastModified", "syncChangeCounter");
       if (aIncludeParentGuid)
         copyProps("parentGuid");
 
       let itemId = aRow.getResultByName("id");
       if (aOptions.includeItemIds)
         item.id = itemId;
 
       // Cache it for promiseItemId consumers regardless.
@@ -1741,30 +1741,31 @@ this.PlacesUtils = {
           break;
       }
       return item;
     }.bind(this);
 
     const QUERY_STR =
       `WITH RECURSIVE
        descendants(fk, level, type, id, guid, parent, parentGuid, position,
-                   title, dateAdded, lastModified) AS (
+                   title, dateAdded, lastModified, syncChangeCounter) AS (
          SELECT b1.fk, 0, b1.type, b1.id, b1.guid, b1.parent,
                 (SELECT guid FROM moz_bookmarks WHERE id = b1.parent),
-                b1.position, b1.title, b1.dateAdded, b1.lastModified
+                b1.position, b1.title, b1.dateAdded, b1.lastModified,
+                b1.syncChangeCounter
          FROM moz_bookmarks b1 WHERE b1.guid=:item_guid
          UNION ALL
          SELECT b2.fk, level + 1, b2.type, b2.id, b2.guid, b2.parent,
                 descendants.guid, b2.position, b2.title, b2.dateAdded,
-                b2.lastModified
+                b2.lastModified, b2.syncChangeCounter
          FROM moz_bookmarks b2
          JOIN descendants ON b2.parent = descendants.id AND b2.id <> :tags_folder)
        SELECT d.level, d.id, d.guid, d.parent, d.parentGuid, d.type,
               d.position AS [index], d.title, d.dateAdded, d.lastModified,
-              h.url, f.url AS iconuri,
+              d.syncChangeCounter, h.url, f.url AS iconuri,
               (SELECT GROUP_CONCAT(t.title, ',')
                FROM moz_bookmarks b2
                JOIN moz_bookmarks t ON t.id = +b2.parent AND t.parent = :tags_folder
                WHERE b2.fk = h.id
               ) AS tags,
               EXISTS (SELECT 1 FROM moz_items_annos
                       WHERE item_id = d.id LIMIT 1) AS has_annos,
               (SELECT a.content FROM moz_annos a
@@ -2117,17 +2118,17 @@ var Keywords = {
     if (!("keyword" in keywordEntry) || !keywordEntry.keyword ||
         typeof(keywordEntry.keyword) != "string")
       throw new Error("Invalid keyword");
     if (("postData" in keywordEntry) && keywordEntry.postData &&
                                         typeof(keywordEntry.postData) != "string")
       throw new Error("Invalid POST data");
     if (!("url" in keywordEntry))
       throw new Error("undefined is not a valid URL");
-    let { keyword, url } = keywordEntry;
+    let { keyword, url, source } = keywordEntry;
     keyword = keyword.trim().toLowerCase();
     let postData = keywordEntry.postData || null;
     // This also checks href for validity
     url = new URL(url);
 
     return PlacesUtils.withConnectionWrapper("Keywords.insert",  Task.async(function*(db) {
         let cache = yield gKeywordsCachePromise;
 
@@ -2162,16 +2163,19 @@ var Keywords = {
             `, { url: url.href, rev_host: PlacesUtils.getReversedHost(url),
                  frecency: url.protocol == "place:" ? 0 : -1 });
           yield db.executeCached(
             `INSERT INTO moz_keywords (keyword, place_id, post_data)
              VALUES (:keyword, (SELECT id FROM moz_places WHERE url_hash = hash(:url) AND url = :url), :post_data)
             `, { url: url.href, keyword: keyword, post_data: postData });
         }
 
+        // Mark the new bookmark as having a sync change.
+        yield addKeywordSyncChange(db, url, source);
+
         cache.set(keyword, { keyword, url, postData });
 
         // In any case, notify about the new keyword.
         yield notifyKeywordChange(url.href, keyword);
       }.bind(this))
     );
   },
 
@@ -2191,22 +2195,24 @@ var Keywords = {
         typeof keywordOrEntry.keyword != "string")
       throw new Error("Invalid keyword");
 
     let keyword = keywordOrEntry.keyword.trim().toLowerCase();
     return PlacesUtils.withConnectionWrapper("Keywords.remove",  Task.async(function*(db) {
       let cache = yield gKeywordsCachePromise;
       if (!cache.has(keyword))
         return;
-      let { url } = cache.get(keyword);
+      let { url, source } = cache.get(keyword);
       cache.delete(keyword);
 
       yield db.execute(`DELETE FROM moz_keywords WHERE keyword = :keyword`,
                        { keyword });
 
+      yield addKeywordSyncChange(db, url, source);
+
       // Notify bookmarks about the removal.
       yield notifyKeywordChange(url.href, "");
     }.bind(this))) ;
   }
 };
 
 // Set by the keywords API to distinguish notifications fired by the old API.
 // Once the old API will be gone, we can remove this and stop observing.
@@ -3673,8 +3679,19 @@ PlacesUntagURITransaction.prototype = {
     PlacesUtils.tagging.untagURI(this.item.uri, this.item.tags);
   },
 
   undoTransaction: function UTUTXN_undoTransaction()
   {
     PlacesUtils.tagging.tagURI(this.item.uri, this.item.tags);
   }
 };
+
+var addKeywordSyncChange = Task.async(function* (db, url, source) {
+  if (source != Ci.nsINavBookmarksService.SOURCE_SYNC) {
+    yield db.executeCached(
+      `UPDATE moz_bookmarks
+       SET syncChangeCounter = syncChangeCounter + 1
+       WHERE fk = (SELECT id FROM moz_places WHERE
+                   url_hash = hash(:url) AND url = :url)
+       `, { url: url.href });
+  }
+});
--- a/toolkit/components/places/nsAnnotationService.cpp
+++ b/toolkit/components/places/nsAnnotationService.cpp
@@ -1966,34 +1966,58 @@ nsAnnotationService::Observe(nsISupports
                              const char *aTopic,
                              const char16_t *aData)
 {
   NS_ASSERTION(NS_IsMainThread(), "This can only be called on the main thread");
 
   if (strcmp(aTopic, TOPIC_PLACES_SHUTDOWN) == 0) {
     // Remove all session annotations, if any.
     if (mHasSessionAnnotations) {
+      // Increment the sync change counter for tracked annotations.
+      nsCOMPtr<mozIStorageAsyncStatement> syncChangeCounterStmt =
+        mDB->GetAsyncStatement("UPDATE moz_bookmarks "
+          "SET syncChangeCounter = syncChangeCounter + 1 "
+          "WHERE id IN ("
+            "SELECT item_id from moz_items_annos WHERE "
+              "expiration = :expire_session AND "
+              "anno_attribute_id IN ("
+                "SELECT id FROM moz_anno_attributes WHERE name IN ("
+                  // These should match the annotations in `IsSyncedAnnotation`.
+                  "'bookmarkProperties/description', "
+                  "'bookmarkProperties/loadInSidebar', "
+                  "'livemark/feedURI', "
+                  "'livemark/siteURI'"
+                ")"
+              ")"
+          ")"
+      );
+      NS_ENSURE_STATE(syncChangeCounterStmt);
+      nsresult rv = syncChangeCounterStmt->BindInt32ByName(
+        NS_LITERAL_CSTRING("expire_session"), EXPIRE_SESSION);
+      NS_ENSURE_SUCCESS(rv, rv);
+
       nsCOMPtr<mozIStorageAsyncStatement> pageAnnoStmt = mDB->GetAsyncStatement(
         "DELETE FROM moz_annos WHERE expiration = :expire_session"
       );
       NS_ENSURE_STATE(pageAnnoStmt);
-      nsresult rv = pageAnnoStmt->BindInt32ByName(NS_LITERAL_CSTRING("expire_session"),
-                                                  EXPIRE_SESSION);
+      rv = pageAnnoStmt->BindInt32ByName(NS_LITERAL_CSTRING("expire_session"),
+                                         EXPIRE_SESSION);
       NS_ENSURE_SUCCESS(rv, rv);
 
       nsCOMPtr<mozIStorageAsyncStatement> itemAnnoStmt = mDB->GetAsyncStatement(
         "DELETE FROM moz_items_annos WHERE expiration = :expire_session"
       );
       NS_ENSURE_STATE(itemAnnoStmt);
       rv = itemAnnoStmt->BindInt32ByName(NS_LITERAL_CSTRING("expire_session"),
                                          EXPIRE_SESSION);
       NS_ENSURE_SUCCESS(rv, rv);
 
       mozIStorageBaseStatement *stmts[] = {
-        pageAnnoStmt.get()
+        syncChangeCounterStmt.get()
+      , pageAnnoStmt.get()
       , itemAnnoStmt.get()
       };
 
       nsCOMPtr<mozIStoragePendingStatement> ps;
       rv = mDB->MainConn()->ExecuteAsync(stmts, ArrayLength(stmts), nullptr,
                                          getter_AddRefs(ps));
       NS_ENSURE_SUCCESS(rv, rv);
     }
--- a/toolkit/components/places/nsINavBookmarksService.idl
+++ b/toolkit/components/places/nsINavBookmarksService.idl
@@ -283,16 +283,25 @@ interface nsINavBookmarksService : nsISu
 
   // Change source constants. These are used to distinguish changes made by
   // Sync from other Places consumers, though they can be extended to support
   // other callers. Sources are passed as optional parameters to methods used
   // by Sync, and forwarded to observers.
   const unsigned short SOURCE_DEFAULT = 0;
   const unsigned short SOURCE_SYNC = 1;
 
+  // Sync Status flags.
+  // "unknown" is for existing records before we've reconciled them, or
+  // after the database has been restored.
+  const unsigned short SYNC_STATUS_UNKNOWN = 0;
+  // "new" means this record has never been synced.
+  const unsigned short SYNC_STATUS_NEW = 1;
+  // "normal" means this record is syncing normally.
+  const unsigned short SYNC_STATUS_NORMAL = 2;
+
   /**
    * Inserts a child bookmark into the given folder.
    *
    *  @param aParentId
    *         The id of the parent folder
    *  @param aURI
    *         The URI to insert
    *  @param aIndex
--- a/toolkit/components/places/nsINavHistoryService.idl
+++ b/toolkit/components/places/nsINavHistoryService.idl
@@ -413,17 +413,17 @@ interface nsINavHistoryResultObserver : 
    *        a uri result node
    *
    * @note: The new tags list is accessible through aNode.tags.
    */
   void nodeTagsChanged(in nsINavHistoryResultNode aNode);
 
   /**
    * Called right after the aNode's keyword property has changed.
-   * 
+   *
    * @param aNode
    *        a uri result node
    * @param aNewKeyword
    *        the new keyword
    */
   void nodeKeywordChanged(in nsINavHistoryResultNode aNode,
                           in AUTF8String aNewKeyword);
 
--- a/toolkit/components/places/nsNavBookmarks.cpp
+++ b/toolkit/components/places/nsNavBookmarks.cpp
@@ -105,16 +105,26 @@ public:
   }
 
 private:
   RefPtr<nsNavBookmarks> mBookmarksSvc;
   Method mCallback;
   DataType mData;
 };
 
+
+bool
+IsSyncedAnno(const nsACString& aName)
+{
+  return aName.EqualsLiteral("bookmarkProperties/description") ||
+         aName.EqualsLiteral("bookmarkProperties/loadInSidebar") ||
+         aName.EqualsLiteral("livemark/feedURI") ||
+         aName.EqualsLiteral("livemark/siteURI");
+}
+
 } // namespace
 
 
 nsNavBookmarks::nsNavBookmarks()
   : mItemCount(0)
   , mRoot(0)
   , mMenuRoot(0)
   , mTagsRoot(0)
@@ -334,33 +344,50 @@ nsNavBookmarks::InsertBookmarkInDB(int64
                                    int64_t* _itemId,
                                    nsACString& _guid)
 {
   // Check for a valid itemId.
   MOZ_ASSERT(_itemId && (*_itemId == -1 || *_itemId > 0));
   // Check for a valid placeId.
   MOZ_ASSERT(aPlaceId && (aPlaceId == -1 || aPlaceId > 0));
 
+  bool isTag = aGrandParentId == mTagsRoot;
+  bool isTagOrTagFolder = isTag || aParentId == mTagsRoot;
+
   nsCOMPtr<mozIStorageStatement> stmt = mDB->GetStatement(
     "INSERT INTO moz_bookmarks "
       "(id, fk, type, parent, position, title, "
-       "dateAdded, lastModified, guid) "
+       "dateAdded, lastModified, guid, syncStatus, syncChangeCounter) "
     "VALUES (:item_id, :page_id, :item_type, :parent, :item_index, "
             ":item_title, :date_added, :last_modified, "
-            "IFNULL(:item_guid, GENERATE_GUID()))"
+            "IFNULL(:item_guid, GENERATE_GUID()), "
+            ":sync_status, :change_counter)"
   );
   NS_ENSURE_STATE(stmt);
   mozStorageStatementScoper scoper(stmt);
 
   nsresult rv;
-  if (*_itemId != -1)
+  if (*_itemId != -1) {
     rv = stmt->BindInt64ByName(NS_LITERAL_CSTRING("item_id"), *_itemId);
-  else
+    NS_ENSURE_SUCCESS(rv, rv);
+
+    // If we're inserting an item with the same ID (for example, undoing a
+    // remove folder transaction), we only track the parent, not the item.
+    rv = stmt->BindInt64ByName(NS_LITERAL_CSTRING("change_counter"), 0);
+    NS_ENSURE_SUCCESS(rv, rv);
+  } else {
     rv = stmt->BindNullByName(NS_LITERAL_CSTRING("item_id"));
-  NS_ENSURE_SUCCESS(rv, rv);
+    NS_ENSURE_SUCCESS(rv, rv);
+
+    // Increment the change counter for new bookmarks, ignoring tags and
+    // tag folders.
+    rv = stmt->BindInt64ByName(NS_LITERAL_CSTRING("change_counter"),
+                               isTagOrTagFolder ? 0 : 1);
+    NS_ENSURE_SUCCESS(rv, rv);
+  }
 
   if (aPlaceId != -1)
     rv = stmt->BindInt64ByName(NS_LITERAL_CSTRING("page_id"), aPlaceId);
   else
     rv = stmt->BindNullByName(NS_LITERAL_CSTRING("page_id"));
   NS_ENSURE_SUCCESS(rv, rv);
 
   rv = stmt->BindInt32ByName(NS_LITERAL_CSTRING("item_type"), aItemType);
@@ -395,16 +422,20 @@ nsNavBookmarks::InsertBookmarkInDB(int64
     MOZ_ASSERT(IsValidGUID(_guid));
     rv = stmt->BindUTF8StringByName(NS_LITERAL_CSTRING("item_guid"), _guid);
   }
   else {
     rv = stmt->BindNullByName(NS_LITERAL_CSTRING("item_guid"));
   }
   NS_ENSURE_SUCCESS(rv, rv);
 
+  rv = stmt->BindInt32ByName(NS_LITERAL_CSTRING("sync_status"),
+                             nsINavBookmarksService::SYNC_STATUS_NEW);
+  NS_ENSURE_SUCCESS(rv, rv);
+
   rv = stmt->Execute();
   NS_ENSURE_SUCCESS(rv, rv);
 
   if (*_itemId == -1) {
     // Get the newly inserted item id and GUID.
     nsCOMPtr<mozIStorageStatement> lastInsertIdStmt = mDB->GetStatement(
       "SELECT id, guid "
       "FROM moz_bookmarks "
@@ -420,20 +451,31 @@ nsNavBookmarks::InsertBookmarkInDB(int64
     NS_ENSURE_TRUE(hasResult, NS_ERROR_UNEXPECTED);
     rv = lastInsertIdStmt->GetInt64(0, _itemId);
     NS_ENSURE_SUCCESS(rv, rv);
     rv = lastInsertIdStmt->GetUTF8String(1, _guid);
     NS_ENSURE_SUCCESS(rv, rv);
   }
 
   if (aParentId > 0) {
+    // If we're inserting a bookmark, increment the change counter of its
+    // parent. Ignore tag folders and tags; we only track tagged bookmarks.
+    SyncChangeExclusionPolicy syncPolicy = isTagOrTagFolder ? IGNORE : TRACK;
+
     // Update last modified date of the ancestors.
     // TODO (bug 408991): Doing this for all ancestors would be slow without a
     //                    nested tree, so for now update only the parent.
-    rv = SetItemDateInternal(LAST_MODIFIED, aParentId, aDateAdded);
+    rv = SetItemDateInternal(LAST_MODIFIED, syncPolicy, aParentId, aDateAdded);
+    NS_ENSURE_SUCCESS(rv, rv);
+  }
+
+  if (isTag) {
+    // If we're tagging a bookmark, increment the change counter for all
+    // bookmarks with the URI.
+    rv = TrackSyncTagChange(*_itemId, aURI);
     NS_ENSURE_SUCCESS(rv, rv);
   }
 
   // Add a cache entry since we know everything about this bookmark.
   BookmarkData bookmark;
   bookmark.id = *_itemId;
   bookmark.guid.Assign(_guid);
   if (aTitle.IsVoid()) {
@@ -572,18 +614,19 @@ nsNavBookmarks::RemoveItem(int64_t aItem
 
   BookmarkData bookmark;
   nsresult rv = FetchItemInfo(aItemId, bookmark);
   NS_ENSURE_SUCCESS(rv, rv);
 
   mozStorageTransaction transaction(mDB->MainConn(), false);
 
   // First, if not a tag, remove item annotations.
-  if (bookmark.parentId != mTagsRoot &&
-      bookmark.grandParentId != mTagsRoot) {
+  bool isTag = bookmark.grandParentId == mTagsRoot;
+  bool isTagOrTagFolder = isTag || bookmark.parentId == mTagsRoot;
+  if (!isTagOrTagFolder) {
     nsAnnotationService* annosvc = nsAnnotationService::GetAnnotationService();
     NS_ENSURE_TRUE(annosvc, NS_ERROR_OUT_OF_MEMORY);
     rv = annosvc->RemoveItemAnnotations(bookmark.id);
     NS_ENSURE_SUCCESS(rv, rv);
   }
 
   if (bookmark.type == TYPE_FOLDER) {
     // Remove all of the folder's children.
@@ -604,21 +647,34 @@ nsNavBookmarks::RemoveItem(int64_t aItem
 
   // Fix indices in the parent.
   if (bookmark.position != DEFAULT_INDEX) {
     rv = AdjustIndices(bookmark.parentId,
                        bookmark.position + 1, INT32_MAX, -1);
     NS_ENSURE_SUCCESS(rv, rv);
   }
 
+  // If we're removing a bookmark, increment the change counter of its
+  // parent. Ignore tags and tag folders.
+  SyncChangeExclusionPolicy syncPolicy = isTagOrTagFolder ? IGNORE : TRACK;
   bookmark.lastModified = RoundedPRNow();
-  rv = SetItemDateInternal(LAST_MODIFIED, bookmark.parentId,
+  rv = SetItemDateInternal(LAST_MODIFIED, syncPolicy, bookmark.parentId,
                            bookmark.lastModified);
   NS_ENSURE_SUCCESS(rv, rv);
 
+  if (isTag) {
+    // If we're removing a tag, increment the change counter for all bookmarks
+    // with the URI.
+    nsCOMPtr<nsIURI> uri;
+    rv = NS_NewURI(getter_AddRefs(uri), bookmark.url);
+    NS_ENSURE_SUCCESS(rv, rv);
+    rv = TrackSyncTagChange(bookmark.id, uri);
+    NS_ENSURE_SUCCESS(rv, rv);
+  }
+
   rv = transaction.Commit();
   NS_ENSURE_SUCCESS(rv, rv);
 
   nsCOMPtr<nsIURI> uri;
   if (bookmark.type == TYPE_BOOKMARK) {
     // If not a tag, recalculate frecency for this entry, since it changed.
     if (bookmark.grandParentId != mTagsRoot) {
       nsNavHistory* history = nsNavHistory::GetHistoryService();
@@ -1085,17 +1141,17 @@ nsNavBookmarks::RemoveFolderChildren(int
       "DELETE FROM moz_items_annos "
       "WHERE id IN ("
         "SELECT a.id from moz_items_annos a "
         "LEFT JOIN moz_bookmarks b ON a.item_id = b.id "
         "WHERE b.id ISNULL)"));
   NS_ENSURE_SUCCESS(rv, rv);
 
   // Set the lastModified date.
-  rv = SetItemDateInternal(LAST_MODIFIED, folder.id, RoundedPRNow());
+  rv = SetItemDateInternal(LAST_MODIFIED, TRACK, folder.id, RoundedPRNow());
   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) {
     BookmarkData& child = folderChildrenArray[i];
@@ -1225,17 +1281,18 @@ nsNavBookmarks::MoveItem(int64_t aItemId
   if (aNewParent == bookmark.parentId && newIndex == bookmark.position) {
     // Nothing to do!
     return NS_OK;
   }
 
   // adjust indices to account for the move
   // do this before we update the parent/index fields
   // or we'll re-adjust the index for the item we are moving
-  if (bookmark.parentId == aNewParent) {
+  bool sameParent = bookmark.parentId == aNewParent;
+  if (sameParent) {
     // We can optimize the updates if moving within the same container.
     // We only shift the items between the old and new positions, since the
     // insertion will offset the deletion.
     if (bookmark.position > newIndex) {
       rv = AdjustIndices(bookmark.parentId, newIndex, bookmark.position - 1, 1);
     }
     else {
       rv = AdjustIndices(bookmark.parentId, bookmark.position + 1, newIndex, -1);
@@ -1250,36 +1307,54 @@ nsNavBookmarks::MoveItem(int64_t aItemId
     // Now, make room in the new parent for the insertion.
     rv = AdjustIndices(aNewParent, newIndex, INT32_MAX, 1);
     NS_ENSURE_SUCCESS(rv, rv);
   }
 
   {
     // Update parent and position.
     nsCOMPtr<mozIStorageStatement> stmt = mDB->GetStatement(
-      "UPDATE moz_bookmarks SET parent = :parent, position = :item_index "
+      "UPDATE moz_bookmarks SET "
+       "parent = :parent, position = :item_index, "
+       "syncChangeCounter = syncChangeCounter + ("
+        "CASE WHEN EXISTS("
+         "SELECT 1 FROM moz_items_annos WHERE "
+          "item_id = :item_id AND "
+          "anno_attribute_id = ("
+           "SELECT id FROM moz_anno_attributes "
+           "WHERE name = 'places/excludeFromBackup'"
+          ")"
+        ") "
+        "THEN 0 "
+        "ELSE :delta "
+        "END"
+       ")"
       "WHERE id = :item_id "
     );
     NS_ENSURE_STATE(stmt);
     mozStorageStatementScoper scoper(stmt);
 
     rv = stmt->BindInt64ByName(NS_LITERAL_CSTRING("parent"), aNewParent);
     NS_ENSURE_SUCCESS(rv, rv);
     rv = stmt->BindInt32ByName(NS_LITERAL_CSTRING("item_index"), newIndex);
     NS_ENSURE_SUCCESS(rv, rv);
     rv = stmt->BindInt64ByName(NS_LITERAL_CSTRING("item_id"), bookmark.id);
     NS_ENSURE_SUCCESS(rv, rv);
+    // The item itself only gets a change increment if it was re-parented.
+    rv = stmt->BindInt64ByName(NS_LITERAL_CSTRING("delta"), sameParent ? 0 : 1);
+    NS_ENSURE_SUCCESS(rv, rv);
     rv = stmt->Execute();
     NS_ENSURE_SUCCESS(rv, rv);
   }
 
   PRTime now = RoundedPRNow();
-  rv = SetItemDateInternal(LAST_MODIFIED, bookmark.parentId, now);
+  rv = SetItemDateInternal(LAST_MODIFIED, TRACK, bookmark.parentId, now);
   NS_ENSURE_SUCCESS(rv, rv);
-  rv = SetItemDateInternal(LAST_MODIFIED, aNewParent, now);
+  rv = SetItemDateInternal(LAST_MODIFIED, sameParent ? IGNORE : TRACK,
+                           aNewParent, now);
   NS_ENSURE_SUCCESS(rv, rv);
 
   rv = transaction.Commit();
   NS_ENSURE_SUCCESS(rv, rv);
 
   NOTIFY_OBSERVERS(mCanNotify, mCacheObservers, mObservers,
                    nsINavBookmarkObserver,
                    OnItemMoved(bookmark.id,
@@ -1360,34 +1435,70 @@ nsNavBookmarks::FetchItemInfo(int64_t aI
     _bookmark.grandParentId = -1;
   }
 
   return NS_OK;
 }
 
 nsresult
 nsNavBookmarks::SetItemDateInternal(enum BookmarkDate aDateType,
+                                    enum SyncChangeExclusionPolicy aSyncPolicy,
                                     int64_t aItemId,
                                     PRTime aValue)
 {
   aValue = RoundToMilliseconds(aValue);
 
+  nsAutoCString syncChangeSuffix;
+  switch (aSyncPolicy) {
+    // Only increments the sync change counter for |aItemId| if it's included
+    // in backups.
+    case IGNORE_IF_EXCLUDED:
+      syncChangeSuffix = NS_LITERAL_CSTRING(
+       ", syncChangeCounter = syncChangeCounter + ("
+        "CASE WHEN EXISTS("
+         "SELECT 1 FROM moz_items_annos WHERE "
+          "item_id = :item_id AND "
+          "anno_attribute_id = ("
+           "SELECT id FROM moz_anno_attributes "
+           "WHERE name = 'places/excludeFromBackup'"
+          ")"
+        ") THEN 0 ELSE 1 END"
+       ")"
+      );
+      break;
+
+    // Unconditionally increment the sync change counter for |aItemId|. This
+    // is used to update the counter for a parent that's excluded from backups.
+    case TRACK:
+      syncChangeSuffix = NS_LITERAL_CSTRING(
+        ", syncChangeCounter = syncChangeCounter + 1");
+      break;
+
+    default:
+      MOZ_FALLTHROUGH_ASSERT("Invalid sync change counter policy");
+    case IGNORE:
+      syncChangeSuffix.Truncate();
+  }
+
   nsCOMPtr<mozIStorageStatement> stmt;
   if (aDateType == DATE_ADDED) {
     // lastModified is set to the same value as dateAdded.  We do this for
     // performance reasons, since it will allow us to use an index to sort items
     // by date.
     stmt = mDB->GetStatement(
-      "UPDATE moz_bookmarks SET dateAdded = :date, lastModified = :date "
-      "WHERE id = :item_id"
+      NS_LITERAL_CSTRING("UPDATE moz_bookmarks SET "
+       "dateAdded = :date, lastModified = :date") + syncChangeSuffix +
+      NS_LITERAL_CSTRING(" WHERE id = :item_id")
     );
   }
   else {
     stmt = mDB->GetStatement(
-      "UPDATE moz_bookmarks SET lastModified = :date WHERE id = :item_id"
+      NS_LITERAL_CSTRING("UPDATE moz_bookmarks SET "
+       "lastModified = :date") + syncChangeSuffix +
+      NS_LITERAL_CSTRING(" WHERE id = :item_id")
     );
   }
   NS_ENSURE_STATE(stmt);
   mozStorageStatementScoper scoper(stmt);
 
   nsresult rv = stmt->BindInt64ByName(NS_LITERAL_CSTRING("date"), aValue);
   NS_ENSURE_SUCCESS(rv, rv);
   rv = stmt->BindInt64ByName(NS_LITERAL_CSTRING("item_id"), aItemId);
@@ -1410,17 +1521,18 @@ nsNavBookmarks::SetItemDateAdded(int64_t
 
   BookmarkData bookmark;
   nsresult rv = FetchItemInfo(aItemId, bookmark);
   NS_ENSURE_SUCCESS(rv, rv);
 
   // Round here so that we notify with the right value.
   bookmark.dateAdded = RoundToMilliseconds(aDateAdded);
 
-  rv = SetItemDateInternal(DATE_ADDED, bookmark.id, bookmark.dateAdded);
+  rv = SetItemDateInternal(DATE_ADDED, IGNORE_IF_EXCLUDED, bookmark.id,
+                           bookmark.dateAdded);
   NS_ENSURE_SUCCESS(rv, rv);
 
   // Note: mDBSetItemDateAdded also sets lastModified to aDateAdded.
   NOTIFY_OBSERVERS(mCanNotify, mCacheObservers, mObservers,
                    nsINavBookmarkObserver,
                    OnItemChanged(bookmark.id,
                                  NS_LITERAL_CSTRING("dateAdded"),
                                  false,
@@ -1458,17 +1570,18 @@ nsNavBookmarks::SetItemLastModified(int6
 
   BookmarkData bookmark;
   nsresult rv = FetchItemInfo(aItemId, bookmark);
   NS_ENSURE_SUCCESS(rv, rv);
 
   // Round here so that we notify with the right value.
   bookmark.lastModified = RoundToMilliseconds(aLastModified);
 
-  rv = SetItemDateInternal(LAST_MODIFIED, bookmark.id, bookmark.lastModified);
+  rv = SetItemDateInternal(LAST_MODIFIED, IGNORE_IF_EXCLUDED, bookmark.id,
+                           bookmark.lastModified);
   NS_ENSURE_SUCCESS(rv, rv);
 
   // Note: mDBSetItemDateAdded also sets lastModified to aDateAdded.
   NOTIFY_OBSERVERS(mCanNotify, mCacheObservers, mObservers,
                    nsINavBookmarkObserver,
                    OnItemChanged(bookmark.id,
                                  NS_LITERAL_CSTRING("lastModified"),
                                  false,
@@ -1493,30 +1606,65 @@ nsNavBookmarks::GetItemLastModified(int6
   BookmarkData bookmark;
   nsresult rv = FetchItemInfo(aItemId, bookmark);
   NS_ENSURE_SUCCESS(rv, rv);
 
   *_lastModified = bookmark.lastModified;
   return NS_OK;
 }
 
+nsresult
+nsNavBookmarks::TrackSyncTagChange(int64_t aTagId, nsIURI* aURI)
+{
+  NS_ENSURE_ARG(aURI);
+
+  nsCOMPtr<mozIStorageStatement> statement = mDB->GetStatement(
+   "UPDATE moz_bookmarks SET "
+    "syncChangeCounter = syncChangeCounter + 1 "
+   "WHERE fk = (SELECT id FROM moz_places WHERE url = :page_url) AND "
+   "id != :tag_id"
+  );
+  NS_ENSURE_STATE(statement);
+  mozStorageStatementScoper scoper(statement);
+
+  nsresult rv = URIBinder::Bind(statement, NS_LITERAL_CSTRING("page_url"), aURI);
+  NS_ENSURE_SUCCESS(rv, rv);
+  rv = statement->BindInt64ByName(NS_LITERAL_CSTRING("tag_id"), aTagId);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  return statement->Execute();
+}
 
 NS_IMETHODIMP
 nsNavBookmarks::SetItemTitle(int64_t aItemId, const nsACString& aTitle,
                              uint16_t aSource)
 {
   NS_ENSURE_ARG_MIN(aItemId, 1);
 
   BookmarkData bookmark;
   nsresult rv = FetchItemInfo(aItemId, bookmark);
   NS_ENSURE_SUCCESS(rv, rv);
 
   nsCOMPtr<mozIStorageStatement> statement = mDB->GetStatement(
-    "UPDATE moz_bookmarks SET title = :item_title, lastModified = :date "
-    "WHERE id = :item_id "
+    "UPDATE moz_bookmarks SET "
+     "title = :item_title, lastModified = :date, "
+     "syncChangeCounter = syncChangeCounter + ("
+      "CASE WHEN EXISTS("
+       "SELECT 1 FROM moz_items_annos WHERE "
+        "item_id = :item_id AND "
+        "anno_attribute_id = ("
+         "SELECT id FROM moz_anno_attributes "
+         "WHERE name = 'places/excludeFromBackup'"
+        ")"
+      ") "
+      "THEN 0 "
+      "ELSE 1 "
+      "END"
+     ")"
+    "WHERE id = :item_id"
   );
   NS_ENSURE_STATE(statement);
   mozStorageStatementScoper scoper(statement);
 
   nsCString title;
   TruncateTitle(aTitle, title);
 
   // Support setting a null title, we support this in insertBookmark.
@@ -1986,17 +2134,31 @@ nsNavBookmarks::ChangeBookmarkURI(int64_
   int64_t newPlaceId;
   nsAutoCString newPlaceGuid;
   rv = history->GetOrCreateIdForPage(aNewURI, &newPlaceId, newPlaceGuid);
   NS_ENSURE_SUCCESS(rv, rv);
   if (!newPlaceId)
     return NS_ERROR_INVALID_ARG;
 
   nsCOMPtr<mozIStorageStatement> statement = mDB->GetStatement(
-    "UPDATE moz_bookmarks SET fk = :page_id, lastModified = :date "
+    "UPDATE moz_bookmarks SET "
+     "fk = :page_id, lastModified = :date, "
+     "syncChangeCounter = syncChangeCounter + ("
+      "CASE WHEN EXISTS("
+       "SELECT 1 FROM moz_items_annos WHERE "
+        "item_id = :item_id AND "
+        "anno_attribute_id = ("
+         "SELECT id FROM moz_anno_attributes "
+         "WHERE name = 'places/excludeFromBackup'"
+        ")"
+      ") "
+      "THEN 0 "
+      "ELSE 1 "
+      "END"
+     ")"
     "WHERE id = :item_id "
   );
   NS_ENSURE_STATE(statement);
   mozStorageStatementScoper scoper(statement);
 
   rv = statement->BindInt64ByName(NS_LITERAL_CSTRING("page_id"), newPlaceId);
   NS_ENSURE_SUCCESS(rv, rv);
   bookmark.lastModified = RoundedPRNow();
@@ -2221,28 +2383,54 @@ nsNavBookmarks::SetItemIndex(int64_t aIt
   int64_t grandParentId;
   nsAutoCString folderGuid;
   rv = FetchFolderInfo(bookmark.parentId, &folderCount, folderGuid, &grandParentId);
   NS_ENSURE_SUCCESS(rv, rv);
   NS_ENSURE_TRUE(aNewIndex < folderCount, NS_ERROR_INVALID_ARG);
   // Check the parent's guid is the expected one.
   MOZ_ASSERT(bookmark.parentGuid == folderGuid);
 
-  nsCOMPtr<mozIStorageStatement> stmt = mDB->GetStatement(
-    "UPDATE moz_bookmarks SET position = :item_index WHERE id = :item_id"
-  );
-  NS_ENSURE_STATE(stmt);
-  mozStorageStatementScoper scoper(stmt);
-
-  rv = stmt->BindInt64ByName(NS_LITERAL_CSTRING("item_id"), aItemId);
-  NS_ENSURE_SUCCESS(rv, rv);
-  rv = stmt->BindInt32ByName(NS_LITERAL_CSTRING("item_index"), aNewIndex);
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  rv = stmt->Execute();
+  mozStorageTransaction transaction(mDB->MainConn(), false);
+
+  {
+    nsCOMPtr<mozIStorageStatement> stmt = mDB->GetStatement(
+      "UPDATE moz_bookmarks SET "
+       "position = :item_index "
+      "WHERE id = :item_id"
+    );
+    NS_ENSURE_STATE(stmt);
+    mozStorageStatementScoper scoper(stmt);
+
+    rv = stmt->BindInt64ByName(NS_LITERAL_CSTRING("item_id"), aItemId);
+    NS_ENSURE_SUCCESS(rv, rv);
+    rv = stmt->BindInt32ByName(NS_LITERAL_CSTRING("item_index"), aNewIndex);
+    NS_ENSURE_SUCCESS(rv, rv);
+
+    rv = stmt->Execute();
+    NS_ENSURE_SUCCESS(rv, rv);
+  }
+
+  {
+    nsCOMPtr<mozIStorageStatement> stmt = mDB->GetStatement(
+      "UPDATE moz_bookmarks SET "
+       "syncChangeCounter = syncChangeCounter + 1 "
+      "WHERE id = :parent_id"
+    );
+    NS_ENSURE_STATE(stmt);
+    mozStorageStatementScoper scoper(stmt);
+
+    rv = stmt->BindInt64ByName(NS_LITERAL_CSTRING("parent_id"),
+                               bookmark.parentId);
+    NS_ENSURE_SUCCESS(rv, rv);
+
+    rv = stmt->Execute();
+    NS_ENSURE_SUCCESS(rv, rv);
+  }
+
+  rv = transaction.Commit();
   NS_ENSURE_SUCCESS(rv, rv);
 
   NOTIFY_OBSERVERS(mCanNotify, mCacheObservers, mObservers,
                    nsINavBookmarkObserver,
                    OnItemMoved(bookmark.id,
                                bookmark.parentId,
                                bookmark.position,
                                bookmark.parentId,
@@ -2296,16 +2484,18 @@ nsNavBookmarks::SetKeywordForBookmark(in
   }
 
   // Trying to remove a non-existent keyword is a no-op.
   if (keyword.IsEmpty() && oldKeywords.Length() == 0) {
     return NS_OK;
   }
 
   if (keyword.IsEmpty()) {
+    mozStorageTransaction removeTxn(mDB->MainConn(), false);
+
     // We are removing the existing keywords.
     for (uint32_t i = 0; i < oldKeywords.Length(); ++i) {
       nsCOMPtr<mozIStorageStatement> stmt = mDB->GetStatement(
         "DELETE FROM moz_keywords WHERE keyword = :old_keyword"
       );
       NS_ENSURE_STATE(stmt);
       mozStorageStatementScoper scoper(stmt);
       rv = stmt->BindStringByName(NS_LITERAL_CSTRING("old_keyword"),
@@ -2313,16 +2503,50 @@ nsNavBookmarks::SetKeywordForBookmark(in
       NS_ENSURE_SUCCESS(rv, rv);
       rv = stmt->Execute();
       NS_ENSURE_SUCCESS(rv, rv);
     }
 
     nsTArray<BookmarkData> bookmarks;
     rv = GetBookmarksForURI(uri, bookmarks);
     NS_ENSURE_SUCCESS(rv, rv);
+
+    if (!bookmarks.IsEmpty()) {
+      nsAutoCString changedIds;
+      changedIds.AppendInt(bookmarks[0].id);
+      for (uint32_t i = 1; i < bookmarks.Length(); ++i) {
+        changedIds.Append(',');
+        changedIds.AppendInt(bookmarks[i].id);
+      }
+      nsCOMPtr<mozIStorageStatement> stmt = mDB->GetStatement(
+        NS_LITERAL_CSTRING("WITH ids AS ("
+         "SELECT id FROM ("
+          "SELECT id FROM moz_bookmarks "
+          "EXCEPT "
+          "SELECT item_id FROM moz_items_annos WHERE "
+           "anno_attribute_id = ("
+            "SELECT id FROM moz_anno_attributes "
+            "WHERE name = 'places/excludeFromBackup'"
+           ")"
+         ") "
+         "WHERE id IN (") + changedIds + NS_LITERAL_CSTRING(")"
+        ") UPDATE moz_bookmarks SET "
+         "syncChangeCounter = syncChangeCounter + 1 "
+        "WHERE id IN ids")
+      );
+      NS_ENSURE_STATE(stmt);
+      mozStorageStatementScoper scoper(stmt);
+
+      rv = stmt->Execute();
+      NS_ENSURE_SUCCESS(rv, rv);
+    }
+
+    rv = removeTxn.Commit();
+    NS_ENSURE_SUCCESS(rv, rv);
+
     for (uint32_t i = 0; i < bookmarks.Length(); ++i) {
       NOTIFY_OBSERVERS(mCanNotify, mCacheObservers, mObservers,
                        nsINavBookmarkObserver,
                        OnItemChanged(bookmarks[i].id,
                                      NS_LITERAL_CSTRING("keyword"),
                                      false,
                                      EmptyCString(),
                                      bookmarks[i].lastModified,
@@ -2361,16 +2585,18 @@ nsNavBookmarks::SetKeywordForBookmark(in
       rv = NS_NewURI(getter_AddRefs(oldUri), spec);
       NS_ENSURE_SUCCESS(rv, rv);
     }
   }
 
   // If another uri is using the new keyword, we must update the keyword entry.
   // Note we cannot use INSERT OR REPLACE cause it wouldn't invoke the delete
   // trigger.
+  mozStorageTransaction updateTxn(mDB->MainConn(), false);
+
   nsCOMPtr<mozIStorageStatement> stmt;
   if (oldUri) {
     // In both cases, notify about the change.
     nsTArray<BookmarkData> bookmarks;
     rv = GetBookmarksForURI(oldUri, bookmarks);
     NS_ENSURE_SUCCESS(rv, rv);
     for (uint32_t i = 0; i < bookmarks.Length(); ++i) {
       NOTIFY_OBSERVERS(mCanNotify, mCacheObservers, mObservers,
@@ -2404,20 +2630,54 @@ nsNavBookmarks::SetKeywordForBookmark(in
 
   rv = stmt->BindInt64ByName(NS_LITERAL_CSTRING("place_id"), bookmark.placeId);
   NS_ENSURE_SUCCESS(rv, rv);
   rv = stmt->BindStringByName(NS_LITERAL_CSTRING("keyword"), keyword);
   NS_ENSURE_SUCCESS(rv, rv);
   rv = stmt->Execute();
   NS_ENSURE_SUCCESS(rv, rv);
 
-  // In both cases, notify about the change.
+  // Update the sync change counter for all bookmarks with the keyword.
   nsTArray<BookmarkData> bookmarks;
   rv = GetBookmarksForURI(uri, bookmarks);
   NS_ENSURE_SUCCESS(rv, rv);
+  if (!bookmarks.IsEmpty()) {
+    nsAutoCString changedIds;
+    changedIds.AppendInt(bookmarks[0].id);
+    for (uint32_t i = 1; i < bookmarks.Length(); ++i) {
+      changedIds.Append(',');
+      changedIds.AppendInt(bookmarks[i].id);
+    }
+    nsCOMPtr<mozIStorageStatement> stmt = mDB->GetStatement(
+      NS_LITERAL_CSTRING("WITH ids AS ("
+       "SELECT id FROM ("
+        "SELECT id FROM moz_bookmarks "
+        "EXCEPT "
+        "SELECT item_id FROM moz_items_annos WHERE "
+         "anno_attribute_id = ("
+          "SELECT id FROM moz_anno_attributes "
+          "WHERE name = 'places/excludeFromBackup'"
+         ")"
+       ") "
+       "WHERE id IN (") + changedIds + NS_LITERAL_CSTRING(")"
+      ") UPDATE moz_bookmarks SET "
+       "syncChangeCounter = syncChangeCounter + 1 "
+      "WHERE id IN ids")
+    );
+    NS_ENSURE_STATE(stmt);
+    mozStorageStatementScoper scoper(stmt);
+
+    rv = stmt->Execute();
+    NS_ENSURE_SUCCESS(rv, rv);
+  }
+
+  rv = updateTxn.Commit();
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  // In both cases, notify about the change.
   for (uint32_t i = 0; i < bookmarks.Length(); ++i) {
     NOTIFY_OBSERVERS(mCanNotify, mCacheObservers, mObservers,
                      nsINavBookmarkObserver,
                      OnItemChanged(bookmarks[i].id,
                                    NS_LITERAL_CSTRING("keyword"),
                                    false,
                                    NS_ConvertUTF16toUTF8(keyword),
                                    bookmarks[i].lastModified,
@@ -2855,18 +3115,26 @@ nsNavBookmarks::OnPageAnnotationSet(nsIU
 NS_IMETHODIMP
 nsNavBookmarks::OnItemAnnotationSet(int64_t aItemId, const nsACString& aName,
                                     uint16_t aSource)
 {
   BookmarkData bookmark;
   nsresult rv = FetchItemInfo(aItemId, bookmark);
   NS_ENSURE_SUCCESS(rv, rv);
 
+  SyncChangeExclusionPolicy syncPolicy = IGNORE;
+  if (aSource != nsNavBookmarks::SOURCE_SYNC && IsSyncedAnno(aName)) {
+    // Track bookmark and livemark properties. TODO(kitcambridge): Consider
+    // tracking all annotation changes, and filtering them out later.
+    syncPolicy = TRACK;
+  };
+
   bookmark.lastModified = RoundedPRNow();
-  rv = SetItemDateInternal(LAST_MODIFIED, bookmark.id, bookmark.lastModified);
+  rv = SetItemDateInternal(LAST_MODIFIED, syncPolicy, bookmark.id,
+                           bookmark.lastModified);
   NS_ENSURE_SUCCESS(rv, rv);
 
   NOTIFY_OBSERVERS(mCanNotify, mCacheObservers, mObservers,
                    nsINavBookmarkObserver,
                    OnItemChanged(bookmark.id,
                                  aName,
                                  true,
                                  EmptyCString(),
--- a/toolkit/components/places/nsNavBookmarks.h
+++ b/toolkit/components/places/nsNavBookmarks.h
@@ -61,16 +61,22 @@ namespace places {
   typedef void (nsNavBookmarks::*ItemVisitMethod)(const ItemVisitData&);
   typedef void (nsNavBookmarks::*ItemChangeMethod)(const ItemChangeData&);
 
   enum BookmarkDate {
     DATE_ADDED = 0
   , LAST_MODIFIED
   };
 
+  enum SyncChangeExclusionPolicy {
+    IGNORE = 0
+  , IGNORE_IF_EXCLUDED
+  , TRACK
+  };
+
 } // namespace places
 } // namespace mozilla
 
 class nsNavBookmarks final : public nsINavBookmarksService
                            , public nsINavHistoryObserver
                            , public nsIAnnotationObserver
                            , public nsIObserver
                            , public nsSupportsWeakReference
@@ -257,16 +263,18 @@ private:
    */
   nsresult FetchFolderInfo(int64_t aFolderId,
                            int32_t* _folderCount,
                            nsACString& _guid,
                            int64_t* _parentId);
 
   nsresult GetLastChildId(int64_t aFolder, int64_t* aItemId);
 
+  nsresult TrackSyncTagChange(int64_t aTagId, nsIURI* aURI);
+
   /**
    * This is an handle to the Places database.
    */
   RefPtr<mozilla::places::Database> mDB;
 
   int32_t mItemCount;
 
   nsMaybeWeakPtrArray<nsINavBookmarkObserver> mObservers;
@@ -281,16 +289,17 @@ private:
     return aFolderId == mRoot || aFolderId == mMenuRoot ||
            aFolderId == mTagsRoot || aFolderId == mUnfiledRoot ||
            aFolderId == mToolbarRoot;
   }
 
   nsresult IsBookmarkedInDatabase(int64_t aBookmarkID, bool* aIsBookmarked);
 
   nsresult SetItemDateInternal(enum mozilla::places::BookmarkDate aDateType,
+                               enum mozilla::places::SyncChangeExclusionPolicy aSyncPolicy,
                                int64_t aItemId,
                                PRTime aValue);
 
   // Recursive method to build an array of folder's children
   nsresult GetDescendantChildren(int64_t aFolderId,
                                  const nsACString& aFolderGuid,
                                  int64_t aGrandParentId,
                                  nsTArray<BookmarkData>& aFolderChildrenArray);
new file mode 100644
--- /dev/null
+++ b/toolkit/components/places/tests/unit/test_sync_fields.js
@@ -0,0 +1,231 @@
+
+// Tracks a set of bookmark ids 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();
+  }
+
+  _getCounter(id) {
+    let stmt = DBConn().createStatement(
+      `SELECT syncChangeCounter FROM moz_bookmarks WHERE id = :id
+      `
+    );
+    try {
+      stmt.params.id = id;
+      Assert.ok(stmt.executeStep());
+      return stmt.row['syncChangeCounter'];
+    } finally {
+      stmt.finalize();
+    }
+  }
+
+  // Call this after creating a new bookmark.
+  track(id, name, expectedInitial = 1) {
+    if (this.tracked.has(id)) {
+      throw new Error("already tracking this item");
+    }
+    let initial = this._getCounter(id);
+    if (expectedInitial !== undefined) {
+      Assert.equal(initial, expectedInitial, `Initial value of item '${name}' is correct`);
+    }
+    this.tracked.set(id, { name, value: expectedInitial });
+  }
+
+  // Call this to check *only* the specified IDs had a change increment, and
+  // that none of the other "tracked" ones did.
+  check(...expectedToIncrement) {
+    do_print("checking counter for items " + expectedToIncrement);
+    this.tracked.forEach((entry, id) => {
+      let { name, value } = entry;
+      let newValue = this._getCounter(id);
+      let desc = `record '${name}' (id=${id})`;
+      if (expectedToIncrement.indexOf(id) != -1) {
+        // Note we don't check specifically for +1, as some changes will
+        // increment the counter by more than 1 (which is OK).
+        Assert.ok(newValue > value,
+                    `${desc} was expected to increment - was ${value}, now ${newValue}`);
+        this.tracked.set(id, { name, value: newValue });
+      } else {
+        Assert.equal(newValue, value, `${desc} was NOT expected to increment`);
+      }
+    });
+  }
+}
+
+// Most places functions don't expose the sync fields, so we hit the DB
+// directly.
+function* checkSyncFields(id, expected) {
+  let stmt = DBConn().createStatement(
+    `SELECT ${Object.keys(expected).join(", ")}
+     FROM moz_bookmarks
+     WHERE id = :id`
+  );
+  try {
+    stmt.params.id = id;
+    Assert.ok(stmt.executeStep());
+    for (let name in expected) {
+      let expectedValue = expected[name];
+      Assert.equal(stmt.row[name], expectedValue, `field ${name} matches item ${id}`);
+    }
+  } finally {
+    stmt.finalize();
+  }
+}
+
+function* setSyncFields(id, { syncStatus, syncChangeCounter }) {
+  yield PlacesUtils.withConnectionWrapper("test", Task.async(function* (db) {
+    yield db.executeCached(
+      `UPDATE moz_bookmarks SET
+       syncStatus = IFNULL(:syncStatus, syncStatus),
+       syncChangeCounter = IFNULL(:syncChangeCounter, syncChangeCounter)
+       WHERE id = :id`,
+       { id, syncStatus, syncChangeCounter }
+    );
+  }));
+}
+
+function *getAllDeletedGUIDs() {
+  let all = [];
+  yield  PlacesUtils.promiseDBConnection().then(connection => {
+    return connection.executeCached(`SELECT guid FROM moz_bookmarks_deleted;`,
+                                    {},
+                                    row => {
+                                      all.push(row.getResultByIndex(0));
+                                    });
+  });
+  return all;
+}
+
+add_task(function* test_bookmark_changes() {
+  let testUri = NetUtil.newURI("http://test.mozilla.org");
+
+  let id = PlacesUtils.bookmarks.insertBookmark(PlacesUtils.unfiledBookmarksFolderId,
+                                                testUri,
+                                                PlacesUtils.bookmarks.DEFAULT_INDEX,
+                                                "bookmark title");
+
+  let guid = yield PlacesUtils.promiseItemGuid(id);
+  yield checkSyncFields(id, {syncStatus: PlacesUtils.bookmarks.SYNC_STATUS_NEW,
+                             syncChangeCounter: 1 });
+
+  // Pretend Sync just did whatever it does
+  yield setSyncFields(id, { syncStatus: PlacesUtils.bookmarks.SYNC_STATUS_NORMAL });
+  yield checkSyncFields(id, { syncStatus: PlacesUtils.bookmarks.SYNC_STATUS_NORMAL,
+                              syncChangeCounter: 1 });
+
+  // update it - it should increment the change counter
+  yield PlacesUtils.bookmarks.update({ guid, title: "new title" });
+  let updated = yield PlacesUtils.bookmarks.fetch({ guid });
+  Assert.equal(updated.title, "new title", "our update worked as expected");
+
+  yield checkSyncFields(id, { syncStatus: PlacesUtils.bookmarks.SYNC_STATUS_NORMAL,
+                              syncChangeCounter: 2 });
+
+  // Changing annotations that aren't tracked shouldn't increment the counter.
+  PlacesUtils.annotations.setItemAnnotation(id, "random-anno",
+                                            "random-value", 0,
+                                            PlacesUtils.annotations.EXPIRE_NEVER);
+  yield checkSyncFields(id, { syncChangeCounter: 2 });
+
+  // But changing a tracked annotation should update the counter.
+  PlacesUtils.annotations.setItemAnnotation(id, "bookmarkProperties/description",
+                                            "Some description", 0,
+                                            PlacesUtils.annotations.EXPIRE_NEVER);
+  yield checkSyncFields(id, { syncChangeCounter: 3 });
+
+  // Tagging a bookmark should update its change counter.
+  PlacesUtils.tagging.tagURI(testUri, ["test-tag"]);
+  yield checkSyncFields(id, { syncChangeCounter: 4 });
+
+/*
+  // TODO: Implement keyword tracking in PlacesUtils.jsm.
+  yield PlacesUtils.keywords.insert({ keyword: "keyword", url: testUri.spec });
+  yield checkSyncFields(id, { syncChangeCounter: 5 });
+
+  yield PlacesUtils.keywords.remove("keyword");
+  yield checkSyncFields(id, { syncChangeCounter: 6 });
+*/
+});
+
+// XXX - refactor this in the 2 "duplicate" tests, but one using only
+// nsINavBookmarksService and the other using only PlacesUtils "extensions".
+add_task(function* test_bookmark_parenting() {
+  let counterTracker = new CounterTracker();
+
+  let unfiled = PlacesUtils.bookmarks.unfiledBookmarksFolder;
+  let folder1 = PlacesUtils.bookmarks.createFolder(unfiled,
+                                                   "folder1",
+                                                   PlacesUtils.bookmarks.DEFAULT_INDEX);
+  do_print(`Created the first folder, id is ${folder1}`)
+
+  // New folder should have a change recorded.
+  counterTracker.track(folder1, "folder 1");
+
+  // Put a new bookmark in the folder.
+  let testUri = NetUtil.newURI("http://test2.mozilla.org");
+  let child1 = PlacesUtils.bookmarks.insertBookmark(folder1,
+                                                    testUri,
+                                                    PlacesUtils.bookmarks.DEFAULT_INDEX,
+                                                    "bookmark title");
+  do_print(`Created a new bookmark into ${folder1}, id is ${child1}`);
+  // both the folder and the child should have a change recorded.
+  counterTracker.track(child1, "child 1");
+  counterTracker.check(folder1);
+
+  // A new child in the folder at index 0 - even though the existing child
+  // was bumped down the list, it should *not* have a change recorded.
+  let child2 = PlacesUtils.bookmarks.insertBookmark(folder1,
+                                                    testUri,
+                                                    0,
+                                                    "bookmark title");
+  do_print(`Created a second new bookmark into folder ${folder1}, id is ${child2}`);
+
+  counterTracker.track(child2, "child 2");
+  counterTracker.check(folder1);
+
+  // Move the items within the same folder - this should result in just a
+  // change for the parent, but for neither of the children.
+  // child0 is currently at index 0, so move child1 there.
+  PlacesUtils.bookmarks.moveItem(child1, folder1, 0);
+  counterTracker.check(folder1);
+
+  // Another folder to play with.
+  let folder2 = PlacesUtils.bookmarks.createFolder(unfiled,
+                                                   "folder2",
+                                                   PlacesUtils.bookmarks.DEFAULT_INDEX);
+  do_print(`Created a second new folder, id is ${folder2}`);
+  counterTracker.track(folder2, "folder 2");
+  // nothing else has changed.
+  counterTracker.check();
+
+  // Move one of the children to the new folder.
+  do_print(`Moving bookmark ${child2} from folder ${folder1} to folder ${folder2}`);
+  PlacesUtils.bookmarks.moveItem(child2, folder2, PlacesUtils.bookmarks.DEFAULT_INDEX);
+  // child1 should have no change, everything should have a new change.
+  counterTracker.check(folder1, folder2, child2);
+  // TODO - move trees?
+
+  // All fields still have a syncStatus of SYNC_STATUS_NEW - so deleting them
+  // should *not* cause any deleted items to be written.
+  let folder1GUID = yield PlacesUtils.promiseItemGuid(folder1);
+  let child1GUID = yield PlacesUtils.promiseItemGuid(child1);
+  yield PlacesUtils.bookmarks.remove(folder1GUID);
+  Assert.equal((yield getAllDeletedGUIDs()).length, 0);
+
+  // Set folder2 and child2 to have a state of SYNC_STATUS_NORMAL and deleting
+  // them will cause both GUIDs to be written to moz_bookmarks_deleted.
+  yield setSyncFields(folder2, { syncStatus: PlacesUtils.bookmarks.SYNC_STATUS_NORMAL });
+  yield setSyncFields(child2, { syncStatus: PlacesUtils.bookmarks.SYNC_STATUS_NORMAL });
+  let folder2GUID = yield PlacesUtils.promiseItemGuid(folder2);
+  let child2GUID = yield PlacesUtils.promiseItemGuid(child2);
+  yield PlacesUtils.bookmarks.remove(folder2GUID);
+  let deleted = yield getAllDeletedGUIDs();
+  Assert.equal(deleted.length, 2);
+  Assert.ok(deleted.indexOf(folder2GUID) >= 0);
+  Assert.ok(deleted.indexOf(child2GUID) >= 0);
+});
+
+// TODO - tags, annotations, etc?
+// TODO - restore/import?
--- a/toolkit/components/places/tests/unit/xpcshell.ini
+++ b/toolkit/components/places/tests/unit/xpcshell.ini
@@ -137,16 +137,17 @@ skip-if = os == "android"
 [test_promiseBookmarksTree.js]
 # Bug 676989: test hangs consistently on Android
 skip-if = os == "android"
 [test_resolveNullBookmarkTitles.js]
 [test_result_sort.js]
 [test_resultsAsVisit_details.js]
 [test_sql_guid_functions.js]
 [test_svg_favicon.js]
+[test_sync_fields.js]
 [test_tag_autocomplete_search.js]
 [test_tagging.js]
 [test_telemetry.js]
 [test_update_frecency_after_delete.js]
 # Bug 676989: test hangs consistently on Android
 skip-if = os == "android"
 [test_utils_backups_create.js]
 [test_utils_getURLsForContainerNode.js]