Implementing a Virtual DOM engine in Rust

A talk presented at the Rust Bangalore June 2025 Meetup

Code repo - https://github.com/ajnsit/concurse

Transcript

1. IMPLEMENTING A VIRTUAL DOM ENGINE IN RUST
2. DOCUMENT OBJECT MODEL Persistent, and therefore Effectful, tree like structure, with node attributes.
3. DOCUMENT OBJECT MODEL �� Opaque data structure struct Node �� Creation fn create_text_node(str: &str) �� Node fn create_element(name: &str) �� Node �� Topology modification fn append_child(&self, child: &Node) fn remove_child(&self, child: &Node) �� Attributes fn set_attribute(&self, key: &str, val: &str) fn remove_attribute(&self, key: &str)
4. HELLO WORLD fn main(rootNode: &Node) { let t = create_text_node("Hello World") rootNode.append_child(t) }
5. INTERIOR MUTABILITY
6. THIS IS AFFINE We use &Node everywhere instead of &mut Node for convenience. fn append_child(&self, child: &Node) �� ^-------------^
7. THIS IS AFFINE 1. You don't have to manage the lifecycle of a Node 2. Compiler will do it for you 3. You have to convince the compiler everything is safe. This is easier than using malloc/free but harder than using the GC. 4. No GC means better performance! 5. This does not get us any more guarantees.
8. THIS IS AFFINE Rug pulls Node identity parent1.append_child(childNode); parent2.append_child(childNode); rootNode.append_child(rootNode);
9. PROBLEM: NOT VERY FUNCTIONAL 1. Non Declarative API 2. Direct access to the node you want to update. Grab nodes by stringly typed ids. 3. Can't control the granularity of updates 4. No place to save per node state
10. COROLLARY: NOT VERY FAST 1. Cannot be parallelised 2. Cannot control when to render. Rendering a�er each update can be very expensive 3. Remember the current state of the page when making updates OR what you end up doing is checking the current state of the DOM to decide what to update 4. DOM is slow, memory is fast
11. SOLUTION We need an in memory representation of the DOM tree. a.k.a Virtual DOM
12. VDOM enum VDom { Text(String), Elem(String, Attributes, Vec<VDom>) }
13. FUNCTIONAL VIEWS For efficiency we need a VDOM diff and patch mechanism fn render(state: SomeState) �� VDom fn apply(vdom: VDom)
14. APPLY fn apply(vdom: VDom) { let oldVdom = getOldVdomFromDom(); let diff = calculateDiff(vdom, oldVDom); patch(diff); }
15. CONSIDERATIONS 1. Ensure that the VDom is kept in sync with the Dom 2. Make the diff and patch efficient
16. MEALY MACHINES A mealy machine computes the next state as a function of the current state and the current input. We call the function that computes the next state step fn step(input: I, state: S) �� S
17. DIRECTLY TRYING TO IMPLEMENT THIS LEADS TO ISSUES 1. State is existential. A machine can have different internal states at different times. Existentials are hard in Rust 2. Even if we abstract the state into an opaque type, Rust abhors first class closures 1. We must know the size of the captured state. 2. We must know the lifetimes of the captured state.
18. WE MUST USE TRAITS trait Machine { type I; type O; fn extract(&self) �� Self��O; fn step(self, i: Self��I) �� Self; fn halt(self); }
19. OR PERHAPS MORE IDIOMATIC? trait Machine { type I; type O; fn extract(&self) �� Self��O; fn step(&mut self, i: Self��I); fn halt(self); }
20. MORE IDIOMATIC, BUT PROBLEMATIC 1. You need a structure that can entirely replace itself with another 2. State can vary wildly 3. Requires knowing all possible states statically
21. THE WORKAROUND There's an entire cottage industry of solutions for replacing values behind an &mut struct VDomMachine { vdom: Machine<���> } fn step(&mut self, inp: Self��I) { take_mut��take(&mut self.vdom, |vdom| return vdom.step(inp); ); }
22. VDOM AS A MEALY MACHINE Given an input VDom, the machine yields a Node type VDomMachine = Machine<I=VDOM, O=Node>
23. RUNNING A VDOM MACHINE fn main() { �� Build the initial machine �� State is the application state fetched from some place let machine1 = build(render(state1)); �� Attach the output node to the DOM �� This only needs to be done once let node = machine1.extract(); appendChildToBody(node); �� Arc so we can share machines let marc = Arc��from(Mutex��from(machine1)); �� Application loop, updates state and runs the machine �� Note that the node is automatically updated in the DOM
24. COMING BACK TO THE PROBLEMS 1. VDOM must be kept in sync with the DOM 2. We need a VDOM diff and patch algorithm Both are solved by mealy machines
25. HOW Through the power of COMPOSITION
26. COMPOSITION Our sample VDOM structure has two variants - We can create the mealy machines for these variants separately, and compose them. enum VDom { Text(String), Elem(String, Attributes, Vec<VDom>) }
27. TEXT MEALY MACHINE What is the internal state of a text node? The text of course! struct TextMachine { str: String, node: Node, }
28. ELEMENT MEALY MACHINE What is the internal state of the element node? The node name, AND a parent manages all the internal mealy machines of all the children struct ElemMachine { name: String, children: Vec<VDomMachine>, node: Node, }
29. BUILDING A MACHINE FROM VDOM fn build(host: Host, vdom: VDom) �� VDomMachine { match vdom { VDom��Text(s) �� { VDomMachine { machine: TextMachine { str: s, node: host.create_text_node(&s) } } } ���
30. BUILDING A MACHINE FROM VDOM CONTD... ��� VDom��Elem(s, children) �� { let node = host.create_element(&s); let children = children.into_iter().map(|vdom| { let child = build(host, vdom); node.append_child(child.extract()); child }).collect(); VDomMachine { machine: ElemMachine { name: s, children, node } }
31. STEPPING A TEXT MACHINE impl Machine for TextMachine { type I = VDom; type O = Node; fn step(&self, inp: Self��I) �� Self { match inp.vdom { Text(s) �� { if s �� *self.str { node.set_text_content(&s); } self } _ �� { self.halt(); build(inp)
32. STEPPING AN ELEMENT MACHINE impl Machine for ElemMachine { type I = VDom; type O = Node; fn step(&self, inp: Self��I) �� Self { match inp.vdom { Elem(s, children) �� { if s �� self.name { self.children = update_children(&self.node, self.children } else { self.halt(); build(inp) } } _ �� {
33. UPDATE_CHILDREN fn update_children( node: &Node, children: Vec<VDomMachine> vdoms: Vec<VDom>, ) �� Vec<VDomMachine> { children.into_iter() .zip_longest(vdoms) .filter_map(|zip| match zip { Both(child, vdom) �� Some(step(child, host, vdom)), Left(child) �� { halt(child); None } Right(vdom) �� { let child = build(host, vdom); parent.append_child(child.vdom.node()); Some(child) }
34. FIN
35. BONUS SLIDES FOLLOW
36. WHAT I LIKE ABOUT RUST 1. Tooling 2. Ecosystem 3. Low level enough to have good performance 4. Strong types
37. WHAT I DON'T LIKE ABOUT RUST
38. 1. Impurity 2. Syntax 3. Splitting up functionality means fighting the borrow checker. You end up with long functions with less safety guarantees 4. Less expressive type system (No typeclasses, existentials, gadts) 5. No first class closures 6. Code is o�en much more verbose, and has more chances to be buggy 7. Macros Ugh 8. Panics are business as usual
39. IN AN IDEAL WORLD 1. Pure strict functional language with advanced types 2. Strong ecosystem 3. Great tooling 4. Close to machine code => performance PureScript is 3 out of 4.
40. MORE PERFORMANT PURESCRIPT 1. Learn from Rust's APIs e.g. Use iterators. Mapping over vector should use builder pattern 2. Choose a blessed backend. Make performance a first class concern 3. Get proper linear types, and ownership tracking. Eschew GC when possible. 4. Fearless concurrency baked into the typesystem. There are papers on this. Regions of disconnected object graphs.