Bug 1363995 - Implement autofill record reconciliation. r=seanlee,lchang,markh
authorKit Cambridge <kit@yakshaving.ninja>
Thu, 29 Jun 2017 14:35:04 -0700
changeset 418650 fc6a547a170d3d17e4bcdaa43644523bdfd34dd9
parent 418649 b6a93a94e7d012ed281a84addcf30f7a02ca3b28
child 418651 7c68a93e32ada88f04623a5c72c706216c2f0ac3
push id7566
push usermtabara@mozilla.com
push dateWed, 02 Aug 2017 08:25:16 +0000
treeherdermozilla-beta@86913f512c3c [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersseanlee, lchang, markh
bugs1363995
milestone56.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 1363995 - Implement autofill record reconciliation. r=seanlee,lchang,markh MozReview-Commit-ID: 5Yvr0M4CuyE
browser/extensions/formautofill/FormAutofillSync.jsm
browser/extensions/formautofill/ProfileStorage.jsm
browser/extensions/formautofill/test/unit/test_addressRecords.js
browser/extensions/formautofill/test/unit/test_reconcile.js
browser/extensions/formautofill/test/unit/test_storage_syncfields.js
browser/extensions/formautofill/test/unit/test_sync.js
browser/extensions/formautofill/test/unit/test_transformFields.js
browser/extensions/formautofill/test/unit/xpcshell.ini
--- a/browser/extensions/formautofill/FormAutofillSync.jsm
+++ b/browser/extensions/formautofill/FormAutofillSync.jsm
@@ -11,16 +11,18 @@ 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://formautofill/FormAutofillUtils.jsm");
 
+XPCOMUtils.defineLazyModuleGetter(this, "Log",
+                                  "resource://gre/modules/Log.jsm");
 XPCOMUtils.defineLazyModuleGetter(this, "profileStorage",
                                   "resource://formautofill/ProfileStorage.jsm");
 
 // A helper to sanitize address and creditcard records suitable for logging.
 function sanitizeStorageObject(ob) {
   if (!ob) {
     return null;
   }
@@ -138,34 +140,41 @@ FormAutofillStore.prototype = {
     let entry = remoteRecord.toEntry();
     this.storage.add(entry, {sourceSync: true});
   },
 
   async createRecord(id, collection) {
     this._log.trace("Create record", id);
     let record = new AutofillRecord(collection, id);
     let entry = this.storage.get(id, {
-      noComputedFields: true,
+      rawData: true,
     });
     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;
     }
     return record;
   },
 
   async _doUpdateRecord(record) {
     this._log.trace("Updating record", record);
 
-    // TODO (bug 1363995) - until we get reconcilliation logic, this is
-    // dangerous, it unconditionally updates, which may cause DATA LOSS.
-    this.storage.update(record.id, record.entry);
+    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
@@ -79,17 +79,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 - hashes of 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.
@@ -125,16 +128,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_ADDRESS_FIELDS = [
   "given-name",
@@ -188,16 +194,27 @@ const INTERNAL_FIELDS = [
   "guid",
   "version",
   "timeCreated",
   "timeLastUsed",
   "timeLastModified",
   "timesUsed",
 ];
 
+function sha512(string) {
+  if (string == null) {
+    return null;
+  }
+  let encoder = new TextEncoder("utf-8");
+  let bytes = encoder.encode(string);
+  let hash = new CryptoHash("sha512");
+  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 {
@@ -236,16 +253,26 @@ class AutofillRecords {
    *
    * @returns {number}
    *          The current schema version number.
    */
   get version() {
     return this._schemaVersion;
   }
 
+  // Ensures that we don't try to apply synced records with newer schema
+  // versions. This is a temporary measure to ensure we don't accidentally
+  // bump the schema version without a syncing strategy in place (bug 1377204).
+  _ensureMatchingVersion(record) {
+    if (record.version != this.version) {
+      throw new Error(`Got unknown record version ${
+        record.version}; want ${this.version}`);
+    }
+  }
+
   /**
    * Adds a new record.
    *
    * @param {Object} record
    *        The new record for saving.
    * @param {boolean} [options.sourceSync = false]
    *        Did sync generate this addition?
    * @returns {string}
@@ -263,26 +290,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({}, record, {
-        // `timeLastUsed` and `timesUsed` are always local.
-        timeLastUsed: 0,
-        timesUsed: 0,
-      });
+      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;
 
@@ -307,16 +330,17 @@ class AutofillRecords {
         throw new Error("a record with this GUID already exists");
       }
       recordToSave = {
         guid: record.guid,
         timeLastModified: record.timeLastModified || Date.now(),
         deleted: true,
       };
     } else {
+      this._ensureMatchingVersion(record);
       recordToSave = record;
     }
 
     if (sourceSync) {
       let sync = this._getSyncMetaData(recordToSave, true);
       sync.changeCounter = 0;
     }
 
@@ -352,22 +376,28 @@ 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;
     }
 
@@ -375,17 +405,18 @@ class AutofillRecords {
     this._computeFields(recordFound);
 
     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);
@@ -453,16 +484,17 @@ class AutofillRecords {
    * @param   {boolean} [options.rawData = false]
    *          Returns a raw record without modifications and the computed fields
    *          (this includes private fields)
    * @returns {Object}
    *          A clone of the record.
    */
   get(guid, {rawData = false} = {}) {
     this.log.debug("get:", guid, rawData);
+
     let recordFound = this._findByGUID(guid);
     if (!recordFound) {
       return null;
     }
 
     // The record is cloned to avoid accidental modifications from outside.
     let clonedRecord = this._clone(recordFound);
     if (rawData) {
@@ -525,16 +557,277 @@ class AutofillRecords {
     this.log.debug("getByFilter:", "Returning", result.length, "result(s)");
     return result;
   }
 
   /**
    * Functions intended to be used in the support of Sync.
    */
 
+  /**
+   * Stores a hash of the last synced value for a field in a locally updated
+   * record. We use this value to rebuild the shared parent, or base, when
+   * reconciling incoming records that may have changed on another device.
+   *
+   * Storing the hash of the values that we last wrote to the Sync server lets
+   * us determine if a remote change conflicts with a local change. If the
+   * hashes for the base, current local value, and remote value all differ, we
+   * have a conflict.
+   *
+   * 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 sync = this._getSyncMetaData(record);
+    if (!sync) {
+      // The record hasn't been uploaded yet, so we can't end up with merge
+      // conflicts.
+      return;
+    }
+    let alreadyChanged = field in sync.lastSyncedFields;
+    if (alreadyChanged) {
+      // This field was already changed multiple times since the last sync.
+      return;
+    }
+    let newValue = record[field];
+    if (lastSyncedValue != newValue) {
+      sync.lastSyncedFields[field] = sha512(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 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 == sha512(localRecord[field]);
+        isRemoteSame = lastSyncedValue == sha512(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.
+   */
+  _replaceRecordAt(index, remoteRecord, {keepSyncMetadata = false} = {}) {
+    let localRecord = this._store.data[this._collectionName][index];
+    let newRecord = this._clone(remoteRecord);
+
+    this._stripComputedFields(newRecord);
+
+    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];
+      }
+    }
+
+    this._computeFields(newRecord);
+  }
+
+  /**
+   * 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}
+   *          A clone of the local record with a new GUID.
+   */
+  _forkLocalRecord(localRecord) {
+    let forkedLocalRecord = this._clone(localRecord);
+
+    this._stripComputedFields(forkedLocalRecord);
+
+    forkedLocalRecord.guid = this._generateGUID();
+    this._store.data[this._collectionName].push(forkedLocalRecord);
+
+    // Give the record fresh Sync metadata and bump its change counter as a
+    // side effect. This also excludes the forked record from de-duping on the
+    // next sync, if the current sync is interrupted before the record can be
+    // uploaded.
+    this._getSyncMetaData(forkedLocalRecord, true);
+
+    this._computeFields(forkedLocalRecord);
+
+    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. `remoteRecord` must not be a tombstone, and
+   *          must have a matching local record with the same GUID. Use
+   *          `add` to insert remote records that don't exist locally, and
+   *          `remove` to apply remote tombstones.
+   * @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) {
+    this._ensureMatchingVersion(remoteRecord);
+    if (remoteRecord.deleted) {
+      throw new Error(`Can't reconcile tombstone ${remoteRecord.guid}`);
+    }
+
+    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,
@@ -623,16 +916,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
@@ -685,16 +983,17 @@ class AutofillRecords {
   // 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 local record with matching common fields and a different GUID.
@@ -707,16 +1006,17 @@ class AutofillRecords {
    * @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");
     }
+    this._ensureMatchingVersion(record);
     if (record.deleted) {
       // Tombstones don't carry enough info to de-dupe, and we should have
       // handled them separately when applying the record.
       throw new Error("Tombstones can't have duplicates");
     }
     let records = this._store.data[this._collectionName];
     for (let profile of records) {
       if (profile.deleted) {
--- a/browser/extensions/formautofill/test/unit/test_addressRecords.js
+++ b/browser/extensions/formautofill/test/unit/test_addressRecords.js
@@ -276,27 +276,34 @@ add_task(async function test_notifyUsed(
   let profileStorage = await initProfileStorage(TEST_STORE_FILE_NAME,
                                                 [TEST_ADDRESS_1, TEST_ADDRESS_2]);
 
   let addresses = profileStorage.addresses.getAll();
   let guid = addresses[1].guid;
   let timeLastUsed = addresses[1].timeLastUsed;
   let timesUsed = addresses[1].timesUsed;
 
+  profileStorage.addresses.pullSyncChanges(); // force sync metadata, which we check below.
+  let changeCounter = getSyncChangeCounter(profileStorage.addresses, guid);
+
   let onChanged = TestUtils.topicObserved("formautofill-storage-changed",
                                           (subject, data) => data == "notifyUsed");
 
   profileStorage.addresses.notifyUsed(guid);
   await onChanged;
 
   let address = profileStorage.addresses.get(guid);
 
   do_check_eq(address.timesUsed, timesUsed + 1);
   do_check_neq(address.timeLastUsed, timeLastUsed);
 
+  // Using a record should not bump its change counter.
+  do_check_eq(getSyncChangeCounter(profileStorage.addresses, guid),
+    changeCounter);
+
   Assert.throws(() => profileStorage.addresses.notifyUsed("INVALID_GUID"),
     /No matching record\./);
 });
 
 add_task(async function test_remove() {
   let profileStorage = await initProfileStorage(TEST_STORE_FILE_NAME,
                                                 [TEST_ADDRESS_1, TEST_ADDRESS_2]);
 
new file mode 100644
--- /dev/null
+++ b/browser/extensions/formautofill/test/unit/test_reconcile.js
@@ -0,0 +1,573 @@
+"use strict";
+
+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",
+      "version": 1,
+      "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",
+      "version": 1,
+      "given-name": "Mark",
+      "family-name": "Hammond",
+    },
+    reconciled: {
+      "guid": "2bbd2d8fbc6b",
+      "given-name": "Skip",
+      "family-name": "Hammond",
+    },
+  },
+  {
+    description: "Remote change",
+    parent: {
+      "guid": "e3680e9f890d",
+      "version": 1,
+      "given-name": "Mark",
+      "family-name": "Hammond",
+    },
+    local: [{
+      "given-name": "Mark",
+      "family-name": "Hammond",
+    }],
+    remote: {
+      "guid": "e3680e9f890d",
+      "version": 1,
+      "given-name": "Skip",
+      "family-name": "Hammond",
+    },
+    reconciled: {
+      "guid": "e3680e9f890d",
+      "given-name": "Skip",
+      "family-name": "Hammond",
+    },
+  },
+  {
+    description: "New local field",
+    parent: {
+      "guid": "0cba738b1be0",
+      "version": 1,
+      "given-name": "Mark",
+      "family-name": "Hammond",
+    },
+    local: [{
+      "given-name": "Mark",
+      "family-name": "Hammond",
+      "tel": "123456",
+    }],
+    remote: {
+      "guid": "0cba738b1be0",
+      "version": 1,
+      "given-name": "Mark",
+      "family-name": "Hammond",
+    },
+    reconciled: {
+      "guid": "0cba738b1be0",
+      "given-name": "Mark",
+      "family-name": "Hammond",
+      "tel": "123456",
+    },
+  },
+  {
+    description: "New remote field",
+    parent: {
+      "guid": "be3ef97f8285",
+      "version": 1,
+      "given-name": "Mark",
+      "family-name": "Hammond",
+    },
+    local: [{
+      "given-name": "Mark",
+      "family-name": "Hammond",
+    }],
+    remote: {
+      "guid": "be3ef97f8285",
+      "version": 1,
+      "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",
+      "version": 1,
+      "given-name": "Mark",
+      "family-name": "Hammond",
+      "tel": "123456",
+    },
+    local: [{
+      "given-name": "Mark",
+      "family-name": "Hammond",
+    }],
+    remote: {
+      "guid": "9627322248ec",
+      "version": 1,
+      "given-name": "Mark",
+      "family-name": "Hammond",
+      "tel": "123456",
+    },
+    reconciled: {
+      "guid": "9627322248ec",
+      "given-name": "Mark",
+      "family-name": "Hammond",
+    },
+  },
+  {
+    description: "Deleted field remotely",
+    parent: {
+      "guid": "7d7509f3eeb2",
+      "version": 1,
+      "given-name": "Mark",
+      "family-name": "Hammond",
+      "tel": "123456",
+    },
+    local: [{
+      "given-name": "Mark",
+      "family-name": "Hammond",
+      "tel": "123456",
+    }],
+    remote: {
+      "guid": "7d7509f3eeb2",
+      "version": 1,
+      "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",
+      "version": 1,
+      "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",
+      "version": 1,
+      "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",
+      "version": 1,
+      "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",
+      "version": 1,
+      "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",
+      "version": 1,
+      "given-name": "Mark",
+      "family-name": "Hammond",
+    },
+    local: [{
+      "given-name": "Skip",
+      "family-name": "Hammond",
+    }],
+    remote: {
+      "guid": "0b3a72a1bea2",
+      "version": 1,
+      "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",
+      "version": 1,
+      "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",
+      "version": 1,
+      "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",
+      "version": 1,
+      "given-name": "Mark",
+      "family-name": "Hammond",
+      "country": "NZ",
+    },
+    local: [{
+      "given-name": "Skip",
+      "family-name": "Hammond",
+      "country": "AU",
+    }],
+    remote: {
+      "guid": "244dbb692e94",
+      "version": 1,
+      "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": "6fc45e03d19a",
+      "version": 1,
+      "given-name": "Mark",
+      "family-name": "Hammond",
+      "country": "AU",
+    },
+    local: [{
+      "given-name": "Mark",
+      "family-name": "Hammond",
+    }],
+    remote: {
+      "guid": "6fc45e03d19a",
+      "version": 1,
+      "given-name": "Mark",
+      "family-name": "Hammond",
+      "country": "NZ",
+    },
+    forked: {
+      "given-name": "Mark",
+      "family-name": "Hammond",
+    },
+    reconciled: {
+      "guid": "6fc45e03d19a",
+      "given-name": "Mark",
+      "family-name": "Hammond",
+      "country": "NZ",
+    },
+  },
+  {
+    description: "Field changed locally, deleted remotely",
+    parent: {
+      "guid": "fff9fa27fa18",
+      "version": 1,
+      "given-name": "Mark",
+      "family-name": "Hammond",
+      "country": "AU",
+    },
+    local: [{
+      "given-name": "Mark",
+      "family-name": "Hammond",
+      "country": "NZ",
+    }],
+    remote: {
+      "guid": "fff9fa27fa18",
+      "version": 1,
+      "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",
+      "version": 1,
+      "given-name": "Mark",
+      "family-name": "Hammond",
+      "timeCreated": 1234,
+      "timeLastModified": 5678,
+      "timeLastUsed": 5678,
+      "timesUsed": 6,
+    },
+    local: [],
+    remote: {
+      "guid": "5113f329c42f",
+      "version": 1,
+      "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",
+      "version": 1,
+      "given-name": "Mark",
+      "family-name": "Hammond",
+      "timeCreated": 1234,
+      "timeLastModified": 5678,
+      "timeLastUsed": 5678,
+      "timesUsed": 6,
+    },
+    local: [{
+      "given-name": "Skip",
+      "family-name": "Hammond",
+    }],
+    remote: {
+      "guid": "791e5608b80a",
+      "version": 1,
+      "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_unknown_version() {
+  let profileStorage = await initProfileStorage(TEST_STORE_FILE_NAME);
+
+  // Cross-version reconciliation isn't supported yet. See bug 1377204.
+  throws(() => {
+    profileStorage.addresses.reconcile({
+      "guid": "31d83d2725ec",
+      "version": 2,
+      "given-name": "Mark",
+      "family-name": "Hammond",
+    });
+  }, /Got unknown record version/);
+});
+
+add_task(async function test_reconcile_idempotent() {
+  let profileStorage = await initProfileStorage(TEST_STORE_FILE_NAME);
+
+  let guid = "de1ba7b094fe";
+  profileStorage.addresses.add({
+    guid,
+    version: 1,
+    "given-name": "Mark",
+    "family-name": "Hammond",
+  }, {sourceSync: true});
+  profileStorage.addresses.update(guid, {
+    "given-name": "Skip",
+    "family-name": "Hammond",
+    "organization": "Mozilla",
+  });
+
+  let remote = {
+    guid,
+    "version": 1,
+    "given-name": "Mark",
+    "family-name": "Hammond",
+    "tel": "123456",
+  };
+
+  {
+    let {forkedGUID} = profileStorage.addresses.reconcile(remote);
+    let updatedRecord = profileStorage.addresses.get(guid, {
+      rawData: true,
+    });
+
+    ok(!forkedGUID, "First merge should not fork record");
+    ok(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, {
+      rawData: true,
+    });
+
+    ok(!forkedGUID, "Second merge should not fork record");
+    ok(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_three_way_merge() {
+  let profileStorage = await initProfileStorage(TEST_STORE_FILE_NAME);
+
+  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, {
+      rawData: true,
+    });
+
+    let {forkedGUID} = profileStorage.addresses.reconcile(test.remote);
+    let reconciledRecord = profileStorage.addresses.get(test.parent.guid, {
+      rawData: true,
+    });
+    if (forkedGUID) {
+      let forkedRecord = profileStorage.addresses.get(forkedGUID, {
+        rawData: true,
+      });
+
+      notEqual(forkedRecord.guid, reconciledRecord.guid);
+      equal(forkedRecord.timeLastModified, localRecord.timeLastModified);
+      ok(objectMatches(forkedRecord, test.forked),
+        `${test.description} should fork record`);
+    } else {
+      ok(!test.forked, `${test.description} should not fork record`);
+    }
+
+    ok(objectMatches(reconciledRecord, test.reconciled));
+  }
+});
--- a/browser/extensions/formautofill/test/unit/test_storage_syncfields.js
+++ b/browser/extensions/formautofill/test/unit/test_storage_syncfields.js
@@ -110,17 +110,17 @@ async function checkingSyncChange(action
   ok(subject.wrappedJSObject.sourceSync, "change notification should have source sync");
 }
 
 add_task(async function test_add_sourceSync() {
   let profileStorage = await initProfileStorage(TEST_STORE_FILE_NAME, []);
 
   // Hardcode a guid so that we don't need to generate a dynamic regex
   let guid = "aaaaaaaaaaaa";
-  let testAddr = Object.assign({guid}, TEST_ADDRESS_1);
+  let testAddr = Object.assign({guid, version: 1}, TEST_ADDRESS_1);
 
   await checkingSyncChange("add", () =>
     profileStorage.addresses.add(testAddr, {sourceSync: true}));
 
   let changeCounter = getSyncChangeCounter(profileStorage.addresses, guid);
   equal(changeCounter, 0);
 
   Assert.throws(() =>
@@ -157,19 +157,19 @@ add_task(async function test_add_resurre
   let profileStorage = await initProfileStorage(TEST_STORE_FILE_NAME, []);
 
   let guid = profileStorage.addresses._generateGUID();
 
   // Add a tombstone.
   profileStorage.addresses.add({guid, deleted: true});
 
   // You can't re-add an item with an explicit GUID.
-  let resurrected = Object.assign({}, TEST_ADDRESS_1, {guid});
+  let resurrected = Object.assign({}, TEST_ADDRESS_1, {guid, version: 1});
   Assert.throws(() => profileStorage.addresses.add(resurrected),
-                /"guid" is not a valid field/);
+                /"(guid|version)" is not a valid field/);
 
   // But Sync can!
   let guid3 = profileStorage.addresses.add(resurrected, {sourceSync: true});
   equal(guid, guid3);
 
   let got = profileStorage.addresses.get(guid);
   equal(got["given-name"], TEST_ADDRESS_1["given-name"]);
 });
@@ -205,17 +205,17 @@ add_task(async function test_remove_sour
   equal(getSyncChangeCounter(profileStorage.addresses, guid), 0);
 });
 
 add_task(async function test_remove_sourceSync_unchanged() {
   // Remove a local record without a change counter.
   let profileStorage = await initProfileStorage(TEST_STORE_FILE_NAME, []);
 
   let guid = profileStorage.addresses._generateGUID();
-  let addr = Object.assign({guid}, TEST_ADDRESS_1);
+  let addr = Object.assign({guid, version: 1}, TEST_ADDRESS_1);
   // add a record with sourceSync to guarantee changeCounter == 0
   await checkingSyncChange("add", () =>
     profileStorage.addresses.add(addr, {sourceSync: true}));
 
   equal(getSyncChangeCounter(profileStorage.addresses, guid), 0);
 
   await checkingSyncChange("remove", () =>
     profileStorage.addresses.remove(guid, {sourceSync: true}));
@@ -236,17 +236,18 @@ add_task(async function test_pullSyncCha
   // All should start without sync metadata
   for (let {guid} of profileStorage.addresses._store.data.addresses) {
     let changeCounter = getSyncChangeCounter(profileStorage.addresses, guid);
     equal(changeCounter, -1);
   }
   profileStorage.addresses.pullSyncChanges(); // force sync metadata
 
   let addedDirectGUID = profileStorage.addresses._generateGUID();
-  let testAddr = Object.assign({guid: addedDirectGUID}, TEST_ADDRESS_3);
+  let testAddr = Object.assign({guid: addedDirectGUID, version: 1},
+                               TEST_ADDRESS_1, TEST_ADDRESS_3);
 
   await checkingSyncChange("add", () =>
     profileStorage.addresses.add(testAddr, {sourceSync: true}));
 
   let tombstoneGUID = profileStorage.addresses._generateGUID();
   await checkingSyncChange("add", () =>
     profileStorage.addresses.add(
       {guid: tombstoneGUID, deleted: true},
@@ -379,16 +380,17 @@ add_task(async function test_findDuplica
     guid: profileStorage.addresses._generateGUID(),
     version: 1,
     timeCreated,
     timeLastModified,
   }, {sourceSync: true});
 
   strictEqual(profileStorage.addresses.findDuplicateGUID({
     guid: profileStorage.addresses._generateGUID(),
+    version: 1,
     timeCreated,
     timeLastModified,
   }), null, "Should ignore internal fields and malformed records");
 });
 
 add_task(async function test_reset() {
   let profileStorage = await initProfileStorage(TEST_STORE_FILE_NAME,
                                                 [TEST_ADDRESS_1, TEST_ADDRESS_2]);
--- a/browser/extensions/formautofill/test/unit/test_sync.js
+++ b/browser/extensions/formautofill/test/unit/test_sync.js
@@ -7,25 +7,26 @@
 /* import-globals-from ../../../../../services/sync/tests/unit/head_helpers.js */
 /* import-globals-from ../../../../../services/sync/tests/unit/head_http_server.js */
 
 "use strict";
 
 Cu.import("resource://services-sync/service.js");
 Cu.import("resource://services-sync/constants.js");
 Cu.import("resource://testing-common/services/sync/utils.js");
-Cu.import("resource://formautofill/ProfileStorage.jsm");
 
 let {sanitizeStorageObject, AutofillRecord, AddressesEngine} =
   Cu.import("resource://formautofill/FormAutofillSync.jsm", {});
 
 
 Services.prefs.setCharPref("extensions.formautofill.loglevel", "Trace");
 initTestLogging("Trace");
 
+const TEST_STORE_FILE_NAME = "test-profile.json";
+
 const TEST_PROFILE_1 = {
   "given-name": "Timothy",
   "additional-name": "John",
   "family-name": "Berners-Lee",
   organization: "World Wide Web Consortium",
   "street-address": "32 Vassar Street\nMIT Room 32-G524",
   "address-level2": "Cambridge",
   "address-level1": "MA",
@@ -35,17 +36,17 @@ const TEST_PROFILE_1 = {
   email: "timbl@w3.org",
 };
 
 const TEST_PROFILE_2 = {
   "street-address": "Some Address",
   country: "US",
 };
 
-function expectLocalProfiles(expected) {
+function expectLocalProfiles(profileStorage, expected) {
   let profiles = profileStorage.addresses.getAll({
     rawData: true,
     includeDeleted: true,
   });
   expected.sort((a, b) => a.guid.localeCompare(b.guid));
   profiles.sort((a, b) => a.guid.localeCompare(b.guid));
   try {
     deepEqual(profiles.map(p => p.guid), expected.map(p => p.guid));
@@ -61,52 +62,51 @@ function expectLocalProfiles(expected) {
     do_print(JSON.stringify(expected, undefined, 2));
     do_print("against actual profiles:");
     do_print(JSON.stringify(profiles, undefined, 2));
     throw ex;
   }
 }
 
 async function setup() {
-  await profileStorage.initialize();
+  let profileStorage = await initProfileStorage(TEST_STORE_FILE_NAME);
   // should always start with no profiles.
   Assert.equal(profileStorage.addresses.getAll({includeDeleted: true}).length, 0);
 
   Services.prefs.setCharPref("services.sync.log.logger.engine.addresses", "Trace");
   let engine = new AddressesEngine(Service);
   await engine.initialize();
   // Avoid accidental automatic sync due to our own changes
   Service.scheduler.syncThreshold = 10000000;
   let server = serverForUsers({"foo": "password"}, {
     meta: {global: {engines: {addresses: {version: engine.version, syncID: engine.syncID}}}},
     addresses: {},
   });
 
   Service.engineManager._engines.addresses = engine;
   engine.enabled = true;
+  engine._store._storage = profileStorage.addresses;
 
   generateNewKeys(Service.collectionKeys);
 
   await SyncTestingInfrastructure(server);
 
   let collection = server.user("foo").collection("addresses");
 
-  return {server, collection, engine};
+  return {profileStorage, server, collection, engine};
 }
 
 async function cleanup(server) {
   let promiseStartOver = promiseOneObserver("weave:service:start-over:finish");
   await Service.startOver();
   await promiseStartOver;
   await promiseStopServer(server);
-  profileStorage.addresses._nukeAllRecords();
 }
 
 add_task(async function test_log_sanitization() {
-  await profileStorage.initialize();
   let sanitized = sanitizeStorageObject(TEST_PROFILE_1);
   // all strings have been mangled.
   for (let key of Object.keys(TEST_PROFILE_1)) {
     let val = TEST_PROFILE_1[key];
     if (typeof val == "string") {
       notEqual(sanitized[key], val);
     }
   }
@@ -116,29 +116,28 @@ add_task(async function test_log_sanitiz
   let serialized = record.toString();
   // None of the string values should appear in the output.
   for (let key of Object.keys(TEST_PROFILE_1)) {
     let val = TEST_PROFILE_1[key];
     if (typeof val == "string") {
       ok(!serialized.includes(val), `"${val}" shouldn't be in: ${serialized}`);
     }
   }
-  profileStorage.addresses._nukeAllRecords();
 });
 
 add_task(async function test_outgoing() {
-  let {server, collection, engine} = await setup();
+  let {profileStorage, server, collection, engine} = await setup();
   try {
     equal(engine._tracker.score, 0);
     let existingGUID = profileStorage.addresses.add(TEST_PROFILE_1);
     // And a deleted item.
     let deletedGUID = profileStorage.addresses._generateGUID();
     profileStorage.addresses.add({guid: deletedGUID, deleted: true});
 
-    expectLocalProfiles([
+    expectLocalProfiles(profileStorage, [
       {
         guid: existingGUID,
       },
       {
         guid: deletedGUID,
         deleted: true,
       },
     ]);
@@ -148,17 +147,17 @@ add_task(async function test_outgoing() 
 
     engine.lastSync = 0;
     await engine.sync();
 
     Assert.equal(collection.count(), 2);
     Assert.ok(collection.wbo(existingGUID));
     Assert.ok(collection.wbo(deletedGUID));
 
-    expectLocalProfiles([
+    expectLocalProfiles(profileStorage, [
       {
         guid: existingGUID,
       },
       {
         guid: deletedGUID,
         deleted: true,
       },
     ]);
@@ -166,37 +165,39 @@ add_task(async function test_outgoing() 
     strictEqual(getSyncChangeCounter(profileStorage.addresses, existingGUID), 0);
     strictEqual(getSyncChangeCounter(profileStorage.addresses, deletedGUID), 0);
   } finally {
     await cleanup(server);
   }
 });
 
 add_task(async function test_incoming_new() {
-  let {server, engine} = await setup();
+  let {profileStorage, server, engine} = await setup();
   try {
     let profileID = Utils.makeGUID();
     let deletedID = Utils.makeGUID();
 
     server.insertWBO("foo", "addresses", new ServerWBO(profileID, encryptPayload({
       id: profileID,
-      entry: TEST_PROFILE_1,
+      entry: Object.assign({
+        version: 1,
+      }, TEST_PROFILE_1),
     }), Date.now() / 1000));
     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;
     await engine.sync();
 
-    expectLocalProfiles([
+    expectLocalProfiles(profileStorage, [
       {
         guid: profileID,
       }, {
         guid: deletedID,
         deleted: true,
       },
     ]);
 
@@ -206,18 +207,54 @@ 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 {profileStorage, 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.lastSync = 0;
+    await engine.sync();
+
+    // now server records that modify the existing items.
+    let modifiedEntry1 = Object.assign({}, TEST_PROFILE_1, {
+      "version": 1,
+      "given-name": "NewName",
+    });
+
+    server.insertWBO("foo", "addresses", new ServerWBO(guid1, encryptPayload({
+      id: guid1,
+      entry: modifiedEntry1,
+    }), engine.lastSync + 10));
+    server.insertWBO("foo", "addresses", new ServerWBO(guid2, encryptPayload({
+      id: guid2,
+      deleted: true,
+    }), engine.lastSync + 10));
+
+    await engine.sync();
+
+    expectLocalProfiles(profileStorage, [
+      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();
+  let {profileStorage, server, collection, engine} = await setup();
   try {
     let existingGUID = profileStorage.addresses.add(TEST_PROFILE_1);
 
     engine.lastSync = 0;
     await engine.sync();
 
     Assert.equal(collection.count(), 1);
     let payload = collection.payloads()[0];
@@ -232,143 +269,316 @@ 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 {profileStorage, server, engine} = await setup();
+  try {
+    let guid = profileStorage.addresses.add(TEST_PROFILE_1);
+
+    engine.lastSync = 0;
+    await 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,
+    }), engine.lastSync + 10);
+
+    await 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 {profileStorage, 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;
+    await 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 {profileStorage, server, engine} = await setup();
+  try {
+    let guid = profileStorage.addresses.add(TEST_PROFILE_1);
+
+    engine.lastSync = 0;
+    await engine.sync();
+
+    // Delete the record remotely.
+    let collection = server.user("foo").collection("addresses");
+    collection.insert(guid, encryptPayload({
+      id: guid,
+      deleted: true,
+    }), engine.lastSync + 10);
+
+    await 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");
+    strictEqual(getSyncChangeCounter(profileStorage.addresses, guid), 0,
+      "Local tombstone should be marked as syncing");
+  } finally {
+    await cleanup(server);
+  }
+});
+
+add_task(async function test_applyIncoming_incoming_restored() {
+  let {profileStorage, server, engine} = await setup();
+  try {
+    let guid = profileStorage.addresses.add(TEST_PROFILE_1);
+
+    // Upload the record to the server.
+    engine.lastSync = 0;
+    await 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), engine.lastSync + 10);
+
+    // Sync again.
+    await engine.sync();
+
+    // We should replace our tombstone with the server's version.
+    let localRecord = profileStorage.addresses.get(guid);
+    ok(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 {profileStorage, server, engine} = await setup();
+  try {
+    let guid = profileStorage.addresses.add(TEST_PROFILE_1);
+
+    // Upload the record to the server.
+    engine.lastSync = 0;
+    await engine.sync();
+
+    // Modify the local record.
+    let localCopy = Object.assign({}, 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,
+    }), engine.lastSync + 10);
+
+    // Sync again.
+    await 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");
+    ok(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();
+  let {profileStorage, 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;
     await engine.sync();
 
-    expectLocalProfiles([{guid}]);
+    expectLocalProfiles(profileStorage, [{guid}]);
   } finally {
     await cleanup(server);
   }
 });
 
 add_task(async function test_incoming_dupes() {
-  let {server, engine} = await setup();
+  let {profileStorage, server, engine} = await setup();
   try {
     // Create a profile locally, then sync to upload the new profile to the
     // server.
     let guid1 = profileStorage.addresses.add(TEST_PROFILE_1);
 
     engine.lastSync = 0;
     await engine.sync();
 
     // Create another profile locally, but don't sync it yet.
     profileStorage.addresses.add(TEST_PROFILE_2);
 
     // Now create two records on the server with the same contents as our local
     // profiles, but different GUIDs.
     let guid1_dupe = Utils.makeGUID();
     server.insertWBO("foo", "addresses", new ServerWBO(guid1_dupe, encryptPayload({
       id: guid1_dupe,
-      entry: TEST_PROFILE_1,
+      entry: Object.assign({
+        version: 1,
+      }, TEST_PROFILE_1),
     }), engine.lastSync + 10));
     let guid2_dupe = Utils.makeGUID();
     server.insertWBO("foo", "addresses", new ServerWBO(guid2_dupe, encryptPayload({
       id: guid2_dupe,
-      entry: TEST_PROFILE_2,
+      entry: Object.assign({
+        version: 1,
+      }, TEST_PROFILE_2),
     }), engine.lastSync + 10));
 
     // Sync again. We should download `guid1_dupe` and `guid2_dupe`, then
     // reconcile changes.
     await engine.sync();
 
-    expectLocalProfiles([
+    expectLocalProfiles(profileStorage, [
       // We uploaded `guid1` during the first sync. Even though its contents
       // are the same as `guid1_dupe`, we keep both.
       Object.assign({}, TEST_PROFILE_1, {guid: guid1}),
       Object.assign({}, TEST_PROFILE_1, {guid: guid1_dupe}),
       // However, we didn't upload `guid2` before downloading `guid2_dupe`, so
       // we *should* dedupe `guid2` to `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();
+  let {profileStorage, 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();
     notEqual(localGuid, remoteGuid);
     server.insertWBO("foo", "addresses", new ServerWBO(remoteGuid, encryptPayload({
       id: remoteGuid,
-      entry: TEST_PROFILE_1,
+      entry: Object.assign({
+        version: 1,
+      }, TEST_PROFILE_1),
     }), Date.now() / 1000));
 
     engine.lastSync = 0;
     await engine.sync();
 
     // Should have 1 item locally with GUID changed to the remote one.
     // There's no tombstone as the original was unsynced.
-    expectLocalProfiles([
+    expectLocalProfiles(profileStorage, [
       {
         guid: remoteGuid,
       },
     ]);
   } finally {
     await cleanup(server);
   }
 });
 
 add_task(async function test_dedupe_identical_synced() {
-  let {server, engine} = await setup();
+  let {profileStorage, 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.lastSync = 0;
     await 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,
+      entry: Object.assign({
+        version: 1,
+      }, TEST_PROFILE_1),
     }), engine.lastSync + 10));
 
     await engine.sync();
 
     // Should have 2 items locally, since the first was synced.
-    expectLocalProfiles([
+    expectLocalProfiles(profileStorage, [
       {guid: localGuid},
       {guid: remoteGuid},
     ]);
   } finally {
     await cleanup(server);
   }
 });
 
 add_task(async function test_dedupe_multiple_candidates() {
-  let {server, engine} = await setup();
+  let {profileStorage, server, engine} = await setup();
   try {
     // It's possible to have duplicate local profiles, with the same fields but
     // different GUIDs. After a node reassignment, or after disconnecting and
     // reconnecting to Sync, we might dedupe a local record A to a remote record
     // B, if we see B before we download and apply A. Since A and B are dupes,
     // that's OK. We'll write a tombstone for A when we dedupe A to B, and
     // overwrite that tombstone when we see A.
 
@@ -395,17 +605,17 @@ add_task(async function test_dedupe_mult
     server.insertWBO("foo", "addresses", new ServerWBO(aGuid, encryptPayload({
       id: aGuid,
       entry: serverRecord,
     }), Date.now() / 1000));
 
     engine.lastSync = 0;
     await engine.sync();
 
-    expectLocalProfiles([
+    expectLocalProfiles(profileStorage, [
       {
         "guid": aGuid,
         "given-name": "Mark",
         "family-name": "Hammond",
         "organization": "Mozilla",
         "country": "AU",
         "tel": "+12345678910",
       },
@@ -422,8 +632,68 @@ add_task(async function test_dedupe_mult
     strictEqual(getSyncChangeCounter(profileStorage.addresses, aGuid), 0,
       "A should be marked as syncing");
     strictEqual(getSyncChangeCounter(profileStorage.addresses, bGuid), 0,
       "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 {profileStorage, server, engine} = await setup();
+  try {
+    // create a record locally.
+    let guid = profileStorage.addresses.add(TEST_PROFILE_1);
+
+    // Upload the record to the server.
+    engine.lastSync = 0;
+    await engine.sync();
+
+    strictEqual(getSyncChangeCounter(profileStorage.addresses, guid), 0,
+      "Original record should be marked as syncing");
+
+    // Change the same field locally and on the server.
+    let localCopy = Object.assign({}, 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), engine.lastSync + 10);
+
+    // Sync again.
+    await engine.sync();
+
+    // 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(profileStorage, [
+      {
+        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!",
+      },
+    ]);
+
+    let changeCounter = getSyncChangeCounter(profileStorage.addresses,
+      forkedPayload.id);
+    strictEqual(changeCounter, 0,
+      "Forked record should be marked as syncing");
+  } finally {
+    await cleanup(server);
+  }
+});
--- a/browser/extensions/formautofill/test/unit/test_transformFields.js
+++ b/browser/extensions/formautofill/test/unit/test_transformFields.js
@@ -536,17 +536,17 @@ add_task(async function test_normalizeAd
   await profileStorage.initialize();
 
   ADDRESS_NORMALIZE_TESTCASES.forEach(testcase => profileStorage.addresses.add(testcase.address));
   await profileStorage._saveImmediately();
 
   profileStorage = new ProfileStorage(path);
   await profileStorage.initialize();
 
-  let addresses = profileStorage.addresses.getAll({noComputedFields: true});
+  let addresses = profileStorage.addresses.getAll();
 
   for (let i in addresses) {
     do_print("Verify testcase: " + ADDRESS_NORMALIZE_TESTCASES[i].description);
     do_check_record_matches(ADDRESS_NORMALIZE_TESTCASES[i].expectedResult, addresses[i]);
   }
 });
 
 add_task(async function test_computeCreditCardFields() {
--- a/browser/extensions/formautofill/test/unit/xpcshell.ini
+++ b/browser/extensions/formautofill/test/unit/xpcshell.ini
@@ -30,15 +30,16 @@ support-files =
 [test_isCJKName.js]
 [test_isFieldEligibleForAutofill.js]
 [test_markAsAutofillField.js]
 [test_migrateRecords.js]
 [test_nameUtils.js]
 [test_onFormSubmitted.js]
 [test_profileAutocompleteResult.js]
 [test_phoneNumber.js]
+[test_reconcile.js]
 [test_savedFieldNames.js]
 [test_toOneLineAddress.js]
 [test_storage_tombstones.js]
 [test_storage_syncfields.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