Skip to main content

module lang::box::util::Box2Text

rascal-0.40.16

Two-dimensional text layout algorithm.

Usage​

import lang::box::util::Box2Text;

Dependencies​

import util::Math;
import List;
import String;
import lang::box::\syntax::Box;

Description​

The input to Box2Text is a hierarchy of "Boxes" represented by the Box algebraic data-type. These boxes put hard and soft relative positioning constraints on the embedded text fragments, and there is the global soft constraints of the width of the screen (or the paper). Box2Text can also add markup for syntax highlighting in either ANSI plaintext encoding, HTML font tags or LaTex macros.

This implementation is a port from ASF+SDF to Rascal. The ASF+SDF implementation was published as "From Box to Tex:An algebraic approach to the construction of documentation tools" by Mark van den Brand and Eelco Visser (June 30, 1994). The original Box concept was introduced by Joel Coutaz as this technical report: "The Box, A Layout Abstraction for User Interface Toolkits" (1984) Pittsburgh, PA: Carnegie Mellon University.

The main function format maps a Box tree to a str:

  • To obtain Box terms people typically transform ASTs or Parse Trees to Box using pattern matching in Rascal.
  • Options encode global default options for constraint parameters that only override local parameters if they were elided.

Examples​

This demonstrates the semantics of the main hard constraints:

  • H for horizontal;
  • V for vertical;
  • I for indentation.
rascal>import lang::box::util::Box2Text;
ok
rascal>import lang::box::\syntax::Box;
ok
rascal>format(H([L("A"), L("B"), L("C")], hs=2))
str: "A  B  C\n"
---
A  B  C

---
rascal>format(H([L("A"), L("B"), L("C")], hs=1))
str: "A B C\n"
---
A B C

---
rascal>format(H([L("A"), L("B"), L("C")], hs=0))
str: "ABC\n"
---
ABC

---
rascal>format(V([L("A"), L("B"), L("C")], vs=2))
str: "A\n\n\nB\n\n\nC\n"
---
A


B


C

---
rascal>format(V([L("A"), L("B"), L("C")], vs=1))
str: "A\n\nB\n\nC\n"
---
A

B

C

---
rascal>format(V([L("A"), L("B"), L("C")], vs=0))
str: "A\nB\nC\n"
---
A
B
C

---
rascal>format(H([L("A"), V([L("B"), L("C")])]))
str: "A B\n  C\n"
---
A B
  C

---
rascal>format(H([L("A"), I([L("B")]), L("C")]))
str: "A B C\n"
---
A B C

---
rascal>format(H([L("A"), V([L("B"), H([L("C"), L("D")])])]))
str: "A B\n  C D\n"
---
A B
  C D

---

The "soft" constraints change their behavior based on available horizontal room:

rascal>format(HV([L("W<i>") | i <- [0..10]]));
str: "W0 W1 W2 W3 W4 W5 W6 W7 W8 W9\n"
---
W0 W1 W2 W3 W4 W5 W6 W7 W8 W9

---
rascal>format(HV([L("W<i>") | i <- [0..20]]));
str: "W0 W1 W2 W3 W4 W5 W6 W7 W8 W9 W10 W11 W12 W13 W14 W15 W16 W17 W18 W19\n"
---
W0 W1 W2 W3 W4 W5 W6 W7 W8 W9 W10 W11 W12 W13 W14 W15 W16 W17 W18 W19

---
rascal>format(HV([L("W<i>") | i <- [0..40]]));
str: "W0 W1 W2 W3 W4 W5 W6 W7 W8 W9 W10 W11 W12 W13 W14 W15 W16 W17 W18 W19 W20 W21\nW22 W23 W24 W25 W26 W27 W28 W29 W30 W31 W32 W33 W34 W35 W36 W37 W38 W39\n"
---
W0 W1 W2 W3 W4 W5 W6 W7 W8 W9 W10 W11 W12 W13 W14 W15 W16 W17 W18 W19 W20 W21
W22 W23 W24 W25 W26 W27 W28 W29 W30 W31 W32 W33 W34 W35 W36 W37 W38 W39

---
rascal>format(HV([L("W<i>") | i <- [0..80]]));
str: "W0 W1 W2 W3 W4 W5 W6 W7 W8 W9 W10 W11 W12 W13 W14 W15 W16 W17 W18 W19 W20 W21\nW22 W23 W24 W25 W26 W27 W28 W29 W30 W31 W32 W33 W34 W35 W36 W37 W38 W39 W40\nW41 W42 W43 W44 W45 W46 W47 W48 W49 W50 W51 W52 W53 W54 W55 W56 W57 W58 W59\nW60 W61 W62 W63 W64 W65 W66 W67 W68 W69 W70 W71 W72 W73 W74 W75 W76 W77 W78\nW79\n"
---
W0 W1 W2 W3 W4 W5 W6 W7 W8 W9 W10 W11 W12 W13 W14 W15 W16 W17 W18 W19 W20 W21
W22 W23 W24 W25 W26 W27 W28 W29 W30 W31 W32 W33 W34 W35 W36 W37 W38 W39 W40
W41 W42 W43 W44 W45 W46 W47 W48 W49 W50 W51 W52 W53 W54 W55 W56 W57 W58 W59
W60 W61 W62 W63 W64 W65 W66 W67 W68 W69 W70 W71 W72 W73 W74 W75 W76 W77 W78
W79

---
rascal>format(HV([L("W<i>") | i <- [0..100]]));
str: "W0 W1 W2 W3 W4 W5 W6 W7 W8 W9 W10 W11 W12 W13 W14 W15 W16 W17 W18 W19 W20 W21\nW22 W23 W24 W25 W26 W27 W28 W29 W30 W31 W32 W33 W34 W35 W36 W37 W38 W39 W40\nW41 W42 W43 W44 W45 W46 W47 W48 W49 W50 W51 W52 W53 W54 W55 W56 W57 W58 W59\nW60 W61 W62 W63 W64 W65 W66 W67 W68 W69 W70 W71 W72 W73 W74 W75 W76 W77 W78\nW79 W80 W81 W82 W83 W84 W85 W86 W87 W88 W89 W90 W91 W92 W93 W94 W95 W96 W97\nW98 W99\n"
---
W0 W1 W2 W3 W4 W5 W6 W7 W8 W9 W10 W11 W12 W13 W14 W15 W16 W17 W18 W19 W20 W21
W22 W23 W24 W25 W26 W27 W28 W29 W30 W31 W32 W33 W34 W35 W36 W37 W38 W39 W40
W41 W42 W43 W44 W45 W46 W47 W48 W49 W50 W51 W52 W53 W54 W55 W56 W57 W58 W59
W60 W61 W62 W63 W64 W65 W66 W67 W68 W69 W70 W71 W72 W73 W74 W75 W76 W77 W78
W79 W80 W81 W82 W83 W84 W85 W86 W87 W88 W89 W90 W91 W92 W93 W94 W95 W96 W97
W98 W99

---
rascal>format(HOV([L("W<i>") | i <- [0..10]]));
str: "W0 W1 W2 W3 W4 W5 W6 W7 W8 W9\n"
---
W0 W1 W2 W3 W4 W5 W6 W7 W8 W9

---
rascal>format(HOV([L("W<i>") | i <- [0..20]]));
str: "W0 W1 W2 W3 W4 W5 W6 W7 W8 W9 W10 W11 W12 W13 W14 W15 W16 W17 W18 W19\n"
---
W0 W1 W2 W3 W4 W5 W6 W7 W8 W9 W10 W11 W12 W13 W14 W15 W16 W17 W18 W19

---
rascal>format(HOV([L("W<i>") | i <- [0..30]]));
str: "W0\nW1\nW2\nW3\nW4\nW5\nW6\nW7\nW8\nW9\nW10\nW11\nW12\nW13\nW14\nW15\nW16\nW17\nW18\nW19\nW20\nW21\nW22\nW23\nW24\nW25\nW26\nW27\nW28\nW29\n"
---
W0
W1
W2
W3
W4
W5
W6
W7
W8
W9
W10
W11
W12
W13
W14
W15
W16
W17
W18
W19
W20
W21
W22
W23
W24
W25
W26
W27
W28
W29

---

By cleverly combining constraints, a specifically desired behavior is easy to achieve:

rascal>format(H([L("if"), H([L("("), L("true"), L(")")], hs=0), HOV([L("doSomething")])]))
str: "if (true) doSomething\n"
---
if (true) doSomething

---
rascal>format(H([L("if"), H([L("("), L("true"), L(")")], hs=0), HOV([L("W<i>") | i <- [0..30]])]))
str: "if (true) W0\n          W1\n          W2\n          W3\n          W4\n          W5\n          W6\n          W7\n          W8\n          W9\n          W10\n          W11\n          W12\n          W13\n          W14\n          W15\n          W16\n          W17\n          W18\n          W19\n          W20\n          W21\n          W22\n          W23\n          W24\n          W25\n          W26\n          W27\n          W28\n          W29\n"
---
if (true) W0
          W1
          W2
          W3
          W4
          W5
          W6
          W7
          W8
          W9
          W10
          W11
          W12
          W13
          W14
          W15
          W16
          W17
          W18
          W19
          W20
          W21
          W22
          W23
          W24
          W25
          W26
          W27
          W28
          W29

---
rascal>format(H([L("if"), H([L("("), L("true"), L(")")], hs=0), HV([L("W<i>") | i <- [0..30]])]))
str: "if (true) W0 W1 W2 W3 W4 W5 W6 W7 W8 W9 W10 W11 W12 W13 W14 W15 W16 W17 W18 W19 W20 W21\n          W22 W23 W24 W25 W26 W27 W28 W29\n"
---
if (true) W0 W1 W2 W3 W4 W5 W6 W7 W8 W9 W10 W11 W12 W13 W14 W15 W16 W17 W18 W19 W20 W21
          W22 W23 W24 W25 W26 W27 W28 W29

---

function format​

Converts boxes into a string by finding an "optimal" two-dimensional layout.

str format(Box b, int maxWidth=80, int wrapAfter=70)
  • This algorithm never changes the left-to-right order of the Boxes constituents, such that syntactical correctness is maintained
  • This algorithm tries to never over-run the maxWidth parameter, but if it must to maintain text order, and the specified nesting of boxes, it will anyway. For example, if a table column doesn't fit it will still be printed. We say maxWidth is a soft constraint.
  • Separator options like i, h and v options are hard constraints, they may lead to overriding maxWidth.
  • H, V and I boxes represent hard constraints too.
  • HV and HOV are the soft constraints that allow for better solutions, so use them where you can to allow for flexible layout that can handle deeply nested expressions and statements.

alias Text​

Box2text uses list[str] as intermediate representation of the output during formatting.

list[str]

Benefits​

  • Helps with fast concatenation
  • Allows for measuring (max) width and height of intermediate results very quickly

Pitfalls​

  • Because of this representation, box2text does not recognize that unprintable characters have width 0. So, ANSI escape codes, and characters like \r and \n in L boxes will break the accuracy of the algorithm.

function box2text​

Converts boxes into list of lines (Unicode).

Text box2text(Box b, int maxWidth=80, int wrapAfter=70)

data Options​

Configuration options for a single formatting run.

data Options  
     = options(
    int hs = 1, 
    int vs = 0, 
    int is = 2, 
    int maxWidth=80, 
    int wrapAfter=70
)
     ;

This is used during the algorithm, not for external usage.

  • hs is the current separation between every horizontal element in H, HV and HOV boxes
  • vs is the current separation between vertical elements in V, HV and HOV boxes
  • is is the default (additional) indentation for indented boxes
  • maxWidth is the number of columns (characters) of a single line on screen or on paper
  • wrapAfter is the threshold criterium for line fullness, to go to the next line in a HV box and to switching between horizontal and vertical for HOV boxes.

function u​

Quickly splice in any nested U boxes.

list[Box] u(list[Box] boxes)

function vv​

Simple vertical concatenation (every list element is a line).

Text vv(Text a, Text b)

function blank​

Create a string of spaces just as wide as the parameter a.

str blank(str a)

function wd​

Computes a white line with the length of the last line of a.

Text wd([])

Text wd([*_, str x])

function width​

Computes the length of unescaped string s.

int width(str s)

function twidth​

Computes the maximum width of text t.

int twidth([])

default int twidth(Text t)

function hwidth​

Computes the length of the last line of t.

int hwidth([])

int hwidth([*_, str last])

function bar​

Prepends str a before text b, all lines of b will be shifted.

Text bar(str a, [])

Text bar(str a, [str bh, *str bt])

function hskip​

Produce text consisting of a white line of length n.

Text hskip(int n)

function vskip​

Produces text consisting of n white lines at length 0.

Text vskip(int n)

function prepend​

Prepend Every line in b with a.

Text prepend(str a, Text b)

function hh​

Implements horizontal concatenation, also for multiple lines.

Text hh([], Text b)

Text hh(Text a, [])

Text hh([a], Text b)

default Text hh(Text a, Text b)

function lhh​

Text lhh([], Text _)

default Text lhh(a, b)

function rhh​

Text rhh(Text _, [])

Text rhh(Text a, Text b)

function rvv​

Text rvv(Text _, [])

default Text rvv(Text a, Text b)

function LL​

Text LL(str s )

function HH​

Text HH([], Box _, Options _opts, int _m)

Text HH(list[Box] b:[_, *_], Box _, Options opts, int m)

function VV​

Text VV([], Box _c, Options _opts, int _m)

Text VV(list[Box] b:[_, *_], Box c, Options opts, int m)

function II​

Text II([], Box _c, Options _opts, int _m)

Text II(list[Box] b:[_, *_], c:H(list[Box] _), Options opts, int m)

Text II(list[Box] b:[Box head, *Box tail], c:V(list[Box] _), Options opts, int m)

function WDWD​

Text WDWD([], Box _c , Options _opts, int _m)

Text WDWD([Box head, *Box tail], Box c , Options opts, int m)

function ifHOV​

Text ifHOV([], Box b,  Box c, Options opts, int m)

Text ifHOV(Text t:[str head], Box b,  Box c, Options opts, int m)

Text ifHOV(Text t:[str head, str _, *str_], Box b,  Box c, Options opts, int m)

function HOVHOV​

Text HOVHOV(list[Box] b, Box c, Options opts, int m)

function HVHV​

Text HVHV(Text T, int s, Text a, Box A, list[Box] B, Options opts, int m)

Text HVHV(Text T, int _s, [], Options _opts,  int _m, Box _c)

Text HVHV(Text T, int s, [Box head, *Box tail], Options opts,  int m, Box c)

Text HVHV([], Box _, Options opts, int m)

Text HVHV(list[Box] b:[Box head], Box _, Options opts, int m)

Text HVHV(list[Box] b:[Box head, Box next, *Box tail], Box _, Options opts, int m)

function GG​

Text GG([], Box(list[Box]) op, int gs, Box c, Options opts, int m)

Text GG([*Box last], Box(list[Box]) op, int gs, Box c, Options opts, int m)

Text GG([*Box heads, *Box tail], Box(list[Box]) op, int gs, Box c, Options opts, int m)

function continueWith​

Text continueWith(Box b:L(str s)         , Box c, Options opts, int m)

Text continueWith(Box b:H(list[Box] bl)  , Box c, Options opts, int m)

Text continueWith(Box b:V(list[Box] bl)  , Box c, Options opts, int m)

Text continueWith(Box b:I(list[Box] bl)  , Box c, Options opts, int m)

Text continueWith(Box b:WD(list[Box] bl) , Box c, Options opts, int m)

Text continueWith(Box b:HOV(list[Box] bl), Box c, Options opts, int m)

Text continueWith(Box b:HV(list[Box] bl) , Box c, Options opts, int m)

Text continueWith(Box b:SPACE(int n)     , Box c, Options opts, int m)

Text continueWith(Box b:U(list[Box] bl)  , Box c, Options opts, int m)

Text continueWith(Box b:A(list[Row] rows), Box c, Options opts, int m)

Text continueWith(Box b:G(list[Box] bl), Box c, Options opts, int m)

alias BoxOp​

General shape of a Box operator, as a parameter to G.

Box(list[Box])

function \continue​

Option inheritance layer; then continue with the next box.

Text \continue(Box b, Box c, Options opts, int m)

The next box is either configured by itself. Options are transferred from the box to the opts parameter for easy passing on to recursive calls.

data Box​

This is to store the result of the first pass of the algorithm over all the cells in an array/table.

data Box (int width=0, int height=1)

function boxSize​

Completely layout a box and then measure its width and height, and annotate the result into the Box.

Box boxSize(Box b, Box c, Options opts, int m)

function RR​

list[list[Box]] RR(list[Row] bl, Box c, Options opts, int m)

function Acolumns​

Compute the maximum number of columns of the rows in a table.

int Acolumns(list[Row] rows)

function Awidth​

Compute the maximum cell width for each column in an array.

list[int] Awidth(list[list[Box]] rows)

function AcompleteRows​

Adds empty cells to every row until every row has the same amount of columns.

list[Row] AcompleteRows(list[Row] rows, int columns=Acolumns(rows))

function align​

Helper function for aligning Text inside an array cell.

Box align(l(), Box cell, int maxWidth)

Box align(r(), Box cell, int maxWidth)

Box align(c(), Box cell, int maxWidth)

function AA​

Text AA(list[Row] table, Box c, list[Alignment] alignments, Options opts, int m)

function noWidthOverflow​

Check soft limit for HV and HOV boxes.

bool noWidthOverflow(list[Box] hv, Options opts)

function applyHVconstraints​

Changes all HV boxes that do fit horizontally into hard H boxes.

Box applyHVconstraints(Box b, Options opts)

function applyHOVconstraints​

Changes all HOV boxes that do fit horizontally into hard H boxes, and the others into hard V boxes.

Box applyHOVconstraints(Box b, Options opts)

function box2data​

Workhorse, that first applies hard HV and HOV limits and then starts the general algorithm.

Text box2data(Box b, Options opts)

Tests

test horizontalPlacement2​

test bool horizontalPlacement2()
    = format(H([L("A"), L("B"), L("C")], hs=2))
    == "A  B  C
       '";

test horizontalPlacement3​

test bool horizontalPlacement3()
    = format(H([L("A"), L("B"), L("C")], hs=3))
    == "A   B   C
       '";

test verticalPlacement0​

test bool verticalPlacement0()
    = format(V([L("A"), L("B"), L("C")], vs=0))
    == "A
       'B
       'C
       '";

test verticalPlacement1​

test bool verticalPlacement1()
    = format(V([L("A"), L("B"), L("C")], vs=1))
    == "A
       '
       'B
       '
       'C
       '";

test verticalIndentation2​

test bool verticalIndentation2()
    = format(V([L("A"), I([L("B")]), L("C")]))
    == "A
       '  B
       'C
       '";

test blockIndent​

test bool blockIndent()
    = format(V([L("A"), I([V([L("B"), L("C")])]), L("D")]))
    == "A
       '  B
       '  C
       'D
       '";

test wrappingIgnoreIndent​

test bool wrappingIgnoreIndent()
    = format(HV([L("A"), I([L("B")]), L("C")], hs=0), maxWidth=2, wrapAfter=2)
    == "AB
       'C
       '";

test wrappingWithIndent​

test bool wrappingWithIndent()
    = format(HV([L("A"), I([L("B")]), I([L("C")])], hs=0), maxWidth=2, wrapAfter=2)
    == "AB
       '  C
       '";

test flipping1NoIndent​

test bool flipping1NoIndent()
    = format(HOV([L("A"), L("B"), L("C")], hs=0, vs=0), maxWidth=2, wrapAfter=2)
    == "A
       'B
       'C
       '";

test horizontalOfOneVertical​

test bool horizontalOfOneVertical()
    = format(H([L("A"), V([L("B"), L("C")])]))
    == "A B
       '  C
       '";

test stairCase​

test bool stairCase()
    = format(H([L("A"), V([L("B"), H([L("C"), V([L("D"), H([L("E"), L("F")])])])])]))
    == "A B
       '  C D
       '    E F
       '";

test simpleTable​

test bool simpleTable() 
    = format(A([R([L("1"),L("2"),L("3")]),R([L("4"), L("5"), L("6")]),R([L("7"), L("8"), L("9")])]))
    == "1 2 3
       '4 5 6
       '7 8 9
       '";

test simpleAlignedTable​

test bool simpleAlignedTable() 
    = format(A([R([L("1"),L("2"),L("3")]),R([L("44"), L("55"), L("66")]),R([L("777"), L("888"), L("999")])], 
                columns=[l(),c(),r()]))
    == "1    2    3
       '44  55   66
       '777 888 999
       '";

test simpleAlignedTableDifferentAlignment​

test bool simpleAlignedTableDifferentAlignment() 
    = format(A([R([L("1"),L("2"),L("3")]),R([L("44"), L("55"), L("66")]),R([L("777"), L("888"), L("999")])], 
                columns=[r(),c(),l()]))
    == "  1  2  3  
       ' 44 55  66 
       '777 888 999
       '";

test WDtest​

test bool WDtest() {
    L1 = H([L("aap")]           , hs=0);
    L2 = H([WD([L1]), L("noot")], hs=0);
    L3 = H([WD([L2]), L("mies")], hs=0);

    return format(V([L1, L2, L3]))
        == "aap
           '   noot
           '       mies
           '";
}

test groupBy​

test bool groupBy() {
    lst  = [L("<i>") | i <- [0..10]];
    g1   = G(lst, op=H, gs=3);
    lst2 = [H([L("<i>"), L("<i+1>"), L("<i+2>")]) | i <- [0,3..7]] + [H([L("9")])];

    return format(V([g1])) == format(V(lst2));
}