This is a design document for a portion of our editor architecture. inspired partially by Our Machinery's "The Truth" mixed a bit with the Elm Architecture popularized by React/Redux.
Design
Overview
Maintain a data-store as a tree of objects/properties (and arrays) as an immutable data structure, with edit events generated by the editor UI and applied and observed at fixed sync points. The immutable data structure allows snap-shots and "perfect" undo/redo.
Data Store
The data store is essentially just a tree of objects. An "object" in this can be a map (string -> properties) or an array (index -> properties).
Map keys will be limited to a specific format [a-zA-Z_][a-zA-Z0-9_-]*, and array indices will be limited to [0,N) where N is the array size. The map key limits are to enable property paths, and to keep some serialized formats safer/simpler.
Properties can be the typical primitives like int64, uint64, float32, string, bool, child objects, and a few other specialized handy types (vec3, asset, etc.).
For the most part, the data-store can be likened to an in-memory JSON tree.
Property Paths
Referencing an object or property in a data-store can be achieved by the use of a dotted notation made of Map keys and Array indices, e.g. entities.0.components.transform.position.y
A component in a path must be either of the Map key format or must be an integer of the form ([0]|[1-9][0-9]*).
It will be reasonable to cache values at property paths for a single frame, but across frames this would result in potentially out-of-date data being read. It may be reasonable for cached values to detect when this has happened and only re-cache the value as necessary, but this feels like it may be a premature optimization.
Iteration and Reading
A read-only reference to an object is allowed by grabbing a (counted) reference to that object. This reference should also include a reference to the data-store itself and some information on the path used to acquire the object.
With these, it is possible to provide efficient native iteration of object keys/indices, queries on key existence or Array length, etc.
Immutability
As Slate is intended to be an immutable data-store pattern, these references will be forever immutable and never able to observe any changes. Uses that want to reference "future" edits to a data-store would need to store the path, not a reference.
The immutable nature of Slate is maintained by offering no direct mutation of the data-store, instead requiring edit events. The application of edit events will apply copy-on-write semantics so any existing snapshot or immutable reference will see no changes.
Note that immutability essentially requires that changes to any property will need a copy-on-write behavior for the property's object, and changes to any object will require copy-on-write behavior for the object's parent, and so on.
The end result is that editing any single bit of the data-store will result in a new object at the root if there are any snapshots.
Edits
Edits to the data-store cannot be made directly. Edits must be batched into edit events which will be applied at a later sync point. This application is where copy-on-write behavior will be performed.
Note: this means that the application code generally cannot read back any edits it just made.
An analogy of this approach is that the data-store is like a Redux data-store, and edits must be made via Actions and are applied via a Reducer
Live Previews
Cases like dragging a slider in an editor, among other kinds of edits, typically want their changes to be made available for the next render. However, we don't want to snapshot these intermediate values or add them to an undo/redo history.
The desired approach is for the data-store to have two different roots: the authoritative root and the "live" root.
Live edits can be "cancelled" by dropping the live root at any time.
Note that it may be overly-complex to go for a full Reducers approach to edits. That can needlessly spread out code that deals with making edits and applying the edits in a way that may be especially painful in non-dynamic languages (and it's not that pleasant even in JS).
Undo/Redo
When edits are applied, a current snapshot of the data-store (just a reference to the root object!) is stored as part of the undo history. This allows Undo to easily roll back by replacing the live version with the current snapshot.
The editor state could even be fully scrubbed via just the edit history, as "applying" old versions of state is efficient and guaranteed lossless.
Observers
The observer pattern should be relatively easy to implement efficiently. An observer would consist of a path and a cached (weakly-held?) object reference.
When the root object is modified, all observers are notified of the change. Each observer re-queries its path and compares to the cached value.
If the cache value is out-of-date, the new value is stored and the observer "fires." Otherwise nothing happens.
This is essentially the same as React state.
Serialization
The natural representation of Slate data would be a JSON tree. More of the core Slate types would directly translate to JSON types, while a few special cases might translate to a JSON object with a $type field or the like.
It would be useful to attach Schema types to each Slate object or array, as well. This will be all but required for polymorphic data.
Efficiency
The primary source of inefficiency in this design is that every mutation requires making a copy of an object and all its tree ancestors. For most objects this cost should be light, however large arrays could suffer.
Several options present themselves for arrays. The solutions depend on whether the arrays require random-access or not. If random-access is required, a multi-level chunked approach to array storage would greatly minimize the cost of changing an elements or adding/removing elements at the end.
If random-access is less important, a variably-sized chunked strategy could make inserts/edits/changes at arbitrary positions efficient.
Further optimizations can be performed when an objects (and all its tree ancestors) are uniquely-held. For instance, changes to the preview tree. When the objects are uniquely-held we can mutate in-place as we don't have to worry about other references wanting to see a snapshot of the old data. Note: all ancestors must be uniquely held; if just a single object is uniquely-held but one of its parents is not, then mutating the object would still cause mutation to a tree snapshot. Thankfully, detecting this case is simplified as tree edit events are applied in batches (and likely single-threaded) so that process can track whether a tree branch is uniquely-held as it descends the tree to apply edits.
This is a design document for a portion of our editor architecture. inspired partially by Our Machinery's "The Truth" mixed a bit with the Elm Architecture popularized by React/Redux.
Design
Overview
Maintain a data-store as a tree of objects/properties (and arrays) as an immutable data structure, with edit events generated by the editor UI and applied and observed at fixed sync points. The immutable data structure allows snap-shots and "perfect" undo/redo.
Data Store
The data store is essentially just a tree of objects. An "object" in this can be a map (string -> properties) or an array (index -> properties).
Map keys will be limited to a specific format
[a-zA-Z_][a-zA-Z0-9_-]*, and array indices will be limited to[0,N)whereNis the array size. The map key limits are to enable property paths, and to keep some serialized formats safer/simpler.Properties can be the typical primitives like
int64,uint64,float32,string,bool, child objects, and a few other specialized handy types (vec3,asset, etc.).For the most part, the data-store can be likened to an in-memory JSON tree.
Property Paths
Referencing an object or property in a data-store can be achieved by the use of a dotted notation made of Map keys and Array indices, e.g.
entities.0.components.transform.position.yA component in a path must be either of the Map key format or must be an integer of the form
([0]|[1-9][0-9]*).It will be reasonable to cache values at property paths for a single frame, but across frames this would result in potentially out-of-date data being read. It may be reasonable for cached values to detect when this has happened and only re-cache the value as necessary, but this feels like it may be a premature optimization.
Iteration and Reading
A read-only reference to an object is allowed by grabbing a (counted) reference to that object. This reference should also include a reference to the data-store itself and some information on the path used to acquire the object.
With these, it is possible to provide efficient native iteration of object keys/indices, queries on key existence or Array length, etc.
Immutability
As Slate is intended to be an immutable data-store pattern, these references will be forever immutable and never able to observe any changes. Uses that want to reference "future" edits to a data-store would need to store the path, not a reference.
The immutable nature of Slate is maintained by offering no direct mutation of the data-store, instead requiring edit events. The application of edit events will apply copy-on-write semantics so any existing snapshot or immutable reference will see no changes.
Note that immutability essentially requires that changes to any property will need a copy-on-write behavior for the property's object, and changes to any object will require copy-on-write behavior for the object's parent, and so on.
The end result is that editing any single bit of the data-store will result in a new object at the root if there are any snapshots.
Edits
Edits to the data-store cannot be made directly. Edits must be batched into edit events which will be applied at a later sync point. This application is where copy-on-write behavior will be performed.
Note: this means that the application code generally cannot read back any edits it just made.
An analogy of this approach is that the data-store is like a Redux data-store, and edits must be made via Actions and are applied via a Reducer
Live Previews
Cases like dragging a slider in an editor, among other kinds of edits, typically want their changes to be made available for the next render. However, we don't want to snapshot these intermediate values or add them to an undo/redo history.
The desired approach is for the data-store to have two different roots: the authoritative root and the "live" root.
Live edits can be "cancelled" by dropping the live root at any time.
Note that it may be overly-complex to go for a full Reducers approach to edits. That can needlessly spread out code that deals with making edits and applying the edits in a way that may be especially painful in non-dynamic languages (and it's not that pleasant even in JS).
Undo/Redo
When edits are applied, a current snapshot of the data-store (just a reference to the root object!) is stored as part of the undo history. This allows Undo to easily roll back by replacing the live version with the current snapshot.
The editor state could even be fully scrubbed via just the edit history, as "applying" old versions of state is efficient and guaranteed lossless.
Observers
The observer pattern should be relatively easy to implement efficiently. An observer would consist of a path and a cached (weakly-held?) object reference.
When the root object is modified, all observers are notified of the change. Each observer re-queries its path and compares to the cached value.
If the cache value is out-of-date, the new value is stored and the observer "fires." Otherwise nothing happens.
This is essentially the same as React state.
Serialization
The natural representation of Slate data would be a JSON tree. More of the core Slate types would directly translate to JSON types, while a few special cases might translate to a JSON object with a
$typefield or the like.It would be useful to attach Schema types to each Slate object or array, as well. This will be all but required for polymorphic data.
Efficiency
The primary source of inefficiency in this design is that every mutation requires making a copy of an object and all its tree ancestors. For most objects this cost should be light, however large arrays could suffer.
Several options present themselves for arrays. The solutions depend on whether the arrays require random-access or not. If random-access is required, a multi-level chunked approach to array storage would greatly minimize the cost of changing an elements or adding/removing elements at the end.
If random-access is less important, a variably-sized chunked strategy could make inserts/edits/changes at arbitrary positions efficient.
Further optimizations can be performed when an objects (and all its tree ancestors) are uniquely-held. For instance, changes to the preview tree. When the objects are uniquely-held we can mutate in-place as we don't have to worry about other references wanting to see a snapshot of the old data. Note: all ancestors must be uniquely held; if just a single object is uniquely-held but one of its parents is not, then mutating the object would still cause mutation to a tree snapshot. Thankfully, detecting this case is simplified as tree edit events are applied in batches (and likely single-threaded) so that process can track whether a tree branch is uniquely-held as it descends the tree to apply edits.