Error occurs when editing Tree due to missing insPrevID in CRDTTree

[chacha912]

What happened:

An error occurs when editing the Tree due to missing insPrevID in the CRDTTree.

The issue seems to stem from incorrect nodes being returned in toTreeNodes because of the absence of the insPrevID information. It seems that the insPrevID might be missing when generating the document from the snapshot.

public toTreeNodes(tree: CRDTTree): [CRDTTreeNode, CRDTTreeNode] {
  // ...

  if (
    !leftSiblingID.equals(parentID) &&
    leftSiblingID.getOffset() > 0 &&
    leftSiblingID.getOffset() === leftNode.id.getOffset() &&
    leftNode.insPrevID
  ) {
    leftNode = tree.findFloorNode(leftNode.insPrevID, true)!;
  }

What you expected to happen:

Editing the Tree should work without encountering errors.

How to reproduce it (as minimally and precisely as possible):

To reproduce the issue, you can run the following test code:

it.only('tree delete test', async function ({ task }) {
  type TestDoc = { t: Tree; num: number };
  const docKey = toDocKey(`${task.name}-${new Date().getTime()}`);

  const d1 = new yorkie.Document<TestDoc>(docKey);
  const d2 = new yorkie.Document<TestDoc>(docKey);

  const c1 = new yorkie.Client(testRPCAddr);
  const c2 = new yorkie.Client(testRPCAddr);

  await c1.activate();
  await c2.activate();

  await c1.attach(d1, { isRealtimeSync: false });
  await c2.attach(d2, { isRealtimeSync: false });

  // Perform a dummy update to apply changes up to the snapshot threshold.
  const snapshotThreshold = 500;
  for (let idx = 0; idx < snapshotThreshold; idx++) {
    d1.update((root) => {
      root.num = 0;
    });
  }

  // Start scenario.
  d1.update((root) => {
    root.t = new Tree({
      type: 'r',
      children: [
        {
          type: 'c',
          children: [
            {
              type: 'u',
              children: [
                {
                  type: 'p',
                  children: [
                    {
                      type: 'n',
                      children: [],
                    },
                  ],
                },
              ],
            },
          ],
        },
        {
          type: 'c',
          children: [
            {
              type: 'p',
              children: [
                {
                  type: 'n',
                  children: [],
                },
              ],
            },
          ],
        },
      ],
    });
  });
  await c1.sync();
  await c2.sync();
  assert.equal(
    d1.getRoot().t.toXML(),
    /*html*/ `<r><c><u><p><n></n></p></u></c><c><p><n></n></p></c></r>`,
  );
  assert.equal(
    d2.getRoot().t.toXML(),
    /*html*/ `<r><c><u><p><n></n></p></u></c><c><p><n></n></p></c></r>`,
  );

  d1.update((r, p) => {
    r.t.editByPath([1, 0, 0, 0], [1, 0, 0, 0], {
      type: 'text',
      value: '1',
    });
    r.t.editByPath([1, 0, 0, 1], [1, 0, 0, 1], {
      type: 'text',
      value: '2',
    });
    r.t.editByPath([1, 0, 0, 2], [1, 0, 0, 2], {
      type: 'text',
      value: '3',
    });
    r.t.editByPath([1, 0, 0, 2], [1, 0, 0, 2], {
      type: 'text',
      value: ' ',
    });
    r.t.editByPath([1, 0, 0, 3], [1, 0, 0, 3], {
      type: 'text',
      value: '네이버랑 ',
    });
  });
  await c1.sync();
  await c2.sync();
  assert.equal(
    d1.getRoot().t.toXML(),
    /*html*/ `<r><c><u><p><n></n></p></u></c><c><p><n>12 네이버랑 3</n></p></c></r>`,
  );
  assert.equal(
    d2.getRoot().t.toXML(),
    /*html*/ `<r><c><u><p><n></n></p></u></c><c><p><n>12 네이버랑 3</n></p></c></r>`,
  );

  d2.update((r, p) => {
    r.t.editByPath([1, 0, 0, 1], [1, 0, 0, 8], {
      type: 'text',
      value: ' 2 네이버랑 ',
    });
    r.t.editByPath([1, 0, 0, 2], [1, 0, 0, 2], {
      type: 'text',
      value: 'ㅋ',
    });
    r.t.editByPath([1, 0, 0, 2], [1, 0, 0, 3], {
      type: 'text',
      value: '카',
    });
    r.t.editByPath([1, 0, 0, 2], [1, 0, 0, 3], {
      type: 'text',
      value: '캌',
    });
    r.t.editByPath([1, 0, 0, 2], [1, 0, 0, 3], {
      type: 'text',
      value: '카카',
    });
    r.t.editByPath([1, 0, 0, 3], [1, 0, 0, 4], {
      type: 'text',
      value: '캉',
    });
    r.t.editByPath([1, 0, 0, 3], [1, 0, 0, 4], {
      type: 'text',
      value: '카오',
    });
    r.t.editByPath([1, 0, 0, 4], [1, 0, 0, 5], {
      type: 'text',
      value: '올',
    });
    r.t.editByPath([1, 0, 0, 4], [1, 0, 0, 5], {
      type: 'text',
      value: '오라',
    });
    r.t.editByPath([1, 0, 0, 5], [1, 0, 0, 6], {
      type: 'text',
      value: '랑',
    });
    r.t.editByPath([1, 0, 0, 6], [1, 0, 0, 6], {
      type: 'text',
      value: ' ',
    });
  });
  await c2.sync();
  await c1.sync();
  assert.equal(
    d1.getRoot().t.toXML(),
    /*html*/ `<r><c><u><p><n></n></p></u></c><c><p><n>1 카카오랑 2 네이버랑 3</n></p></c></r>`,
  );
  assert.equal(
    d2.getRoot().t.toXML(),
    /*html*/ `<r><c><u><p><n></n></p></u></c><c><p><n>1 카카오랑 2 네이버랑 3</n></p></c></r>`,
  );

  d1.update((r, p) => {
    r.t.editByPath([1, 0, 0, 13], [1, 0, 0, 14]);
    r.t.editByPath([1, 0, 0, 12], [1, 0, 0, 13]);
  });
  await c1.sync();
  await c2.sync();
  assert.equal(
    d1.getRoot().t.toXML(),
    /*html*/ `<r><c><u><p><n></n></p></u></c><c><p><n>1 카카오랑 2 네이버3</n></p></c></r>`,
  );
  assert.equal(
    d2.getRoot().t.toXML(),
    /*html*/ `<r><c><u><p><n></n></p></u></c><c><p><n>1 카카오랑 2 네이버3</n></p></c></r>`,
  );

  d2.update((r, p) => {
    r.t.editByPath([1, 0, 0, 6], [1, 0, 0, 7]);
    r.t.editByPath([1, 0, 0, 5], [1, 0, 0, 6]);
  });
  await c2.sync();
  await c1.sync();
  assert.equal(
    d1.getRoot().t.toXML(),
    /*html*/ `<r><c><u><p><n></n></p></u></c><c><p><n>1 카카오2 네이버3</n></p></c></r>`,
  );
  assert.equal(
    d2.getRoot().t.toXML(),
    /*html*/ `<r><c><u><p><n></n></p></u></c><c><p><n>1 카카오2 네이버3</n></p></c></r>`,
  );

  d1.update((r, p) => {
    r.t.editByPath([1, 0, 0, 9], [1, 0, 0, 10]);
  });
  await c1.sync();
  await c2.sync();
  assert.equal(
    d1.getRoot().t.toXML(),
    /*html*/ `<r><c><u><p><n></n></p></u></c><c><p><n>1 카카오2 네이3</n></p></c></r>`,
  );
  assert.equal(
    d2.getRoot().t.toXML(),
    /*html*/ `<r><c><u><p><n></n></p></u></c><c><p><n>1 카카오2 네이3</n></p></c></r>`,
  );

  // A new client has been added.
  const d3 = new yorkie.Document<TestDoc>(docKey);
  const c3 = new yorkie.Client(testRPCAddr);
  await c3.activate();
  await c3.attach(d3, { isRealtimeSync: false });
  assert.equal(
    d3.getRoot().t.toXML(),
    /*html*/ `<r><c><u><p><n></n></p></u></c><c><p><n>1 카카오2 네이3</n></p></c></r>`,
  );
  await c2.sync();

  d3.update((r, p) => {
    r.t.editByPath([1, 0, 0, 4], [1, 0, 0, 5]);
    r.t.editByPath([1, 0, 0, 3], [1, 0, 0, 4]);
  });
  await c3.sync();
  await c2.sync();
  assert.equal(
    d3.getRoot().t.toXML(),
    /*html*/ `<r><c><u><p><n></n></p></u></c><c><p><n>1 카2 네이3</n></p></c></r>`,
  );
  assert.equal(
    d2.getRoot().t.toXML(),
    /*html*/ `<r><c><u><p><n></n></p></u></c><c><p><n>1 카2 네이3</n></p></c></r>`,
  );

  // debugger;
  d3.update((r, p) => {
    r.t.editByPath([1, 0, 0, 2], [1, 0, 0, 3]);
  });

  await c3.sync();
  await c2.sync();
  assert.equal(
    d3.getRoot().t.toXML(),
    /*html*/ `<r><c><u><p><n></n></p></u></c><c><p><n>1 2 네이3</n></p></c></r>`,
  );
  assert.equal(
    d2.getRoot().t.toXML(),
    /*html*/ `<r><c><u><p><n></n></p></u></c><c><p><n>1 2 네이3</n></p></c></r>`,
  );

  await c1.deactivate();
  await c2.deactivate();
  await c3.deactivate();
});

Anything else we need to know?:

Environment:

• Operating system:
• Browser and version:
• Yorkie version (use yorkie version):
• Yorkie JS SDK version: