Getting started with Rust

I haven't really thought through where this blog post is going, but it will probably just be a duplicate of 2,000 others out there (including the official documentation) which say "get started with Rust by …". But this is my living memory of doing it.

I am working from The Rust Programming Language (2nd Edition), which I will hereafter refer to as "the book".

I've just acquired a new Linux box, and apart from the obvious setup that you always need to do on a new box (installing Chrome, logging in, etc [on this occasion installing a new kernel to get the WiFi to work]), I've not doing anything with it yet. So the first thing I'm going to do is install Rust.

According to the book, I need to type this:

% curl --proto '=https' --tlsv1.3 https://sh.rustup.rs -sSf | sh

I have never used the --proto option before, but both that and the --tlsv1.3 options seem like overkill to me. Maybe they offer some level of protection against MITM attacks; I don't know. Curl usually seems pretty good to me about mismatched certificates and the like. Before passing it directly to sh, I did decide to look at the script. Hmm, pretty hairy.

So, let's go and run it.

info: downloading installer
Welcome to Rust!
This will download and install the official compiler for the Rust
programming language, and its package manager, Cargo.
Rustup metadata and toolchains will be installed into the Rustup
home directory, located at:
  /home/gareth/.rustup
This can be modified with the RUSTUP_HOME environment variable.
The Cargo home directory is located at:
  /home/gareth/.cargo
This can be modified with the CARGO_HOME environment variable.
The cargo, rustc, rustup and other commands will be added to
Cargo's bin directory, located at:
  /home/gareth/.cargo/bin
This path will then be added to your PATH environment variable by
modifying the profile files located at:
  /home/gareth/.profile
  /home/gareth/.bashrc
You can uninstall at any time with rustup self uninstall and
these changes will be reverted.
Current installation options:
   default host triple: x86_64-unknown-linux-gnu
     default toolchain: stable (default)
               profile: default
  modify PATH variable: yes
1) Proceed with installation (default)
2) Customize installation
3) Cancel installation

I'd been advised that it may ask for my password, but actually the first thing it does is ask if I want to proceed, customize or cancel the installation. I presume I want to proceed since I don't know (yet) what customizations I might want and cancelling seems somewhat self-defeating.

It then goes off and downloads a lot of things

>1
info: profile set to 'default'
info: default host triple is x86_64-unknown-linux-gnu
info: syncing channel updates for 'stable-x86_64-unknown-linux-gnu'
info: latest update on 2023-10-05, rust version 1.73.0 (cc66ad468 2023-10-03)
info: downloading component 'cargo'
  7.8 MiB /   7.8 MiB (100 %)   2.5 MiB/s in  2s ETA:  0s
info: downloading component 'clippy'
info: downloading component 'rust-docs'
 13.8 MiB /  13.8 MiB (100 %)   3.2 MiB/s in  4s ETA:  0s
info: downloading component 'rust-std'
 24.7 MiB /  24.7 MiB (100 %)   3.8 MiB/s in  7s ETA:  0s
info: downloading component 'rustc'
 61.6 MiB /  61.6 MiB (100 %)   3.4 MiB/s in 21s ETA:  0s
info: downloading component 'rustfmt'
info: installing component 'cargo'
info: installing component 'clippy'
info: installing component 'rust-docs'
 13.8 MiB /  13.8 MiB (100 %)   6.5 MiB/s in  1s ETA:  0s
info: installing component 'rust-std'
 24.7 MiB /  24.7 MiB (100 %)  12.4 MiB/s in  1s ETA:  0s
info: installing component 'rustc'
 61.6 MiB /  61.6 MiB (100 %)  14.2 MiB/s in  4s ETA:  0s
info: installing component 'rustfmt'
info: default toolchain set to 'stable-x86_64-unknown-linux-gnu'
  stable-x86_64-unknown-linux-gnu installed - rustc 1.73.0 (cc66ad468 2023-10-03)
Rust is installed now. Great!
To get started you may need to restart your current shell.
This would reload your PATH environment variable to include
Cargo's bin directory ($HOME/.cargo/bin).
To configure your current shell, run:
source "$HOME/.cargo/env"

Very good, so let's run the .cargo/env script ... seems fine.

We can now check that we have a rust compiler installed.

$ rustc --version
rustc 1.73.0 (cc66ad468 2023-10-03)

OK, so let's try creating a project. I tend to put personal projects in a "Projects" directory, but that isn't there yet because (did I mention this?) this is a brand new machine.

$ mkdir Projects
$ cd Projects
$ cargo new hello_rust
     Created binary (application) `hello_rust` package
$ find hello_rust -type f -name \* -print -o -name .git -prune
hello_rust/Cargo.toml
hello_rust/src/main.rs
hello_rust/.gitignore

So far, so good. We have a new project with a git repo, a cargo file and a main source file. We should be able to compile this, right?

$ cd hello_rust/
$ cargo build
   Compiling hellorust v0.1.0 (/home/gareth/Projects/hellorust)
    Finished dev [unoptimized + debuginfo] target(s) in 0.17s
$ cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.00s
     Running `target/debug/hello_rust`
Hello, world!

I'm not wild about chatty compilers. Get on with your job, I'm a client, not your manager. But otherwise, that's fine.

VSCode

OK. I used to develop code with just vi or Emacs (looking back, I realize that I was actually a fairly early adopter of Emacs, but it didn't seem that way at the time), but this is the 21st Century, and we use IDEs. The book suggests that I should be able to use VSCode with Rust, so let's try that.

First, I need to install VSCode on this new machine. I'm not even sure how to do that on a Linux box. Is it in a repo, or do I need to download something? Going to the VisualStudio site, it offers me a .deb download, but doesn't suggest adding a repo and linking to that. So I will download that and try and install it.

$ sudo apt install ~/Downloads/code*
[sudo] password for gareth:         
Reading package lists... Done
Building dependency tree... Done
Reading state information... Done
Note, selecting 'code' instead of '/home/gareth/Downloads/code1.83.1-1696982868amd64.deb'
The following NEW packages will be installed
  code
0 to upgrade, 1 to newly install, 0 to remove and 4 not to upgrade.
Need to get 0 B/95.7 MB of archives.
After this operation, 386 MB of additional disk space will be used.
Get:1 /home/gareth/Downloads/code1.83.1-1696982868amd64.deb code amd64 1.83.1-1696982868 [95.7 MB]
Selecting previously unselected package code.
(Reading database ... 607240 files and directories currently installed.)
Preparing to unpack .../code1.83.1-1696982868amd64.deb ...
Unpacking code (1.83.1-1696982868) ...
Setting up code (1.83.1-1696982868) ...
Processing triggers for gnome-menus (3.36.0-1ubuntu3) ...
Processing triggers for shared-mime-info (2.1-2) ...
Processing triggers for mailcap (3.70+nmu1ubuntu1) ...
Processing triggers for desktop-file-utils (0.26+mint3+victoria) ...
N: Download is performed unsandboxed as root, as file '/home/gareth/Downloads/code1.83.1-1696982868amd64.deb' couldn't be accessed by user '_apt'. - pkgAcquire::Run (13: Permission denied)

So that then seems to imply that it has installed the package code instead of my file, but maybe that just means it's choosing the name. Either way, it has installed the version I downloaded:

$ code --version
1.83.1
f1b07bd25dfad64b0167beb15359ae573aecd2cc
x64

So, let's start it up:

code

As I do this, the "Welcome" window pops up and offers me a suite of options to configure, one of which is recommended language support. Lo and behold, in there is rust-analyzer, just what I was looking for. Let me install that.

And now I can clear all that off, and open a new folder (~/Projects/hello_rust). And there it all is. I can now press C-F5 and it will compile and run, right. Uh, no. A menu pops up inviting me to "select debugger" (odd, when I wanted to run without debugging...). It does have an option to "install an extension for Rust". Let me see what I can find out.

From reading this page, it seems that what you need to do is to run the cargo build and cargo run commands in a terminal, including the integrated terminal. OK, seems lame, but yes it works.

It also says that you can install a debugger for runtime debugging called LLDB which is a good, old-fashioned binary debugger. So let's install that. We then need to enable the option "Debug: Allow breakpoints everywhere". OK, done. And add a breakpoint. Yeah, makes sense. And then use the Debug command. Now when I do this, one of the options is LLDB, which, since I've just installed it, makes a lot of sense to choose. This then complains that there isn't a target to run, but then offers to create one from my Cargo.toml file. Sounds good. And then everything works just the way I'd expect it to. C-F5 works too, and doesn't obviously put out any of the chatter about compiling and running. Maybe that's just gone in another terminal window.

And just to be absolutely sure I've understood what's happening, I'll make a change to the output and check that it comes out as expected when I run it again.

Hello there, world!

Most excellent.

Cross compiling

Now, while it may seem I am just playing with Rust for the sake of it, there is a bigger picture here (to be revealed in a later post), but I want to be able to compile on my Linux box and run on a Raspberry Pi with an ARM processor. So I need to be able to cross-compile for ARM and then check if that works. I don't think that's covered in the book, so we need a different resource.

First off, we apparently need to install a cross-compiling version of gcc. I think this is the one I want, and can be installed from the debian repository:

$ sudo apt install gcc-arm-linux-gnueabihf

Next up, we want to install what is called a "target" in Rust-speak, that is an environment which we can compile for from our current environment. The full command for this appears to be:

$ rustup target add armv7-unknown-linux-gnueabihf
info: downloading component 'rust-std' for 'armv7-unknown-linux-gnueabihf'
info: installing component 'rust-std' for 'armv7-unknown-linux-gnueabihf'
 23.8 MiB /  23.8 MiB (100 %)  13.1 MiB/s in  1s ETA:  0s

And, lo and behold, we have a target environment in place. So can we now compile "hello, world" for this target, install it and run it successfully? Yes, I doubt it, too, but let's give it a try.

We need to add a --target option to the cargo build command to tell it to use the appropriate libraries and tools for this target environment; furthermore, we need to use the cross-compiled linker we just installed when building for this target environment. So, first we create a directory .cargo for our project, and add a file config with the following contents:

[target.armv7-unknown-linux-gnueabihf]
linker = "arm-linux-gnueabihf-gcc"

The first line here says "use these options when you are compiling for the target armv7-unknown-linux-gnueabihf". The second line specifies a specific linker (the ARM one) that we should use for this job. Now we can run cargo from the command line:

$ cargo build --release --target=armv7-unknown-linux-gnueabihf
   Compiling hellorust v0.1.0 (/home/gareth/Projects/hellorust)
    Finished release [optimized] target(s) in 0.21s

And we have a binary file generated in an appropriate subdirectory of our project directory:

$ file target/armv7-unknown-linux-gnueabihf/release/hello_rust
target/armv7-unknown-linux-gnueabihf/release/hellorust: ELF 32-bit LSB pie executable, ARM, EABI5 version 1 (SYSV), dynamically linked, interpreter /lib/ld-linux-armhf.so.3, BuildID[sha1]=0a43f1c8602c9423d269bee77f131676dce1236b, for GNU/Linux 3.2.0, with debuginfo, not stripped

Personally, I'm a little surprised to see that a "release" build ends up with debug_info and not being stripped, but maybe I'm just not really understanding what "release" builds are in this context, or maybe that is something I can configure.

So, now I can copy that across to my Raspberry Pi and everything will just work:

$ scp target/armv7-unknown-linux-gnueabihf/release/hellorust pi@testpi:hellorust
hello_rust                                                                                                     100% 4278KB   6.5MB/s   00:00    

And then on the Pi:

$ ./hello_rust 
-bash: ./hello_rust: cannot execute: required file not found

That would be a no, then. I'm not quite sure why. The file is definitely there. Is it some other file it's not able to pull in? Let's use strace to find out:

$ strace ./hello_rust 
execve("./hello_rust", ["./hello_rust"], 0x7fd7eae660 / 22 vars /) = -1 ENOENT (No such file or directory)
strace: exec: No such file or directory
+++ exited with 1 +++

Uh, well, whatever is going wrong is going wrong down in the kernel where we can't see it. Let's see if file has any insights to offer:

$ file hello_rust 
hello_rust: ELF 32-bit LSB pie executable, ARM, EABI5 version 1 (SYSV), dynamically linked, interpreter /lib/ld-linux-armhf.so.3, BuildID[sha1]=0a43f1c8602c9423d269bee77f131676dce1236b, for GNU/Linux 3.2.0, with debug_info, not stripped

OK, well, that says "32-bit" and I think I'm running a 64-bit OS:

$ uname -a
Linux testpi-61 6.1.0-rpi4-rpi-v8 #1 SMP PREEMPT Debian 1:6.1.54-1+rpt2 (2023-10-05) aarch64 GNU/Linux

I certainly want to be running 64-bit (who wants to develop with old stuff?) but just to be sure there's nothing weird going on let's just check, say, cat:

$ file /bin/cat
/bin/cat: ELF 64-bit LSB pie executable, ARM aarch64, version 1 (SYSV), dynamically linked, interpreter /lib/ld-linux-aarch64.so.1, BuildID[sha1]=67c0f2beecec29f5643100ff22b6eef7af5c1ad1, for GNU/Linux 3.7.0, stripped

So, that's 64 bit, and aarch64 with a different linker and for a different Linux (3.7.0). In short, it's a different target. So, basically, I've followed some out of date instructions, but it's reasonable to assume that they were along the right lines, so let's go and find a different target and possibly a different set of development tools and wire everything up slightly differently.

Looking at the official list of Rust targets it would seem that what we are most likely to want is aarch64-unknown-linux-gnu, so let's try that:

$ rustup target add aarch64-unknown-linux-gnu    
info: downloading component 'rust-std' for 'aarch64-unknown-linux-gnu'
info: installing component 'rust-std' for 'aarch64-unknown-linux-gnu'
 29.9 MiB /  29.9 MiB (100 %)  12.5 MiB/s in  2s ETA:  0s
$ apt install gcc-aarch64-linux-gnu      

And likewise update our .cargo/config file to specify the linker for this target:

[target.aarch64-unknown-linux-gnu]
linker = "aarch64-linux-gnu-gcc"

Now we can build and copy it again, being sure to update all our references to the target:

$ cargo build --release --target=aarch64-unknown-linux-gnu
   Compiling hellorust v0.1.0 (/home/gareth/Projects/hellorust)
    Finished release [optimized] target(s) in 0.17s
$ scp target/aarch64-unknown-linux-gnu/release/hellorust pi@testpi:hellorust
hello_rust                                                                                                     100% 4751KB   5.5MB/s   00:00    

And then on the Pi we can run it to our heart's content:

$ ./hello_rust 
Hello there, world!

Wow.

(Editor's note: this was, in fact, a lot more of a struggle than it looked, because apart from everything else, I was using a Pi that I hadn't updated in a couple of years. During my attempts to bring it up to date, it died horribly and I had to reinstall from scratch. A whole Sunday afternoon disappeared while I was doing this. Compared to that, the Rust portion was relatively trivial, even though I couldn't find a definitive reference of which targets and linkers I should use for the exact combination of hardware and software I was using. If you are using a Pi 3B+ and the "latest" version of RaspberryPiOS (64-bit), you now do!).

This code is checked in and tagged HELLO_RUST.

Polishing things off (for now)

In order to finish up this project, at least for a first phase, which is all this is, we need to tidy up the UI. This consists of two things: first of all, adding in some CSS; secondly to add actions on the tab buttons so that clicking on the tab labels will cause the associated tab to be shown; and thirdly to clean up the error handling so that the error tab only appears (and is automatically selected) when there are errors.

It turns out that in order to do all of this, we need to restructure the HTML somewhat and break apart the tab titles and the tab bodies. This adds more complexity all over the place, but none of it is really interesting. For those scoring at home, it is this change that the ensureTabs method depends on.

In fact, none of this work is interesting, so feel free to dig in if you want to, it's really just essential to making it look acceptable.

Future Work

What isn't in the future? This really is just a question of scratching the surface of what can be done. To progress, this tool really needs to be used in anger, with the intent of drawing diagrams that mean something. Earlier in this blog, I have drawn some diagrams by hand, but I'm not going to draw those again just to test this tool out. But next time this blog calls for diagrams, you can be sure I'm going to dig this tool out. It will also be interesting to see how I go about incorporating such a diagram into the blog (I could experiment with that here using the samples, but I'm not going to).

Among other things that still need to be done:

• No complex connectors have yet been addressed, and these obviously come up all the time in real diagrams.
• In spite of the claims I may have implied for my algorithm, I think there are quite a few cases where it will be necessary to move nodes after they have been placed.
• So far we only have "nodes" and "edges". I would like to have a much richer semantic description of the diagrams I want to draw, but I'm not really sure what that would look like until I try it (but would have a domain-specific vocabulary of things like "server", "queue", "notification", "processing", "store" for a cloud-based software system). In addition to improving the clarity of the diagram description, I would expect this to provide information to the layout algorithm.
• I definitely want to be able to handle very large diagrams - let's say 200 nodes - and be able to expand and compress them by having the tool offer an "overview" or "schematic" of a whole system with just (say) five nodes, each of which can be expanded to a subsystem of more nodes. Obviously, this would be hierarchical. The most important point would be that the actual truth of all the diagrams is only presented once and the other diagrams are just defined in terms of what is included or left out.
• It seems to me that in certain cases, there needs to be the ability for humans to "override" the layout decisions, for example to indicate that certain nodes should be aligned horizontally or vertically, or that a node should be deflected slightly from its normal place, or that two nodes should have more space between them. On the other hand, I consider all such things "hacks" and wonder what semantic information is missing from the diagram that they are necessary.
• There should be a mechanism for adding comments to diagrams so that users can collaborate on a diagram, and probably connections to sharing tools such as github and Google Docs.

Interested? Get in touch and let's see what we can do.

Rendering the Diagram

Now we've laid out the diagram, we can move on to the final step of drawing, or rendering it. This is mainly dull and technical, relating to getting what we have in mind onto the canvas. Inasmuch as there is anything interesting to the task, it is figuring out how much space to leave in the gaps between the shapes, and how to label both shapes and connectors so that nothing overlaps. And while that may not be boring, it is tricky.

In order to try and break up some of the complexity, I have added another layer into this, which abstracts away the canvas. This also has the benefit of making the render algorithm testable. The abstraction layer, of course, can only be tested using complex image-comparison tools.

Creating the Diagram Tabs

Anyway, first off, we need to dispose of something that's been hanging over us for a while, to wit, finding the tab and the canvas to draw into. As I said before, I want to make this as stable as possible, so we want each tab to be named according to the first node laid out in the diagram (at least until we have some better way of naming things), and then to have the diagrams remain in the same sequence based on this.

Then, as we render, we reuse the tabs and canvas objects that already existed, and delete or add any to reflect bigger changes in the overall portfolio of diagrams.

  ensureTabs(tabrow, tabdisplay) {
    this.tabs = {};
    var titles = tabrow.querySelectorAll(".diagram-tab");
    var bodies = tabdisplay.querySelectorAll(".diagram-tab");
    var toRemove = [];
    for (var i=0;i<titles.length;i++) {
      toRemove[titles[i].dataset["diagramFor"]] = { title: titles[i], body: bodies[i] };
    }
    for (var i=0;i<this.diagrams.length;i++) {
      var d = this.diagrams[i];
      var t = findTabFor(titles, d.named);
      var b = findTabFor(bodies, d.named);
      if (!t) {
        t = addDiagramTab(tabrow, tabdisplay, d.named);
      } else {
        delete toRemove[d.named];
        t = { title: t, diagram: b };
      }
      this.tabs[d.named] = t;
    }
    var keys = Object.keys(toRemove);
    for (var i=0;i<keys.length;i++) {
      tabrow.removeChild(toRemove[keys[i]]);
    }
  }

(For complicated reasons, this code does not quite align with its history, and only works with the code that comes from polishing the UI which follows).

The function to add a new diagram tab looks like this:

function addDiagramTab(titles, display, name) {
  var t = document.createElement("div");
  t.className = "diagram-tab tab-title";
  t.dataset["diagramFor"] = name;
  t.appendChild(document.createTextNode(name));
  titles.appendChild(t);
  clickFor(ev => selectDiagramTab(name)) (t);

  var d = document.createElement("div");
  d.className = "diagram-tab tab-body";
  d.dataset["diagramFor"] = name;
  var cd = document.createElement("div");
  var c = document.createElement("canvas");
  c.className="diagram";
  c.setAttribute("width", "1200");
  c.setAttribute("height", "800");
  cd.appendChild(c);
  d.appendChild(cd);
  display.appendChild(d);

  return { title: t, diagram: d };
 }

export default Portfolio;

Rendering the Diagram

Then we can come back and implement the render code. The first step is to implement the Render interface, and collect all the information from Layout about the shapes and connectors. As we do this, we collect metadata about the rows and columns which are implied in the layout.

  shape(x, y, s) {
    if (x >= this.maxx) this.maxx = x+1;
    if (y >= this.maxy) this.maxy = y+1;

    if (!this.rows[y]) {
      this.rows[y] = new RowInfo();
    }
    if (!this.columns[x]) {
      this.columns[x] = new ColumnInfo();
    }
    this.rows[y].include(s);
    this.columns[x].include(s);

    this.shapes.push({ x: x, y: y, s: s });
  }

Ultimately, the connector method needs to do similar analysis, figuring out how wide individual canals will need to be, and thus the spacing between the grid. But we haven't got that far yet, so it's just a question of recording the fact that the connector needs to be drawn.

  connector(pts) {
    this.connectors.push(pts);
  }

When layout is complete, it calls the done method which figures out what the actual size of all the elements, including the overall diagram, will be and then draws all the shapes and connectors in the right places, using the canvas abstraction.

  done() {
    this.figureGrid();

    // draw all the shapes
    for (var i=0;i<this.shapes.length;i++) {
      var si = this.shapes[i];
      this.drawShape(si.x, si.y, si.s);
    }

    // draw the connectors
    for (var i=0;i<this.connectors.length;i++) {
      var pts = this.connectors[i];
      this.drawConnector(pts);
    }
  }

  figureGrid() {
    // based on the rows and columns, we can figure out what the grid should be
    // because it's a grid, which just need two sets of values, one that maps x units to x locations and one for y
    var xpos = minCanal; // the left margin
    for (var i=0;i<this.maxx;i++) {
      if (!this.columns[i]) continue; // this should not be possible, but safety first ...
      var c = this.columns[i];
      c.from = xpos;
      xpos += c.maxwidth;
      c.to = xpos;
      c.channels = [];
      xpos += c.right;
    }
    this.totalWidth = xpos;

    var ypos = minCanal; // the top margin
    for (var i=0;i<this.maxy;i++) {
      if (!this.rows[i]) continue; // this should not be possible, but safety first ...
      var c = this.rows[i];
      c.from = ypos;
      ypos += c.maxheight;
      c.to = ypos;
      c.channels = [];
      ypos += c.below;
    }
    this.totalHeight = ypos;
  }

Laying out the diagram

Now we know we have a diagram (possibly a set of diagrams, but we will deal with them one at a time) which has a set of fully connected nodes and we want to lay it out on a two-dimensional grid.

As I said before, I am no expert on graph theory or layout, so I'm not going to do anything complicated. I am going to lay out the nodes on a rectangular grid with "standard" coordinates starting at 0 and going right and down. It will be the job of the rendering engine to make that look nice by adapting those coordinates to something in real space.

The abstract model will have "shapes" and "connectors". A shape is simply at a point in this 2D space, and connectors run between them in the "gaps". This is slightly more difficult to describe, but I view the space between the shapes as being like rivers or canals, and in that there are "channels". The rule is that any given channel (that is, a specific segment of a specific vertical or horizontal line between the shapes) may only have one connector line running down it. They may, however, cross an arbitrary number of times. A connector will always join at least two shapes (or quite possibly more); each limb will ultimately reach a shape; in between it will always run down channels between the shapes, never crossing a shape; the various limbs of a connector connecting more than 2 shapes must be connected in some way at some point so that they can be seen not to be crossing.

My approach for trying to get the graph as "tight" as possible (that is, as many shapes close to their friends as possible, thus reducing the length of the connectors) is to place first the shape with the most number of connectors to it, then to try and place all the shapes connected to it (again, going from the most connections to the least), and then (recursively) working our way down the list. This may or may not work out well. It may also present additional challenges as and when we introduce constraints (such as a desire to have certain shapes all be on the same row).

Before we get started, I should (perhaps) clarify that I did not write this in the order in which I presented it, but did some layout and some rendering and slowly worked my way to this algorithm. Also, I worked up to it using unit tests for some simple cases and, if and when I come back to add more complex cases, the algorithm will change again.

Layout is kicked off from inside the Diagram, but it basically just delegates to the LayoutAlgorithm to first lay the diagram out and then to render it. Obviously to do that, it passes in the knowledge it has collected about the diagram.

  layout(render) {
    var alg = new LayoutAlgorithm(this.errors, this.nodes, this.nodeNames, this.edges);
    alg.layout();
    alg.render(render);
  }

The layout algorithm comes in two parts: we first place the nodes on a hypothetical grid, and then we connect them with the edges.

  layout() {
    // handle the empty diagram
    if (this.nodes.length == 0) return;

    this.placeNodes();
    this.connectNodes();
  }

Placing the nodes is, of course, where all the meaty stuff happens. We want to lay the nodes out in such a way that nodes which are connected are close together and then connecting them via the edges should be relatively easy. We need to place the nodes one at a time; the first node is chosen to be the one with the most connections; after that, we can choose any node which is connected to a node already in the diagram. In practice, we try to choose the one with the most connections to nodes already in the diagram.

To make this code simpler, we delegate the process of tracking which nodes are eligible for selection (and the appropriate order) to a class called PushFrontier (so named because it is continually pushing forward the frontier of the graph which has been chosen) and the process of placing the nodes to a class called Placement.

With these in place, the function to place the nodes is not too awful:

  placeNodes() {
    // The frontier model is designed to provide us with the nodes in a "most connected" order
    var frontier = new PushFrontier(this.nodes, this.edges);

    // First place the most connected node
    var name = frontier.first();
    this.placement.place(0, 0, this.nameMap[name]);

    // Now, iteratively consider all the remaining nodes
    // Each node we receive will be connected to one or more (preferably more) nodes already in the diagram
    while (frontier.push(name)) {
      name = frontier.next();

      // try and figure out where it's near ...
      var avgpos = this.findNear(frontier, name);

      // noew place it somewhere near there that isn't occupied
      this.placement.place(avgpos.x, avgpos.y, this.nameMap[name]);
    }
  }

Selecting the next node

The PushFrontier code works by first analyzing all the nodes and edges to build an inverted table of all the nodes with their connections. It then sorts these to find the nodes with the greatest number of connections and then identifies the list of connection arities. It turns out that this is a very good fit for a radix sort.

class PushFrontier {
  constructor(nodes, edges) {
    this.conns = this.groupByConnections(nodes, edges);
    this.sorted = this.sortConnections(this.conns);
    this.radices = this.gatherRadices(this.sorted);
    this.done = [];
    this.frontier = [];
  }

The code to choose the first node simply looks for the first node in the list of nodes with the highest radix.

  first() {
    var r = this.radices[0];
    var node = this.sorted[r][0];
    return node;
  }

Once the node has been added to the graph, the push method is called, which adds it to the list of nodes that have been used (both so that it will not be returned again, and so that we can see which nodes are already in the graph). It then looks at all the nodes which are connected to this node (and which have not already been placed) and adds those to the expanding frontier.

  push(node) {
    this.done.push(node);
    var add = this.conns[node];
    for (var i=0;i<add.length;i++) {
      if (!this.done.includes(add[i]))
      this.frontier.push(add[i]);
    }
    return this.frontier.length > 0;
  }

And finally, when we are asked to provide the next node, we scan through the list of frontier nodes (all of which have the property that they have not yet been placed, but are connected to a node which has been placed) and choose the one which:

• has the most connections to a node in the graph; or, failing that
• is tied for the most connections in the graph and, among those, has the most total connections; or, failing that
• is tied for the most number of connections, and has the alphabetically first name.

  next() {
    var mostInGraph = -1;
    var mostTotal = -1;
    var ret = null;
    var pos = -1;
    for (var i=0;i<this.frontier.length;i++) {
      var node = this.frontier[i];
      var total = this.conns[node].length;
      var inGraph = this.chooseDone(this.conns[node]);
      var chooseMe = false;
      if (inGraph > mostInGraph) { // it is connected to the most already in the graph
        chooseMe = true;
      } else if (inGraph == mostInGraph && total > mostTotal) { // it is connected to the most other total nodes
        chooseMe = true;
      } else if (inGraph == mostInGraph && total == mostTotal && node < ret) { // it is at least as good and has an earlier name
        chooseMe = true;
      }
      if (chooseMe) {
        mostInGraph = inGraph;
        mostTotal = total;
        ret = node;
        pos = i;
      }
    }
    this.frontier.splice(pos, 1);
    return ret;
  }

Placing the Nodes on a Grid

The other half of the task is to figure out where to put each node once we have identified it as the next node to be placed on the grid. For the first node, this is easy: we just say we want to place it at (0,0) and we're done. For all subsequent nodes, what we really want to do is to place them at the average position of all the nodes they are connected to.

  // Look at all the nodes connected to this one which have already been placed and figure out their average position
  // We want to be somewhere near there
  findNear(frontier, name) {
    var sx = 0, sy = 0, cnt = 0;
    var conns = frontier.connectedTo(name);
    for (var i=0;i<conns.length;i++) {
      var c = conns[i];
      var pl = this.placement.isPlaced(c);
      if (pl) {
        sx += pl.x;
        sy += pl.y;
        cnt++;
      }
    }
    return { x: sx/cnt, y: sy/cnt };
  }

Of course, there is a significant probability that that space is already taken, and we need to put it somewhere else "near" there. The Placement class is responsible for handling that. For the cases I have added tests for so far, this code is adequate, but clearly there will be the need to do more later.

  // find a slot for the node to go in, ideally the one it asked for
  findSlot(x, y) {
    // rounding is good from the perspective of trying something, but we possibly should try "all 4" (if not an integer) before trying neighbouring squares.
    x = Math.round(x);
    y = Math.round(y);

    // if that slot is free, go for it!
    if (!this.haveNodeAt(x, y)) return { x, y };

    // first try the four cardinal points
    if (!this.haveNodeAt(x+1, y)) return { x: x+1, y: y };
    if (!this.haveNodeAt(x, y+1)) return { x: x, y: y+1 };
    if (!this.haveNodeAt(x-1, y)) return { x: x-1, y: y };
    if (!this.haveNodeAt(x, y-1)) return { x: x, y: y-1 };

    this.errors.raise("can't handle this case in layout");
  }

Connecting Nodes

Once we have placed all the nodes, we need to go back and look at all the edges and figure out how to connect them. My thought for a connector is that it is a series of line segments which are joined together in such a way as to make a continuous line between two nodes. In order to trace such a path, it must have a series of points, all of which are relative to the grid. The ultimate idea (not yet in code) is that between the main grid nodes are a set of "canals" divided into "channels" through which the edges can flow. This means that there are two distinct types of points: those where the point is attached to a side of a node; and those where the point is in a canal. For now, we only have the points connected to the side of a node (called a ShapeEdge). This point is identified by the (x,y) grid position of the node, which side of the node it is attached to, and which "channel" it is going to use (here, the same idea of a channel is to be able to distinguish between two different edges both coming into the same side of a node).

For now, I have only written the code to handle connections between two nodes which are on the same horizontal or vertical line (the only cases I have considered as yet). In this case, the connector has exactly two points, each of which is a ShapeEdge. I have also not handled the case with multiple connectors from the same side of the same node.

  connectNodes() {
    for (var i=0;i<this.edges.length;i++) {
      var e = this.edges[i];
      if (e.ends.length != 2) {
        this.errors.raise("cannot handle this case yet");
        continue;
      }
      var f = e.ends[0];
      var t = e.ends[1];
      var fn = this.placement.isPlaced(f.name);
      var tn = this.placement.isPlaced(t.name);
      // This is nothing like sophisticated enough for 90% of cases. But it passes all current unit tests
      this.placement.connect([ new ShapeEdge(fn.x, fn.y, tn.x-fn.x, tn.y - fn.y, 0), new ShapeEdge(tn.x, tn.y, fn.x - tn.x, fn.y - tn.y, 0) ]);
    }
  }

Partitioning the Diagram

In some ideal world, the resultant diagram from parsing would be fully connected.

This isn't true for a number of reasons. The most obvious one is just user "error". As the user is entering information, they simply may not be aware of one or more connections, or unsure how to describe them. It is better to handle this case than to complain and force the user to take corrective action.

Another is that we want to explicitly support the idea of "modules" or "subsystems" which deliberately target a set of nodes.

And it seems to me that if you have two diagrams that aren't connected, then you should have two separate diagrams drawn, not put all the information onto one diagram.

So the next phase is to try and follow the edges between the nodes and partition the diagram into a number of smaller, independent diagrams. In the case of subsystems (which are not yet supported), the expectation would be to create a "duplicate" diagram where we copy across the requested nodes and edges, allowing a number of edges to be "dangling" with no nodes to attach them to.

(Note that dangling edges should not normally be allowed, but as yet we have not done any verification on our model: this also covers the fact that we shouldn't allow multiple nodes to have the same name.)

We are going to create a number (which may be 1) of diagrams based on the information in the original parsed diagram in the partitionInto method in DiagramModel. Each one will be given a name so that we can identify them, and this name will be the name of the (alphabetically) first node in the diagram. I am hoping this will be (relatively) tolerant to change when we go through the relayout-redraw cycle so that the visual display is relatively static.

The process by which we are going to do this is really very simple. We add a node to a diagram, keeping track of the nodes we've added as we go. We then find all the edges that connect to that node, and ask them for all the nodes they want to connect to. We then add all those nodes in turn, repeating the process until no more nodes turn up. We then move on to the next diagram, starting with the first unused node, until there are no more unused nodes. At that point, we are done.

  partitionInto(c) {
    // Collect together all the node names in order, and create a map back to the actual nodes
    var unseen = [];
    var map = {};
    for (var i=0;i<this.nodes.length;i++) {
      var n = this.nodes[i];
      unseen.push(n.name);
      map[n.name] = n;
    }

Parsing the Diagram Description

The core of what we are trying to do here is to describe a diagram (or set of diagrams) in a declarative, textual way. As much as possible, we want that description to be abstract and close to the semantics of what is going on. But there must obviously be some means by which that is mapped onto a diagram consisting of boxes and lines.

That being the case, I'm going to start from a very generic notion from graph theory that we have a graph consisting of nodes and edges. Each of these items may have metadata of various forms attached to them, which will inform how we lay them out and render them. Some of these may be semantic and need further interpretation; others may be more direct.

It would be great if the layout were fully automatic and exactly right every time; however, such an algorithm has not yet been invented, so there are going to have to be commands in the description which enable us to describe the manner in which nodes and edges should be connected.

And this is the right point to add the disclaimer that I am not any kind of expert in the fields of graph theory or layout, and that I'm going to come up with a layout algorithm that sort of works. I'll be happy to work with anybody who can do better - I'm just interested in a "tool" that can produce decent-ish pictures from a completely textual description.

The description language

The basis of the description language is a set of lines with nesting. Each "top level" line either introduces a new node or a new edge; adds metadata to an existing node or edge; or adds a constraint between multiple existing items. Because the language is declarative, the order of the declarations is irrelevant. If needed, additional information is included in nested lines.

Let's start with a very simple example:

node producer
    label "Producer"
node consumer
    label "Consumer"
edge
    from producer
    to consumer
        cap arrow

So this introduces two nodes, a "producer" and a "consumer" (and gives them labels) and then defines an arrow leading from the producer to the consumer.

Analyzing the description

The way in which I'm approaching this problem is much the same as at the top level: I'm going to build a TDA pipeline in which the parser is mainly responsible for breaking the input up into lines, and then calling a tokenizer on each of them, and having that pass any "interesting" (non-blank, non-comment) lines on to the next step.

import { tokenize } from "./tokenize.js";
import Blocker from "./blocker.js";

function parser(top, errors) {
  return function(text) {
    var lines = text.split(/\n/);
    var blocker = new Blocker(top);
    for (var i=0;i<lines.length;i++) {
      tokenize(lines[i], blocker, errors);
    }
  }
}

export default parser;

The next step is to try and "group" these by indentation level. Any lines with no indentation go directly to the "top level parser", which creates a model object (attaching it to the top level model) and returns a parser which will handle any nested items. Lines with greater indentation are assessed according to a "stack": it is passed to the deepest parser with an indentation strictly less than the current line.

The parser which is called is responsible for understanding the meaning of the tokenized line in its context and updating the model it possesses, and then returning a new parser which is capable of handling any nested content. If it does not wish to support nested content, returning null or undefined will cause the blocker to automatically raise an error.

class Blocker {
  constructor(top, errors) {
    this.top = top;
    this.errors = errors;
    this.stack = [];
  }

  line(tok) {
    var current = this.top; // the default

    // find which parser to use, closing and shifting others more deeply indented
    while (this.stack.length > 0) {
      var first = this.stack[0];
      if (tok.indent > first.indent) {
        current = first.handler;
        break;
      }
      if (first.handler && first.handler.complete) {
        first.handler.complete();
      }
      this.stack.shift();
    }

    // call the current parser
    if (!current) {
      // if there is no handler specified at this level, it's because no further nesting is allowed
      this.errors.raise("no content allowed here");
    } else {
      var nested = current.line(tok);
    
      // record this parser for everything under this nesting level
      this.stack.unshift({indent: tok.indent, handler: nested});
    }
  }

  complete() { // on end of input
    this.top.complete();
  }
}

While we have been doing this, we have quietly introduced modules into the code, and started writing simple tests of the tokenizer and blocker. We have also introduced some rudimentary error handling.

The Top Level Parser

We're now ready to try building a top level parser. Three lines of input should be presented to it: the two node lines and the edge line. It should be able to identify these, reject anything else, build a model entry for the item and add it to the model, and then return a parser to handle any configuration items that they may have (a NodeConfigurationParser and an EdgeConfigurationParser respectively). How hard can this be?

import NodeConfigParser from "./nodeconfig.js";
import EdgeConfigParser from "./edgeconfig.js";
import Node from "./model/node.js";
import Edge from "./model/edge.js";

class TopLevelParser {
  constructor(model, errors) {
    this.model = model;
    this.errors = errors;
  }

  line(l) {
    var cmd = l.tokens[0];
    switch (cmd) {
      case "node": {
        switch(l.tokens.length) {
          case 1: {
            this.errors.raise("node command requires a name");
            break;
          }
          case 2: {
            var node = new Node(l.tokens[1]);
            this.model.add(node);
            return new NodeConfigParser(node);
          }
          default: {
            this.errors.raise("node: too many arguments");
            break;
          }
        }
        break;
      }
      case "edge": {
        switch(l.tokens.length) {
          case 1: {
            var edge = new Edge();
            this.model.add(edge);
            return new EdgeConfigParser(edge);
          }
          default: {
            this.errors.raise("edge: not allowed arguments");
            break;
          }
        }
        break;
      }
      default: {
        this.errors.raise("no command: " + cmd);
      }
    }
  }
}

Each of the nested parsers go much the same way: the node parser supports the label property and the edge parser supports the from and to properties. The latter, in turn, allows further configuration using the EdgeEndParser. We now have the ability to parse the input script outlined above.

Handling Errors

I've quietly added some (primitive) error handling into the code above, but it still just prints on the console. This doesn't seem the best idea, so I'm going to add an error tab and put the errors in there. We still haven't implemented any CSS, so we don't have tabs as such, but the idea will be that normally this error tab will be hidden, but that when there are errors all the diagram tabs will be hidden, the error tab will be visible and selected.

This follows much the same pattern as the happy path in the code. We add a block in the tabs for the errors to appear:

          <div class="error-tab">
            <div class="tab-title">Errors</div>
            <div class="error-messages">
            </div>
          </div>

In the pipeline, we check if we have seen any errors. If so, we recover the error-tab and pass it to the show method on the ErrorReporter object, otherwise we continue with the normal flow, making sure to clear any previous errors.

function pipeline(ev) {
  var errors = new ErrorReporter();
  var model = new DiagramModel(errors);
  readText("text-input", parser(new TopLevelParser(model, errors), errors));
  if (errors.hasErrors()) {
    applyToDiv("error-messages", tab => errors.show(tab));
  } else {
    applyToDiv("error-messages", tab => tab.innerHTML = '');
    var portfolio = new Portfolio();
    model.partitionInto(portfolio);
    applyToDiv("tabs-row", ensureTabs(portfolio));
    portfolio.each((graph, tab) => graph.layout(d => d.drawInto(tab)));
  }
}

And here is the ErrorReporter class, now pulled out into its own file:

class ErrorReporter {
  constructor() {
    this.errors = [];
  }

  hasErrors() {
    return this.errors.length > 0;
  }

  raise(s) {
    console.log("error: " + s);
    this.errors.push(s);
  }

  show(elt) {
    elt.innerHTML = '';
    for (var i=0;i<this.errors.length;i++) {
      var msgdiv = document.createElement("div");
      msgdiv.className = "error-message";
      var msgtext = document.createTextNode(this.errors[i]);
      msgdiv.appendChild(msgtext);
      elt.appendChild(msgdiv);
    }
  }
}

export default ErrorReporter;

Drawing Diagrams

Way back in the day, I used to draw diagrams with a tool called pic. This only worked with troff. Then I used fig when I was working with latex. Since the early '90s, I've been forced into hideously painful WYSIWYG diagram editors (Powerpoint is only the worst example; Visio, Framemaker, Illustrator and the like are all painful).

I was reminiscing earlier this week with a colleague who has similar values and a need to produce documentation on a large system he is building. I discussed pic and fig and how much easier it was back in the day, although at the same time noted the many issues these tools had. And how I would pay good money for a tool that made it easy again.

After we'd finished talking, I realized how what I'd described matched exactly the sort of problem I like to tackle … and furthermore the sort of problem I like to tackle here. So here goes.

Because in the interim the world has gone Web, my default output is going to be for the Web, so I'm going to build everything in JavaScript. Because I want a lot of flexibility, I'm going to go straight for a Canvas model and draw everything by hand.

So, as always(?), I want to start by building something that approaches "the whole application" so that we can see the overall picture and then fill in the details as they emerge. In this case, before we start getting fancy, I basically want to have a div with a couple of tabs: one with a text area to enter the description, and one with a canvas to show the "final" diagram (we will return to the notion of how many diagrams, later). So this requires a simple HTML file and a bunch of stubbed JavaScript in main.js. For those playing at home, this is checked in with the tag DIAGRAM_TOOL_FIRST_STEP.

<html>
  <head>
    <title>Diagrammer</title>
    <script type="text/javascript" src="js/main.js"></script>
  </head>
  <body onload="initialize()">
    <div>
      <div class="toolbar">
        <button class="toolbar-update">Update</button>
      </div>
      <div class="tabbed-window">
        <div class="tabs-row">
          <div class="input-tab">
            <div class="tab-title">Input</div>
            <div>
              <textarea class="text-input"></textarea>
            </div>
          </div>
          <div class="output-tab">
            <div class="tab-title">Output</div>
            <div>
              <canvas class="diagram"></canvas>
            </div>
          </div>
        </div>
      </div>
    </div>
  </body>
</html>

function initialize() {
  var updateButton = document.getElementsByClassName("toolbar-update")[0];
  updateButton.addEventListener("click", pipeline);
}

function pipeline(ev) {
  var model = new DiagramModel();
  readText("text-input", parser(model));
  var portfolio = new Portfolio();
  model.partitionInto(portfolio);
  tabModel("tabs-row", ensureTabs(portfolio));
  portfolio.each((graph, tab) => graph.layout(d => d.drawInto(tab)));
}

// TODO: everything below here needs to broken out into modules

// jstda.js
function readText(label, processor) {
  var input = document.getElementsByClassName(label)[0];
  processor(input.value);
}

function tabModel(label, processor) {
  var tabrow = document.getElementsByClassName(label)[0];
  processor(tabrow);
}

function ensureTabs(portfolio) {
  return function(tabrow) {
    portfolio.ensureTabs(tabrow);
  }
}

// parser.js
function parser() {
  return function(text) {
    console.log(text);
  }
}

// model.js
class DiagramModel {
  partitionInto(c) {
    console.log("partition model into", c);
  }
}

// portfolio.js
class Portfolio {
  ensureTabs(tabrow) {
    console.log("need to ensure tabs");
  }

  each(f) {
    console.log("iterate over graphs and provide tabs");
  }
}

As always, the output from that is unpleasant on the eye and really needs some CSS to make it palatable. I'll come back to that, but for now, let's consider what that pipeline means.

First off, as regular readers know, I'm a TDA (tell-don't-ask) enthusiast. Mainly this stems from doing TDD with complex systems in Java; the mock support is not as good in JavaScript, but my brain remains wired up the same way - if it can't be functional, let it be TDA. And you never know, I may get around to actually writing some tests this time!

Consequently, everything is coupled up in pipeline and that's the only function I'm going to talk about. Almost everything else is plumbing that is just there so that the pipeline doesn't throw any errors.

There are four "phases" to the pipeline:

• We convert the input text into a model of the graph in memory;
• We split the graph into connected chunks (if the graph is completely connected, there will only be one such chunk) and build a Diagram for each chunk which are collected in a Portfolio;
• We make sure that there is a tab and a canvas for each Diagram;
• We go through each Diagram in the portfolio, first laying it out and then rendering it into the canvas.

What could be simpler?