--- a/toolkit/components/places/nsNavBookmarks.cpp
+++ b/toolkit/components/places/nsNavBookmarks.cpp
@@ -10,35 +10,40 @@
 #include "nsPlacesMacros.h"
 #include "Helpers.h"
 
 #include "nsAppDirectoryServiceDefs.h"
 #include "nsNetUtil.h"
 #include "nsUnicharUtils.h"
 #include "nsPrintfCString.h"
 #include "prprf.h"
+#include "mozilla/Preferences.h"
 #include "mozilla/storage.h"
 
 #include "GeckoProfiler.h"
 
 using namespace mozilla;
 
 // These columns sit to the right of the kGetInfoIndex_* columns.
 const int32_t nsNavBookmarks::kGetChildrenIndex_Guid = 18;
 const int32_t nsNavBookmarks::kGetChildrenIndex_Position = 19;
 const int32_t nsNavBookmarks::kGetChildrenIndex_Type = 20;
 const int32_t nsNavBookmarks::kGetChildrenIndex_PlaceID = 21;
+const int32_t nsNavBookmarks::kGetChildrenIndex_SyncStatus = 22;
+const int32_t nsNavBookmarks::kGetChildrenIndex_Syncable = 23;
 
 using namespace mozilla::places;
 
 PLACES_FACTORY_SINGLETON_IMPLEMENTATION(nsNavBookmarks, gBookmarksService)
 
 #define BOOKMARKS_ANNO_PREFIX "bookmarks/"
 #define BOOKMARKS_TOOLBAR_FOLDER_ANNO NS_LITERAL_CSTRING(BOOKMARKS_ANNO_PREFIX "toolbarFolder")
 #define FEED_URI_ANNO NS_LITERAL_CSTRING("livemark/feedURI")
+#define SYNC_PARENT_ANNO "sync/parent"
+#define SQLITE_MAX_VARIABLE_NUMBER 999
 
 
 namespace {
 
 #define SKIP_TAGS(condition) ((condition) ? SkipTags : DontSkip)
 
 bool DontSkip(nsCOMPtr<nsINavBookmarkObserver> obs) { return false; }
 bool SkipTags(nsCOMPtr<nsINavBookmarkObserver> obs) {
@@ -119,16 +124,68 @@ public:
   }
 
 private:
   RefPtr<nsNavBookmarks> mBookmarksSvc;
   Method mCallback;
   DataType mData;
 };
 
+// Returns the sync change counter increment for a change source constant.
+inline int64_t
+DetermineSyncChangeDelta(uint16_t aSource) {
+  return aSource == nsINavBookmarksService::SOURCE_SYNC ? 0 : 1;
+}
+
+// Returns the sync status for a new item inserted by a change source.
+inline int32_t
+DetermineInitialSyncStatus(uint16_t aSource) {
+  if (aSource == nsINavBookmarksService::SOURCE_SYNC) {
+    return nsINavBookmarksService::SYNC_STATUS_NORMAL;
+  }
+  if (aSource == nsINavBookmarksService::SOURCE_IMPORT_REPLACE) {
+    return nsINavBookmarksService::SYNC_STATUS_UNKNOWN;
+  }
+  return nsINavBookmarksService::SYNC_STATUS_NEW;
+}
+
+// Indicates whether an item is syncable and has been uploaded to the server.
+inline bool
+NeedsTombstone(const BookmarkData& aBookmark) {
+  return aBookmark.syncable &&
+         aBookmark.syncStatus == nsINavBookmarksService::SYNC_STATUS_NORMAL;
+}
+
+// Removes the Sync orphan annotation from a synced item, so that Sync doesn't
+// try to reparent the item once it sees the original parent.
+nsresult
+PreventSyncReparenting(const BookmarkData& aBookmark, uint16_t aSource)
+{
+  if (!NeedsTombstone(aBookmark)) {
+    return NS_OK;
+  }
+  nsAnnotationService* annosvc = nsAnnotationService::GetAnnotationService();
+  NS_ENSURE_TRUE(annosvc, NS_ERROR_OUT_OF_MEMORY);
+  bool isOrphan;
+  // Check if the anno exists, so that we don't fire spurious
+  // `OnItemAnnotationSet` or `OnItemChanged` notifications.
+  nsresult rv = annosvc->ItemHasAnnotation(aBookmark.id,
+                                           NS_LITERAL_CSTRING(SYNC_PARENT_ANNO),
+                                           &isOrphan);
+  NS_ENSURE_SUCCESS(rv, rv);
+  if (isOrphan) {
+    rv = annosvc->RemoveItemAnnotation(aBookmark.id,
+                                       NS_LITERAL_CSTRING(SYNC_PARENT_ANNO),
+                                       aSource);
+    NS_ENSURE_SUCCESS(rv, rv);
+  }
+  return NS_OK;
+}
+
+
 } // namespace
 
 
 nsNavBookmarks::nsNavBookmarks()
   : mItemCount(0)
   , mRoot(0)
   , mMenuRoot(0)
   , mTagsRoot(0)
@@ -376,20 +433,22 @@ nsNavBookmarks::InsertBookmarkInDB(int64
   // Check for a valid itemId.
   MOZ_ASSERT(_itemId && (*_itemId == -1 || *_itemId > 0));
   // Check for a valid placeId.
   MOZ_ASSERT(aPlaceId && (aPlaceId == -1 || aPlaceId > 0));
 
   nsCOMPtr<mozIStorageStatement> stmt = mDB->GetStatement(
     "INSERT INTO moz_bookmarks "
       "(id, fk, type, parent, position, title, "
-       "dateAdded, lastModified, guid) "
+       "dateAdded, lastModified, guid, syncStatus, syncChangeCounter, "
+       "folder_type /* syncable */) "
     "VALUES (:item_id, :page_id, :item_type, :parent, :item_index, "
             ":item_title, :date_added, :last_modified, "
-            ":item_guid)"
+            ":item_guid, :sync_status, :change_counter, "
+            "(SELECT folder_type /* syncable */ FROM moz_bookmarks WHERE id = :parent))"
   );
   NS_ENSURE_STATE(stmt);
   mozStorageStatementScoper scoper(stmt);
 
   nsresult rv;
   if (*_itemId != -1)
     rv = stmt->BindInt64ByName(NS_LITERAL_CSTRING("item_id"), *_itemId);
   else
@@ -425,42 +484,68 @@ nsNavBookmarks::InsertBookmarkInDB(int64
   }
   else {
     rv = stmt->BindInt64ByName(NS_LITERAL_CSTRING("last_modified"), aDateAdded);
   }
   NS_ENSURE_SUCCESS(rv, rv);
 
   // Could use IsEmpty because our callers check for GUID validity,
   // but it doesn't hurt.
-  if (_guid.Length() == 12) {
+  bool hasExistingGuid = _guid.Length() == 12;
+  if (hasExistingGuid) {
     MOZ_ASSERT(IsValidGUID(_guid));
     rv = stmt->BindUTF8StringByName(NS_LITERAL_CSTRING("item_guid"), _guid);
     NS_ENSURE_SUCCESS(rv, rv);
   }
   else {
     nsAutoCString guid;
     rv = GenerateGUID(guid);
     NS_ENSURE_SUCCESS(rv, rv);
     rv = stmt->BindUTF8StringByName(NS_LITERAL_CSTRING("item_guid"), guid);
     NS_ENSURE_SUCCESS(rv, rv);
     _guid.Assign(guid);
   }
 
+  int64_t syncChangeDelta = DetermineSyncChangeDelta(aSource);
+  rv = stmt->BindInt64ByName(NS_LITERAL_CSTRING("change_counter"),
+                             syncChangeDelta);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  uint16_t syncStatus = DetermineInitialSyncStatus(aSource);
+  rv = stmt->BindInt32ByName(NS_LITERAL_CSTRING("sync_status"),
+                             syncStatus);
+  NS_ENSURE_SUCCESS(rv, rv);
+
   rv = stmt->Execute();
   NS_ENSURE_SUCCESS(rv, rv);
 
+  // Remove stale tombstones if we're reinserting an item.
+  if (hasExistingGuid) {
+    rv = RemoveTombstone(_guid);
+    NS_ENSURE_SUCCESS(rv, rv);
+  }
+
   if (*_itemId == -1) {
     *_itemId = sLastInsertedItemId;
   }
 
   if (aParentId > 0) {
     // 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, syncChangeDelta, aParentId,
+                             aDateAdded);
+    NS_ENSURE_SUCCESS(rv, rv);
+  }
+
+  bool isTagging = aGrandParentId == mTagsRoot;
+  if (isTagging) {
+    // If we're tagging a bookmark, increment the change counter for all
+    // bookmarks with the URI.
+    rv = AddSyncChangesForBookmarksWithURI(aURI, syncChangeDelta);
     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()) {
@@ -479,16 +564,17 @@ nsNavBookmarks::InsertBookmarkInDB(int64
   else
     bookmark.lastModified = aDateAdded;
   if (aURI) {
     rv = aURI->GetSpec(bookmark.url);
     NS_ENSURE_SUCCESS(rv, rv);
   }
   bookmark.parentGuid = aParentGuid;
   bookmark.grandParentId = aGrandParentId;
+  bookmark.syncStatus = syncStatus;
 
   return NS_OK;
 }
 
 NS_IMETHODIMP
 nsNavBookmarks::InsertBookmark(int64_t aFolder,
                                nsIURI* aURI,
                                int32_t aIndex,
@@ -599,18 +685,18 @@ 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 isUntagging = bookmark.grandParentId == mTagsRoot;
+  if (bookmark.parentId != mTagsRoot && !isUntagging) {
     nsAnnotationService* annosvc = nsAnnotationService::GetAnnotationService();
     NS_ENSURE_TRUE(annosvc, NS_ERROR_OUT_OF_MEMORY);
     rv = annosvc->RemoveItemAnnotations(bookmark.id, aSource);
     NS_ENSURE_SUCCESS(rv, rv);
   }
 
   if (bookmark.type == TYPE_FOLDER) {
     // Remove all of the folder's children.
@@ -631,21 +717,36 @@ 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);
   }
 
+  int64_t syncChangeDelta = DetermineSyncChangeDelta(aSource);
+
+  // Add a tombstone for synced items.
+  if (syncChangeDelta) {
+    rv = InsertTombstone(bookmark);
+    NS_ENSURE_SUCCESS(rv, rv);
+  }
+
   bookmark.lastModified = RoundedPRNow();
-  rv = SetItemDateInternal(LAST_MODIFIED, bookmark.parentId,
-                           bookmark.lastModified);
+  rv = SetItemDateInternal(LAST_MODIFIED, syncChangeDelta,
+                           bookmark.parentId, bookmark.lastModified);
   NS_ENSURE_SUCCESS(rv, rv);
 
+  if (isUntagging) {
+    // If we're removing a tag, increment the change counter for all bookmarks
+    // with the URI.
+    rv = AddSyncChangesForBookmarksWithURL(bookmark.url, syncChangeDelta);
+    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();
@@ -993,17 +1094,18 @@ nsNavBookmarks::GetDescendantChildren(in
     // This is a LEFT JOIN because not all bookmarks types have a place.
     // We construct a result where the first columns exactly match
     // kGetInfoIndex_* order, and additionally contains columns for position,
     // item_child, and folder_child from moz_bookmarks.
     nsCOMPtr<mozIStorageStatement> stmt = mDB->GetStatement(
       "SELECT h.id, h.url, IFNULL(b.title, h.title), h.rev_host, h.visit_count, "
              "h.last_visit_date, f.url, b.id, b.dateAdded, b.lastModified, "
              "b.parent, null, h.frecency, h.hidden, h.guid, null, null, null, "
-             "b.guid, b.position, b.type, b.fk "
+             "b.guid, b.position, b.type, b.fk, b.syncStatus, "
+             "b.folder_type = '1' AS syncable "
       "FROM moz_bookmarks b "
       "LEFT JOIN moz_places h ON b.fk = h.id "
       "LEFT JOIN moz_favicons f ON h.favicon_id = f.id "
       "WHERE b.parent = :parent "
       "ORDER BY b.position ASC"
     );
     NS_ENSURE_STATE(stmt);
     mozStorageStatementScoper scoper(stmt);
@@ -1022,16 +1124,20 @@ nsNavBookmarks::GetDescendantChildren(in
       rv = stmt->GetInt32(kGetChildrenIndex_Type, &child.type);
       NS_ENSURE_SUCCESS(rv, rv);
       rv = stmt->GetInt64(kGetChildrenIndex_PlaceID, &child.placeId);
       NS_ENSURE_SUCCESS(rv, rv);
       rv = stmt->GetInt32(kGetChildrenIndex_Position, &child.position);
       NS_ENSURE_SUCCESS(rv, rv);
       rv = stmt->GetUTF8String(kGetChildrenIndex_Guid, child.guid);
       NS_ENSURE_SUCCESS(rv, rv);
+      rv = stmt->GetInt32(kGetChildrenIndex_SyncStatus, &child.syncStatus);
+      NS_ENSURE_SUCCESS(rv, rv);
+      rv = stmt->GetInt32(kGetChildrenIndex_Syncable, &child.syncable);
+      NS_ENSURE_SUCCESS(rv, rv);
 
       if (child.type == TYPE_BOOKMARK) {
         rv = stmt->GetUTF8String(nsNavHistory::kGetInfoIndex_URL, child.url);
         NS_ENSURE_SUCCESS(rv, rv);
       }
 
       // Append item to children's array.
       aFolderChildrenArray.AppendElement(child);
@@ -1086,16 +1192,18 @@ nsNavBookmarks::RemoveFolderChildren(int
     BookmarkData& child = folderChildrenArray[i];
 
     if (child.type == TYPE_FOLDER) {
       foldersToRemove.Append(',');
       foldersToRemove.AppendInt(child.id);
     }
   }
 
+  int64_t syncChangeDelta = DetermineSyncChangeDelta(aSource);
+
   // Delete items from the database now.
   mozStorageTransaction transaction(mDB->MainConn(), false);
 
   nsCOMPtr<mozIStorageStatement> deleteStatement = mDB->GetStatement(
     NS_LITERAL_CSTRING(
       "DELETE FROM moz_bookmarks "
       "WHERE parent IN (:parent") + foldersToRemove + NS_LITERAL_CSTRING(")")
   );
@@ -1113,19 +1221,44 @@ 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, syncChangeDelta, folder.id,
+                           RoundedPRNow());
   NS_ENSURE_SUCCESS(rv, rv);
 
+  if (syncChangeDelta) {
+    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};
+        tombstones.AppendElement(childTombstone);
+      }
+      bool isUntagging = child.grandParentId == mTagsRoot;
+      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);
+    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];
 
     nsCOMPtr<nsIURI> uri;
@@ -1256,38 +1389,47 @@ 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);
     }
     NS_ENSURE_SUCCESS(rv, rv);
   }
   else {
+    if (!MatchesSyncable(aNewParent, bookmark.syncable)) {
+      // Moving an item from a synced folder to an unsynced folder causes
+      // other devices to miss changes; moving from unsynced to synced
+      // orphans an item's descendants and uploads an inconsistent tree.
+      return NS_ERROR_INVALID_ARG;
+    }
     // We're moving between containers, so this happens in two steps.
     // First, fill the hole from the removal from the old parent.
     rv = AdjustIndices(bookmark.parentId, bookmark.position + 1, INT32_MAX, -1);
     NS_ENSURE_SUCCESS(rv, rv);
     // Now, make room in the new parent for the insertion.
     rv = AdjustIndices(aNewParent, newIndex, INT32_MAX, 1);
     NS_ENSURE_SUCCESS(rv, rv);
   }
 
+  int64_t syncChangeDelta = DetermineSyncChangeDelta(aSource);
+
   {
     // Update parent and position.
     nsCOMPtr<mozIStorageStatement> stmt = mDB->GetStatement(
       "UPDATE moz_bookmarks SET parent = :parent, position = :item_index "
       "WHERE id = :item_id "
     );
     NS_ENSURE_STATE(stmt);
     mozStorageStatementScoper scoper(stmt);
@@ -1298,19 +1440,43 @@ nsNavBookmarks::MoveItem(int64_t aItemId
     NS_ENSURE_SUCCESS(rv, rv);
     rv = stmt->BindInt64ByName(NS_LITERAL_CSTRING("item_id"), bookmark.id);
     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, syncChangeDelta,
+                           bookmark.parentId, now);
   NS_ENSURE_SUCCESS(rv, rv);
-  rv = SetItemDateInternal(LAST_MODIFIED, aNewParent, now);
+  if (sameParent) {
+    // If we're moving within the same container, only the parent needs a sync
+    // change. Update the item's last modified date without bumping its counter.
+    rv = SetItemDateInternal(LAST_MODIFIED, 0, bookmark.id, now);
+    NS_ENSURE_SUCCESS(rv, rv);
+  } else {
+    // Otherwise, if we're moving between containers, both parents and the child
+    // need sync changes.
+    rv = SetItemDateInternal(LAST_MODIFIED, syncChangeDelta, aNewParent, now);
+    NS_ENSURE_SUCCESS(rv, rv);
+    rv = SetItemDateInternal(LAST_MODIFIED, syncChangeDelta, bookmark.id, now);
+    NS_ENSURE_SUCCESS(rv, rv);
+  }
+
+  bool isChangingTagFolder = bookmark.parentId == mTagsRoot;
+  if (isChangingTagFolder) {
+    // Moving a tag folder out of the tags root untags all its bookmarks. This
+    // is an odd case, but the tagging service adds an observer to handle it,
+    // so we bump the change counter for each untagged item for consistency.
+    rv = AddSyncChangesForBookmarksInFolder(bookmark.id, syncChangeDelta);
+    NS_ENSURE_SUCCESS(rv, rv);
+  }
+
+  rv = PreventSyncReparenting(bookmark, aSource);
   NS_ENSURE_SUCCESS(rv, rv);
 
   rv = transaction.Commit();
   NS_ENSURE_SUCCESS(rv, rv);
 
   NOTIFY_OBSERVERS(mCanNotify, mCacheObservers, mObservers,
                    nsINavBookmarkObserver,
                    OnItemMoved(bookmark.id,
@@ -1328,17 +1494,18 @@ nsNavBookmarks::MoveItem(int64_t aItemId
 
 nsresult
 nsNavBookmarks::FetchItemInfo(int64_t aItemId,
                               BookmarkData& _bookmark)
 {
   // LEFT JOIN since not all bookmarks have an associated place.
   nsCOMPtr<mozIStorageStatement> stmt = mDB->GetStatement(
     "SELECT b.id, h.url, b.title, b.position, b.fk, b.parent, b.type, "
-           "b.dateAdded, b.lastModified, b.guid, t.guid, t.parent "
+           "b.dateAdded, b.lastModified, b.guid, t.guid, t.parent, "
+           "b.syncStatus, b.folder_type = '1' AS syncable "
     "FROM moz_bookmarks b "
     "LEFT JOIN moz_bookmarks t ON t.id = b.parent "
     "LEFT JOIN moz_places h ON h.id = b.fk "
     "WHERE b.id = :item_id"
   );
   NS_ENSURE_STATE(stmt);
   mozStorageStatementScoper scoper(stmt);
 
@@ -1386,49 +1553,59 @@ nsNavBookmarks::FetchItemInfo(int64_t aI
     rv = stmt->GetUTF8String(10, _bookmark.parentGuid);
     NS_ENSURE_SUCCESS(rv, rv);
     rv = stmt->GetInt64(11, &_bookmark.grandParentId);
     NS_ENSURE_SUCCESS(rv, rv);
   }
   else {
     _bookmark.grandParentId = -1;
   }
+  rv = stmt->GetInt32(12, &_bookmark.syncStatus);
+  NS_ENSURE_SUCCESS(rv, rv);
+  rv = stmt->GetInt32(13, &_bookmark.syncable);
+  NS_ENSURE_SUCCESS(rv, rv);
 
   return NS_OK;
 }
 
 nsresult
 nsNavBookmarks::SetItemDateInternal(enum BookmarkDate aDateType,
+                                    int64_t aSyncChangeDelta,
                                     int64_t aItemId,
                                     PRTime aValue)
 {
   aValue = RoundToMilliseconds(aValue);
 
   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 "
+      "UPDATE moz_bookmarks SET dateAdded = :date, lastModified = :date, "
+       "syncChangeCounter = syncChangeCounter + :delta "
       "WHERE id = :item_id"
     );
   }
   else {
     stmt = mDB->GetStatement(
-      "UPDATE moz_bookmarks SET lastModified = :date WHERE id = :item_id"
+      "UPDATE moz_bookmarks SET lastModified = :date, "
+       "syncChangeCounter = syncChangeCounter + :delta "
+      "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);
   NS_ENSURE_SUCCESS(rv, rv);
+  rv = stmt->BindInt64ByName(NS_LITERAL_CSTRING("delta"), aSyncChangeDelta);
+  NS_ENSURE_SUCCESS(rv, rv);
 
   rv = stmt->Execute();
   NS_ENSURE_SUCCESS(rv, rv);
 
   // note, we are not notifying the observers
   // that the item has changed.
 
   return NS_OK;
@@ -1440,21 +1617,42 @@ nsNavBookmarks::SetItemDateAdded(int64_t
                                  uint16_t aSource)
 {
   NS_ENSURE_ARG_MIN(aItemId, 1);
 
   BookmarkData bookmark;
   nsresult rv = FetchItemInfo(aItemId, bookmark);
   NS_ENSURE_SUCCESS(rv, rv);
 
+  bool isTagging = bookmark.grandParentId == mTagsRoot;
+  int64_t syncChangeDelta = DetermineSyncChangeDelta(aSource);
+
   // Round here so that we notify with the right value.
   bookmark.dateAdded = RoundToMilliseconds(aDateAdded);
 
-  rv = SetItemDateInternal(DATE_ADDED, bookmark.id, bookmark.dateAdded);
-  NS_ENSURE_SUCCESS(rv, rv);
+  if (isTagging) {
+    // If we're changing a tag, bump the change counter for all tagged
+    // bookmarks. We use a separate code path to avoid a transaction for
+    // non-tags.
+    mozStorageTransaction transaction(mDB->MainConn(), false);
+
+    rv = SetItemDateInternal(DATE_ADDED, syncChangeDelta, bookmark.id,
+                             bookmark.dateAdded);
+    NS_ENSURE_SUCCESS(rv, rv);
+
+    rv = AddSyncChangesForBookmarksWithURL(bookmark.url, syncChangeDelta);
+    NS_ENSURE_SUCCESS(rv, rv);
+
+    rv = transaction.Commit();
+    NS_ENSURE_SUCCESS(rv, rv);
+  } else {
+    rv = SetItemDateInternal(DATE_ADDED, syncChangeDelta, 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,
                                  nsPrintfCString("%lld", bookmark.dateAdded),
@@ -1489,21 +1687,42 @@ nsNavBookmarks::SetItemLastModified(int6
                                     uint16_t aSource)
 {
   NS_ENSURE_ARG_MIN(aItemId, 1);
 
   BookmarkData bookmark;
   nsresult rv = FetchItemInfo(aItemId, bookmark);
   NS_ENSURE_SUCCESS(rv, rv);
 
+  bool isTagging = bookmark.grandParentId == mTagsRoot;
+  int64_t syncChangeDelta = DetermineSyncChangeDelta(aSource);
+
   // Round here so that we notify with the right value.
   bookmark.lastModified = RoundToMilliseconds(aLastModified);
 
-  rv = SetItemDateInternal(LAST_MODIFIED, bookmark.id, bookmark.lastModified);
-  NS_ENSURE_SUCCESS(rv, rv);
+  if (isTagging) {
+    // If we're changing a tag, bump the change counter for all tagged
+    // bookmarks. We use a separate code path to avoid a transaction for
+    // non-tags.
+    mozStorageTransaction transaction(mDB->MainConn(), false);
+
+    rv = SetItemDateInternal(LAST_MODIFIED, syncChangeDelta, bookmark.id,
+                             bookmark.lastModified);
+    NS_ENSURE_SUCCESS(rv, rv);
+
+    rv = AddSyncChangesForBookmarksWithURL(bookmark.url, syncChangeDelta);
+    NS_ENSURE_SUCCESS(rv, rv);
+
+    rv = transaction.Commit();
+    NS_ENSURE_SUCCESS(rv, rv);
+  } else {
+    rv = SetItemDateInternal(LAST_MODIFIED, syncChangeDelta, 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,
                                  nsPrintfCString("%lld", bookmark.lastModified),
@@ -1528,54 +1747,225 @@ nsNavBookmarks::GetItemLastModified(int6
   nsresult rv = FetchItemInfo(aItemId, bookmark);
   NS_ENSURE_SUCCESS(rv, rv);
 
   *_lastModified = bookmark.lastModified;
   return NS_OK;
 }
 
 
+nsresult
+nsNavBookmarks::AddSyncChangesForBookmarksWithURL(const nsACString& aURL,
+                                                  int64_t aSyncChangeDelta)
+{
+  if (!aSyncChangeDelta) {
+    return NS_OK;
+  }
+  nsCOMPtr<nsIURI> uri;
+  nsresult rv = NS_NewURI(getter_AddRefs(uri), aURL);
+  if (NS_WARN_IF(NS_FAILED(rv))) {
+    // Ignore sync changes for invalid URLs.
+    return NS_OK;
+  }
+  return AddSyncChangesForBookmarksWithURI(uri, aSyncChangeDelta);
+}
+
+
+nsresult
+nsNavBookmarks::AddSyncChangesForBookmarksWithURI(nsIURI* aURI,
+                                                  int64_t aSyncChangeDelta)
+{
+  if (NS_WARN_IF(!aURI) || !aSyncChangeDelta) {
+    // Ignore sync changes for invalid URIs.
+    return NS_OK;
+  }
+
+  nsCOMPtr<mozIStorageStatement> statement = mDB->GetStatement(
+   "UPDATE moz_bookmarks SET "
+    "syncChangeCounter = syncChangeCounter + :delta "
+   "WHERE folder_type = '1' /* syncable */ AND "
+         "type = :type AND "
+         "fk = (SELECT id FROM moz_places WHERE url_hash = hash(:url) AND "
+               "url = :url)"
+  );
+  NS_ENSURE_STATE(statement);
+  mozStorageStatementScoper scoper(statement);
+
+  nsresult rv = statement->BindInt64ByName(NS_LITERAL_CSTRING("delta"),
+                                           aSyncChangeDelta);
+  NS_ENSURE_SUCCESS(rv, rv);
+  rv = statement->BindInt64ByName(NS_LITERAL_CSTRING("type"),
+                                  nsINavBookmarksService::TYPE_BOOKMARK);
+  NS_ENSURE_SUCCESS(rv, rv);
+  rv = URIBinder::Bind(statement, NS_LITERAL_CSTRING("url"), aURI);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  return statement->Execute();
+}
+
+
+nsresult
+nsNavBookmarks::AddSyncChangesForBookmarksInFolder(int64_t aFolderId,
+                                                   int64_t aSyncChangeDelta)
+{
+  if (!aSyncChangeDelta) {
+    return NS_OK;
+  }
+
+  nsCOMPtr<mozIStorageStatement> statement = mDB->GetStatement(
+   "UPDATE moz_bookmarks SET "
+    "syncChangeCounter = syncChangeCounter + :delta "
+    "WHERE type = :type AND "
+          "fk = (SELECT fk FROM moz_bookmarks WHERE parent = :parent) AND "
+          "folder_type /* syncable */ = '1'"
+  );
+  NS_ENSURE_STATE(statement);
+  mozStorageStatementScoper scoper(statement);
+
+  nsresult rv = statement->BindInt64ByName(NS_LITERAL_CSTRING("delta"),
+                                           aSyncChangeDelta);
+  NS_ENSURE_SUCCESS(rv, rv);
+  rv = statement->BindInt64ByName(NS_LITERAL_CSTRING("type"),
+                                  nsINavBookmarksService::TYPE_BOOKMARK);
+  NS_ENSURE_SUCCESS(rv, rv);
+  rv = statement->BindInt64ByName(NS_LITERAL_CSTRING("parent"), aFolderId);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  rv = statement->Execute();
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  return NS_OK;
+}
+
+
+nsresult
+nsNavBookmarks::InsertTombstone(const BookmarkData& aBookmark)
+{
+  if (!NeedsTombstone(aBookmark)) {
+    return NS_OK;
+  }
+  nsCOMPtr<mozIStorageStatement> stmt = mDB->GetStatement(
+    "INSERT INTO moz_bookmarks_deleted (guid, dateRemoved) "
+    "VALUES (:guid, :date_removed)"
+  );
+  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->Execute();
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  return NS_OK;
+}
+
+
+nsresult
+nsNavBookmarks::InsertTombstones(const nsTArray<TombstoneData>& aTombstones)
+{
+  if (aTombstones.IsEmpty()) {
+    return NS_OK;
+  }
+
+  size_t paramsPerChunk = SQLITE_MAX_VARIABLE_NUMBER / 2;
+  for (uint32_t startIndex = 0; startIndex < aTombstones.Length(); startIndex += paramsPerChunk) {
+    size_t chunkLength = std::min(paramsPerChunk, aTombstones.Length() - startIndex);
+
+    // Build a query to insert all tombstones in a single statement.
+    nsAutoCString tombstonesToInsert;
+    tombstonesToInsert.AppendLiteral("VALUES (?, ?)");
+    for (uint32_t i = 1; i < chunkLength; ++i) {
+      tombstonesToInsert.AppendLiteral(", (?, ?)");
+    }
+#ifdef DEBUG
+    MOZ_ASSERT(tombstonesToInsert.CountChar('?') == chunkLength * 2,
+               "Expected one binding param per column for each tombstone");
+#endif
+
+    nsCOMPtr<mozIStorageStatement> stmt = mDB->GetStatement(
+      NS_LITERAL_CSTRING("INSERT INTO moz_bookmarks_deleted "
+        "(guid, dateRemoved) ") +
+      tombstonesToInsert
+    );
+    NS_ENSURE_STATE(stmt);
+    mozStorageStatementScoper scoper(stmt);
+
+    uint32_t paramIndex = 0;
+    nsresult rv;
+    for (uint32_t i = 0; i < chunkLength; ++i) {
+      const TombstoneData& tombstone = aTombstones[startIndex + i];
+      rv = stmt->BindUTF8StringByIndex(paramIndex++, tombstone.guid);
+      NS_ENSURE_SUCCESS(rv, rv);
+      rv = stmt->BindInt64ByIndex(paramIndex++, tombstone.dateRemoved);
+      NS_ENSURE_SUCCESS(rv, rv);
+    }
+
+    rv = stmt->Execute();
+    NS_ENSURE_SUCCESS(rv, rv);
+  }
+
+  return NS_OK;
+}
+
+
+nsresult
+nsNavBookmarks::RemoveTombstone(const nsACString& aGUID)
+{
+  nsCOMPtr<mozIStorageStatement> stmt = mDB->GetStatement(
+    "DELETE FROM moz_bookmarks_deleted WHERE guid = :guid"
+  );
+  NS_ENSURE_STATE(stmt);
+  mozStorageStatementScoper scoper(stmt);
+
+  nsresult rv = stmt->BindUTF8StringByName(NS_LITERAL_CSTRING("guid"), aGUID);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  return stmt->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 "
-  );
-  NS_ENSURE_STATE(statement);
-  mozStorageStatementScoper scoper(statement);
-
-  nsCString title;
+  bool isChangingTagFolder = bookmark.parentId == mTagsRoot;
+  int64_t syncChangeDelta = DetermineSyncChangeDelta(aSource);
+
+  nsAutoCString title;
   TruncateTitle(aTitle, title);
 
-  // Support setting a null title, we support this in insertBookmark.
-  if (title.IsVoid()) {
-    rv = statement->BindNullByName(NS_LITERAL_CSTRING("item_title"));
+  if (isChangingTagFolder) {
+    // If we're changing the title of a tag folder, bump the change counter
+    // for all tagged bookmarks. We use a separate code path to avoid a
+    // transaction for non-tags.
+    mozStorageTransaction transaction(mDB->MainConn(), false);
+
+    rv = SetItemTitleInternal(bookmark, aTitle, syncChangeDelta);
+    NS_ENSURE_SUCCESS(rv, rv);
+
+    rv = AddSyncChangesForBookmarksInFolder(bookmark.id, syncChangeDelta);
+    NS_ENSURE_SUCCESS(rv, rv);
+
+    rv = transaction.Commit();
+    NS_ENSURE_SUCCESS(rv, rv);
+  } else {
+    rv = SetItemTitleInternal(bookmark, title, syncChangeDelta);
+    NS_ENSURE_SUCCESS(rv, rv);
   }
-  else {
-    rv = statement->BindUTF8StringByName(NS_LITERAL_CSTRING("item_title"),
-                                         title);
-  }
-  NS_ENSURE_SUCCESS(rv, rv);
-  bookmark.lastModified = RoundToMilliseconds(RoundedPRNow());
-  rv = statement->BindInt64ByName(NS_LITERAL_CSTRING("date"),
-                                  bookmark.lastModified);
-  NS_ENSURE_SUCCESS(rv, rv);
-  rv = statement->BindInt64ByName(NS_LITERAL_CSTRING("item_id"), bookmark.id);
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  rv = statement->Execute();
-  NS_ENSURE_SUCCESS(rv, rv);
 
   NOTIFY_OBSERVERS(mCanNotify, mCacheObservers, mObservers,
                    nsINavBookmarkObserver,
                    OnItemChanged(bookmark.id,
                                  NS_LITERAL_CSTRING("title"),
                                  false,
                                  title,
                                  bookmark.lastModified,
@@ -1584,16 +1974,57 @@ nsNavBookmarks::SetItemTitle(int64_t aIt
                                  bookmark.guid,
                                  bookmark.parentGuid,
                                  EmptyCString(),
                                  aSource));
   return NS_OK;
 }
 
 
+nsresult
+nsNavBookmarks::SetItemTitleInternal(BookmarkData& aBookmark,
+                                     const nsACString& aTitle,
+                                     int64_t aSyncChangeDelta)
+{
+  nsCOMPtr<mozIStorageStatement> statement = mDB->GetStatement(
+    "UPDATE moz_bookmarks SET "
+     "title = :item_title, lastModified = :date, "
+     "syncChangeCounter = syncChangeCounter + :delta "
+    "WHERE id = :item_id"
+  );
+  NS_ENSURE_STATE(statement);
+  mozStorageStatementScoper scoper(statement);
+
+  // Support setting a null title, we support this in insertBookmark.
+  nsresult rv;
+  if (aTitle.IsVoid()) {
+    rv = statement->BindNullByName(NS_LITERAL_CSTRING("item_title"));
+  }
+  else {
+    rv = statement->BindUTF8StringByName(NS_LITERAL_CSTRING("item_title"),
+                                         aTitle);
+  }
+  NS_ENSURE_SUCCESS(rv, rv);
+  aBookmark.lastModified = RoundToMilliseconds(RoundedPRNow());
+  rv = statement->BindInt64ByName(NS_LITERAL_CSTRING("date"),
+                                  aBookmark.lastModified);
+  NS_ENSURE_SUCCESS(rv, rv);
+  rv = statement->BindInt64ByName(NS_LITERAL_CSTRING("item_id"), aBookmark.id);
+  NS_ENSURE_SUCCESS(rv, rv);
+  rv = statement->BindInt64ByName(NS_LITERAL_CSTRING("delta"),
+                                  aSyncChangeDelta);
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  rv = statement->Execute();
+  NS_ENSURE_SUCCESS(rv, rv);
+
+  return NS_OK;
+}
+
+
 NS_IMETHODIMP
 nsNavBookmarks::GetItemTitle(int64_t aItemId,
                              nsACString& _title)
 {
   NS_ENSURE_ARG_MIN(aItemId, 1);
 
   BookmarkData bookmark;
   nsresult rv = FetchItemInfo(aItemId, bookmark);
@@ -1837,16 +2268,34 @@ nsNavBookmarks::QueryFolderChildrenAsync
   rv = stmt->ExecuteAsync(aNode, getter_AddRefs(pendingStmt));
   NS_ENSURE_SUCCESS(rv, rv);
 
   NS_IF_ADDREF(*_pendingStmt = pendingStmt);
   return NS_OK;
 }
 
 
+bool
+nsNavBookmarks::MatchesSyncable(int64_t aItemId, int32_t aSyncable)
+{
+  nsCOMPtr<mozIStorageStatement> stmt = mDB->GetStatement(
+    "SELECT 1 FROM moz_bookmarks WHERE id = :item_id AND folder_type = '1'");
+  NS_ENSURE_TRUE(stmt, false);
+  mozStorageStatementScoper scoper(stmt);
+
+  nsresult rv = stmt->BindInt64ByName(NS_LITERAL_CSTRING("item_id"), aItemId);
+  NS_ENSURE_SUCCESS(rv, false);
+
+  bool hasResult;
+  rv = stmt->ExecuteStep(&hasResult);
+  NS_ENSURE_SUCCESS(rv, false);
+  return hasResult == !!aSyncable;
+}
+
+
 nsresult
 nsNavBookmarks::FetchFolderInfo(int64_t aFolderId,
                                 int32_t* _folderCount,
                                 nsACString& _guid,
                                 int64_t* _parentId)
 {
   *_folderCount = 0;
   *_parentId = -1;
@@ -2011,43 +2460,59 @@ nsNavBookmarks::ChangeBookmarkURI(int64_
 
   BookmarkData bookmark;
   nsresult rv = FetchItemInfo(aBookmarkId, bookmark);
   NS_ENSURE_SUCCESS(rv, rv);
   NS_ENSURE_ARG(bookmark.type == TYPE_BOOKMARK);
 
   mozStorageTransaction transaction(mDB->MainConn(), false);
 
+  bool isTagging = bookmark.grandParentId == mTagsRoot;
+  int64_t syncChangeDelta = DetermineSyncChangeDelta(aSource);
+
   nsNavHistory* history = nsNavHistory::GetHistoryService();
   NS_ENSURE_TRUE(history, NS_ERROR_OUT_OF_MEMORY);
   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 + :delta "
     "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();
   rv = statement->BindInt64ByName(NS_LITERAL_CSTRING("date"),
                                   bookmark.lastModified);
   NS_ENSURE_SUCCESS(rv, rv);
   rv = statement->BindInt64ByName(NS_LITERAL_CSTRING("item_id"), bookmark.id);
   NS_ENSURE_SUCCESS(rv, rv);
+  rv = statement->BindInt64ByName(NS_LITERAL_CSTRING("delta"), syncChangeDelta);
+  NS_ENSURE_SUCCESS(rv, rv);
   rv = statement->Execute();
   NS_ENSURE_SUCCESS(rv, rv);
 
+  if (isTagging) {
+    // For consistency with the tagging service behavior, changing a tag entry's
+    // URL bumps the change counter for bookmarks with the old and new URIs.
+    rv = AddSyncChangesForBookmarksWithURL(bookmark.url, syncChangeDelta);
+    NS_ENSURE_SUCCESS(rv, rv);
+    rv = AddSyncChangesForBookmarksWithURI(aNewURI, syncChangeDelta);
+    NS_ENSURE_SUCCESS(rv, rv);
+  }
+
   rv = transaction.Commit();
   NS_ENSURE_SUCCESS(rv, rv);
 
   rv = history->UpdateFrecency(newPlaceId);
   NS_ENSURE_SUCCESS(rv, rv);
 
   // Upon changing the URI for a bookmark, update the frecency for the old
   // place as well.
@@ -2144,17 +2609,17 @@ nsNavBookmarks::GetBookmarksForURI(nsIUR
 {
   NS_ENSURE_ARG(aURI);
 
   // Double ordering covers possible lastModified ties, that could happen when
   // importing, syncing or due to extensions.
   // Note: not using a JOIN is cheaper in this case.
   nsCOMPtr<mozIStorageStatement> stmt = mDB->GetStatement(
     "/* do not warn (bug 1175249) */ "
-    "SELECT b.id, b.guid, b.parent, b.lastModified, t.guid, t.parent "
+    "SELECT b.id, b.guid, b.parent, b.lastModified, t.guid, t.parent, b.syncStatus "
     "FROM moz_bookmarks b "
     "JOIN moz_bookmarks t on t.id = b.parent "
     "WHERE b.fk = (SELECT id FROM moz_places WHERE url_hash = hash(:page_url) AND url = :page_url) "
     "ORDER BY b.lastModified DESC, b.id DESC "
   );
   NS_ENSURE_STATE(stmt);
   mozStorageStatementScoper scoper(stmt);
 
@@ -2179,16 +2644,18 @@ nsNavBookmarks::GetBookmarksForURI(nsIUR
     rv = stmt->GetUTF8String(1, bookmark.guid);
     NS_ENSURE_SUCCESS(rv, rv);
     rv = stmt->GetInt64(2, &bookmark.parentId);
     NS_ENSURE_SUCCESS(rv, rv);
     rv = stmt->GetInt64(3, reinterpret_cast<int64_t*>(&bookmark.lastModified));
     NS_ENSURE_SUCCESS(rv, rv);
     rv = stmt->GetUTF8String(4, bookmark.parentGuid);
     NS_ENSURE_SUCCESS(rv, rv);
+    rv = stmt->GetInt32(6, &bookmark.syncStatus);
+    NS_ENSURE_SUCCESS(rv, rv);
 
     NS_ENSURE_TRUE(aBookmarks.AppendElement(bookmark), NS_ERROR_OUT_OF_MEMORY);
   }
 
   return NS_OK;
 }
 
 NS_IMETHODIMP
@@ -2258,28 +2725,64 @@ 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);
+  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);
+  }
+
+  int64_t syncChangeDelta = DetermineSyncChangeDelta(aSource);
+
+  {
+    // Sync stores child indices in the parent's record, so we only need to
+    // bump the parent's change counter.
+    nsCOMPtr<mozIStorageStatement> stmt = mDB->GetStatement(
+      "UPDATE moz_bookmarks SET "
+       "syncChangeCounter = syncChangeCounter + :delta "
+      "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->BindInt64ByName(NS_LITERAL_CSTRING("delta"),
+                               syncChangeDelta);
+    NS_ENSURE_SUCCESS(rv, rv);
+
+    rv = stmt->Execute();
+    NS_ENSURE_SUCCESS(rv, rv);
+  }
+
+  rv = PreventSyncReparenting(bookmark, aSource);
   NS_ENSURE_SUCCESS(rv, rv);
-  rv = stmt->BindInt32ByName(NS_LITERAL_CSTRING("item_index"), aNewIndex);
-  NS_ENSURE_SUCCESS(rv, rv);
-
-  rv = stmt->Execute();
+
+  rv = transaction.Commit();
   NS_ENSURE_SUCCESS(rv, rv);
 
   NOTIFY_OBSERVERS(mCanNotify, mCacheObservers, mObservers,
                    nsINavBookmarkObserver,
                    OnItemMoved(bookmark.id,
                                bookmark.parentId,
                                bookmark.position,
                                bookmark.parentId,
@@ -2334,17 +2837,21 @@ nsNavBookmarks::SetKeywordForBookmark(in
     }
   }
 
   // Trying to remove a non-existent keyword is a no-op.
   if (keyword.IsEmpty() && oldKeywords.Length() == 0) {
     return NS_OK;
   }
 
+  int64_t syncChangeDelta = DetermineSyncChangeDelta(aSource);
+
   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"),
@@ -2352,16 +2859,47 @@ 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 (syncChangeDelta && !bookmarks.IsEmpty()) {
+      // Build a query to update all bookmarks in a single statement.
+      nsAutoCString changedIds;
+      changedIds.AppendInt(bookmarks[0].id);
+      for (uint32_t i = 1; i < bookmarks.Length(); ++i) {
+        changedIds.Append(',');
+        changedIds.AppendInt(bookmarks[i].id);
+      }
+      // Update the sync change counter for all bookmarks with the removed
+      // keyword.
+      nsCOMPtr<mozIStorageStatement> stmt = mDB->GetStatement(
+        NS_LITERAL_CSTRING(
+        "UPDATE moz_bookmarks SET "
+         "syncChangeCounter = syncChangeCounter + :delta "
+        "WHERE id IN (") + changedIds + NS_LITERAL_CSTRING(")")
+      );
+      NS_ENSURE_STATE(stmt);
+      mozStorageStatementScoper scoper(stmt);
+
+      rv = stmt->BindInt64ByName(NS_LITERAL_CSTRING("delta"),
+                                 syncChangeDelta);
+      NS_ENSURE_SUCCESS(rv, rv);
+
+      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,
@@ -2400,16 +2938,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,
@@ -2443,20 +2983,49 @@ 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.
   nsTArray<BookmarkData> bookmarks;
   rv = GetBookmarksForURI(uri, bookmarks);
   NS_ENSURE_SUCCESS(rv, rv);
+
+  if (syncChangeDelta && !bookmarks.IsEmpty()) {
+    // Build a query to update all bookmarks in a single statement.
+    nsAutoCString changedIds;
+    changedIds.AppendInt(bookmarks[0].id);
+    for (uint32_t i = 1; i < bookmarks.Length(); ++i) {
+      changedIds.Append(',');
+      changedIds.AppendInt(bookmarks[i].id);
+    }
+    // Update the sync change counter for all bookmarks with the new keyword.
+    nsCOMPtr<mozIStorageStatement> stmt = mDB->GetStatement(
+      NS_LITERAL_CSTRING(
+      "UPDATE moz_bookmarks SET "
+       "syncChangeCounter = syncChangeCounter + :delta "
+      "WHERE id IN (") + changedIds + NS_LITERAL_CSTRING(")")
+    );
+    NS_ENSURE_STATE(stmt);
+    mozStorageStatementScoper scoper(stmt);
+
+    rv = stmt->BindInt64ByName(NS_LITERAL_CSTRING("delta"), syncChangeDelta);
+    NS_ENSURE_SUCCESS(rv, rv);
+
+    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,
@@ -2893,17 +3462,18 @@ 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);
 
   bookmark.lastModified = RoundedPRNow();
-  rv = SetItemDateInternal(LAST_MODIFIED, bookmark.id, bookmark.lastModified);
+  rv = SetItemDateInternal(LAST_MODIFIED, DetermineSyncChangeDelta(aSource),
+                           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
@@ -31,16 +31,18 @@ namespace places {
     int64_t id;
     nsCString url;
     nsCString title;
     int32_t position;
     int64_t placeId;
     int64_t parentId;
     int64_t grandParentId;
     int32_t type;
+    int32_t syncStatus;
+    int32_t syncable;
     nsCString serviceCID;
     PRTime dateAdded;
     PRTime lastModified;
     nsCString guid;
     nsCString parentGuid;
   };
 
   struct ItemVisitData {
@@ -53,16 +55,21 @@ namespace places {
   struct ItemChangeData {
     BookmarkData bookmark;
     nsCString property;
     bool isAnnotation;
     nsCString newValue;
     nsCString oldValue;
   };
 
+  struct TombstoneData {
+    nsCString guid;
+    PRTime dateRemoved;
+  };
+
   typedef void (nsNavBookmarks::*ItemVisitMethod)(const ItemVisitData&);
   typedef void (nsNavBookmarks::*ItemChangeMethod)(const ItemChangeData&);
 
   enum BookmarkDate {
     DATE_ADDED = 0
   , LAST_MODIFIED
   };
 
@@ -210,16 +217,18 @@ public:
    */
   nsresult GetDescendantFolders(int64_t aFolderId,
                                 nsTArray<int64_t>& aDescendantFoldersArray);
 
   static const int32_t kGetChildrenIndex_Guid;
   static const int32_t kGetChildrenIndex_Position;
   static const int32_t kGetChildrenIndex_Type;
   static const int32_t kGetChildrenIndex_PlaceID;
+  static const int32_t kGetChildrenIndex_SyncStatus;
+  static const int32_t kGetChildrenIndex_Syncable;
 
   static mozilla::Atomic<int64_t> sLastInsertedItemId;
   static void StoreLastInsertedId(const nsACString& aTable,
                                   const int64_t aLastInsertedId);
 
 private:
   static nsNavBookmarks* gBookmarksService;
 
@@ -261,16 +270,44 @@ private:
    */
   nsresult FetchFolderInfo(int64_t aFolderId,
                            int32_t* _folderCount,
                            nsACString& _guid,
                            int64_t* _parentId);
 
   nsresult GetLastChildId(int64_t aFolder, int64_t* aItemId);
 
+  nsresult AddSyncChangesForBookmarksWithURL(const nsACString& aURL,
+                                             int64_t aSyncChangeDelta);
+
+  // Bumps the change counter for all bookmarks with |aURI|. This is used to
+  // update tagged bookmarks when adding or changing a tag entry.
+  nsresult AddSyncChangesForBookmarksWithURI(nsIURI* aURI,
+                                             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);
+
+  // Inserts tombstones for removed synced items.
+  nsresult InsertTombstones(const nsTArray<TombstoneData>& aTombstones);
+
+  // Removes a stale synced bookmark tombstone.
+  nsresult RemoveTombstone(const nsACString& aGUID);
+
+  nsresult SetItemTitleInternal(BookmarkData& aBookmark,
+                                const nsACString& aTitle,
+                                int64_t aSyncChangeDelta);
+
+  bool MatchesSyncable(int64_t aItemId, int32_t aSyncable);
+
   /**
    * This is an handle to the Places database.
    */
   RefPtr<mozilla::places::Database> mDB;
 
   int32_t mItemCount;
 
   nsMaybeWeakPtrArray<nsINavBookmarkObserver> mObservers;
@@ -286,16 +323,17 @@ private:
     return aFolderId == mRoot || aFolderId == mMenuRoot ||
            aFolderId == mTagsRoot || aFolderId == mUnfiledRoot ||
            aFolderId == mToolbarRoot || aFolderId == mMobileRoot;
   }
 
   nsresult IsBookmarkedInDatabase(int64_t aBookmarkID, bool* aIsBookmarked);
 
   nsresult SetItemDateInternal(enum mozilla::places::BookmarkDate aDateType,
+                               int64_t aSyncChangeDelta,
                                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);

--- a/toolkit/components/places/nsTaggingService.js
+++ b/toolkit/components/places/nsTaggingService.js
@@ -149,23 +149,29 @@ TaggingService.prototype = {
 
     let taggingFunction = () => {
       for (let tag of tags) {
         if (tag.id == -1) {
           // Tag does not exist yet, create it.
           this._createTag(tag.name, aSource);
         }
 
-        if (this._getItemIdForTaggedURI(aURI, tag.name) == -1) {
+        let itemId = this._getItemIdForTaggedURI(aURI, tag.name);
+        if (itemId == -1) {
           // The provided URI is not yet tagged, add a tag for it.
           // Note that bookmarks under tag containers must have null titles.
           PlacesUtils.bookmarks.insertBookmark(
             tag.id, aURI, PlacesUtils.bookmarks.DEFAULT_INDEX,
             /* aTitle */ null, /* aGuid */ null, aSource
           );
+        } else {
+          // Otherwise, bump the tag's timestamp, so that we can increment the
+          // sync change counter for all bookmarks with the URI.
+          PlacesUtils.bookmarks.setItemLastModified(itemId,
+            PlacesUtils.toPRTime(Date.now()), aSource);
         }
 
         // Try to preserve user's tag name casing.
         // Rename the tag container so the Places view matches the most-recent
         // user-typed value.
         if (PlacesUtils.bookmarks.getItemTitle(tag.id) != tag.name) {
           // this._tagFolders is updated by the bookmarks observer.
           PlacesUtils.bookmarks.setItemTitle(tag.id, tag.name, aSource);

new file mode 100644
--- /dev/null
+++ b/toolkit/components/places/tests/bookmarks/test_sync_fields.js
@@ -0,0 +1,387 @@
+/* Any copyright is dedicated to the Public Domain.
+   http://creativecommons.org/publicdomain/zero/1.0/ */
+
+// 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();
+  }
+
+  *_getCounter(guid) {
+    let fields = yield PlacesTestUtils.fetchBookmarkSyncFields(guid);
+    if (!fields.length) {
+      throw new Error(`Item ${guid} does not exist`);
+    }
+    return fields[0].syncChangeCounter;
+  }
+
+  // Call this after creating a new bookmark.
+  *track(guid, name, expectedInitial = 1) {
+    if (this.tracked.has(guid)) {
+      throw new Error(`Already tracking item ${guid}`);
+    }
+    let initial = yield* this._getCounter(guid);
+    Assert.equal(initial, expectedInitial, `Initial value of item '${name}' is correct`);
+    this.tracked.set(guid, { 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 ${JSON.stringify(expectedToIncrement)}`);
+    for (let [guid, entry] of this.tracked) {
+      let { name, value } = entry;
+      let newValue = yield* this._getCounter(guid);
+      let desc = `record '${name}' (guid=${guid})`;
+      if (expectedToIncrement.includes(guid)) {
+        // 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(guid, { name, value: newValue });
+      } else {
+        Assert.equal(newValue, value, `${desc} was NOT expected to increment`);
+      }
+    }
+  }
+}
+
+function* checkSyncFields(guid, expected) {
+  let results = yield PlacesTestUtils.fetchBookmarkSyncFields(guid);
+  if (!results.length) {
+    throw new Error(`Missing sync fields for ${guid}`);
+  }
+  for (let name in expected) {
+    let expectedValue = expected[name];
+    Assert.equal(results[0][name], expectedValue, `field ${name} matches item ${guid}`);
+  }
+}
+
+// Common test cases for sync field changes.
+class TestCases {
+  *run() {
+    do_print("Test 1: inserts, updates, tags, and keywords");
+    try {
+      yield* this.testChanges();
+    } finally {
+      do_print("Reset sync fields after test 1");
+      yield PlacesTestUtils.markBookmarksAsSynced();
+    }
+
+    do_print("Test 2: reparenting");
+    try {
+      yield* this.testReparenting();
+    } finally {
+      do_print("Reset sync fields after test 2");
+      yield PlacesTestUtils.markBookmarksAsSynced();
+    }
+  }
+
+  *testChanges() {
+    let testUri = NetUtil.newURI("http://test.mozilla.org");
+
+    let guid = yield* this.insertBookmark(PlacesUtils.bookmarks.unfiledGuid,
+                                          testUri,
+                                          PlacesUtils.bookmarks.DEFAULT_INDEX,
+                                          "bookmark title");
+    do_print(`Inserted bookmark ${guid}`);
+    yield* checkSyncFields(guid, { syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NEW,
+                                   syncChangeCounter: 1 });
+
+    // Pretend Sync just did whatever it does
+    yield PlacesTestUtils.setBookmarkSyncFields({ guid,
+                                                  syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NORMAL });
+    do_print(`Updated sync status of ${guid}`);
+    yield* checkSyncFields(guid, { syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NORMAL,
+                                   syncChangeCounter: 1 });
+
+    // update it - it should increment the change counter
+    yield* this.setTitle(guid, "new title");
+    do_print(`Changed title of ${guid}`);
+    yield* checkSyncFields(guid, { syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NORMAL,
+                                   syncChangeCounter: 2 });
+
+    yield* this.setAnno(guid, "random-anno", "random-value");
+    do_print(`Set anno on ${guid}`);
+    yield* checkSyncFields(guid, { syncChangeCounter: 3 });
+
+    // Tagging a bookmark should update its change counter.
+    yield* this.tagURI(testUri, ["test-tag"]);
+    do_print(`Tagged bookmark ${guid}`);
+    yield* checkSyncFields(guid, { syncChangeCounter: 4 });
+
+    yield* this.setKeyword(guid, "keyword");
+    do_print(`Set keyword for bookmark ${guid}`);
+    yield* checkSyncFields(guid, { syncChangeCounter: 5 });
+
+    yield* this.removeKeyword(guid, "keyword");
+    do_print(`Removed keyword from bookmark ${guid}`);
+    yield* checkSyncFields(guid, { syncChangeCounter: 6 });
+  }
+
+  *testReparenting() {
+    let counterTracker = new CounterTracker();
+
+    let folder1 = yield* this.createFolder(PlacesUtils.bookmarks.unfiledGuid,
+                                           "folder1",
+                                           PlacesUtils.bookmarks.DEFAULT_INDEX);
+    do_print(`Created the first folder, guid is ${folder1}`);
+
+    // New folder should have a change recorded.
+    yield* counterTracker.track(folder1, "folder 1");
+
+    // Put a new bookmark in the folder.
+    let testUri = NetUtil.newURI("http://test2.mozilla.org");
+    let child1 = yield* this.insertBookmark(folder1,
+                                            testUri,
+                                            PlacesUtils.bookmarks.DEFAULT_INDEX,
+                                            "bookmark 1");
+    do_print(`Created a new bookmark into ${folder1}, guid is ${child1}`);
+    // both the folder and the child should have a change recorded.
+    yield* counterTracker.track(child1, "child 1");
+    yield* 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 = yield* this.insertBookmark(folder1,
+                                            testUri,
+                                            0,
+                                            "bookmark 2");
+    do_print(`Created a second new bookmark into folder ${folder1}, guid is ${child2}`);
+
+    yield* counterTracker.track(child2, "child 2");
+    yield* 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.
+    yield* this.moveItem(child1, folder1, 0);
+    yield* counterTracker.check(folder1);
+
+    // Another folder to play with.
+    let folder2 = yield* this.createFolder(PlacesUtils.bookmarks.unfiledGuid,
+                                           "folder2",
+                                           PlacesUtils.bookmarks.DEFAULT_INDEX);
+    do_print(`Created a second new folder, guid is ${folder2}`);
+    yield* counterTracker.track(folder2, "folder 2");
+    // nothing else has changed.
+    yield* counterTracker.check();
+
+    // Move one of the children to the new folder.
+    do_print(`Moving bookmark ${child2} from folder ${folder1} to folder ${folder2}`);
+    yield* this.moveItem(child2, folder2, PlacesUtils.bookmarks.DEFAULT_INDEX);
+    // child1 should have no change, everything should have a new change.
+    yield* counterTracker.check(folder1, folder2, child2);
+
+    // Move the new folder to another root.
+    yield* this.moveItem(folder2, PlacesUtils.bookmarks.toolbarGuid,
+                         PlacesUtils.bookmarks.DEFAULT_INDEX);
+    do_print(`Moving folder ${folder2} to toolbar`);
+    yield* counterTracker.check(folder2, PlacesUtils.bookmarks.toolbarGuid,
+                                PlacesUtils.bookmarks.unfiledGuid);
+
+    let child3 = yield* this.insertBookmark(folder2,
+                                            testUri,
+                                            0,
+                                            "bookmark 3");
+    do_print(`Prepended child ${child3} to folder ${folder2}`);
+    yield* counterTracker.check(folder2, child3);
+
+    // Reordering should only track the parent.
+    yield* this.reorder(folder2, [child2, child3]);
+    do_print(`Reorder children of ${folder2}`);
+    yield* counterTracker.check(folder2);
+
+    // All fields still have a syncStatus of SYNC_STATUS_NEW - so deleting them
+    // should *not* cause any deleted items to be written.
+    yield* this.removeItem(folder1);
+    Assert.equal((yield PlacesTestUtils.fetchSyncTombstones()).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 PlacesTestUtils.setBookmarkSyncFields({ guid: folder2,
+                                                  syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NORMAL });
+    yield PlacesTestUtils.setBookmarkSyncFields({ guid: child2,
+                                                  syncStatus: PlacesUtils.bookmarks.SYNC_STATUS.NORMAL });
+    yield* this.removeItem(folder2);
+    let tombstones = yield PlacesTestUtils.fetchSyncTombstones();
+    let tombstoneGuids = sortBy(tombstones, "guid").map(({ guid }) => guid);
+    Assert.equal(tombstoneGuids.length, 2);
+    Assert.deepEqual(tombstoneGuids, [folder2, child2].sort(compareAscending));
+  }
+
+  // Annos don't have an async API, so we use the sync API for both tests.
+  *setAnno(guid, name, value) {
+    let id = yield PlacesUtils.promiseItemId(guid);
+    PlacesUtils.annotations.setItemAnnotation(id, name, value, 0,
+                                              PlacesUtils.annotations.EXPIRE_NEVER);
+  }
+}
+
+// Exercises the legacy, synchronous `nsINavBookmarksService` calls implemented
+// in C++.
+class SyncTestCases extends TestCases {
+  *createFolder(parentGuid, title, index) {
+    let parentId = yield PlacesUtils.promiseItemId(parentGuid);
+    let id = PlacesUtils.bookmarks.createFolder(parentId, title, index);
+    return yield PlacesUtils.promiseItemGuid(id);
+  }
+
+  *insertBookmark(parentGuid, uri, index, title) {
+    let parentId = yield PlacesUtils.promiseItemId(parentGuid);
+    let id = PlacesUtils.bookmarks.insertBookmark(parentId, uri, index, title);
+    return yield PlacesUtils.promiseItemGuid(id);
+  }
+
+  *moveItem(guid, newParentGuid, index) {
+    let id = yield PlacesUtils.promiseItemId(guid);
+    let newParentId = yield PlacesUtils.promiseItemId(newParentGuid);
+    PlacesUtils.bookmarks.moveItem(id, newParentId, index);
+  }
+
+  *removeItem(guid) {
+    let id = yield PlacesUtils.promiseItemId(guid);
+    PlacesUtils.bookmarks.removeItem(id);
+  }
+
+  *setTitle(guid, title) {
+    let id = yield PlacesUtils.promiseItemId(guid);
+    PlacesUtils.bookmarks.setItemTitle(id, title);
+  }
+
+  *setKeyword(guid, keyword) {
+    let id = yield PlacesUtils.promiseItemId(guid);
+    PlacesUtils.bookmarks.setKeywordForBookmark(id, keyword);
+  }
+
+  *removeKeyword(guid, keyword) {
+    let id = yield PlacesUtils.promiseItemId(guid);
+    if (PlacesUtils.bookmarks.getKeywordForBookmark(id) != keyword) {
+      throw new Error(`Keyword ${keyword} not set for bookmark ${guid}`);
+    }
+    PlacesUtils.bookmarks.setKeywordForBookmark(id, "");
+  }
+
+  *tagURI(uri, tags) {
+    PlacesUtils.tagging.tagURI(uri, tags);
+  }
+
+  *reorder(parentGuid, childGuids) {
+    let parentId = yield PlacesUtils.promiseItemId(parentGuid);
+    for (let index = 0; index < childGuids.length; ++index) {
+      let id = yield PlacesUtils.promiseItemId(childGuids[index]);
+      PlacesUtils.bookmarks.moveItem(id, parentId, index);
+    }
+  }
+}
+
+function* findTagFolder(tag) {
+  let db = yield PlacesUtils.promiseDBConnection()
+  let results = yield db.executeCached(`
+  SELECT guid
+  FROM moz_bookmarks
+  WHERE type = :type AND
+        parent = :tagsFolderId AND
+        title = :tag`,
+  { type: PlacesUtils.bookmarks.TYPE_FOLDER,
+    tagsFolderId: PlacesUtils.tagsFolderId, tag });
+  return results.length ? results[0].getResultByName("guid") : null;
+}
+
+// Exercises the new, async calls implemented in `Bookmarks.jsm`.
+class AsyncTestCases extends TestCases {
+  *createFolder(parentGuid, title, index) {
+    let item = yield PlacesUtils.bookmarks.insert({
+      type: PlacesUtils.bookmarks.TYPE_FOLDER,
+      parentGuid,
+      title,
+      index,
+    });
+    return item.guid;
+  }
+
+  *insertBookmark(parentGuid, uri, index, title) {
+    let item = yield PlacesUtils.bookmarks.insert({
+      parentGuid,
+      url: uri,
+      index,
+      title,
+    });
+    return item.guid;
+  }
+
+  *moveItem(guid, newParentGuid, index) {
+    yield PlacesUtils.bookmarks.update({
+      guid,
+      parentGuid: newParentGuid,
+      index,
+    });
+  }
+
+  *removeItem(guid) {
+    yield PlacesUtils.bookmarks.remove(guid);
+  }
+
+  *setTitle(guid, title) {
+    yield PlacesUtils.bookmarks.update({ guid, title });
+  }
+
+  *setKeyword(guid, keyword) {
+    let item = yield PlacesUtils.bookmarks.fetch(guid);
+    if (!item) {
+      throw new Error(`Cannot set keyword ${
+        keyword} on nonexistent bookmark ${guid}`);
+    }
+    yield PlacesUtils.keywords.insert({ keyword, url: item.url });
+  }
+
+  *removeKeyword(guid, keyword) {
+    let item = yield PlacesUtils.bookmarks.fetch(guid);
+    if (!item) {
+      throw new Error(`Cannot remove keyword ${
+        keyword} from nonexistent bookmark ${guid}`);
+    }
+    let entry = yield PlacesUtils.keywords.fetch({ keyword, url: item.url });
+    if (!entry) {
+      throw new Error(`Keyword ${keyword} not set on bookmark ${guid}`);
+    }
+    yield PlacesUtils.keywords.remove(entry);
+  }
+
+  // There's no async API for tags, but the `PlacesUtils.bookmarks` methods are
+  // tag-aware, and should bump the change counters for tagged bookmarks when
+  // called directly.
+  *tagURI(uri, tags) {
+    for (let tag of tags) {
+      let tagFolderGuid = yield findTagFolder(tag);
+      if (!tagFolderGuid) {
+        let tagFolder = yield PlacesUtils.bookmarks.insert({
+          type: PlacesUtils.bookmarks.TYPE_FOLDER,
+          parentGuid: PlacesUtils.bookmarks.tagsGuid,
+          title: tag,
+        });
+        tagFolderGuid = tagFolder.guid;
+      }
+      yield PlacesUtils.bookmarks.insert({
+        url: uri,
+        parentGuid: tagFolderGuid,
+      });
+    }
+  }
+
+  *reorder(parentGuid, childGuids) {
+    yield PlacesUtils.bookmarks.reorder(parentGuid, childGuids);
+  }
+}
+
+add_task(function* test_sync_api() {
+  let tests = new SyncTestCases();
+  yield* tests.run();
+});
+
+add_task(function* test_async_api() {
+  let tests = new AsyncTestCases();
+  yield* tests.run();
+});

--- a/toolkit/components/places/tests/bookmarks/xpcshell.ini
+++ b/toolkit/components/places/tests/bookmarks/xpcshell.ini
@@ -43,8 +43,9 @@ skip-if = toolkit == 'android' || toolki
 [test_changeBookmarkURI.js]
 [test_getBookmarkedURIFor.js]
 [test_keywords.js]
 [test_nsINavBookmarkObserver.js]
 [test_protectRoots.js]
 [test_removeFolderTransaction_reinsert.js]
 [test_removeItem.js]
 [test_savedsearches.js]
+[test_sync_fields.js]

--- a/toolkit/components/places/tests/head_common.js
+++ b/toolkit/components/places/tests/head_common.js
@@ -863,8 +863,22 @@ function* foreign_count(url) {
     url = url.spec;
   let db = yield PlacesUtils.promiseDBConnection();
   let rows = yield db.executeCached(
     `SELECT foreign_count FROM moz_places
      WHERE url_hash = hash(:url) AND url = :url
     `, { url });
   return rows.length == 0 ? 0 : rows[0].getResultByName("foreign_count");
 }
+
+function compareAscending(a, b) {
+  if (a > b) {
+    return 1;
+  }
+  if (a < b) {
+    return -1;
+  }
+  return 0;
+}
+
+function sortBy(array, prop) {
+  return array.sort((a, b) => compareAscending(a[prop], b[prop]));
+}

--- a/toolkit/components/places/tests/unit/test_sync_utils.js
+++ b/toolkit/components/places/tests/unit/test_sync_utils.js
@@ -40,26 +40,16 @@ function shuffle(array) {
   for (let i = 0; i < array.length; ++i) {
     let randomIndex = Math.floor(Math.random() * (i + 1));
     results[i] = results[randomIndex];
     results[randomIndex] = array[i];
   }
   return results;
 }
 
-function compareAscending(a, b) {
-  if (a > b) {
-    return 1;
-  }
-  if (a < b) {
-    return -1;
-  }
-  return 0;
-}
-
 function assertTagForURLs(tag, urls, message) {
   let taggedURLs = PlacesUtils.tagging.getURIsForTag(tag).map(uri => uri.spec);
   deepEqual(taggedURLs.sort(compareAscending), urls.sort(compareAscending), message);
 }
 
 function assertURLHasTags(url, tags, message) {
   let actualTags = PlacesUtils.tagging.getTagsForURI(uri(url));
   deepEqual(actualTags.sort(compareAscending), tags, message);