Bug 1363995 - Implement autofill record reconciliation. draft
authorKit Cambridge <kit@yakshaving.ninja>
Wed, 14 Jun 2017 12:58:33 +1000
changeset 600701 274049f6f47d18398079b4aaef5d01ab47ee117c
parent 600700 23ae55958dc431888e170b10e3f1062779c8c0c4
child 635069 54c22f6ad8c45736a68586c75ca5da0d5c4f61e6
push id65844
push userbmo:kit@mozilla.com
push dateTue, 27 Jun 2017 18:57:45 +0000
bugs1363995
milestone56.0a1
Bug 1363995 - Implement autofill record reconciliation. This patch ignores cross-version migrations for now, and adds basic three-way merging and forking that should handle most common scenarios. We can figure out how to handle these later, once we have some concrete changes we'd like to make. I suspect modifying a record from a future version of the add-on won't be safe in the general case. We might need to clone and hide the original record so that it can be edited, then synced, migrated, and deduped on a device that understands the new fields. But it's hard to know without a concrete example, and easy to overengineer. MozReview-Commit-ID: HOkltoWT9eS
browser/extensions/formautofill/FormAutofillSync.jsm
browser/extensions/formautofill/ProfileStorage.jsm
browser/extensions/formautofill/test/unit/head.js
browser/extensions/formautofill/test/unit/test_reconcile.js
browser/extensions/formautofill/test/unit/test_sync.js
browser/extensions/formautofill/test/unit/xpcshell.ini
--- a/browser/extensions/formautofill/FormAutofillSync.jsm
+++ b/browser/extensions/formautofill/FormAutofillSync.jsm
@@ -11,47 +11,26 @@ this.EXPORTED_SYMBOLS = ["AddressesEngin
 Cu.import("resource://gre/modules/Services.jsm");
 Cu.import("resource://gre/modules/XPCOMUtils.jsm");
 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/constants.js");
 Cu.import("resource://services-common/async.js");
 
+XPCOMUtils.defineLazyModuleGetter(this, "Log",
+                                  "resource://gre/modules/Log.jsm");
 XPCOMUtils.defineLazyModuleGetter(this, "profileStorage",
                                   "resource://formautofill/ProfileStorage.jsm");
 
-
-// XXX - this will end up in ProfileStorage - here for a POC (and at the top
-// of the file for eslint)
-function findDuplicateGUID(record) {
-  for (let profile of profileStorage.addresses.getAll()) {
-    let keys = new Set(Object.keys(record));
-    for (let key of Object.keys(profile)) {
-      keys.add(key);
-    }
-    let same = true;
-    for (let key of keys) {
-      if (!same) {
-        break;
-      }
-      if (profile.hasOwnProperty(key) && record.hasOwnProperty(key)) {
-        same = profile[key] == record[key];
-      }
-      // else something smarter, possibly using version field?
-    }
-    if (same) {
-      return profile.guid;
-    }
-  }
-  return null;
-}
-
 // A helper to sanitize address and creditcard records suitable for logging.
 function sanitizeStorageObject(ob) {
+  if (!ob) {
+    return null;
+  }
   const whitelist = ["timeCreated", "timeLastUsed", "timeLastModified"];
   let result = {};
   for (let key of Object.keys(ob)) {
     let origVal = ob[key];
     if (whitelist.includes(key)) {
       result[key] = origVal;
     } else if (typeof origVal == "string") {
       result[key] = "X".repeat(origVal.length);
@@ -69,24 +48,34 @@ const AUTOFILL_TTL = 3 * 365 * 24 * 60 *
 function AutofillRecord(collection, id) {
   CryptoWrapper.call(this, collection, id);
 }
 
 AutofillRecord.prototype = {
   __proto__: CryptoWrapper.prototype,
   ttl: AUTOFILL_TTL,
 
+  toEntry() {
+    this.entry.guid = this.id;
+    return this.entry;
+  },
+
+  fromEntry(entry) {
+    this.id = entry.guid;
+    this.entry = entry;
+    // The GUID is already stored in record.id, so we nuke it from the entry
+    // itself to save a tiny bit of space. The profileStorage clones profiles,
+    // so nuking in-place is OK.
+    delete this.entry.guid;
+  },
+
   cleartextToString() {
     // And a helper so logging a *Sync* record auto sanitizes.
     let record = this.cleartext;
-    let result = {entry: {}};
-    if (record.entry) {
-      result.entry = sanitizeStorageObject(record.entry);
-    }
-    return JSON.stringify(result);
+    return JSON.stringify({entry: sanitizeStorageObject(record.entry)});
   },
 };
 
 // Profile data is stored in the "entry" object of the record.
 Utils.deferGetSet(AutofillRecord, "cleartext", ["entry"]);
 
 function FormAutofillStore(name, engine) {
   Store.call(this, name, engine);
@@ -133,60 +122,63 @@ FormAutofillStore.prototype = {
 
     if (this.itemExists(remoteRecord.id)) {
       // We will never get a tombstone here, so we are updating a real record.
       this._doUpdateRecord(remoteRecord);
       return;
     }
 
     // No matching local record. Try to dedupe a NEW local record.
-    let localDupeID = /* this.storage. */findDuplicateGUID(remoteRecord.entry);
+    let localDupeID = this.storage.findDuplicateGUID(remoteRecord.toEntry());
     if (localDupeID) {
       this._log.trace(`Deduping local record ${localDupeID} to remote`, remoteRecord);
       // Change the local GUID to match the incoming record, then apply the
       // incoming record.
       this.changeItemID(localDupeID, remoteRecord.id);
       this._doUpdateRecord(remoteRecord);
       return;
     }
 
     // We didn't find a dupe, either, so must be a new record (or possibly
-    // a non-deleted version of an item we have a tombstone for, which create()
+    // a non-deleted version of an item we have a tombstone for, which add()
     // handles for us.)
     this._log.trace("Add record", remoteRecord);
-    remoteRecord.entry.guid = remoteRecord.id;
-    this.storage.add(remoteRecord.entry, {sourceSync: true});
+    let entry = remoteRecord.toEntry();
+    this.storage.add(entry, {sourceSync: true});
   },
 
   createRecord(id, collection) {
     this._log.trace("Create record", id);
     let record = new AutofillRecord(collection, id);
-    record.entry = this.storage.get(id, {
+    let entry = this.storage.get(id, {
       noComputedFields: true,
     });
-    if (!record.entry) {
+    if (entry) {
+      record.fromEntry(entry);
+    } else {
       // We should consider getting a more authortative indication it's actually deleted.
       this._log.debug(`Failed to get autofill record with id "${id}", assuming deleted`);
       record.deleted = true;
-    } else {
-      // The GUID is already stored in record.id, so we nuke it from the entry
-      // itself to save a tiny bit of space. The profileStorage clones profiles,
-      // so nuking in-place is OK.
-      delete record.entry.guid;
     }
     return record;
   },
 
   _doUpdateRecord(record) {
     this._log.trace("Update record", record);
 
-    // XXX - until we get reconcilliation logic, this is dangerous - it
-    // unconditionally updates, which may cause DATA LOSS
-    this.storage.update(record.id, record.entry);
-    this._log.debug("Updated local record", record);
+    let entry = record.toEntry();
+    let {forkedGUID} = this.storage.reconcile(entry);
+    if (this._log.level <= Log.Level.Debug) {
+      let forkedRecord = forkedGUID ? this.storage.get(forkedGUID) : null;
+      let reconciledRecord = this.storage.get(record.id);
+      this._log.debug("Updated local record", {
+        forked: sanitizeStorageObject(forkedRecord),
+        updated: sanitizeStorageObject(reconciledRecord),
+      });
+    }
   },
 
   // NOTE: Because we re-implement the incoming/reconcilliation logic we leave
   // the |create|, |remove| and |update| methods undefined - the base
   // implementation throws, which is what we want to happen so we can identify
   // any places they are "accidentally" called.
 };
 
--- a/browser/extensions/formautofill/ProfileStorage.jsm
+++ b/browser/extensions/formautofill/ProfileStorage.jsm
@@ -73,17 +73,20 @@
  *     }
  *   ]
  * }
  *
  * Sync Metadata:
  *
  * Records may also have a _sync field, which consists of:
  * {
- *   changeCounter, // integer - the number of changes made since a last sync.
+ *   changeCounter,    // integer - the number of changes made since the last
+ *                     // sync.
+ *   lastSyncedFields, // object - the original values for fields changed since
+ *                     // the last sync.
  * }
  *
  * Records with such a field have previously been synced. Records without such
  * a field are yet to be synced, so are treated specially in some cases (eg,
  * they don't need a tombstone, de-duping logic treats them as special etc).
  * Records without the field are always considered "dirty" from Sync's POV
  * (meaning they will be synced on the next sync), at which time they will gain
  * this new field.
@@ -117,16 +120,19 @@ XPCOMUtils.defineLazyGetter(this, "REGIO
   let countries = Services.strings.createBundle("chrome://global/locale/regionNames.properties").getSimpleEnumeration();
   while (countries.hasMoreElements()) {
     let country = countries.getNext().QueryInterface(Components.interfaces.nsIPropertyElement);
     regionNames[country.key.toUpperCase()] = country.value;
   }
   return regionNames;
 });
 
+const CryptoHash = Components.Constructor("@mozilla.org/security/hash;1",
+                                          "nsICryptoHash", "initWithString");
+
 const PROFILE_JSON_FILE_NAME = "autofill-profiles.json";
 
 const STORAGE_SCHEMA_VERSION = 1;
 const ADDRESS_SCHEMA_VERSION = 1;
 const CREDIT_CARD_SCHEMA_VERSION = 1;
 
 const VALID_PROFILE_FIELDS = [
   "given-name",
@@ -154,16 +160,27 @@ const INTERNAL_FIELDS = [
   "guid",
   "version",
   "timeCreated",
   "timeLastUsed",
   "timeLastModified",
   "timesUsed",
 ];
 
+function sha256(string) {
+  if (string == null) {
+    return null;
+  }
+  let encoder = new TextEncoder("utf-8");
+  let bytes = encoder.encode(string);
+  let hash = new CryptoHash("sha256");
+  hash.update(bytes, bytes.length);
+  return hash.finish(/* base64 */ true);
+}
+
 /**
  * Class that manipulates records in a specified collection.
  *
  * Note that it is responsible for converting incoming data to a consistent
  * format in the storage. For example, computed fields will be transformed to
  * the original fields and 2-digit years will be calculated into 4 digits.
  */
 class AutofillRecords {
@@ -174,20 +191,21 @@ class AutofillRecords {
    *        An instance of JSONFile.
    * @param {string} collectionName
    *        A key of "store.data".
    * @param {Array.<string>} validFields
    *        A list containing non-metadata field names.
    * @param {number} schemaVersion
    *        The schema version for the new record.
    */
-  constructor(store, collectionName, validFields, schemaVersion) {
+  constructor(store, collectionName, validFields, internalFields, schemaVersion) {
     FormAutofillUtils.defineLazyLogGetter(this, "AutofillRecords:" + collectionName);
 
     this.VALID_FIELDS = validFields;
+    this.INTERNAL_FIELDS = internalFields;
 
     this._store = store;
     this._collectionName = collectionName;
     this._schemaVersion = schemaVersion;
   }
 
   /**
    * Gets the schema version number.
@@ -221,26 +239,22 @@ class AutofillRecords {
       if (index > -1) {
         let existing = this._store.data[this._collectionName][index];
         if (existing.deleted) {
           this._store.data[this._collectionName].splice(index, 1);
         } else {
           throw new Error(`Record ${record.guid} already exists`);
         }
       }
-      let recordToSave = Object.assign({
-        // `timeLastUsed` and `timesUsed` are always local.
-        timeLastUsed: 0,
-        timesUsed: 0,
-      }, record);
+      let recordToSave = this._clone(record);
       return this._saveRecord(recordToSave, {sourceSync});
     }
 
     if (record.deleted) {
-      return this._saveRecord(record, {sourceSync});
+      return this._saveRecord(record);
     }
 
     let recordToSave = this._clone(record);
     this._normalizeRecord(recordToSave);
 
     recordToSave.guid = this._generateGUID();
     recordToSave.version = this.version;
 
@@ -309,38 +323,45 @@ class AutofillRecords {
 
     let recordFound = this._findByGUID(guid);
     if (!recordFound) {
       throw new Error("No matching record.");
     }
 
     let recordToUpdate = this._clone(record);
     this._normalizeRecord(recordToUpdate);
+
     for (let field of this.VALID_FIELDS) {
-      if (recordToUpdate[field] !== undefined) {
-        recordFound[field] = recordToUpdate[field];
+      let oldValue = recordFound[field];
+      let newValue = recordToUpdate[field];
+
+      if (newValue != null) {
+        recordFound[field] = newValue;
       } else {
         delete recordFound[field];
       }
+
+      this._maybeStoreLastSyncedField(recordFound, field, oldValue);
     }
 
     recordFound.timeLastModified = Date.now();
     let syncMetadata = this._getSyncMetaData(recordFound);
     if (syncMetadata) {
       syncMetadata.changeCounter += 1;
     }
 
     this._store.saveSoon();
 
     Services.obs.notifyObservers(null, "formautofill-storage-changed", "update");
   }
 
   /**
    * Notifies the storage of the use of the specified record, so we can update
-   * the metadata accordingly.
+   * the metadata accordingly. This does not bump the Sync change counter, since
+   * we don't sync `timesUsed` or `timeLastUsed`.
    *
    * @param  {string} guid
    *         Indicates which record to be notified.
    */
   notifyUsed(guid) {
     this.log.debug("notifyUsed:", guid);
 
     let recordFound = this._findByGUID(guid);
@@ -400,32 +421,34 @@ class AutofillRecords {
     Services.obs.notifyObservers({wrappedJSObject: {sourceSync}}, "formautofill-storage-changed", "remove");
   }
 
   /**
    * Returns the record with the specified GUID.
    *
    * @param   {string} guid
    *          Indicates which record to retrieve.
+   * @param   {boolean} [options.noComputedFields = false]
+   *          Returns the record without computed fields.
    * @param   {boolean} [options.includePrivateFields = false]
    *          Should fields starting with underscore be included in the result?
    * @returns {Object}
    *          A clone of the record.
    */
-  get(guid, {includePrivateFields = false} = {}) {
+  get(guid, {noComputedFields = false, includePrivateFields = false} = {}) {
     this.log.debug("get:", guid);
 
     let recordFound = this._findByGUID(guid);
     if (!recordFound) {
       return null;
     }
 
     // The record is cloned to avoid accidental modifications from outside.
     let clonedRecord = this._clone(recordFound, {includePrivateFields});
-    this._recordReadProcessor(clonedRecord);
+    this._recordReadProcessor(clonedRecord, {noComputedFields});
     return clonedRecord;
   }
 
   /**
    * Returns all records.
    *
    * @param   {Object} config
    *          Specifies how data will be retrieved.
@@ -474,16 +497,257 @@ class AutofillRecords {
     this.log.debug("getByFilter:", "Returning", result.length, "result(s)");
     return result;
   }
 
   /**
    * Functions intended to be used in the support of Sync.
    */
 
+  /**
+   * Stores the last synced value for a field in a locally updated record. We
+   * use this value to rebuild the shared parent when reconciling incoming
+   * records that may have changed on another device. Storing the value of
+   * the field we last wrote to the Sync server lets us determine if a remote
+   * change conflicts with a local change.
+   *
+   * These fields are not themselves synced, and will be removed locally as
+   * soon as we have successfully written the record to the Sync server - so
+   * it is expected they will not remain for long, as changes which cause a
+   * last synced field to be written will itself cause a sync.
+   *
+   * We also skip this for updates made by Sync, for internal fields, for
+   * records that haven't been uploaded yet, and for fields which have already
+   * been changed since the last sync.
+   *
+   * @param   {Object} record
+   *          The updated local record.
+   * @param   {string} field
+   *          The field name.
+   * @param   {string} lastSyncedValue
+   *          The last synced field value.
+   */
+  _maybeStoreLastSyncedField(record, field, lastSyncedValue) {
+    let isSyncing = "_sync" in record;
+    if (!isSyncing) {
+      return;
+    }
+    let syncMetadata = record._sync;
+    let alreadyChanged = field in syncMetadata.lastSyncedFields;
+    if (alreadyChanged) {
+      return;
+    }
+    let newValue = record[field];
+    if (lastSyncedValue != newValue) {
+      syncMetadata.lastSyncedFields[field] = sha256(lastSyncedValue);
+    }
+  }
+
+  /**
+   * Attempts a three-way merge between a changed local record, an incoming
+   * remote record, and the shared parent that we synthesize from the last
+   * synced fields - see _maybeStoreLastSyncedField.
+   *
+   * @param   {Object} localRecord
+   *          The changed local record, currently in storage.
+   * @param   {Object} remoteRecord
+   *          The remote record.
+   * @returns {Object|null}
+   *          The merged record, or `null` if there are conflicts and the
+   *          records can't be merged.
+   */
+  _mergeSyncedRecords(localRecord, remoteRecord) {
+    let sync = this._getSyncMetaData(localRecord, true);
+
+    // Copy all internal fields from the remote record. We'll update their
+    // values in `_replaceRecordAt`.
+    let mergedRecord = {};
+    for (let field of this.INTERNAL_FIELDS) {
+      if (remoteRecord[field] != null) {
+        mergedRecord[field] = remoteRecord[field];
+      }
+    }
+
+    for (let field of this.VALID_FIELDS) {
+      let isLocalSame = false;
+      let isRemoteSame = false;
+      if (field in sync.lastSyncedFields) {
+        // If the field has changed since the last sync, compare hashes to
+        // determine if the local and remote values are different. Hashing is
+        // expensive, but we don't expect this to happen frequently.
+        let lastSyncedValue = sync.lastSyncedFields[field];
+        isLocalSame = lastSyncedValue == sha256(localRecord[field]);
+        isRemoteSame = lastSyncedValue == sha256(remoteRecord[field]);
+      } else {
+        // Otherwise, if the field hasn't changed since the last sync, we know
+        // it's the same locally.
+        isLocalSame = true;
+        isRemoteSame = localRecord[field] == remoteRecord[field];
+      }
+
+      let value;
+      if (isLocalSame && isRemoteSame) {
+        // Local and remote are the same; doesn't matter which one we pick.
+        value = localRecord[field];
+      } else if (isLocalSame && !isRemoteSame) {
+        value = remoteRecord[field];
+      } else if (!isLocalSame && isRemoteSame) {
+        // We don't need to bump the change counter when taking the local
+        // change, because the counter must already be > 0 if we're attempting
+        // a three-way merge.
+        value = localRecord[field];
+      } else if (localRecord[field] == remoteRecord[field]) {
+        // Shared parent doesn't match either local or remote, but the values
+        // are identical, so there's no conflict.
+        value = localRecord[field];
+      } else {
+        // Both local and remote changed to different values. We'll need to fork
+        // the local record to resolve the conflict.
+        return null;
+      }
+
+      if (value != null) {
+        mergedRecord[field] = value;
+      }
+    }
+
+    return mergedRecord;
+  }
+
+  /**
+   * Replaces a local record with a remote or merged record, copying internal
+   * fields and Sync metadata.
+   *
+   * @param   {number} index
+   * @param   {Object} remoteRecord
+   * @param   ?boolean} [options.keepSyncMetadata = false]
+   *          Should we copy Sync metadata? This is true if `remoteRecord` is a
+   *          merged record with local changes that we need to upload. Passing
+   *          `keepSyncMetadata` retains the record's change counter and
+   *          last synced fields, so that we don't clobber the local change if
+   *          the sync is interrupted after the record is merged, but before
+   *          it's uploaded.
+   * @returns {Object}
+   *          The final merged record.
+   */
+  _replaceRecordAt(index, remoteRecord, {keepSyncMetadata = false} = {}) {
+    let localRecord = this._store.data[this._collectionName][index];
+
+    let timeCreated = localRecord.timeCreated;
+    let timeLastModified = localRecord.timeLastModified;
+
+    let newRecord = this._clone(remoteRecord);
+    this._store.data[this._collectionName][index] = newRecord;
+
+    if (keepSyncMetadata) {
+      // It's safe to move the Sync metadata from the old record to the new
+      // record, since we always clone records when we return them, and we
+      // never hand out references to the metadata object via public methods.
+      newRecord._sync = localRecord._sync;
+    } else {
+      // As a side effect, `_getSyncMetaData` marks the record as syncing if the
+      // existing `localRecord` is a dupe of `remoteRecord`, and we're replacing
+      // local with remote.
+      let sync = this._getSyncMetaData(newRecord, true);
+      sync.changeCounter = 0;
+    }
+
+    if (!newRecord.timeCreated ||
+        localRecord.timeCreated < newRecord.timeCreated) {
+      newRecord.timeCreated = localRecord.timeCreated;
+    }
+
+    if (!newRecord.timeLastModified ||
+        localRecord.timeLastModified > newRecord.timeLastModified) {
+      newRecord.timeLastModified = localRecord.timeLastModified;
+    }
+
+    // Copy local-only fields from the existing local record.
+    for (let field of ["timeLastUsed", "timesUsed"]) {
+      if (localRecord[field] != null) {
+        newRecord[field] = localRecord[field];
+      }
+    }
+  }
+
+  /**
+   * Clones a local record, giving the clone a new GUID and Sync metadata. The
+   * original record remains unchanged in storage.
+   *
+   * @param   {Object} localRecord
+   *          The local record.
+   * @returns {string}
+   *          The GUID of the cloned record.
+   */
+  _forkLocalRecord(localRecord) {
+    let forkedLocalRecord = this._clone(localRecord);
+    forkedLocalRecord.guid = this._generateGUID();
+    this._store.data[this._collectionName].push(forkedLocalRecord);
+
+    let sync = this._getSyncMetaData(forkedLocalRecord, true);
+    sync.changeCounter++;
+
+    return forkedLocalRecord;
+  }
+
+  /**
+   * Reconciles an incoming remote record into the matching local record. This
+   * method is only used by Sync; other callers should use `merge`.
+   *
+   * @param   {Object} remoteRecord
+   *          The incoming record.
+   * @returns {Object}
+   *          A `{forkedGUID}` tuple. `forkedGUID` is `null` if the merge
+   *          succeeded without conflicts, or a new GUID referencing the
+   *          existing locally modified record if the conflicts could not be
+   *          resolved.
+   */
+  reconcile(remoteRecord) {
+    let localIndex = this._findIndexByGUID(remoteRecord.guid);
+    if (localIndex < 0) {
+      throw new Error(`Record ${remoteRecord.guid} not found`);
+    }
+
+    let localRecord = this._store.data[this._collectionName][localIndex];
+    let sync = this._getSyncMetaData(localRecord, true);
+
+    let forkedGUID = null;
+
+    if (sync.changeCounter === 0) {
+      // Local not modified. Replace local with remote.
+      this._replaceRecordAt(localIndex, remoteRecord, {
+        keepSyncMetadata: false,
+      });
+    } else {
+      let mergedRecord = this._mergeSyncedRecords(localRecord, remoteRecord);
+      if (mergedRecord) {
+        // Local and remote modified, but we were able to merge. Replace the
+        // local record with the merged record.
+        this._replaceRecordAt(localIndex, mergedRecord, {
+          keepSyncMetadata: true,
+        });
+      } else {
+        // Merge conflict. Fork the local record, then replace the original
+        // with the merged record.
+        let forkedLocalRecord = this._forkLocalRecord(localRecord);
+        forkedGUID = forkedLocalRecord.guid;
+        this._replaceRecordAt(localIndex, remoteRecord, {
+          keepSyncMetadata: false,
+        });
+      }
+    }
+
+    this._store.saveSoon();
+    Services.obs.notifyObservers({wrappedJSObject: {
+      sourceSync: true,
+    }}, "formautofill-storage-changed", "reconcile");
+
+    return {forkedGUID};
+  }
+
   _removeSyncedRecord(guid) {
     let index = this._findIndexByGUID(guid, {includeDeleted: true});
     if (index == -1) {
       // Removing a record we don't know about. It may have been synced and
       // removed by another device before we saw it. Store the tombstone in
       // case the server is later wiped and we need to reupload everything.
       let tombstone = {
         guid,
@@ -572,16 +836,21 @@ class AutofillRecords {
       }
       let recordFound = this._findByGUID(guid, {includeDeleted: true});
       if (!recordFound) {
         this.log.warn("No profile found to persist changes for guid " + guid);
         continue;
       }
       let sync = this._getSyncMetaData(recordFound, true);
       sync.changeCounter = Math.max(0, sync.changeCounter - counter);
+      if (sync.changeCounter === 0) {
+        // Clear the shared parent fields once we've uploaded all pending
+        // changes, since the server now matches what we have locally.
+        sync.lastSyncedFields = {};
+      }
     }
     this._store.saveSoon();
   }
 
   /**
    * Reset all sync metadata for all items.
    *
    * This is called when Sync is disconnected from this device. All sync
@@ -626,31 +895,108 @@ class AutofillRecords {
       throw new Error("changeGUID: existing record has already been synced");
     }
 
     profile.guid = newID;
 
     this._store.saveSoon();
   }
 
+  /**
+   * Indicates whether a record has been uploaded to the Sync server. Synced
+   * records store additional metadata for tracking changes and resolving
+   * merge conflicts. Deleting a synced record replaces the record with a
+   * tombstone.
+   *
+   * @param   {string} guid
+   *          The GUID of the record or tombstone.
+   * @returns {boolean}
+   *          `true` if the record or tombstone is syncing; `false` if the
+   *          record doesn't exist or hasn't been synced yet.
+   */
+  isSyncing(guid) {
+    let record = this._findByGUID(guid, {includeDeleted: true});
+    if (!record) {
+      return false;
+    }
+    return !!this._getSyncMetaData(record);
+  }
+
   // Used to get, and optionally create, sync metadata. Brand new records will
   // *not* have sync meta-data - it will be created when they are first
   // synced.
   _getSyncMetaData(record, forceCreate = false) {
     if (!record._sync && forceCreate) {
       // create default metadata and indicate we need to save.
       record._sync = {
         changeCounter: 1,
+        lastSyncedFields: {},
       };
       this._store.saveSoon();
     }
     return record._sync;
   }
 
   /**
+   * Finds a new record with a different GUID but the same contents as the
+   * given record. Sync uses this method to dedupe existing local records to
+   * incoming remote records that don't exist locally.
+   *
+   * @param   {Object} record
+   *          The remote record.
+   * @returns {string|null}
+   *          The GUID of the matching local record, or `null` if no records
+   *          match.
+   */
+  findDuplicateGUID(record) {
+    if (!record.guid) {
+      throw new Error("Record missing GUID");
+    }
+
+    if (record.deleted) {
+      // Tombstones don't carry enough info to dedupe, and we should have handled
+      // them separately when applying the record.
+      throw new Error("Tombstones can't have duplicates");
+    }
+
+    for (let profile of this.getAll({includePrivateFields: true})) {
+      if (profile.guid == record.guid) {
+        throw new Error("should not call this if there's an existing one");
+      }
+      let sync = profile._sync;
+      if (sync) {
+        // this record is already syncing, so can't be a dupe of a new incoming
+        // item.
+        continue;
+      }
+      let keys = new Set(Object.keys(record));
+      for (let key of Object.keys(profile)) {
+        keys.add(key);
+      }
+      for (let field of this.INTERNAL_FIELDS) {
+        keys.delete(field);
+      }
+      let same = true;
+      for (let key of keys) {
+        if (profile.hasOwnProperty(key) && record.hasOwnProperty(key)) {
+          same = profile[key] == record[key];
+        }
+        if (!same) {
+          break;
+        }
+        // else something smarter, possibly using version field?
+      }
+      if (same) {
+        return profile.guid;
+      }
+    }
+    return null;
+  }
+
+  /**
    * Internal helper functions.
    */
 
   _clone(record, {includePrivateFields = false} = {}) {
     let result = Object.assign({}, record);
     if (includePrivateFields) {
       return result;
     }
@@ -703,17 +1049,18 @@ class AutofillRecords {
   mergeIfPossible(guid, record) {}
 
   // An interface to be inherited.
   mergeToStorage(targetRecord) {}
 }
 
 class Addresses extends AutofillRecords {
   constructor(store) {
-    super(store, "addresses", VALID_PROFILE_FIELDS, ADDRESS_SCHEMA_VERSION);
+    super(store, "addresses", VALID_PROFILE_FIELDS, INTERNAL_FIELDS,
+          ADDRESS_SCHEMA_VERSION);
   }
 
   _recordReadProcessor(profile, {noComputedFields} = {}) {
     if (noComputedFields) {
       return;
     }
 
     // Compute name
@@ -890,17 +1237,18 @@ class Addresses extends AutofillRecords 
     }
     this.log.debug("Existing records matching and merging count is", mergedGUIDs.length);
     return mergedGUIDs;
   }
 }
 
 class CreditCards extends AutofillRecords {
   constructor(store) {
-    super(store, "creditCards", VALID_CREDIT_CARD_FIELDS, CREDIT_CARD_SCHEMA_VERSION);
+    super(store, "creditCards", VALID_CREDIT_CARD_FIELDS, INTERNAL_FIELDS,
+          CREDIT_CARD_SCHEMA_VERSION);
   }
 
   _recordReadProcessor(creditCard, {noComputedFields} = {}) {
     if (noComputedFields) {
       return;
     }
 
     // Compute split names
--- a/browser/extensions/formautofill/test/unit/head.js
+++ b/browser/extensions/formautofill/test/unit/head.js
@@ -148,16 +148,26 @@ function runHeuristicsTest(patterns, fix
           expectedField.elementWeakRef = field.elementWeakRef;
           Assert.deepEqual(field, expectedField);
         });
       });
     });
   });
 }
 
+function objectMatches(object, fields) {
+  for (let key of Object.keys(fields)) {
+    if (typeof fields[key] == "object") {
+      objectMatches(object[key], fields[key]);
+    } else {
+      equal(object[key], fields[key]);
+    }
+  }
+}
+
 add_task(async function head_initialize() {
   Services.prefs.setBoolPref("extensions.formautofill.experimental", true);
   Services.prefs.setBoolPref("extensions.formautofill.heuristics.enabled", true);
   Services.prefs.setBoolPref("dom.forms.autocomplete.experimental", true);
 
   // Clean up after every test.
   do_register_cleanup(function head_cleanup() {
     Services.prefs.clearUserPref("extensions.formautofill.experimental");
new file mode 100644
--- /dev/null
+++ b/browser/extensions/formautofill/test/unit/test_reconcile.js
@@ -0,0 +1,506 @@
+"use strict";
+
+const {ProfileStorage} = Cu.import("resource://formautofill/ProfileStorage.jsm", {});
+
+const TEST_STORE_FILE_NAME = "test-profile.json";
+
+// NOTE: a guide to reading these test-cases:
+// parent: What the local record looked like the last time we wrote the
+//         record to the Sync server.
+// local:  What the local record looks like now. IOW, the differences between
+//         'parent' and 'local' are changes recently made which we wish to sync.
+// remote: An incoming record we need to apply (ie, a record that was possibly
+//         changed on a remote device)
+//
+// To further help understanding this, a few of the testcases are annotated.
+const RECONCILE_TESTCASES = [
+  {
+    description: "Local change",
+    parent: {
+      // So when we last wrote the record to the server, it had these values.
+      "guid": "2bbd2d8fbc6b",
+      "given-name": "Mark",
+      "family-name": "Hammond",
+    },
+    local: [{
+      // The current local record - by comparing against parent we can see that
+      // only the given-name has changed locally.
+      "given-name": "Skip",
+      "family-name": "Hammond",
+    }],
+    remote: {
+      // This is the incoming record. It has the same values as "parent", so
+      // we can deduce the record hasn't actually been changed remotely so we
+      // can safely ignore the incoming record and write our local changes.
+      "guid": "2bbd2d8fbc6b",
+      "given-name": "Mark",
+      "family-name": "Hammond",
+    },
+    reconciled: {
+      "guid": "2bbd2d8fbc6b",
+      "given-name": "Skip",
+      "family-name": "Hammond",
+    },
+  },
+  {
+    description: "Remote change",
+    parent: {
+      "guid": "e3680e9f890d",
+      "given-name": "Mark",
+      "family-name": "Hammond",
+    },
+    local: [{
+      "given-name": "Mark",
+      "family-name": "Hammond",
+    }],
+    remote: {
+      "guid": "e3680e9f890d",
+      "given-name": "Skip",
+      "family-name": "Hammond",
+    },
+    reconciled: {
+      "guid": "e3680e9f890d",
+      "given-name": "Skip",
+      "family-name": "Hammond",
+    },
+  },
+  {
+    description: "New local field",
+    parent: {
+      "guid": "0cba738b1be0",
+      "given-name": "Mark",
+      "family-name": "Hammond",
+    },
+    local: [{
+      "given-name": "Mark",
+      "family-name": "Hammond",
+      "tel": "123456",
+    }],
+    remote: {
+      "guid": "0cba738b1be0",
+      "given-name": "Mark",
+      "family-name": "Hammond",
+    },
+    reconciled: {
+      "guid": "0cba738b1be0",
+      "given-name": "Mark",
+      "family-name": "Hammond",
+      "tel": "123456",
+    },
+  },
+  {
+    description: "New remote field",
+    parent: {
+      "guid": "be3ef97f8285",
+      "given-name": "Mark",
+      "family-name": "Hammond",
+    },
+    local: [{
+      "given-name": "Mark",
+      "family-name": "Hammond",
+    }],
+    remote: {
+      "guid": "be3ef97f8285",
+      "given-name": "Mark",
+      "family-name": "Hammond",
+      "tel": "123456",
+    },
+    reconciled: {
+      "guid": "be3ef97f8285",
+      "given-name": "Mark",
+      "family-name": "Hammond",
+      "tel": "123456",
+    },
+  },
+  {
+    description: "Deleted field locally",
+    parent: {
+      "guid": "9627322248ec",
+      "given-name": "Mark",
+      "family-name": "Hammond",
+      "tel": "123456",
+    },
+    local: [{
+      "given-name": "Mark",
+      "family-name": "Hammond",
+    }],
+    remote: {
+      "guid": "9627322248ec",
+      "given-name": "Mark",
+      "family-name": "Hammond",
+      "tel": "123456",
+    },
+    reconciled: {
+      "guid": "9627322248ec",
+      "given-name": "Mark",
+      "family-name": "Hammond",
+    },
+  },
+  {
+    description: "Deleted field remotely",
+    parent: {
+      "guid": "7d7509f3eeb2",
+      "given-name": "Mark",
+      "family-name": "Hammond",
+      "tel": "123456",
+    },
+    local: [{
+      "given-name": "Mark",
+      "family-name": "Hammond",
+      "tel": "123456",
+    }],
+    remote: {
+      "guid": "7d7509f3eeb2",
+      "given-name": "Mark",
+      "family-name": "Hammond",
+    },
+    reconciled: {
+      "guid": "7d7509f3eeb2",
+      "given-name": "Mark",
+      "family-name": "Hammond",
+    },
+  },
+  {
+    description: "Local and remote changes to unrelated fields",
+    parent: {
+      // The last time we wrote this to the server, country was NZ.
+      "guid": "e087a06dfc57",
+      "given-name": "Mark",
+      "family-name": "Hammond",
+      "country": "NZ",
+    },
+    local: [{
+      // The current local record - so locally we've changed given-name to Skip.
+      "given-name": "Skip",
+      "family-name": "Hammond",
+      "country": "NZ",
+    }],
+    remote: {
+      // Remotely, we've changed the country to AU.
+      "guid": "e087a06dfc57",
+      "given-name": "Mark",
+      "family-name": "Hammond",
+      "country": "AU",
+    },
+    reconciled: {
+      "guid": "e087a06dfc57",
+      "given-name": "Skip",
+      "family-name": "Hammond",
+      "country": "AU",
+    },
+  },
+  {
+    description: "Multiple local changes",
+    parent: {
+      "guid": "340a078c596f",
+      "given-name": "Mark",
+      "family-name": "Hammond",
+      "tel": "123456",
+    },
+    local: [{
+      "given-name": "Skip",
+      "family-name": "Hammond",
+    }, {
+      "given-name": "Skip",
+      "family-name": "Hammond",
+      "organization": "Mozilla",
+    }],
+    remote: {
+      "guid": "340a078c596f",
+      "given-name": "Mark",
+      "family-name": "Hammond",
+      "tel": "123456",
+      "country": "AU",
+    },
+    reconciled: {
+      "guid": "340a078c596f",
+      "given-name": "Skip",
+      "family-name": "Hammond",
+      "organization": "Mozilla",
+      "country": "AU",
+    },
+  },
+  {
+    // Local and remote diverged from the shared parent, but the values are the
+    // same, so we shouldn't fork.
+    description: "Same change to local and remote",
+    parent: {
+      "guid": "0b3a72a1bea2",
+      "given-name": "Mark",
+      "family-name": "Hammond",
+    },
+    local: [{
+      "given-name": "Skip",
+      "family-name": "Hammond",
+    }],
+    remote: {
+      "guid": "0b3a72a1bea2",
+      "given-name": "Skip",
+      "family-name": "Hammond",
+    },
+    reconciled: {
+      "guid": "0b3a72a1bea2",
+      "given-name": "Skip",
+      "family-name": "Hammond",
+    },
+  },
+  {
+    description: "Conflicting changes to single field",
+    parent: {
+      // This is what we last wrote to the sync server.
+      "guid": "62068784d089",
+      "given-name": "Mark",
+      "family-name": "Hammond",
+    },
+    local: [{
+      // The current version of the local record - the given-name has changed locally.
+      "given-name": "Skip",
+      "family-name": "Hammond",
+    }],
+    remote: {
+      // An incoming record has a different given-name than any of the above!
+      "guid": "62068784d089",
+      "given-name": "Kip",
+      "family-name": "Hammond",
+    },
+    forked: {
+      // So we've forked the local record to a new GUID (and the next sync is
+      // going to write this as a new record)
+      "given-name": "Skip",
+      "family-name": "Hammond",
+    },
+    reconciled: {
+      // And we've updated the local version of the record to be the remote version.
+      guid: "62068784d089",
+      "given-name": "Kip",
+      "family-name": "Hammond",
+    },
+  },
+  {
+    description: "Conflicting changes to multiple fields",
+    parent: {
+      "guid": "244dbb692e94",
+      "given-name": "Mark",
+      "family-name": "Hammond",
+      "country": "NZ",
+    },
+    local: [{
+      "given-name": "Skip",
+      "family-name": "Hammond",
+      "country": "AU",
+    }],
+    remote: {
+      "guid": "244dbb692e94",
+      "given-name": "Kip",
+      "family-name": "Hammond",
+      "country": "CA",
+    },
+    forked: {
+      "given-name": "Skip",
+      "family-name": "Hammond",
+      "country": "AU",
+    },
+    reconciled: {
+      "guid": "244dbb692e94",
+      "given-name": "Kip",
+      "family-name": "Hammond",
+      "country": "CA",
+    },
+  },
+  {
+    description: "Field deleted locally, changed remotely",
+    parent: {
+      "guid": "fff9fa27fa18",
+      "given-name": "Mark",
+      "family-name": "Hammond",
+      "country": "AU",
+    },
+    local: [{
+      "given-name": "Mark",
+      "family-name": "Hammond",
+      "country": "NZ",
+    }],
+    remote: {
+      "guid": "fff9fa27fa18",
+      "given-name": "Mark",
+      "family-name": "Hammond",
+    },
+    forked: {
+      "given-name": "Mark",
+      "family-name": "Hammond",
+      "country": "NZ",
+    },
+    reconciled: {
+      "guid": "fff9fa27fa18",
+      "given-name": "Mark",
+      "family-name": "Hammond",
+    },
+  },
+  {
+    // Created, last modified should be synced; last used and times used should
+    // be local. Remote created time older than local, remote modified time
+    // newer than local.
+    description: "Created, last modified time reconciliation without local changes",
+    parent: {
+      "guid": "5113f329c42f",
+      "given-name": "Mark",
+      "family-name": "Hammond",
+      "timeCreated": 1234,
+      "timeLastModified": 5678,
+      "timeLastUsed": 5678,
+      "timesUsed": 6,
+    },
+    local: [],
+    remote: {
+      "guid": "5113f329c42f",
+      "given-name": "Mark",
+      "family-name": "Hammond",
+      "timeCreated": 1200,
+      "timeLastModified": 5700,
+      "timeLastUsed": 5700,
+      "timesUsed": 3,
+    },
+    reconciled: {
+      "guid": "5113f329c42f",
+      "given-name": "Mark",
+      "family-name": "Hammond",
+      "timeCreated": 1200,
+      "timeLastModified": 5700,
+      "timeLastUsed": 5678,
+      "timesUsed": 6,
+    },
+  },
+  {
+    // Local changes, remote created time newer than local, remote modified time
+    // older than local.
+    description: "Created, last modified time reconciliation with local changes",
+    parent: {
+      "guid": "791e5608b80a",
+      "given-name": "Mark",
+      "family-name": "Hammond",
+      "timeCreated": 1234,
+      "timeLastModified": 5678,
+      "timeLastUsed": 5678,
+      "timesUsed": 6,
+    },
+    local: [{
+      "given-name": "Skip",
+      "family-name": "Hammond",
+    }],
+    remote: {
+      "guid": "791e5608b80a",
+      "given-name": "Mark",
+      "family-name": "Hammond",
+      "timeCreated": 1300,
+      "timeLastModified": 5000,
+      "timeLastUsed": 5000,
+      "timesUsed": 3,
+    },
+    reconciled: {
+      "guid": "791e5608b80a",
+      "given-name": "Skip",
+      "family-name": "Hammond",
+      "timeCreated": 1234,
+      "timeLastUsed": 5678,
+      "timesUsed": 6,
+    },
+  },
+];
+
+add_task(async function test_reconcile_idempotent() {
+  let path = getTempFile(TEST_STORE_FILE_NAME).path;
+
+  let profileStorage = new ProfileStorage(path);
+  await profileStorage.initialize();
+
+  let guid = "de1ba7b094fe";
+  profileStorage.addresses.add({
+    guid,
+    "given-name": "Mark",
+    "family-name": "Hammond",
+  }, {sourceSync: true});
+  profileStorage.addresses.update(guid, {
+    "given-name": "Skip",
+    "family-name": "Hammond",
+    "organization": "Mozilla",
+  });
+
+  let remote = {
+    guid,
+    "given-name": "Mark",
+    "family-name": "Hammond",
+    "tel": "123456",
+  };
+
+  {
+    let {forkedGUID} = profileStorage.addresses.reconcile(remote);
+    let updatedRecord = profileStorage.addresses.get(guid, {
+      noComputedFields: true,
+    });
+
+    ok(!forkedGUID, "First merge should not fork record");
+    objectMatches(updatedRecord, {
+      "guid": "de1ba7b094fe",
+      "given-name": "Skip",
+      "family-name": "Hammond",
+      "organization": "Mozilla",
+      "tel": "123456",
+    }, "First merge should merge local and remote changes");
+  }
+
+  {
+    let {forkedGUID} = profileStorage.addresses.reconcile(remote);
+    let updatedRecord = profileStorage.addresses.get(guid, {
+      noComputedFields: true,
+    });
+
+    ok(!forkedGUID, "Second merge should not fork record");
+    objectMatches(updatedRecord, {
+      "guid": "de1ba7b094fe",
+      "given-name": "Skip",
+      "family-name": "Hammond",
+      "organization": "Mozilla",
+      "tel": "123456",
+    }, "Second merge should not change record");
+  }
+});
+
+add_task(async function test_reconcile_merge() {
+  let path = getTempFile(TEST_STORE_FILE_NAME).path;
+
+  let profileStorage = new ProfileStorage(path);
+  await profileStorage.initialize();
+
+  for (let test of RECONCILE_TESTCASES) {
+    do_print(test.description);
+
+    profileStorage.addresses.add(test.parent, {sourceSync: true});
+
+    for (let updatedRecord of test.local) {
+      profileStorage.addresses.update(test.parent.guid, updatedRecord);
+    }
+
+    let localRecord = profileStorage.addresses.get(test.parent.guid, {
+      noComputedFields: true,
+    });
+
+    let {forkedGUID} = profileStorage.addresses.reconcile(test.remote);
+    let reconciledRecord = profileStorage.addresses.get(test.parent.guid, {
+      noComputedFields: true,
+    });
+    if (forkedGUID) {
+      let forkedRecord = profileStorage.addresses.get(forkedGUID, {
+        noComputedFields: true,
+      });
+
+      notEqual(forkedRecord.guid, reconciledRecord.guid);
+      equal(forkedRecord.timeLastModified, localRecord.timeLastModified);
+      objectMatches(forkedRecord, test.forked,
+        `${test.description} should fork record`);
+    } else {
+      ok(!test.forked, `${test.description} should not fork record`);
+    }
+
+    objectMatches(reconciledRecord, test.reconciled);
+  }
+});
--- a/browser/extensions/formautofill/test/unit/test_sync.js
+++ b/browser/extensions/formautofill/test/unit/test_sync.js
@@ -44,31 +44,27 @@ function expectLocalProfiles(expected) {
   let profiles = profileStorage.addresses.getAll({
     includePrivateFields: true,
     includeDeleted: true,
   });
   expected.sort((a, b) => a.guid.localeCompare(b.guid));
   profiles.sort((a, b) => a.guid.localeCompare(b.guid));
   let doCheckObject = (a, b) => {
     for (let key of Object.keys(a)) {
-      if (typeof a[key] == "object") {
-        doCheckObject(a[key], b[key]);
-      } else {
-        equal(a[key], b[key]);
-      }
+
     }
   };
   try {
     deepEqual(profiles.map(p => p.guid), expected.map(p => p.guid));
     for (let i = 0; i < expected.length; i++) {
       let thisExpected = expected[i];
       let thisGot = profiles[i];
       // always check "deleted".
       equal(thisExpected.deleted, thisGot.deleted);
-      doCheckObject(thisExpected, thisGot);
+      objectMatches(thisGot, thisExpected);
     }
   } catch (ex) {
     do_print("Comparing expected profiles:");
     do_print(JSON.stringify(expected, undefined, 2));
     do_print("against actual profiles:");
     do_print(JSON.stringify(profiles, undefined, 2));
     throw ex;
   }
@@ -190,16 +186,17 @@ add_task(async function test_incoming_ne
     server.insertWBO("foo", "addresses", new ServerWBO(deletedID, encryptPayload({
       id: deletedID,
       deleted: true,
     }), Date.now() / 1000));
 
     // The tracker should start with no score.
     equal(engine._tracker.score, 0);
 
+    engine.lastSync = 0;
     engine.sync();
 
     expectLocalProfiles([
       {
         guid: profileID,
         _sync: {changeCounter: 0},
       }, {
         guid: deletedID,
@@ -211,16 +208,49 @@ add_task(async function test_incoming_ne
     // The sync applied new records - ensure our tracker knew it came from
     // sync and didn't bump the score.
     equal(engine._tracker.score, 0);
   } finally {
     await cleanup(server);
   }
 });
 
+add_task(async function test_incoming_existing() {
+  let {server, engine} = await setup();
+  try {
+    let guid1 = profileStorage.addresses.add(TEST_PROFILE_1);
+    let guid2 = profileStorage.addresses.add(TEST_PROFILE_2);
+
+    // an initial sync so we don't think they are locally modified.
+    engine.sync();
+
+    // now server records that modify the existing items.
+    let modifiedEntry1 = Object.assign({}, TEST_PROFILE_1, {"given-name": "NewName"});
+
+    server.insertWBO("foo", "addresses", new ServerWBO(guid1, encryptPayload({
+      id: guid1,
+      entry: modifiedEntry1,
+    }), Date.now() / 1000));
+    server.insertWBO("foo", "addresses", new ServerWBO(guid2, encryptPayload({
+      id: guid2,
+      deleted: true,
+    }), Date.now() / 1000));
+
+    engine.lastSync = 0;
+    engine.sync();
+
+    expectLocalProfiles([
+      Object.assign({}, modifiedEntry1, {guid: guid1}),
+      {guid: guid2, deleted: true},
+    ]);
+  } finally {
+    await cleanup(server);
+  }
+});
+
 add_task(async function test_tombstones() {
   let {server, collection, engine} = await setup();
   try {
     let existingGUID = profileStorage.addresses.add(TEST_PROFILE_1);
 
     engine.sync();
 
     Assert.equal(collection.count(), 1);
@@ -236,65 +266,290 @@ add_task(async function test_tombstones(
     payload = collection.payloads()[0];
     equal(payload.id, existingGUID);
     equal(payload.deleted, true);
   } finally {
     await cleanup(server);
   }
 });
 
+add_task(async function test_applyIncoming_both_deleted() {
+  let {server, engine} = await setup();
+  try {
+    let guid = profileStorage.addresses.add(TEST_PROFILE_1);
+
+    engine.lastSync = 0;
+    engine.sync();
+
+    // Delete synced record locally.
+    profileStorage.addresses.remove(guid);
+
+    // Delete same record remotely.
+    let collection = server.user("foo").collection("addresses");
+    collection.insert(guid, encryptPayload({
+      id: guid,
+      deleted: true,
+    }), Date.now() / 1000);
+
+    engine.sync();
+
+    ok(!profileStorage.addresses.get(guid),
+      "Should not return record for locally deleted item");
+
+    let localRecords = profileStorage.addresses.getAll({
+      includeDeleted: true,
+    });
+    equal(localRecords.length, 1, "Only tombstone should exist locally");
+
+    equal(collection.count(), 1,
+      "Only tombstone should exist on server");
+  } finally {
+    await cleanup(server);
+  }
+});
+
+add_task(async function test_applyIncoming_nonexistent_tombstone() {
+  let {server, engine} = await setup();
+  try {
+    let guid = profileStorage.addresses._generateGUID();
+    let collection = server.user("foo").collection("addresses");
+    collection.insert(guid, encryptPayload({
+      id: guid,
+      deleted: true,
+    }), Date.now() / 1000);
+
+    engine.lastSync = 0;
+    engine.sync();
+
+    ok(!profileStorage.addresses.get(guid),
+      "Should not return record for uknown deleted item");
+    let localTombstone = profileStorage.addresses.getAll({
+      includeDeleted: true,
+    }).find(record => record.guid == guid);
+    ok(localTombstone, "Should store tombstone for unknown item");
+  } finally {
+    await cleanup(server);
+  }
+});
+
+add_task(async function test_applyIncoming_incoming_deleted() {
+  let {server, engine} = await setup();
+  try {
+    let guid = profileStorage.addresses.add(TEST_PROFILE_1);
+
+    engine.lastSync = 0;
+    engine.sync();
+
+    // Delete the record remotely.
+    let collection = server.user("foo").collection("addresses");
+    collection.insert(guid, encryptPayload({
+      id: guid,
+      deleted: true,
+    }), Date.now() / 1000);
+
+    engine.sync();
+
+    ok(!profileStorage.addresses.get(guid), "Should delete unmodified item locally");
+
+    let localTombstone = profileStorage.addresses.getAll({
+      includeDeleted: true,
+    }).find(record => record.guid == guid);
+    ok(localTombstone, "Should keep local tombstone for remotely deleted item");
+    ok(profileStorage.addresses.isSyncing(guid), "Local tombstone should be marked as syncing");
+  } finally {
+    await cleanup(server);
+  }
+});
+
+add_task(async function test_applyIncoming_incoming_restored() {
+  let {server, engine} = await setup();
+  try {
+    let guid = profileStorage.addresses.add(TEST_PROFILE_1);
+
+    // Upload the record to the server.
+    engine.lastSync = 0;
+    engine.sync();
+
+    // Removing a synced record should write a tombstone.
+    profileStorage.addresses.remove(guid);
+
+    // Modify the deleted record remotely.
+    let collection = server.user("foo").collection("addresses");
+    let serverPayload = JSON.parse(JSON.parse(collection.payload(guid)).ciphertext);
+    serverPayload.entry["street-address"] = "I moved!";
+    collection.insert(guid, encryptPayload(serverPayload), Date.now() / 1000);
+
+    // Sync again.
+    engine.sync();
+
+    // We should replace our tombstone with the server's version.
+    let localRecord = profileStorage.addresses.get(guid);
+    objectMatches(localRecord, {
+      "given-name": "Timothy",
+      "family-name": "Berners-Lee",
+      "street-address": "I moved!",
+    });
+
+    let maybeNewServerPayload = JSON.parse(JSON.parse(collection.payload(guid)).ciphertext);
+    deepEqual(maybeNewServerPayload, serverPayload, "Should not change record on server");
+  } finally {
+    await cleanup(server);
+  }
+});
+
+add_task(async function test_applyIncoming_outgoing_restored() {
+  let {server, engine} = await setup();
+  try {
+    let guid = profileStorage.addresses.add(TEST_PROFILE_1);
+
+    // Upload the record to the server.
+    engine.lastSync = 0;
+    engine.sync();
+
+    // Modify the local record.
+    let localCopy = Cu.cloneInto(TEST_PROFILE_1, {});
+    localCopy["street-address"] = "I moved!";
+    profileStorage.addresses.update(guid, localCopy);
+
+    // Replace the record with a tombstone on the server.
+    let collection = server.user("foo").collection("addresses");
+    collection.insert(guid, encryptPayload({
+      id: guid,
+      deleted: true,
+    }), Date.now() / 1000);
+
+    // Sync again.
+    engine.sync();
+
+    // We should resurrect the record on the server.
+    let serverPayload = JSON.parse(JSON.parse(collection.payload(guid)).ciphertext);
+    ok(!serverPayload.deleted, "Should resurrect record on server");
+    objectMatches(serverPayload.entry, {
+      "given-name": "Timothy",
+      "family-name": "Berners-Lee",
+      "street-address": "I moved!",
+    });
+
+    let localRecord = profileStorage.addresses.get(guid);
+    ok(localRecord, "Modified record should not be deleted locally");
+  } finally {
+    await cleanup(server);
+  }
+});
+
 // Unlike most sync engines, we want "both modified" to inspect the records,
 // and if materially different, create a duplicate.
 add_task(async function test_reconcile_both_modified_identical() {
   let {server, engine} = await setup();
   try {
     // create a record locally.
     let guid = profileStorage.addresses.add(TEST_PROFILE_1);
 
     // and an identical record on the server.
     server.insertWBO("foo", "addresses", new ServerWBO(guid, encryptPayload({
       id: guid,
       entry: TEST_PROFILE_1,
     }), Date.now() / 1000));
 
+    engine.lastSync = 0;
     engine.sync();
 
     expectLocalProfiles([{guid}]);
   } finally {
     await cleanup(server);
   }
 });
 
-add_task(async function test_dedupe_identical() {
+add_task(async function test_incoming_dupes() {
+  let {server, engine} = await setup();
+  try {
+    let guid1 = profileStorage.addresses.add(TEST_PROFILE_1);
+
+    // an initial sync so we don't think it is locally modified.
+    engine.sync();
+
+    // Another profile that we *do* think is locally modified and is yet to be
+    // synced.
+    let guid2 = profileStorage.addresses.add(TEST_PROFILE_2);
+
+    // now server records that duplicate the existing items.
+    let guid1_dupe = Utils.makeGUID();
+    server.insertWBO("foo", "addresses", new ServerWBO(guid1_dupe, encryptPayload({
+      id: guid1_dupe,
+      entry: TEST_PROFILE_1,
+    }), Date.now() / 1000));
+    let guid2_dupe = Utils.makeGUID();
+    server.insertWBO("foo", "addresses", new ServerWBO(guid2_dupe, encryptPayload({
+      id: guid2_dupe,
+      entry: TEST_PROFILE_2,
+    }), Date.now() / 1000));
+
+    engine.lastSync = 0;
+    engine.sync();
+
+    expectLocalProfiles([
+      // guid1 had previously synced, so isn't touched.
+      Object.assign({}, TEST_PROFILE_1, {guid: guid1}),
+      // The incoming "dupe" of guid1 was applied.
+      Object.assign({}, TEST_PROFILE_1, {guid: guid1_dupe}),
+      // and guid2 is now guid2_dupe.
+      Object.assign({}, TEST_PROFILE_2, {guid: guid2_dupe}),
+    ]);
+  } finally {
+    await cleanup(server);
+  }
+});
+
+add_task(async function test_dedupe_identical_unsynced() {
   let {server, engine} = await setup();
   try {
     // create a record locally.
     let localGuid = profileStorage.addresses.add(TEST_PROFILE_1);
 
     // and an identical record on the server but different GUID.
     let remoteGuid = Utils.makeGUID();
     server.insertWBO("foo", "addresses", new ServerWBO(remoteGuid, encryptPayload({
       id: remoteGuid,
       entry: TEST_PROFILE_1,
     }), Date.now() / 1000));
 
+    engine.lastSync = 0;
     engine.sync();
 
-    // Should have 1 item locally with GUID changed to the remote one, and a
-    // tombstone for the now deleted item.
+    // Should have 1 item locally with GUID changed to the remote one.
+    // There's no tombstone as the original was unsynced.
+    expectLocalProfiles([{guid: remoteGuid}]);
+  } finally {
+    await cleanup(server);
+  }
+});
+
+add_task(async function test_dedupe_identical_synced() {
+  let {server, engine} = await setup();
+  try {
+    // create a record locally.
+    let localGuid = profileStorage.addresses.add(TEST_PROFILE_1);
+    // sync it - it will no longer be a candidate for de-duping.
+    engine.sync();
+
+    // and an identical record on the server but different GUID.
+    let remoteGuid = Utils.makeGUID();
+    server.insertWBO("foo", "addresses", new ServerWBO(remoteGuid, encryptPayload({
+      id: remoteGuid,
+      entry: TEST_PROFILE_1,
+    }), Date.now() / 1000));
+
+    engine.lastSync = 0;
+    engine.sync();
+
+    // Should have 2 items locally, since the first was synced.
     expectLocalProfiles([
-      {
-        guid: localGuid,
-        deleted: true,
-      },
-      {
-        guid: remoteGuid,
-      },
+      {guid: localGuid},
+      {guid: remoteGuid},
     ]);
-    // XXX - check tombstone on the server.
   } finally {
     await cleanup(server);
   }
 });
 
 add_task(async function test_dedupe_multiple_candidates() {
   let {server, engine} = await setup();
   try {
@@ -323,16 +578,17 @@ add_task(async function test_dedupe_mult
       id: bGuid,
       entry: bRecord,
     }), Date.now() / 1000));
     server.insertWBO("foo", "addresses", new ServerWBO(aGuid, encryptPayload({
       id: aGuid,
       entry: aRecord,
     }), Date.now() / 1000));
 
+    engine.lastSync = 0;
     engine.sync();
 
     expectLocalProfiles([
       {
         "guid": aGuid,
         "given-name": "Mark",
         "family-name": "Hammond",
         "organization": "Mozilla",
@@ -344,41 +600,74 @@ add_task(async function test_dedupe_mult
         "given-name": "Mark",
         "family-name": "Hammond",
         "organization": "Mozilla",
         "country": "AU",
         "tel": "123456",
       },
     ]);
 
-    // TODO: Check Sync fields, verify they're both SYNCING.
+    ok(profileStorage.addresses.isSyncing(aGuid),
+      "A should be marked as syncing");
+    ok(profileStorage.addresses.isSyncing(bGuid),
+      "B should be marked as syncing");
   } finally {
     await cleanup(server);
   }
 });
 
 // Unlike most sync engines, we want "both modified" to inspect the records,
 // and if materially different, create a duplicate.
 add_task(async function test_reconcile_both_modified_conflict() {
   let {server, engine} = await setup();
   try {
     // create a record locally.
     let guid = profileStorage.addresses.add(TEST_PROFILE_1);
 
-    // clone the profile and adjust something for storing on the server.
-    let serverCopy = Object.assign({}, TEST_PROFILE_1);
-    serverCopy["street-address"] = "I moved!";
+    // Upload the record to the server.
+    engine.lastSync = 0;
+    engine.sync();
+
+    ok(profileStorage.addresses.isSyncing(guid),
+      "Original record should be marked as syncing");
 
-    server.insertWBO("foo", "addresses", new ServerWBO(guid, encryptPayload({
-      id: guid,
-      entry: serverCopy,
-    }), Date.now() / 1000));
+    // Change the same field locally and on the server.
+    let localCopy = Cu.cloneInto(TEST_PROFILE_1, {});
+    localCopy["street-address"] = "I moved!";
+    profileStorage.addresses.update(guid, localCopy);
 
+    let collection = server.user("foo").collection("addresses");
+    let serverPayload = JSON.parse(JSON.parse(collection.payload(guid)).ciphertext);
+    serverPayload.entry["street-address"] = "I moved, too!";
+    collection.insert(guid, encryptPayload(serverPayload), Date.now() / 1000);
+
+    // Sync again.
     engine.sync();
 
-    // TODO: check semantics - (ie, remote copy should have same ID, local
-    // copy should have had the GUID changed and be marked as changed.)
-    // XXX - call expectLocalProfiles - but this doesn't work yet.
-    // XXX - FIXME!
+    // Since we wait to pull changes until we're ready to upload, both records
+    // should now exist on the server; we don't need a follow-up sync.
+    let serverPayloads = collection.payloads();
+    equal(serverPayloads.length, 2, "Both records should exist on server");
+
+    let forkedPayload = serverPayloads.find(payload => payload.id != guid);
+    ok(forkedPayload, "Forked record should exist on server");
+
+    expectLocalProfiles([
+      {
+        guid,
+        "given-name": "Timothy",
+        "family-name": "Berners-Lee",
+        "street-address": "I moved, too!",
+      },
+      {
+        guid: forkedPayload.id,
+        "given-name": "Timothy",
+        "family-name": "Berners-Lee",
+        "street-address": "I moved!",
+      },
+    ]);
+
+    ok(profileStorage.addresses.isSyncing(forkedPayload.id),
+      "Forked record should be marked as syncing");
   } finally {
     await cleanup(server);
   }
 });
--- a/browser/extensions/formautofill/test/unit/xpcshell.ini
+++ b/browser/extensions/formautofill/test/unit/xpcshell.ini
@@ -30,11 +30,12 @@ support-files =
 [test_isFieldEligibleForAutofill.js]
 [test_markAsAutofillField.js]
 [test_nameUtils.js]
 [test_onFormSubmitted.js]
 [test_profileAutocompleteResult.js]
 [test_savedFieldNames.js]
 [test_storage_tombstones.js]
 [test_storage_syncfields.js]
+[test_reconcile.js]
 [test_transformFields.js]
 [test_sync.js]
 head = head.js ../../../../../services/sync/tests/unit/head_appinfo.js ../../../../../services/common/tests/unit/head_helpers.js ../../../../../services/sync/tests/unit/head_helpers.js ../../../../../services/sync/tests/unit/head_http_server.js