Moving from a list of nodes to a tree #2403
Replies: 7 comments 22 replies
-
|
CC @miguelcmedeiros @brian-superlist @knopp @Jethro87 @jmatth @aloisdeniel @BazinC @jezell - I'd appreciate your thoughts on this possible shift in |
Beta Was this translation helpful? Give feedback.
-
|
I hope you don't mind me chiming in, but this is something I am very interested in. I've been working on creating an outline editing package based on super_editor in the last weeks, and this would make things much easier. With my work based on a recent super_editor from main branch, I decided to go for an To illustrate this, here a short window of the editor. My notion of a Treenode means a data structure that contains a title DocumentNode and zero or more ParagraphNodes. As the DocumentNodes are linearly exposed via the MutableDocument interface, the core super editor library does not need any knowledge about my tree, but commands, reactions and keyboard actions do, by casting the editor's document to an OutlineTreeDocument. While the caret can be moved seamlessly between the nodes, selections are modified by a reaction to assure the user does not violate the tree structure. I also use reactions to take care of the caret jumping over hidden areas, when parts of the document are folded, as with super_editor as is I did not find a way to implement this earlier in the pipeline without having to rewrite larger parts. outline_editor.mp4While the distinction between a "tree node", that only defines logical document structure, and a DocumentNode for the editing experience lead me to a somewhat confusing nomenclature and may not fit for every use case, it worked out for me, as outline editing is very much a structure thing. My main project is not far enough that I could really judge if my approach holds in the long run, but it works fine enough for now. Right now, I stopped working on the outline library, as I suspect with the advent of immutable nodes and your work on a tree structure, a bigger refactoring or rewrite will happen anyway, and because for me it does enough for now to continue on other aspects of my project. |
Beta Was this translation helpful? Give feedback.
-
|
Thanks for the writeup @JostSchenck - I appreciate the effort you've put in there. Hopefully we come up with something that makes things easier on your end. |
Beta Was this translation helpful? Give feedback.
-
|
I can see how it is definitively more complex, but in my opinion it is also required if super_editor wants to be the final boss of editors. Implementing tables, or columns layouts with current implementation is tedious, and having a tree representation would make their implementation simply natural. A nice implementation that can be used as reference is ProseMirror. The documentation is a great source of inspiration! Also, a great library that should be considered is Yjs, and more specifically its Rust+FFI implementation : y-crdt. This allows real time updates from multiple sources, and smartly resolve conflicts. It solves a lot of issues, and has a tree representation. |
Beta Was this translation helpful? Give feedback.
-
|
ProseMirror looks interesting. There are definitely some parallels between their chosen approach and some decisions we've already made. ProseMirror chose to represent inline nodes as a list of nodes (instead of the DOM's approach to use a tree) to better support text formatting. We have ProseMirror makes their nodes and document immutable. This is something we already have in progress: #2384 WRT queries, it looks like ProseMirror has embraced both tree-based queries, and a Quill-style counting mechanism:
An interesting callout on their index system:
This seems to suggest that the logical node indexing and counting system is actually based on the visual question of where the caret might appear or move. That's an interesting decision because I've seen different caret position policies for the same document situation. Think about something like inline code. I've seen apps where you can position the caret at the end of the inline code, and then press right arrow, and move the caret to just beyond the inline code. I've also seen apps where you can't do that. The later apps should probably be considered buggy, but the point remains that different apps might want different rules about caret placement, so it's a bit odd that such a policy would be enshrined in the core document data model. ProseMirror uses a concept of "transformations" to alter a document, with essentially the exact same motivation that lead us to develop our editor pipeline (requests, commands, events, reactions): https://prosemirror.net/docs/guide/#transform The ProseMirror description of editor state nearly identically reflects the pieces we assembled early on: 
|
Beta Was this translation helpful? Give feedback.
-
|
should it be not tree, but something like custom embeds in Quill delta? New table module was implemented using this feature It allows embed any custom type, but the most trivial is embedded delta. |
Beta Was this translation helpful? Give feedback.
-
|
YJS added support as well |
Beta Was this translation helpful? Give feedback.
-
|
That table construct is effectively a tree - the table is a node that points to rows and columns which points to cells. Also, Delta is a serialization format, not a runtime data structure. Quill Deltas text is parsed into one or more data structures that represent the content while the app is running. Then the app content is re-serialized to text whenever somebody wants to export the updated deltas. If I'm wrong about any of that, please let me know. |
Beta Was this translation helpful? Give feedback.
-
it's a document format of quill editor
I did not get it. I don't think it's the case for quill editor, Delta is a document format for quill editor, "parchment" (blots) is presentation (DOM elements) of this format |
Beta Was this translation helpful? Give feedback.
-
|
YJS itself also directly stores quill style deltas in Y.Text, so a lot of the editors just work straight with the deltas. However, Y.ProseMirror uses Y.XmlFragment, which might be a little easier of an approach. They also started out with a whole editor with it's own set of concepts before supporting CRDT via plugins to get collaborative editing working out of the box, and Xml fragment was the easiest to map their structures into without reworking everything: https://github.com/yjs/y-prosemirror I'm a huge fan of ProseMirror. I think anything that follows in its footsteps is probably going down a good path. |
Beta Was this translation helpful? Give feedback.
-
|
This question touches on a lot of different subjects that I'm struggling to tie together in a coherent way, so I'll just summarize my opinions up front:
> If anyone has good alternative suggestions, I'd like to hear them.I think a tree structure is the right way to go to implement the features you listed, but to play devil's advocate for a second: you can get most or all of the way to each of those features without a tree.
Regarding yjs and similarA couple other comments have already called out the yjs/yrs libraries as a potential way to store document state. As much as I'd like sync as a natively supported feature in SuperEditor, I don't think adding a dependency on FFI is the way to go. I think a more reasonable approach is to consider that some implementations may use other data structures as their source of truth, in which case
This is actually possible right now, and I have a very basic and barely working proof of concept that uses Loro to store and sync two SuperEditor documents. Regarding ProseMirrorProseMirror was also already mentioned in another comment, so I'll just add a +1 to using it as a reference if/when SuperEditor makes significant changes to its document structure. It is successful enough in the JS space to have at least one commercialized offering built on it (TipTap, which I think also uses yjs for sync), supports an official sync/collaboration interface without being opinionated about the implementation, and has a change transaction system with an official undo/redo plugin built on top of it. It seems ideal as a document editor framework. I don't know that I would call any of these implementations replacements for a truly tree based document structure, but it is possible to approximate such features using just the current flat list implementation. |
Beta Was this translation helpful? Give feedback.
-
Ok. So this implies the following tradeoff:
Both of those changes are highly disruptive and complicated. My initial thought is that the first option would be much better received by most users. I think most users would be overwhelmed by creating a new document layout, even if we try to make it easier, and document it. But feel free to tell me if you think I'm wrong about that.
Answers to such UI/UX questions can probably be answered by inspecting Notion, which supports collapsible headers that don't apply to all content below them. Rather, they apply to select blocks below them.
In general, we want to prohibit the fewest things possible. This sounds like an application decision, not a toolkit decision. As for serialization, that depends on what you're serializing to. I don't think we can uphold the idea that we can always serialize to flat text. That certainly isn't what Google Docs or Word does - they use a complicated hierarchical XML serialization. Quill Deltas are hierarchical with JSON. ProseMirror is hierarchical. Even Markdown, while superficially flat, requires structure to make any use of its overall syntax. |
Beta Was this translation helpful? Give feedback.
-
I don't think that making it possible to integrate a custom document layout is all that disruptive on the Super Editor side, at least within the constraint that the layouts grow vertically like All that being said, I think it would make sense to implement collapse/expand behavior upstream because there are several other parts of Super Editor that need to be updated to support it: the gesture system needs to understand that a node in a collapsed section isn't available for hit testing, moving the caret needs to either skip collapsed sections or automatically expand them, etc. These are all things that are difficult or impossible to implement without upstream changes. To summarize: I think a collapsible sections feature should be implemented upstream because it involves complexities that are difficult or impossible to work around downstream. At the same time,
Agreed, I just wanted to call it out because it's a decision that Super Editor has already made in its default editor implementation. Moving to a tree structure and utilizing it to implement collapsing sections moves that default implementation from something that resembles a word document to something that more closely resembles a notion document. That may or may not be desirable for all downstream users, so it might be best to consider how hard it would be to opt out of the new behavior.
My comments are purely related to the in-memory data structures and how the editor interface is presented to the user. The way I described converting the tree back to flat text was poor wording on my part. What I meant was ensuring this hypothetical document tree could be fully represented by the current UI. My second example, with a paragraph sibling to a heading, fails that criteria because |
Beta Was this translation helpful? Give feedback.
-
FFI requirement really would be a drag and isn't supported at all by dart2js or dart2wasm at the moment. However, for CRDT the only reasonable path is FFI or port YJS to dart. I think there would be a ton of value in doing that because there are a lot of missing pieces like what do you do on the server side, but it's a bit of a project on its own. |
Beta Was this translation helpful? Give feedback.
-
|
For context we currently do flutter_quill + yjs + hocuspocus. It works, but it's a lot of complexity that we'd like to get rid of at some point. We'd definitely be interested in working with others on a dart yjs port if there was interest, as that's the ideal pathway toward simplification. That said, I don't think super_editor needs a dependency on CRDT. ProseMirror is a good example of a way to make CRDT work with an existing system without baking it in. |
Beta Was this translation helpful? Give feedback.
-
|
I'd like to avoid getting too deep into CRDTs, YJS, etc, except to ask the following question. Are any of you aware of any document structure decisions that are likely to be critical to CRDTs and YJS that can't be overcome through a translation? In other words, can you think of anything that would satisfy the following:
To help inform those questions, I want to make sure everyone understands the API that we're really talking about here. The When it comes to altering documents, we have Thus we have a Command and Query Responsibility Segregation (CQRS), which hopefully minimized the imposition of Super Editor on the underlying document format. |
Beta Was this translation helpful? Give feedback.
-
|
I'm revisiting document trees. Hopefully we'll get something merged relatively soon. However, I've come upon another fundamental question with tree modeling. HTML and ProseMirror utilize a generic node concept, which only becomes specialized by adding properties. HTMLConsider some HTML: <section>
<h1>Some Title</h1>
<p>Some paragraph of information.</p>
<ul>
<li>List item 1</li>
<li>List item 2</li>
</ul>
</section>When this HTML is parsed into a DOM, we don't get different classes like Moreover, because every <table>
<tr>
<td>Row 0, Col 0</td>
<td>Row 0, Col 1</td>
</tr>
<tr>
<td>Row 1, Col 0</td>
<td>Row 1, Col 1</td>
</tr>
</table>Notice that this approach can't prevent attempts to insert incompatible children into a table. What would it mean to place a ProseMirrorProseMirror also uses generic
Super EditorThe question then comes to the new document structure in Super Editor. Do we change all nodes to be generic artifacts with a Here's a look at some pseudo code for these two approaches: // Examples similar to our existing modeling style, with explicit node types.
//
// Advantages:
// - Unique APIs
// - Each node can expose Dart properties unique to itself, e.g., `table.rowCount`.
// - Each node can provide specialized constructors, e.g., `TableNode(rows: [])` and `TableNode.sparse()`
//
// Disadvantages:
// - Whatever generalized traversal mechanisms that we need to support for a
// Document, must be implemented by each grouped node type. This might be trivial
// with some kind of inheritance, or it might be very tedious.
TableNode.sparse(
Editor.createNodeId(),
cells: {
(0, 0): TableCellNode(
Editor.createNodeId(),
content: [ParagraphNode(id: Editor.createNodeId(), text: AttributedText("Row 0, Col 0"))],
),
(1, 1): TableCellNode(
Editor.createNodeId(),
content: [ParagraphNode(id: Editor.createNodeId(), text: AttributedText("Row 1, Col 1"))],
),
},
);
TableNode(
Editor.createNodeId(),
rows: <List<DocumentNode>>[
// Row 1
[
TableCellNode(
Editor.createNodeId(),
content: [ParagraphNode(id: Editor.createNodeId(), text: AttributedText("Row 0, Col 0"))],
),
TableCellNode(
Editor.createNodeId(),
content: [
ParagraphNode(id: Editor.createNodeId(), text: AttributedText("Row 0...")),
ParagraphNode(id: Editor.createNodeId(), text: AttributedText("Col 1")),
],
),
TableCellNode(
Editor.createNodeId(),
content: [ParagraphNode(id: Editor.createNodeId(), text: AttributedText("Row 0, Col 2"))],
),
],
// Row 2
[
TableCellNode(
Editor.createNodeId(),
content: [ParagraphNode(id: Editor.createNodeId(), text: AttributedText("Row 1, Col 0"))],
),
TableCellNode(
Editor.createNodeId(),
content: [ParagraphNode(id: Editor.createNodeId(), text: AttributedText("Row 1, Col 1"))],
),
TableCellNode(
Editor.createNodeId(),
content: [ParagraphNode(id: Editor.createNodeId(), text: AttributedText("Row 1, Col 2"))],
),
],
// Row 3
[
TableCellNode(
Editor.createNodeId(),
content: [ParagraphNode(id: Editor.createNodeId(), text: AttributedText("Row 2, Col 0"))],
),
TableCellNode(
Editor.createNodeId(),
content: [ParagraphNode(id: Editor.createNodeId(), text: AttributedText("Row 2, Col 1"))],
),
TableCellNode(
Editor.createNodeId(),
content: [ParagraphNode(id: Editor.createNodeId(), text: AttributedText("Row 2, Col 2"))],
),
],
],
);
// Example similar to HTML.
//
// Advantages:
// - Some behaviors around node traversal can get generalized because all
// GroupNodes have the same API. It's not clear what this generality might
// be or how helpful it would be.
//
// Problems:
// - Too generic
// - Commands won't have access to Dart properties that are specific to a
// type, e.g., tables, because all GroupNode's will have the same API.
// - Layout will have to handle the possibility of unsupported child nodes
// because any DocumentNode can be given as a child to a GroupNode, when
// something like a table might only support TableCellNode's.
GroupNode(
type: "table",
id: Editor.createNodeId(),
children: [
LeafNode(
type: "table_cell",
id: Editor.createNodeId(),
metadata: {
"cell": (0, 0),
},
children: [
LeafNode(type: "paragraph", id: Editor.createNodeId(), metadata: {"text": AttributedText("Row 0, Col 0")}),
],
),
LeafNode(
type: "table_cell",
id: Editor.createNodeId(),
metadata: {
"cell": (1, 1),
},
children: [
LeafNode(type: "paragraph", id: Editor.createNodeId(), metadata: {"text": AttributedText("Row 1, Col 1")}),
],
),
],
); |
Beta Was this translation helpful? Give feedback.
-
|
Do you see a meaningful benefit in the separation of schema from nodes, where nodes are generic and the schema makes them specific? Or, do you think this is just a consequence of ProseMirror being built on top of browser fundamentals, which already included |
Beta Was this translation helpful? Give feedback.
-
|
ProseMirror doesn't really build on top of browser fundamentals. If the browser worked well, ProseMirror wouldn't exist. ProseMirror itself came about from the realization that to make editing work well in the browser they needed to make their own entirely separate document object model instead of trying to build on top of HTML nodes. HTML itself has typed nodes, so the Prosemirror model is a bit of a departure from HTML, and is more like XML + an XML Schema. We did the same kind of separation of schema and node in our implementation of document trees for sync which we then added support for SuperEditor for. Definitely was influenced subconsciously by the ProseMirror design, but it works well. I think I prefer a generic document node + attributes. Ideally, I should be able to generically sync, save, and inspect a any document without needing a factory to construct a custom data structure for each node. It was a lot more code to build sync for SuperEditor compared to Quill for example because of the use of so many strong types in SuperEditor instead of a generic data structure like Quill uses. |
Beta Was this translation helpful? Give feedback.
-
I think we need much more than preferences. Such a change would rewrite nearly every assumption across all of Super Editor. The operative questions are "what specific gains do we get with such a change?" and "what costs do we pay for such a change?".
I don't know that this is a generally true or accurate statement. I'd need to see a cost/benefit analysis. Obviously some things become more convenient in that world. But also, some things become more difficult, or even impossible.
Quill is a proof of my point above. Quill makes very simple things very easy, and it makes complicated things very tricky. It's not trivial to encode a table in Quill. Yet, if you fundamentally have a "Quill editor", then that's what you have to do. Moreover, Quill is really more of a transport/storage format than it is an in-memory format. If your in-memory data structure is a list of Quill deltas, then you're constantly traversing the Deltas to execute operations - either that, or you've added an index on top of the Quill deltas so that you remember where things are, at which point you've kind of created a new document structure on top of deltas. Also, everything in your document has to make sure that it makes sense from a "counting" perspective, because Quill comes with this requirement that everything in a document support a concept of length, even if length doesn't really make sense. So there are some weird things about Quill and we shouldn't pretend those things don't exist just because there might be some positive things, too. The second analysis also needs to happen in reverse, which is, did SuperEditor require more work because its current approach is fundamentally difficult for sync'ing? Or, is it because SuperEditor doesn't include some APIs in its strongly typed system that could have made it easier to implement sync? Adding missing APIs is probably orders of magnitude easier than completely re-writing the document structure. |
Beta Was this translation helpful? Give feedback.
-
I believe the main benefit is that it makes things like sync, persistence, and extension a lot easier. The tradeoff is likely to be seen in additional complexity in the editor views.
Yeah it's definitely not easy to do in Quill because Quill is just a flat list of deltas. It's closer to SuperEditor in terms of some of its challenges with document structure being limited by being a flat list. ProseMirror's model is a lot better than Quill's model. Both are generic, but ProseMirror's is a generic tree and Quill's is a flat list with generic attributes laid on top.
I think if every super editor node extended a base type and had a protocol that exposed all the changes and state generically for each node type then it would definitely be easier. But then you kind of end up with a generic node type anyway, an possibly a lot of extra code if you have to implement a protocol to notify about changes to every field. However, as soon as you can extend the node type you can just add a field to your class and put state in it without exposing change notifications or implementing whatever protocol is required to let someone generically see the data. Those problems go away if you keep the node type generic and instead make people extend the schema type. |
Beta Was this translation helpful? Give feedback.
-
IMHO, the opinionated nature of Super Editor with typed nodes is great. It makes the code easier to understand, follow and trouble shoot. It's important however that developers can define their own custom node types, and that those node types are free to implement their own behavior in the editor (with regards to things like rendering, cursor movement, text selection etc.).
To me this sounds more like a symptom of SuperEditor documents not having an established way of being serialized to a structured format. |
Beta Was this translation helpful? Give feedback.
-
|
Hi, any updates on moving from a list of nodes to a tree? @matthew-carroll |
Beta Was this translation helpful? Give feedback.
Uh oh!
There was an error while loading. Please reload this page.
-
We have some features that we want to implement, which imply a document hierarchy where currently there is none.
For example, we want to support tables, where each cell contains any number of other nodes. We also want to make it possible for clients to create the concept of "banners", which are decorated boxes that contain any number of other nodes.
These features impact painting, layout, and UX. E.g.,
These requirements seem to point towards the need for a tree-based document, instead of a list-based document. This requirement isn't a surprise. Most document formats are structured as trees, e.g., XML, HTML, Markdown. However, we wanted to take our simplistic document list as far as we could before investing in the complexity of a tree-based document. Along those lines, if there's a reasonable path to implement these requirements without moving away from a document list, I'd like to hear about it.
API Problems
By leaning into a document list instead of a document tree, we've created a number of heavily used APIs that don't necessarily make sense in a tree.
Document APIs:
Edit requests:
In other words, all APIs that imply a natural order to nodes are now ambiguous, at best.
We can, in theory, continue to support these APIs by selecting a single tree traversal policy. For example, we can say that we'll always traverse the tree in a depth-first order. This would retain ordering, and would allow us to speak about each node as sitting at a specific index. However, it's unclear if any of the existing uses of the aforementioned APIs would work as expected with tree traversal indices. For example, the composite nodes themselves would be traversed, and would receive an index. Should composite nodes interact with UX policies the same way as a paragraph? Does it make any sense for the caret to placed within a composite node? Probably not.
Comparisons
HTML
HTML is probably the most popular document format due to its use in every webpage. HTML is based on the DOM, which is comprised of a tree of Elements:
https://developer.mozilla.org/en-US/docs/Web/API/HTML_DOM_API
HTML Elements are notoriously annoying to work with. The use of this tree structure eventually lead to the advent of JQuery - a collection of functions for more easily querying and mutating the DOM.
https://jquery.com/
Markdown
Markdown is a very simple markup language, which is used in many text editors today. This discussion post is written in Markdown.
While the syntax is minimal, the structure remains hierarchical. I don't know the exact reason that Markdown went hierarchical, but one important detail about Markdown is that it officially supports embedding HTML within it. Therefore, Markdown was probably constrained by HTML's existing decision.
Here's a random specification and implementation of a Markdown Abstract Syntax Tree (AST): https://github.com/syntax-tree/mdast
DocX
DocX is Microsoft's document format for Word. It's serialization format is XML, so it's a hierarchy that's similar in nature to HTML.
LaTeX
LaTeX is a document format that's used heavily in academia. It also uses a hierarchical structure.
Example:
Non-Tree Document Formats
In a quick search for popular document formats that aren't tree-based, the only formats I found are Comma-Separated Values (CSV), and Rich-Text Format (RTF). Both of these formats have a far more narrow application than what Super Editor needs to support.
Should we move to a tree structure?
The first question we need to align on is wether a tree-based document is the right move. It will be a significant move, and will almost certainly require significant rework among our users. If anyone has good alternative suggestions, I'd like to hear them.
Should we separate logical nodes from visual nodes?
Currently, every node in a
Documenthas a visual purpose: paragraph, image, horizontal rule, list item, task.In a world with hierarchy, we need to decide whether we should use a special type of node for hierarchy (
CompositeNode), or whether we start from the premise that any node might have children.Beta Was this translation helpful? Give feedback.
All reactions