Computing a Layout

A layout says where each box goes. Ours is simple and predictable: the nodes that nothing calls go in the top row, the nodes they call in the next row, and so on. Each row is centred, and the nodes of a row keep the order of the description. Graphviz and its friends do much more (they move nodes to avoid crossings and route lines around boxes), but this one fits on a page, and it is enough for the diagrams of this book.

The functions of this section live in the library module draw.xqm, namespace urn:example:draw. We'll read it a part at a time and run each part as we go; Writing SVG with XQuery shows the module as a whole.

Ranks

The rank of a node is its row: how many edges away it is from the top. The top row starts with the nodes without incoming edges, here the two SDKs. XPath finds them, and the nodes one edge further from the flags module:

$ sxml xpath --context-item=diagram.xml '//node[not(@id = //edge/@to)]/@id/string()'
"browser"
"node"
$ sxml xpath --context-item=diagram.xml '//edge[@from = "flags"]/@to/string()'
"registry"
"cache"

Doing that step again and again until no new node turns up is a breadth-first search. The ranks found so far are a map from node id to rank, and each step adds the nodes one edge away from the last rank, leaving out the ones that already have a rank. map:build makes the first map from a sequence of keys and a function that gives each key's value; fn { 0 } is a function that ignores its argument:

$ sxml xpath --context-item=diagram.xml 'map:build(("browser", "node"), value := fn { 0 })'
{"browser":0,"node":0}

Here is the search as two functions of draw.xqm:

(:~ The ids of the nodes one edge away from the last rank found. :)
declare %private function draw:next(
  $diagram as element(diagram),
  $ranks as map(xs:string, xs:integer)
) as xs:string* {
  let $last := max(map:items($ranks))
  let $frontier := map:keys($ranks)[$ranks(.) = $last]
  return distinct-values($diagram/edge[@from = $frontier]/@to)
    [not(map:contains($ranks, .))]
};

(:~ The rank of every node: a map from node id to row number. :)
declare function draw:ranks($diagram as element(diagram)) as map(xs:string, xs:integer) {
  let $targets := $diagram/edge/@to
  let $starts := ($diagram/node[1], $diagram/node[not(@id = $targets)])/@id
  let $reached := while-do(
    map:build($starts, string#1, fn { 0 }),
    fn($ranks) { exists(draw:next($diagram, $ranks)) },
    fn($ranks) {
      let $rank := max(map:items($ranks)) + 1
      return map:merge(($ranks, map:build(draw:next($diagram, $ranks), value := fn { $rank })))
    }
  )
  let $rest := $diagram/node/@id[not(map:contains($reached, .))]
  return map:merge(($reached, map:build($rest, string#1, fn { max(map:items($reached)) + 1 })))
};

draw:next finds the frontier (the nodes of the last rank) and the nodes their edges lead to. while-do holds the state of the loop, the map, and calls its third argument as long as its second one says there is more to do. Because a node gets a rank only once, the search ends even when the edges go round in a circle.

Two details make it work on any graph. The first node of the description always starts too, so a diagram in which every node has an incoming edge (a state machine, say) still has a top row; and nodes the search never reaches go into one last row, so no node is lost. In a module, draw: is the module's prefix, and %private keeps draw:next out of the module's interface.

Let's run it. An import module declaration in the query names the module's namespace and file, and --method=adaptive shows the map:

$ sxml xquery --method=adaptive --context-item=diagram.xml --expression='import module namespace draw = "urn:example:draw" at "draw.xqm"; draw:ranks(/diagram)'
{"browser":0,"node":0,"api":1,"flags":2,"registry":3,"cache":3,"postgresql":4,"redis":4}

A diagram with cycles works the same way. states.xml has four states of a feature flag; every state has an incoming edge except archived:

states.xml:

<?xml version="1.0" encoding="UTF-8"?>
<!-- Three states of a feature flag and a fourth that nothing leads to.
     Every state has an incoming edge except archived. -->
<diagram title="Flag states">
  <node id="stable" label="stable"/>
  <node id="checking" label="checking"/>
  <node id="rolling-out" label="rolling-out"/>
  <node id="archived" label="archived"/>
  <edge from="stable" to="checking" label="rollout.request"/>
  <edge from="checking" to="rolling-out" label="check.passed"/>
  <edge from="checking" to="stable" label="check.failed"/>
  <edge from="rolling-out" to="stable" label="step.done"/>
  <edge from="archived" to="stable" label="kill.request"/>
</diagram>

$ sxml xquery --method=adaptive --context-item=states.xml --expression='import module namespace draw = "urn:example:draw" at "draw.xqm"; draw:ranks(/diagram)'
{"stable":0,"archived":0,"checking":1,"rolling-out":2}

stable is first, so it starts the search; archived has no incoming edge, so it starts too. The edges back to stable change nothing, because it already has a rank. And here are two nodes that only point at each other, behind a first node that leads nowhere: they go into the last row.

$ sxml xquery --method=adaptive --expression='import module namespace draw = "urn:example:draw" at "draw.xqm"; draw:ranks(<diagram><node id="a"/><node id="b"/><node id="c"/><edge from="b" to="c"/><edge from="c" to="b"/></diagram>)'
{"a":0,"b":1,"c":1}

The same search as a fold

while-do stops when the frontier leads nowhere new. The search can also be written as a fixed number of passes: a graph of n nodes has no rank above n − 1, so n passes of fold-left are always enough, and pass number p ranks the nodes one edge away from rank p − 1:

ranks-fold.xq:

xquery version "4.0";
(: The ranks of diagram.xml (the context item) with a fold: one pass per
   node, each pass ranking the nodes one edge away from the last rank. :)
let $diagram := /diagram
let $starts := ($diagram/node[1], $diagram/node[not(@id = $diagram/edge/@to)])/@id
return fold-left(
  1 to count($diagram/node),
  map:build($starts, string#1, fn { 0 }),
  fn($ranks, $pass) {
    let $frontier := map:keys($ranks)[$ranks(.) = $pass - 1]
    let $next := distinct-values($diagram/edge[@from = $frontier]/@to)
      [not(map:contains($ranks, .))]
    return map:merge(($ranks, map:build($next, value := fn { $pass })))
  }
)

$ sxml xquery --method=adaptive --context-item=diagram.xml ranks-fold.xq
{"browser":0,"node":0,"api":1,"flags":2,"registry":3,"cache":3,"postgresql":4,"redis":4}
$ sxml xquery --method=adaptive --context-item=states.xml ranks-fold.xq
{"stable":0,"archived":0,"checking":1,"rolling-out":2}

The results are the same. The fold says plainly that it ends, and it does its last passes for nothing; while-do stops as soon as it can. The distinct-values matters in both: map:build keeps every value given for a key, so a node that two frontier nodes lead to would get its rank twice:

$ sxml xpath 'map:build(("a", "b", "a"), value := fn { 0 })'
{"a":(0,0),"b":0}

Rows

With the ranks known, the rows are a grouping: the nodes grouped by their rank, in the order of the ranks. Each group becomes an array of ids, so that the rows stay apart (a sequence of sequences would flatten into one sequence):

rows.xq:

xquery version "4.0";
(: The rows of diagram.xml (the context item): one array of node ids per rank. :)
import module namespace draw = "urn:example:draw" at "draw.xqm";

let $ranks := draw:ranks(/diagram)
for $node in /diagram/node
group by $rank := $ranks($node/@id)
order by $rank
return array { $node/@id/string() }

$ sxml xquery --method=adaptive --context-item=diagram.xml rows.xq
["browser","node"]
["api"]
["flags"]
["registry","cache"]
["postgresql","redis"]
$ sxml xquery --method=adaptive --context-item=states.xml rows.xq
["stable","archived"]
["checking"]
["rolling-out"]

group by keeps the nodes of each group in their order in the description, so registry comes before cache.

Places as records

Each box needs a place: the x and y of its top left corner. A map with two entries holds that well, and a record type says which entries it has and what they hold. declare record names the type and also declares a function of the same name that makes one. The module starts with the sizes of the drawing and two records:

(: The sizes of the drawing, in SVG user units. :)
declare variable $draw:box-width := 140;
declare variable $draw:box-height := 40;
declare variable $draw:gap-across := 40;
declare variable $draw:gap-down := 60;
declare variable $draw:padding := 20;

(: The top left corner of a node's box. :)
declare record draw:place(x as xs:integer, y as xs:integer);

(: A computed layout: the size of the drawing and a place per node id. :)
declare record draw:layout(
  width as xs:integer,
  height as xs:integer,
  places as map(xs:string, draw:place)
);

A record is a map, so ?x reads an entry. The type checks what goes in:

$ sxml xquery --method=adaptive --expression='import module namespace draw = "urn:example:draw" at "draw.xqm"; draw:place(110, 20), draw:place(110, 20)?x'
{"x":110,"y":20}
110
$ sxml xquery --method=adaptive --expression='import module namespace draw = "urn:example:draw" at "draw.xqm"; draw:place(1.5, 20)'
expression:1:66: err:XPTY0004: The value does not match the required type (XPath 4.0, section 3.4, coercion rules)

draw:layout uses a record type for its result too, with a typed map inside: map(xs:string, draw:place) is a map from strings to places.

The widest row, and centring

A row of n boxes is n × 140 wide plus n − 1 gaps of 40. The drawing is as wide as its widest row plus the padding on both sides, and each row starts half of its free space in from the left. The width of a row is a small function, kept in a variable so that it can be used twice:

$ sxml xpath 'let $row-width := fn($row as array(*)) { array:size($row) * 140 + (array:size($row) - 1) * 40 } return (["api"], ["registry", "cache"]) ! $row-width(.)'
140
320

For the Vane diagram the widest rows have two boxes, 320, so the drawing is 360 wide. The row of one box starts at (360 − 140) / 2 = 110, and the row of two at (360 − 320) / 2 = 20. Rows are 40 high with 60 between them, so row r (counting from 1) is at y = 20 + (r − 1) × 100, and five rows make the drawing 2 × 20 + 5 × 40 + 4 × 60 = 480 high. Here is all of it:

(:~ The layout of a diagram: the size of the drawing and where each box goes. :)
declare function draw:layout($diagram as element(diagram)) as draw:layout {
  let $ranks := draw:ranks($diagram)
  let $rows := (
    for $node in $diagram/node
    group by $rank := $ranks($node/@id)
    order by $rank
    return array { $node/@id/string() }
  )
  let $row-width := fn($row as array(*)) as xs:integer {
    array:size($row) * $draw:box-width + (array:size($row) - 1) * $draw:gap-across
  }
  let $width := 2 * $draw:padding + max($rows ! $row-width(.))
  let $height := 2 * $draw:padding + count($rows) * $draw:box-height
    + (count($rows) - 1) * $draw:gap-down
  let $places := map:merge(
    for $row at $row-number in $rows
    let $left := ($width - $row-width($row)) idiv 2
    for member $id at $position in $row
    return {
      $id: draw:place(
        $left + ($position - 1) * ($draw:box-width + $draw:gap-across),
        $draw:padding + ($row-number - 1) * ($draw:box-height + $draw:gap-down)
      )
    }
  )
  return draw:layout($width, $height, $places)
};

The places come from two nested loops: for $row at $row-number over the sequence of rows, and for member $id at $position over the members of one row's array. Each pair gives a one-entry map, and map:merge puts them together.

$ sxml xquery --method=adaptive --context-item=diagram.xml --expression='import module namespace draw = "urn:example:draw" at "draw.xqm"; draw:layout(/diagram)'
{"width":360,"height":480,"places":{"browser":{"x":20,"y":20},"node":{"x":200,"y":20},"api":{"x":110,"y":120},"flags":{"x":110,"y":220},"registry":{"x":20,"y":320},"cache":{"x":200,"y":320},"postgresql":{"x":20,"y":420},"redis":{"x":200,"y":420}}}

These are the numbers in diagram.svg: the rect of registry is at x="20" y="320".

Where the lines go

An edge is a line between two boxes. Which sides it joins depends on where the boxes are, and draw:line returns the line's ends as four numbers, or nothing for an edge from a node to itself, which draw:loop draws as a small curve below the box instead:

(:~ The ends of an edge's line (x1, y1, x2, y2), or nothing for an edge
    from a node to itself. :)
declare function draw:line($from as draw:place, $to as draw:place) as xs:integer* {
  let $half := $draw:box-width idiv 2
  let $middle := $draw:box-height idiv 2
  return if ($from?x = $to?x and $from?y = $to?y) then ()
    else if ($to?y > $from?y) then      (: down: bottom centre to top centre :)
      ($from?x + $half, $from?y + $draw:box-height, $to?x + $half, $to?y)
    else if ($to?y < $from?y) then      (: up: right of the centre, so that it
                                           does not cover an edge going down :)
      ($from?x + $half + 30, $from?y, $to?x + $half + 30, $to?y + $draw:box-height)
    else if ($to?x > $from?x) then      (: across, to the right :)
      ($from?x + $draw:box-width, $from?y + $middle, $to?x, $to?y + $middle)
    else                                (: across, to the left :)
      ($from?x, $from?y + $middle, $to?x + $draw:box-width, $to?y + $middle)
};

(:~ The path of an edge from a node to itself: a loop below the box, left
    of the edges that leave its centre. :)
declare function draw:loop($place as draw:place) as xs:string {
  let $left := $place?x + 20
  let $bottom := $place?y + $draw:box-height
  return `M {$left} {$bottom} C {$left} {$bottom + 24}, {$left + 30} {$bottom + 24}, {$left + 30} {$bottom}`
};

An edge down, the common case, leaves the bottom centre of its source and arrives at the top centre of its target. An edge up (in states.xml, check.failed from checking back to stable) runs a little to the right, so that it doesn't cover the edge that goes down between the same boxes. Edges in one row join the sides. A line that passes a box on its way is hidden under it, because the boxes are drawn last; a bigger tool would route it around.

$ sxml xquery --method=adaptive --expression='import module namespace draw = "urn:example:draw" at "draw.xqm"; draw:line(draw:place(110, 220), draw:place(20, 320)), draw:loop(draw:place(20, 20))'
180
260
90
320
"M 40 60 C 40 84, 70 84, 70 60"

The first four numbers are the edge from flags down to registry, as diagram.svg draws it: from (180, 260) to (90, 320).

The layout as XML

Maps and records are what XQuery computes with, but another tool can't read them. layout.xq writes the layout as XML: the description again, with the size of the drawing on diagram, the place on each node, and the line (or the loop's path, d) on each edge:

layout.xq:

xquery version "4.0";
(: The layout of a diagram (the context item) as XML: the description
   with the size of the drawing, the place of every box, and the line
   (or, from a node to itself, the loop) of every edge. :)
import module namespace draw = "urn:example:draw" at "draw.xqm";
declare option output:indent "yes";

let $diagram := /diagram
let $layout := draw:layout($diagram)
let $places := $layout?places
return <diagram>{
  $diagram/@*,
  attribute width { $layout?width },
  attribute height { $layout?height },
  for $node in $diagram/node
  let $place := $places($node/@id)
  return <node>{ $node/@*, attribute x { $place?x }, attribute y { $place?y } }</node>,
  for $edge in $diagram/edge
  let $from := $places($edge/@from)
  let $line := draw:line($from, $places($edge/@to))
  return <edge>{
    $edge/@*,
    if (exists($line)) then
      for $name at $position in ("x1", "y1", "x2", "y2")
      return attribute { $name } { $line[$position] }
    else attribute d { draw:loop($from) }
  }</edge>
}</diagram>

Attributes are copied from the description and made with computed attribute constructors: attribute { $name } { … } takes its name from an expression, which is how the four ends of a line get their names. An edge between two modules has no label in the description, so it has none here either: $edge/@* copies the attributes there are.

$ sxml xquery --context-item=diagram.xml layout.xq
<diagram title="Vane" width="360" height="480">
  <node id="browser" label="@vane/browser" x="20" y="20"/>
  <node id="node" label="@vane/node" x="200" y="20"/>
  <node id="api" label="vane/api" x="110" y="120"/>
  <node id="flags" label="vane/flags" x="110" y="220"/>
  <node id="registry" label="vane/registry" x="20" y="320"/>
  <node id="cache" label="vane/cache" x="200" y="320"/>
  <node id="postgresql" label="postgresql" kind="store" x="20" y="420"/>
  <node id="redis" label="redis" kind="store" x="200" y="420"/>
  <edge from="browser" to="api" label="HTTP" x1="90" y1="60" x2="180" y2="120"/>
  <edge from="node" to="api" label="HTTP" x1="270" y1="60" x2="180" y2="120"/>
  <edge from="api" to="flags" x1="180" y1="160" x2="180" y2="220"/>
  <edge from="flags" to="registry" x1="180" y1="260" x2="90" y2="320"/>
  <edge from="flags" to="cache" x1="180" y1="260" x2="270" y2="320"/>
  <edge from="registry" to="postgresql" label="SQL" x1="90" y1="360" x2="90" y2="420"/>
  <edge from="cache" to="redis" label="Redis" x1="270" y1="360" x2="270" y2="420"/>
</diagram>

Drawing with XSLT draws from this file. First, the drawing in XQuery itself.