Didact: Instances, reconciliation and virtual DOM
[Update] This post is based on the old React architecture, there’s a new self-contained post where we build everything from scratch including hooks, concurrent mode, fibers, etc.
This story is part of a series where we build own version version of React step by step:
So far we implemented a mechanism for creating dom elements based on a JSX description. In this post we will focus on how to update the DOM.
Until we introduce setState in a later post, the only way to update the dom will be to call again the render function (from the first post) with a different element. For instance, if we want to render a clock, the code will be:
With the current version of the render function, this doesn’t work. Instead of updating the same div for each tick it will append a new one. A first approach to fix this is to replace the div for each update. At the end of the render function, we check if the parent has any child, if it has we replace it with the dom generated from the new element:
For this little example this solution works well, but for more complex cases the performance cost of re-creating all the child nodes won’t be acceptable. So we need a way to compare between the trees of elements generated by the current and the previous call to render, and only update the differences.
Virtual DOM and Reconciliation
React calls this “diffing” process reconciliation. For us to do the same, first we need to preserve the previous rendered tree so we can compare it with the new tree. In other words, we are going to maintain our own version of the DOM, a virtual DOM.
What should be the “nodes” in this virtual DOM? One option would be to just use Didact Elements, they already have a props.children property that allow us to navigate them as a tree. But there are two problems, one is that we need to keep a reference to the real dom node on each node of the virtual DOM in order to make the reconciliation easier, and we prefer to keep the elements immutable. The second problem is that (later) we will need to support Components, which have their own state, and elements won’t be able to handle it.
Instances
So we need to introduce a new term: instances. An instance represents an element that has been rendered to the DOM. It’s a plain JS object that has three properties: element, dom, and childInstances. childInstances is an array with the instances of the children of the element.
Note that what we are referring as instances here is not the same instance that Dan Abramov uses in React Components, Elements, and Instances. He refers to public instances, which are what React gets when it calls the constructor of a class that inherits from
React.Component. We will add public instances to Didact on a future post.
Each DOM node will have a matching instance. One goal of the reconciliation algorithm is to avoid creating or removing instances as much as it can. Creating and removing instances means that we will also be modifying the DOM tree, so the more we re-utilize instances the less we modify the DOM tree.
Refactoring
Let’s rewrite our render function, keeping the same brute reconciliation algorithm, and adding an instantiate function that creates an instance (and its children) given an element:
The code does the same as before, but we are now storing the instances from the last call to render. We also separated the reconciliation function from the instantiation.
In order to reuse dom nodes, we will need a way to update the dom properties (className, style, onClick, etc.) without creating a new dom node. So, let’s extract the part of the code that is currently setting the properties to a more generic function that updates them:
updateDomProperties removes all the old properties from the dom node and then add all the new ones. It doesn’t change if the property has changed, so it will make a lot of unnecessary updates, but for the sake of simplicity let’s leave it like that for now.
Reusing DOM nodes
We said that the reconciliation algorithm needs to reuse as much DOM nodes as possible. Let’s add a validation to the reconcile function to check if the previous rendered element has the same type as the one we are currently trying to render. If the type is the same, we will reuse it (updating the properties to match the new ones):
Children Reconciliation
The reconcile function is missing a crucial step, it’s leaving the children untouched. Children reconciliation is a key aspect of React, it requires an extra property in the elements (key) to match children from the previous and current tree. We will use a naive version of this algorithm that only compares children on the same position of the children array. The cost of this approach is that we lose the opportunity to reuse DOM nodes when they change order on the children array between renders.
To implement this, we match the previous child instances instance.childInstances with the element children element.props.children, and we recurse calling reconcile one by one. We also keep all the instances returned by reconcile so we can update the childInstances:
Removing DOM nodes
If nextChildElements is longer than childInstances, reconcileChildren will call reconcile with an undefined instance for all the extra child elements. That shouldn’t be a problem because the if (instance == null) will take care of it and create the new instance. But what about the other way around? When childInstances is longer than nextChildElements it will pass an undefined element to reconcile and throw an error when trying to get element.type.
That’s because we haven’t considered the case when we need to remove an element from the DOM. So we need to do two more things, check for element == null in the reconcile function and filter the childInstances on the reconcileChildren function:
Summary
In this post we enhanced Didact to allow updates to the DOM. We also made it more efficient, avoiding most of the changes to the DOM tree by reusing DOM nodes. This also has the nice side-effect of maintaining some of the DOM internal state like scroll position or focus.
I updated the codepen from before. It calls render for each change in the state (stories array). You can check in the dev tools if the DOM nodes are re-created.
As we are calling render on the root of the tree, the reconciliation is applied to the full tree. In the next post we’ll introduce Components, which will allow us to apply the reconciliation algorithm just to the affected sub-tree:
Check these three commits on GitHub to see how the code changed from the previous post.
Thanks for reading.
