Repository: apollographql/apollo-client

Problem statement:
Cache does not merge fragments correctly
**Intended outcome:**
Complex fragment merges work as though they were all specified in a single large query

**Actual outcome:**
Fragment merges can result in the cache dropping fields, which ends up returning an empty value from useQuery when ``returnPartialData`` is off, and misses fields when ``returnPartialData`` is on.

**How to reproduce the issue:**
https://github.com/chrbala/apollo-bug-repro/tree/data-missing

As the repo is presented, the data comes back empty, and there is a warning about cache data getting lost. Note that the [data comes back correctly](https://github.com/chrbala/apollo-bug-repro/blob/data-missing/src/index.jsx#L49) from the "server", but is corrupted in the cache.

* If ``returnPartialData`` is used, the query returns a value, but the ``text`` field is missing from the data.
* If the ``text`` field [on line 86](https://github.com/chrbala/apollo-bug-repro/blob/data-missing/src/index.jsx#L86) is replaced with ``__typename`` (the same as the contents of ``ItemFragment``), the query succeeds. This is likely because there are no conflicts for the item.
* If ``...ValueFragment`` is removed from [line 82](https://github.com/chrbala/apollo-bug-repro/blob/data-missing/src/index.jsx#L82), the query succeeds. This is likely because there are no conflicts for the item.
* If the ``id`` field is removed from [line 84](https://github.com/chrbala/apollo-bug-repro/blob/data-missing/src/index.jsx#L84), the query succeeds. This is likely because the item is included in the parent's item in the cache and is no longer normalized.

There appears to be a very broad issue (#8063) that shares this outcome, but this seems to be one of likely many root causes, so I thought it was appropriate to open a unique issue here.

**Versions**
  System:
    OS: macOS Mojave 10.14.6
  Binaries:
    Node: 12.13.1 - /usr/local/bin/node
    Yarn: 1.22.10 - /usr/local/bin/yarn
    npm: 6.12.1 - /usr/local/bin/npm
  Browsers:
    Chrome: 91.0.4472.77
    Firefox: 89.0
    Safari: 14.1
  npmPackages:
    @apollo/client: ^3.3.19 => 3.3.20 


Hints:

Patch:
diff --git a/src/cache/inmemory/writeToStore.ts b/src/cache/inmemory/writeToStore.ts
--- a/src/cache/inmemory/writeToStore.ts
+++ b/src/cache/inmemory/writeToStore.ts
@@ -1,4 +1,4 @@
-import { SelectionSetNode, FieldNode } from 'graphql';
+import { SelectionSetNode, FieldNode, SelectionNode } from 'graphql';
 import { invariant, InvariantError } from 'ts-invariant';
 import { equal } from '@wry/equality';
 
@@ -39,6 +39,11 @@ export interface WriteContext extends ReadMergeModifyContext {
   merge<T>(existing: T, incoming: T): T;
   // If true, merge functions will be called with undefined existing data.
   overwrite: boolean;
+  incomingById: Map<string, {
+    fields: StoreObject;
+    mergeTree: MergeTree;
+    selections: Set<SelectionNode>;
+  }>;
 };
 
 interface ProcessSelectionSetOptions {
@@ -70,28 +75,75 @@ export class StoreWriter {
       ...variables!,
     };
 
+    const context: WriteContext = {
+      store,
+      written: Object.create(null),
+      merge<T>(existing: T, incoming: T) {
+        return merger.merge(existing, incoming) as T;
+      },
+      variables,
+      varString: canonicalStringify(variables),
+      fragmentMap: createFragmentMap(getFragmentDefinitions(query)),
+      overwrite: !!overwrite,
+      incomingById: new Map,
+    };
+
     const ref = this.processSelectionSet({
       result: result || Object.create(null),
       dataId,
       selectionSet: operationDefinition.selectionSet,
       mergeTree: { map: new Map },
-      context: {
-        store,
-        written: Object.create(null),
-        merge<T>(existing: T, incoming: T) {
-          return merger.merge(existing, incoming) as T;
-        },
-        variables,
-        varString: canonicalStringify(variables),
-        fragmentMap: createFragmentMap(getFragmentDefinitions(query)),
-        overwrite: !!overwrite,
-      },
+      context,
     });
 
     if (!isReference(ref)) {
       throw new InvariantError(`Could not identify object ${JSON.stringify(result)}`);
     }
 
+    // So far, the store has not been modified, so now it's time to process
+    // context.incomingById and merge those incoming fields into context.store.
+    context.incomingById.forEach(({ fields, mergeTree, selections }, dataId) => {
+      const entityRef = makeReference(dataId);
+
+      if (mergeTree.map.size) {
+        fields = this.applyMerges(mergeTree, entityRef, fields, context);
+      }
+
+      if (process.env.NODE_ENV !== "production" && !context.overwrite) {
+        const hasSelectionSet = (storeFieldName: string) =>
+          fieldsWithSelectionSets.has(fieldNameFromStoreName(storeFieldName));
+        const fieldsWithSelectionSets = new Set<string>();
+        selections.forEach(selection => {
+          if (isField(selection) && selection.selectionSet) {
+            fieldsWithSelectionSets.add(selection.name.value);
+          }
+        });
+
+        const hasMergeFunction = (storeFieldName: string) => {
+          const childTree = mergeTree.map.get(storeFieldName);
+          return Boolean(childTree && childTree.info && childTree.info.merge);
+        };
+
+        Object.keys(fields).forEach(storeFieldName => {
+          // If a merge function was defined for this field, trust that it
+          // did the right thing about (not) clobbering data. If the field
+          // has no selection set, it's a scalar field, so it doesn't need
+          // a merge function (even if it's an object, like JSON data).
+          if (hasSelectionSet(storeFieldName) &&
+              !hasMergeFunction(storeFieldName)) {
+            warnAboutDataLoss(
+              entityRef,
+              fields,
+              storeFieldName,
+              context.store,
+            );
+          }
+        });
+      }
+
+      store.merge(dataId, fields);
+    });
+
     // Any IDs written explicitly to the cache will be retained as
     // reachable root IDs for garbage collection purposes. Although this
     // logic includes root IDs like ROOT_QUERY and ROOT_MUTATION, their
@@ -170,9 +222,9 @@ export class StoreWriter {
       incomingFields.__typename = typename;
     }
 
-    const workSet = new Set(selectionSet.selections);
+    const selections = new Set(selectionSet.selections);
 
-    workSet.forEach(selection => {
+    selections.forEach(selection => {
       if (!shouldInclude(selection, context.variables)) return;
 
       if (isField(selection)) {
@@ -192,9 +244,41 @@ export class StoreWriter {
           let incomingValue =
             this.processFieldValue(value, selection, context, childTree);
 
-          const childTypename = selection.selectionSet
-            && context.store.getFieldValue<string>(incomingValue as StoreObject, "__typename")
-            || void 0;
+          // To determine if this field holds a child object with a merge
+          // function defined in its type policy (see PR #7070), we need to
+          // figure out the child object's __typename.
+          let childTypename: string | undefined;
+
+          // The field's value can be an object that has a __typename only if
+          // the field has a selection set. Otherwise incomingValue is scalar.
+          if (selection.selectionSet) {
+            // We attempt to find the child __typename first in context.store,
+            // but the child object may not exist in the store yet, likely
+            // because it's being written for the first time, during this very
+            // call to writeToStore. Note: if incomingValue is a non-normalized
+            // StoreObject (not a Reference), getFieldValue will read from that
+            // object's properties to find its __typename.
+            childTypename = context.store.getFieldValue<string>(
+              incomingValue as StoreObject | Reference,
+              "__typename",
+            );
+
+            // If the child object is being written for the first time, but
+            // incomingValue is a Reference, then the entity that Reference
+            // identifies should have an entry in context.incomingById, which
+            // likely contains a __typename field we can use. After all, how
+            // could we know the object's ID if it had no __typename? If we
+            // wrote data into context.store as each processSelectionSet call
+            // finished processing an entity object, the child object would
+            // already be in context.store, so we wouldn't need this extra
+            // check, but holding all context.store.merge calls until after
+            // we've finished all processSelectionSet work is cleaner and solves
+            // other problems, such as issue #8370.
+            if (!childTypename && isReference(incomingValue)) {
+              const info = context.incomingById.get(incomingValue.__ref);
+              childTypename = info && info.fields.__typename;
+            }
+          }
 
           const merge = policies.getMergeFunction(
             typename,
@@ -257,53 +341,29 @@ export class StoreWriter {
             // __typename strings produced by server/schema changes, which
             // would otherwise be breaking changes.
             policies.fragmentMatches(fragment, typename, result, context.variables)) {
-          fragment.selectionSet.selections.forEach(workSet.add, workSet);
+          fragment.selectionSet.selections.forEach(selections.add, selections);
         }
       }
     });
 
     if ("string" === typeof dataId) {
-      const entityRef = makeReference(dataId);
-
-      if (mergeTree.map.size) {
-        incomingFields = this.applyMerges(mergeTree, entityRef, incomingFields, context);
-      }
-
-      if (process.env.NODE_ENV !== "production" && !context.overwrite) {
-        const hasSelectionSet = (storeFieldName: string) =>
-          fieldsWithSelectionSets.has(fieldNameFromStoreName(storeFieldName));
-        const fieldsWithSelectionSets = new Set<string>();
-        workSet.forEach(selection => {
-          if (isField(selection) && selection.selectionSet) {
-            fieldsWithSelectionSets.add(selection.name.value);
-          }
-        });
-
-        const hasMergeFunction = (storeFieldName: string) => {
-          const childTree = mergeTree.map.get(storeFieldName);
-          return Boolean(childTree && childTree.info && childTree.info.merge);
-        };
-
-        Object.keys(incomingFields).forEach(storeFieldName => {
-          // If a merge function was defined for this field, trust that it
-          // did the right thing about (not) clobbering data. If the field
-          // has no selection set, it's a scalar field, so it doesn't need
-          // a merge function (even if it's an object, like JSON data).
-          if (hasSelectionSet(storeFieldName) &&
-              !hasMergeFunction(storeFieldName)) {
-            warnAboutDataLoss(
-              entityRef,
-              incomingFields,
-              storeFieldName,
-              context.store,
-            );
-          }
+      const previous = context.incomingById.get(dataId);
+      if (previous) {
+        previous.fields = context.merge(previous.fields, incomingFields);
+        previous.mergeTree = mergeMergeTrees(previous.mergeTree, mergeTree);
+        // Add all previous SelectionNode objects, rather than creating a new
+        // Set, since the original unmerged selections Set is not going to be
+        // needed again (only the merged Set).
+        previous.selections.forEach(selections.add, selections);
+        previous.selections = selections;
+      } else {
+        context.incomingById.set(dataId, {
+          fields: incomingFields,
+          mergeTree,
+          selections,
         });
       }
-
-      context.store.merge(dataId, incomingFields);
-
-      return entityRef;
+      return makeReference(dataId);
     }
 
     return incomingFields;
@@ -388,11 +448,13 @@ export class StoreWriter {
       };
 
       mergeTree.map.forEach((childTree, storeFieldName) => {
+        const eVal = getValue(e, storeFieldName);
+        const iVal = getValue(i, storeFieldName);
+        // If we have no incoming data, leave any existing data untouched.
+        if (void 0 === iVal) return;
         if (getStorageArgs) {
           getStorageArgs.push(storeFieldName);
         }
-        const eVal = getValue(e, storeFieldName);
-        const iVal = getValue(i, storeFieldName);
         const aVal = this.applyMerges(
           childTree,
           eVal,
@@ -444,14 +506,59 @@ function getChildMergeTree(
   return map.get(name)!;
 }
 
+function mergeMergeTrees(
+  left: MergeTree | undefined,
+  right: MergeTree | undefined,
+): MergeTree {
+  if (left === right || !right || mergeTreeIsEmpty(right)) return left!;
+  if (!left || mergeTreeIsEmpty(left)) return right;
+
+  const info = left.info && right.info ? {
+    ...left.info,
+    ...right.info,
+  } : left.info || right.info;
+
+  const needToMergeMaps = left.map.size && right.map.size;
+  const map = needToMergeMaps ? new Map :
+    left.map.size ? left.map : right.map;
+
+  const merged = { info, map };
+
+  if (needToMergeMaps) {
+    const remainingRightKeys = new Set(right.map.keys());
+
+    left.map.forEach((leftTree, key) => {
+      merged.map.set(
+        key,
+        mergeMergeTrees(leftTree, right.map.get(key)),
+      );
+      remainingRightKeys.delete(key);
+    });
+
+    remainingRightKeys.forEach(key => {
+      merged.map.set(
+        key,
+        mergeMergeTrees(
+          right.map.get(key),
+          left.map.get(key),
+        ),
+      );
+    });
+  }
+
+  return merged;
+}
+
+function mergeTreeIsEmpty(tree: MergeTree | undefined): boolean {
+  return !tree || !(tree.info || tree.map.size);
+}
+
 function maybeRecycleChildMergeTree(
   { map }: MergeTree,
   name: string | number,
 ) {
   const childTree = map.get(name);
-  if (childTree &&
-      !childTree.info &&
-      !childTree.map.size) {
+  if (childTree && mergeTreeIsEmpty(childTree)) {
     emptyMergeTreePool.push(childTree);
     map.delete(name);
   }


Test patch:
diff --git a/src/cache/inmemory/__tests__/__snapshots__/writeToStore.ts.snap b/src/cache/inmemory/__tests__/__snapshots__/writeToStore.ts.snap
--- a/src/cache/inmemory/__tests__/__snapshots__/writeToStore.ts.snap
+++ b/src/cache/inmemory/__tests__/__snapshots__/writeToStore.ts.snap
@@ -34,6 +34,70 @@ Object {
 }
 `;
 
+exports[`writing to the store correctly merges fragment fields along multiple paths 1`] = `
+Object {
+  "Item:0f47f85d-8081-466e-9121-c94069a77c3e": Object {
+    "__typename": "Item",
+    "id": "0f47f85d-8081-466e-9121-c94069a77c3e",
+    "value": Object {
+      "__typename": "Container",
+      "value": Object {
+        "__typename": "Value",
+        "item": Object {
+          "__ref": "Item:6dc3530b-6731-435e-b12a-0089d0ae05ac",
+        },
+      },
+    },
+  },
+  "Item:6dc3530b-6731-435e-b12a-0089d0ae05ac": Object {
+    "__typename": "Item",
+    "id": "6dc3530b-6731-435e-b12a-0089d0ae05ac",
+    "value": Object {
+      "__typename": "Container",
+      "text": "Hello World",
+      "value": Object {
+        "__typename": "Value",
+      },
+    },
+  },
+  "ROOT_QUERY": Object {
+    "__typename": "Query",
+    "item({\\"id\\":\\"123\\"})": Object {
+      "__ref": "Item:0f47f85d-8081-466e-9121-c94069a77c3e",
+    },
+  },
+}
+`;
+
+exports[`writing to the store should respect id fields added by fragments 1`] = `
+Object {
+  "AType:a-id": Object {
+    "__typename": "AType",
+    "b": Array [
+      Object {
+        "__ref": "BType:b-id",
+      },
+    ],
+    "id": "a-id",
+  },
+  "BType:b-id": Object {
+    "__typename": "BType",
+    "c": Object {
+      "__typename": "CType",
+      "title": "Your experience",
+      "titleSize": null,
+    },
+    "id": "b-id",
+  },
+  "ROOT_QUERY": Object {
+    "__typename": "Query",
+    "a": Object {
+      "__ref": "AType:a-id",
+    },
+  },
+}
+`;
+
 exports[`writing to the store user objects should be able to have { __typename: "Mutation" } 1`] = `
 Object {
   "Gene:{\\"id\\":\\"SLC45A2\\"}": Object {
diff --git a/src/cache/inmemory/__tests__/writeToStore.ts b/src/cache/inmemory/__tests__/writeToStore.ts
--- a/src/cache/inmemory/__tests__/writeToStore.ts
+++ b/src/cache/inmemory/__tests__/writeToStore.ts
@@ -1402,6 +1402,145 @@ describe('writing to the store', () => {
     });
   });
 
+  it('correctly merges fragment fields along multiple paths', () => {
+    const cache = new InMemoryCache({
+      typePolicies: {
+        Container: {
+          // Uncommenting this line fixes the test, but should not be necessary,
+          // since the Container response object in question has the same
+          // identity along both paths.
+          // merge: true,
+        },
+      },
+    });
+
+    const query = gql`
+      query Query {
+        item(id: "123") {
+          id
+          value {
+            ...ContainerFragment
+          }
+        }
+      }
+
+      fragment ContainerFragment on Container {
+        value {
+          ...ValueFragment
+          item {
+            id
+            value {
+              text
+            }
+          }
+        }
+      }
+
+      fragment ValueFragment on Value {
+        item {
+          ...ItemFragment
+        }
+      }
+
+      fragment ItemFragment on Item {
+        value {
+          value {
+            __typename
+          }
+        }
+      }
+    `;
+
+    const data = {
+      item: {
+        __typename: "Item",
+        id: "0f47f85d-8081-466e-9121-c94069a77c3e",
+        value: {
+          __typename: "Container",
+          value: {
+            __typename: "Value",
+            item: {
+              __typename: "Item",
+              id: "6dc3530b-6731-435e-b12a-0089d0ae05ac",
+              value: {
+                __typename: "Container",
+                text: "Hello World",
+                value: {
+                  __typename: "Value"
+                },
+              },
+            },
+          },
+        },
+      },
+    };
+
+    cache.writeQuery({
+      query,
+      data,
+    });
+
+    expect(cache.readQuery({ query })).toEqual(data);
+    expect(cache.extract()).toMatchSnapshot();
+  });
+
+  it('should respect id fields added by fragments', () => {
+    const query = gql`
+      query ABCQuery {
+        __typename
+        a {
+          __typename
+          id
+          ...SharedFragment
+          b {
+            __typename
+            c {
+              __typename
+              title
+              titleSize
+            }
+          }
+        }
+      }
+      fragment SharedFragment on AShared {
+        __typename
+        b {
+          __typename
+          id
+          c {
+            __typename
+          }
+        }
+      }
+    `;
+
+    const data = {
+      __typename: "Query",
+      a: {
+        __typename: "AType",
+        id: "a-id",
+        b: [{
+          __typename: "BType",
+          id: "b-id",
+          c: {
+            __typename: "CType",
+            title: "Your experience",
+            titleSize: null
+          },
+        }],
+      },
+    };
+
+    const cache = new InMemoryCache({
+      possibleTypes: { AShared: ["AType"] }
+    });
+
+    cache.writeQuery({ query, data });
+    expect(cache.readQuery({ query })).toEqual(data);
+
+    expect(cache.extract()).toMatchSnapshot();
+  });
+
   it('should allow a union of objects of a different type, when overwriting a generated id with a real id', () => {
     const dataWithPlaceholder = {
       author: {