1 # Miscellaneous notes and things to possibly do and such
3 (This started out as a short file of simple entries,
4 but then I went adding more notes to individual items,
5 and it ended up what it is now.)
7 ## Better node ID allocator
9 I’ve currently implemented the simplest possible node ID allocator: auto-increment without reuse;
10 for this, the client need only track a u32 of the next ID, and the VM side uses an ever-growing sparse array.
12 I should compare it with the following more serious allocator:
13 client and VM both track all allocated IDs in an array that will always be as large as the maximum number of IDs that have existed at any given time.
14 The VM code will look quite like this:
17 let nodes: (Node | u32)[] = [document];
25 function push_node(node) {
26 if (next_id === nodes.length) nodes.push(next_id + 1);
35 And the client side like this:
40 next_free_slot: NonZeroU32,
46 nodes: Vec<NodeSlot> = vec![NodeSlot::Full],
47 next_id: NonZeroU32 = 1,
51 fn free(&mut self, id: NonZeroU32) {
52 self.nodes[id] = NodeSlot::Free { next_free_slot: self.next_id };
56 fn allocate_node(&mut self) -> NodeId {
57 if self.next_id == self.nodes.len() {
58 self.nodes.push(NodeSlot::Free { next_free_slot: self.next_id + 1 });
60 let id = self.next_id;
61 self.next_id = match &mut self.nodes[id] {
62 slot @ NodeSlot::Free { next_free_slot } => {
63 *slot = NodeSlot::Full;
66 NodeSlot::Full => unreachable!(),
73 If I ever decide that the client side needs to materialise an actual DOM-like tree
74 (which I’m trying to avoid, but which may become desirable for event propagation),
75 then this would become a fairly obvious choice
76 (though it might need some finesse to keep size down—2 billion nodes ought to be enough for anyone,
77 I could limit the next free slot numbers to 31-bit and use one bit as a discriminant over some kind of pointer to the actual node data).
79 Otherwise, I honestly don’t know;
80 the limit of only ever creating 2\³\² nodes in total is not too awful, and sparse arrays are probably fairly decent.
81 Try to benchmark it plausibly.
82 Try to keep it easy to swap in and out too.
86 The **host** (also known as the **VM host**)
87 is the bit of JavaScript that runs in the main browser thread,
88 and executes the VM bytecode.
90 The **client** (also known as the **VM client**)
91 is the bit that writes the VM bytecode and potentially receives serialised events.
92 In my primary designed use case,
93 it runs in a worker and is WebAssembly,
94 with ideally a SharedArrayBuffer or two as the channel between the client and host,
95 but it could be written in any language and even run on a completely different machine.
96 In fact, you could use this to implement something like Phoenix LiveView with a WebSocket as the channel—in that instance,
97 the VM client would run on the server!
98 (Mind you, you *would* need to be a bit careful about disconnect recovery.)
102 Yes, the first part that’s not write-only.
104 1. By some means, the host will learn what events the client is interested in.
106 (Qwik’s approach is interesting here:
107 it writes the events names of interest to the DOM,
108 and Qwik only even bothers registering for the ones that are *on screen*,
109 IntersectionObserver and all.
110 I don’t intend to *start* that way,
111 but I’m keeping it in mind and definitely not ruling it out.)
113 2. There will also be some means of the host synchronously determining where `preventDefault` should be invoked.
114 (The two main approaches that I have in mind:
115 declare a JavaScript function that takes the target element and returns a boolean;
116 or specify a DOM attribute so that you can check ◊code.js`target.closest('[prevent-default]')`.)
118 3. The host will add corresponding event listeners to the rendering root
119 (which will probably not be ◊code.js`document` or ◊code.js`document.documentElement`).
121 (It’d be quite at liberty to add and remove them dynamically, too.)
123 4. When an event is fired, the host will serialise it along with the target’s node ID.
124 (The precise serialisation may vary by application, as with the instruction bytecode—
125 for optimal size and performance, this project is a VM factory, not a VM.)
127 5. The client will deserialise this and can do what it likes with it,
128 which can, if desired, entail a total reimplementation of event dispatch except for `preventDefault`.
129 (It actually doesn’t even need a full tree,
130 only a mapping from node to parent
131 (which doesn’t even take more memory, given the reallocater:
132 limit it to ◊`2³¹ − 1` node IDs, and store the parent ◊code.rs`Option<NonZeroU31>` in ◊code.rs`NodeSlot::Full`):
133 trace the path to the root node,
134 fire capture phase while unwinding that,
135 then trace it again for bubbling.)
137 (In practice, I’m not decided on the precise event dispatch model.
138 There is some appeal to widget-based dispatch like Druid’s,
139 where propagation is entirely left to the component.)
141 With the proposed node → parent mapping,
142 the client side will still not be able to enumerate their children,
143 a single “remove node” instruction (… huh, haven’t implemented that yet)
144 may need to be followed be a large number of “free” instructions,
145 because I expect that’ll still be the cheapest way of implementing it.
146 I’ll still want a “remove all children” opcode, too,
147 because for nodes with many children its performance is better
148 (though I should benchmark that at length in various realistic circumstances).
150 ## The race condition problem
152 It sounds like everything’s neat and sorted at this point,
153 but there’s one rather uncomfortable problem remaining: race conditions.
154 This architecture is asynchronous,
155 so the host could send an event for a node that has been removed or moved.
156 *Most* of the time, these race conditions should be harmless,
157 because root-finding on a removed node will fail due to a parentless or freed node,
158 or event semantics are probably equivalent on a moved node in its before and after locations.
159 But both could be bad: if a node is removed and freed,
160 that ID may already have been reallocated,
161 and so the event could be fired on the wrong node altogether.
162 The sorts of checks that would be required to catch that
163 (some kind of DOM epoch tracking) would be onerous and usually wasteful.
164 Moved could also be bad: in a lazy-rendered scrolling component,
165 nodes are commonly reused so that the same node ID.
166 In each case, the problem is rendered extremely uncommon by intended very low latency between client and host,
167 and mitigated further by the unlikelihood of user events so very immediately following UI state change,
168 but I’d find it a genuine concern for something like LiveView on high latency connections because that easily gives a problem window *baseline* of hundreds of milliseconds,
169 and probably want to do event dispatch by something other than node ID,
170 e.g. serialise any event-data DOM attributes from the event target’s lineage.
174 No dynamic `preventDefault`.
176 No rewriting of an ◊code.css`a[href]` in the mousedown or click handler,
177 which can occasionally be genuinely useful (and I don’t count Google’s historical use of it in search result pages),
178 and `preventDefault()` followed by href change followed by `click()` is not a suitable alternative because it’ll lose the effect of modifiers like ◊kbd`Ctrl`.
179 This will be one of those “redesign your UI” cases, which will I think *normally* be a good thing.
181 One concern of doing this asynchronously is that user-activation-gated API calls might not work.
182 <https://html.spec.whatwg.org/multipage/interaction.html#tracking-user-activation> has the spec details.
183 We should be OK now (though when they first started doing this we probably *wouldn’t* have been):
184 it’s time-based, and although the transient activation duration is not specified and not supposed to be more than a few seconds,
185 that should be enough for conceptually-relatively-synchronous actions even if the VM client is on the other side of the world.
186 (In Firefox as I write this on 2021-09-23,
187 it’s controlled by dom.user_activation.transient.timeout which defaults to 5000 milliseconds.)
189 Might have issues calling things that are only allowed to be called in response to a user action—not certain.
190 But per , probably OK.
192 ## Opcodes to implement
194 • `Remove { node: ChildNode }`: equivalent to `node.remove()`.
195 Does *not* free: you might want to put it back later.
197 ## Other potential opcodes
199 (But they need justification, whether of functionality or performance.)
201 • `AppendChildren { parent: ParentNode, number_of_children: u32, children: [...Node] }`:
202 equivalent to `parent.append(...children)`.
203 Compare performance with a sequence of `appendChild`.
205 • `AppendUntrackedString { parent: ParentNode, data: string }`:
206 equivalent to CreateTextNode followed by AppendChild, but without allocating a node ID.
207 The host can use `parent.append(data)` instead of `parent.appendChild(document.createTextNode(data))`.
208 Very unlikely to be warranted, but `AppendChildren` got me thinking of it;
209 I don’t think there’d be any sane way of integrating untracked string children into `AppendChildren`.
211 • `RemoveAllChildren { node: ParentNode }`:
212 removes all children;
213 equivalent to `node.textContent = ""` or any number of ways of doing the same thing.
214 (Doesn’t *free* them, though.)
216 • `SetUntrackedInnerHtml { parent: ParentNode, inner_html: string }`:
218 The resulting child nodes will be invisible to both client and host.
219 At first glance this might seem to complicate event handling for the host because now it may need to traverse target’s parents until it finds one with a node ID,
220 but browser extensions mean that we could never quite trust that all targets would have node IDs anyway,
221 so making it more robust in this way is probably for the best.
222 This could be justified as a performance thing for what I’ll call “static trees”,
223 meaning parts of components that don’t contain anything where node identification is required
224 (though performance claims will naturally need to be verified).
225 In whatever sort of component layer my own client implementations end up with,
226 this could really start to shine if components could be identified as being static trees,
227 and allow such components to be part of static trees,
228 and merge them recursively—
229 I don’t know of any framework where components are able to be zero-cost like this,
230 even in environments that try to be at least a little bit clever about it
231 (I’m talking DOM ones; SSR ones there are plenty that directly write strings to a buffer so that the difference will be negligible).
232 Any tracked children removed by this operation would still be allocated and need freeing.
234 • `SetTextContent { node: Node, data: string }`:
236 TODO: verify performance on setting `data` and `textContent` on `CharacterData`,
237 as they do exactly the same thing for `CharacterData` and maybe I should remove `SetData` in favour of `SetTextContent`.
238 If this were implemented,
239 I’d probably also ditch plans for `RemoveAllChildren`
240 in favour of `SetTextContent { node, inner_html: "" }`
241 as saving four bytes on the instruction isn’t worth the cost to the VM size.
243 • `SetTrackedInnerHtml { parent: ParentNode, inner_html: string }`:
244 sets innerHTML and then traverses the children recursively in tree order,
245 assigning a node ID to each.
246 (The client must naturally have done something equivalent.)
247 It’s *possible* that this could be faster than the corresponding sequence of `createElement`/`createTextNode`/`appendChild` calls,
248 but I think it’d need to be quite big before it’d stand much chance of being worthwhilely better.
249 As far as wire size is concerned,
250 the bytecode is very compact,
251 so serialised HTML would be unnlikely to be smaller.
252 I’d levy a pretty big burden of proof on this one.
254 • `InsertTrackedAdjacentHtml { parent: ParentNode, position: enum { BeforeBegin, AfterBegin, BeforeEnd, AfterEnd }, html: string }`:
255 `SetTrackedInnerHtml`, but for `insertAdjacentHTML` instead of `innerHTML`.
256 A smidgeon more complicated.
258 ## On dictionaries and string interning
260 I doubt that a dynamic dictionary will be worthwhile, though I could turn out to be wrong.
261 But a static dictionary, absolutely: I like the idea of applying profile-guided optimisation.
262 Definitely going to need to generate the remote-dom-vm JS and client together for this.