lang: Cache layout facts to avoid remeasuring

f1ee027f5e3e2296d55ff21225a2258c7474dd998048abf3375ca23deb004ec1
The formatter spent much of its time walking subtrees again: `hasTab`
and `hasBroken` visited every descendant of each row, and every box
nested in a box that already fit was measured again by `fits`.

`layout::new` now records the tab stop columns, the broken parts, and
whether a layout is plain, which is text and boxes without hard line
breaks. The renderer reads these facts, and skips the measure of a box
nested in a flat plain box, because its content is part of a line that
already fit. This takes 17% off the instructions of formatting
lower.rad, and the output of every checked source is unchanged.

Tabs, choices, broken parts and blank lines are not plain, since they
change columns or break lines after the measure.

Assisted-by: Claude:opus-5.5
Alexis Sellier committed ago 1 parent cac939be
lib/std/lang/layout.rad +74 -1
118 118
export record Layout: Copy {
119 119
    /// AST node that this layout presents, if any.
120 120
    source: ?*ast::Node,
121 121
    /// Layout element.
122 122
    item: Item,
123 +
    /// Set of the columns of the tab stops in this layout and in the boxes
124 +
    /// nested in it, as a bit mask. Set by [`new`].
125 +
    tabs: u32,
126 +
    /// Whether a renderer that measures the layout flat finds a broken part
127 +
    /// in it: a [`Item::Broken`] in it or in the boxes nested in it, or in the
128 +
    /// first alternative of a choice. Set by [`new`].
129 +
    broken: bool,
130 +
    /// Whether the layout is only text and boxes whose children are all on the
131 +
    /// line of the previous sibling when the box is flat. If a renderer puts
132 +
    /// such a layout flat on one line, so is every box in it. Set by [`new`].
133 +
    plain: bool,
123 134
}
124 135
125 136
/// Allocate a layout node with the given source node and item.
126 137
export fn new(
127 138
    a: &mut opaque alloc::Allocator, source: ?*ast::Node, item: Item
128 139
) -> *Layout throws (alloc::AllocError) {
129 140
    let mut nodes: *mut [Layout] = &mut [];
130 -
    try nodes.append(Layout { source, item }, a);
141 +
    try nodes.append(
142 +
        Layout {
143 +
            source,
144 +
            item,
145 +
            tabs: tabStops(item),
146 +
            broken: hasBroken(item),
147 +
            plain: isPlain(item),
148 +
        },
149 +
        a
150 +
    );
131 151
132 152
    return &nodes[0];
133 153
}
154 +
155 +
/// Whether an item holds a broken part, in the form that a renderer measures.
156 +
fn hasBroken(item: Item) -> bool {
157 +
    match item {
158 +
        case Item::Broken(_) => return true,
159 +
        case Item::Box(children) => {
160 +
            for child in children {
161 +
                if child.layout.broken {
162 +
                    return true;
163 +
                }
164 +
            }
165 +
            return false;
166 +
        }
167 +
        case Item::Choice(alts) => return alts[0].broken,
168 +
        else                    => return false,
169 +
    }
170 +
}
171 +
172 +
/// Whether an item is plain: see [`Layout::plain`].
173 +
fn isPlain(item: Item) -> bool {
174 +
    match item {
175 +
        case Item::Text { .. }, Item::BrokenText { .. } => return true,
176 +
        case Item::Box(children) => {
177 +
            for child in children {
178 +
                match child.placement {
179 +
                    case Placement::Line, Placement::Indent => return false,
180 +
                    else                                    => {}
181 +
                }
182 +
                if not child.layout.plain {
183 +
                    return false;
184 +
                }
185 +
            }
186 +
            return true;
187 +
        }
188 +
        else => return false,
189 +
    }
190 +
}
191 +
192 +
/// Columns of the tab stops of an item, as a bit mask. Only a stop and the
193 +
/// boxes that hold one count, as a renderer pads rows only by those.
194 +
fn tabStops(item: Item) -> u32 {
195 +
    match item {
196 +
        case Item::Tab(column) => return 1 << column,
197 +
        case Item::Box(children) => {
198 +
            let mut tabs: u32 = 0;
199 +
            for child in children {
200 +
                set tabs |= child.layout.tabs;
201 +
            }
202 +
            return tabs;
203 +
        }
204 +
        else => return 0,
205 +
    }
206 +
}
lib/std/lang/layout/tests.rad +47 -0
780 780
            at(Placement::Line, text(a, "cc,")),
781 781
        ]
782 782
    );
783 783
    try expectRender(root, 80, 4, "a,   // one\nbbb, // two\ncc,\n");
784 784
}
785 +
786 +
/// Test that a layout records the tab stops and broken parts in it, and
787 +
/// whether it is plain.
788 +
@test unsafe fn testLayoutFacts() throws (testing::TestError) {
789 +
    static STORAGE: [u8; 4096] = [0; 4096];
790 +
    let mut arena = alloc::new(&mut STORAGE[..]);
791 +
    let a: &mut opaque alloc::Allocator = &mut arena;
792 +
793 +
    let plain = call(a, ";");
794 +
    try testing::expect(plain.plain);
795 +
    try testing::expect(not plain.broken);
796 +
    try testing::expect(plain.tabs == 0);
797 +
798 +
    let stop = box(a, &[at(none(), text(a, "a")), at(none(), tab(a, 1))]);
799 +
    try testing::expect(not stop.plain);
800 +
    try testing::expect(stop.tabs == 2);
801 +
802 +
    let lines = box(a, &[at(none(), text(a, "a")), at(Placement::Line, text(a, "b"))]);
803 +
    try testing::expect(not lines.plain);
804 +
805 +
    let opened = box(a, &[at(none(), broken(a, plain))]);
806 +
    try testing::expect(opened.broken);
807 +
    try testing::expect(not opened.plain);
808 +
    try testing::expect(not box(a, &[at(none(), choice(a, &[plain, opened]))]).broken);
809 +
    try testing::expect(box(a, &[at(none(), choice(a, &[opened, plain]))]).broken);
810 +
}
811 +
812 +
/// Test that boxes nested in a plain box that fits are flat, and that a box
813 +
/// nested in a plain box that does not fit is measured on its own.
814 +
@test unsafe fn testNestedPlainBoxes() throws (testing::TestError) {
815 +
    static STORAGE: [u8; 8192] = [0; 8192];
816 +
    let mut arena = alloc::new(&mut STORAGE[..]);
817 +
    let a: &mut opaque alloc::Allocator = &mut arena;
818 +
    let outer = box(
819 +
        a,
820 +
        &[
821 +
            at(none(), text(a, "f(")),
822 +
            at(softIndent(), call(a, "")),
823 +
            at(soft(), text(a, ")")),
824 +
        ]
825 +
    );
826 +
    try expectRender(outer, 80, 2, "f(call(aaaa, bbbb, cccc))\n");
827 +
    try expectRender(outer, 24, 2, "f(\n  call(aaaa, bbbb, cccc)\n)\n");
828 +
    try expectRender(
829 +
        outer, 12, 2, "f(\n  call(\n    aaaa,\n    bbbb,\n    cccc\n  )\n)\n"
830 +
    );
831 +
}
lib/std/lang/layout/text.rad +27 -29
117 117
        spaces: 0,
118 118
        written: 0,
119 119
        tail: Tail::Code,
120 120
        pads: [0; super::CELL_COLUMNS],
121 121
    };
122 -
    renderLayout(&mut st, out, root, 0, emptySpan());
122 +
    renderLayout(&mut st, out, root, 0, emptySpan(), false);
123 123
    if st.written > 0 {
124 124
        out.write("\n");
125 125
    }
126 126
}
127 127
414 414
        }
415 415
    }
416 416
}
417 417
418 418
/// Render a layout whose box indentation is `indent`. `rest` describes the
419 -
/// content that follows the layout.
419 +
/// content that follows the layout. `inFlat` is set if the layout is in a plain
420 +
/// box that is flat, so a box in it is flat without a measure, and `rest` is
421 +
/// not used.
420 422
fn renderLayout(
421 423
    st: &mut State,
422 424
    out: &mut opaque sexpr::Output,
423 425
    layout: *super::Layout,
424 426
    indent: u32,
425 -
    rest: Span
427 +
    rest: Span,
428 +
    inFlat: bool
426 429
) {
427 430
    match layout.item {
428 431
        case super::Item::Text { text, role }                   => writeText(st, out, text, role),
429 432
        case super::Item::Blank, super::Item::BrokenText { .. } => {}
430 433
        case super::Item::Box(children) => {
431 -
            let mode = Mode::Flat
432 -
                if fits(layout, st.options.width, st.col, st.tail, rest)
433 -
                else Mode::Broken;
434 -
            renderChildren(st, out, children, mode, indent, rest);
434 +
            let flat = inFlat
435 +
                or fits(layout, st.options.width, st.col, st.tail, rest);
436 +
            let mode = Mode::Flat if flat else Mode::Broken;
437 +
            renderChildren(
438 +
                st, out, children, mode, indent, rest, flat and layout.plain
439 +
            );
435 440
        }
436 441
        case super::Item::Broken(inner) =>
437 442
            renderChildren(
438 -
                st, out, brokenChildren(inner), Mode::Broken, indent, rest
443 +
                st, out, brokenChildren(inner), Mode::Broken, indent, rest, false
439 444
            ),
440 445
        case super::Item::Tab(column) => {
441 446
            let pad = st.pads[column];
442 447
            set st.pads[column] = 0;
443 448
            set st.spaces += pad;
449 454
                if fitsAlternative(alt, st, indent, rest) {
450 455
                    set pick = alt;
451 456
                    break;
452 457
                }
453 458
            }
454 -
            renderLayout(st, out, pick, indent, rest);
459 +
            renderLayout(st, out, pick, indent, rest, false);
455 460
        }
456 461
    }
457 462
}
458 463
459 464
/// Indentation level of a child that starts a line in a box with the given
507 512
    return end;
508 513
}
509 514
510 515
/// Whether a layout holds the tab stop of `column`.
511 516
fn hasTab(layout: *super::Layout, column: u32) -> bool {
512 -
    match layout.item {
513 -
        case super::Item::Tab(found) => return found == column,
514 -
        case super::Item::Box(children) => {
515 -
            for child in children {
516 -
                if hasTab(child.layout, column) {
517 -
                    return true;
518 -
                }
519 -
            }
520 -
            return false;
521 -
        }
522 -
        else => return false,
523 -
    }
517 +
    return (layout.tabs & (1 << column)) <> 0;
524 518
}
525 519
526 520
/// Whether the row `from..end` has the tab stop of `column`.
527 521
fn rowHasTab(
528 522
    children: *[super::Child], from: u32, end: u32, column: u32
761 755
    st: &mut State,
762 756
    out: &mut opaque sexpr::Output,
763 757
    children: *[super::Child],
764 758
    mode: Mode,
765 759
    indent: u32,
766 -
    rest: Span
760 +
    rest: Span,
761 +
    inFlat: bool
767 762
) {
768 763
    let mut runs =
769 764
        [
770 765
            Run { end: 0, target: 0, aligned: false }; super::CELL_COLUMNS
771 766
        ];
779 774
                }
780 775
            }
781 776
            case super::Item::Text { .. }, super::Item::Blank => {
782 777
                let level = place(st, child.placement, mode, indent);
783 778
                padRow(st, children, i, mode, indent, &mut runs[..]);
784 -
                renderLayout(st, out, child.layout, level, emptySpan());
779 +
                renderLayout(st, out, child.layout, level, emptySpan(), inFlat);
785 780
            }
786 781
            else => {
787 782
                let level = place(st, child.placement, mode, indent);
788 783
                padRow(st, children, i, mode, indent, &mut runs[..]);
789 -
                let mut next = measureChildren(
790 -
                    children, i + 1, mode, Mode::Broken, st.options.width
791 -
                );
792 -
                if next.status == Status::Open {
793 -
                    set next = join(next, 0, rest, st.options.width);
784 +
                let mut next = emptySpan();
785 +
                if not inFlat {
786 +
                    set next = measureChildren(
787 +
                        children, i + 1, mode, Mode::Broken, st.options.width
788 +
                    );
789 +
                    if next.status == Status::Open {
790 +
                        set next = join(next, 0, rest, st.options.width);
791 +
                    }
794 792
                }
795 -
                renderLayout(st, out, child.layout, level, next);
793 +
                renderLayout(st, out, child.layout, level, next, inFlat);
796 794
            }
797 795
        }
798 796
    }
799 797
}
lib/std/lang/pretty.rad +1 -13
1462 1462
}
1463 1463
1464 1464
/// Whether a layout has a broken part, in the form that a renderer measures:
1465 1465
/// the first alternative of a choice.
1466 1466
fn hasBroken(l: *layout::Layout) -> bool {
1467 -
    match l.item {
1468 -
        case layout::Item::Broken(_) => return true,
1469 -
        case layout::Item::Box(children) => {
1470 -
            for child in children {
1471 -
                if hasBroken(child.layout) {
1472 -
                    return true;
1473 -
                }
1474 -
            }
1475 -
            return false;
1476 -
        }
1477 -
        case layout::Item::Choice(alts) => return hasBroken(alts[0]),
1478 -
        else                            => return false,
1479 -
    }
1467 +
    return l.broken;
1480 1468
}
1481 1469
1482 1470
/// Layout of the call `l`, a call with arguments that is the last argument of
1483 1471
/// another call, broken after its opening parenthesis.
1484 1472
///