--- a/services/sync/modules/bookmark_utils.js
+++ b/services/sync/modules/bookmark_utils.js
@@ -4,29 +4,50 @@
 
 "use strict";
 
 this.EXPORTED_SYMBOLS = ["BookmarkSpecialIds", "BookmarkAnnos"];
 
 const { utils: Cu, interfaces: Ci, classes: Cc } = Components;
 
 Cu.import("resource://gre/modules/PlacesUtils.jsm");
+Cu.import("resource://gre/modules/XPCOMUtils.jsm");
+Cu.import("resource://services-common/async.js");
 
 let BookmarkAnnos = {
   ALLBOOKMARKS_ANNO:    "AllBookmarks",
   DESCRIPTION_ANNO:     "bookmarkProperties/description",
   SIDEBAR_ANNO:         "bookmarkProperties/loadInSidebar",
   MOBILEROOT_ANNO:      "mobile/bookmarksRoot",
   MOBILE_ANNO:          "MobileBookmarks",
   EXCLUDEBACKUP_ANNO:   "places/excludeFromBackup",
   SMART_BOOKMARKS_ANNO: "Places/SmartBookmark",
   PARENT_ANNO:          "sync/parent",
   ORGANIZERQUERY_ANNO:  "PlacesOrganizer/OrganizerQuery",
 };
 
+// Accessing `PlacesUtils.bookmarks` initializes the bookmarks service, which,
+// in turn, initializes the database and upgrades the schema as a side effect.
+// This causes Sync unit tests that exercise older database formats to fail,
+// so we define this map as a lazy getter.
+XPCOMUtils.defineLazyGetter(this, "SpecialGUIDToPlacesGUID", () => {
+  return {
+    "menu": PlacesUtils.bookmarks.menuGuid,
+    "places": PlacesUtils.bookmarks.rootGuid,
+    "tags": PlacesUtils.bookmarks.tagsGuid,
+    "toolbar": PlacesUtils.bookmarks.toolbarGuid,
+    "unfiled": PlacesUtils.bookmarks.unfiledGuid,
+
+    get mobile() {
+      let mobileRootId = BookmarkSpecialIds.findMobileRoot(true);
+      return Async.promiseSpinningly(PlacesUtils.promiseItemGuid(mobileRootId));
+    },
+  };
+});
+
 let BookmarkSpecialIds = {
 
   // Special IDs. Note that mobile can attempt to create a record on
   // dereference; special accessors are provided to prevent recursion within
   // observers.
   guids: ["menu", "places", "tags", "toolbar", "unfiled", "mobile"],
 
   // Create the special mobile folder to store mobile bookmarks.
@@ -68,16 +89,20 @@ let BookmarkSpecialIds = {
   // Don't bother creating mobile: if it doesn't exist, this ID can't be it!
   specialGUIDForId: function specialGUIDForId(id) {
     for (let guid of this.guids)
       if (this.specialIdForGUID(guid, false) == id)
         return guid;
     return null;
   },
 
+  syncIDToPlacesGUID(g) {
+    return g in SpecialGUIDToPlacesGUID ? SpecialGUIDToPlacesGUID[g] : g;
+  },
+
   get menu() {
     return PlacesUtils.bookmarksMenuFolderId;
   },
   get places() {
     return PlacesUtils.placesRootId;
   },
   get tags() {
     return PlacesUtils.tagsFolderId;

--- a/services/sync/modules/engines/bookmarks.js
+++ b/services/sync/modules/engines/bookmarks.js
@@ -6,32 +6,46 @@ this.EXPORTED_SYMBOLS = ['BookmarksEngin
                          "BookmarkFolder", "BookmarkQuery",
                          "Livemark", "BookmarkSeparator"];
 
 var Cc = Components.classes;
 var Ci = Components.interfaces;
 var Cu = Components.utils;
 
 Cu.import("resource://gre/modules/PlacesUtils.jsm");
+Cu.import("resource://gre/modules/PlacesSyncUtils.jsm");
 Cu.import("resource://gre/modules/XPCOMUtils.jsm");
 Cu.import("resource://services-common/async.js");
 Cu.import("resource://services-sync/constants.js");
 Cu.import("resource://services-sync/engines.js");
 Cu.import("resource://services-sync/record.js");
 Cu.import("resource://services-sync/util.js");
 Cu.import("resource://services-sync/bookmark_utils.js");
 Cu.import("resource://gre/modules/Task.jsm");
 Cu.import("resource://gre/modules/PlacesBackups.jsm");
 
 const ANNOS_TO_TRACK = [BookmarkAnnos.DESCRIPTION_ANNO, BookmarkAnnos.SIDEBAR_ANNO,
                         PlacesUtils.LMANNO_FEEDURI, PlacesUtils.LMANNO_SITEURI];
 
 const SERVICE_NOT_SUPPORTED = "Service not supported on this platform";
 const FOLDER_SORTINDEX = 1000000;
 
+// Maps Sync record property names to `PlacesSyncUtils` bookmark properties.
+const RECORD_PROPS_TO_BOOKMARK_PROPS = {
+  title: "title",
+  bmkUri: "url",
+  tags: "tags",
+  keyword: "keyword",
+  description: "description",
+  loadInSidebar: "loadInSidebar",
+  queryId: "query",
+  siteUri: "site",
+  feedUri: "feed",
+};
+
 this.PlacesItem = function PlacesItem(collection, id, type) {
   CryptoWrapper.call(this, collection, id);
   this.type = type || "item";
 }
 PlacesItem.prototype = {
   decrypt: function PlacesItem_decrypt(keyBundle) {
     // Do the normal CryptoWrapper decrypt, but change types before returning
     let clear = CryptoWrapper.prototype.decrypt.call(this, keyBundle);
@@ -439,75 +453,17 @@ function BookmarksStore(name, engine) {
   }, this);
 }
 BookmarksStore.prototype = {
   __proto__: Store.prototype,
 
   itemExists: function BStore_itemExists(id) {
     return this.idForGUID(id, true) > 0;
   },
-  
-  /*
-   * If the record is a tag query, rewrite it to refer to the local tag ID.
-   * 
-   * Otherwise, just return.
-   */
-  preprocessTagQuery: function preprocessTagQuery(record) {
-    if (record.type != "query" ||
-        record.bmkUri == null ||
-        !record.folderName)
-      return;
-    
-    // Yes, this works without chopping off the "place:" prefix.
-    let uri           = record.bmkUri
-    let queriesRef    = {};
-    let queryCountRef = {};
-    let optionsRef    = {};
-    PlacesUtils.history.queryStringToQueries(uri, queriesRef, queryCountRef,
-                                             optionsRef);
-    
-    // We only process tag URIs.
-    if (optionsRef.value.resultType != optionsRef.value.RESULTS_AS_TAG_CONTENTS)
-      return;
-    
-    // Tag something to ensure that the tag exists.
-    let tag = record.folderName;
-    let dummyURI = Utils.makeURI("about:weave#BStore_preprocess");
-    PlacesUtils.tagging.tagURI(dummyURI, [tag]);
 
-    // Look for the id of the tag, which might just have been added.
-    let tags = this._getNode(PlacesUtils.tagsFolderId);
-    if (!(tags instanceof Ci.nsINavHistoryQueryResultNode)) {
-      this._log.debug("tags isn't an nsINavHistoryQueryResultNode; aborting.");
-      return;
-    }
-
-    tags.containerOpen = true;
-    try {
-      for (let i = 0; i < tags.childCount; i++) {
-        let child = tags.getChild(i);
-        if (child.title == tag) {
-          // Found the tag, so fix up the query to use the right id.
-          this._log.debug("Tag query folder: " + tag + " = " + child.itemId);
-          
-          this._log.trace("Replacing folders in: " + uri);
-          for (let q of queriesRef.value)
-            q.setFolders([child.itemId], 1);
-          
-          record.bmkUri = PlacesUtils.history.queriesToQueryString(
-            queriesRef.value, queryCountRef.value, optionsRef.value);
-          return;
-        }
-      }
-    }
-    finally {
-      tags.containerOpen = false;
-    }
-  },
-  
   applyIncoming: function BStore_applyIncoming(record) {
     this._log.debug("Applying record " + record.id);
     let isSpecial = record.id in BookmarkSpecialIds;
 
     if (record.deleted) {
       if (isSpecial) {
         this._log.warn("Ignoring deletion for special record " + record.id);
         return;
@@ -528,415 +484,172 @@ BookmarksStore.prototype = {
 
     // Skip malformed records. (Bug 806460.)
     if (record.type == "query" &&
         !record.bmkUri) {
       this._log.warn("Skipping malformed query bookmark: " + record.id);
       return;
     }
 
-    // Preprocess the record before doing the normal apply.
-    this.preprocessTagQuery(record);
-
     // Figure out the local id of the parent GUID if available
     let parentGUID = record.parentid;
     if (!parentGUID) {
       throw "Record " + record.id + " has invalid parentid: " + parentGUID;
     }
     this._log.debug("Local parent is " + parentGUID);
 
-    let parentId = this.idForGUID(parentGUID);
-    if (parentId > 0) {
-      // Save the parent id for modifying the bookmark later
-      record._parent = parentId;
-      record._orphan = false;
-      this._log.debug("Record " + record.id + " is not an orphan.");
-    } else {
-      this._log.trace("Record " + record.id +
-                      " is an orphan: could not find parent " + parentGUID);
-      record._orphan = true;
-    }
-
     // Do the normal processing of incoming records
     Store.prototype.applyIncoming.call(this, record);
 
-    // Do some post-processing if we have an item
-    let itemId = this.idForGUID(record.id);
-    if (itemId > 0) {
-      // Move any children that are looking for this folder as a parent
-      if (record.type == "folder") {
-        this._reparentOrphans(itemId);
-        // Reorder children later
-        if (record.children)
-          this._childrenToOrder[record.id] = record.children;
-      }
-
-      // Create an annotation to remember that it needs reparenting.
-      if (record._orphan) {
-        PlacesUtils.annotations.setItemAnnotation(
-          itemId, BookmarkAnnos.PARENT_ANNO, parentGUID, 0,
-          PlacesUtils.annotations.EXPIRE_NEVER);
-      }
-    }
-  },
-
-  /**
-   * Find all ids of items that have a given value for an annotation
-   */
-  _findAnnoItems: function BStore__findAnnoItems(anno, val) {
-    return PlacesUtils.annotations.getItemsWithAnnotation(anno, {})
-                      .filter(function(id) {
-      return PlacesUtils.annotations.getItemAnnotation(id, anno) == val;
-    });
-  },
-
-  /**
-   * For the provided parent item, attach its children to it
-   */
-  _reparentOrphans: function _reparentOrphans(parentId) {
-    // Find orphans and reunite with this folder parent
-    let parentGUID = this.GUIDForId(parentId);
-    let orphans = this._findAnnoItems(BookmarkAnnos.PARENT_ANNO, parentGUID);
-
-    this._log.debug("Reparenting orphans " + orphans + " to " + parentId);
-    orphans.forEach(function(orphan) {
-      // Move the orphan to the parent and drop the missing parent annotation
-      if (this._reparentItem(orphan, parentId)) {
-        PlacesUtils.annotations.removeItemAnnotation(orphan, BookmarkAnnos.PARENT_ANNO);
-      }
-    }, this);
-  },
-
-  _reparentItem: function _reparentItem(itemId, parentId) {
-    this._log.trace("Attempting to move item " + itemId + " to new parent " +
-                    parentId);
-    try {
-      if (parentId > 0) {
-        PlacesUtils.bookmarks.moveItem(itemId, parentId,
-                                       PlacesUtils.bookmarks.DEFAULT_INDEX);
-        return true;
-      }
-    } catch(ex) {
-      this._log.debug("Failed to reparent item", ex);
-    }
-    return false;
-  },
-
-  // Turn a record's nsINavBookmarksService constant and other attributes into
-  // a granular type for comparison.
-  _recordType: function _recordType(itemId) {
-    let bms  = PlacesUtils.bookmarks;
-    let type = bms.getItemType(itemId);
-
-    switch (type) {
-      case bms.TYPE_FOLDER:
-        if (PlacesUtils.annotations
-                       .itemHasAnnotation(itemId, PlacesUtils.LMANNO_FEEDURI)) {
-          return "livemark";
-        }
-        return "folder";
-
-      case bms.TYPE_BOOKMARK:
-        let bmkUri = bms.getBookmarkURI(itemId).spec;
-        if (bmkUri.indexOf("place:") == 0) {
-          return "query";
-        }
-        return "bookmark";
-
-      case bms.TYPE_SEPARATOR:
-        return "separator";
-
-      default:
-        return null;
+    if (record.type == "folder" && record.children) {
+      this._childrenToOrder[record.id] = record.children;
     }
   },
 
   create: function BStore_create(record) {
-    // Default to unfiled if we don't have the parent yet.
-    
-    // Valid parent IDs are all positive integers. Other values -- undefined,
-    // null, -1 -- all compare false for > 0, so this catches them all. We
-    // don't just use <= without the !, because undefined and null compare
-    // false for that, too!
-    if (!(record._parent > 0)) {
-      this._log.debug("Parent is " + record._parent + "; reparenting to unfiled.");
-      record._parent = BookmarkSpecialIds.unfiled;
-    }
-
     switch (record.type) {
     case "bookmark":
     case "query":
     case "microsummary": {
-      let uri = Utils.makeURI(record.bmkUri);
-      let newId = PlacesUtils.bookmarks.insertBookmark(
-        record._parent, uri, PlacesUtils.bookmarks.DEFAULT_INDEX, record.title,
-        record.id);
-      this._log.debug("created bookmark " + newId + " under " + record._parent
-                      + " as " + record.title + " " + record.bmkUri);
-
-      // Smart bookmark annotations are strings.
+      let info = {
+        kind: record.type,
+        url: record.bmkUri,
+        parentGuid: BookmarkSpecialIds.syncIDToPlacesGUID(record.parentid),
+        title: record.title,
+        guid: BookmarkSpecialIds.syncIDToPlacesGUID(record.id),
+        tags: record.tags,
+        keyword: record.keyword,
+      };
+      if (record.loadInSidebar) {
+        info.loadInSidebar = record.loadInSidebar;
+      }
       if (record.queryId) {
-        PlacesUtils.annotations.setItemAnnotation(
-          newId, BookmarkAnnos.SMART_BOOKMARKS_ANNO, record.queryId, 0,
-          PlacesUtils.annotations.EXPIRE_NEVER);
+        info.query = record.queryId;
+      }
+      if (record.folderName) {
+        info.folder = record.folderName;
+      }
+      if (record.description) {
+        info.description = record.description;
       }
 
-      if (Array.isArray(record.tags)) {
-        this._tagURI(uri, record.tags);
-      }
-      PlacesUtils.bookmarks.setKeywordForBookmark(newId, record.keyword);
-      if (record.description) {
-        PlacesUtils.annotations.setItemAnnotation(
-          newId, BookmarkAnnos.DESCRIPTION_ANNO, record.description, 0,
-          PlacesUtils.annotations.EXPIRE_NEVER);
-      }
-
-      if (record.loadInSidebar) {
-        PlacesUtils.annotations.setItemAnnotation(
-          newId, BookmarkAnnos.SIDEBAR_ANNO, true, 0,
-          PlacesUtils.annotations.EXPIRE_NEVER);
-      }
+      let bmk = Async.promiseSpinningly(PlacesSyncUtils.bookmarks.insert(info));
+      this._log.debug("created bookmark " + bmk.guid + " under " + bmk.parentGuid
+                      + " as " + bmk.title + " " + bmk.url.href);
 
     } break;
     case "folder": {
-      let newId = PlacesUtils.bookmarks.createFolder(
-        record._parent, record.title, PlacesUtils.bookmarks.DEFAULT_INDEX,
-        record.id);
-      this._log.debug("created folder " + newId + " under " + record._parent
-                      + " as " + record.title);
+      let info = {
+        kind: PlacesSyncUtils.bookmarks.KIND_FOLDER,
+        parentGuid: BookmarkSpecialIds.syncIDToPlacesGUID(record.parentid),
+        guid: BookmarkSpecialIds.syncIDToPlacesGUID(record.id),
+        title: record.title,
+      };
+      if (record.description) {
+        info.description = record.description;
+      }
 
-      if (record.description) {
-        PlacesUtils.annotations.setItemAnnotation(
-          newId, BookmarkAnnos.DESCRIPTION_ANNO, record.description, 0,
-          PlacesUtils.annotations.EXPIRE_NEVER);
-      }
+      let folder = Async.promiseSpinningly(PlacesSyncUtils.bookmarks.insert(info));
+      this._log.debug("created folder " + folder.guid + " under " + folder.parentGuid
+                      + " as " + folder.title);
 
       // record.children will be dealt with in _orderChildren.
     } break;
     case "livemark":
-      let siteURI = null;
       if (!record.feedUri) {
         this._log.debug("No feed URI: skipping livemark record " + record.id);
         return;
       }
-      if (PlacesUtils.annotations
-                     .itemHasAnnotation(record._parent, PlacesUtils.LMANNO_FEEDURI)) {
-        this._log.debug("Invalid parent: skipping livemark record " + record.id);
-        return;
+      let info = {
+        kind: PlacesSyncUtils.bookmarks.KIND_LIVEMARK,
+        title: record.title,
+        parentGuid: BookmarkSpecialIds.syncIDToPlacesGUID(record.parentid),
+        feed: record.feedUri,
+        site: record.siteUri,
+        guid: BookmarkSpecialIds.syncIDToPlacesGUID(record.id),
+      };
+      let livemark = Async.promiseSpinningly(PlacesSyncUtils.bookmarks.insert(info));
+      if (livemark) {
+        this._log.debug("Created livemark " + livemark.id + " under " +
+                        livemark.parentId + " as " + livemark.title +
+                        ", " + livemark.siteURI.spec + ", " +
+                        livemark.feedURI.spec + ", GUID " +
+                        livemark.guid);
       }
-
-      if (record.siteUri != null)
-        siteURI = Utils.makeURI(record.siteUri);
-
-      // Until this engine can handle asynchronous error reporting, we need to
-      // detect errors on creation synchronously.
-      let spinningCb = Async.makeSpinningCallback();
-
-      let livemarkObj = {title: record.title,
-                         parentId: record._parent,
-                         index: PlacesUtils.bookmarks.DEFAULT_INDEX,
-                         feedURI: Utils.makeURI(record.feedUri),
-                         siteURI: siteURI,
-                         guid: record.id};
-      PlacesUtils.livemarks.addLivemark(livemarkObj).then(
-        aLivemark => { spinningCb(null, [Components.results.NS_OK, aLivemark]) },
-        ex => {
-          this._log.error("creating livemark failed: " + ex);
-          spinningCb(null, [Components.results.NS_ERROR_UNEXPECTED, null])
-        }
-      );
-
-      let [status, livemark] = spinningCb.wait();
-      if (!Components.isSuccessCode(status)) {
-        throw status;
-      }
-
-      this._log.debug("Created livemark " + livemark.id + " under " +
-                      livemark.parentId + " as " + livemark.title +
-                      ", " + livemark.siteURI.spec + ", " +
-                      livemark.feedURI.spec + ", GUID " +
-                      livemark.guid);
       break;
     case "separator": {
-      let newId = PlacesUtils.bookmarks.insertSeparator(
-        record._parent, PlacesUtils.bookmarks.DEFAULT_INDEX, record.id);
-      this._log.debug("created separator " + newId + " under " + record._parent);
+      let separator = Async.promiseSpinningly(PlacesSyncUtils.bookmarks.insert({
+        kind: PlacesSyncUtils.bookmarks.KIND_SEPARATOR,
+        parentGuid: BookmarkSpecialIds.syncIDToPlacesGUID(record.parentid),
+        guid: BookmarkSpecialIds.syncIDToPlacesGUID(record.id),
+      }));
+      this._log.debug("created separator " + separator.guid + " under " + separator.parentGuid);
     } break;
     case "item":
       this._log.debug(" -> got a generic places item.. do nothing?");
       return;
     default:
       this._log.error("_create: Unknown item type: " + record.type);
       return;
     }
-
-  },
-
-  // Factored out of `remove` to avoid redundant DB queries when the Places ID
-  // is already known.
-  removeById: function removeById(itemId, guid) {
-    let type = PlacesUtils.bookmarks.getItemType(itemId);
-
-    switch (type) {
-    case PlacesUtils.bookmarks.TYPE_BOOKMARK:
-      this._log.debug("  -> removing bookmark " + guid);
-      PlacesUtils.bookmarks.removeItem(itemId);
-      break;
-    case PlacesUtils.bookmarks.TYPE_FOLDER:
-      this._log.debug("  -> removing folder " + guid);
-      PlacesUtils.bookmarks.removeItem(itemId);
-      break;
-    case PlacesUtils.bookmarks.TYPE_SEPARATOR:
-      this._log.debug("  -> removing separator " + guid);
-      PlacesUtils.bookmarks.removeItem(itemId);
-      break;
-    default:
-      this._log.error("remove: Unknown item type: " + type);
-      break;
-    }
   },
 
   remove: function BStore_remove(record) {
     if (BookmarkSpecialIds.isSpecialGUID(record.id)) {
       this._log.warn("Refusing to remove special folder " + record.id);
       return;
     }
 
-    let itemId = this.idForGUID(record.id);
-    if (itemId <= 0) {
+    let guid = BookmarkSpecialIds.syncIDToPlacesGUID(record.id);
+    let ok = Async.promiseSpinningly(PlacesSyncUtils.bookmarks.remove(guid));
+    if (!ok) {
       this._log.debug("Item " + record.id + " already removed");
-      return;
     }
-    this.removeById(itemId, record.id);
-  },
-
-  _taggableTypes: ["bookmark", "microsummary", "query"],
-  isTaggable: function isTaggable(recordType) {
-    return this._taggableTypes.indexOf(recordType) != -1;
   },
 
   update: function BStore_update(record) {
-    let itemId = this.idForGUID(record.id);
-
-    if (itemId <= 0) {
-      this._log.debug("Skipping update for unknown item: " + record.id);
-      return;
-    }
+    let info = {
+      parentGuid: BookmarkSpecialIds.syncIDToPlacesGUID(record.parentid),
+      guid: BookmarkSpecialIds.syncIDToPlacesGUID(record.id),
+      kind: record.type,
+    };
 
-    // Two items are the same type if they have the same ItemType in Places,
-    // and also share some key characteristics (e.g., both being livemarks).
-    // We figure this out by examining the item to find the equivalent granular
-    // (string) type.
-    // If they're not the same type, we can't just update attributes. Delete
-    // then recreate the record instead.
-    let localItemType    = this._recordType(itemId);
-    let remoteRecordType = record.type;
-    this._log.trace("Local type: " + localItemType + ". " +
-                    "Remote type: " + remoteRecordType + ".");
-
-    if (localItemType != remoteRecordType) {
-      this._log.debug("Local record and remote record differ in type. " +
-                      "Deleting and recreating.");
-      this.removeById(itemId, record.id);
-      this.create(record);
-      return;
-    }
-
-    this._log.trace("Updating " + record.id + " (" + itemId + ")");
-
-    // Move the bookmark to a new parent or new position if necessary
-    if (record._parent > 0 &&
-        PlacesUtils.bookmarks.getFolderIdForItem(itemId) != record._parent) {
-      this._reparentItem(itemId, record._parent);
+    for (let prop of Object.keys(RECORD_PROPS_TO_BOOKMARK_PROPS)) {
+      let bmkProp = RECORD_PROPS_TO_BOOKMARK_PROPS[prop];
+      if (prop in record.cleartext) {
+        info[bmkProp] = record.cleartext[prop];
+      }
     }
 
-    for (let [key, val] in Iterator(record.cleartext)) {
-      switch (key) {
-      case "title":
-        PlacesUtils.bookmarks.setItemTitle(itemId, val);
-        break;
-      case "bmkUri":
-        PlacesUtils.bookmarks.changeBookmarkURI(itemId, Utils.makeURI(val));
-        break;
-      case "tags":
-        if (Array.isArray(val)) {
-          if (this.isTaggable(remoteRecordType)) {
-            this._tagID(itemId, val);
-          } else {
-            this._log.debug("Remote record type is invalid for tags: " + remoteRecordType);
-          }
-        }
-        break;
-      case "keyword":
-        PlacesUtils.bookmarks.setKeywordForBookmark(itemId, val);
-        break;
-      case "description":
-        if (val) {
-          PlacesUtils.annotations.setItemAnnotation(
-            itemId, BookmarkAnnos.DESCRIPTION_ANNO, val, 0,
-            PlacesUtils.annotations.EXPIRE_NEVER);
-        } else {
-          PlacesUtils.annotations.removeItemAnnotation(itemId, BookmarkAnnos.DESCRIPTION_ANNO);
-        }
-        break;
-      case "loadInSidebar":
-        if (val) {
-          PlacesUtils.annotations.setItemAnnotation(
-            itemId, BookmarkAnnos.SIDEBAR_ANNO, true, 0,
-            PlacesUtils.annotations.EXPIRE_NEVER);
-        } else {
-          PlacesUtils.annotations.removeItemAnnotation(itemId, BookmarkAnnos.SIDEBAR_ANNO);
-        }
-        break;
-      case "queryId":
-        PlacesUtils.annotations.setItemAnnotation(
-          itemId, BookmarkAnnos.SMART_BOOKMARKS_ANNO, val, 0,
-          PlacesUtils.annotations.EXPIRE_NEVER);
-        break;
-      }
-    }
+    let bmk = Async.promiseSpinningly(PlacesSyncUtils.bookmarks.update(info));
+    this._log.debug("updated bookmark " + bmk.guid + " under " + bmk.parentGuid);
   },
 
   _orderChildren: function _orderChildren() {
-    for (let [guid, children] in Iterator(this._childrenToOrder)) {
-      // Reorder children according to the GUID list. Gracefully deal
-      // with missing items, e.g. locally deleted.
-      let delta = 0;
-      let parent = null;
-      for (let idx = 0; idx < children.length; idx++) {
-        let itemid = this.idForGUID(children[idx]);
-        if (itemid == -1) {
-          delta += 1;
-          this._log.trace("Could not locate record " + children[idx]);
-          continue;
-        }
-        try {
-          // This code path could be optimized by caching the parent earlier.
-          // Doing so should take in count any edge case due to reparenting
-          // or parent invalidations though.
-          if (!parent) {
-            parent = PlacesUtils.bookmarks.getFolderIdForItem(itemid);
-          }
-          PlacesUtils.bookmarks.moveItem(itemid, parent, idx - delta);
-        } catch (ex) {
-          this._log.debug("Could not move item " + children[idx] + ": " + ex);
-        }
+    let promises = Object.keys(this._childrenToOrder).map(syncID => {
+      let children = this._childrenToOrder[syncID];
+      if (!children.length) {
+        return Promise.resolve();
       }
-    }
+      let guid = BookmarkSpecialIds.syncIDToPlacesGUID(syncID);
+      let childGUIDs = children.map(syncID => BookmarkSpecialIds.syncIDToPlacesGUID(syncID));
+      return PlacesSyncUtils.bookmarks.order(guid, childGUIDs).catch(ex => {
+        this._log.debug(`Could not order children for ${guid}: ${ex}`);
+      });
+    });
+    Async.promiseSpinningly(Promise.all(promises));
   },
 
   changeItemID: function BStore_changeItemID(oldID, newID) {
     this._log.debug("Changing GUID " + oldID + " to " + newID);
 
-    // Make sure there's an item to change GUIDs
-    let itemId = this.idForGUID(oldID);
-    if (itemId <= 0)
-      return;
-
-    this._setGUID(itemId, newID);
+    Async.promiseSpinningly(PlacesSyncUtils.bookmarks.changeGuid(
+      BookmarkSpecialIds.syncIDToPlacesGUID(oldID),
+      BookmarkSpecialIds.syncIDToPlacesGUID(newID)
+    ));
   },
 
   _getNode: function BStore__getNode(folder) {
     let query = PlacesUtils.history.getNewQuery();
     query.setFolders([folder], 1);
     return PlacesUtils.history.executeQuery(
       query, PlacesUtils.history.getNewQueryOptions()).root;
   },
@@ -1094,78 +807,44 @@ BookmarksStore.prototype = {
     return this._getStmt(
         "SELECT frecency " +
         "FROM moz_places " +
         "WHERE url_hash = hash(:url) AND url = :url " +
         "LIMIT 1");
   },
   _frecencyCols: ["frecency"],
 
-  get _setGUIDStm() {
-    return this._getStmt(
-      "UPDATE moz_bookmarks " +
-      "SET guid = :guid " +
-      "WHERE id = :item_id");
-  },
-
-  // Some helper functions to handle GUIDs
-  _setGUID: function _setGUID(id, guid) {
-    if (!guid)
-      guid = Utils.makeGUID();
-
-    let stmt = this._setGUIDStm;
-    stmt.params.guid = guid;
-    stmt.params.item_id = id;
-    Async.querySpinningly(stmt);
-    PlacesUtils.invalidateCachedGuidFor(id);
-    return guid;
-  },
-
-  get _guidForIdStm() {
-    return this._getStmt(
-      "SELECT guid " +
-      "FROM moz_bookmarks " +
-      "WHERE id = :item_id");
-  },
-  _guidForIdCols: ["guid"],
-
   GUIDForId: function GUIDForId(id) {
     let special = BookmarkSpecialIds.specialGUIDForId(id);
     if (special)
       return special;
 
-    let stmt = this._guidForIdStm;
-    stmt.params.item_id = id;
-
-    // Use the existing GUID if it exists
-    let result = Async.querySpinningly(stmt, this._guidForIdCols)[0];
-    if (result && result.guid)
-      return result.guid;
-
-    // Give the uri a GUID if it doesn't have one
-    return this._setGUID(id);
+    return Async.promiseSpinningly(
+      PlacesSyncUtils.bookmarks.ensureGuidForId(id));
   },
 
   get _idForGUIDStm() {
     return this._getStmt(
       "SELECT id AS item_id " +
       "FROM moz_bookmarks " +
       "WHERE guid = :guid");
   },
   _idForGUIDCols: ["item_id"],
 
   // noCreate is provided as an optional argument to prevent the creation of
   // non-existent special records, such as "mobile".
   idForGUID: function idForGUID(guid, noCreate) {
+    // guid might be a String object rather than a string.
+    guid = guid.toString();
+
     if (BookmarkSpecialIds.isSpecialGUID(guid))
       return BookmarkSpecialIds.specialIdForGUID(guid, !noCreate);
 
     let stmt = this._idForGUIDStm;
-    // guid might be a String object rather than a string.
-    stmt.params.guid = guid.toString();
+    stmt.params.guid = guid;
 
     let results = Async.querySpinningly(stmt, this._idForGUIDCols);
     this._log.trace("Number of rows matching GUID " + guid + ": "
                     + results.length);
     
     // Here's the one we care about: the first.
     let result = results[0];
     
@@ -1222,58 +901,16 @@ BookmarksStore.prototype = {
       finally {
         node.containerOpen = false;
       }
     }
 
     return items;
   },
 
-  /**
-   * Associates the URI of the item with the provided ID with the
-   * provided array of tags.
-   * If the provided ID does not identify an item with a URI,
-   * returns immediately.
-   */
-  _tagID: function _tagID(itemID, tags) {
-    if (!itemID || !tags) {
-      return;
-    }
-
-    try {
-      let u = PlacesUtils.bookmarks.getBookmarkURI(itemID);
-      this._tagURI(u, tags);
-    } catch (e) {
-      this._log.warn(`Got exception fetching URI for ${itemID} not tagging`, e);
-
-      // I guess it doesn't have a URI. Don't try to tag it.
-      return;
-    }
-  },
-
-  /**
-   * Associate the provided URI with the provided array of tags.
-   * If the provided URI is falsy, returns immediately.
-   */
-  _tagURI: function _tagURI(bookmarkURI, tags) {
-    if (!bookmarkURI || !tags) {
-      return;
-    }
-
-    // Filter out any null/undefined/empty tags.
-    tags = tags.filter(t => t);
-
-    // Temporarily tag a dummy URI to preserve tag ids when untagging.
-    let dummyURI = Utils.makeURI("about:weave#BStore_tagURI");
-    PlacesUtils.tagging.tagURI(dummyURI, tags);
-    PlacesUtils.tagging.untagURI(bookmarkURI, null);
-    PlacesUtils.tagging.tagURI(bookmarkURI, tags);
-    PlacesUtils.tagging.untagURI(dummyURI, null);
-  },
-
   getAllIDs: function BStore_getAllIDs() {
     let items = {"menu": true,
                  "toolbar": true,
                  "unfiled": true,
                 };
     // We also want "mobile" but only if a local mobile folder already exists
     // (otherwise we'll later end up creating it, which we want to avoid until
     // we actually need it.)
@@ -1287,21 +924,24 @@ BookmarksStore.prototype = {
     return items;
   },
 
   wipe: function BStore_wipe() {
     let cb = Async.makeSpinningCallback();
     Task.spawn(function* () {
       // Save a backup before clearing out all bookmarks.
       yield PlacesBackups.create(null, true);
-      for (let guid of BookmarkSpecialIds.guids)
-        if (guid != "places") {
-          let id = BookmarkSpecialIds.specialIdForGUID(guid);
-          if (id)
-            PlacesUtils.bookmarks.removeFolderChildren(id);
+      // Instead of exposing a "clear folder" method, we should instead have
+      // `PlacesSyncUtils` clear all roots. `eraseEverything` comes close,
+      // but doesn't clear the mobile root. The fix is to move mobile root
+      // and query handling into Places.
+      for (let syncID of BookmarkSpecialIds.guids)
+        if (syncID != "places") {
+          let guid = BookmarkSpecialIds.syncIDToPlacesGUID(syncID);
+          yield PlacesSyncUtils.bookmarks.clear(guid);
         }
       cb();
     });
     cb.wait();
   }
 };
 
 function BookmarksTracker(name, engine) {

--- a/services/sync/tests/unit/test_bookmark_engine.js
+++ b/services/sync/tests/unit/test_bookmark_engine.js
@@ -1,17 +1,19 @@
 /* Any copyright is dedicated to the Public Domain.
    http://creativecommons.org/publicdomain/zero/1.0/ */
 
 Cu.import("resource://gre/modules/PlacesUtils.jsm");
+Cu.import("resource://gre/modules/PlacesSyncUtils.jsm");
 Cu.import("resource://gre/modules/BookmarkJSONUtils.jsm");
 Cu.import("resource://services-common/async.js");
 Cu.import("resource://gre/modules/Log.jsm");
 Cu.import("resource://services-sync/engines.js");
 Cu.import("resource://services-sync/engines/bookmarks.js");
+Cu.import("resource://services-sync/bookmark_utils.js");
 Cu.import("resource://services-sync/service.js");
 Cu.import("resource://services-sync/util.js");
 Cu.import("resource://testing-common/services/sync/utils.js");
 Cu.import("resource://gre/modules/Promise.jsm");
 
 initTestLogging("Trace");
 
 Service.engineManager.register(BookmarksEngine);
@@ -56,17 +58,19 @@ add_test(function test_ID_caching() {
 
   _("Ensure that Places IDs are not cached.");
   let engine = new BookmarksEngine(Service);
   let store = engine._store;
   _("All IDs: " + JSON.stringify(store.getAllIDs()));
 
   let mobileID = store.idForGUID("mobile");
   _("Change the GUID for that item, and drop the mobile anno.");
-  store._setGUID(mobileID, "abcdefghijkl");
+  let mobileRoot = BookmarkSpecialIds.specialIdForGUID("mobile", false);
+  let mobileGUID = Async.promiseSpinningly(PlacesUtils.promiseItemGuid(mobileRoot));
+  Async.promiseSpinningly(PlacesSyncUtils.bookmarks.changeGuid(mobileGUID, "abcdefghijkl"));
   PlacesUtils.annotations.removeItemAnnotation(mobileID, "mobile/bookmarksRoot");
 
   let err;
   let newMobileID;
 
   // With noCreate, we don't find an entry.
   try {
     newMobileID = store.idForGUID("mobile", true);
@@ -317,45 +321,47 @@ add_test(function test_mismatched_types(
   let oldRecord = {
     "id": "l1nZZXfB8nC7",
     "type":"folder",
     "parentName":"Bookmarks Toolbar",
     "title":"Innerst i Sneglehode",
     "description":null,
     "parentid": "toolbar"
   };
+  oldRecord.cleartext = oldRecord;
 
   let newRecord = {
     "id": "l1nZZXfB8nC7",
     "type":"livemark",
     "siteUri":"http://sneglehode.wordpress.com/",
     "feedUri":"http://sneglehode.wordpress.com/feed/",
     "parentName":"Bookmarks Toolbar",
     "title":"Innerst i Sneglehode",
     "description":null,
     "children":
       ["HCRq40Rnxhrd", "YeyWCV1RVsYw", "GCceVZMhvMbP", "sYi2hevdArlF",
        "vjbZlPlSyGY8", "UtjUhVyrpeG6", "rVq8WMG2wfZI", "Lx0tcy43ZKhZ",
        "oT74WwV8_j4P", "IztsItWVSo3-"],
     "parentid": "toolbar"
   };
+  newRecord.cleartext = newRecord;
 
   let engine = new BookmarksEngine(Service);
   let store  = engine._store;
   let server = serverForFoo(engine);
   new SyncTestingInfrastructure(server.server);
 
   _("GUID: " + store.GUIDForId(6, true));
 
   try {
     let bms = PlacesUtils.bookmarks;
     let oldR = new FakeRecord(BookmarkFolder, oldRecord);
     let newR = new FakeRecord(Livemark, newRecord);
-    oldR._parent = PlacesUtils.bookmarks.toolbarFolder;
-    newR._parent = PlacesUtils.bookmarks.toolbarFolder;
+    oldR.parentid = PlacesUtils.bookmarks.toolbarGuid;
+    newR.parentid = PlacesUtils.bookmarks.toolbarGuid;
 
     store.applyIncoming(oldR);
     _("Applied old. It's a folder.");
     let oldID = store.idForGUID(oldR.id);
     _("Old ID: " + oldID);
     do_check_eq(bms.getItemType(oldID), bms.TYPE_FOLDER);
     do_check_false(PlacesUtils.annotations
                               .itemHasAnnotation(oldID, PlacesUtils.LMANNO_FEEDURI));
@@ -424,64 +430,16 @@ add_test(function test_bookmark_guidMap_
     err = ex;
   }
   do_check_eq(err, "Nooo");
 
   PlacesUtils.promiseBookmarksTree = pbt;
   server.stop(run_next_test);
 });
 
-add_test(function test_bookmark_is_taggable() {
-  let engine = new BookmarksEngine(Service);
-  let store = engine._store;
-
-  do_check_true(store.isTaggable("bookmark"));
-  do_check_true(store.isTaggable("microsummary"));
-  do_check_true(store.isTaggable("query"));
-  do_check_false(store.isTaggable("folder"));
-  do_check_false(store.isTaggable("livemark"));
-  do_check_false(store.isTaggable(null));
-  do_check_false(store.isTaggable(undefined));
-  do_check_false(store.isTaggable(""));
-
-  run_next_test();
-});
-
-add_test(function test_bookmark_tag_but_no_uri() {
-  _("Ensure that a bookmark record with tags, but no URI, doesn't throw an exception.");
-
-  let engine = new BookmarksEngine(Service);
-  let store = engine._store;
-
-  // We're simply checking that no exception is thrown, so
-  // no actual checks in this test.
-
-  store._tagURI(null, ["foo"]);
-  store._tagURI(null, null);
-  store._tagURI(Utils.makeURI("about:fake"), null);
-
-  let record = {
-    _parent:     PlacesUtils.bookmarks.toolbarFolder,
-    id:          Utils.makeGUID(),
-    description: "",
-    tags:        ["foo"],
-    title:       "Taggy tag",
-    type:        "folder"
-  };
-
-  // Because update() walks the cleartext.
-  record.cleartext = record;
-
-  store.create(record);
-  record.tags = ["bar"];
-  store.update(record);
-
-  run_next_test();
-});
-
 add_test(function test_misreconciled_root() {
   _("Ensure that we don't reconcile an arbitrary record with a root.");
 
   let engine = new BookmarksEngine(Service);
   let store = engine._store;
   let server = serverForFoo(engine);
 
   // Log real hard for this test.

--- a/services/sync/tests/unit/test_bookmark_livemarks.js
+++ b/services/sync/tests/unit/test_bookmark_livemarks.js
@@ -98,46 +98,37 @@ add_test(function test_livemark_descript
                                             PlacesUtils.annotations.EXPIRE_NEVER);
 
   run_next_test();
 });
 
 add_test(function test_livemark_invalid() {
   _("Livemarks considered invalid by nsLivemarkService are skipped.");
 
-  _("Parent is 0, which is invalid. Will be set to unfiled.");
-  let noParentRec = makeLivemark(record631361.payload, true);
-  noParentRec._parent = 0;
-  store.create(noParentRec);
-  let recID = store.idForGUID(noParentRec.id, true);
-  do_check_true(recID > 0);
-  do_check_eq(PlacesUtils.bookmarks.getFolderIdForItem(recID), PlacesUtils.bookmarks.unfiledBookmarksFolder);
-
   _("Parent is unknown. Will be set to unfiled.");
   let lateParentRec = makeLivemark(record631361.payload, true);
   let parentGUID = Utils.makeGUID();
   lateParentRec.parentid = parentGUID;
-  lateParentRec._parent = store.idForGUID(parentGUID);   // Usually done by applyIncoming.
-  do_check_eq(-1, lateParentRec._parent);
+  do_check_eq(-1, store.idForGUID(parentGUID));
 
   store.create(lateParentRec);
   recID = store.idForGUID(lateParentRec.id, true);
   do_check_true(recID > 0);
   do_check_eq(PlacesUtils.bookmarks.getFolderIdForItem(recID),
               PlacesUtils.bookmarks.unfiledBookmarksFolder);
 
   _("No feed URI, which is invalid. Will be skipped.");
   let noFeedURIRec = makeLivemark(record631361.payload, true);
   delete noFeedURIRec.cleartext.feedUri;
   store.create(noFeedURIRec);
   // No exception, but no creation occurs.
   do_check_eq(-1, store.idForGUID(noFeedURIRec.id, true));
 
   _("Parent is a Livemark. Will be skipped.");
   let lmParentRec = makeLivemark(record631361.payload, true);
-  lmParentRec._parent = recID;
+  lmParentRec.parentid = store.GUIDForId(recID);
   store.create(lmParentRec);
   // No exception, but no creation occurs.
   do_check_eq(-1, store.idForGUID(lmParentRec.id, true));
 
   // Clear event loop.
   Utils.nextTick(run_next_test);
 });

--- a/services/sync/tests/unit/test_bookmark_order.js
+++ b/services/sync/tests/unit/test_bookmark_order.js
@@ -12,22 +12,38 @@ function getBookmarks(folderId) {
 
   let pos = 0;
   while (true) {
     let itemId = PlacesUtils.bookmarks.getIdForItemAt(folderId, pos);
     _("Got itemId", itemId, "under", folderId, "at", pos);
     if (itemId == -1)
       break;
 
+    let isOrphan = PlacesUtils.annotations.itemHasAnnotation(itemId,
+      "sync/parent");
     switch (PlacesUtils.bookmarks.getItemType(itemId)) {
       case PlacesUtils.bookmarks.TYPE_BOOKMARK:
-        bookmarks.push(PlacesUtils.bookmarks.getItemTitle(itemId));
+        let title = PlacesUtils.bookmarks.getItemTitle(itemId);
+        if (isOrphan) {
+          let requestedParent = PlacesUtils.annotations.getItemAnnotation(
+            itemId, "sync/parent");
+          bookmarks.push({ title, requestedParent });
+        } else {
+          bookmarks.push(title);
+        }
         break;
       case PlacesUtils.bookmarks.TYPE_FOLDER:
-        bookmarks.push(getBookmarks(itemId));
+        let titles = getBookmarks(itemId);
+        if (isOrphan) {
+          let requestedParent = PlacesUtils.annotations.getItemAnnotation(
+            itemId, "sync/parent");
+          bookmarks.push({ titles, requestedParent });
+        } else {
+          bookmarks.push(titles);
+        }
         break;
       default:
         _("Unsupported item type..");
     }
 
     pos++;
   }
 
@@ -91,23 +107,24 @@ function run_test() {
   let f30 = folder(id30, "", [id31]);
   apply(f30);
   check([id10, id20, [id31]]);
 
   let id41 = "41_aaaaaaaaa";
   let id40 = "f40_aaaaaaaa";
   _("insert missing parent -> append to unfiled");
   apply(bookmark(id41, id40));
-  check([id10, id20, [id31], id41]);
+  check([id10, id20, [id31], { title: id41, requestedParent: id40 }]);
 
   let id42 = "42_aaaaaaaaa";
 
   _("insert another missing parent -> append");
   apply(bookmark(id42, id40));
-  check([id10, id20, [id31], id41, id42]);
+  check([id10, id20, [id31], { title: id41, requestedParent: id40 },
+    { title: id42, requestedParent: id40 }]);
 
   _("insert folder -> move children and followers");
   let f40 = folder(id40, "", [id41, id42]);
   apply(f40);
   check([id10, id20, [id31], [id41, id42]]);
 
   _("Moving 41 behind 42 -> update f40");
   f40.children = [id42, id41];

--- a/services/sync/tests/unit/test_bookmark_places_query_rewriting.js
+++ b/services/sync/tests/unit/test_bookmark_places_query_rewriting.js
@@ -5,47 +5,53 @@
 Cu.import("resource://gre/modules/PlacesUtils.jsm");
 Cu.import("resource://services-sync/engines/bookmarks.js");
 Cu.import("resource://services-sync/service.js");
 Cu.import("resource://services-sync/util.js");
 
 var engine = new BookmarksEngine(Service);
 var store = engine._store;
 
+function makeTagRecord(id, uri) {
+  let tagRecord = new BookmarkQuery("bookmarks", id);
+  tagRecord.queryId = "MagicTags";
+  tagRecord.parentName = "Bookmarks Toolbar";
+  tagRecord.bmkUri = uri;
+  tagRecord.title = "tagtag";
+  tagRecord.folderName = "bar";
+  tagRecord.parentid = PlacesUtils.bookmarks.toolbarGuid;
+  return tagRecord;
+}
+
 function run_test() {
   initTestLogging("Trace");
   Log.repository.getLogger("Sync.Engine.Bookmarks").level = Log.Level.Trace;
   Log.repository.getLogger("Sync.Store.Bookmarks").level = Log.Level.Trace;
 
-  let tagRecord = new BookmarkQuery("bookmarks", "abcdefabcdef");
   let uri = "place:folder=499&type=7&queryType=1";
-  tagRecord.queryId = "MagicTags";
-  tagRecord.parentName = "Bookmarks Toolbar";
-  tagRecord.bmkUri = uri;
-  tagRecord.title = "tagtag";
-  tagRecord.folderName = "bar";
+  let tagRecord = makeTagRecord("abcdefabcdef", uri);
 
   _("Type: " + tagRecord.type);
   _("Folder name: " + tagRecord.folderName);
-  store.preprocessTagQuery(tagRecord);
-
-  _("Verify that the URI has been rewritten.");
-  do_check_neq(tagRecord.bmkUri, uri);
+  store.applyIncoming(tagRecord);
 
   let tags = store._getNode(PlacesUtils.tagsFolderId);
   tags.containerOpen = true;
   let tagID;
   for (let i = 0; i < tags.childCount; ++i) {
     let child = tags.getChild(i);
     if (child.title == "bar")
       tagID = child.itemId;
   }
   tags.containerOpen = false;
 
   _("Tag ID: " + tagID);
-  do_check_eq(tagRecord.bmkUri, uri.replace("499", tagID));
+  let insertedRecord = store.createRecord("abcdefabcdef", "bookmarks");
+  do_check_eq(insertedRecord.bmkUri, uri.replace("499", tagID));
 
   _("... but not if the type is wrong.");
   let wrongTypeURI = "place:folder=499&type=2&queryType=1";
-  tagRecord.bmkUri = wrongTypeURI;
-  store.preprocessTagQuery(tagRecord);
-  do_check_eq(tagRecord.bmkUri, wrongTypeURI);
+  let wrongTypeRecord = makeTagRecord("fedcbafedcba", wrongTypeURI);
+  store.applyIncoming(wrongTypeRecord);
+
+  insertedRecord = store.createRecord("fedcbafedcba", "bookmarks");
+  do_check_eq(insertedRecord.bmkUri, wrongTypeURI);
 }

--- a/toolkit/modules/Sqlite.jsm
+++ b/toolkit/modules/Sqlite.jsm
@@ -799,17 +799,17 @@ ConnectionData.prototype = Object.freeze
               deferred.resolve(result);
             } else {
               deferred.reject(new Error("Statement was cancelled."));
             }
 
             break;
 
           case Ci.mozIStorageStatementCallback.REASON_ERROR:
-            let error = new Error("Error(s) encountered during statement execution: " + errors.map(e => e.message).join(", "));
+            let error = new Error("Error(s) encountered during statement " + index + " execution: " + errors.map(e => e.message).join(", "));
             error.errors = errors;
             deferred.reject(error);
             break;
 
           default:
             deferred.reject(new Error("Unknown completion reason code: " +
                                       reason));
             break;