sd-visualiser/sd-visualiser

String diagram visualiser

sd-visualiser's Issues

Support 'weak' edges

We need a way to deal with non-DAG structure. Currently, our code makes some heavy assumptions that we deal with DAGs only.

Type checking hypergraph

We could perform a type checking phase on the hypergraph to check that operations have the appropriate number/right type of inputs.

Interaction: Gather

The tool should be able to gather nodes together.

This relies on being able to select a group of nodes, likely with #18. We would then perform movements on these nodes to move them to adjacent levels. There's multiple ways we could do this, but we will likely have to make arbitrary choices at some point.

It also might be a wanted feature to also gather the associated text with the selected subgraph. This could be quite difficult as we have no mechanism to modify the text at the moment. We could either try to regenerate the specific part of the text or just try to reorder bind statements, but either of these requires creating new text.

Investigate different lp solvers

We might be better off using HIGHs if we can

Click on a thunk to expand it

We need to change the unfold to specify which thunk to expand (idea is to use the node index from #2). Also add click handler on each thunk node.

"About" window

We should have a button that displays a window with some about text.

Things to include:

• authorship
• license text (this is borderline necessary, depending on how you read the license)
• which LP backend we have compiled against

Do not render on every frame if text did not change

Subgraph selection

We likely need a way to be able to select some notion of subgraph of the hypergraph.

Compile button instead of live preview

It's a bit confusing that if some code is edited, the graph may relayout everything. We decided that an explicit 'compile' button would be nicer UX.

Fix shortcut text on buttons

It currently overlaps with the button text for some reason

Decompilation returns corrupt for selection with thunk outputs

For example take examples/sd/corrupt.sd and select the 1 and minus

Decompilation should change on selection expansion

When we click an arrow in the selection to expand it by a node, the decompilation text should also change

Multi output thunks

I think MLIR graph regions support thunks with multiple outputs, so we likely need to be able to support this. The main barrier here is that we will need thunk outputs to not align with the outputs of the thunk node, as there will be a different number of each.

We could try to make this an option, as it is nice to have sometimes

Try to store span information in AST

There's a few things where it would be useful to be able to map a node in the AST to the portion of the text that defines it. Pest gives us this information but we currently throw it away when converting to an AST.

Add boxes around expanded thunks

Blocked by #2.

When expanding a thunk, we append its label to the every node in the body (to keep track of where nodes come from). Then it should be easy to collect all nodes belonging to a thunk and compute the bounding box.

Improve language abstraction

We currently have one AST for our languages. It could be nice to try to make a better abstraction on language. The "obvious" solution is to pretty much only accept hypergraphs, though this will probably lead to a bit of code duplication. It would be nice if we could avoid duplication "variable representation" -> "hypergraph" logic that we do.

Not really sure what the solution is here, but we should investigate it before doing MLIR

Highlighting text/nodes on hover

It would be nice if hovering over text highlighted the corresponding node in the graph and if hovering over a node in the graph highlighted the corresponding text.

Make AST recursive and use weak edges

Explore different layering algorithms

The hypergraph -> monoidal graph translation starts by setting a layer to each operation. There are two possible improvements:

• Make it aware of input and output nodes so that these are always put on their own layer.
• At the moment operations are put in the latest layer possible. We could explore other algorithms for e.g. reducing the layers spanned by a single edge.

Add node indexes to monoidal graph

Add backlinks from the operations of the monoidal graph to the hypergraph. These should be lists of NodeIndexes, which specify which thunk of the graph the operation is in and which operation of the appropriate thunk.

Have option to expand/de-expand all thunks

Could be useful for big graphs

Modular Monoidal term generation

Idea for rewrite of monoidal term generation:

• Start by generating a "dumb" monoidal term. I'm thinking this would just put one operation per layer, only use binary copies etc. Basically anything that makes it easy
• We then run a modular set of "optimisations" which improve the look of the graph
  • One would compact layers together
  • One should try to choose permutations of each layer
  • Permutations could be chosen in a cleverer way than we do at the moment
  • There could be other optimisations we could do (push deletes up as far as possible?)

Part of this change would also be to move explicit copies into the monoidal wired term, as we think the user might want to drag copies around

Make thunks separate in syntax

The syntax could have expressions like:

bind x = y.y in x

This will make the language closer to the graph representation and will allow us to clean up the syntax a lot.

Build AST from hypergraph

Get web assembly build working

Resetting the zoom/pan could default to a better zoom level

With big graphs the default it to just be zoomed in on the center of the graph.
It could make sense to use the width/height of the graph to generate an appropriate initial zoom level

Decompilation of subgraphs could be optional

Perhaps if the editor is closed you don't care about decompilation either?

Interaction: Node moving

It should be possible to drag nodes left, right, up, and down. These movements should modify the MonoidalWiredGraph but not the hypergraph.

We should think about whether we will want to be able to move copy nodes around. If we do then the MonoidalWiredGraph should probably have explicit copies and we might want to think about merging/unmerging copies and how to do that. We are pretty certain that the user should not be able to interact with swaps and that these should just be sorted for the user automatically.

Free variable inputs should be assigned different input nodes

This will mean that their order can be changed by layout and will make other layout algorithms look a bit better. It will however become hard to enforce that special thunk inputs should occur on the right.

Make monoidal term generation work with weak edges

Decompilation window on subgraphs makes the whole window way too wide

Make monoidal term generation more generic

If the inputs to monoidal graph generation were all traitified, then we would not have to generate a whole new hypergraph (or add more inputs to the generation functions) when doing things like subgraphing or cutting wires.

Tweak gaps between slices

The gaps between slices is too big. Also the gap before the first slice / after the last slice needs to be the same.

Store weights in thunks

It would be useful to allow thunks to carry weights (of a different type than operations).

I would like to store thunk addresses (from the language) in the thunk instead of in the output edge, which would not work if we allow thunks to have multiple outputs or if we allow users to bind thunks to variables (does MLIR allow this?).

Add panning and zooming

The graph display should have some viewing options. Centering would also be nice

Bug in swap minimisation

Looking at ad.chil, at the bottom the wire goo1(id: %44) is moved a long way. This shouldn't happen based on the current swap minimisation algorithm and so likely suggests that there is some bug.

Collapsible thunks in text

A nice feature could be to collapse the text of a thunk when we collapse the thunk in the graph viewer.
For example the thunk:

bind x = y.bind a = plus(y,y) in a in x

Could be collapsed to

bind x = y.{...} in x

We would need to be careful about how to treat the {...} in the text edit, as we likely would want it to act as a single atomic block with respect to deletion (i.e. we don't want to be able to delete one of the dots). Also likely depends on #15

Display parse errors to user

We could have a box under the textedit which displays parse errors (and maybe other errors) to the user. They are currently ignored.

Configurable operations

It has been suggested that our set of operations could be user configurable. A nice way to do this could be to have a json file that can be read by the tool.

Widen nodes in layout

Now that operations can expand slightly to accommodate more text, we should probably give them more space in layout so that they do not overlap.

Add text to operations (maybe also thunks)

Operations should be labelled (e.g. "0", "+", "x", etc.). Also maybe thunks?

There is a text shape in epaint. It takes a fonts argument and the only way to get the fonts is from egui:Ui::fonts, but I tried that and nothing was rendering (but I was probably missing something).

Adjust tolerance for highlighting lines

When zoomed out on a big graph it is very hard to highlight wires. We likely need to up the tolerance or make it depend on the zoom level.

Make high level user documentation

We should make a high level overview of the tool and what it can do, this could either be a readme or github wiki or maybe even rust documentation

Rendering tweaks

Thought we could have an issue to collect up tweaks to rendering that could be done.

• Make a more generic way of deciding the height of operation. For swaps we currently use the square root of the distance between the inputs.
• Positioning nodes vertically: When a node with low height appears in a slice which is tall it looks odd. We could make sure that the node renders at its normal height and/or render it closer to the top or bottom of the slice (depending if number of inputs > number of outputs) instead of always centering it
• Tweaking bezier curves. With the bigger diagrams, some of the bezier curves don't look great. Not really sure how to fix it but someone could probably mess with it for a bit and make it slightly better

We can add some more things here if we think of them

Accept MLIR input

We need to parse or input MLIR in some way

Multiple outputs for operations

To support MLIR we need to allow operations with multiple outputs. It would be a good start to add this to sd-lang

Store variables in hypergraph

Allow input wires to thunks to bend

At the moment the inputs to a thunk must be straight wires, which causes some thunks to become very wide. I think it would look nicer if these wires were allowed to bend, though it's not clear what the best way to do this is.

The simplest option is to work this into the thunk layout logic, allowing all wires to bend (with the amount of bend added to the objective function) though we will have to be careful to extend the height of the thunk

Decide how to draw blocks

In MLIR, "regions" correspond quite closely to the thunks we have implemented, though there is also a notion of "block" which is slightly different. We should decide how to draw these.

One thing to consider is that a block is always terminated by a special branching operation, which will refer to the next block
Another consideration is whether we want to draw data flow and control flow in the same way.

More information when you hover over nodes

E.g. type, variable binding.