The DOM diff solution used in Respo

Tried to make a video but my cough bothers. It's still simple that I can write down my words.

Respo is using a Diff algorithm learnt from React. I don't know every detail of React's algorithm but only its idea. Respo is no complicated than React.

The core of Respo's solution is the sorted-map in Clojure which says:

Returns a new sorted map with supplied mappings. If any keys are equal, they are handled as if by repeated uses of assoc.

(sorted-map :z 1, :b 2, :a 3)   ;;=> {:a 3, :b 2, :z 1}
(into (sorted-map) {:b 2 :a 1}) ;;=> {:a 1, :b 2}

Diffing a sorted map is easy, it's just keep comparing the heads of two maps and decide what to do. Suppose there are [key-a val-a] and [key-b val-b],

  • if (and (= key-a key-b) (= val-a val-b)) then nothing changed
  • if (and (= key-a key-b) (not= val-a val-b)) then only value if changed
  • if (< key-a key-b) then key-a is removed
  • if (> key-a key-b) then key-b is added just now

It's easy to get a vector of diffs and use it in patching. DOM properties is such a sorted-map data, so Respo can handle that. For some reason React is treating styles as a map so we can patch styles. Luckily style can be treated as a sorted-map too.

The problem lays in the solution for children. At first I thought childNodes is just a map that uses numbers as keys and I can solve the problem the same way. It's actually a bit different. Suppose we are in a position that all children elements are removed, we may generated diffs like this [[:rm 0] [:rm 1] [:rm 2]]. But the truth is when child 0 is removed, child 1 will become child 0 and at last we will lose child 2. To me it's like a problem of the DOM and we need to fix that in the DOM somehow.

But it's fine since I can by pass the problem very quickly but collecting the index of the muted DOM. For example, I initialised a cursor pointing to my current position, if child 0 is ok, I would move the cursor from 0 to 1, if child 0 is removed, I would keep the cursor as 0, then I can get the right position to manipulate the DOM.

So, both properties and child elements can be covered in this DOM diff solution.

However I noticed some limitation here since I need all children to be sorted for the purpose of diffing. What if we are using a list the changes it's order frequently, isn't the diff algorithm becoming slow? So my answer is to keep the list a constant order, but to render them in different orders, with position: absolute; top: #{x}px; or order: x;. It's not perfect, but it works well.

So this is the basic ideas of Respo's DOM diff solution. There are still some tricks if you dig into Respo. Ask me if you got any questions.

(Since I haven't really look into React's DOM diff algorithm, I still need time to compare both solution to see what I have missed.)

Write your comment…

Be the first one to comment