Automatic Layout of Railroad Diagrams

In this paper, we study the layout of railroad diagrams as an emblematic instance of a 1.5-dimensional problem, whose challenges – nested wrapping, alignment and justification, wide hand-drawn stylistic variation – are representative of the class. More precisely, we formalize and develop an algorithm for railroad layout:

1. 1.

   We define a diagram language and a layout language (Subsection 2.1, Subsection 2.2) that lets us precisely specify railroad layout as compilation from the former to the latter (Subsection 2.4).

2. 2.

   We show that our formalism is realistic despite being simple: it captures most of the variation in hand-drawn railroad diagrams and guides the design of a practical algorithm.

3. 3.

   We design a three-step compilation algorithm, illustrated in Figure 4, consisting of vertical alignment, then wrapping to meet a target width, and finally horizontal justification.

4. 4.

   We frame wrapping as parametric optimization and develop practical heuristics (Subsection 3.2).

5. 5.

   We implement the compiler that we describe.

First, we present our formalism (Section 2) and then our algorithm (Section 3), although the two evolved together in reality. Then, we argue that our formalism is realistic by showing that common grammar notations are easy to translate to our diagram language (Subsection 4.1) and that most manual layouts can be expressed in our layout language (Subsection 4.2). We further argue that our algorithm compares favorably to manual layout, going beyond existing tools (Subsection 4.3) while being performant enough for interactive use (Subsection 4.4). Lastly, we discuss how prior work in layout and diagramming relates to ours (Section 5).

The novelty of our solution lies in its practical, principled approach to automatic railroad layout, notably for wrapping. When used as static documentation, railroad diagrams are often laid out and updated by hand (e.g. Figures 1 and 5 except 5(d)). Manual layout is tedious and hard to update [15], especially when reflowing a wrapped layout or maintaining differently-wrapped layouts for different media. Worse, it is prone to semantic errors and stylistic inconsistencies (e.g. Figures 25 and 26) [15]. Beyond addressing these problems with automation, our tool can also reproduce many existing manual layouts and produce comparable alternatives for the rest, making it a practical replacement. Further, it is unique in its principled approach aiming for convenient layout “idioms” and “cost-benefit balance” [21], with exploratory, interactive theorem-proving and programming environments in mind. For instance, few other tools perform automatic wrapping, and none let the user control it.

Formalism has long served as a tool for clarity of thought and computational expression in layout research, and we follow suit. We hope that formal foundations will aid further study of railroad layout beyond our work and of its applications beyond syntax. As an example, an extension of regular algebra gives Kleene Algebra with Tests (KAT), a powerful formalism for equational reasoning about programs and control flow [57]; a corresponding slight extension to railroad diagrams can illustrate KAT terms (e.g. Figure 3). Recent work on the formal semantics of railroad diagrams and similar diagrammatic calculi [40, 69, 2] as well as formally verified web layout [67, 66] and pretty-printing [74] suggests several directions for future work. More broadly, structured layout remains an open problem for ubiquitous diagrammatic notations, and we hope railroad-style layout may play a part in a unifying solution.

diagram

A conceptual specification in terms of components and how they connect and compose. It has no height, width, or other visual properties, but it has structure.

layout

A graphical specification in terms of basic shapes and their sizes and positions. It has visual properties like height and width, but also retains structure from which the diagram can be recovered. It is the result of laying out a diagram, possibly under constraints like width. Figure 3 illustrates how a diagram can have many different layouts.

rendering

A concrete realization of a layout, in a format that can be directly displayed (like a bitmap) or executed for display (like canvas drawing instructions).

A diagram cannot be directly rendered, but must first be laid out. Yet, to have a visual reference for raw or partially laid-out diagrams, we use layouts rendered with dashed red lines, sometimes partly built by hand, e.g. to depict ill-formed intermediate states in Figure 4. Proper layouts are in solid black and are all generated by our tool.

1.5-dimensional layout problem

When layouts exhibit a hierarchically nested reading order. See the last paragraph before Subsection 1.1. Our definition aligns with previous, more limited uses of the term, discussed further in Section 5.

bounding box

The smallest axes-aligned rectangle that completely encloses a shape.

flexbox

The CSS Flexible Box Layout Module [92], which inspires some of our terminology but is not general enough for railroad layout. We will return to it in Section 3 and Section 5.

We define our diagram language inductively in Figure 7. The first two cases are terminal and nonterminal tokens parameterized by a string label. The next case is a sequence with zero or more subterms. The last case is a stack with exactly two subterms, parameterized by a polarity, + or -. An empty sequence () is also denoted $\epsilon$. For the rest of this paper, a “diagram” is a term in this language. The constructors are illustrated in 6(a).

Although laid-out stacks often appear to have more than two subdiagrams (e.g. the three-way stack in 1(a)), we find that having stacks be only binary is the simplest model that accounts exactly for all possible layouts. We use the same constructor for positive and negative stacks because both result in a layout with (i) vertically stacked sublayouts with brackets on the sides, (ii) no wrapping opportunities beyond what the sublayouts present, and (iii) possible collapsing with a containing stack. However, they differ in when such collapsing is possible, such as in 6(b). We thus need layout well-formedness rules to capture such differences, and in Subsection 2.3, we state a clean set of such rules while treating all stack layouts as binary. Consequently, to simplify the relation between diagrams and layouts, we treat (diagram-level) stacks as binary, too. (The association order of nested binary positive stacks does not affect the rendering, unlike negative stacks (see Subsection 4.1).)

In contrast to stacks, the association order of subdiagrams in a sequence has no bearing on the layout, so sequences are $n$-ary without ado. Formally, the canonical form of a diagram is the result of repeatedly splicing nested sequences, a trivially confluent rewriting: any sequence (D₁ …) with a subdiagram D_i which is itself a sequence (D_i1 …) is rewritten to (D₁ … D_i1 … …), replacing D_i with its subdiagrams. We call two diagrams equivalent if they have the same canonical form.

We define our layout language inductively in Figure 9 and illustrate it in Figure 10. The constructors, and their parameters beyond direction (left-to-right or right-to-left), are:

• $\mathrm{■}$

  (atomic constructors) rails, with a nonnegative real width; spaces; and stations, with a string label and a terminal flag indicating whether it is a terminal;

• $\mathrm{■}$

  a horizontal concatenation of one or more subterms;

• $\mathrm{■}$

  an inline vertical concatenation (“inline VC”) of two or more subterms, with a string marker and left and right tip specifications; and

• $\mathrm{■}$

  a block vertical concatenation (“block VC”) of exactly two subterms, with a polarity (positive or negative) and left and right tip specifications.

A tip is where a layout starts or ends, and where a containing layout can connect to enter or exit it. Naturally, each layout has a tip on either side. Either tip of a VC can be specified as:

• $\mathrm{■}$

  vertical, for collapsing with a containing stack;

• $\mathrm{■}$

  a logical row number, a positive integer, to align with an inner sublayout after collapse; or

• $\mathrm{■}$

  a physical proportion, a real between 0 and 1, interpolating between the highest (0) and lowest (1) possible tips, which are not necessarily aligned with logical rows.

Any other layout has (logical 1) tips on both sides by default. Lastly, we define the start and end sides of an inline VC as left and right if the direction is left-to-right, else vice versa.

Unlike diagrams, not all layouts in the language above are well-formed. For instance, a right-to-left horizontal concatenation must be constructed with right-to-left sublayouts, in visual (i.e., reverse) order (e.g. bottom left of Figure 10). In informal terms, our definition of well-formedness (to follow) aims to avoid “nonsense” layouts, where, say, a collapsed edge has no consistent direction, or sublayouts are visually disconnected. Moreover, a well-formed layout leaves no ambiguity or context-dependence in its rendering.

To state the well-formedness rules, we must first define three other layout properties: width, number of logical and connectable rows on either side, and up- and down-connectability on either side. The definition of width below assumes a constant $S$, the unit width around curves and boxes.

• $\mathrm{■}$

  The width of a rail is its width parameter.

• $\mathrm{■}$

  The width of a space is $2S$.

• $\mathrm{■}$

  Stations have implementation-dependent widths, plus $2S$.

• $\mathrm{■}$

  The width of a horizontal concatenation is the sum of its sublayouts’.

• $\mathrm{■}$

  The width of an inline VC is the sum of: (i) the width of its first sublayout; (ii) the width of its marker (implementation-dependent); and (iii) $3S$ if its start-side tip specification is a physical proportion other than 0 (i.e. if it needs a bracket), and likewise for its end side if other than 1.

• $\mathrm{■}$

  The width of a block VC is that of its first sublayout, plus $3S$ for each non-vertical tip.

The multiples of $S$ account for vertical brackets in the rendering, e.g. as illustrated by Figure 13 for a block VC.

Second, we define the number of logical rows on either side. The number of connectable rows is equal to the logical one except where noted. All tips and numbers of rows refer to the same universally quantified side:

• $\mathrm{■}$

  Spaces, rails, stations, and block VCs with a non-vertical tip all have 1 row.

• $\mathrm{■}$

  A horizontal concatenation has as many rows as its sidemost sublayout.

• $\mathrm{■}$

  An inline VC has as many rows on its start side as its first sublayout on that side, and likewise for its end side with its last sublayout.

• $\mathrm{■}$

  A positive block VC with a vertical tip has as many rows as the sum of the number of connectable rows of its top and bottom sublayouts.

• $\mathrm{■}$

  A negative block VC with a vertical tip has as many logical rows as the sum of its top and bottom sublayouts, minus the number of connectable rows of its top sublayout, plus 1; and only 1 connectable row. (See Figure 13.)

Third, we define up- and down-connectability on either side. Up-connectability is meant to capture if a layout can be connected to “from above” when contained in block VCs, and likewise for down-connectability; see Figure 13. “Both-” and “neither-connectable” have their natural meanings. “Up-/down-” means up- and down- separately. On each side:

• $\mathrm{■}$

  Rails, stations, and block VCs with a non-vertical tip are all neither-connectable.

• $\mathrm{■}$

  A space is both-connectable.

• $\mathrm{■}$

  A horizontal concatenation is up-/down-connectable only if its sidemost sublayout is.

• $\mathrm{■}$

  An inline VC is up-/down-connectable on its start side only if its first sublayout is; and likewise on its end side with its last sublayout.

• $\mathrm{■}$

  The up-/down-connectability of a block VC with a vertical tip and polarity pol depends on the nature of its top/bottom sublayout and is best described with tables. Below, “if top/bot” means “if the top/bottom sublayout has the property under consideration”.

  pol	top sublayout	up-ctbl.
  +	-ve block VC	no
  +	else	if top
  -	+ve block VC	no (Figure 13)
  -	else	if top

  pol	bot sublayout	down-ctbl.
  +	-ve block VC	no
  +	else	if bot
  -	-ve block VC	no
  -	else	if bot

Finally, we can state the well-formedness rules, also presented as formulae in Figure 14.

WF_r, WF_sp, WF_st

Rails, spaces, and stations are well-formed.

WF_c

A horizontal or inline vertical concatenation $\mathrm{\ell }$ is well-formed if all sublayouts are well-formed and have the same direction as $\mathrm{\ell }$.

WF_hc

In addition to WF_c, a horizontal concatenation is well-formed if all sublayouts are neither-connectable, except possibly its sidemost sublayouts.

WF_t

A VC is well-formed if, on either side, if the tip is (logical r), then r is no greater than the number of logical rows; or if it is vertical, then the VC is either up- or down-connectable.

WF_ivc

In addition to WF_t, an inline VC is well-formed if:

• $\mathrm{■}$

  All sublayouts are neither-connectable, except possibly the first sublayout on its start side or the last sublayout on its end side.

• $\mathrm{■}$

  The first and last sublayouts have the same width $w\ge m$, and the other sublayouts have width $w-m$, where $m$ is the width of the marker.

WF_bvc

In addition to WF_t, a block VC with direction dir and polarity pol is well-formed if:

• $\mathrm{■}$

  Both sublayouts are well-formed and have the same width.

• $\mathrm{■}$

  The top sublayout is down-connectable on each side, and has direction dir.

• $\mathrm{■}$

  The bottom sublayout is up-connectable on each side, and has direction dir iff pol is +.

$\widehat{\text{WF}}$

In addition to all the above, a top-level (i.e. outermost) layout is well-formed if it is neither-connectable on both sides.

To lay out a diagram is to compile a diagram d to a layout l such that (i) d and (diagram-of l ) are equivalent, with equivalence as defined at the end of Subsection 2.1, and the function diagram-of as defined below; and (ii) $\widehat{\text{WF}}$(l ) as defined above.

Layouts of linear content often have a main axis aligned with the inherent linear order and an orthogonal cross axis, each with a natural start and end side.³³3Although we explain our terminology without further citation below, it is heavily inspired by the CSS Flexible Box Layout Module [92], or flexbox for short. We discuss key differences in Section 5. E.g., the main axis of English text is left-to-right, and the cross axis is top-to-bottom (18(a)); the main axis of a vinyl is circular, and the cross axis is radial. Railroad layouts have a horizontal main axis with a direction per their dir parameter, and a top-to-bottom cross axis. Then, alignment and justification are about the cross- and main-axis positioning of sublayouts, respectively.

Railroad alignment is best described in terms of the tips of each layout on each side, rather than the positions of their bounding boxes. For example, the sublayouts of sequences in 18(b) cannot be explained as top-, center-, or bottom-aligned with respect to their bounding boxes. It is simpler to say that each is laid out with a default choice of logical tips, and the containing layouts are formed by positioning the sublayouts so as to align the tips. An alignment policy, then, specifies for any diagram which tips its subdiagrams are to be laid out with under which circumstances. Alignment accounts for collapsing: a subdiagram contained in a stack may be laid out with a vertical tip to collapse with its container. 18(c) illustrates the alignment policies we suggest. “Baseline” captures common patterns beyond the three simpler positional ones, such as choosing logical 2 tips for a stack whose top subdiagram is an empty sequence and bottom has only one row. It also demonstrates that the left and right tips of a layout need not be at the same height.

Thus, alignment lowers an immediate diagram to an aligned diagram as presented in Figure 16, where each sequence and stack has tip specifications for its eventual layout, and spaces are explicit. To ensure well-formedness, our compiler: (i) specifies vertical tips and inserts spaces to make the sublayouts of block VCs correctly connectable (WF_bvc), as the recursive definitions of connectability have only spaces as their positive base case; (ii) avoids their negative base cases by conservatively never specifying vertical tips for negative block VCs;⁴⁴4Creators sometimes prefer negative block VCs to not collapse even when possible, such as in Figure 3. and (iii) avoids inserting spaces in the middle of a sequence (WF_hc, WF_ivc) or at the ends of an outermost sequence ($\widehat{\text{WF}}$).

Next, wrapping turns each sequence into a set of possible compositions of horizontal and inline vertical concatenations (wraps) and orders them by preference. We describe this process in detail in the next section but assume its result, viz. Figure 17, to explain justification below. In particular, we assume the min-content and max-content widths are defined for each term: the minimum width of its eventual layout if, respectively, all wrapping opportunities are taken, or none are.

The last step of lowering to the layout language is justification. It chooses one of the possible wraps and distributes extra width around and among items in each (wrapped) row, aiming to ensure three properties at each level of nesting, explained in Figure 19. The policies for distributing width around items (if any) are illustrated in 18(d). This process satisfies width-related well-formedness criteria by creating horizontal concatenations and rails while preserving diagram equivalence.

Our compiler implements justification as a recursive algorithm on wrapped diagrams with an additional target-width argument. The top-level target-width the user requests must be at least the min-content of the top-level diagram to ensure that some layout is possible. Then:

• $\mathrm{■}$

  For stations and spaces, the algorithm does nothing, as they are inflexible.

• $\mathrm{■}$

  For each vertical concatenation, the algorithm (i) subtracts the fixed widths associated with tips and markers from target-width; (ii) ensures that each subdiagram is a horizontal concatenation (potentially by constructing one); and finally (iii) recurses on each (horizontal concatenation) subdiagram with the (updated) target-width.

• $\mathrm{■}$

  For each ordered set of wraps, the algorithm selects the first (i.e. most preferred) wrap whose min-content is no greater than target-width (i.e. which is guaranteed to fit).

For each horizontal concatenation, the algorithm is more involved:

1. 1.

   Let aw and rw be variables representing the absorbed and remaining width to be distributed around and among sublayouts, respectively. Let sw_i be variables representing the subwidths assigned to each subdiagram d_i, for 1 $\le$ i $\le$ n.

   1. a.

      Initialize aw to $(\text{n}-1)\cdot \text{gap}$ (minimum spacing).

   2. b.

      Initialize each sw_i to d_i.min-content (minimum widths).

   3. c.

      Initialize rw to $\text{target-width}-\text{aw}-\mathrm{\Sigma }\text{sw}\text{<sub class="ltx\_sub"><span class="ltx\_text ltx\_font\_sansserif ltx\_font\_italic">i</span></sub>}$.

   We will maintain the invariant $\text{rw}+\text{aw}+\mathrm{\Sigma }\text{sw}\text{<sub class="ltx\_sub"><span class="ltx\_text ltx\_font\_sansserif ltx\_font\_italic">i</span></sub>}=\text{target-width}$. By the end, $\text{rw}=0$.

2. 2.

   Let the growth width $\text{g}\text{<sub class="ltx\_sub"><span class="ltx\_text ltx\_font\_sansserif ltx\_font\_italic">i</span></sub>}=(\text{d}\text{<sub class="ltx\_sub">i</sub>}\text{.max-content}-\text{d}\text{<sub class="ltx\_sub">i</sub>}\text{.min-content})$. Let the maximum growth width $\text{mg}=\min (\text{rw},\mathrm{\Sigma }\text{g}\text{<sub class="ltx\_sub"><span class="ltx\_text ltx\_font\_sansserif ltx\_font\_italic">i</span></sub>})$. Increment each sw_i by $\text{mg}\cdot \text{g}\text{<sub class="ltx\_sub"><span class="ltx\_text ltx\_font\_sansserif ltx\_font\_italic">i</span></sub>}/\mathrm{\Sigma }\text{g}\text{<sub class="ltx\_sub"><span class="ltx\_text ltx\_font\_sansserif ltx\_font\_italic">i</span></sub>}$, and decrement rw by mg.

3. 3.

   Increment aw by $\text{rw}\cdot \text{flex-absorb}$, and decrement rw by the same amount.

4. 4.

   Let d_j, etc. denote only those subdiagrams that are concatenations (and hence can grow further). If there are none, increment aw by rw and set rw to zero. Else, increment each sw_j by $\text{rw}\cdot (\text{d}\text{<sub class="ltx\_sub">j</sub>}\text{.max-content})/\mathrm{\Sigma }(\text{d}\text{<sub class="ltx\_sub">j</sub>}\text{.max-content})$ and set rw to zero.

5. 5.

   Distribute aw among rails between and around subdiagrams per justify-content, gap, and the current direction. Recursively justify each subdiagram with target width sw_i. Return a new horizontal concatenation with said justified subdiagrams and rails.

We make three remarks about the relationship between alignment and justification. First, alignment applies to each sublayout of a container individually, whereas justification only makes sense as a collective property of all the sublayouts taken together, so the former policy is called align-items and the latter justify-content. Second, if a sequence wraps across multiple rows, alignment and justification apply to each row independently, although policies may specify different behaviors for the first, middle, and last rows. And third, alignment actually depends on the justification policy, because the side of a stack can collapse with its container only if the two are guaranteed to be directly adjacent, without the possibility of any rails in between (e.g. Figure 20). Now, justification must happen after wrapping because it works on each wrapped row, and wrapping must happen after alignment because it depends on widths, which depend on tip specifications; but the dependency is not circular, because alignment only depends on the justification policy, and not its realization.

The net result of the lowering is thus a well-formed layout, equivalent to the original diagram, that has width exactly target-width, with alignment and justification per the align-items, justify-content, flex-absorb, and gap global parameters.

Many layout problems are stated in terms of hard constraints and softer optimization objectives. 1-dimensional problems like text wrapping and code pretty-printing treat layout width as a hard constraint, while trying to minimize properties like height,⁶⁶6This seems obvious but bears further thought. It is the main axis that has a hard constraint, and the cross axis that is subject to minimization. Layouts with different reading orders behave accordingly: for instance, traditional Chinese calligraphy was laid out on horizontal scrolls, with a top-to-bottom main axis (limited by paper height) and a right-to-left cross axis (e.g. [33]). 1-dimensional layouts are informally often measured along the cross axis – books in pages, code in lines, scrolls in inches – implicitly assuming the layout makes good use of a reasonable main-axis size. deviance from normative spacing, and drastic variation between lines [56, 74]. In contrast, the constraints and objectives for 2-dimensional layout problems are typically isotropic properties, unlike size. For instance, among Graphviz’s 8 graph layout algorithms, 5 do not favor any axis over another; 1 (“circo”) distinguishes radial and circular axes, but minimizes edge crossings (independent of direction); and 2 (“dot” and “twopi”) are explicitly hierarchical layouts that impose a 1-dimensional structure of discrete “ranks” or “levels”) on the graph [35].

Railroad layouts, being 1.5-dimensional, fall somewhere in between. Like 1-dimensional layouts, they follow a reading order and are wrapped in practice, so we treat target width as a hard constraint (and in fact, an exact one, as railroad layouts stretch more and suffer less from sparse rows than text or code). But Figure 22 illustrates how the usual parameters of 1-dimensional layout – width, height, and balance – cannot explain the additional “.5 dimension” of railroad layout decisions. Informally, layouts with less and shallower wrapping are preferred, while trying to make good use of available space.

One of our key contributions is to identify that encoding these preferences as optimization for just the wrapping step is sufficient for practical purposes, instead of phrasing the whole railroad layout problem as optimization. This helps us avoid the instability typical of optimization-based 2-dimensional layouts and develop heuristics for local wrapping (of every sequence) in addition to global wrapping (of the whole diagram). In computational terms, we express the result of wrapping as a total order over possible wraps, i.e. compositions of horizontal and inline vertical concatenations for each sequence, either per sequence (“local”) or for all sequences in the diagram at once (“global”). This results in a locally or globally wrapped diagram as in Figure 17. Standard techniques can then find the optimal (per the total order) wrap subject to a target width constraint.⁷⁷7Technically, a total order is stronger than we need: an order in which any subset of wraps bounded by width has a least element would be sufficient. However, we have not found the distinction to matter.

Next, rather than try to define a single total order to cater to all styles and use cases, we describe a few principled optimality parameters that explain wrapping decisions we observed in the wild. We begin with three preliminary definitions: the wrap specification for a sequence, the min-content and max-content widths of a wrapped diagram, and the height of a globally wrapped diagram.

A wrap specification encodes a composition of horizontal and inline vertical concatenations for a sequence as a set of positive integer wrap points, each specifying the index of the first subdiagram on a row (and hence each no less than 1 and no greater than the number of subdiagrams). Naturally, 1 must be a wrap point; the wrap specification {1} means there is only one row, i.e. a horizontal concatenation, and other specifications signify an inline VC containing horizontal concatenations.⁸⁸8Although it would be valid to nest inline VCs further, our encoding cannot express it, because we have not found it useful in practice and it can be achieved with nested sequences anyway. For example, for the sequence d₁, d₂, d₃, d₄, the wrap specification {1, 4} means d₁, d₂, and d₃ are on the first row, and d₄ is on the second.

The min- or max-content width of a wrapped diagram is the minimum width of its eventual layout if, respectively, all wrap points are taken, or none are.

• $\mathrm{■}$

  For stations and spaces, both are equal to the layout width as defined in Subsection 2.2.

• $\mathrm{■}$

  For a horizontal concatenation, min-content is computed just like the layout width, except using the min-contents of its subdiagrams instead of their layout widths, and accounting for the minimum gap between subdiagrams; and likewise for max-content.

• $\mathrm{■}$

  For a vertical concatenation, min-content is computed just like the layout width, except using the maximum min-content among its subdiagrams instead of the layout width of the first sublayout; and likewise for max-content.

• $\mathrm{■}$

  For a set of wrapped diagrams, min-content is the minimum value of min-content, and max-content is the max-content of the element in which all wrap specifications are {1}.

Note that we are not actually performing layout to compute these properties, but just using the same formulae. Note also that a globally wrapped diagram is a set of global wraps, but global wraps contain no sets themselves (see Figure 17). Hence, min- and max-content coincide for a global wrap and are equal to its layout width, which we will call just the content width, because their formulae only differ when there is a set of possibilities.

Lastly, the height of a global wrap is straightforward to compute. Stations have implementation-dependent heights; the height of a vertical concatenation is the sum of the heights of its subdiagrams, plus any space between rows; and the height of a horizontal concatenation can be computed by vertically aligning the internal tips of its subdiagrams to form a “baseline”, and taking the difference between the largest extent above and below that baseline of any subdiagram.

We can now explain the wrapping decisions we observed in manual layouts as finding an optimal global wrap with the objectives below. means gw₁ is preferable to gw₂.

Greater content width.

In other words, we prefer layouts that use more of the available width. All else being equal, $\text{gw}\text{<sub class="ltx\_sub">1</sub>}\text{.content}>\text{gw}\text{<sub class="ltx\_sub">2</sub>}\text{.content}$ implies .

Less and shallower wrapping.

Let the depth $d_{\text{t}}$ of each term t in a global wrap be defined as zero for the top-level term and one greater than the containing term for each subterm. Let ${\mathrm{\ell }}_{\text{t}}$ be the length of the wrap specification if t is a sequence wrap, else zero. Let $p_d(d_{\text{t}})$ be a real-valued depth penalty function and $p_{\mathrm{\ell }}({\mathrm{\ell }}_{\text{t}})$ a real-valued wrap-length penalty function. Then, the wrap penalty $p_w(\text{gw})$ is ${\mathrm{\Sigma }}_{\text{t}}{p}_{\mathrm{\ell }}({\mathrm{\ell }}_{\text{t}})\cdot p_d(d_{\text{t}})$. We need $p_d$ and $p_{\mathrm{\ell }}$ to be monotonic and positive. All else being equal, implies .

Lower height.

All else being equal, implies .

The last three criteria are phrased in terms of “all else being equal” assumptions. Two practical ways to satisfy them all at once are (i) to make a lexicographic order, defining a priority order among the three, or (ii) to make a numerical order on a linear combination of content width, wrap penalty, and height, where the first has a negative weight and the other two have positive weights. Either option makes a total order.

Of course, it is impractical to enumerate all global wraps to choose one: a diagram with $k$ sequences of $n$ subdiagrams each has $2^{k(n-1)}$ possible wraps. This motivates our locally wrapped diagrams, for which a recursive layout process can alternate between justification and choosing a wrap for each sequence, avoiding the combinatorial explosion. Below, we translate the global objectives into reasonable local versions. Recall that min-content and max-content are now distinct, and the unresolved ambiguity in subterms means that we cannot yet compute the height of a diagram.

Lesser max-content width beyond target width.

For global wraps, we prefer greater content widths for using more of the available space, because we know they are no greater than the target width. But for sequence wraps, the max-content width is typically greater than the target width; the smaller the excess, the closer its subdiagrams will be to their “full” max-contents, reducing further nested wrapping. (See Figure 22.)

Lesser max-content width for multi-row sequences.

As the max-content of a multi-row sequence is the maximum of its subdiagrams’, minimizing it leads to more balanced rows and better use of horizontal space, as moving any subdiagram from one row to another would only increase it. (The first row of Figure 22 illustrates this objective.)

Less and shallower wrapping.

As for global wraps.

As before, lexicographic order or numerical order on a linear combination of max-content and the wrap penalty are practical choices. (min-content seems irrelevant to the order. It roughly scales with the width of the widest or most deeply nested station in a diagram, not with any holistic property. Moreover, in our experiments, we have not yet found a case in which min-content distinguishes between two otherwise equal sequence wraps.)

We implemented a prototype of the algorithm above in Scala (compiled with Scala.js). It is available at github.com/epfl-systemf/librrd. As a summary, the parameters to layout are:

• $\mathrm{■}$

  the target width (and whether it should be achieved by global or local wrapping);

• $\mathrm{■}$

  align-items, the policy for vertical alignment of sublayouts;

• $\mathrm{■}$

  justify-content, the policy for horizontal justification of sublayouts;

• $\mathrm{■}$

  flex-absorb, the proportion of any extra width a horizontal concatenation uses for justification before passing the rest on to its sublayouts; and

• $\mathrm{■}$

  the minimum gap between sublayouts of a horizontal concatenation.

Layouts are rendered to SVG with classes and hierarchical structure amenable to further CSS styling. Our implementation is 1141 SLOC (excluding empty lines and comments), plus 314 SLOC for rendering. A web UI is available at systemf.epfl.ch/etc/librrd/. It implements an order over sequence wraps (local wrapping) that we have found to work well in practice, which first minimizes $\max {(0,\text{w}.\text{max-content}-\text{target-width})}^2+10\cdot p_w(\text{w})$ with wrap-length penalty $p_{\mathrm{\ell }}(\mathrm{\ell })=\mathrm{\ell }$ and depth penalty $p_d(d)=2^{2d}$, and then minimizes max-content.

A recursive translation from nonempty regular expressions to our diagram language is given in 23(a). (It is identical to the construction in [40].) An empty regular expression (i.e. 0, the empty language) cannot be drawn; to draw an arbitrary regular expression, 0s must first be eliminated using standard equivalences like $r\cdot 0=0$.

For a grammar specified in Backus-Naur form (BNF), the right-hand side of each rule is translated to a railroad diagram. A rule can refer to another of name a with the syntax <a>, represented as a nonterminal token [a]. The rest of the translation is also in 23(a).

Although technically sufficient, the treatment of iteration/recursion in both translations above is a little unsatisfying. Consider the definition of JSON list syntax as a regular expression and in BNF in 23(b), and the translation to railroad diagrams, assuming a list item is separately defined. In the regular expression diagram, we may prefer item to appear only once, as the top of the negative stack; similarly, we may prefer to make the recursion explicit in the BNF diagram as a negative stack. But we may prefer this transformation not to happen if there are several kinds of lists, and it just happens to be the case in the one depicted above that the first item is of the same kind as the rest. We cannot accommodate such preferences merely by adding rules to our translation table. Rather, seen as a notation for syntax diagrams, both regular expressions and BNF have a conflict between canonicity – objects are equivalent iff their representations are equal – and idiomaticity – the ability to conveniently express common representation idioms, like negative stacks for recursion. (This terminology was introduced by [21].)

Our diagram language, together with our approach to its compilation, is idiomatic, as it is specifically designed to express railroad diagrams under common constraints. However, it is not canonical: nested positive stacks can be reassociated without affecting the rendering, and the diagram (- (- D₁ D₂) D₃) can seemingly be rewritten to (- D₁ (+ D₂ D₃)). The deeper problem is that railroad diagrams do not yet enjoy the solid theoretical foundations of other syntax notations, from either the theory of computation or graph automata, that would let us reason more precisely about rewriting, canonicity, and semantics in general.

Figure 5 showed a few examples of diagrams outside our scope, chosen due to their broad variety of complex layout features, from corpuses that are often considered a reference by other illustrators to emulate. In Figure 24, we show our best approximation of each. It would not make sense to directly compare rendering properties like width and height, because they depend as much on stylistic choices like fonts and spacing as on layout. Neither would it make sense to compare wrap penalties, because we cannot infer the penalty functions implicitly expressed in those diagrams. We can only argue that our layouts are comparably compact and readable with the additional merit of being automatically laid out. Meanwhile, it is worth noting that the diagrams in Figure 5 (except 5(d)) were laid out by hand to document very widely used syntaxes: Apple Pascal, JSON, and SQLite. High-impact settings may motivate creators to invest in custom manual layout even when automated tools are available.

SQLite has made a particular effort to maintain high-quality railroad diagrams documenting its complete input syntax over many years, which makes for an instructive case study. A brief history (from check-ins 289df32643 and 9f5383c824): the diagrams were first introduced in 2008, using Tcl scripts to render from a railroad layout DSL. In 2020, striving for “additional flexibility in the formatting of syntax diagrams [to make them] easier to read and understand [and] maintain”, the project moved to directly specifying renderings in Pikchr, a modernized implementation of the PIC graphics language [71, 51]. The manual renderings indeed have many features the automatic ones did not: custom alignment and justification, more wrapping and collapsing, etc. But, being hand-written, they sometimes introduced stylistic inconsistencies (e.g. Figure 25, 26(a)). Nevertheless, in this tricky tradeoff between manual layout and manual rendering, the creators evidently chose the latter.

Our approach is an appealing third option in such a tradeoff space. Not only would it recover the benefits of automatic rendering for stylistic consistency, but it would also guarantee layout consistency, going beyond both manual layout and manual rendering. For instance, our notion of alignment would avoid the inconsistencies in Figure 25, 26(b), and 26(c) in current SQLite documentation. (We have reported the issues and submitted a patch fixing them.) Moreover, the translations presented in Subsection 4.1 open up the possibility of generating documentation diagrams for a language from the same standard syntax notation its parser uses, avoiding issues like in 26(d). These benefits would come at only a small cost: out of SQLite’s 71 syntax diagrams,

• $\mathrm{■}$

  46 can be expressed in our layout language, of which 41 perfectly and 5 differing only in permitted collapsing;

• $\mathrm{■}$

  20 are ill-nested layouts that can still be expressed in our diagram language and compiled to comparable layouts; and

• $\mathrm{■}$

  5 are ill-nested diagrams that would have to be rewritten to equivalent well-nested ones.

One of the 20 from the second category above is shown in Table 1, along with its specification in the pre-2020 SQLite DSL, our diagram language, and Pikchr. (Its pre-2020 layout was perfectly expressible in our layout language but its modern one is not, due to a vertical semantic $\epsilon$.) On one hand, the rendering from our prototype compiler is not significantly less readable or compact, and it corresponds to just one of many possible configurations for wrapping, alignment, and justification. On the other, our specification is the same size as the pre-2020 manual layout, and simpler, as it does not use layout-specific constructors like stack (for wrapping) or optx (for alignment), instead leaving those decisions to the compiler. To be clear, we do not aim to cast our prototype as a surefire replacement for SQLite’s current diagrams, but rather as a reasonable alternative in contexts with similar demands for consistency, flexibility, and maintainability.

Existing railroad diagram tools fall into two broad categories: rendering tools that render layout descriptions, and grammar translation tools that turn grammar notations into renderings. We describe the capabilities and limitations of a few representatives of each. In comparison, we argue that our system fills a niche in between, and can expand the capabilities of both.

Rendering tools define DSLs for specifying railroad layouts and compile these specifications to various backends. [88] cites the pre-2020 SQLite DSL as inspiration, and offers similar primitives for manual wrapping, manual alignment, etc. The design of the following tools is largely similar: [62, 5, 36, 24, 85, 41]. One that stands out is [4], for two reasons: (i) its layout DSL is considerably larger, with rare and complex constructs such as 5(d); and (ii) it enables a greater range of custom styling by letting users tag layout components to style their output SVG counterparts with CSS. These features, along with the quality of its renderings and its parallel implementations in two popular languages (Python and JavaScript), may explain why several other tools build upon it (e.g. [61, 58, 60, 29, 19]). [1], an in-progress work, tries to use CSS not just for styling but also for rendering, with an XML-like layout language directly embedded in a webpage. Lastly, [55, 70, 8, 98] have a more limited range of output but work within the constraints of the LaTeX and TikZ/PGF environments.

Grammar translation tools take descriptions of grammars instead of layouts as input. [6] renders from JavaScript-style regular expressions, [77] from EBNF, and [3] (e.g. 1(d)) from a syntax representation fragment of the XML-based DITA markup language [31]. In all grammar translators, the conflict between canonicity and idiomaticity that we described in Subsection 4.1 is evident. For example, [77] implements additional translation rules to better handle recursion, as well as some inlining of nonterminals and factoring of common subexpressions, but these are coarse-grained settings that affect all rules in a grammar (see Figure 27). [6] supports a variety of regex constructs, like ranged quantifiers, but does not produce nonempty loops at all. Many other tools run into the same conflict – [26, 52, 44, 28, 89, 76, 90, 34, 47, 16, 81] – and some choose to introduce layout-specific annotations (e.g., to explicitly notate loops) into their otherwise grammar-focused notations, while others have a fixed translation outside the user’s control. [90] is unique in letting users click to expand and collapse nonterminals inline, making it the only tool we have seen that uses a dynamic rendering format.

We found only four existing tools that perform automatic wrapping of any kind. [3] and [77] use a greedy algorithm, and [98] coöpts TeX’s line-breaking; none perform internal or nested wrapping or have any user-facing parameters besides the target width, as illustrated in Figure 27. [16] takes a different approach, with an algorithm for “compressing” diagrams translated from BNF by inlining or abstracting grammar rules in a diagram according to the available line width.

Three previous attempts at formalizing railroad layout have had varying results. The first, [39], proposed to address perceived flaws in conventional diagrams with an alternative “structured” diagrammatic notation, which seems to not have caught on. The second, [81], framed the layout problem as compilation from EBNF to a custom rendering language, all declaratively specified in Prolog. Despite the limitations of graphical environments of its time, the formal treatment quickly surfaces many finer properties of railroad layout such as nested wrapping and alignment, which we study in the present work. More recently, [7] introduced a graph-based formalism for railroad diagrams and a corresponding layout algorithm that combines layered layout with railroad-specific heuristics. However, the resulting layouts do not always look conventional, due to edge crossings, unnatural edge routing, etc.

Our approach starts from a specification of neither a layout nor a grammar, but a diagram, and compiles it to a layout independent of rendering. Grammar notations are intended for describing formal languages, not their visual representations, while previous layout DSLs are tightly coupled with rendering and have no definite notions of diagrammatic equivalence; our diagram language is the missing intermediate representation. The way we characterize the compilation problem lets us implement at least four features that no other tool has:

• $\mathrm{■}$

  parametric wrapping, either globally or locally;

• $\mathrm{■}$

  independent alignment of the two sides of a sublayout, e.g. to collapse one or both sides of a stack automatically in valid contexts, such as happens several times in 24(c);

• $\mathrm{■}$

  direction-aware justification; and

• $\mathrm{■}$

  wrapping and justification that account for the possible internal wrapping of sublayouts.

We posit that our layouts can easily be rendered with additional backends or features from the rendering tools above, and that our diagram language can be an idiomatic target for grammar translation tools that would let them address canonicity independently of layout.

We measured how long our prototype compiler took to lay out a few sample diagrams with the same parameters that produced the layout of each shown in this paper. We also measured a few of the largest diagrams we found in the SQLite and Oracle SQL documentation [59, 82]. For each diagram, we computed the mean and standard deviation over 10 runs, in milliseconds. We measured layout time on a laptop with an i7-1265U processor at 2.7 GHz and 32 GB of memory, running the Scala.js 1.19.0 compiler and the Node.js 20.10.0 runtime under Ubuntu 22.04.5. Table 2 shows the results.

As a point of comparison, we cite Penrose [99], an optimization-based mathematical diagramming tool intended for iterative, exploratory use. Our tool, despite being written with no explicit attention to performance, is well under the 500 ms limit Penrose considers the target for “data visualization, live programming, and other exploratory creative tools”.