Something I’ve kind of wondered several times over...

# compose

[spierce7]

Something I’ve kind of wondered several times over the past few months, and haven’t been able to get an answer for - if Compose doesn’t use a shadow dom, how is it working under the hood? I’ve tried to understand it, and I know it creates a tree structure under the hood. How does it stay efficient and function under the hood if the tree structure it maintains is not a virtual dom?

[Adam Powell]

it uses a variant of a gap buffer for internal bookkeeping, identity management, and `remember {}`ed things and issues commands to an Applier that performs real tree modifications based on a changelist built during composition

[spierce7]

Thanks for your response! So why is this not considered a shadow dom?

[Adam Powell]

Usually when people say shadow dom they mean a fully constructed tree structure returned by a render or build process. The runtime then compares the new tree to a source of truth and uses that to determine real-dom changes to make.

[Adam Powell]

Compose more or less does the "comparison" as composition is executing and builds edits to the gap buffer as it goes

[Adam Powell]

I'm sure Chuck could give a better and more precise description later 🙂

[spierce7]

I’d like that if Chuck did that 🙂 It’s still not entirely clicking for me. I’ll read more about Gap Buffers in the mean time.

[Zach Klippenstein (he/him) [MOD]]

It might not be entirely accurate, but I think of it like the purpose of a shadow dom is to generate a diff to use to update a real dom. Compose skips the middle step and just generates the diff directly.

[spierce7]

@Chuck Jazdzewski [G] ^^

[Chuck Jazdzewski [G]]

Composition records information about the execution of a composable function in the slot table in the form of a tree linearly layed out into an array (two parallel arrays actually). It is easiest to think of this as just a tree, however. It is a tree recording the call graph (tree) of the composition; each call is recorded as a node in the tree called a Group (as it contains a group of nodes). Each group has a key generated by the compiler that is unique its code location. Each group can contain any number of sub-groups. There are special groups, called node groups, that record when a node is emitted (e.g. a layout node) and each group records how many nodes it contains (but not how many nodes a node group contains).

During recomposition, as a function executes, it compares the group keys in the tree with what was recorded previously, if things are the same, nothing is recorded and it moves on. If, however, a difference is detected the remaining sibling are collected in a hash table and one of two things are true, 1) the group being generated is in the sibling list at a different location, 2) the group is not in the sibling list. If (1) is the case, a move is recorded and the composition continues as if that group was moved already, if (2) an insert of new content is recorded and composition generates new content to be inserted. At the end of the sibling list generation unused siblings are removed. An additional case is when no more siblings are present in the tree but additional groups are generated, this triggers an insert.

When inserting, moving or removing groups, the corresponding index in the container node is tracked and if a group is removed the corresponding nodes are removed. If the group is moved the corresponding nodes for the group are moved. This is made easy to track by keeping track of the number nodes each group contains.

Given the above algorithm, all edits to the recorded information are forward walking, once an edit is performed (insert, delete, or move) at a location in the tree no other changes will occur to earlier groups. Also, the changes are inserts, deletes, and moves. This screamed gap buffer to me as these operations are very efficient in a gap buffer so the call graph is stored in a gap buffer.

Also of note is that the fundamental data types is the Group. This is why the compiler focuses on reducing groups. The lower the number of groups the faster this above algorithm will work.