Set paragraphs into lines: bidi, script runs, shaping, line breaking, visual order

text/layout.c puts the checked parts together: a paragraph's levels,
scripts resolved for Common and Inherited characters, break
opportunities, one shaping to measure, lines broken at the last
opportunity that fits (trailing spaces hang, and a line that shapes
wider than measured backs off), then per line L1, runs of one level and
one script shaped again, the runs in L2's order and their glyphs placed.
test-layout checks 30,000 random mixed-script paragraphs: lines cover
the text, mandatory breaks end lines, lines fit when they can, and
glyphs come in the order UAX #9 gives the characters. vega-symbols
paragraph draws a layout through the symbol file's glyphs.

6 files changed, 587 insertions, 5 deletions

diff --git a/Makefile b/Makefile
index 860f48e..af7b522 100644
--- a/Makefile
+++ b/Makefile
@@ -48,9 +48,9 @@ HARFBUZZ_LIBS ?= $(shell pkg-config --libs harfbuzz)
 # Drawing them on the GPU takes OpenGL ES 3.1 through EGL.
 GL_LIBS ?= $(shell pkg-config --libs egl glesv2)
 SYMBOLS = symbols/symbols.c symbols/symbols-gl.c
-SHAPE = text/shape.c text/unicode-data.c
+SHAPE = text/shape.c text/layout.c text/bidi.c text/linebreak.c text/unicode-data.c
 $(BUILD)/vega-symbols: symbols/symbols-tool.c $(SYMBOLS) symbols/symbols.h symbols/symbols-gl.h $(SHAPE) text/shape-build.c \
-		text/shape.h text/shape-build.h text/text.h | $(BUILD)
+		text/shape.h text/shape-build.h text/layout.h text/text.h | $(BUILD)
 	$(CC) $(CPPFLAGS) $(CFLAGS) $(FREETYPE_CFLAGS) $(HARFBUZZ_CFLAGS) -Itext symbols/symbols-tool.c $(SYMBOLS) $(SHAPE) \
 		text/shape-build.c $(LDFLAGS) $(FREETYPE_LIBS) $(HARFBUZZ_LIBS) $(GL_LIBS) -lm $(LDLIBS) -o $@
 
@@ -58,6 +58,11 @@ TEXT = text/bidi.c text/normalize.c text/linebreak.c text/grapheme.c text/word.c
 $(BUILD)/test-text: text/test-text.c $(TEXT) text/text.h | $(BUILD)
 	$(CC) $(CPPFLAGS) $(CFLAGS) -Itext text/test-text.c $(TEXT) $(LDFLAGS) $(LDLIBS) -o $@
 
+LAYOUT = text/layout.c text/shape.c text/bidi.c text/linebreak.c text/unicode-data.c
+$(BUILD)/test-layout: text/test-layout.c $(LAYOUT) text/layout.h text/shape.h text/text.h symbols/symbols.c \
+		symbols/symbols.h | $(BUILD)
+	$(CC) $(CPPFLAGS) $(CFLAGS) -Itext -Isymbols text/test-layout.c $(LAYOUT) symbols/symbols.c $(LDFLAGS) -lm $(LDLIBS) -o $@
+
 # Unicode's conformance tests, where the UCD is installed (Debian: unicode-data);
 # and shaping, where DejaVu Sans is: the build refuses a file whose shaping
 # differs from HarfBuzz's on random runs of Latin, Greek, Cyrillic, Hebrew,
@@ -65,11 +70,11 @@ $(BUILD)/test-text: text/test-text.c $(TEXT) text/text.h | $(BUILD)
 UCD ?= /usr/share/unicode
 SHAPED_FONT ?= /usr/share/fonts/truetype/dejavu/DejaVuSans.ttf
 SHAPED_CODES = 0x20-0x7e,0xa0-0x24f,0x300-0x36f,0x370-0x3ff,0x400-0x4ff,0x591-0x5f4,0x600-0x6ff,0x2000-0x206f
-check: $(BUILD)/vega $(BUILD)/vega-symbols $(BUILD)/vega-surface.so $(BUILD)/test-text
+check: $(BUILD)/vega $(BUILD)/vega-symbols $(BUILD)/vega-surface.so $(BUILD)/test-text $(BUILD)/test-layout
 	if [ -f $(UCD)/BidiTest.txt ]; then $(BUILD)/test-text $(UCD); else echo "no UCD at $(UCD): text tests skipped"; fi
 	if [ -f $(SHAPED_FONT) ]; then $(BUILD)/vega-symbols build --font $(SHAPED_FONT) --codes $(SHAPED_CODES) \
-		--shape Latn,Grek,Cyrl,Hebr,Arab,Zyyy --runs 5000 -o $(BUILD)/shaped.vsym; \
-		else echo "no $(SHAPED_FONT): shaping tests skipped"; fi
+		--shape Latn,Grek,Cyrl,Hebr,Arab,Zyyy --runs 5000 -o $(BUILD)/shaped.vsym && \
+		$(BUILD)/test-layout $(BUILD)/shaped.vsym; else echo "no $(SHAPED_FONT): shaping tests skipped"; fi
 	$(MAKE) -C $(AUP) build/aup
 	$(MAKE) -C $(PURE) build/pure-serve
 	python3 tests/check.py --vega $(BUILD)/vega --symbols $(BUILD)/vega-symbols --aup $(AUP)/build/aup --serve $(PURE)/build/pure-serve
diff --git a/docs/design/004-text.md b/docs/design/004-text.md
index b95a205..3e4dc99 100644
--- a/docs/design/004-text.md
+++ b/docs/design/004-text.md
@@ -123,3 +123,30 @@ advance, 오프셋 가운데 하나라도 다른 실행이 있으면 파일을 �
 - 기본·아랍·히브리 셰이퍼가 아닌 문자 체계: 인도계, 태국·라오, 한글 자모, 크메르, 미얀마, USE 문자 체계들, 시리아.
 - 이체 선택자(cmap 형식 14)는 싣지 않는다. 선택자는 숨기고 앞 글자는 기본 글리프로 둔다.
 
+## 비례폭 글줄
+
+[text/layout.c](../../text/layout.c)는 검증한 부품을 UAX #9 3.4절과 UAX #14가 말하는 순서로 잇는다.
+
+1. 문단의 수준(P2–I2). 제거된 문자는 앞 문자의 수준을 받는다.
+2. 문자마다 문자 체계. Common과 Inherited는 앞 문자의 것을 받고, 맨 앞이면 뒤에서 처음 나오는 것을 받는다.
+3. 줄 바꿈 기회와, 문단을 한 번 셰이핑해 잰 문자마다의 폭.
+4. 줄: 보이는 부분이 아직 들어가는 마지막 기회에서 바꾼다. 줄 끝의 공백은 줄 밖으로 걸린다. 들어가는 기회가 없으면 첫 기회에서
+   바꾼다. 줄로 다시 셰이핑하면 잰 것보다 넓을 수 있다(줄 끝 글자가 끝 꼴이 되는 아랍 문자). 그러면 앞 기회로 물러난다.
+5. 줄마다: 줄 끝에서 L1을 하고, 수준과 문자 체계가 같은 실행으로 나눠 다시 셰이핑하고(연결과 커닝이 줄과 함께 끝난다),
+   실행들을 L2 순서로 놓고, 글리프를 왼쪽부터 놓는다. 오른쪽에서 왼쪽으로 쓰는 문단의 줄은 오른쪽 끝에 맞춘다.
+
+정답인 참조 구현이 없으므로(브라우저마다 다르다), [text/test-layout.c](../../text/test-layout.c)는 부품이 약속하는 것을 확인한다.
+무작위 문단(라틴·아랍·히브리 낱말, 부호, 숫자, 괄호, 방향 표시, 줄 구분자)을 무작위 폭으로 짠다. 그리고 다음을 본다.
+
+- 줄이 문단을 순서대로 빈틈없이 덮는다.
+- 필수 줄 바꿈마다 줄이 끝난다.
+- 안에서 바꿀 기회가 있는 줄은 폭을 넘지 않는다.
+- 글리프의 클러스터가 자기 줄 안에 있다.
+- 글리프가 `vega_bidi_order`(줄 끝의 L1 뒤)가 문자를 놓는 순서대로 놓인다.
+
+3만 문단(565만 문자, 22.9만 줄)에서 어긋남이 없다. 문자당 776 ns다(재기 위한 셰이핑과 줄마다의 셰이핑 두 번, 양방향, 줄 바꿈
+포함).
+
+`vega-symbols paragraph`는 문단을 짜서 심볼로 그린다. 라틴(ffi·fi·fj 합자, AVAWA 커닝), 아랍(연결, lam-alef, 부호,
+오른쪽 맞춤과 줄 사이의 순서), 히브리 부호, 섞인 문장(왼쪽에서 오른쪽 문장 안의 아랍 낱말과 괄호, 숫자)을 눈으로도 확인했다.
+
diff --git a/symbols/symbols-tool.c b/symbols/symbols-tool.c
index 765dd5c..0682c1c 100644
--- a/symbols/symbols-tool.c
+++ b/symbols/symbols-tool.c
@@ -8,6 +8,7 @@
  *   vega-symbols info OUT.vsym
  *   vega-symbols render OUT.vsym CODE PIXELS OUT.pgm
  *   vega-symbols gpu OUT.vsym --sizes 12,16,32,64 [--frames N] */
+#include "layout.h"
 #include "shape-build.h"
 #include "symbols-gl.h"
 #include "symbols.h"
@@ -1149,7 +1150,91 @@ static int shape_one(int argc, char **argv) {
     return 0;
 }
 
+/* UTF-8 (valid) to code points; how many. */
+static size_t decode_utf8(const char *text, uint32_t *out, size_t room) {
+    size_t n = 0;
+    for (const unsigned char *p = (const unsigned char *)text; *p && n < room;) {
+        uint32_t c = *p;
+        int more = c >= 0xF0 ? 3 : c >= 0xE0 ? 2 : c >= 0xC0 ? 1 : 0;
+        c &= more == 3 ? 0x07 : more == 2 ? 0x0F : more == 1 ? 0x1F : 0x7F;
+        for (++p; more-- > 0 && *p; ++p) c = c << 6 | (*p & 0x3F);
+        out[n++] = c;
+    }
+    return n;
+}
+
+/* Set text in lines at most width pixels wide and draw it: vega-symbols
+ * paragraph OUT.vsym PIXELS WIDTH OUT.pgm TEXT... (the texts are
+ * paragraphs, one after another). */
+static int paragraph(int argc, char **argv) {
+    if (argc < 7) fail("usage: vega-symbols paragraph OUT.vsym PIXELS WIDTH OUT.pgm TEXT...");
+    char *bytes, error[128];
+    VegaSymbols s = open_symbols(argv[2], &bytes);
+    VegaShaping shaping;
+    if (!s.shaping || !vega_shaping_open(&shaping, s.shaping, s.shaping_size, error, sizeof(error))) fail("no shaping");
+    double pixels = atof(argv[3]), per_unit = pixels / shaping.upem;
+    int width = atoi(argv[4]), margin = (int)pixels, line_height = (int)ceil((s.ascent - s.descent) * pixels / s.units);
+    int ascent = (int)ceil(s.ascent * pixels / s.units);
+    VegaShaper *shaper = vega_shaper_new();
+    VegaGlyphs *glyphs = vega_glyphs_open(&s, (float)(pixels / s.units));
+    VegaLayout layouts[16] = {0};
+    int paragraphs = argc - 6 < 16 ? argc - 6 : 16, height = 2 * margin;
+    for (int k = 0; k < paragraphs; ++k) {
+        uint32_t codes[4096];
+        size_t count = decode_utf8(argv[6 + k], codes, 4096);
+        if (!vega_layout(&layouts[k], shaper, &shaping, codes, count, VEGA_BIDI_AUTO, (int32_t)(width / per_unit)))
+            fail("cannot lay out");
+        height += (int)layouts[k].line_count * line_height + line_height / 2;
+    }
+    int total_width = width + 2 * margin;
+    unsigned char *image = malloc((size_t)total_width * (size_t)height);
+    memset(image, 255, (size_t)total_width * (size_t)height);
+    int top = margin;
+    for (int k = 0; k < paragraphs; ++k) {
+        const VegaLayout *l = &layouts[k];
+        for (size_t i = 0; i < l->line_count; ++i, top += line_height) {
+            const VegaLine *line = &l->lines[i];
+            int baseline = top + ascent;
+            for (size_t g = line->first; g < line->first + line->count; ++g) {
+                const VegaPlaced *placed = &l->glyphs[g];
+                const VegaBitmap *b = vega_glyph(glyphs, VEGA_GLYPH_SYMBOLS + placed->glyph);
+                if (!b) continue;
+                int pen_x = margin + (int)lround(placed->x * per_unit), pen_y = baseline - (int)lround(placed->y * per_unit);
+                for (int y = 0; y < b->place.height; ++y)
+                    for (int x = 0; x < b->place.width; ++x) {
+                        int px = pen_x + b->place.left + x, py = pen_y - b->place.top + y;
+                        if (px < 0 || py < 0 || px >= total_width || py >= height) continue;
+                        unsigned a = b->pixels[(size_t)y * (size_t)b->place.width + (size_t)x];
+                        unsigned char *out = &image[(size_t)py * (size_t)total_width + (size_t)px];
+                        *out = (unsigned char)(*out * (255 - a) / 255);
+                    }
+            }
+        }
+        top += line_height / 2;
+    }
+    FILE *f = fopen(argv[5], "wb");
+    if (!f) fail("cannot write the image");
+    fprintf(f, "P5\n%d %d\n255\n", total_width, height);
+    fwrite(image, 1, (size_t)total_width * (size_t)height, f);
+    fclose(f);
+    size_t lines = 0, glyph_count = 0;
+    for (int k = 0; k < paragraphs; ++k) {
+        lines += layouts[k].line_count;
+        glyph_count += layouts[k].glyph_count;
+        vega_layout_free(&layouts[k]);
+    }
+    printf("{\"paragraphs\":%d,\"lines\":%zu,\"glyphs\":%zu,\"width\":%d,\"height\":%d}\n", paragraphs, lines,
+           glyph_count, total_width, height);
+    free(image);
+    vega_glyphs_close(glyphs);
+    vega_shaper_free(shaper);
+    vega_shaping_close(&shaping);
+    free(bytes);
+    return 0;
+}
+
 int main(int argc, char **argv) {
+    if (argc > 1 && !strcmp(argv[1], "paragraph")) return paragraph(argc, argv);
     if (argc > 1 && !strcmp(argv[1], "shape")) return shape_one(argc, argv);
     if (argc > 1 && !strcmp(argv[1], "build")) return build(argc, argv);
     if (argc > 1 && !strcmp(argv[1], "shape-check")) return shape_check(argc, argv);
diff --git a/text/layout.c b/text/layout.c
new file mode 100644
index 0000000..dd4bd4d
--- /dev/null
+++ b/text/layout.c
@@ -0,0 +1,239 @@
+/* Paragraphs set into lines (text/layout.h). The parts are the ones Unicode
+ * and HarfBuzz check (bidi.c, linebreak.c, shape.c); this puts them
+ * together as UAX #9 section 3.4 and UAX #14 describe:
+ *   1. levels for the paragraph (P2 to I2), each removed character at the
+ *      level of the one before it;
+ *   2. a script for each character, Common and Inherited ones taking the
+ *      one before them (at the start, the first after);
+ *   3. break opportunities, and one shaping of the paragraph to measure it;
+ *   4. lines: the last opportunity where what shows still fits (spaces at a
+ *      line's end hang past it), or the first when none does;
+ *   5. each line: L1 at its end, runs of one level and one script shaped
+ *      again (so joining and kerning end with the line), the runs in L2's
+ *      order, the glyphs placed left to right. */
+#include "layout.h"
+#include "text.h"
+#include <stdlib.h>
+#include <string.h>
+
+typedef struct { size_t start, end; uint8_t level; VegaScript script; } Run;
+
+static bool grow(void **array, size_t *allocated, size_t need, size_t size) {
+    if (need <= *allocated) return true;
+    size_t n = *allocated ? *allocated : 16;
+    while (n < need) n *= 2;
+    void *grown = realloc(*array, n * size);
+    if (!grown) return false;
+    *array = grown;
+    *allocated = n;
+    return true;
+}
+
+static bool isolate_control(VegaBidiClass c) {
+    return c == VEGA_BIDI_LRI || c == VEGA_BIDI_RLI || c == VEGA_BIDI_FSI || c == VEGA_BIDI_PDI;
+}
+static bool removed(VegaBidiClass c) {
+    return c == VEGA_BIDI_BN || c == VEGA_BIDI_LRE || c == VEGA_BIDI_RLE || c == VEGA_BIDI_LRO || c == VEGA_BIDI_RLO ||
+           c == VEGA_BIDI_PDF;
+}
+
+/* Shape [r->start, r->end) and add its glyphs at *pen. */
+static bool shape_run(VegaLayout *l, VegaShaper *shaper, const VegaShaping *s, const uint32_t *codes, const Run *r,
+                      int32_t *pen) {
+    const VegaShaped *g;
+    long n = vega_shape(shaper, s, codes + r->start, r->end - r->start, vega_script_code(r->script),
+                        r->level & 1 ? VEGA_SHAPE_RTL : VEGA_SHAPE_LTR, &g);
+    if (n < 0 || !grow((void **)&l->glyphs, &l->glyphs_allocated, l->glyph_count + (size_t)n, sizeof(VegaPlaced)))
+        return false;
+    for (long k = 0; k < n; ++k) {
+        l->glyphs[l->glyph_count++] = (VegaPlaced){g[k].glyph, (uint32_t)(r->start + g[k].cluster), *pen + g[k].x_offset,
+                                                   g[k].y_offset, g[k].x_advance};
+        *pen += g[k].x_advance;
+    }
+    return true;
+}
+
+/* Runs of one level and one script in [start, end). */
+static size_t itemize(const uint8_t *levels, const VegaScript *scripts, size_t start, size_t end, Run *out) {
+    size_t n = 0;
+    for (size_t i = start; i < end; ++i) {
+        if (n && out[n - 1].level == levels[i] && out[n - 1].script == scripts[i]) out[n - 1].end = i + 1;
+        else out[n++] = (Run){i, i + 1, levels[i], scripts[i]};
+    }
+    return n;
+}
+
+static bool set_line(VegaLayout *l, VegaShaper *shaper, const VegaShaping *s, const uint32_t *codes,
+                     const VegaBidiClass *classes, const uint8_t *levels, uint8_t *line_levels, const VegaScript *scripts,
+                     Run *runs, size_t *order, int paragraph, size_t start, size_t end, int32_t *pen_out,
+                     int32_t *hang_out);
+
+bool vega_layout(VegaLayout *l, VegaShaper *shaper, const VegaShaping *s, const uint32_t *codes, size_t count,
+                 int direction, int32_t width) {
+    l->line_count = l->glyph_count = 0;
+    l->width = 0;
+    l->level = direction == VEGA_BIDI_RTL;
+    if (!count) return true;
+    /* The work, in one block: classes, levels (the paragraph's, and a
+     * line's), scripts, breaks, each character's advance, runs and their
+     * order, and each line's end widths. */
+    size_t need = count * (sizeof(VegaBidiClass) + 2 + sizeof(VegaScript) + 1 + sizeof(int32_t) + sizeof(Run) +
+                           sizeof(size_t) + 2 * sizeof(int32_t)) + 64;
+    if (!grow(&l->work, &l->work_size, need, 1)) return false;
+    VegaBidiClass *classes = l->work;
+    int32_t *advance = (int32_t *)(classes + count), *totals = advance + count, *hanging = totals + count;
+    Run *runs = (Run *)(hanging + count);
+    size_t *order = (size_t *)(runs + count);
+    uint8_t *levels = (uint8_t *)(order + count), *line_levels = levels + count, *breaks = line_levels + count;
+    VegaScript *scripts = breaks + count + 1;
+
+    /* 1. Levels. */
+    for (size_t i = 0; i < count; ++i) classes[i] = vega_bidi_class(codes[i]);
+    int paragraph = vega_bidi_levels(classes, codes, count, direction, levels);
+    if (paragraph < 0) return false;
+    l->level = paragraph;
+    for (size_t i = 0; i < count; ++i)
+        if (levels[i] == VEGA_BIDI_REMOVED) levels[i] = (uint8_t)(i ? levels[i - 1] : paragraph);
+    /* 2. Scripts. */
+    VegaScript first = VEGA_SCRIPT_COMMON, last = 0;
+    for (size_t i = 0; i < count; ++i) {
+        VegaScript script = vega_script(codes[i]);
+        if (script > VEGA_SCRIPT_INHERITED) {
+            first = script;
+            break;
+        }
+    }
+    for (size_t i = 0; i < count; ++i) {
+        VegaScript script = vega_script(codes[i]);
+        if (script > VEGA_SCRIPT_INHERITED) last = script;
+        scripts[i] = script > VEGA_SCRIPT_INHERITED ? script : last ? last : first;
+    }
+    /* 3. Opportunities, and what each character takes. */
+    if (!vega_line_breaks(codes, count, breaks)) return false;
+    memset(advance, 0, count * sizeof(*advance));
+    size_t run_count = itemize(levels, scripts, 0, count, runs);
+    for (size_t r = 0; r < run_count; ++r) {
+        size_t before = l->glyph_count;
+        int32_t pen = 0;
+        if (!shape_run(l, shaper, s, codes, &runs[r], &pen)) return false;
+        for (size_t k = before; k < l->glyph_count; ++k) advance[l->glyphs[k].cluster] += l->glyphs[k].advance;
+        l->glyph_count = before;
+    }
+    /* 4. Lines, and 5. what each holds. */
+    int32_t widest = 0;
+    for (size_t start = 0; start < count;) {
+        int32_t sum = 0, trail = 0;
+        size_t candidate = 0, end = count;
+        for (size_t i = start; i < count; ++i) {
+            sum += advance[i];
+            trail = classes[i] == VEGA_BIDI_WS ? trail + advance[i] : 0;
+            uint8_t b = breaks[i + 1];
+            if (b == VEGA_BREAK_NONE) continue;
+            bool fits = !width || sum - trail <= width;
+            if (b == VEGA_BREAK_MANDATORY) {
+                end = fits || !candidate ? i + 1 : candidate;
+                break;
+            }
+            if (fits) candidate = i + 1;
+            else {
+                end = candidate ? candidate : i + 1;
+                break;
+            }
+        }
+        size_t first = l->glyph_count;
+        int32_t pen, hang;
+        for (;;) {
+            if (!set_line(l, shaper, s, codes, classes, levels, line_levels, scripts, runs, order, paragraph, start, end,
+                          &pen, &hang))
+                return false;
+            /* Shaped as a line, it may be wider than measured (a letter
+             * at its end takes its final form): then end at the opportunity
+             * before, if there is one. */
+            if (!width || pen - hang <= width) break;
+            size_t earlier = end - 1;
+            while (earlier > start && breaks[earlier] == VEGA_BREAK_NONE) --earlier;
+            if (earlier == start) break;
+            end = earlier;
+            l->glyph_count = first;
+        }
+        if (!grow((void **)&l->lines, &l->lines_allocated, l->line_count + 1, sizeof(VegaLine))) return false;
+        totals[l->line_count] = pen;
+        hanging[l->line_count] = hang;
+        l->lines[l->line_count++] = (VegaLine){first, l->glyph_count - first, start, end, 0, pen - hang};
+        if (pen - hang > widest) widest = pen - hang;
+        start = end;
+    }
+    /* Right to left, lines end at the paragraph's right edge. */
+    l->width = width ? width : widest;
+    if (paragraph & 1)
+        for (size_t i = 0; i < l->line_count; ++i) {
+            VegaLine *line = &l->lines[i];
+            line->left = l->width - totals[i];
+            for (size_t k = line->first; k < line->first + line->count; ++k) l->glyphs[k].x += line->left;
+            line->left += hanging[i];
+        }
+    return true;
+}
+
+/* Lay out [start, end) as one line: its glyphs added to the layout, how
+ * far they go (pen) and how much of that is spaces hanging at its end. */
+static bool set_line(VegaLayout *l, VegaShaper *shaper, const VegaShaping *s, const uint32_t *codes,
+                     const VegaBidiClass *classes, const uint8_t *levels, uint8_t *line_levels, const VegaScript *scripts,
+                     Run *runs, size_t *order, int paragraph, size_t start, size_t end, int32_t *pen_out,
+                     int32_t *hang_out) {
+    /* L1 at the line's end: separators, and the whitespace and isolate
+     * controls before them or at the end, go to the paragraph's level. */
+    memcpy(line_levels + start, levels + start, end - start);
+    for (size_t i = end, trailing = 1; i-- > start;) {
+        VegaBidiClass c = classes[i];
+        if (c == VEGA_BIDI_S || c == VEGA_BIDI_B) line_levels[i] = (uint8_t)paragraph, trailing = 1;
+        else if (c == VEGA_BIDI_WS || isolate_control(c) || removed(c)) {
+            if (trailing) line_levels[i] = (uint8_t)paragraph;
+        } else
+            trailing = 0;
+    }
+    size_t n = itemize(line_levels, scripts, start, end, runs);
+    /* L2 over the runs: from the highest level to the lowest odd one,
+     * reverse each stretch of runs at that level or higher. */
+    uint8_t highest = 0, lowest_odd = 0xff;
+    for (size_t r = 0; r < n; ++r) {
+        order[r] = r;
+        if (runs[r].level > highest) highest = runs[r].level;
+        if ((runs[r].level & 1) && runs[r].level < lowest_odd) lowest_odd = runs[r].level;
+    }
+    for (int level = highest; lowest_odd != 0xff && level >= lowest_odd; --level)
+        for (size_t k = 0; k < n;) {
+            if (runs[order[k]].level < level) {
+                ++k;
+                continue;
+            }
+            size_t stop = k;
+            while (stop < n && runs[order[stop]].level >= level) ++stop;
+            for (size_t a = k, z = stop - 1; a < z; ++a, --z) {
+                size_t swap = order[a];
+                order[a] = order[z];
+                order[z] = swap;
+            }
+            k = stop;
+        }
+    size_t first = l->glyph_count;
+    int32_t pen = 0;
+    for (size_t r = 0; r < n; ++r)
+        if (!shape_run(l, shaper, s, codes, &runs[order[r]], &pen)) return false;
+    /* The spaces at its end hang: they are not in its width. */
+    size_t shown = end;
+    while (shown > start && classes[shown - 1] == VEGA_BIDI_WS) --shown;
+    int32_t hang = 0;
+    for (size_t k = first; k < l->glyph_count; ++k)
+        if (l->glyphs[k].cluster >= shown) hang += l->glyphs[k].advance;
+    *pen_out = pen;
+    *hang_out = hang;
+    return true;
+}
+
+void vega_layout_free(VegaLayout *l) {
+    free(l->lines);
+    free(l->glyphs);
+    free(l->work);
+    *l = (VegaLayout){0};
+}
diff --git a/text/layout.h b/text/layout.h
new file mode 100644
index 0000000..9282536
--- /dev/null
+++ b/text/layout.h
@@ -0,0 +1,38 @@
+#ifndef VEGA_LAYOUT_H
+#define VEGA_LAYOUT_H
+#include "shape.h"
+
+/* A paragraph set into lines (docs/design/004-text.md): its bidi levels
+ * (UAX #9), lines broken where UAX #14 allows and they fit (spaces at a
+ * line's end hang past it), and each line's runs (one level, one script)
+ * shaped and put in visual order. Positions are in the font's units: x
+ * from the paragraph's left edge, y up from the line's baseline. */
+typedef struct {
+    uint32_t glyph;   /* the font's: its symbol is VEGA_GLYPH_SYMBOLS + glyph */
+    uint32_t cluster; /* the paragraph index of the first character it came from */
+    int32_t x, y, advance;
+} VegaPlaced;
+typedef struct {
+    size_t first, count; /* its glyphs, left to right */
+    size_t start, end;   /* the characters it holds, [start, end) */
+    int32_t left, width; /* where it starts and how far what shows goes */
+} VegaLine;
+typedef struct {
+    VegaLine *lines;
+    size_t line_count;
+    VegaPlaced *glyphs;
+    size_t glyph_count;
+    int level;           /* the paragraph's: odd is right to left, and its lines align right */
+    int32_t width;       /* the widest line's */
+    /* what setting the paragraph works in, kept for the next */
+    void *work;
+    size_t work_size, lines_allocated, glyphs_allocated;
+} VegaLayout;
+
+/* Set count characters in lines of at most width (0: no limit) with the
+ * font's shaping; direction is VEGA_BIDI_AUTO, _LTR or _RTL. The layout
+ * holds the result until it is set again; false without memory. */
+bool vega_layout(VegaLayout *, VegaShaper *, const VegaShaping *, const uint32_t *codes, size_t count, int direction,
+                 int32_t width);
+void vega_layout_free(VegaLayout *);
+#endif
diff --git a/text/test-layout.c b/text/test-layout.c
new file mode 100644
index 0000000..5282572
--- /dev/null
+++ b/text/test-layout.c
@@ -0,0 +1,188 @@
+/* Paragraph layout against what its parts promise (text/layout.h):
+ *     test-layout SHAPED.vsym [PARAGRAPHS]
+ * Random paragraphs of Latin, Arabic and Hebrew words (with marks, digits,
+ * brackets, directional marks and line feeds between), set at random
+ * widths. Every layout must: cover the paragraph with lines in order; end
+ * a line at every mandatory break; keep each line within the width unless
+ * it has no break opportunity inside; keep each glyph's cluster in its
+ * line; and put glyphs in the order UAX #9 puts the line's characters
+ * (vega_bidi_order, with L1 at the line's end). Prints one JSON line;
+ * exits 1 on a failure (the first few shown). */
+#define _POSIX_C_SOURCE 200809L
+#include "layout.h"
+#include "symbols.h"
+#include "text.h"
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <time.h>
+
+static unsigned failures;
+static void fail(size_t paragraph, const char *what) {
+    if (failures++ < 10) fprintf(stderr, "paragraph %zu: %s\n", paragraph, what);
+}
+
+static uint64_t state = 0x9E3779B97F4A7C15ULL;
+static uint32_t below(uint32_t n) {
+    state ^= state >> 12;
+    state ^= state << 25;
+    state ^= state >> 27;
+    return n ? (uint32_t)((state * 0x2545F4914F6CDD1DULL) >> 33) % n : 0;
+}
+
+typedef struct { uint32_t items[4096]; size_t count; } Pool;
+
+static bool whitespace(VegaBidiClass c) { return c == VEGA_BIDI_WS; }
+static bool trailing_kind(VegaBidiClass c) {
+    return c == VEGA_BIDI_WS || c == VEGA_BIDI_LRI || c == VEGA_BIDI_RLI || c == VEGA_BIDI_FSI || c == VEGA_BIDI_PDI ||
+           c == VEGA_BIDI_BN || c == VEGA_BIDI_LRE || c == VEGA_BIDI_RLE || c == VEGA_BIDI_LRO || c == VEGA_BIDI_RLO ||
+           c == VEGA_BIDI_PDF;
+}
+
+int main(int argc, char **argv) {
+    if (argc < 2) {
+        fprintf(stderr, "usage: test-layout SHAPED.vsym [PARAGRAPHS]\n");
+        return 2;
+    }
+    size_t paragraphs = argc > 2 ? strtoul(argv[2], NULL, 10) : 3000;
+    FILE *f = fopen(argv[1], "rb");
+    if (!f) { perror(argv[1]); return 2; }
+    fseek(f, 0, SEEK_END);
+    size_t size = (size_t)ftell(f);
+    fseek(f, 0, SEEK_SET);
+    unsigned char *bytes = malloc(size);
+    if (!bytes || fread(bytes, 1, size, f) != size) return 2;
+    fclose(f);
+    char error[128];
+    VegaSymbols symbols;
+    VegaShaping shaping;
+    if (!vega_symbols_open(&symbols, bytes, size, error, sizeof(error)) || !symbols.shaping ||
+        !vega_shaping_open(&shaping, symbols.shaping, symbols.shaping_size, error, sizeof(error))) {
+        fprintf(stderr, "%s: %s\n", argv[1], symbols.shaping ? error : "no shaping");
+        return 2;
+    }
+    /* Words from each script's letters (marks after some), and what goes
+     * between them. */
+    static Pool latin, arabic, hebrew, marks_latin, marks_arabic, marks_hebrew;
+    for (uint32_t i = 0; i < symbols.symbols; ++i) {
+        uint32_t code = vega_symbol_at(&symbols, i).code;
+        if (code >= VEGA_GLYPH_SYMBOLS) continue;
+        VegaScript script = vega_script(code);
+        VegaCategory c = vega_category(code);
+        bool mark = c == VEGA_MN || c == VEGA_MC;
+        bool letter = c >= VEGA_LU && c <= VEGA_LO;
+        Pool *p = NULL;
+        if (script == VEGA_SCRIPT_LATIN && letter) p = &latin;
+        else if (script == VEGA_SCRIPT_ARABIC && letter && code != 0x0640) p = &arabic;
+        else if (script == VEGA_SCRIPT_HEBREW && letter) p = &hebrew;
+        else if (mark && code >= 0x0300 && code <= 0x036F) p = &marks_latin;
+        else if (mark && code >= 0x064B && code <= 0x0652) p = &marks_arabic;
+        else if (mark && code >= 0x05B0 && code <= 0x05C2) p = &marks_hebrew;
+        if (p && p->count < 4096) p->items[p->count++] = code;
+    }
+    if (!latin.count || !arabic.count || !hebrew.count) {
+        fprintf(stderr, "%s: needs Latin, Arabic and Hebrew letters\n", argv[1]);
+        return 2;
+    }
+    static const uint32_t between[] = {' ', ' ', ' ', ' ', ',', '.', '(', ')', '[', ']', '-', '!', '?', 0x060C, 0x061F,
+                                       '1', '2', '3', 0x0661, 0x0662, 0x200E, 0x200F, 0x2028, 0x2014, 0x00A0};
+    VegaShaper *shaper = vega_shaper_new();
+    VegaLayout layout = {0};
+    size_t lines = 0, glyphs = 0, characters = 0;
+    double seconds = 0;
+    static uint32_t codes[2048];
+    static uint8_t breaks[2049], levels[2048], line_levels[2048];
+    static VegaBidiClass classes[2048];
+    static uint32_t order[2048], rank[2048];
+    for (size_t k = 0; k < paragraphs; ++k) {
+        size_t n = 0;
+        unsigned words = 1 + below(40);
+        for (unsigned w = 0; w < words && n < 1900; ++w) {
+            unsigned which = below(10);
+            const Pool *letters = which < 5 ? &latin : which < 8 ? &arabic : &hebrew;
+            const Pool *marks = which < 5 ? &marks_latin : which < 8 ? &marks_arabic : &marks_hebrew;
+            if (w) {
+                codes[n++] = between[below(sizeof(between) / sizeof(*between))];
+                if (below(3)) codes[n++] = ' ';
+            }
+            unsigned length = 1 + below(12);
+            for (unsigned c = 0; c < length; ++c) {
+                codes[n++] = letters->items[below((uint32_t)letters->count)];
+                if (marks->count && below(100) < (which < 5 ? 5u : 30u)) codes[n++] = marks->items[below((uint32_t)marks->count)];
+            }
+        }
+        int direction = below(3) == 0 ? VEGA_BIDI_AUTO : below(2) ? VEGA_BIDI_LTR : VEGA_BIDI_RTL;
+        int32_t width = below(5) == 0 ? 0 : (int32_t)(shaping.upem * (1 + below(30)));
+        struct timespec a, b;
+        clock_gettime(CLOCK_MONOTONIC, &a);
+        if (!vega_layout(&layout, shaper, &shaping, codes, n, direction, width)) {
+            fail(k, "no layout");
+            continue;
+        }
+        clock_gettime(CLOCK_MONOTONIC, &b);
+        seconds += (double)(b.tv_sec - a.tv_sec) + (double)(b.tv_nsec - a.tv_nsec) / 1e9;
+        lines += layout.line_count;
+        glyphs += layout.glyph_count;
+        characters += n;
+        vega_line_breaks(codes, n, breaks);
+        for (size_t i = 0; i < n; ++i) classes[i] = vega_bidi_class(codes[i]);
+        int paragraph = vega_bidi_levels(classes, codes, n, direction, levels);
+        size_t expect = 0;
+        for (size_t i = 0; i < layout.line_count; ++i) {
+            const VegaLine *line = &layout.lines[i];
+            if (line->start != expect || line->end <= line->start || line->end > n) {
+                fail(k, "lines do not cover the paragraph in order");
+                break;
+            }
+            expect = line->end;
+            for (size_t p = line->start + 1; p < line->end; ++p)
+                if (breaks[p] == VEGA_BREAK_MANDATORY) fail(k, "a line runs past a mandatory break");
+            if (width && line->width > width) {
+                bool inside = false;
+                for (size_t p = line->start + 1; p < line->end && !inside; ++p) {
+                    /* an opportunity after only spaces is no way to shorten the line */
+                    bool spaces_only = true;
+                    for (size_t q = p; q < line->end && spaces_only; ++q) spaces_only = whitespace(classes[q]);
+                    inside = breaks[p] != VEGA_BREAK_NONE && !spaces_only;
+                }
+                if (inside) fail(k, "a line wider than asked though it could break inside");
+            }
+            for (size_t g = line->first; g < line->first + line->count; ++g)
+                if (layout.glyphs[g].cluster < line->start || layout.glyphs[g].cluster >= line->end)
+                    fail(k, "a glyph's cluster is outside its line");
+            /* L1 at the line's end, then the characters' visual order. */
+            memcpy(line_levels, levels + line->start, line->end - line->start);
+            for (size_t i2 = line->end, trailing = 1; i2-- > line->start;) {
+                VegaBidiClass c = classes[i2];
+                if (c == VEGA_BIDI_S || c == VEGA_BIDI_B) line_levels[i2 - line->start] = (uint8_t)paragraph, trailing = 1;
+                else if (trailing_kind(c)) {
+                    if (trailing && line_levels[i2 - line->start] != VEGA_BIDI_REMOVED)
+                        line_levels[i2 - line->start] = (uint8_t)paragraph;
+                } else
+                    trailing = 0;
+            }
+            size_t shown = vega_bidi_order(line_levels, line->end - line->start, order);
+            for (size_t r = 0; r < line->end - line->start; ++r) rank[r] = UINT32_MAX;
+            for (size_t r = 0; r < shown; ++r) rank[order[r]] = (uint32_t)r;
+            uint32_t last = 0;
+            for (size_t g = line->first; g < line->first + line->count; ++g) {
+                uint32_t r = rank[layout.glyphs[g].cluster - line->start];
+                if (r == UINT32_MAX) continue;
+                if (r < last) {
+                    fail(k, "glyphs out of the characters' visual order");
+                    break;
+                }
+                last = r;
+            }
+        }
+        if (expect != n) fail(k, "lines end before the paragraph does");
+    }
+    printf("{\"paragraphs\":%zu,\"characters\":%zu,\"lines\":%zu,\"glyphs\":%zu,\"ns_per_character\":%.1f,"
+           "\"failures\":%u}\n",
+           paragraphs, characters, lines, glyphs, characters ? 1e9 * seconds / (double)characters : 0, failures);
+    vega_layout_free(&layout);
+    vega_shaper_free(shaper);
+    vega_shaping_close(&shaping);
+    free(bytes);
+    return failures ? 1 : 0;
+}