# Bevy/Quill Incrementalization Architecture
This document describes how Quill approaches the problem of incremental updates to Bevy entities and components.
The basic flow goes like this: Given a *template*, which is a tree of template nodes (called `Views`), we want to be able to use this template to to one of two things:
* **Create** a Bevy hierarchy comprised of entities and components.
* **Synchronize** an already-created hierarchy, such that the hierarchy is brought into conformance with the template, using the minimal number of mutations.
The first of these two goals is actually a degenerate case of the second: creating a tree is the same as synchronizing a tree whose prior state is the empty tree. So for example, if a newly created element has no children, and the template says that it ought to have 3 children, then 3 new entities are spawned.
Thus, we really only need to talk about the algorithm for synchronization; however this subdivides into a number of parts depending on whether we are talking about entities, components, or other things such as text sections.
# Entities
Entities are produced by template nodes in a number of ways:
* The `Element::<B>` view creates an entity and a Bundle `B` to go with that entity, similar to the way `Commands.spawn()` works. The most common element type is `Element::<NodeBundle>` which is used for UIs, but other types of bundles can, and have been, used.
* An element always produces a single entity as output.
* `Element`s can have `children` which are also template nodes. These children can be `Elements`, or they can be other types of views. These other types of views don't necessarily have to produce a single child entity.
* Most `Element`s spawn a new entity; however the `Element` view has an alternate constructor which accepts an already-created entity instead. This is often used in cases where you need to know the entity id before the template is finished building.
Besides `Element`s, there are a number of other types of template nodes (the word "node" here is used to indicate a template node, not a UI entity):
* `Cond` (conditional) nodes have a true branch and a false branch, both of which are template nodes. The test expression determines which branch's output is produced.
* `ForEach` and `ForIndex` nodes produce a variable number of children, depending on the iterator parameter.
* "Fragment" nodes represent multiple child nodes, and are represented by a variable length tuple, much like Bevy systems during registration. The output of the fragment is simply the concatenation of the output of all of it's child nodes.
* Note that when passing template nodes as a parameter to another template, the type of the parameter is a fragment wrapped in an `Arc`. This means, for example, you can invoke a `Dialog` template, and pass in any number of children as the dialog's "body". A separate parameter allows you to specify the dialog's title.
* `Portal` nodes build their children, but produce no output, meaning that the children are unparented. This is used for things like menu popups and dialogs which need to be absolutely positioned in window coordinates.
* `Text` nodes produce a single entity as output, which has a `Text` component.
* `Template Invocations` are nodes which call some function to execute a child template. The output of this function is also a template node tree, which is then evaluated normally.
## State reconciliation
When a template is re-run, it compares the state of each template node with the previous state. This "state" is not the same as the output entities, but rather the set of data needed by the template to determine if the output has changed. For the case of an Element, the state is simply the entity id of the output.
Note that in the Quill architecture, template states are associated trait types which are stored externally from the actual template node - they are not "objects" in the OOP sense. (This pattern is borrowed from Xylem). In other words, the actual template tree is created anew every execution (which is very cheap since it's just tuples on the stack) but the template's state is stored in a hidden component, and outlives the actual template nodes.
Most template nodes do minimal reconciliation. An element's output entity never changes, unless the element is destroyed, so it's state reconciliation step does nothing. (It does, however, reconcile it's components, which will be covered in the next section).
A `Cond` node is slightly more involved: it has a boolean state variable which indicates whether the true branch or the false branch was taken the previous execution. If the condition value is the same, it does nothing; otherwise it tears down the nodes from the old branch (by calling `.raze()`), and builds up the nodes for the new branch (by calling `.build()`).
The most complex template node reconciliation is in the `ForEach` node, which maintains a copy of the array elements that were passed in. It does a `diff` (using a basic LCS algorithm) to identify insertions, deletions, and mutations of the input array, and then rebuilds the child nodes based on that.
## Child entity reconciliation
After the template is executed, and all of the entities are created or destroyed, there's a separate phase whereby we attach the remaining entities to their parents. This phase is only run when needed; the output of the state reconciliation phase is a boolean variable which indicates whether any of the child entities changed; if none of them did, then this phase can be skipped.
During this phase, each Element does the following:
* A new, empty vector of entities is created on the stack.
* This vector is passed to each child as a mutable reference.
* The child appends all of it's output entities to the vector.
* Finally, the parent element calls `entity.replace_children()` to replace all of the target entitie's child entities.
It is important to understand the difference between the array of child template nodes (which is a permanent part of the view template) and the array of child entities (which is a temporary variable that only exists during this phase). These two arrays generally do not have a 1:1 correspondence between them, although they will always be in the same order.
Here's a concrete example: suppose we have an element which has 3 children:
```
[
header,
ForEach(...),
footer
]
```
The header will always be the first element, and the footer the last. However, the total number of child entities produced may be different from one execution to the next, depending on how many entities are output by the loop in the middle. The number of *template nodes*, on the other hand, will always be 3.
This also means that the array index of the footer entity may change over time, but the array index of the footer's template node which produces those entities never changes.
Note that the above scenario is not the only case where the number of children can vary widely. Consider, for example, the following:
```
[
header,
fragment,
footer
]
```
Where `fragment` is a parameter passed to the template by it's caller. The template has no way of knowing in advance how many entities are in the fragment, and this number may change from one execution to the next.
# Components
There are three different strategies for reconciling components:
* Replacement
* Mutation
* Conditional Insertion and Removal. This strategy is generally only used for marker components which need to be dynamically removed from the entity when a condition is false.
All of these strategies are selected explicitly at the template level by the user: Quill uses a fluent syntax for defining components, and the choice of which fluent method is used detemines which of the above strategies will be applied. For example, if the user calls the `.insert_dyn()` method, it will use the replacement strategy. This is similar to the way Bevy systems and commands work: the user can query a component and mutate it, or use `.insert()` to overwrite it, it's their choice.
All of these strategies are implemented by the `EntityEffect` trait. Every `Element` has a list of `Box<dyn EntityEffect>` effects which are invoked during reconciliation. Entity effects are created whenever you call a fluent builder method on an element.
In addition to the above methods, there are also some special "one-shot" or "static" versions of the above, which are only executed once, when the template is run the first time. The reasoning behind these methods is that most components aren't dynamic, and don't need to be updated after creation.
For general component insertion, there are 4 methods:
* `insert()` - the static, one-shot version.
* `insert_dyn()` - the dynamic replacement version
* `insert_if()` - the conditional insertion/replacement version
* `effect()` - the general swiss-army-knife component mutation hook.
For styling, there are also some specialized methods which take a `StyleBuilder` argument:
* `style()` - the one-shot version, used to set up base styles.
* `style_dyn()` - the dynamic mutating version, used to apply dynamic styles.
`StyleBuilder` provides a large set of convenience methods and automatic type conversions for things like setting border widths, background colors and so on.
# Text
Currently Quill only supports text entities with a single `TextSection`. The reason for this is as follows:
* The vast majority of text fragments (like button labels) are single strings.
* Writing a reconciler for multiple text sections would be non-trivial.
Even so, there is a reconciliation algorithm for that single text section, which looks like this:
* If the text is the same as before, then do nothing.
* If the text is different, then update the TextSection with the new text.
* If the entity doesn't have a text section at all, then despawn the entity and create a new one with a `Text` bundle. (Ideally this should never happen).
Sign in with Wallet
Connect another wallet