Coding Ouroboros

At DEVLIKE, we’re in the middle of writing a full-fledged graph editor. Last week, I was working on implementing a menu to add components to nodes. It was designed to be quite flexible and show lists of components loaded from a file when the editor boots.

The components we want to add have fields of certain datatypes and in a certain order, and we have a small DSL (Domain-Specific Language) for typing them out similar to type definitions in other languages. Here’s a few examples:

Position: { x: f32, y: f32 };
Comment: s128;
Tag: unit;
Error: { text: s128, line: u32, caret: u16, filename: s32 };

But let’s backtrack a bit and explain our environment: this is all done in Rust in which we are developing a framework for doing almost anything with graphs stored in memory in an ECS (Entity-Component-Systems) friendly manner for fast access and convenient usage. Our framework is called Mosaic, it’s nice like that. Instead of distinguishing nodes and arrows, we call the entities inside Mosaic tiles.

Mosaic allows you to store any kind of graph and process it using any semantic you choose. Based on this framework, we’re developing an editor (GRASP) that will be able to give semantic layers to your graphs and transform them to do whatever you need, for example: transforming a finite-state machine directly to code or even a compiled library ready for use elsewhere.

Towards this goal, we need some way to create component types that will be shown in the editor through a context menu. It would be nice to have them organized into categories.

In code this would be a vector of category structs and category entries. These are simple types:

The display property of an entry defines a nicer label to show in the menu (for example, instead of MyComponent, we could show it with spaces). We can also hide things from the menu both on a category level and per entry. The details of each entry are lost here and kept in another place, but that’s outside of this blogpost.

As you can see, this structure is a kind of tree, and that’s a graph! Why not move it to our Mosaic?

Our Setup Before

Before even thinking of moving, to add a type into Mosaic, we had what amounts to this:

We can vectorize components so that we don’t repeat ourselves too much:

The next logical step was splitting this whole list into files, separating them by category and loading them from there. We won’t linger on how to implement this behavior, but it felt like we can go a bit further: most of our components are actually unit, which means they don’t carry any fields and data – they are markers.

We repeat ourselves again by typing : unit; over and over again in multiple files, but not doing so would mean we have to change our DSL, or add another one. So, how about we just draw a category and its items? Do they even need to be text?

Saving this graph to a .mos file enabled us to load it afterwards while booting the editor:

The load_mosaic_components_from_file is the same one we use for any other Mosaic document, meaning that we have zero special-case work with parsing or figuring out what is what. What we lack, however, is what it means to be a component menu…

Adding Semantics

Instead of using the structs you’ve seen above – the ones that describe categories and their entries – we can now query the graph directly:

let all_categories = loader_mosaic.get_all().iter()
                                  .filter_objects()
                                  .filter(|o| o.get_arrows_into().is_empty());

for category_tile in all_categories { ... }

We query for all of our categories – specifically objects that have no arrows going INTO them. They then lead into components. To do so, we simply repeat the same practice: we now need all the objects at the end of any arrow going FROM the category.

for entry_tile in category_tile
                     .iter()
                     .get_arrows()
                     .get_targets()
{
    ...
}

Now we need to get this into the menu:

if !item_tile.get("hidden").as_bool() && 
    ui.menu_item(DisplayName(item).query())
{
    for selected_entity in &self.editor_data.selected {
        selected_entity.add_component(
            &Label(item).query(),
            void(),
        );
    }
}

Here’s what this looks like in a picture:

We could now erase the Rust definitions of CategoryComponent and CategoryEntry from our code as we’ve completely circumvented them: the giant snake is now eating its own tail, and hyped about it! We draw a picture, and it gets evaluated into a custom semantics of defining a menu.

But maybe our snake is actually a dragon. Let’s investigate…

Bonus Round

What we currently have is, in a way, an “interpreted” menu. We load the data from the file every time, and then get it into a form that’s readable by traversing the arrows and getting the labels from the nodes. This form isn’t perfect for running inside a core loop – our entities are most probably still nodes and arrows visible in the editor – this means they have a position property, a label, etc. We can go lean and mean with them now by compiling them into a much smaller, more to-the-point graph.

First off, some new definitions:

ComponentCategorySet: unit;
ComponentCategory: { name: s32, hidden: bool };
ComponentEntry: { name: s32, display: s32, hidden: bool };

As you can see, we are mirroring the Rust side of things, except that we are removing structural information: the category data doesn’t hold the info that a category contains entries – this is going to be in the graph.

If we still have the Rust side structs, a one-to-one transition grows out quite naturally:

We now have a sort of “emulation” of Rust structures within Mosaic, and we can’t even draw this graph anymore – it holds no visual data, just the relationships. It’s perfect for loading into the editor at boot as it requires ZERO prep.

We can think of this new graph as a “compiled” version of the initial one. We actually made a transformer of data from one graph into another, similar to what happens to code when it’s compiling. Instead of the image of the graph that we can’t render, here’s the code we no longer need within the core loop:

Creating new component types for GRASP is no longer a code change, rather making a simple graph via mouse, and loading it at boot at zero cost. We wanted to lift our code from text to graph, and there it is! Like an Ouroboros, our graph that we coded ate the code that made it and now we have fewer lines, more pictures, and we didn’t sacrifice speed! Until next time, keep eating your tail drawing!