Gooey internals: keyless lists

Over the past few years, I’ve been building a frontend web framework called Gooey. This article is part of a series around how it works:

• Gooey internals: keyless lists
• Gooey internals: simplifying the graph

Frontend frameworks are usually be placed into one of two categories: “keyed” and “non-keyed”.

Stefan Krause—who has made the JS Framework Benchmark since 2016—describes the distinction in his post, JS web frameworks benchmark – keyed vs. non-keyed.

But this “keyed”/“non-keyed” distinction is a false dichotomy.

Gooey behaves like a keyed framework. All DOM nodes always map to the same list item. But you don’t need to give each item a key prop at all!

Gooey is keyless: you get all the benefits of a keyed framework without needing to do additional work.

Let’s dig into how Gooey manages to do this.

Here’s what the same list-rendering code looks like in React and Gooey:

const defaultItems = [
  { key: 'a', value: 'one' },
  { key: 'b', value: 'two' },
  { key: 'c', value: 'three' },
];

let nextCharacter = 3;
const makeNewItem = () => ({
  key: String.fromCharCode(0x61 + nextCharacter++),
  value: 'new item',
});

const MyComponent = ({ items }) => {
  return (
    <ul>{items.map((item) => (
      <li key={item.key}>{item.value}</li>
    ))}</ul>
  );
};

const App = () => {
  const [items, setItems] = useState(defaultItems);
  return (
    <div>
      <MyComponent items={items} />
      <button onClick={() => setItems([...items, makeNewItem()])}>
        Add item
      </button>
    </div>
  );
}

const defaultItems = [
  { value: 'one' },
  { value: 'two' },
  { value: 'three' },
);

const makeNewItem = () => ({
  value: 'new item',
});

const MyComponent = ({ items }) => (
  <ul>{items.mapView((item) => (
    <li>{item.value}</li>
  ))}</ul>
);

const App = () => {
  const items = collection(defaultItems);
  return (
    <div>
      <MyComponent items={items} />
      <button on:click={() => items.push(makeNewItem())}>
        Add item
      </button>
    </div>
  );
}

These are structurally similar, but have a few small differences:

• React uses useState() to hold items, and changes to items create an entirely new array
• Gooey uses a collection() to hold items, and it is able to be mutated via .push()
• Gooey uses a .mapView() function to create a mapped view that is bound to the DOM

But how they go about displaying and updating these list items is very different:

React first renders MyComponent with an array of items and associates each key with each <li> JSX node rendered.

When the items prop is replaced by a new array, it does a virtual DOM diff, comparing the previous list of key values against the new set. React reuses the <li> DOM nodes which match prior key values.

Gooey first renders MyComponent with a collection of items, which is mapped to a dynamic “view” of <li> elements.

When the items collection has an additional item added via .push(), Gooey renders that new <li> item via the mapping function and adds it to the DOM in the same place the item was added to the collection. The preexisting <li> DOM nodes are untouched.

No virtual DOM diffing is performed and no redundant array of items are allocated/garbage collected.

React needs key props so it can find out what has changed in an array.

Gooey sees each array operation, so it knows what has changed in an array.

There are only a few things you really can do to change an array.

You can add & remove items and you can reorder them. This can be distilled into two operations: splice and sort.

Sorting happens when .sort() is called. All of the other things you can do to an array can be mapped to splice operations.

myArray[idx] = newValue;

{
  type: "splice",
  index: idx,
  count: 1,
  values: [newValue],
}

myArray.push(...values);

{
  type: "splice",
  index: myArray.length,
  count: 0,
  values: values,
}

myArray.unshift(...values);

{
  type: "splice",
  index: 0,
  count: 0,
  values: values,
}

myArray.pop();

{
  type: "splice",
  index: myArray.length - 1,
  count: 1,
  values: [],
}

myArray.shift();

{
  type: "splice",
  index: 0,
  count: 1,
  values: []
}

myArray.sort();

{
  type: "sort",
  from: 0, // where the sort starts
  indexes: [...newIndexes], // indexes of the sorted array
}

So if you want to emit a stream of array events that represents each change to an array, you map each kind of operation to either a splice or sort data structure that describes what has happened.

This is why Gooey has that collection() function. It returns an array-like object that observes the operations performed on it—and also has a .subscribe() method to get a stream of these array events.

Under the hood, a Proxy is used to see these array mutations, and methods are wrapped to map the common operations to splice events.

To demonstrate, here’s some code that shows the stream of array events emitted when a collection is mutated:

Each mutation maps directly to a single array event, holding all of the information needed to recreate that exact mutation.

Take a closer look at how the <div class="letter"> elements are given a background color. The color is picked at random in the render function for each list item. When new items are added, they’re given a color; when existing items are moved around via sorting, the colors don’t change.

In Gooey, render functions are called exactly once—there is no “rerendering”. This means that the random color is picked once.

Ok, so we can plainly see that a key prop is totally not needed to render lists with correct DOM nodes!

And what about this .mapView() function—how does that work?

I like to think there are two kinds of data in an application: authoritative data and derived data.

Authoritative data can be changed by users or the application intentionally. It is the local source of truth for whatever it represents. It’s like a cell in a spreadsheet with a plain old value.

Derived data, on the other hand, is read-only data that is created by transforming, filtering, or merging with other data. It’s not a source of truth, but it’s often more useful than raw authoritative data. It’s like a cell in a spreadsheet with a formula.

This .mapView(mapFn) function creates a view: a read-only, derived collection. It takes the stream of array events, transforms them using a mapping function, and produces a live, read-only array which has values that are produced via the mapFn(item) for each item in the original collection.

Visually, it’s a bit like this:

Given the similarity, you might be able to guess what happens in that “Bind to DOM” bubble.

A funny thing starts happening when you see that array events can be transformed and used to make a derived array. You start to look for other places where arrays become “projections” of other arrays.

Rendering JSX to the DOM can be thought of as “projecting” one tree structure into the DOM tree structure.

Let’s look at this JSX:

<p class="letters">
  <strong>
    Our <code>letters</code> collection:
  </strong>
  {letters.mapView((letter) => (
    <span 
      style:background-color={`hsl(${Math.random() * 360}deg 50 75)`}
      class="letter"
    >
      {letter}
    </span>
  ))}
</p>

Gooey turns each JSX node into a tree of RenderNode values, each having a specific responsibility.

Here’s what this JSX looks like as a tree of these RenderNode values:

Each RenderNode emits a stream of array events holding DOM nodes. These events flow upward (in the direction of the arrows) to their parent RenderNode.

The IntrinsicRenderNode nodes map 1:1 to each intrinsic DOM element (<p>, <strong>, etc...). When attached, they emit a single array event splicing in this DOM element. When detached, they emit a single array event splicing out that DOM element. All of the child array events it consumes are applied to its element’s children, which is treated as an array.

The TextRenderNode nodes map 1:1 to each Text node, representing the raw text in a document. It acts the exact same as an IntrinsicRenderNode, except it doesn’t need to manage children.

The other two, ArrayRenderNode and CollectionRenderNode, act like a confluence of multiple rivers joined into one. Array events flow up from its children, have their indexes shifted to the right to account for the space taken up by earlier children, and are emitted as a single stream of events to its parent. By shifting indexes, the parent sees a stream of DOM nodes maintained in the order that they’re present in JSX.

Essentially, DOM nodes flow upward as a stream of array events until they hit an IntrinsicRenderNode, where they are consumed and bound to the right location in its element’s children.

And that’s it! Array events are the core abstraction that allow Gooey to render lists correctly and efficiently to the DOM without needing a key prop.

These events are a surprisingly flexible core abstraction that unlock capabilities (detached rendering, intrinsic observer) that don’t really exist in React or other frameworks.