--- a/browser/extensions/formautofill/FormAutofillSync.jsm
+++ b/browser/extensions/formautofill/FormAutofillSync.jsm
@@ -12,16 +12,18 @@ Cu.import("resource://gre/modules/Servic
 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");
 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;
   }
@@ -140,34 +142,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,17 @@ 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},
+  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(
@@ -380,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