Hey.

Many frontend developers believe that the VDOM technology, which, in particular, is used in React.js, works like a black box. Also in the npm spaces there are a lot of libraries implementing this technology, however, as for me, it will break the leg in them. The very topic of the VDOM I was interested in some time ago and I started experimenting by touch myself. In the end, it was all over with the fact that I made my own VDOM implementation and embedded it in my datagram framework (I'll write about it somehow). It turned out to be not easy, but very simple and in this article I will explain in detail what is what, why and why. And how it works, too, will tell. Dive under the cat and we indulge in an interesting experience.

Disclamer

I'm not a frontend developer. Do not hit me with slippers.
Also, do not write "take the finished framework, cudgel". I know that there are ready-made frameworks, but I need my own implementation for a number of purely technical reasons.

Why is it necessary

TL; DR : Example from this article on jsfiddle sources

On Habré somewhere already there was an article about VDOM , but I don’t like the explanation of the essence of the matter. So let me scatter on my fingers. So let's say you have a webpage, huh? It draws a certain HTML element (probably quite large). To add some context, I’ll say that this element is drawn by stretching the template onto the view model. Well, everyone used frameworks that do this, right? Handlebars there, lodash-templates, AngularJS to some extent ... And in short, imagine that the model on which the template is being pulled is changed. And you need to draw these changes inside the HTML element. The question arises - how to do it and not be a fool? Here, as usual, there are several options.

innerHTML

You can run the data model through the template engine, get the HTML and just make element.innerHTML = ourHtmlString; . Cheap and angry, but for some tasks it rolls well. What is terrible here, you ask?

And I will answer you: this option is bad first of all because all the child elements located inside the element will be mercilessly killed by the browser and replaced with new ones. Consequently? Yes, therefore you will lose all the event subscriptions (within your element, of course) that you had. You will have to re-sign the newly created elements again. Here I honestly do not know how garbage collection works in different js engines, but I admit that if you previously saved some of the child elements in your code, for example, in variables, then these elements will be removed from the tree, but not destroyed. Hi, memory leak, we missed you. Well, this is assuming that the browser uses reference counting for DOM elements, for example. Who knows the details - please write in the comments.

Besides this, this variant is very slow, especially when there are many children. That is, the browser honestly erases everything that was drawn inside the element, recalculate and redraw it anew. Just imagine - you have a Grisha user's card in which there are 100 different fields. And in your data only the date of birth has changed. And now - "All garbage, Grisha, let's be new" for one unfortunate piece of text? Kill Grisha entirely, calculate and draw again? Do you know that redrawing the interface in the browser is actually a long time? And if Grisha consists of 150 elements, then all the same. But if out of a thousand (the autopsy shows Grisha an abundance of fine details), then on some machines the redrawing can take several seconds, which greatly reduces the responsiveness of the interface.

Well and the saddest thing: not all elements are drawn through innerHTML. As an example, in IE8 it is not possible to set innerHTML on the tbody element. In Google Chrome, the table headings ( th ) are poorly rendered via innerHTML. Everything that you put in there through innerHTML will be truncated to plain text for an unknown reason. Pruflinka will not be - information from my own experience. Probably now it was repaired, but the sediment remained.

Thus innerHTML is like a fast and dirty hack. Unreliable in general, has a bunch of side effects, and in general - we are not here in grade 9 school to write like that. Of the benefits - is implemented on the knee.

HTML parser

Frankly, this option solves only the latest and most sad innerHTML problem - the finest fastidiousness in the created elements. But it is definitely worth mentioning it, largely because we need it to implement VDOM.

How does it work? Yes, it just works. Parsing HTML and calling document.createElement for each node, followed by setting attributes. Then do element.innerHTML = '' and go through the received elements by calling appendChild / insertBefore .

Well ... First, we have not solved the problem with the killing of elements. Secondly, with HTML parsing, everything is not so smooth in this world.

Parsing HTML is about how to parse an XML document and is most often used for client side in parsers in food thread parser. Dada, it's about like StAX in Java . It is proved that the use of XML stream parser is good for health. Why? Yes, because it is fast and easy to write. You should not use the classic tree parser for this task as for XML. It is simply not necessary here.

Everything in the world of HTML parsers is good, except for one thing: I don’t have them, poor things built into browsers. In MDN , the DOMParser is mentioned , but it is still experimental and, apparently, will give you a tree at the output. Well, that's just to bypass the trees and call document.createElement on the client side, and we didn’t have enough, yeah. In a word, he is strange. Let's not touch it. There is htmlparser2 - there lies in npm . Event stream parser, but I did not use it myself, because as the ideology of my framework it does not allow me to use third-party dependencies. And there is an article and an example of John Rezig's code (please take it apart from jQuery), where he explains everything on his fingers and gives the code of a simple parser. I don't like it because it works on regular expressions. I see this very hard. However, quite workable. For a long time, I (I repent) used just the code from this article, revised for TypeScript. However, then I replaced it with a stream parser on a simple state machine (which I will share with you today) in order to minimize string comparisons and support for creating virtual elements (which, for example, John was somewhat uncomfortable).

VDOM in person

And here we finally come to the most cunning approach, which solves problems with both performance and the fastidiousness of innerHTML to elements. Namely - using the HTML parser, we can, suddenly, parse our HTML, but call for each element not document.createElement , but simply create some object that will store the tag name and attributes. This very object will be called a virtual DOM node , and their combination - a virtual DOM tree , or VDOM. Here it is worth noting that create a thousand objects in JS through var a = {}; - it's fast. Very fast. But to create a thousand real DOM nodes is slow. From this circumstance, sobsno, and results in productivity gains.

OK, created. And what will we do with this good? Take off your pants and run You can not take off your pants, but you will have to run: we will compare the structure of our VDOM tree with what has already been drawn, make some sort of diff patch from this (what needs to be added, what to remove, where to drop attributes, where to change the content) and roll it onto an existing DOM tree. This is exactly the same as it happens in your favorite git during the merge. Fortunately, the task of building a diff in programming is quite well known - it is googling, suddenly, according to the words, finding the largest common subsequence . It is solved by dynamic programming. The algorithm has a quadratic complexity. In good universities, the solution of this problem is studied in the first courses, but here I will describe it thesis and tell you how to adapt it to the trees.

UPD: in the comments I was already showered with tomatoes for the fact that LCS is not optimal for this task - it is necessary to use LIS, but I cannot rewrite the article and the code so quickly. So just keep in mind that the part that is involved in calculating the diff can be optimized much "denser".

As a result, the VDOM approach does not kill those elements of the tree that have not changed and does not create unnecessary elements, which significantly saves memory and keeps event subscriptions (if the elements are not destroyed), at the same time forcing your CPU to do more comparisons than creating HTML elements . And this gives a notable increase in productivity, when only one of the 1000 elements on the screen has changed.

Let's get started

We will write a small application that will consist of a textarea on the left, in which you will drive in and / or modify your HTML, and in the window on the right you will see the result of the work. No additional libraries - only TypeScript and browser. Let us, as they say, create magic from the air.

You know, at first I wanted to add a lot of code to this article with line-by-line parsing of it, but, remembering my previous articles, I did not dare to do that. Directly, the code reduces readability and bores. So, with your permission, I’ll just give links to Github and explain how and what works. Our VDOM will consist of three main components - the HTML parser, the comparator itself and the batch calculator, as well as app.ts , which will put all this app.ts together and make it work.

Parser

Here it is necessary to make a reservation. As I understand it, React.js works without an HTML parser since its templates (jsx / tsx) are already being assembled into the corresponding calls for creating nodes. This is a good move that improves speed, but you know ... it was not my plan to create my own template making language and writing a compiler for it when I was writing this article. So we will parse the bare HTML hands. This implementation guarantees us the opportunity to embed our craft anywhere, well, and will allow you to avoid purely pedagogical curiosities, if you know what I mean :) So, let's go.

Stack

JavaScript does not contain effective tools for working with stacks, but we need it. Therefore, we make a simple stack . No comments.

Constructor node

As you know, in terms of JavaScript, an HTML document consists of nodes. Some of which are quite HTML elements, such as HTMLInputElement ( input tag), HTMLDivElement ( div tag). And some - no (text, comment). All available node types are listed here in MDN . We begin with a simple one - we will declare a so-called interface. "constructor node". In order not to enter into our HTML parser, I call document.createElement and use the same parser for the DOM and for the VDOM. In my implementation, it looks like this . As you can see, we are limited to three types of nodes - HTML element, text (content) and comment. The interface is extremely simple and provides for the possibility of creating all three types of nodes, and for an HTML element also the installation of attributes. In order not to depart from the cash register, we immediately implement it for real HTML nodes. It is very simple. Even a child can handle it .

Here we will think over how we will store VDOM nodes. What is important for us to know about a node, besides its type? In the case of an HTML element, a tag and attributes. In the case of a comment and text - the content. In addition to everything else, the list of child nodes is just as important to us. Fine. We describe the interface and enum for types, after which we implement the constructor itself: like this .

HTML parser

Parser - we will have such a thing, which has a limited number of states . She is leisurely It goes according to the HTML transmitted to it, symbol by symbol and changes its state depending on the current symbol. When moving from state to state, the parser will pull the constructor's node methods, performing the appropriate actions.

For example: reads the parser characters, does not touch anyone. Op - met < , remembers where he saw him, changes his state to "listen carefully, now there will be an HTML tag". Reads on. Op - meets the whitespace character, and like this: aha! here is the name of the tag. He remembers where he met < , gnaws the text from there to the current position - this is the name of the tag. So, it is necessary to pull the constructor node and call create on it, passing the name of the tag. Then the parser skips all whitespace characters and if it sees > , it goes to its original state. And if he sees the letter of the alphabet, he also catches the name of the attribute, = , the attribute value in quotes, pulls the constructor node ... And so on, until it reaches the end.

The created tags will be stored on the stack. Every time we reach the opening tag, we put it on the stack. When creating an element through the constructor, we indicate the current top of the stack as the parent element. Trivially. I am sure that at least once everyone did something similar when they wrote a calculator on the first courses of the university.

All states, as well as actions during transitions, we put in a state machine , which technically is a huge Dictionary fucking c # in head a hash object of the form "state" -> "description of actions". The description of actions in our case consists of three parts:

• the function that will be executed on entering the state;
• a function that will be executed at the exit from the state;
• the function that will be called for each next character read;

I combined these three functions into a piece that I called IStateInfo . In the same place I described all possible states of the parser. I made the parser itself , providing it with several useful tester functions (this is when we look at what the current symbol is, what was n characters back, whether the next m characters follow such a word, and so on). The fix() function stands out in fix() : when we change the state of the parser, it remembers the position of the current character with the thought that by moving a few characters further, we can gnaw a piece of text between the stored position and the current position. Gnawing out a piece of text from the memorized position to the current position is performed by the cut() function. Usually, after calling cut() , a state machine sends a signal to the parser - like "oh, look, the opening tag is caught, here is its name." Why so hard? Well ... I am an economical person. Made a parser that does not create unnecessary lines unnecessarily.

Well and, actually, further I simply listed all possible states of the parser and all possible actions - as they say, I programmed the state machine . There are many nuances associated with quotes around attributes, self-closing tags, symbols - and : in attribute names. Allow me to omit here the detailed chewing of each of these cases - everything is in the code, if you wish, you will see it.

Another feature: the style and script parser cuts and folds separately, so that the user of the parser himself decides execute or pardon them what to do next with them. You can, for example, make eval for scripts. But what to do with styles - the question is not clear even for me. The only thing that is not taken into account in my implementation is the tricky possible structure of these tags. Say, if in a script you have text in the spirit of return '</script>'; , the parser mistakenly recognizes it as closing the script tag, which is unpleasant, but it is easy to repair. I'm just too lazy .

Calculate the difference

So, at the current stage, we have a valid HTML parser, to which you can transfer a piece of HTML-me and parse it into real DOM elements, or into VDOM elements. This is just great.
Now imagine that we have already drawn some kind of HTML on the screen, we want to change it slightly. We take it, make adjustments, feed the parser with the VDOM constructor. Get the list of VDOM nodes. Now we need to calculate the difference between the HTML that is drawn on the screen and what our parser has done to us. In fact, we need to take a parent-node, inside which our HTML is rendered, take an array of all its children and compare it with a similar array of virtual children, which we created the HTML-parser. And when I say "compare" - I mean not only answer the question "match or not," but also generate a so-called. "update batch" - a list of which items to add and which ones to remove from where to get a new one from an old piece of wood. After that, the resulting packet of changes simply rolls onto the already rendered HTML, without destroying the already rendered and unchanged, but cleverly changing only the affected nodes. This operation is called VDOM update . Something like that. But first things first.

Comparison cache

First you need to learn how to compare HTML nodes and VDOM nodes. This is done relatively simply:

1. Compare types. If it does not match, the nodes are different.
2. If both nodes are textual or comments - compare the content. Coincides? The same. Does not match? Various.
3. Compare the number of attributes. Does not match? Various.
4. Meaningfully we compare the presence of attributes and their values. Something did not match? Well, you understand.
5. We perform steps 1-4 for each child node.
6. If you are reading this, then the nodes still match.

As you can see, comparing nodes from scratch each time is labor-intensive. Largely due to recursion in step 5. Therefore, I made a cache comparator that lives within one update and stores the results of comparisons of nodes with each other. Thus, if the fact that two nodes are different has already been installed, it is not installed again, but is taken from the cache. A lot of the same type of code .

LCS

This is short for "Longest Common Subsequence". This class is essentially a matrix for solving a LCS problem using dynamic programming. We give it two arrays to the input - one of the real nodes, the other - from the virtual ones, we also feed the comparison cache, which I described above. Next, call produceModifyBatch and get an array of batch entries (described at the bottom) , which essentially says what needs to be done with such and such an account node - update, delete, or insert another (and which) node BEFORE it.

First, after calling produceModifyBatch , LCS cuts the same elements from the beginning and from the end of the arrays (the doSkips function). Next, on the remaining data is the matrix of dynamic programming - exactly as explained in this video . Then bypass this, determining which nodes should be removed and which ones should be added (also described in the video). Please note that at this stage we do not get a list of nodes that need to be updated . The result contains only delete-add, but! But deleting-adding a node to the same place (or adding-deleting) is the update . The normalizeBatch operation does just that, which collapses the nearby add-delete in one operation — the update , reformatting the primary batch entry array. The result, finally, you can return a happy user.

LCS is the most difficult thing in VDOM, which makes it seem like a terrible magic to many. As you can see, the algorithm itself, as they say, is tricky, but quite understandable to itself. Its complexity, by the way, is quadratic, but there is nothing to be afraid of. If the changes are relatively small and they are somewhere in the middle of a pack of elements, most of them are cut off at the doSkips stage and as a result, the dynamic programming matrix rarely exceeds 3x3 in size. Of course, if your users do not redraw 10 thousand buttons, standing under each other. In practice, such cases rarely occur. So it makes sense not to build the LCS-matrix, if you have 2 or 1 element, but to process the result with your hands. Much more often in real life there is a large nesting of elements, for that matter. , , JS ( ). . , React.js — . — . .

DOM Differ

, update, parent-, LCS-, HTML- . , , — , . No comments.

! !

update: parent-, VDOM-. LCS, update batch. , , , , — . , — updateAttributes , update, (, VDOM--). : , — , parent.insertBefore . , — parent.removeChild . . .

diff , update batch-. , .

HTML- , app.ts , .

Results

, VDOM. , , , JS-. -, , HTML- — , .

, .