Todo List

So far, we’ve focused on Y.Map. Let’s spend some time on another important shared type: Y.Array.

This is a simple todo list. You can drag items around to reorder them and click the checkbox to check them off.

Here’s what the data looks like in JSON:

[
  { "id": "1", "text": "Check mail", "done": false },
  { "id": "2", "text": "Sweep floor", "done": false },
  { "id": "3", "text": "Buy milk", "done": false }
]

How would you implement the reordering functionality?

You might think we could just modify the array. If we had a normal JavaScript array, we could write something like this:

function move(todos, from, to) {
  // remove the todo from the `from` index…
  const [todo] = todos.splice(from, 1);

  // …and insert it at the `to` index
  todos.splice(to, 0, todo);
}

Just like before, though, things can get wonky when we start adding latency. See if you can break this one:

Did you manage to find a bug? Take a moment to think about why that might have happened before moving on.

Distributed Gotchas

Here’s a curious fact about Yjs. Once you add a shared type to a document, it can never be moved. You can change what it contains and you can delete it, but you can’t move it from one place to another.

That probably seems odd. There’s no way Yjs won’t let you reorder items in arrays, right?

Consider what the normal JavaScript code above is actually doing: first removing the element from the array, and second adding it somewhere else. “Move” is actually implemented as “delete” and “insert”.

Here’s a playground with a timeline, so you can see what’s happening under the hood:

Each client deletes a todo and inserts an identical one somewhere else. The issue is that Yjs doesn’t understand that there’s a connection between the delete and insert. As far as it can tell, the deleted item is totally unrelated to the inserted item.

If you made conflicting edits, there are two things that could have gone wrong:

1. You lost a checkmark. On one client you checked or unchecked a todo, while on the other client you moved that same todo. That move deleted the todo you checked or unchecked, and the copy inserted elsewhere didn’t have the updated checkmark.
2. You duplicated an item. On each client, you moved the same todo to different places. Since delete is an idempotent operation, there’s no problem if both clients do it at the same time. But as far as Yjs knows, each insert is different — even if the item being inserted is superficially the same.

Can you come up with a way to model the data that avoids this issue? Think about it before continuing!

A Better Data Model

Instead of keeping the todos in an array, try keeping them in a map.

Like its JavaScript counterpart, Y.Map is technically ordered by when each key was inserted. That won’t work for us, though: we want to be able to rearrange the todos into any order.

We can solve this by adding an index property to each todo. The ordered list of todos is an array of the map values sorted by the index property. To move a todo, simply set a new index!

While that sort of works works, it presents a new problem. If you move a todo before another one, wouldn’t you need to change that todo’s index as well? Come to think of it, wouldn’t you need to change every subsequent todo’s index?

The trick is a technique called fractional indexing, in which indices are fractions rather than integers.

Each item receives a fraction between 0 and 1, exclusive. To move an item, simply set its index to a fraction between the two adjacent items’ indices. Usually, that’s as simple as taking the average of the two indices: add them together and divide by two.

The “exclusive” part is important. Because no item will ever have an index of 0 or 1, those numbers can be used to move items to the extremes of the list. Moving an item to the beginning of the list means finding a fraction between 0 and the first item, while moving an item to the end means finding a fraction between the last item and 1.

Excercise 1

Let’s try implementing fractional indexing. We’ll be creating two functions:

• getTodos(map) takes a map of todos and returns them in an array, sorted in ascending order by their index property.
• move(map, from, to) takes a map of todos and a from and to index, and moves the todo from one to the other.

Implement the functions to rearrange and sort the todos using their fractional indices. Remember, there are hints and unit tests below to help you!

export function getTodos(map) {
  const values = [...map.values()];
  return values.sort((a, b) => a.get('index') - b.get('index'));
}

export function move(map, from, to) {
  const todos = getTodos(map);

  const todo = todos[from];
  if (!todo) return;
}

export function move(map, from, to) {
  // ...

  const earlier = from > to;
  const before = todos[earlier ? to - 1 : to];
  const after = todos[earlier ? to : to + 1];
}

export function move(map, from, to) {
  // ...

  const start = before?.get("index") ?? 0;
  const end = after?.get("index") ?? 1;
}

export function move(map, from, to) {
  // ...

  todo.set("index", (start + end) / 2);
}

export function move(map, from, to) {
  const todos = getTodos(map);

  const todo = todos[from];
  if (!todo) return;

  const earlier = from > to;
  const before = todos[earlier ? to - 1 : to];
  const after = todos[earlier ? to : to + 1];

  const start = before?.get("index") ?? 0;
  const end = after?.get("index") ?? 1;

  todo.set('index', (start + end) / 2);
}

Conflicting Writes

You might have noticed a problem with the fractional indexing algorithm.

Here’s a playground that uses fractional indexing. See if you can find the bug:

With the latency high, drag a different todo to the top on each client. If you look at the document, they’ll both have the same index value.

Try dragging the last todo between them. Now that one has the same index, too!

Two items with the same index is really bad. It means that we can’t ever move any items between them. Since their indices are equal, their average will just be the same number.

Excercise 2

See if you can figure out how to make sure that two todos will never share an index — even if both clients move them to the same spot.

We’ve moved your code from the last exercise over here, so you can pick up where you left off.

export function move(map, from, to) {
  // ...
  const index = (end - start) * (Math.random() + Number.MIN_VALUE) + start;

  todo.set('index', index);
}

export function move(map, from, to) {
  // ...
  const average = (start + end) / 2;

  const range = (end - start) * 1e-1000;
  const jitter = -range / 2 + Math.random() * range;

  todo.set('index', average + jitter);
}

export function move(map, from, to) {
  const todos = getTodos(map);

  const todo = todos[from];
  if (!todo) return;

  const earlier = from > to;
  const before = todos[earlier ? to - 1 : to];
  const after = todos[earlier ? to : to + 1];

  const start = before?.get("index") ?? 0;
  const end = after?.get("index") ?? 1;
  const index = (after - before) * (Math.random() + Number.MIN_VALUE) + before;

  todo.set('index', index);
}