lib/termtex/src/layout.zig
daab053ee43316e1809a84551d573ddd1e5bf3d2
1 const std = @import("std");
2 const ast = @import("ast.zig");
3 const operator = @import("operator.zig");
4
5 pub const Box = struct {
6 width: usize,
7 height: usize,
8 baseline: usize,
9 cells: []Cell,
10
11 pub fn at(self: Box, x: usize, y: usize) Cell {
12 return self.cells[y * self.width + x];
13 }
14
15 pub fn set(self: *Box, x: usize, y: usize, cell: Cell) void {
16 self.cells[y * self.width + x] = cell;
17 }
18 };
19
20 const Cell = []const u8;
21 const space = " ";
22
23 pub fn layout(arena: std.mem.Allocator, expr: *const ast.Expr) std.mem.Allocator.Error!Box {
24 return switch (expr.*) {
25 .row => |items| layoutRow(arena, items),
26 .text => |value| textBox(arena, value),
27 .operator => |value| layout(arena, value.body),
28 .space => |value| layoutSpace(arena, value),
29 .fraction => |value| layoutFraction(arena, value),
30 .sqrt => |value| layoutSqrt(arena, value),
31 .scripts => |value| layoutScripts(arena, value),
32 .accent => |value| layoutAccent(arena, value),
33 .grid => |value| layoutGrid(arena, value),
34 .annotation => |value| layoutAnnotation(arena, value),
35 .delimited => |value| layoutDelimited(arena, value),
36 };
37 }
38
39 pub fn rows(arena: std.mem.Allocator, value: Box) std.mem.Allocator.Error![]const []const u8 {
40 const out = try arena.alloc([]const u8, value.height);
41 for (0..value.height) |y| {
42 var end = value.width;
43 while (end > 0 and std.mem.eql(u8, value.at(end - 1, y), space)) end -= 1;
44 var line: std.ArrayListUnmanaged(u8) = .empty;
45 for (0..end) |x| try line.appendSlice(arena, value.at(x, y));
46 out[y] = try line.toOwnedSlice(arena);
47 }
48 return out;
49 }
50
51 fn layoutRow(arena: std.mem.Allocator, items: []const *ast.Expr) std.mem.Allocator.Error!Box {
52 if (items.len == 0) return makeBox(arena, 0, 1, 0);
53 const children = try arena.alloc(Box, items.len);
54 var width: usize = 0;
55 var baseline: usize = 0;
56 var descent: usize = 0;
57 for (items, 0..) |item, index| {
58 children[index] = try layout(arena, item);
59 width += children[index].width;
60 baseline = @max(baseline, children[index].baseline);
61 descent = @max(descent, children[index].height - children[index].baseline - 1);
62 }
63 var out = try makeBox(arena, width, baseline + descent + 1, baseline);
64 var x: usize = 0;
65 for (children) |child| {
66 putBox(&out, x, baseline - child.baseline, child);
67 x += child.width;
68 }
69 return out;
70 }
71
72 fn layoutSpace(arena: std.mem.Allocator, value: ast.Space) std.mem.Allocator.Error!Box {
73 return makeBox(arena, spaceCells(value), 1, 0);
74 }
75
76 fn layoutFraction(arena: std.mem.Allocator, value: ast.Fraction) std.mem.Allocator.Error!Box {
77 const numerator = try layout(arena, value.numerator);
78 const denominator = try layout(arena, value.denominator);
79 const width = @max(numerator.width, denominator.width) + 2;
80 var out = try makeBox(arena, width, numerator.height + denominator.height + 1, numerator.height);
81 putBox(&out, centered(width, numerator.width), 0, numerator);
82 for (0..width) |x| out.set(x, numerator.height, "─");
83 putBox(&out, centered(width, denominator.width), numerator.height + 1, denominator);
84 return out;
85 }
86
87 fn layoutSqrt(arena: std.mem.Allocator, value: ast.Radical) std.mem.Allocator.Error!Box {
88 const body = try layout(arena, value.body);
89 const index = if (value.index) |expr| try layout(arena, expr) else null;
90 const prefix = if (index) |idx| @max(idx.width, @as(usize, 1)) else 1;
91 const height = body.height + 1;
92 var out = try makeBox(arena, prefix + body.width + 1, height, body.baseline + 1);
93 if (index) |idx| putBox(&out, prefix - idx.width, 0, idx);
94 out.set(prefix - 1, out.baseline, "√");
95 for (0..body.width + 1) |x| out.set(prefix + x, 0, "─");
96 putBox(&out, prefix + 1, 1, body);
97 return out;
98 }
99
100 fn layoutScripts(arena: std.mem.Allocator, value: ast.Scripts) std.mem.Allocator.Error!Box {
101 if (operator.limitsBase(value.base)) return layoutLimits(arena, value);
102 const base = try layout(arena, value.base);
103 const sup = if (value.sup) |expr| try layout(arena, expr) else null;
104 const sub = if (value.sub) |expr| try layout(arena, expr) else null;
105 const script_width = @max(if (sup) |box| box.width else 0, if (sub) |box| box.width else 0);
106 const top = if (sup) |box| box.height else 0;
107 const bottom = if (sub) |box| box.height else 0;
108 var out = try makeBox(arena, base.width + script_width, top + base.height + bottom, top + base.baseline);
109 if (sup) |box| putBox(&out, base.width, 0, box);
110 putBox(&out, 0, top, base);
111 if (sub) |box| putBox(&out, base.width, top + base.height, box);
112 return out;
113 }
114
115 fn layoutLimits(arena: std.mem.Allocator, value: ast.Scripts) std.mem.Allocator.Error!Box {
116 const base = try layout(arena, value.base);
117 const sup = if (value.sup) |expr| try layout(arena, expr) else null;
118 const sub = if (value.sub) |expr| try layout(arena, expr) else null;
119 const width = @max(base.width, @max(if (sup) |box| box.width else 0, if (sub) |box| box.width else 0));
120 const top = if (sup) |box| box.height else 0;
121 const bottom = if (sub) |box| box.height else 0;
122 var out = try makeBox(arena, width, top + base.height + bottom, top + base.baseline);
123 if (sup) |box| putBox(&out, centered(width, box.width), 0, box);
124 putBox(&out, centered(width, base.width), top, base);
125 if (sub) |box| putBox(&out, centered(width, box.width), top + base.height, box);
126 return out;
127 }
128
129 fn layoutAccent(arena: std.mem.Allocator, value: ast.Accent) std.mem.Allocator.Error!Box {
130 const body = try layout(arena, value.body);
131 if (value.mark == .underline) {
132 var out = try makeBox(arena, body.width, body.height + 1, body.baseline);
133 putBox(&out, 0, 0, body);
134 for (0..body.width) |x| out.set(x, body.height, "─");
135 return out;
136 }
137 var out = try makeBox(arena, body.width, body.height + 1, body.baseline + 1);
138 if (body.width != 0) {
139 switch (value.mark) {
140 .bar => for (0..body.width) |x| out.set(x, 0, "─"),
141 .hat => out.set(centered(body.width, 1), 0, "^"),
142 .vec => out.set(centered(body.width, 1), 0, "→"),
143 .dot => out.set(centered(body.width, 1), 0, "˙"),
144 .underline => unreachable,
145 .tilde => out.set(centered(body.width, 1), 0, "~"),
146 .check => out.set(centered(body.width, 1), 0, "ˇ"),
147 .breve => out.set(centered(body.width, 1), 0, "˘"),
148 .ddot => out.set(centered(body.width, 1), 0, "¨"),
149 .acute => out.set(centered(body.width, 1), 0, "´"),
150 .grave => out.set(centered(body.width, 1), 0, "`"),
151 .ring => out.set(centered(body.width, 1), 0, "˚"),
152 .overleft => out.set(centered(body.width, 1), 0, "←"),
153 .overleftright => out.set(centered(body.width, 1), 0, "↔"),
154 }
155 }
156 putBox(&out, 0, 1, body);
157 return out;
158 }
159
160 fn layoutAnnotation(arena: std.mem.Allocator, value: ast.Annotation) std.mem.Allocator.Error!Box {
161 return switch (value.kind) {
162 .plain => layoutStack(arena, value),
163 .overbrace => layoutBraceAnnotation(arena, value.base, .over),
164 .underbrace => layoutBraceAnnotation(arena, value.base, .under),
165 .boxed => layoutBoxed(arena, value.base),
166 };
167 }
168
169 const BraceSide = enum {
170 over,
171 under,
172 };
173
174 fn layoutStack(arena: std.mem.Allocator, value: ast.Annotation) std.mem.Allocator.Error!Box {
175 const base = try layout(arena, value.base);
176 const over = if (value.over) |expr| try layout(arena, expr) else null;
177 const under = if (value.under) |expr| try layout(arena, expr) else null;
178 const width = @max(base.width, @max(if (over) |box| box.width else 0, if (under) |box| box.width else 0));
179 const top = if (over) |box| box.height else 0;
180 const bottom = if (under) |box| box.height else 0;
181 var out = try makeBox(arena, width, top + base.height + bottom, top + base.baseline);
182 if (over) |box| putBox(&out, centered(width, box.width), 0, box);
183 putBox(&out, centered(width, base.width), top, base);
184 if (under) |box| putBox(&out, centered(width, box.width), top + base.height, box);
185 return out;
186 }
187
188 fn layoutBraceAnnotation(arena: std.mem.Allocator, body_expr: *ast.Expr, side: BraceSide) std.mem.Allocator.Error!Box {
189 const body = try layout(arena, body_expr);
190 var out = try makeBox(arena, body.width, body.height + 1, switch (side) {
191 .over => body.baseline + 1,
192 .under => body.baseline,
193 });
194 if (body.width != 0) {
195 switch (side) {
196 .over => for (0..body.width) |x| out.set(x, 0, "⏞"),
197 .under => for (0..body.width) |x| out.set(x, body.height, "⏟"),
198 }
199 }
200 switch (side) {
201 .over => putBox(&out, 0, 1, body),
202 .under => putBox(&out, 0, 0, body),
203 }
204 return out;
205 }
206
207 fn layoutBoxed(arena: std.mem.Allocator, body_expr: *ast.Expr) std.mem.Allocator.Error!Box {
208 const body = try layout(arena, body_expr);
209 var out = try makeBox(arena, body.width + 4, body.height + 2, body.baseline + 1);
210 out.set(0, 0, "┌");
211 for (1..out.width - 1) |x| out.set(x, 0, "─");
212 out.set(out.width - 1, 0, "┐");
213 for (1..out.height - 1) |y| {
214 out.set(0, y, "│");
215 out.set(out.width - 1, y, "│");
216 }
217 out.set(0, out.height - 1, "└");
218 for (1..out.width - 1) |x| out.set(x, out.height - 1, "─");
219 out.set(out.width - 1, out.height - 1, "┘");
220 putBox(&out, 2, 1, body);
221 return out;
222 }
223
224 fn layoutDelimited(arena: std.mem.Allocator, value: ast.Delimited) std.mem.Allocator.Error!Box {
225 const body = try layout(arena, value.body);
226 const left = try layoutDelimiter(arena, value.left, body.height, body.baseline);
227 const right = try layoutDelimiter(arena, value.right, body.height, body.baseline);
228 var out = try makeBox(arena, left.width + body.width + right.width, body.height, body.baseline);
229 putBox(&out, 0, 0, left);
230 putBox(&out, left.width, 0, body);
231 putBox(&out, left.width + body.width, 0, right);
232 return out;
233 }
234
235 fn layoutDelimiter(
236 arena: std.mem.Allocator,
237 delimiter: ast.Delimiter,
238 height: usize,
239 baseline: usize,
240 ) std.mem.Allocator.Error!Box {
241 return switch (delimiter) {
242 .none => makeBox(arena, 0, height, baseline),
243 .shape => |shape| block: {
244 var out = try makeBox(arena, 1, height, baseline);
245 for (0..height) |y| out.set(0, y, delimiterShapeGlyph(shape, y, height));
246 break :block out;
247 },
248 .text => |value| block: {
249 const text = try textBox(arena, value);
250 var out = try makeBox(arena, text.width, height, baseline);
251 putBox(&out, 0, @min(baseline, height - 1), text);
252 break :block out;
253 },
254 };
255 }
256
257 fn layoutGrid(arena: std.mem.Allocator, value: ast.Grid) std.mem.Allocator.Error!Box {
258 if (value.rows.len == 0) return makeBox(arena, 0, 1, 0);
259 var columns: usize = 0;
260 for (value.rows) |row| columns = @max(columns, row.cells.len);
261 if (columns == 0) return makeBox(arena, 0, 1, 0);
262
263 const column_widths = try arena.alloc(usize, columns);
264 for (column_widths) |*width| width.* = 0;
265 const row_baselines = try arena.alloc(usize, value.rows.len);
266 const row_heights = try arena.alloc(usize, value.rows.len);
267 const boxes = try arena.alloc([]Box, value.rows.len);
268
269 for (value.rows, 0..) |row, row_index| {
270 boxes[row_index] = try arena.alloc(Box, row.cells.len);
271 var baseline: usize = 0;
272 var descent: usize = 0;
273 for (row.cells, 0..) |cell, column_index| {
274 const box = try layout(arena, cell);
275 boxes[row_index][column_index] = box;
276 column_widths[column_index] = @max(column_widths[column_index], box.width);
277 baseline = @max(baseline, box.baseline);
278 descent = @max(descent, box.height - box.baseline - 1);
279 }
280 row_baselines[row_index] = baseline;
281 row_heights[row_index] = baseline + descent + 1;
282 }
283
284 const gap: usize = if (columns > 1) 2 else 0;
285 var body_width: usize = gap * (columns - 1);
286 for (column_widths) |width| body_width += width;
287 var body_height: usize = 0;
288 for (row_heights) |height| body_height += height;
289
290 const left_width = if (leftFence(value.fence) != null) @as(usize, 1) else 0;
291 const right_width = if (rightFence(value.fence) != null) @as(usize, 1) else 0;
292 var out = try makeBox(arena, left_width + body_width + right_width, body_height, body_height / 2);
293 if (leftFence(value.fence)) |fence| drawFence(&out, 0, fence, .left);
294 if (rightFence(value.fence)) |fence| drawFence(&out, left_width + body_width, fence, .right);
295
296 var y: usize = 0;
297 for (value.rows, 0..) |row, row_index| {
298 var x = left_width;
299 for (0..columns) |column_index| {
300 if (column_index < row.cells.len) {
301 const box = boxes[row_index][column_index];
302 const offset = switch (value.alignment) {
303 .center => centered(column_widths[column_index], box.width),
304 .left => 0,
305 };
306 putBox(&out, x + offset, y + row_baselines[row_index] - box.baseline, box);
307 }
308 x += column_widths[column_index] + gap;
309 }
310 y += row_heights[row_index];
311 }
312 return out;
313 }
314
315 pub fn spaceCells(value: ast.Space) usize {
316 if (value.numerator <= 0) return 0;
317 const numerator: u64 = @intCast(value.numerator);
318 const denominator: u64 = value.denominator;
319 const cells: usize = @intCast(@divTrunc(numerator * 2 + denominator - 1, denominator));
320 return @max(@as(usize, 1), cells);
321 }
322
323 fn textBox(arena: std.mem.Allocator, value: []const u8) std.mem.Allocator.Error!Box {
324 var count: usize = 0;
325 var index: usize = 0;
326 while (index < value.len) {
327 const len = std.unicode.utf8ByteSequenceLength(value[index]) catch 1;
328 index += @min(len, value.len - index);
329 count += 1;
330 }
331 var out = try makeBox(arena, count, 1, 0);
332 index = 0;
333 var x: usize = 0;
334 while (index < value.len) : (x += 1) {
335 const len = std.unicode.utf8ByteSequenceLength(value[index]) catch 1;
336 const end = index + @min(len, value.len - index);
337 out.set(x, 0, value[index..end]);
338 index = end;
339 }
340 return out;
341 }
342
343 fn makeBox(arena: std.mem.Allocator, width: usize, height: usize, baseline: usize) std.mem.Allocator.Error!Box {
344 const cells = try arena.alloc(Cell, width * height);
345 for (cells) |*cell| cell.* = space;
346 return .{
347 .width = width,
348 .height = height,
349 .baseline = baseline,
350 .cells = cells,
351 };
352 }
353
354 fn putBox(out: *Box, x: usize, y: usize, child: Box) void {
355 for (0..child.height) |row| {
356 for (0..child.width) |col| {
357 out.set(x + col, y + row, child.at(col, row));
358 }
359 }
360 }
361
362 fn centered(width: usize, inner: usize) usize {
363 if (inner >= width) return 0;
364 return (width - inner) / 2;
365 }
366
367 const Fence = enum {
368 paren,
369 bracket,
370 brace,
371 bar,
372 double_bar,
373 };
374
375 const FenceSide = enum {
376 left,
377 right,
378 };
379
380 fn leftFence(fence: ast.GridFence) ?Fence {
381 return switch (fence) {
382 .none => null,
383 .paren => .paren,
384 .bracket => .bracket,
385 .brace => .brace,
386 .bar => .bar,
387 .double_bar => .double_bar,
388 .left_brace => .brace,
389 };
390 }
391
392 fn rightFence(fence: ast.GridFence) ?Fence {
393 return switch (fence) {
394 .none, .left_brace => null,
395 .paren => .paren,
396 .bracket => .bracket,
397 .brace => .brace,
398 .bar => .bar,
399 .double_bar => .double_bar,
400 };
401 }
402
403 fn drawFence(out: *Box, x: usize, fence: Fence, side: FenceSide) void {
404 for (0..out.height) |y| out.set(x, y, fenceGlyph(fence, side, y, out.height));
405 }
406
407 fn delimiterShapeGlyph(shape: ast.DelimiterShape, y: usize, height: usize) []const u8 {
408 return switch (shape) {
409 .left_paren => fenceGlyph(.paren, .left, y, height),
410 .right_paren => fenceGlyph(.paren, .right, y, height),
411 .left_bracket => fenceGlyph(.bracket, .left, y, height),
412 .right_bracket => fenceGlyph(.bracket, .right, y, height),
413 .left_brace => fenceGlyph(.brace, .left, y, height),
414 .right_brace => fenceGlyph(.brace, .right, y, height),
415 .bar => "|",
416 .double_bar => "‖",
417 .left_angle => "⟨",
418 .right_angle => "⟩",
419 .left_double_angle => "⟪",
420 .right_double_angle => "⟫",
421 .left_double_bracket => "⟦",
422 .right_double_bracket => "⟧",
423 .left_floor => if (height == 1 or y + 1 == height) "⌊" else "⎢",
424 .right_floor => if (height == 1 or y + 1 == height) "⌋" else "⎥",
425 .left_ceil => if (height == 1 or y == 0) "⌈" else "⎢",
426 .right_ceil => if (height == 1 or y == 0) "⌉" else "⎥",
427 };
428 }
429
430 fn fenceGlyph(fence: Fence, side: FenceSide, y: usize, height: usize) []const u8 {
431 return switch (fence) {
432 .bar => "|",
433 .double_bar => "‖",
434 .paren => if (height == 1)
435 switch (side) {
436 .left => "(",
437 .right => ")",
438 }
439 else if (y == 0)
440 switch (side) {
441 .left => "⎛",
442 .right => "⎞",
443 }
444 else if (y + 1 == height)
445 switch (side) {
446 .left => "⎝",
447 .right => "⎠",
448 }
449 else switch (side) {
450 .left => "⎜",
451 .right => "⎟",
452 },
453 .bracket => if (height == 1)
454 switch (side) {
455 .left => "[",
456 .right => "]",
457 }
458 else if (y == 0)
459 switch (side) {
460 .left => "⎡",
461 .right => "⎤",
462 }
463 else if (y + 1 == height)
464 switch (side) {
465 .left => "⎣",
466 .right => "⎦",
467 }
468 else switch (side) {
469 .left => "⎢",
470 .right => "⎥",
471 },
472 .brace => if (height == 1)
473 switch (side) {
474 .left => "{",
475 .right => "}",
476 }
477 else if (y == 0)
478 switch (side) {
479 .left => "⎧",
480 .right => "⎫",
481 }
482 else if (y + 1 == height)
483 switch (side) {
484 .left => "⎩",
485 .right => "⎭",
486 }
487 else if (y == height / 2)
488 switch (side) {
489 .left => "⎨",
490 .right => "⎬",
491 }
492 else switch (side) {
493 .left => "⎪",
494 .right => "⎪",
495 },
496 };
497 }