diff options
| author | Laurenz <laurmaedje@gmail.com> | 2024-10-27 19:04:55 +0100 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2024-10-27 18:04:55 +0000 |
| commit | be7cfc85d08c545abfac08098b7b33b4bd71f37e (patch) | |
| tree | f4137fa2aaa57babae1f7603a9b2ed7e688f43d8 /crates/typst-layout/src/grid | |
| parent | b8034a343831e8609aec2ec81eb7eeda57aa5d81 (diff) | |
Split out four new crates (#5302)
Diffstat (limited to 'crates/typst-layout/src/grid')
| -rw-r--r-- | crates/typst-layout/src/grid/cells.rs | 1349 | ||||
| -rw-r--r-- | crates/typst-layout/src/grid/layouter.rs | 1582 | ||||
| -rw-r--r-- | crates/typst-layout/src/grid/lines.rs | 1548 | ||||
| -rw-r--r-- | crates/typst-layout/src/grid/mod.rs | 416 | ||||
| -rw-r--r-- | crates/typst-layout/src/grid/repeated.rs | 192 | ||||
| -rw-r--r-- | crates/typst-layout/src/grid/rowspans.rs | 1217 |
6 files changed, 6304 insertions, 0 deletions
diff --git a/crates/typst-layout/src/grid/cells.rs b/crates/typst-layout/src/grid/cells.rs new file mode 100644 index 00000000..175e2183 --- /dev/null +++ b/crates/typst-layout/src/grid/cells.rs @@ -0,0 +1,1349 @@ +use std::num::NonZeroUsize; +use std::sync::Arc; + +use ecow::eco_format; +use typst_library::diag::{bail, At, Hint, HintedStrResult, HintedString, SourceResult}; +use typst_library::engine::Engine; +use typst_library::foundations::{Content, Smart, StyleChain}; +use typst_library::introspection::Locator; +use typst_library::layout::{ + Abs, Alignment, Axes, Celled, Fragment, Length, Regions, Rel, ResolvedCelled, Sides, + Sizing, +}; +use typst_library::visualize::{Paint, Stroke}; +use typst_syntax::Span; +use typst_utils::NonZeroExt; + +use super::{Footer, Header, Line, Repeatable}; + +/// Used for cell-like elements which are aware of their final properties in +/// the table, and may have property overrides. +pub trait ResolvableCell { + /// Resolves the cell's fields, given its coordinates and default grid-wide + /// fill, align, inset and stroke properties, plus the expected value of + /// the `breakable` field. + /// Returns a final Cell. + #[allow(clippy::too_many_arguments)] + fn resolve_cell<'a>( + self, + x: usize, + y: usize, + fill: &Option<Paint>, + align: Smart<Alignment>, + inset: Sides<Option<Rel<Length>>>, + stroke: Sides<Option<Option<Arc<Stroke<Abs>>>>>, + breakable: bool, + locator: Locator<'a>, + styles: StyleChain, + ) -> Cell<'a>; + + /// Returns this cell's column override. + fn x(&self, styles: StyleChain) -> Smart<usize>; + + /// Returns this cell's row override. + fn y(&self, styles: StyleChain) -> Smart<usize>; + + /// The amount of columns spanned by this cell. + fn colspan(&self, styles: StyleChain) -> NonZeroUsize; + + /// The amount of rows spanned by this cell. + fn rowspan(&self, styles: StyleChain) -> NonZeroUsize; + + /// The cell's span, for errors. + fn span(&self) -> Span; +} + +/// A grid item, possibly affected by automatic cell positioning. Can be either +/// a line or a cell. +pub enum ResolvableGridItem<T: ResolvableCell> { + /// A horizontal line in the grid. + HLine { + /// The row above which the horizontal line is drawn. + y: Smart<usize>, + start: usize, + end: Option<NonZeroUsize>, + stroke: Option<Arc<Stroke<Abs>>>, + /// The span of the corresponding line element. + span: Span, + /// The line's position. "before" here means on top of row `y`, while + /// "after" means below it. + position: LinePosition, + }, + /// A vertical line in the grid. + VLine { + /// The column before which the vertical line is drawn. + x: Smart<usize>, + start: usize, + end: Option<NonZeroUsize>, + stroke: Option<Arc<Stroke<Abs>>>, + /// The span of the corresponding line element. + span: Span, + /// The line's position. "before" here means to the left of column `x`, + /// while "after" means to its right (both considering LTR). + position: LinePosition, + }, + /// A cell in the grid. + Cell(T), +} + +/// Represents a cell in CellGrid, to be laid out by GridLayouter. +pub struct Cell<'a> { + /// The cell's body. + pub body: Content, + /// The cell's locator. + pub locator: Locator<'a>, + /// The cell's fill. + pub fill: Option<Paint>, + /// The amount of columns spanned by the cell. + pub colspan: NonZeroUsize, + /// The amount of rows spanned by the cell. + pub rowspan: NonZeroUsize, + /// The cell's stroke. + /// + /// We use an Arc to avoid unnecessary space usage when all sides are the + /// same, or when the strokes come from a common source. + pub stroke: Sides<Option<Arc<Stroke<Abs>>>>, + /// Which stroke sides were explicitly overridden by the cell, over the + /// grid's global stroke setting. + /// + /// This is used to define whether or not this cell's stroke sides should + /// have priority over adjacent cells' stroke sides, if those don't + /// override their own stroke properties (and thus have less priority when + /// defining with which stroke to draw grid lines around this cell). + pub stroke_overridden: Sides<bool>, + /// Whether rows spanned by this cell can be placed in different pages. + /// By default, a cell spanning only fixed-size rows is unbreakable, while + /// a cell spanning at least one `auto`-sized row is breakable. + pub breakable: bool, +} + +impl<'a> Cell<'a> { + /// Create a simple cell given its body and its locator. + pub fn new(body: Content, locator: Locator<'a>) -> Self { + Self { + body, + locator, + fill: None, + colspan: NonZeroUsize::ONE, + rowspan: NonZeroUsize::ONE, + stroke: Sides::splat(None), + stroke_overridden: Sides::splat(false), + breakable: true, + } + } + + /// Layout the cell into the given regions. + /// + /// The `disambiguator` indicates which instance of this cell this should be + /// layouted as. For normal cells, it is always `0`, but for headers and + /// footers, it indicates the index of the header/footer among all. See the + /// [`Locator`] docs for more details on the concepts behind this. + pub fn layout( + &self, + engine: &mut Engine, + disambiguator: usize, + styles: StyleChain, + regions: Regions, + ) -> SourceResult<Fragment> { + let mut locator = self.locator.relayout(); + if disambiguator > 0 { + locator = locator.split().next_inner(disambiguator as u128); + } + crate::layout_fragment(engine, &self.body, locator, styles, regions) + } +} + +/// Indicates whether the line should be drawn before or after the track with +/// its index. This is mostly only relevant when gutter is used, since, then, +/// the position after a track is not the same as before the next +/// non-gutter track. +#[derive(Copy, Clone, PartialEq, Eq)] +pub enum LinePosition { + /// The line should be drawn before its track (e.g. hline on top of a row). + Before, + /// The line should be drawn after its track (e.g. hline below a row). + After, +} + +/// A grid entry. +pub enum Entry<'a> { + /// An entry which holds a cell. + Cell(Cell<'a>), + /// An entry which is merged with another cell. + Merged { + /// The index of the cell this entry is merged with. + parent: usize, + }, +} + +impl<'a> Entry<'a> { + /// Obtains the cell inside this entry, if this is not a merged cell. + fn as_cell(&self) -> Option<&Cell<'a>> { + match self { + Self::Cell(cell) => Some(cell), + Self::Merged { .. } => None, + } + } +} + +/// Any grid child, which can be either a header or an item. +pub enum ResolvableGridChild<T: ResolvableCell, I> { + Header { repeat: bool, span: Span, items: I }, + Footer { repeat: bool, span: Span, items: I }, + Item(ResolvableGridItem<T>), +} + +/// A grid of cells, including the columns, rows, and cell data. +pub struct CellGrid<'a> { + /// The grid cells. + pub entries: Vec<Entry<'a>>, + /// The column tracks including gutter tracks. + pub cols: Vec<Sizing>, + /// The row tracks including gutter tracks. + pub rows: Vec<Sizing>, + /// The vertical lines before each column, or on the end border. + /// Gutter columns are not included. + /// Contains up to 'cols_without_gutter.len() + 1' vectors of lines. + pub vlines: Vec<Vec<Line>>, + /// The horizontal lines on top of each row, or on the bottom border. + /// Gutter rows are not included. + /// Contains up to 'rows_without_gutter.len() + 1' vectors of lines. + pub hlines: Vec<Vec<Line>>, + /// The repeatable header of this grid. + pub header: Option<Repeatable<Header>>, + /// The repeatable footer of this grid. + pub footer: Option<Repeatable<Footer>>, + /// Whether this grid has gutters. + pub has_gutter: bool, +} + +impl<'a> CellGrid<'a> { + /// Generates the cell grid, given the tracks and cells. + pub fn new( + tracks: Axes<&[Sizing]>, + gutter: Axes<&[Sizing]>, + cells: impl IntoIterator<Item = Cell<'a>>, + ) -> Self { + let entries = cells.into_iter().map(Entry::Cell).collect(); + Self::new_internal(tracks, gutter, vec![], vec![], None, None, entries) + } + + /// Resolves and positions all cells in the grid before creating it. + /// Allows them to keep track of their final properties and positions + /// and adjust their fields accordingly. + /// Cells must implement Clone as they will be owned. Additionally, they + /// must implement Default in order to fill positions in the grid which + /// weren't explicitly specified by the user with empty cells. + #[allow(clippy::too_many_arguments)] + pub fn resolve<T, C, I>( + tracks: Axes<&[Sizing]>, + gutter: Axes<&[Sizing]>, + locator: Locator<'a>, + children: C, + fill: &Celled<Option<Paint>>, + align: &Celled<Smart<Alignment>>, + inset: &Celled<Sides<Option<Rel<Length>>>>, + stroke: &ResolvedCelled<Sides<Option<Option<Arc<Stroke>>>>>, + engine: &mut Engine, + styles: StyleChain, + span: Span, + ) -> SourceResult<Self> + where + T: ResolvableCell + Default, + I: Iterator<Item = ResolvableGridItem<T>>, + C: IntoIterator<Item = ResolvableGridChild<T, I>>, + C::IntoIter: ExactSizeIterator, + { + let mut locator = locator.split(); + + // Number of content columns: Always at least one. + let c = tracks.x.len().max(1); + + // Lists of lines. + // Horizontal lines are only pushed later to be able to check for row + // validity, since the amount of rows isn't known until all items were + // analyzed in the for loop below. + // We keep their spans so we can report errors later. + // The additional boolean indicates whether the hline had an automatic + // 'y' index, and is used to change the index of hlines at the top of a + // header or footer. + let mut pending_hlines: Vec<(Span, Line, bool)> = vec![]; + + // For consistency, only push vertical lines later as well. + let mut pending_vlines: Vec<(Span, Line)> = vec![]; + let has_gutter = gutter.any(|tracks| !tracks.is_empty()); + + let mut header: Option<Header> = None; + let mut repeat_header = false; + + // Stores where the footer is supposed to end, its span, and the + // actual footer structure. + let mut footer: Option<(usize, Span, Footer)> = None; + let mut repeat_footer = false; + + // Resolves the breakability of a cell. Cells that span at least one + // auto-sized row or gutter are considered breakable. + let resolve_breakable = |y, rowspan| { + let auto = Sizing::Auto; + let zero = Sizing::Rel(Rel::zero()); + tracks + .y + .iter() + .chain(std::iter::repeat(tracks.y.last().unwrap_or(&auto))) + .skip(y) + .take(rowspan) + .any(|row| row == &Sizing::Auto) + || gutter + .y + .iter() + .chain(std::iter::repeat(gutter.y.last().unwrap_or(&zero))) + .skip(y) + .take(rowspan - 1) + .any(|row_gutter| row_gutter == &Sizing::Auto) + }; + + // We can't just use the cell's index in the 'cells' vector to + // determine its automatic position, since cells could have arbitrary + // positions, so the position of a cell in 'cells' can differ from its + // final position in 'resolved_cells' (see below). + // Therefore, we use a counter, 'auto_index', to determine the position + // of the next cell with (x: auto, y: auto). It is only stepped when + // a cell with (x: auto, y: auto), usually the vast majority, is found. + let mut auto_index: usize = 0; + + // We have to rebuild the grid to account for arbitrary positions. + // Create at least 'children.len()' positions, since there could be at + // least 'children.len()' cells (if no explicit lines were specified), + // even though some of them might be placed in arbitrary positions and + // thus cause the grid to expand. + // Additionally, make sure we allocate up to the next multiple of 'c', + // since each row will have 'c' cells, even if the last few cells + // weren't explicitly specified by the user. + // We apply '% c' twice so that the amount of cells potentially missing + // is zero when 'children.len()' is already a multiple of 'c' (thus + // 'children.len() % c' would be zero). + let children = children.into_iter(); + let Some(child_count) = children.len().checked_add((c - children.len() % c) % c) + else { + bail!(span, "too many cells or lines were given") + }; + let mut resolved_cells: Vec<Option<Entry>> = Vec::with_capacity(child_count); + for child in children { + let mut is_header = false; + let mut is_footer = false; + let mut child_start = usize::MAX; + let mut child_end = 0; + let mut child_span = Span::detached(); + let mut start_new_row = false; + let mut first_index_of_top_hlines = usize::MAX; + let mut first_index_of_non_top_hlines = usize::MAX; + + let (header_footer_items, simple_item) = match child { + ResolvableGridChild::Header { repeat, span, items, .. } => { + if header.is_some() { + bail!(span, "cannot have more than one header"); + } + + is_header = true; + child_span = span; + repeat_header = repeat; + + // If any cell in the header is automatically positioned, + // have it skip to the next row. This is to avoid having a + // header after a partially filled row just add cells to + // that row instead of starting a new one. + // FIXME: Revise this approach when headers can start from + // arbitrary rows. + start_new_row = true; + + // Any hlines at the top of the header will start at this + // index. + first_index_of_top_hlines = pending_hlines.len(); + + (Some(items), None) + } + ResolvableGridChild::Footer { repeat, span, items, .. } => { + if footer.is_some() { + bail!(span, "cannot have more than one footer"); + } + + is_footer = true; + child_span = span; + repeat_footer = repeat; + + // If any cell in the footer is automatically positioned, + // have it skip to the next row. This is to avoid having a + // footer after a partially filled row just add cells to + // that row instead of starting a new one. + start_new_row = true; + + // Any hlines at the top of the footer will start at this + // index. + first_index_of_top_hlines = pending_hlines.len(); + + (Some(items), None) + } + ResolvableGridChild::Item(item) => (None, Some(item)), + }; + + let items = header_footer_items + .into_iter() + .flatten() + .chain(simple_item.into_iter()); + for item in items { + let cell = match item { + ResolvableGridItem::HLine { + y, + start, + end, + stroke, + span, + position, + } => { + let has_auto_y = y.is_auto(); + let y = y.unwrap_or_else(|| { + // Avoid placing the hline inside consecutive + // rowspans occupying all columns, as it'd just + // disappear, at least when there's no column + // gutter. + skip_auto_index_through_fully_merged_rows( + &resolved_cells, + &mut auto_index, + c, + ); + + // When no 'y' is specified for the hline, we place + // it under the latest automatically positioned + // cell. + // The current value of the auto index is always + // the index of the latest automatically positioned + // cell placed plus one (that's what we do in + // 'resolve_cell_position'), so we subtract 1 to + // get that cell's index, and place the hline below + // its row. The exception is when the auto_index is + // 0, meaning no automatically positioned cell was + // placed yet. In that case, we place the hline at + // the top of the table. + // + // Exceptionally, the hline will be placed before + // the minimum auto index if the current auto index + // from previous iterations is smaller than the + // minimum it should have for the current grid + // child. Effectively, this means that a hline at + // the start of a header will always appear above + // that header's first row. Similarly for footers. + auto_index + .checked_sub(1) + .map_or(0, |last_auto_index| last_auto_index / c + 1) + }); + if end.is_some_and(|end| end.get() < start) { + bail!(span, "line cannot end before it starts"); + } + let line = Line { index: y, start, end, stroke, position }; + + // Since the amount of rows is dynamic, delay placing + // hlines until after all cells were placed so we can + // properly verify if they are valid. Note that we + // can't place hlines even if we already know they + // would be in a valid row, since it's possible that we + // pushed pending hlines in the same row as this one in + // previous iterations, and we need to ensure that + // hlines from previous iterations are pushed to the + // final vector of hlines first - the order of hlines + // must be kept, as this matters when determining which + // one "wins" in case of conflict. Pushing the current + // hline before we push pending hlines later would + // change their order! + pending_hlines.push((span, line, has_auto_y)); + continue; + } + ResolvableGridItem::VLine { + x, + start, + end, + stroke, + span, + position, + } => { + let x = x.unwrap_or_else(|| { + // When no 'x' is specified for the vline, we place + // it after the latest automatically positioned + // cell. + // The current value of the auto index is always + // the index of the latest automatically positioned + // cell placed plus one (that's what we do in + // 'resolve_cell_position'), so we subtract 1 to + // get that cell's index, and place the vline after + // its column. The exception is when the auto_index + // is 0, meaning no automatically positioned cell + // was placed yet. In that case, we place the vline + // to the left of the table. + // + // Exceptionally, a vline is also placed to the + // left of the table if we should start a new row + // for the next automatically positioned cell. + // For example, this means that a vline at + // the beginning of a header will be placed to its + // left rather than after the previous + // automatically positioned cell. Same for footers. + auto_index + .checked_sub(1) + .filter(|_| !start_new_row) + .map_or(0, |last_auto_index| last_auto_index % c + 1) + }); + if end.is_some_and(|end| end.get() < start) { + bail!(span, "line cannot end before it starts"); + } + let line = Line { index: x, start, end, stroke, position }; + + // For consistency with hlines, we only push vlines to + // the final vector of vlines after processing every + // cell. + pending_vlines.push((span, line)); + continue; + } + ResolvableGridItem::Cell(cell) => cell, + }; + let cell_span = cell.span(); + let colspan = cell.colspan(styles).get(); + let rowspan = cell.rowspan(styles).get(); + // Let's calculate the cell's final position based on its + // requested position. + let resolved_index = { + let cell_x = cell.x(styles); + let cell_y = cell.y(styles); + resolve_cell_position( + cell_x, + cell_y, + colspan, + rowspan, + &resolved_cells, + &mut auto_index, + &mut start_new_row, + c, + ) + .at(cell_span)? + }; + let x = resolved_index % c; + let y = resolved_index / c; + + if colspan > c - x { + bail!( + cell_span, + "cell's colspan would cause it to exceed the available column(s)"; + hint: "try placing the cell in another position or reducing its colspan" + ) + } + + let Some(largest_index) = c + .checked_mul(rowspan - 1) + .and_then(|full_rowspan_offset| { + resolved_index.checked_add(full_rowspan_offset) + }) + .and_then(|last_row_pos| last_row_pos.checked_add(colspan - 1)) + else { + bail!( + cell_span, + "cell would span an exceedingly large position"; + hint: "try reducing the cell's rowspan or colspan" + ) + }; + + // Let's resolve the cell so it can determine its own fields + // based on its final position. + let cell = cell.resolve_cell( + x, + y, + &fill.resolve(engine, styles, x, y)?, + align.resolve(engine, styles, x, y)?, + inset.resolve(engine, styles, x, y)?, + stroke.resolve(engine, styles, x, y)?, + resolve_breakable(y, rowspan), + locator.next(&cell_span), + styles, + ); + + if largest_index >= resolved_cells.len() { + // Ensure the length of the vector of resolved cells is + // always a multiple of 'c' by pushing full rows every + // time. Here, we add enough absent positions (later + // converted to empty cells) to ensure the last row in the + // new vector length is completely filled. This is + // necessary so that those positions, even if not + // explicitly used at the end, are eventually susceptible + // to show rules and receive grid styling, as they will be + // resolved as empty cells in a second loop below. + let Some(new_len) = largest_index + .checked_add(1) + .and_then(|new_len| new_len.checked_add((c - new_len % c) % c)) + else { + bail!(cell_span, "cell position too large") + }; + + // Here, the cell needs to be placed in a position which + // doesn't exist yet in the grid (out of bounds). We will + // add enough absent positions for this to be possible. + // They must be absent as no cells actually occupy them + // (they can be overridden later); however, if no cells + // occupy them as we finish building the grid, then such + // positions will be replaced by empty cells. + resolved_cells.resize_with(new_len, || None); + } + + // The vector is large enough to contain the cell, so we can + // just index it directly to access the position it will be + // placed in. However, we still need to ensure we won't try to + // place a cell where there already is one. + let slot = &mut resolved_cells[resolved_index]; + if slot.is_some() { + bail!( + cell_span, + "attempted to place a second cell at column {x}, row {y}"; + hint: "try specifying your cells in a different order" + ); + } + + *slot = Some(Entry::Cell(cell)); + + // Now, if the cell spans more than one row or column, we fill + // the spanned positions in the grid with Entry::Merged + // pointing to the original cell as its parent. + for rowspan_offset in 0..rowspan { + let spanned_y = y + rowspan_offset; + let first_row_index = resolved_index + c * rowspan_offset; + for (colspan_offset, slot) in resolved_cells[first_row_index..] + [..colspan] + .iter_mut() + .enumerate() + { + let spanned_x = x + colspan_offset; + if spanned_x == x && spanned_y == y { + // This is the parent cell. + continue; + } + if slot.is_some() { + bail!( + cell_span, + "cell would span a previously placed cell at column {spanned_x}, row {spanned_y}"; + hint: "try specifying your cells in a different order or reducing the cell's rowspan or colspan" + ) + } + *slot = Some(Entry::Merged { parent: resolved_index }); + } + } + + if is_header || is_footer { + // Ensure each cell in a header or footer is fully + // contained within it. + child_start = child_start.min(y); + child_end = child_end.max(y + rowspan); + + if start_new_row && child_start <= auto_index.div_ceil(c) { + // No need to start a new row as we already include + // the row of the next automatically positioned cell in + // the header or footer. + start_new_row = false; + } + + if !start_new_row { + // From now on, upcoming hlines won't be at the top of + // the child, as the first automatically positioned + // cell was placed. + first_index_of_non_top_hlines = + first_index_of_non_top_hlines.min(pending_hlines.len()); + } + } + } + + if (is_header || is_footer) && child_start == usize::MAX { + // Empty header/footer: consider the header/footer to be + // at the next empty row after the latest auto index. + auto_index = find_next_empty_row(&resolved_cells, auto_index, c); + child_start = auto_index.div_ceil(c); + child_end = child_start + 1; + + if resolved_cells.len() <= c * child_start { + // Ensure the automatically chosen row actually exists. + resolved_cells.resize_with(c * (child_start + 1), || None); + } + } + + if is_header { + if child_start != 0 { + bail!( + child_span, + "header must start at the first row"; + hint: "remove any rows before the header" + ); + } + + header = Some(Header { + // Later on, we have to correct this number in case there + // is gutter. But only once all cells have been analyzed + // and the header has fully expanded in the fixup loop + // below. + end: child_end, + }); + } + + if is_footer { + // Only check if the footer is at the end later, once we know + // the final amount of rows. + footer = Some(( + child_end, + child_span, + Footer { + // Later on, we have to correct this number in case there + // is gutter, but only once all cells have been analyzed + // and the header's and footer's exact boundaries are + // known. That is because the gutter row immediately + // before the footer might not be included as part of + // the footer if it is contained within the header. + start: child_start, + }, + )); + } + + if is_header || is_footer { + let amount_hlines = pending_hlines.len(); + for (_, top_hline, has_auto_y) in pending_hlines + .get_mut( + first_index_of_top_hlines + ..first_index_of_non_top_hlines.min(amount_hlines), + ) + .unwrap_or(&mut []) + { + if *has_auto_y { + // Move this hline to the top of the child, as it was + // placed before the first automatically positioned cell + // and had an automatic index. + top_hline.index = child_start; + } + } + + // Next automatically positioned cell goes under this header. + // FIXME: Consider only doing this if the header has any fully + // automatically positioned cells. Otherwise, + // `resolve_cell_position` should be smart enough to skip + // upcoming headers. + // Additionally, consider that cells with just an 'x' override + // could end up going too far back and making previous + // non-header rows into header rows (maybe they should be + // placed at the first row that is fully empty or something). + // Nothing we can do when both 'x' and 'y' were overridden, of + // course. + // None of the above are concerns for now, as headers must + // start at the first row. + auto_index = auto_index.max(c * child_end); + } + } + + // If the user specified cells occupying less rows than the given rows, + // we shall expand the grid so that it has at least the given amount of + // rows. + let Some(expected_total_cells) = c.checked_mul(tracks.y.len()) else { + bail!(span, "too many rows were specified"); + }; + let missing_cells = expected_total_cells.saturating_sub(resolved_cells.len()); + + // Fixup phase (final step in cell grid generation): + // 1. Replace absent entries by resolved empty cells, and produce a + // vector of 'Entry' from 'Option<Entry>'. + // 2. Add enough empty cells to the end of the grid such that it has at + // least the given amount of rows. + // 3. If any cells were added to the header's rows after the header's + // creation, ensure the header expands enough to accommodate them + // across all of their spanned rows. Same for the footer. + // 4. If any cells before the footer try to span it, error. + let resolved_cells = resolved_cells + .into_iter() + .chain(std::iter::repeat_with(|| None).take(missing_cells)) + .enumerate() + .map(|(i, cell)| { + if let Some(cell) = cell { + if let Some(parent_cell) = cell.as_cell() { + if let Some(header) = &mut header + { + let y = i / c; + if y < header.end { + // Ensure the header expands enough such that + // all cells inside it, even those added later, + // are fully contained within the header. + // FIXME: check if start < y < end when start can + // be != 0. + // FIXME: when start can be != 0, decide what + // happens when a cell after the header placed + // above it tries to span the header (either + // error or expand upwards). + header.end = header.end.max(y + parent_cell.rowspan.get()); + } + } + + if let Some((end, footer_span, footer)) = &mut footer { + let x = i % c; + let y = i / c; + let cell_end = y + parent_cell.rowspan.get(); + if y < footer.start && cell_end > footer.start { + // Don't allow a cell before the footer to span + // it. Surely, we could move the footer to + // start at where this cell starts, so this is + // more of a design choice, as it's unlikely + // for the user to intentionally include a cell + // before the footer spanning it but not + // being repeated with it. + bail!( + *footer_span, + "footer would conflict with a cell placed before it at column {x} row {y}"; + hint: "try reducing that cell's rowspan or moving the footer" + ); + } + if y >= footer.start && y < *end { + // Expand the footer to include all rows + // spanned by this cell, as it is inside the + // footer. + *end = (*end).max(cell_end); + } + } + } + + Ok(cell) + } else { + let x = i % c; + let y = i / c; + + // Ensure all absent entries are affected by show rules and + // grid styling by turning them into resolved empty cells. + let new_cell = T::default().resolve_cell( + x, + y, + &fill.resolve(engine, styles, x, y)?, + align.resolve(engine, styles, x, y)?, + inset.resolve(engine, styles, x, y)?, + stroke.resolve(engine, styles, x, y)?, + resolve_breakable(y, 1), + locator.next(&()), + styles, + ); + Ok(Entry::Cell(new_cell)) + } + }) + .collect::<SourceResult<Vec<Entry>>>()?; + + // Populate the final lists of lines. + // For each line type (horizontal or vertical), we keep a vector for + // every group of lines with the same index. + let mut vlines: Vec<Vec<Line>> = vec![]; + let mut hlines: Vec<Vec<Line>> = vec![]; + let row_amount = resolved_cells.len().div_ceil(c); + + for (line_span, line, _) in pending_hlines { + let y = line.index; + if y > row_amount { + bail!(line_span, "cannot place horizontal line at invalid row {y}"); + } + if y == row_amount && line.position == LinePosition::After { + bail!( + line_span, + "cannot place horizontal line at the 'bottom' position of the bottom border (y = {y})"; + hint: "set the line's position to 'top' or place it at a smaller 'y' index" + ); + } + let line = if line.position == LinePosition::After + && (!has_gutter || y + 1 == row_amount) + { + // Just place the line on top of the next row if + // there's no gutter and the line should be placed + // after the one with given index. + // + // Note that placing after the last row is also the same as + // just placing on the grid's bottom border, even with + // gutter. + Line { + index: y + 1, + position: LinePosition::Before, + ..line + } + } else { + line + }; + let y = line.index; + + if hlines.len() <= y { + hlines.resize_with(y + 1, Vec::new); + } + hlines[y].push(line); + } + + for (line_span, line) in pending_vlines { + let x = line.index; + if x > c { + bail!(line_span, "cannot place vertical line at invalid column {x}"); + } + if x == c && line.position == LinePosition::After { + bail!( + line_span, + "cannot place vertical line at the 'end' position of the end border (x = {c})"; + hint: "set the line's position to 'start' or place it at a smaller 'x' index" + ); + } + let line = + if line.position == LinePosition::After && (!has_gutter || x + 1 == c) { + // Just place the line before the next column if + // there's no gutter and the line should be placed + // after the one with given index. + // + // Note that placing after the last column is also the + // same as just placing on the grid's end border, even + // with gutter. + Line { + index: x + 1, + position: LinePosition::Before, + ..line + } + } else { + line + }; + let x = line.index; + + if vlines.len() <= x { + vlines.resize_with(x + 1, Vec::new); + } + vlines[x].push(line); + } + + let header = header + .map(|mut header| { + // Repeat the gutter below a header (hence why we don't + // subtract 1 from the gutter case). + // Don't do this if there are no rows under the header. + if has_gutter { + // - 'header.end' is always 'last y + 1'. The header stops + // before that row. + // - Therefore, '2 * header.end' will be 2 * (last y + 1), + // which is the adjusted index of the row before which the + // header stops, meaning it will still stop right before it + // even with gutter thanks to the multiplication below. + // - This means that it will span all rows up to + // '2 * (last y + 1) - 1 = 2 * last y + 1', which equates + // to the index of the gutter row right below the header, + // which is what we want (that gutter spacing should be + // repeated across pages to maintain uniformity). + header.end *= 2; + + // If the header occupies the entire grid, ensure we don't + // include an extra gutter row when it doesn't exist, since + // the last row of the header is at the very bottom, + // therefore '2 * last y + 1' is not a valid index. + let row_amount = (2 * row_amount).saturating_sub(1); + header.end = header.end.min(row_amount); + } + header + }) + .map(|header| { + if repeat_header { + Repeatable::Repeated(header) + } else { + Repeatable::NotRepeated(header) + } + }); + + let footer = footer + .map(|(footer_end, footer_span, mut footer)| { + if footer_end != row_amount { + bail!(footer_span, "footer must end at the last row"); + } + + let header_end = + header.as_ref().map(Repeatable::unwrap).map(|header| header.end); + + if has_gutter { + // Convert the footer's start index to post-gutter coordinates. + footer.start *= 2; + + // Include the gutter right before the footer, unless there is + // none, or the gutter is already included in the header (no + // rows between the header and the footer). + if header_end.map_or(true, |header_end| header_end != footer.start) { + footer.start = footer.start.saturating_sub(1); + } + } + + if header_end.is_some_and(|header_end| header_end > footer.start) { + bail!(footer_span, "header and footer must not have common rows"); + } + + Ok(footer) + }) + .transpose()? + .map(|footer| { + if repeat_footer { + Repeatable::Repeated(footer) + } else { + Repeatable::NotRepeated(footer) + } + }); + + Ok(Self::new_internal( + tracks, + gutter, + vlines, + hlines, + header, + footer, + resolved_cells, + )) + } + + /// Generates the cell grid, given the tracks and resolved entries. + pub fn new_internal( + tracks: Axes<&[Sizing]>, + gutter: Axes<&[Sizing]>, + vlines: Vec<Vec<Line>>, + hlines: Vec<Vec<Line>>, + header: Option<Repeatable<Header>>, + footer: Option<Repeatable<Footer>>, + entries: Vec<Entry<'a>>, + ) -> Self { + let mut cols = vec![]; + let mut rows = vec![]; + + // Number of content columns: Always at least one. + let c = tracks.x.len().max(1); + + // Number of content rows: At least as many as given, but also at least + // as many as needed to place each item. + let r = { + let len = entries.len(); + let given = tracks.y.len(); + let needed = len / c + (len % c).clamp(0, 1); + given.max(needed) + }; + + let has_gutter = gutter.any(|tracks| !tracks.is_empty()); + let auto = Sizing::Auto; + let zero = Sizing::Rel(Rel::zero()); + let get_or = |tracks: &[_], idx, default| { + tracks.get(idx).or(tracks.last()).copied().unwrap_or(default) + }; + + // Collect content and gutter columns. + for x in 0..c { + cols.push(get_or(tracks.x, x, auto)); + if has_gutter { + cols.push(get_or(gutter.x, x, zero)); + } + } + + // Collect content and gutter rows. + for y in 0..r { + rows.push(get_or(tracks.y, y, auto)); + if has_gutter { + rows.push(get_or(gutter.y, y, zero)); + } + } + + // Remove superfluous gutter tracks. + if has_gutter { + cols.pop(); + rows.pop(); + } + + Self { + cols, + rows, + entries, + vlines, + hlines, + header, + footer, + has_gutter, + } + } + + /// Get the grid entry in column `x` and row `y`. + /// + /// Returns `None` if it's a gutter cell. + #[track_caller] + pub fn entry(&self, x: usize, y: usize) -> Option<&Entry<'a>> { + assert!(x < self.cols.len()); + assert!(y < self.rows.len()); + + if self.has_gutter { + // Even columns and rows are children, odd ones are gutter. + if x % 2 == 0 && y % 2 == 0 { + let c = 1 + self.cols.len() / 2; + self.entries.get((y / 2) * c + x / 2) + } else { + None + } + } else { + let c = self.cols.len(); + self.entries.get(y * c + x) + } + } + + /// Get the content of the cell in column `x` and row `y`. + /// + /// Returns `None` if it's a gutter cell or merged position. + #[track_caller] + pub fn cell(&self, x: usize, y: usize) -> Option<&Cell<'a>> { + self.entry(x, y).and_then(Entry::as_cell) + } + + /// Returns the position of the parent cell of the grid entry at the given + /// position. It is guaranteed to have a non-gutter, non-merged cell at + /// the returned position, due to how the grid is built. + /// - If the entry at the given position is a cell, returns the given + /// position. + /// - If it is a merged cell, returns the parent cell's position. + /// - If it is a gutter cell, returns None. + #[track_caller] + pub fn parent_cell_position(&self, x: usize, y: usize) -> Option<Axes<usize>> { + self.entry(x, y).map(|entry| match entry { + Entry::Cell(_) => Axes::new(x, y), + Entry::Merged { parent } => { + let c = if self.has_gutter { + 1 + self.cols.len() / 2 + } else { + self.cols.len() + }; + let factor = if self.has_gutter { 2 } else { 1 }; + Axes::new(factor * (*parent % c), factor * (*parent / c)) + } + }) + } + + /// Returns the position of the actual parent cell of a merged position, + /// even if the given position is gutter, in which case we return the + /// parent of the nearest adjacent content cell which could possibly span + /// the given gutter position. If the given position is not a gutter cell, + /// then this function will return the same as `parent_cell_position` would. + /// If the given position is a gutter cell, but no cell spans it, returns + /// `None`. + /// + /// This is useful for lines. A line needs to check if a cell next to it + /// has a stroke override - even at a gutter position there could be a + /// stroke override, since a cell could be merged with two cells at both + /// ends of the gutter cell (e.g. to its left and to its right), and thus + /// that cell would impose a stroke under the gutter. This function allows + /// getting the position of that cell (which spans the given gutter + /// position, if it is gutter), if it exists; otherwise returns None (it's + /// gutter and no cell spans it). + #[track_caller] + pub fn effective_parent_cell_position( + &self, + x: usize, + y: usize, + ) -> Option<Axes<usize>> { + if self.has_gutter { + // If (x, y) is a gutter cell, we skip it (skip a gutter column and + // row) to the nearest adjacent content cell, in the direction + // which merged cells grow toward (increasing x and increasing y), + // such that we can verify if that adjacent cell is merged with the + // gutter cell by checking if its parent would come before (x, y). + // Otherwise, no cell is merged with this gutter cell, and we + // return None. + self.parent_cell_position(x + x % 2, y + y % 2) + .filter(|&parent| parent.x <= x && parent.y <= y) + } else { + self.parent_cell_position(x, y) + } + } + + /// Checks if the track with the given index is gutter. + /// Does not check if the index is a valid track. + #[inline] + pub fn is_gutter_track(&self, index: usize) -> bool { + self.has_gutter && index % 2 == 1 + } + + /// Returns the effective colspan of a cell, considering the gutters it + /// might span if the grid has gutters. + #[inline] + pub fn effective_colspan_of_cell(&self, cell: &Cell) -> usize { + if self.has_gutter { + 2 * cell.colspan.get() - 1 + } else { + cell.colspan.get() + } + } + + /// Returns the effective rowspan of a cell, considering the gutters it + /// might span if the grid has gutters. + #[inline] + pub fn effective_rowspan_of_cell(&self, cell: &Cell) -> usize { + if self.has_gutter { + 2 * cell.rowspan.get() - 1 + } else { + cell.rowspan.get() + } + } +} + +/// Given a cell's requested x and y, the vector with the resolved cell +/// positions, the `auto_index` counter (determines the position of the next +/// `(auto, auto)` cell) and the amount of columns in the grid, returns the +/// final index of this cell in the vector of resolved cells. +/// +/// The `start_new_row` parameter is used to ensure that, if this cell is +/// fully automatically positioned, it should start a new, empty row. This is +/// useful for headers and footers, which must start at their own rows, without +/// interference from previous cells. +#[allow(clippy::too_many_arguments)] +fn resolve_cell_position( + cell_x: Smart<usize>, + cell_y: Smart<usize>, + colspan: usize, + rowspan: usize, + resolved_cells: &[Option<Entry>], + auto_index: &mut usize, + start_new_row: &mut bool, + columns: usize, +) -> HintedStrResult<usize> { + // Translates a (x, y) position to the equivalent index in the final cell vector. + // Errors if the position would be too large. + let cell_index = |x, y: usize| { + y.checked_mul(columns) + .and_then(|row_index| row_index.checked_add(x)) + .ok_or_else(|| HintedString::from(eco_format!("cell position too large"))) + }; + match (cell_x, cell_y) { + // Fully automatic cell positioning. The cell did not + // request a coordinate. + (Smart::Auto, Smart::Auto) => { + // Let's find the first available position starting from the + // automatic position counter, searching in row-major order. + let mut resolved_index = *auto_index; + if *start_new_row { + resolved_index = + find_next_empty_row(resolved_cells, resolved_index, columns); + + // Next cell won't have to start a new row if we just did that, + // in principle. + *start_new_row = false; + } else { + while let Some(Some(_)) = resolved_cells.get(resolved_index) { + // Skip any non-absent cell positions (`Some(None)`) to + // determine where this cell will be placed. An out of + // bounds position (thus `None`) is also a valid new + // position (only requires expanding the vector). + resolved_index += 1; + } + } + + // Ensure the next cell with automatic position will be + // placed after this one (maybe not immediately after). + // + // The calculation below also affects the position of the upcoming + // automatically-positioned lines. + *auto_index = if colspan == columns { + // The cell occupies all columns, so no cells can be placed + // after it until all of its rows have been spanned. + resolved_index + colspan * rowspan + } else { + // The next cell will have to be placed at least after its + // spanned columns. + resolved_index + colspan + }; + + Ok(resolved_index) + } + // Cell has chosen at least its column. + (Smart::Custom(cell_x), cell_y) => { + if cell_x >= columns { + return Err(HintedString::from(eco_format!( + "cell could not be placed at invalid column {cell_x}" + ))); + } + if let Smart::Custom(cell_y) = cell_y { + // Cell has chosen its exact position. + cell_index(cell_x, cell_y) + } else { + // Cell has only chosen its column. + // Let's find the first row which has that column available. + let mut resolved_y = 0; + while let Some(Some(_)) = + resolved_cells.get(cell_index(cell_x, resolved_y)?) + { + // Try each row until either we reach an absent position + // (`Some(None)`) or an out of bounds position (`None`), + // in which case we'd create a new row to place this cell in. + resolved_y += 1; + } + cell_index(cell_x, resolved_y) + } + } + // Cell has only chosen its row, not its column. + (Smart::Auto, Smart::Custom(cell_y)) => { + // Let's find the first column which has that row available. + let first_row_pos = cell_index(0, cell_y)?; + let last_row_pos = first_row_pos + .checked_add(columns) + .ok_or_else(|| eco_format!("cell position too large"))?; + + (first_row_pos..last_row_pos) + .find(|possible_index| { + // Much like in the previous cases, we skip any occupied + // positions until we either reach an absent position + // (`Some(None)`) or an out of bounds position (`None`), + // in which case we can just expand the vector enough to + // place this cell. In either case, we found an available + // position. + !matches!(resolved_cells.get(*possible_index), Some(Some(_))) + }) + .ok_or_else(|| { + eco_format!( + "cell could not be placed in row {cell_y} because it was full" + ) + }) + .hint("try specifying your cells in a different order") + } + } +} + +/// Computes the index of the first cell in the next empty row in the grid, +/// starting with the given initial index. +fn find_next_empty_row( + resolved_cells: &[Option<Entry>], + initial_index: usize, + columns: usize, +) -> usize { + let mut resolved_index = initial_index.next_multiple_of(columns); + while resolved_cells + .get(resolved_index..resolved_index + columns) + .is_some_and(|row| row.iter().any(Option::is_some)) + { + // Skip non-empty rows. + resolved_index += columns; + } + + resolved_index +} + +/// Fully merged rows under the cell of latest auto index indicate rowspans +/// occupying all columns, so we skip the auto index until the shortest rowspan +/// ends, such that, in the resulting row, we will be able to place an +/// automatically positioned cell - and, in particular, hlines under it. The +/// idea is that an auto hline will be placed after the shortest such rowspan. +/// Otherwise, the hline would just be placed under the first row of those +/// rowspans and disappear (except at the presence of column gutter). +fn skip_auto_index_through_fully_merged_rows( + resolved_cells: &[Option<Entry>], + auto_index: &mut usize, + columns: usize, +) { + // If the auto index isn't currently at the start of a row, that means + // there's still at least one auto position left in the row, ignoring + // cells with manual positions, so we wouldn't have a problem in placing + // further cells or, in this case, hlines here. + if *auto_index % columns == 0 { + while resolved_cells + .get(*auto_index..*auto_index + columns) + .is_some_and(|row| { + row.iter().all(|entry| matches!(entry, Some(Entry::Merged { .. }))) + }) + { + *auto_index += columns; + } + } +} diff --git a/crates/typst-layout/src/grid/layouter.rs b/crates/typst-layout/src/grid/layouter.rs new file mode 100644 index 00000000..7c94617d --- /dev/null +++ b/crates/typst-layout/src/grid/layouter.rs @@ -0,0 +1,1582 @@ +use std::fmt::Debug; + +use typst_library::diag::{bail, SourceResult}; +use typst_library::engine::Engine; +use typst_library::foundations::{Resolve, StyleChain}; +use typst_library::layout::{ + Abs, Axes, Dir, Fr, Fragment, Frame, FrameItem, Length, Point, Region, Regions, Rel, + Size, Sizing, +}; +use typst_library::text::TextElem; +use typst_library::visualize::Geometry; +use typst_syntax::Span; +use typst_utils::{MaybeReverseIter, Numeric}; + +use super::{ + generate_line_segments, hline_stroke_at_column, vline_stroke_at_row, Cell, CellGrid, + LinePosition, LineSegment, Repeatable, Rowspan, UnbreakableRowGroup, +}; + +/// Performs grid layout. +pub struct GridLayouter<'a> { + /// The grid of cells. + pub(super) grid: &'a CellGrid<'a>, + /// The regions to layout children into. + pub(super) regions: Regions<'a>, + /// The inherited styles. + pub(super) styles: StyleChain<'a>, + /// Resolved column sizes. + pub(super) rcols: Vec<Abs>, + /// The sum of `rcols`. + pub(super) width: Abs, + /// Resolve row sizes, by region. + pub(super) rrows: Vec<Vec<RowPiece>>, + /// Rows in the current region. + pub(super) lrows: Vec<Row>, + /// The amount of unbreakable rows remaining to be laid out in the + /// current unbreakable row group. While this is positive, no region breaks + /// should occur. + pub(super) unbreakable_rows_left: usize, + /// Rowspans not yet laid out because not all of their spanned rows were + /// laid out yet. + pub(super) rowspans: Vec<Rowspan>, + /// The initial size of the current region before we started subtracting. + pub(super) initial: Size, + /// Frames for finished regions. + pub(super) finished: Vec<Frame>, + /// Whether this is an RTL grid. + pub(super) is_rtl: bool, + /// The simulated header height. + /// This field is reset in `layout_header` and properly updated by + /// `layout_auto_row` and `layout_relative_row`, and should not be read + /// before all header rows are fully laid out. It is usually fine because + /// header rows themselves are unbreakable, and unbreakable rows do not + /// need to read this field at all. + pub(super) header_height: Abs, + /// The simulated footer height for this region. + /// The simulation occurs before any rows are laid out for a region. + pub(super) footer_height: Abs, + /// The span of the grid element. + pub(super) span: Span, +} + +/// Details about a resulting row piece. +#[derive(Debug)] +pub struct RowPiece { + /// The height of the segment. + pub height: Abs, + /// The index of the row. + pub y: usize, +} + +/// Produced by initial row layout, auto and relative rows are already finished, +/// fractional rows not yet. +pub(super) enum Row { + /// Finished row frame of auto or relative row with y index. + /// The last parameter indicates whether or not this is the last region + /// where this row is laid out, and it can only be false when a row uses + /// `layout_multi_row`, which in turn is only used by breakable auto rows. + Frame(Frame, usize, bool), + /// Fractional row with y index and disambiguator. + Fr(Fr, usize, usize), +} + +impl Row { + /// Returns the `y` index of this row. + fn index(&self) -> usize { + match self { + Self::Frame(_, y, _) => *y, + Self::Fr(_, y, _) => *y, + } + } +} + +impl<'a> GridLayouter<'a> { + /// Create a new grid layouter. + /// + /// This prepares grid layout by unifying content and gutter tracks. + pub fn new( + grid: &'a CellGrid<'a>, + regions: Regions<'a>, + styles: StyleChain<'a>, + span: Span, + ) -> Self { + // We use these regions for auto row measurement. Since at that moment, + // columns are already sized, we can enable horizontal expansion. + let mut regions = regions; + regions.expand = Axes::new(true, false); + + Self { + grid, + regions, + styles, + rcols: vec![Abs::zero(); grid.cols.len()], + width: Abs::zero(), + rrows: vec![], + lrows: vec![], + unbreakable_rows_left: 0, + rowspans: vec![], + initial: regions.size, + finished: vec![], + is_rtl: TextElem::dir_in(styles) == Dir::RTL, + header_height: Abs::zero(), + footer_height: Abs::zero(), + span, + } + } + + /// Determines the columns sizes and then layouts the grid row-by-row. + pub fn layout(mut self, engine: &mut Engine) -> SourceResult<Fragment> { + self.measure_columns(engine)?; + + if let Some(Repeatable::Repeated(footer)) = &self.grid.footer { + // Ensure rows in the first region will be aware of the possible + // presence of the footer. + self.prepare_footer(footer, engine, 0)?; + if matches!(self.grid.header, None | Some(Repeatable::NotRepeated(_))) { + // No repeatable header, so we won't subtract it later. + self.regions.size.y -= self.footer_height; + } + } + + for y in 0..self.grid.rows.len() { + if let Some(Repeatable::Repeated(header)) = &self.grid.header { + if y < header.end { + if y == 0 { + self.layout_header(header, engine, 0)?; + self.regions.size.y -= self.footer_height; + } + // Skip header rows during normal layout. + continue; + } + } + + if let Some(Repeatable::Repeated(footer)) = &self.grid.footer { + if y >= footer.start { + if y == footer.start { + self.layout_footer(footer, engine, self.finished.len())?; + } + continue; + } + } + + self.layout_row(y, engine, 0)?; + } + + self.finish_region(engine, true)?; + + // Layout any missing rowspans. + // There are only two possibilities for rowspans not yet laid out + // (usually, a rowspan is laid out as soon as its last row, or any row + // after it, is laid out): + // 1. The rowspan was fully empty and only spanned fully empty auto + // rows, which were all prevented from being laid out. Those rowspans + // are ignored by 'layout_rowspan', and are not of any concern. + // + // 2. The rowspan's last row was an auto row at the last region which + // was not laid out, and no other rows were laid out after it. Those + // might still need to be laid out, so we check for them. + for rowspan in std::mem::take(&mut self.rowspans) { + self.layout_rowspan(rowspan, None, engine)?; + } + + self.render_fills_strokes() + } + + /// Layout the given row. + pub(super) fn layout_row( + &mut self, + y: usize, + engine: &mut Engine, + disambiguator: usize, + ) -> SourceResult<()> { + // Skip to next region if current one is full, but only for content + // rows, not for gutter rows, and only if we aren't laying out an + // unbreakable group of rows. + let is_content_row = !self.grid.is_gutter_track(y); + if self.unbreakable_rows_left == 0 && self.regions.is_full() && is_content_row { + self.finish_region(engine, false)?; + } + + if is_content_row { + // Gutter rows have no rowspans or possibly unbreakable cells. + self.check_for_rowspans(disambiguator, y); + self.check_for_unbreakable_rows(y, engine)?; + } + + // Don't layout gutter rows at the top of a region. + if is_content_row || !self.lrows.is_empty() { + match self.grid.rows[y] { + Sizing::Auto => self.layout_auto_row(engine, disambiguator, y)?, + Sizing::Rel(v) => { + self.layout_relative_row(engine, disambiguator, v, y)? + } + Sizing::Fr(v) => self.lrows.push(Row::Fr(v, y, disambiguator)), + } + } + + self.unbreakable_rows_left = self.unbreakable_rows_left.saturating_sub(1); + + Ok(()) + } + + /// Add lines and backgrounds. + fn render_fills_strokes(mut self) -> SourceResult<Fragment> { + let mut finished = std::mem::take(&mut self.finished); + let frame_amount = finished.len(); + for ((frame_index, frame), rows) in + finished.iter_mut().enumerate().zip(&self.rrows) + { + if self.rcols.is_empty() || rows.is_empty() { + continue; + } + + // Render grid lines. + // We collect lines into a vector before rendering so we can sort + // them based on thickness, such that the lines with largest + // thickness are drawn on top; and also so we can prepend all of + // them at once in the frame, as calling prepend() for each line, + // and thus pushing all frame items forward each time, would result + // in quadratic complexity. + let mut lines = vec![]; + + // Which line position to look for in the list of lines for a + // track, such that placing lines with those positions will + // correspond to placing them before the given track index. + // + // If the index represents a gutter track, this means the list of + // lines will actually correspond to the list of lines in the + // previous index, so we must look for lines positioned after the + // previous index, and not before, to determine which lines should + // be placed before gutter. + // + // Note that the maximum index is always an odd number when + // there's gutter, so we must check for it to ensure we don't give + // it the same treatment as a line before a gutter track. + let expected_line_position = |index, is_max_index: bool| { + if self.grid.is_gutter_track(index) && !is_max_index { + LinePosition::After + } else { + LinePosition::Before + } + }; + + // Render vertical lines. + // Render them first so horizontal lines have priority later. + for (x, dx) in points(self.rcols.iter().copied()).enumerate() { + let dx = if self.is_rtl { self.width - dx } else { dx }; + let is_end_border = x == self.grid.cols.len(); + let expected_vline_position = expected_line_position(x, is_end_border); + + let vlines_at_column = self + .grid + .vlines + .get(if !self.grid.has_gutter { + x + } else if is_end_border { + // The end border has its own vector of lines, but + // dividing it by 2 and flooring would give us the + // vector of lines with the index of the last column. + // Add 1 so we get the border's lines. + x / 2 + 1 + } else { + // If x is a gutter column, this will round down to the + // index of the previous content column, which is + // intentional - the only lines which can appear before + // a gutter column are lines for the previous column + // marked with "LinePosition::After". Therefore, we get + // the previous column's lines. Worry not, as + // 'generate_line_segments' will correctly filter lines + // based on their LinePosition for us. + // + // If x is a content column, this will correctly return + // its index before applying gutters, so nothing + // special here (lines with "LinePosition::After" would + // then be ignored for this column, as we are drawing + // lines before it, not after). + x / 2 + }) + .into_iter() + .flatten() + .filter(|line| line.position == expected_vline_position); + + let tracks = rows.iter().map(|row| (row.y, row.height)); + + // Determine all different line segments we have to draw in + // this column, and convert them to points and shapes. + // + // Even a single, uniform line might generate more than one + // segment, if it happens to cross a colspan (over which it + // must not be drawn). + let segments = generate_line_segments( + self.grid, + tracks, + x, + vlines_at_column, + vline_stroke_at_row, + ) + .map(|segment| { + let LineSegment { stroke, offset: dy, length, priority } = segment; + let stroke = (*stroke).clone().unwrap_or_default(); + let thickness = stroke.thickness; + let half = thickness / 2.0; + let target = Point::with_y(length + thickness); + let vline = Geometry::Line(target).stroked(stroke); + ( + thickness, + priority, + Point::new(dx, dy - half), + FrameItem::Shape(vline, self.span), + ) + }); + + lines.extend(segments); + } + + // Render horizontal lines. + // They are rendered second as they default to appearing on top. + // First, calculate their offsets from the top of the frame. + let hline_offsets = points(rows.iter().map(|piece| piece.height)); + + // Additionally, determine their indices (the indices of the + // rows they are drawn on top of). In principle, this will + // correspond to the rows' indices directly, except for the + // last hline index, which must be (amount of rows) in order to + // draw the table's bottom border. + let hline_indices = rows + .iter() + .map(|piece| piece.y) + .chain(std::iter::once(self.grid.rows.len())); + + // Converts a row to the corresponding index in the vector of + // hlines. + let hline_index_of_row = |y: usize| { + if !self.grid.has_gutter { + y + } else if y == self.grid.rows.len() { + y / 2 + 1 + } else { + // Check the vlines loop for an explanation regarding + // these index operations. + y / 2 + } + }; + + let get_hlines_at = |y| { + self.grid + .hlines + .get(hline_index_of_row(y)) + .map(Vec::as_slice) + .unwrap_or(&[]) + }; + + let mut prev_y = None; + for (y, dy) in hline_indices.zip(hline_offsets) { + // Position of lines below the row index in the previous iteration. + let expected_prev_line_position = prev_y + .map(|prev_y| { + expected_line_position( + prev_y + 1, + prev_y + 1 == self.grid.rows.len(), + ) + }) + .unwrap_or(LinePosition::Before); + + // FIXME: In the future, directly specify in 'self.rrows' when + // we place a repeated header rather than its original rows. + // That would let us remove most of those verbose checks, both + // in 'lines.rs' and here. Those checks also aren't fully + // accurate either, since they will also trigger when some rows + // have been removed between the header and what's below it. + let is_under_repeated_header = self + .grid + .header + .as_ref() + .and_then(Repeatable::as_repeated) + .zip(prev_y) + .is_some_and(|(header, prev_y)| { + // Note: 'y == header.end' would mean we're right below + // the NON-REPEATED header, so that case should return + // false. + prev_y < header.end && y > header.end + }); + + // If some grid rows were omitted between the previous resolved + // row and the current one, we ensure lines below the previous + // row don't "disappear" and are considered, albeit with less + // priority. However, don't do this when we're below a header, + // as it must have more priority instead of less, so it is + // chained later instead of before. The exception is when the + // last row in the header is removed, in which case we append + // both the lines under the row above us and also (later) the + // lines under the header's (removed) last row. + let prev_lines = prev_y + .filter(|prev_y| { + prev_y + 1 != y + && (!is_under_repeated_header + || self + .grid + .header + .as_ref() + .and_then(Repeatable::as_repeated) + .is_some_and(|header| prev_y + 1 != header.end)) + }) + .map(|prev_y| get_hlines_at(prev_y + 1)) + .unwrap_or(&[]); + + let expected_hline_position = + expected_line_position(y, y == self.grid.rows.len()); + + let hlines_at_y = get_hlines_at(y) + .iter() + .filter(|line| line.position == expected_hline_position); + + let top_border_hlines = if prev_y.is_none() && y != 0 { + // For lines at the top of the region, give priority to + // the lines at the top border. + get_hlines_at(0) + } else { + &[] + }; + + let mut expected_header_line_position = LinePosition::Before; + let header_hlines = if let Some((Repeatable::Repeated(header), prev_y)) = + self.grid.header.as_ref().zip(prev_y) + { + if is_under_repeated_header + && (!self.grid.has_gutter + || matches!( + self.grid.rows[prev_y], + Sizing::Rel(length) if length.is_zero() + )) + { + // For lines below a header, give priority to the + // lines originally below the header rather than + // the lines of what's below the repeated header. + // However, no need to do that when we're laying + // out the header for the first time, since the + // lines being normally laid out then will be + // precisely the lines below the header. + // + // Additionally, we don't repeat lines above the row + // below the header when gutter is enabled, since, in + // that case, there will be a gutter row between header + // and content, so no lines should overlap. The + // exception is when the gutter at the end of the + // header has a size of zero, which happens when only + // column-gutter is specified, for example. In that + // case, we still repeat the line under the gutter. + expected_header_line_position = expected_line_position( + header.end, + header.end == self.grid.rows.len(), + ); + get_hlines_at(header.end) + } else { + &[] + } + } else { + &[] + }; + + // The effective hlines to be considered at this row index are + // chained in order of increasing priority: + // 1. Lines from the row right above us, if needed; + // 2. Lines from the current row (usually, only those are + // present); + // 3. Lines from the top border (above the top cells, hence + // 'before' position only); + // 4. Lines from the header above us, if present. + let hlines_at_row = + prev_lines + .iter() + .filter(|line| line.position == expected_prev_line_position) + .chain(hlines_at_y) + .chain( + top_border_hlines + .iter() + .filter(|line| line.position == LinePosition::Before), + ) + .chain(header_hlines.iter().filter(|line| { + line.position == expected_header_line_position + })); + + let tracks = self.rcols.iter().copied().enumerate(); + + // Normally, given an hline above row y, the row above it is + // 'y - 1' (if y > 0). However, sometimes that's not true, for + // example if 'y - 1' is in a previous region, or if 'y - 1' + // was an empty auto row which was removed. Therefore, we tell + // the hlines at this index which row is actually above them in + // the laid out region so they can include that row's bottom + // strokes in the folding process. + let local_top_y = prev_y; + + // When we're in the last region, the bottom border stroke + // doesn't necessarily gain priority like it does in previous + // regions. + let in_last_region = frame_index + 1 == frame_amount; + + // Determine all different line segments we have to draw in + // this row, and convert them to points and shapes. + let segments = generate_line_segments( + self.grid, + tracks, + y, + hlines_at_row, + |grid, y, x, stroke| { + hline_stroke_at_column( + grid, + rows, + local_top_y, + in_last_region, + y, + x, + stroke, + ) + }, + ) + .map(|segment| { + let LineSegment { stroke, offset: dx, length, priority } = segment; + let stroke = (*stroke).clone().unwrap_or_default(); + let thickness = stroke.thickness; + let half = thickness / 2.0; + let dx = if self.is_rtl { self.width - dx - length } else { dx }; + let target = Point::with_x(length + thickness); + let hline = Geometry::Line(target).stroked(stroke); + ( + thickness, + priority, + Point::new(dx - half, dy), + FrameItem::Shape(hline, self.span), + ) + }); + + // Draw later (after we sort all lines below.) + lines.extend(segments); + + prev_y = Some(y); + } + + // Sort by increasing thickness, so that we draw larger strokes + // on top. When the thickness is the same, sort by priority. + // + // Sorting by thickness avoids layering problems where a smaller + // hline appears "inside" a larger vline. When both have the same + // size, hlines are drawn on top (since the sort is stable, and + // they are pushed later). + lines.sort_by_key(|(thickness, priority, ..)| (*thickness, *priority)); + + // Render cell backgrounds. + // We collect them into a vector so they can all be prepended at + // once to the frame, together with lines. + let mut fills = vec![]; + + // Reverse with RTL so that later columns start first. + let mut dx = Abs::zero(); + for (x, &col) in self.rcols.iter().enumerate().rev_if(self.is_rtl) { + let mut dy = Abs::zero(); + for row in rows { + // We want to only draw the fill starting at the parent + // positions of cells. However, sometimes the parent + // position is absent from the current region, either + // because the first few rows of a rowspan were empty auto + // rows and thus removed from layout, or because the parent + // cell was in a previous region (in which case we'd want + // to draw its fill again, in the current region). + // Therefore, we first analyze the parent position to see + // if the current row would be the first row spanned by the + // parent cell in this region. If so, this means we have to + // start drawing the cell's fill here. If not, we ignore + // the position `(x, row.y)`, as its fill will already have + // been rendered before. + // + // Note: In the case of gutter rows, we have to check the + // row below before discarding them fully, because a + // gutter row might be the first row spanned by a rowspan + // in this region (e.g. if the first row was empty and + // therefore removed), so its fill could start in that + // gutter row. That's why we use + // 'effective_parent_cell_position'. + let parent = self + .grid + .effective_parent_cell_position(x, row.y) + .filter(|parent| { + // Ensure this is the first column spanned by the + // cell before drawing its fill, otherwise we + // already rendered its fill in a previous + // iteration of the outer loop (and/or this is a + // gutter column, which we ignore). + // + // Additionally, we should only draw the fill when + // this row is the local parent Y for this cell, + // that is, the first row spanned by the cell's + // parent in this region, because if the parent + // cell's fill was already drawn in a previous + // region, we must render it again in later regions + // spanned by that cell. Note that said condition + // always holds when the current cell has a rowspan + // of 1 and we're not currently at a gutter row. + parent.x == x + && (parent.y == row.y + || rows + .iter() + .find(|row| row.y >= parent.y) + .is_some_and(|first_spanned_row| { + first_spanned_row.y == row.y + })) + }); + + if let Some(parent) = parent { + let cell = self.grid.cell(parent.x, parent.y).unwrap(); + let fill = cell.fill.clone(); + if let Some(fill) = fill { + let rowspan = self.grid.effective_rowspan_of_cell(cell); + let height = if rowspan == 1 { + row.height + } else { + rows.iter() + .filter(|row| { + (parent.y..parent.y + rowspan).contains(&row.y) + }) + .map(|row| row.height) + .sum() + }; + let width = self.cell_spanned_width(cell, x); + // In the grid, cell colspans expand to the right, + // so we're at the leftmost (lowest 'x') column + // spanned by the cell. However, in RTL, cells + // expand to the left. Therefore, without the + // offset below, cell fills would start at the + // rightmost visual position of a cell and extend + // over to unrelated columns to the right in RTL. + // We avoid this by ensuring the fill starts at the + // very left of the cell, even with colspan > 1. + let offset = + if self.is_rtl { -width + col } else { Abs::zero() }; + let pos = Point::new(dx + offset, dy); + let size = Size::new(width, height); + let rect = Geometry::Rect(size).filled(fill); + fills.push((pos, FrameItem::Shape(rect, self.span))); + } + } + dy += row.height; + } + dx += col; + } + + // Now we render each fill and stroke by prepending to the frame, + // such that both appear below cell contents. Fills come first so + // that they appear below lines. + frame.prepend_multiple( + fills + .into_iter() + .chain(lines.into_iter().map(|(_, _, point, shape)| (point, shape))), + ); + } + + Ok(Fragment::frames(finished)) + } + + /// Determine all column sizes. + fn measure_columns(&mut self, engine: &mut Engine) -> SourceResult<()> { + // Sum of sizes of resolved relative tracks. + let mut rel = Abs::zero(); + + // Sum of fractions of all fractional tracks. + let mut fr = Fr::zero(); + + // Resolve the size of all relative columns and compute the sum of all + // fractional tracks. + for (&col, rcol) in self.grid.cols.iter().zip(&mut self.rcols) { + match col { + Sizing::Auto => {} + Sizing::Rel(v) => { + let resolved = + v.resolve(self.styles).relative_to(self.regions.base().x); + *rcol = resolved; + rel += resolved; + } + Sizing::Fr(v) => fr += v, + } + } + + // Size that is not used by fixed-size columns. + let available = self.regions.size.x - rel; + if available >= Abs::zero() { + // Determine size of auto columns. + let (auto, count) = self.measure_auto_columns(engine, available)?; + + // If there is remaining space, distribute it to fractional columns, + // otherwise shrink auto columns. + let remaining = available - auto; + if remaining >= Abs::zero() { + self.grow_fractional_columns(remaining, fr); + } else { + self.shrink_auto_columns(available, count); + } + } + + // Sum up the resolved column sizes once here. + self.width = self.rcols.iter().sum(); + + Ok(()) + } + + /// Total width spanned by the cell (among resolved columns). + /// Includes spanned gutter columns. + pub(super) fn cell_spanned_width(&self, cell: &Cell, x: usize) -> Abs { + let colspan = self.grid.effective_colspan_of_cell(cell); + self.rcols.iter().skip(x).take(colspan).sum() + } + + /// Measure the size that is available to auto columns. + fn measure_auto_columns( + &mut self, + engine: &mut Engine, + available: Abs, + ) -> SourceResult<(Abs, usize)> { + let mut auto = Abs::zero(); + let mut count = 0; + let all_frac_cols = self + .grid + .cols + .iter() + .enumerate() + .filter(|(_, col)| col.is_fractional()) + .map(|(x, _)| x) + .collect::<Vec<_>>(); + + // Determine size of auto columns by laying out all cells in those + // columns, measuring them and finding the largest one. + for (x, &col) in self.grid.cols.iter().enumerate() { + if col != Sizing::Auto { + continue; + } + + let mut resolved = Abs::zero(); + for y in 0..self.grid.rows.len() { + // We get the parent cell in case this is a merged position. + let Some(parent) = self.grid.parent_cell_position(x, y) else { + continue; + }; + if parent.y != y { + // Don't check the width of rowspans more than once. + continue; + } + let cell = self.grid.cell(parent.x, parent.y).unwrap(); + let colspan = self.grid.effective_colspan_of_cell(cell); + if colspan > 1 { + let last_spanned_auto_col = self + .grid + .cols + .iter() + .enumerate() + .skip(parent.x) + .take(colspan) + .rev() + .find(|(_, col)| **col == Sizing::Auto) + .map(|(x, _)| x); + + if last_spanned_auto_col != Some(x) { + // A colspan only affects the size of the last spanned + // auto column. + continue; + } + } + + if colspan > 1 + && self.regions.size.x.is_finite() + && !all_frac_cols.is_empty() + && all_frac_cols + .iter() + .all(|x| (parent.x..parent.x + colspan).contains(x)) + { + // Additionally, as a heuristic, a colspan won't affect the + // size of auto columns if it already spans all fractional + // columns, since those would already expand to provide all + // remaining available after auto column sizing to that + // cell. However, this heuristic is only valid in finite + // regions (pages without 'auto' width), since otherwise + // the fractional columns don't expand at all. + continue; + } + + // Sum the heights of spanned rows to find the expected + // available height for the cell, unless it spans a fractional + // or auto column. + let rowspan = self.grid.effective_rowspan_of_cell(cell); + let height = self + .grid + .rows + .iter() + .skip(y) + .take(rowspan) + .try_fold(Abs::zero(), |acc, col| { + // For relative rows, we can already resolve the correct + // base and for auto and fr we could only guess anyway. + match col { + Sizing::Rel(v) => Some( + acc + v + .resolve(self.styles) + .relative_to(self.regions.base().y), + ), + _ => None, + } + }) + .unwrap_or_else(|| self.regions.base().y); + + // Don't expand this auto column more than the cell actually + // needs. To do this, we check how much the other, previously + // resolved columns provide to the cell in terms of width + // (if it is a colspan), and subtract this from its expected + // width when comparing with other cells in this column. Note + // that, since this is the last auto column spanned by this + // cell, all other auto columns will already have been resolved + // and will be considered. + // Only fractional columns will be excluded from this + // calculation, which can lead to auto columns being expanded + // unnecessarily when cells span both a fractional column and + // an auto column. One mitigation for this is the heuristic + // used above to not expand the last auto column spanned by a + // cell if it spans all fractional columns in a finite region. + let already_covered_width = self.cell_spanned_width(cell, parent.x); + + let size = Size::new(available, height); + let pod = Region::new(size, Axes::splat(false)); + let frame = cell.layout(engine, 0, self.styles, pod.into())?.into_frame(); + resolved.set_max(frame.width() - already_covered_width); + } + + self.rcols[x] = resolved; + auto += resolved; + count += 1; + } + + Ok((auto, count)) + } + + /// Distribute remaining space to fractional columns. + fn grow_fractional_columns(&mut self, remaining: Abs, fr: Fr) { + if fr.is_zero() { + return; + } + + for (&col, rcol) in self.grid.cols.iter().zip(&mut self.rcols) { + if let Sizing::Fr(v) = col { + *rcol = v.share(fr, remaining); + } + } + } + + /// Redistribute space to auto columns so that each gets a fair share. + fn shrink_auto_columns(&mut self, available: Abs, count: usize) { + let mut last; + let mut fair = -Abs::inf(); + let mut redistribute = available; + let mut overlarge = count; + let mut changed = true; + + // Iteratively remove columns that don't need to be shrunk. + while changed && overlarge > 0 { + changed = false; + last = fair; + fair = redistribute / (overlarge as f64); + + for (&col, &rcol) in self.grid.cols.iter().zip(&self.rcols) { + // Remove an auto column if it is not overlarge (rcol <= fair), + // but also hasn't already been removed (rcol > last). + if col == Sizing::Auto && rcol <= fair && rcol > last { + redistribute -= rcol; + overlarge -= 1; + changed = true; + } + } + } + + // Redistribute space fairly among overlarge columns. + for (&col, rcol) in self.grid.cols.iter().zip(&mut self.rcols) { + if col == Sizing::Auto && *rcol > fair { + *rcol = fair; + } + } + } + + /// Layout a row with automatic height. Such a row may break across multiple + /// regions. + fn layout_auto_row( + &mut self, + engine: &mut Engine, + disambiguator: usize, + y: usize, + ) -> SourceResult<()> { + // Determine the size for each region of the row. If the first region + // ends up empty for some column, skip the region and remeasure. + let mut resolved = match self.measure_auto_row( + engine, + disambiguator, + y, + true, + self.unbreakable_rows_left, + None, + )? { + Some(resolved) => resolved, + None => { + self.finish_region(engine, false)?; + self.measure_auto_row( + engine, + disambiguator, + y, + false, + self.unbreakable_rows_left, + None, + )? + .unwrap() + } + }; + + // Nothing to layout. + if resolved.is_empty() { + return Ok(()); + } + + // Layout into a single region. + if let &[first] = resolved.as_slice() { + let frame = self.layout_single_row(engine, disambiguator, first, y)?; + self.push_row(frame, y, true); + + if self + .grid + .header + .as_ref() + .and_then(Repeatable::as_repeated) + .is_some_and(|header| y < header.end) + { + // Add to header height. + self.header_height += first; + } + + return Ok(()); + } + + // Expand all but the last region. + // Skip the first region if the space is eaten up by an fr row. + let len = resolved.len(); + for ((i, region), target) in self + .regions + .iter() + .enumerate() + .zip(&mut resolved[..len - 1]) + .skip(self.lrows.iter().any(|row| matches!(row, Row::Fr(..))) as usize) + { + // Subtract header and footer heights from the region height when + // it's not the first. + target.set_max( + region.y + - if i > 0 { + self.header_height + self.footer_height + } else { + Abs::zero() + }, + ); + } + + // Layout into multiple regions. + let fragment = self.layout_multi_row(engine, disambiguator, &resolved, y)?; + let len = fragment.len(); + for (i, frame) in fragment.into_iter().enumerate() { + self.push_row(frame, y, i + 1 == len); + if i + 1 < len { + self.finish_region(engine, false)?; + } + } + + Ok(()) + } + + /// Measure the regions sizes of an auto row. The option is always `Some(_)` + /// if `can_skip` is false. + /// If `unbreakable_rows_left` is positive, this function shall only return + /// a single frame. Useful when an unbreakable rowspan crosses this auto + /// row. + /// The `row_group_data` option is used within the unbreakable row group + /// simulator to predict the height of the auto row if previous rows in the + /// group were placed in the same region. + pub(super) fn measure_auto_row( + &self, + engine: &mut Engine, + disambiguator: usize, + y: usize, + can_skip: bool, + unbreakable_rows_left: usize, + row_group_data: Option<&UnbreakableRowGroup>, + ) -> SourceResult<Option<Vec<Abs>>> { + let breakable = unbreakable_rows_left == 0; + let mut resolved: Vec<Abs> = vec![]; + let mut pending_rowspans: Vec<(usize, usize, Vec<Abs>)> = vec![]; + + for x in 0..self.rcols.len() { + // Get the parent cell in case this is a merged position. + let Some(parent) = self.grid.parent_cell_position(x, y) else { + // Skip gutter columns. + continue; + }; + if parent.x != x { + // Only check the height of a colspan once. + continue; + } + // The parent cell is never a gutter or merged position. + let cell = self.grid.cell(parent.x, parent.y).unwrap(); + let rowspan = self.grid.effective_rowspan_of_cell(cell); + + if rowspan > 1 { + let last_spanned_auto_row = self + .grid + .rows + .iter() + .enumerate() + .skip(parent.y) + .take(rowspan) + .rev() + .find(|(_, &row)| row == Sizing::Auto) + .map(|(y, _)| y); + + if last_spanned_auto_row != Some(y) { + // A rowspan should only affect the height of its last + // spanned auto row. + continue; + } + } + + let measurement_data = self.prepare_auto_row_cell_measurement( + parent, + cell, + breakable, + row_group_data, + ); + let size = Axes::new(measurement_data.width, measurement_data.height); + let backlog = + measurement_data.backlog.unwrap_or(&measurement_data.custom_backlog); + + let pod = if !breakable { + // Force cell to fit into a single region when the row is + // unbreakable, even when it is a breakable rowspan, as a best + // effort. + let mut pod: Regions = Region::new(size, self.regions.expand).into(); + pod.full = measurement_data.full; + + if measurement_data.frames_in_previous_regions > 0 { + // Best effort to conciliate a breakable rowspan which + // started at a previous region going through an + // unbreakable auto row. Ensure it goes through previously + // laid out regions, but stops at this one when measuring. + pod.backlog = backlog; + } + + pod + } else { + // This row is breakable, so measure the cell normally, with + // the initial height and backlog determined previously. + let mut pod = self.regions; + pod.size = size; + pod.backlog = backlog; + pod.full = measurement_data.full; + pod.last = measurement_data.last; + + pod + }; + + let frames = + cell.layout(engine, disambiguator, self.styles, pod)?.into_frames(); + + // Skip the first region if one cell in it is empty. Then, + // remeasure. + if let Some([first, rest @ ..]) = + frames.get(measurement_data.frames_in_previous_regions..) + { + if can_skip + && breakable + && first.is_empty() + && rest.iter().any(|frame| !frame.is_empty()) + { + return Ok(None); + } + } + + // Skip frames from previous regions if applicable. + let mut sizes = frames + .iter() + .skip(measurement_data.frames_in_previous_regions) + .map(|frame| frame.height()) + .collect::<Vec<_>>(); + + // Don't expand this row more than the cell needs. + // To figure out how much height the cell needs, we must first + // subtract, from the cell's expected height, the already resolved + // heights of its spanned rows. Note that this is the last spanned + // auto row, so all previous auto rows were already resolved, as + // well as fractional rows in previous regions. + // Additionally, we subtract the heights of fixed-size rows which + // weren't laid out yet, since those heights won't change in + // principle. + // Upcoming fractional rows are ignored. + // Upcoming gutter rows might be removed, so we need to simulate + // them. + if rowspan > 1 { + let should_simulate = self.prepare_rowspan_sizes( + y, + &mut sizes, + cell, + parent.y, + rowspan, + unbreakable_rows_left, + &measurement_data, + ); + + if should_simulate { + // Rowspan spans gutter and is breakable. We'll need to + // run a simulation to predict how much this auto row needs + // to expand so that the rowspan's contents fit into the + // table. + pending_rowspans.push((parent.y, rowspan, sizes)); + continue; + } + } + + let mut sizes = sizes.into_iter(); + + for (target, size) in resolved.iter_mut().zip(&mut sizes) { + target.set_max(size); + } + + // New heights are maximal by virtue of being new. Note that + // this extend only uses the rest of the sizes iterator. + resolved.extend(sizes); + } + + // Simulate the upcoming regions in order to predict how much we need + // to expand this auto row for rowspans which span gutter. + if !pending_rowspans.is_empty() { + self.simulate_and_measure_rowspans_in_auto_row( + y, + &mut resolved, + &pending_rowspans, + unbreakable_rows_left, + row_group_data, + disambiguator, + engine, + )?; + } + + debug_assert!(breakable || resolved.len() <= 1); + + Ok(Some(resolved)) + } + + /// Layout a row with relative height. Such a row cannot break across + /// multiple regions, but it may force a region break. + fn layout_relative_row( + &mut self, + engine: &mut Engine, + disambiguator: usize, + v: Rel<Length>, + y: usize, + ) -> SourceResult<()> { + let resolved = v.resolve(self.styles).relative_to(self.regions.base().y); + let frame = self.layout_single_row(engine, disambiguator, resolved, y)?; + + if self + .grid + .header + .as_ref() + .and_then(Repeatable::as_repeated) + .is_some_and(|header| y < header.end) + { + // Add to header height. + self.header_height += resolved; + } + + // Skip to fitting region, but only if we aren't part of an unbreakable + // row group. We use 'in_last_with_offset' so our 'in_last' call + // properly considers that a header and a footer would be added on each + // region break. + let height = frame.height(); + while self.unbreakable_rows_left == 0 + && !self.regions.size.y.fits(height) + && !in_last_with_offset(self.regions, self.header_height + self.footer_height) + { + self.finish_region(engine, false)?; + + // Don't skip multiple regions for gutter and don't push a row. + if self.grid.is_gutter_track(y) { + return Ok(()); + } + } + + self.push_row(frame, y, true); + + Ok(()) + } + + /// Layout a row with fixed height and return its frame. + fn layout_single_row( + &mut self, + engine: &mut Engine, + disambiguator: usize, + height: Abs, + y: usize, + ) -> SourceResult<Frame> { + if !self.width.is_finite() { + bail!(self.span, "cannot create grid with infinite width"); + } + + if !height.is_finite() { + bail!(self.span, "cannot create grid with infinite height"); + } + + let mut output = Frame::soft(Size::new(self.width, height)); + let mut pos = Point::zero(); + + // Reverse the column order when using RTL. + for (x, &rcol) in self.rcols.iter().enumerate().rev_if(self.is_rtl) { + if let Some(cell) = self.grid.cell(x, y) { + // Rowspans have a separate layout step + if cell.rowspan.get() == 1 { + let width = self.cell_spanned_width(cell, x); + let size = Size::new(width, height); + let mut pod: Regions = Region::new(size, Axes::splat(true)).into(); + if self.grid.rows[y] == Sizing::Auto + && self.unbreakable_rows_left == 0 + { + // Cells at breakable auto rows have lengths relative + // to the entire page, unlike cells in unbreakable auto + // rows. + pod.full = self.regions.full; + } + let frame = cell + .layout(engine, disambiguator, self.styles, pod)? + .into_frame(); + let mut pos = pos; + if self.is_rtl { + // In the grid, cell colspans expand to the right, + // so we're at the leftmost (lowest 'x') column + // spanned by the cell. However, in RTL, cells + // expand to the left. Therefore, without the + // offset below, the cell's contents would be laid out + // starting at its rightmost visual position and extend + // over to unrelated cells to its right in RTL. + // We avoid this by ensuring the rendered cell starts at + // the very left of the cell, even with colspan > 1. + let offset = -width + rcol; + pos.x += offset; + } + output.push_frame(pos, frame); + } + } + + pos.x += rcol; + } + + Ok(output) + } + + /// Layout a row spanning multiple regions. + fn layout_multi_row( + &mut self, + engine: &mut Engine, + disambiguator: usize, + heights: &[Abs], + y: usize, + ) -> SourceResult<Fragment> { + // Prepare frames. + let mut outputs: Vec<_> = heights + .iter() + .map(|&h| Frame::soft(Size::new(self.width, h))) + .collect(); + + // Prepare regions. + let size = Size::new(self.width, heights[0]); + let mut pod: Regions = Region::new(size, Axes::splat(true)).into(); + pod.full = self.regions.full; + pod.backlog = &heights[1..]; + + // Layout the row. + let mut pos = Point::zero(); + for (x, &rcol) in self.rcols.iter().enumerate().rev_if(self.is_rtl) { + if let Some(cell) = self.grid.cell(x, y) { + // Rowspans have a separate layout step + if cell.rowspan.get() == 1 { + let width = self.cell_spanned_width(cell, x); + pod.size.x = width; + + // Push the layouted frames into the individual output frames. + let fragment = + cell.layout(engine, disambiguator, self.styles, pod)?; + for (output, frame) in outputs.iter_mut().zip(fragment) { + let mut pos = pos; + if self.is_rtl { + let offset = -width + rcol; + pos.x += offset; + } + output.push_frame(pos, frame); + } + } + } + + pos.x += rcol; + } + + Ok(Fragment::frames(outputs)) + } + + /// Push a row frame into the current region. + /// The `is_last` parameter must be `true` if this is the last frame which + /// will be pushed for this particular row. It can be `false` for rows + /// spanning multiple regions. + fn push_row(&mut self, frame: Frame, y: usize, is_last: bool) { + self.regions.size.y -= frame.height(); + self.lrows.push(Row::Frame(frame, y, is_last)); + } + + /// Finish rows for one region. + pub(super) fn finish_region( + &mut self, + engine: &mut Engine, + last: bool, + ) -> SourceResult<()> { + if self + .lrows + .last() + .is_some_and(|row| self.grid.is_gutter_track(row.index())) + { + // Remove the last row in the region if it is a gutter row. + self.lrows.pop().unwrap(); + } + + // If no rows other than the footer have been laid out so far, and + // there are rows beside the footer, then don't lay it out at all. + // This check doesn't apply, and is thus overridden, when there is a + // header. + let mut footer_would_be_orphan = self.lrows.is_empty() + && !in_last_with_offset( + self.regions, + self.header_height + self.footer_height, + ) + && self + .grid + .footer + .as_ref() + .and_then(Repeatable::as_repeated) + .is_some_and(|footer| footer.start != 0); + + if let Some(Repeatable::Repeated(header)) = &self.grid.header { + if self.grid.rows.len() > header.end + && self + .grid + .footer + .as_ref() + .and_then(Repeatable::as_repeated) + .map_or(true, |footer| footer.start != header.end) + && self.lrows.last().is_some_and(|row| row.index() < header.end) + && !in_last_with_offset( + self.regions, + self.header_height + self.footer_height, + ) + { + // Header and footer would be alone in this region, but there are more + // rows beyond the header and the footer. Push an empty region. + self.lrows.clear(); + footer_would_be_orphan = true; + } + } + + let mut laid_out_footer_start = None; + if let Some(Repeatable::Repeated(footer)) = &self.grid.footer { + // Don't layout the footer if it would be alone with the header in + // the page, and don't layout it twice. + if !footer_would_be_orphan + && self.lrows.iter().all(|row| row.index() < footer.start) + { + laid_out_footer_start = Some(footer.start); + self.layout_footer(footer, engine, self.finished.len())?; + } + } + + // Determine the height of existing rows in the region. + let mut used = Abs::zero(); + let mut fr = Fr::zero(); + for row in &self.lrows { + match row { + Row::Frame(frame, _, _) => used += frame.height(), + Row::Fr(v, _, _) => fr += *v, + } + } + + // Determine the size of the grid in this region, expanding fully if + // there are fr rows. + let mut size = Size::new(self.width, used).min(self.initial); + if fr.get() > 0.0 && self.initial.y.is_finite() { + size.y = self.initial.y; + } + + // The frame for the region. + let mut output = Frame::soft(size); + let mut pos = Point::zero(); + let mut rrows = vec![]; + let current_region = self.finished.len(); + + // Place finished rows and layout fractional rows. + for row in std::mem::take(&mut self.lrows) { + let (frame, y, is_last) = match row { + Row::Frame(frame, y, is_last) => (frame, y, is_last), + Row::Fr(v, y, disambiguator) => { + let remaining = self.regions.full - used; + let height = v.share(fr, remaining); + (self.layout_single_row(engine, disambiguator, height, y)?, y, true) + } + }; + + let height = frame.height(); + + // Ensure rowspans which span this row will have enough space to + // be laid out over it later. + for rowspan in self + .rowspans + .iter_mut() + .filter(|rowspan| (rowspan.y..rowspan.y + rowspan.rowspan).contains(&y)) + .filter(|rowspan| { + rowspan.max_resolved_row.map_or(true, |max_row| y > max_row) + }) + { + // If the first region wasn't defined yet, it will have the + // initial value of usize::MAX, so we can set it to the current + // region's index. + if rowspan.first_region > current_region { + rowspan.first_region = current_region; + // The rowspan starts at this region, precisely at this + // row. In other regions, it will start at dy = 0. + rowspan.dy = pos.y; + // When we layout the rowspan later, the full size of the + // pod must be equal to the full size of the first region + // it appears in. + rowspan.region_full = self.regions.full; + } + let amount_missing_heights = (current_region + 1) + .saturating_sub(rowspan.heights.len() + rowspan.first_region); + + // Ensure the vector of heights is long enough such that the + // last height is the one for the current region. + rowspan + .heights + .extend(std::iter::repeat(Abs::zero()).take(amount_missing_heights)); + + // Ensure that, in this region, the rowspan will span at least + // this row. + *rowspan.heights.last_mut().unwrap() += height; + + if is_last { + // Do not extend the rowspan through this row again, even + // if it is repeated in a future region. + rowspan.max_resolved_row = Some(y); + } + } + + // We use a for loop over indices to avoid borrow checking + // problems (we need to mutate the rowspans vector, so we can't + // have an iterator actively borrowing it). We keep a separate + // 'i' variable so we can step the counter back after removing + // a rowspan (see explanation below). + let mut i = 0; + while let Some(rowspan) = self.rowspans.get(i) { + // Layout any rowspans which end at this row, but only if this is + // this row's last frame (to avoid having the rowspan stop being + // laid out at the first frame of the row). + // Any rowspans ending before this row are laid out even + // on this row's first frame. + if laid_out_footer_start.map_or(true, |footer_start| { + // If this is a footer row, then only lay out this rowspan + // if the rowspan is contained within the footer. + y < footer_start || rowspan.y >= footer_start + }) && (rowspan.y + rowspan.rowspan < y + 1 + || rowspan.y + rowspan.rowspan == y + 1 && is_last) + { + // Rowspan ends at this or an earlier row, so we take + // it from the rowspans vector and lay it out. + // It's safe to pass the current region as a possible + // region for the rowspan to be laid out in, even if + // the rowspan's last row was at an earlier region, + // because the rowspan won't have an entry for this + // region in its 'heights' vector if it doesn't span + // any rows in this region. + // + // Here we don't advance the index counter ('i') because + // a new element we haven't checked yet in this loop + // will take the index of the now removed element, so + // we have to check the same index again in the next + // iteration. + let rowspan = self.rowspans.remove(i); + self.layout_rowspan(rowspan, Some((&mut output, &rrows)), engine)?; + } else { + i += 1; + } + } + + output.push_frame(pos, frame); + rrows.push(RowPiece { height, y }); + pos.y += height; + } + + self.finish_region_internal(output, rrows); + + if !last { + let disambiguator = self.finished.len(); + if let Some(Repeatable::Repeated(footer)) = &self.grid.footer { + self.prepare_footer(footer, engine, disambiguator)?; + } + + if let Some(Repeatable::Repeated(header)) = &self.grid.header { + // Add a header to the new region. + self.layout_header(header, engine, disambiguator)?; + } + + // Ensure rows don't try to overrun the footer. + self.regions.size.y -= self.footer_height; + } + + Ok(()) + } + + /// Advances to the next region, registering the finished output and + /// resolved rows for the current region in the appropriate vectors. + pub(super) fn finish_region_internal( + &mut self, + output: Frame, + resolved_rows: Vec<RowPiece>, + ) { + self.finished.push(output); + self.rrows.push(resolved_rows); + self.regions.next(); + self.initial = self.regions.size; + } +} + +/// Turn an iterator of extents into an iterator of offsets before, in between, +/// and after the extents, e.g. [10mm, 5mm] -> [0mm, 10mm, 15mm]. +pub(super) fn points( + extents: impl IntoIterator<Item = Abs>, +) -> impl Iterator<Item = Abs> { + let mut offset = Abs::zero(); + std::iter::once(Abs::zero()).chain(extents).map(move |extent| { + offset += extent; + offset + }) +} + +/// Checks if the first region of a sequence of regions is the last usable +/// region, assuming that the last region will always be occupied by some +/// specific offset height, even after calling `.next()`, due to some +/// additional logic which adds content automatically on each region turn (in +/// our case, headers). +pub(super) fn in_last_with_offset(regions: Regions<'_>, offset: Abs) -> bool { + regions.backlog.is_empty() + && regions.last.map_or(true, |height| regions.size.y + offset == height) +} diff --git a/crates/typst-layout/src/grid/lines.rs b/crates/typst-layout/src/grid/lines.rs new file mode 100644 index 00000000..3e89612a --- /dev/null +++ b/crates/typst-layout/src/grid/lines.rs @@ -0,0 +1,1548 @@ +use std::num::NonZeroUsize; +use std::sync::Arc; + +use typst_library::foundations::{AlternativeFold, Fold}; +use typst_library::layout::Abs; +use typst_library::visualize::Stroke; + +use super::{CellGrid, LinePosition, Repeatable, RowPiece}; + +/// Represents an explicit grid line (horizontal or vertical) specified by the +/// user. +pub struct Line { + /// The index of the track after this line. This will be the index of the + /// row a horizontal line is above of, or of the column right after a + /// vertical line. + /// + /// Must be within `0..=tracks.len()` (where `tracks` is either `grid.cols` + /// or `grid.rows`, ignoring gutter tracks, as appropriate). + pub index: usize, + /// The index of the track at which this line starts being drawn. + /// This is the first column a horizontal line appears in, or the first row + /// a vertical line appears in. + /// + /// Must be within `0..tracks.len()` minus gutter tracks. + pub start: usize, + /// The index after the last track through which the line is drawn. + /// Thus, the line is drawn through tracks `start..end` (note that `end` is + /// exclusive). + /// + /// Must be within `1..=tracks.len()` minus gutter tracks. + /// `None` indicates the line should go all the way to the end. + pub end: Option<NonZeroUsize>, + /// The line's stroke. This is `None` when the line is explicitly used to + /// override a previously specified line. + pub stroke: Option<Arc<Stroke<Abs>>>, + /// The line's position in relation to the track with its index. + pub position: LinePosition, +} + +/// Indicates which priority a particular grid line segment should have, based +/// on the highest priority configuration that defined the segment's stroke. +#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] +pub enum StrokePriority { + /// The stroke of the segment was derived solely from the grid's global + /// stroke setting, so it should have the lowest priority. + GridStroke = 0, + /// The segment's stroke was derived (even if partially) from a cell's + /// stroke override, so it should have priority over non-overridden cell + /// strokes and be drawn on top of them (when they have the same + /// thickness). + CellStroke = 1, + /// The segment's stroke was derived from a user's explicitly placed line + /// (hline or vline), and thus should have maximum priority, drawn on top + /// of any cell strokes (when they have the same thickness). + ExplicitLine = 2, +} + +/// Data for a particular line segment in the grid as generated by +/// `generate_line_segments`. +#[derive(Debug, PartialEq, Eq)] +pub struct LineSegment { + /// The stroke with which to draw this segment. + pub stroke: Arc<Stroke<Abs>>, + /// The offset of this segment since the beginning of its axis. + /// For a vertical line segment, this is the offset since the top of the + /// table in the current page; for a horizontal line segment, this is the + /// offset since the start border of the table. + pub offset: Abs, + /// The length of this segment. + pub length: Abs, + /// The segment's drawing priority, indicating on top of which other + /// segments this one should be drawn. + pub priority: StrokePriority, +} + +/// Generates the segments of lines that should be drawn alongside a certain +/// axis in the grid, going through the given tracks (orthogonal to the lines). +/// Each returned segment contains its stroke, its offset from the start, and +/// its length. +/// +/// Accepts, as parameters, the index of the lines that should be produced +/// (for example, the column at which vertical lines will be drawn); a list of +/// user-specified lines with the same index (the `lines` parameter); whether +/// the given index corresponds to the maximum index for the line's axis; and a +/// function which returns the final stroke that should be used for each track +/// the line goes through, alongside the priority of the returned stroke (its +/// parameters are the grid, the index of the line to be drawn, the number of +/// the track to draw at and the stroke of the user hline/vline override at +/// this index to fold with, if any). Contiguous segments with the same stroke +/// and priority are joined together automatically. +/// +/// The function should return `None` for positions at which the line would +/// otherwise cross a merged cell (for example, a vline could cross a colspan), +/// in which case a new segment should be drawn after the merged cell(s), even +/// if it would have the same stroke as the previous one. +/// +/// Regarding priority, the function should return a priority of ExplicitLine +/// when the user-defined line's stroke at the current position isn't None +/// (note that it is passed by parameter to the function). When it is None, the +/// function should return a priority of CellStroke if the stroke returned was +/// given or affected by a per-cell override of the grid's global stroke. +/// When that isn't the case, the returned stroke was entirely provided by the +/// grid's global stroke, and thus a priority of GridStroke should be returned. +/// +/// Note that we assume that the tracks are sorted according to ascending +/// number, and they must be iterable over pairs of (number, size). For +/// vertical lines, for instance, `tracks` would describe the rows in the +/// current region, as pairs (row index, row height). +pub fn generate_line_segments<'grid, F, I, L>( + grid: &'grid CellGrid, + tracks: I, + index: usize, + lines: L, + line_stroke_at_track: F, +) -> impl Iterator<Item = LineSegment> + 'grid +where + F: Fn( + &CellGrid, + usize, + usize, + Option<Option<Arc<Stroke<Abs>>>>, + ) -> Option<(Arc<Stroke<Abs>>, StrokePriority)> + + 'grid, + I: IntoIterator<Item = (usize, Abs)>, + I::IntoIter: 'grid, + L: IntoIterator<Item = &'grid Line>, + L::IntoIter: Clone + 'grid, +{ + // The segment currently being drawn. + // + // It is extended for each consecutive track through which the line would + // be drawn with the same stroke and priority. + // + // Starts as None to force us to create a new segment as soon as we find + // the first track through which we should draw. + let mut current_segment: Option<LineSegment> = None; + + // How far from the start (before the first track) have we gone so far. + // Used to determine the positions at which to draw each segment. + let mut offset = Abs::zero(); + + // How much to multiply line indices by to account for gutter. + let gutter_factor = if grid.has_gutter { 2 } else { 1 }; + + // Create an iterator of line segments, which will go through each track, + // from start to finish, to create line segments and extend them until they + // are interrupted and thus yielded through the iterator. We then repeat + // the process, picking up from the track after the one at which we had + // an interruption, until we have gone through all tracks. + // + // When going through each track, we check if the current segment would be + // interrupted, either because, at this track, we hit a merged cell over + // which we shouldn't draw, or because the line would have a different + // stroke or priority at this point (so we have to start a new segment). If + // so, the current segment is yielded and its variable is either set to + // 'None' (if no segment should be drawn at the point of interruption, + // meaning we might have to create a new segment later) or to the new + // segment (if we're starting to draw a segment with a different stroke or + // priority than before). + // Otherwise (if the current segment should span the current track), it is + // simply extended (or a new one is created, if it is 'None'), and no value + // is yielded for the current track, since the segment isn't yet complete + // (the next tracks might extend it further before it is interrupted and + // yielded). That is, we yield each segment only when it is interrupted, + // since then we will know its final length for sure. + // + // After the loop is done (and thus we went through all tracks), we + // interrupt the current segment one last time, to ensure the final segment + // is always interrupted and yielded, if it wasn't interrupted earlier. + let mut tracks = tracks.into_iter(); + let lines = lines.into_iter(); + std::iter::from_fn(move || { + // Each time this closure runs, we advance the track iterator as much + // as possible before returning because the current segment was + // interrupted. The for loop is resumed from where it stopped at the + // next call due to that, ensuring we go through all tracks and then + // stop. + for (track, size) in &mut tracks { + // Get the expected line stroke at this track by folding the + // strokes of each user-specified line (with priority to the + // user-specified line specified last). + let mut line_strokes = lines + .clone() + .filter(|line| { + line.end + .map(|end| { + // Subtract 1 from end index so we stop at the last + // cell before it (don't cross one extra gutter). + let end = if grid.has_gutter { + 2 * end.get() - 1 + } else { + end.get() + }; + (gutter_factor * line.start..end).contains(&track) + }) + .unwrap_or_else(|| track >= gutter_factor * line.start) + }) + .map(|line| line.stroke.clone()); + + // Distinguish between unspecified stroke (None, if no lines + // were matched above) and specified stroke of None (Some(None), + // if some lines were matched and the one specified last had a + // stroke of None) by conditionally folding after 'next()'. + let line_stroke = line_strokes.next().map(|first_stroke| { + line_strokes.fold(first_stroke, |acc, line_stroke| line_stroke.fold(acc)) + }); + + // The function shall determine if it is appropriate to draw + // the line at this position or not (i.e. whether or not it + // would cross a merged cell), and, if so, the final stroke it + // should have (because cells near this position could have + // stroke overrides, which have priority and should be folded + // with the stroke obtained above). + // + // If we are currently already drawing a segment and the function + // indicates we should, at this track, draw some other segment + // (with a different stroke or priority), or even no segment at + // all, we interrupt and yield the current segment (which was drawn + // up to the previous track) by returning it wrapped in 'Some()' + // (which indicates, in the context of 'std::iter::from_fn', that + // our iterator isn't over yet, and this should be its next value). + if let Some((stroke, priority)) = + line_stroke_at_track(grid, index, track, line_stroke) + { + // We should draw at this position. Let's check if we were + // already drawing in the previous position. + if let Some(current_segment) = &mut current_segment { + // We are currently building a segment. Let's check if + // we should extend it to this track as well. + if current_segment.stroke == stroke + && current_segment.priority == priority + { + // Extend the current segment so it covers at least + // this track as well, since we should use the same + // stroke as in the previous one when a line goes + // through this track, with the same priority. + current_segment.length += size; + } else { + // We got a different stroke or priority now, so create + // a new segment with the new stroke and spanning the + // current track. Yield the old segment, as it was + // interrupted and is thus complete. + let new_segment = + LineSegment { stroke, offset, length: size, priority }; + let old_segment = std::mem::replace(current_segment, new_segment); + offset += size; + return Some(old_segment); + } + } else { + // We should draw here, but there is no segment + // currently being drawn, either because the last + // position had a merged cell, had a stroke + // of 'None', or because this is the first track. + // Create a new segment to draw. We start spanning this + // track. + current_segment = + Some(LineSegment { stroke, offset, length: size, priority }); + } + } else if let Some(old_segment) = Option::take(&mut current_segment) { + // We shouldn't draw here (stroke of None), so we yield the + // current segment, as it was interrupted. + offset += size; + return Some(old_segment); + } + // Either the current segment is None (meaning we didn't start + // drawing a segment yet since the last yielded one), so we keep + // searching for a track where we should draw one; or the current + // segment is Some but wasn't interrupted at this track, so we keep + // looping through the following tracks until it is interrupted, + // or we reach the end. + offset += size; + } + + // Reached the end of all tracks, so we interrupt and finish + // the current segment. Note that, on future calls to this + // closure, the current segment will necessarily be 'None', + // so the iterator will necessarily end (that is, we will return None) + // after this. + // + // Note: Fully-qualified notation because rust-analyzer is confused. + Option::take(&mut current_segment) + }) +} + +/// Returns the correct stroke with which to draw a vline right before column +/// `x` when going through row `y`, given the stroke of the user-specified line +/// at this position, if any (note that a stroke of `None` is unspecified, +/// while `Some(None)` means specified to remove any stroke at this position). +/// Also returns the stroke's drawing priority, which depends on its source. +/// +/// If the vline would go through a colspan, returns None (shouldn't be drawn). +/// If the one (when at the border) or two (otherwise) cells to the left and +/// right of the vline have right and left stroke overrides, respectively, +/// then the cells' stroke overrides are folded together with the vline's +/// stroke (with priority to the vline's stroke, followed by the right cell's +/// stroke, and, finally, the left cell's) and returned. If only one of the two +/// cells around the vline (if there are two) has an override, that cell's +/// stroke is given priority when folding. If, however, the cells around the +/// vline at this row do not have any stroke overrides, then the vline's own +/// stroke, as defined by user-specified lines (if any), is returned. +/// +/// The priority associated with the returned stroke follows the rules +/// described in the docs for `generate_line_segment`. +pub fn vline_stroke_at_row( + grid: &CellGrid, + x: usize, + y: usize, + stroke: Option<Option<Arc<Stroke<Abs>>>>, +) -> Option<(Arc<Stroke<Abs>>, StrokePriority)> { + // When the vline isn't at the border, we need to check if a colspan would + // be present between columns 'x' and 'x-1' at row 'y', and thus overlap + // with the line. + // To do so, we analyze the cell right after this vline. If it is merged + // with a cell before this line (parent.x < x) which is at this row or + // above it (parent.y <= y, which is checked by + // 'effective_parent_cell_position'), this means it would overlap with the + // vline, so the vline must not be drawn at this row. + if x != 0 && x != grid.cols.len() { + // Use 'effective_parent_cell_position' to skip the gutters, if x or y + // represent gutter tracks. + // We would then analyze the cell one column after (if at a gutter + // column), and/or one row below (if at a gutter row), in order to + // check if it would be merged with a cell before the vline. + if let Some(parent) = grid.effective_parent_cell_position(x, y) { + if parent.x < x { + // There is a colspan cell going through this vline's position, + // so don't draw it here. + return None; + } + } + } + + let (left_cell_stroke, left_cell_prioritized) = x + .checked_sub(1) + .and_then(|left_x| { + // Let's find the parent cell of the position before us, in order + // to take its right stroke, even with gutter before us. + grid.effective_parent_cell_position(left_x, y) + }) + .map(|parent| { + let left_cell = grid.cell(parent.x, parent.y).unwrap(); + (left_cell.stroke.right.clone(), left_cell.stroke_overridden.right) + }) + .unwrap_or((None, false)); + + let (right_cell_stroke, right_cell_prioritized) = if x < grid.cols.len() { + // Let's find the parent cell of the position after us, in order + // to take its left stroke, even with gutter after us. + grid.effective_parent_cell_position(x, y) + .map(|parent| { + let right_cell = grid.cell(parent.x, parent.y).unwrap(); + (right_cell.stroke.left.clone(), right_cell.stroke_overridden.left) + }) + .unwrap_or((None, false)) + } else { + (None, false) + }; + + let priority = if stroke.is_some() { + StrokePriority::ExplicitLine + } else if left_cell_prioritized || right_cell_prioritized { + StrokePriority::CellStroke + } else { + StrokePriority::GridStroke + }; + + let (prioritized_cell_stroke, deprioritized_cell_stroke) = + if left_cell_prioritized && !right_cell_prioritized { + (left_cell_stroke, right_cell_stroke) + } else { + // When both cells' strokes have the same priority, we default to + // prioritizing the right cell's left stroke. + (right_cell_stroke, left_cell_stroke) + }; + + // When both cells specify a stroke for this line segment, fold + // both strokes, with priority to either the one prioritized cell, + // or to the right cell's left stroke in case of a tie. But when one of + // them doesn't specify a stroke, the other cell's stroke should be used + // instead, regardless of priority (hence the usage of 'fold_or'). + let cell_stroke = prioritized_cell_stroke.fold_or(deprioritized_cell_stroke); + + // Fold the line stroke and folded cell strokes, if possible. + // Give priority to the explicit line stroke. + // Otherwise, use whichever of the two isn't 'none' or unspecified. + let final_stroke = stroke.fold_or(Some(cell_stroke)).flatten(); + + final_stroke.zip(Some(priority)) +} + +/// Returns the correct stroke with which to draw a hline on top of row `y` +/// when going through column `x`, given the stroke of the user-specified line +/// at this position, if any (note that a stroke of `None` is unspecified, +/// while `Some(None)` means specified to remove any stroke at this position). +/// Also returns the stroke's drawing priority, which depends on its source. +/// +/// The `local_top_y` parameter indicates which row is effectively on top of +/// this hline at the current region. This is `None` if the hline is above the +/// first row in the region, for instance. The `in_last_region` parameter +/// indicates whether this is the last region of the table. If not and this is +/// a line at the bottom border, the bottom border's line gains priority. +/// +/// If the one (when at the border) or two (otherwise) cells above and below +/// the hline have bottom and top stroke overrides, respectively, then the +/// cells' stroke overrides are folded together with the hline's stroke (with +/// priority to hline's stroke, followed by the bottom cell's stroke, and, +/// finally, the top cell's) and returned. If only one of the two cells around +/// the vline (if there are two) has an override, that cell's stroke is given +/// priority when folding. If, however, the cells around the hline at this +/// column do not have any stroke overrides, then the hline's own stroke, as +/// defined by user-specified lines (if any), is directly returned. +/// +/// The priority associated with the returned stroke follows the rules +/// described in the docs for `generate_line_segment`. +/// +/// The rows argument is needed to know which rows are effectively present in +/// the current region, in order to avoid unnecessary hline splitting when a +/// rowspan's previous rows are either in a previous region or empty (and thus +/// wouldn't overlap with the hline, since its first row in the current region +/// is below the hline). +/// +/// This function assumes columns are sorted by increasing `x`, and rows are +/// sorted by increasing `y`. +pub fn hline_stroke_at_column( + grid: &CellGrid, + rows: &[RowPiece], + local_top_y: Option<usize>, + in_last_region: bool, + y: usize, + x: usize, + stroke: Option<Option<Arc<Stroke<Abs>>>>, +) -> Option<(Arc<Stroke<Abs>>, StrokePriority)> { + // When the hline isn't at the border, we need to check if a rowspan + // would be present between rows 'y' and 'y-1' at column 'x', and thus + // overlap with the line. + // To do so, we analyze the cell right below this hline. If it is + // merged with a cell above this line (parent.y < y) which is at this + // column or before it (parent.x <= x, which is checked by + // 'effective_parent_cell_position'), this means it would overlap with the + // hline, so the hline must not be drawn at this column. + if y != 0 && y != grid.rows.len() { + // Use 'effective_parent_cell_position' to skip the gutters, if x or y + // represent gutter tracks. + // We would then analyze the cell one column after (if at a gutter + // column), and/or one row below (if at a gutter row), in order to + // check if it would be merged with a cell before the hline. + if let Some(parent) = grid.effective_parent_cell_position(x, y) { + if parent.y < y { + // Get the first 'y' spanned by the possible rowspan in this region. + // The 'parent.y' row and any other spanned rows above 'y' could be + // missing from this region, which could have lead the check above + // to be triggered, even though there is no spanned row above the + // hline in the final layout of this region, and thus no overlap + // with the hline, allowing it to be drawn regardless of the + // theoretical presence of a rowspan going across its position. + let local_parent_y = rows + .iter() + .find(|row| row.y >= parent.y) + .map(|row| row.y) + .unwrap_or(y); + + if local_parent_y < y { + // There is a rowspan cell going through this hline's + // position, so don't draw it here. + return None; + } + } + } + } + + // When the hline is at the top of the region and this isn't the first + // region, fold with the top stroke of the topmost cell at this column, + // that is, the top border. + let use_top_border_stroke = local_top_y.is_none() && y != 0; + let (top_cell_stroke, top_cell_prioritized) = local_top_y + .or(use_top_border_stroke.then_some(0)) + .and_then(|top_y| { + // Let's find the parent cell of the position above us, in order + // to take its bottom stroke, even when we're below gutter. + grid.effective_parent_cell_position(x, top_y) + }) + .map(|parent| { + let top_cell = grid.cell(parent.x, parent.y).unwrap(); + if use_top_border_stroke { + (top_cell.stroke.top.clone(), top_cell.stroke_overridden.top) + } else { + (top_cell.stroke.bottom.clone(), top_cell.stroke_overridden.bottom) + } + }) + .unwrap_or((None, false)); + + // Use the bottom border stroke with priority if we're not in the last + // region, we have the last index, and (as a failsafe) we don't have the + // last row of cells above us. + let use_bottom_border_stroke = !in_last_region + && local_top_y.map_or(true, |top_y| top_y + 1 != grid.rows.len()) + && y == grid.rows.len(); + let bottom_y = + if use_bottom_border_stroke { grid.rows.len().saturating_sub(1) } else { y }; + let (bottom_cell_stroke, bottom_cell_prioritized) = if bottom_y < grid.rows.len() { + // Let's find the parent cell of the position below us, in order + // to take its top stroke, even when we're above gutter. + grid.effective_parent_cell_position(x, bottom_y) + .map(|parent| { + let bottom_cell = grid.cell(parent.x, parent.y).unwrap(); + if use_bottom_border_stroke { + ( + bottom_cell.stroke.bottom.clone(), + bottom_cell.stroke_overridden.bottom, + ) + } else { + (bottom_cell.stroke.top.clone(), bottom_cell.stroke_overridden.top) + } + }) + .unwrap_or((None, false)) + } else { + // No cell below the bottom border. + (None, false) + }; + + let priority = if stroke.is_some() { + StrokePriority::ExplicitLine + } else if top_cell_prioritized || bottom_cell_prioritized { + StrokePriority::CellStroke + } else { + StrokePriority::GridStroke + }; + + // Top border stroke and header stroke are generally prioritized, unless + // they don't have explicit hline overrides and one or more user-provided + // hlines would appear at the same position, which then are prioritized. + let top_stroke_comes_from_header = grid + .header + .as_ref() + .and_then(Repeatable::as_repeated) + .zip(local_top_y) + .is_some_and(|(header, local_top_y)| { + // Ensure the row above us is a repeated header. + // FIXME: Make this check more robust when headers at arbitrary + // positions are added. + local_top_y < header.end && y > header.end + }); + + // Prioritize the footer's top stroke as well where applicable. + let bottom_stroke_comes_from_footer = grid + .footer + .as_ref() + .and_then(Repeatable::as_repeated) + .is_some_and(|footer| { + // Ensure the row below us is a repeated footer. + // FIXME: Make this check more robust when footers at arbitrary + // positions are added. + local_top_y.unwrap_or(0) + 1 < footer.start && y >= footer.start + }); + + let (prioritized_cell_stroke, deprioritized_cell_stroke) = + if !use_bottom_border_stroke + && !bottom_stroke_comes_from_footer + && (use_top_border_stroke + || top_stroke_comes_from_header + || top_cell_prioritized && !bottom_cell_prioritized) + { + // Top border must always be prioritized, even if it did not + // request for that explicitly. + (top_cell_stroke, bottom_cell_stroke) + } else { + // When both cells' strokes have the same priority, we default to + // prioritizing the bottom cell's top stroke. + // Additionally, the bottom border cell's stroke always has + // priority. Same for stroke above footers. + (bottom_cell_stroke, top_cell_stroke) + }; + + // When both cells specify a stroke for this line segment, fold + // both strokes, with priority to either the one prioritized cell, + // or to the bottom cell's top stroke in case of a tie. But when one of + // them doesn't specify a stroke, the other cell's stroke should be used + // instead, regardless of priority (hence the usage of 'fold_or'). + let cell_stroke = prioritized_cell_stroke.fold_or(deprioritized_cell_stroke); + + // Fold the line stroke and folded cell strokes, if possible. + // Give priority to the explicit line stroke. + // Otherwise, use whichever of the two isn't 'none' or unspecified. + let final_stroke = stroke.fold_or(Some(cell_stroke)).flatten(); + + final_stroke.zip(Some(priority)) +} + +#[cfg(test)] +mod test { + use typst_library::foundations::Content; + use typst_library::introspection::Locator; + use typst_library::layout::{Axes, Sides, Sizing}; + use typst_utils::NonZeroExt; + + use super::super::cells::Entry; + use super::super::Cell; + use super::*; + + fn sample_cell() -> Cell<'static> { + Cell { + body: Content::default(), + locator: Locator::root(), + fill: None, + colspan: NonZeroUsize::ONE, + rowspan: NonZeroUsize::ONE, + stroke: Sides::splat(Some(Arc::new(Stroke::default()))), + stroke_overridden: Sides::splat(false), + breakable: true, + } + } + + fn cell_with_colspan_rowspan(colspan: usize, rowspan: usize) -> Cell<'static> { + Cell { + body: Content::default(), + locator: Locator::root(), + fill: None, + colspan: NonZeroUsize::try_from(colspan).unwrap(), + rowspan: NonZeroUsize::try_from(rowspan).unwrap(), + stroke: Sides::splat(Some(Arc::new(Stroke::default()))), + stroke_overridden: Sides::splat(false), + breakable: true, + } + } + + fn sample_grid_for_vlines(gutters: bool) -> CellGrid<'static> { + const COLS: usize = 4; + const ROWS: usize = 6; + let entries = vec![ + // row 0 + Entry::Cell(sample_cell()), + Entry::Cell(sample_cell()), + Entry::Cell(cell_with_colspan_rowspan(2, 1)), + Entry::Merged { parent: 2 }, + // row 1 + Entry::Cell(sample_cell()), + Entry::Cell(cell_with_colspan_rowspan(3, 1)), + Entry::Merged { parent: 5 }, + Entry::Merged { parent: 5 }, + // row 2 + Entry::Merged { parent: 4 }, + Entry::Cell(sample_cell()), + Entry::Cell(cell_with_colspan_rowspan(2, 1)), + Entry::Merged { parent: 10 }, + // row 3 + Entry::Cell(sample_cell()), + Entry::Cell(cell_with_colspan_rowspan(3, 2)), + Entry::Merged { parent: 13 }, + Entry::Merged { parent: 13 }, + // row 4 + Entry::Cell(sample_cell()), + Entry::Merged { parent: 13 }, + Entry::Merged { parent: 13 }, + Entry::Merged { parent: 13 }, + // row 5 + Entry::Cell(sample_cell()), + Entry::Cell(sample_cell()), + Entry::Cell(cell_with_colspan_rowspan(2, 1)), + Entry::Merged { parent: 22 }, + ]; + CellGrid::new_internal( + Axes::with_x(&[Sizing::Auto; COLS]), + if gutters { + Axes::new(&[Sizing::Auto; COLS - 1], &[Sizing::Auto; ROWS - 1]) + } else { + Axes::default() + }, + vec![], + vec![], + None, + None, + entries, + ) + } + + #[test] + fn test_vline_splitting_without_gutter() { + let stroke = Arc::new(Stroke::default()); + let grid = sample_grid_for_vlines(false); + let rows = &[ + RowPiece { height: Abs::pt(1.0), y: 0 }, + RowPiece { height: Abs::pt(2.0), y: 1 }, + RowPiece { height: Abs::pt(4.0), y: 2 }, + RowPiece { height: Abs::pt(8.0), y: 3 }, + RowPiece { height: Abs::pt(16.0), y: 4 }, + RowPiece { height: Abs::pt(32.0), y: 5 }, + ]; + let expected_vline_splits = &[ + vec![LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(0.), + length: Abs::pt(1. + 2. + 4. + 8. + 16. + 32.), + priority: StrokePriority::GridStroke, + }], + vec![LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(0.), + length: Abs::pt(1. + 2. + 4. + 8. + 16. + 32.), + priority: StrokePriority::GridStroke, + }], + // interrupted a few times by colspans + vec![ + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(0.), + length: Abs::pt(1.), + priority: StrokePriority::GridStroke, + }, + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(1. + 2.), + length: Abs::pt(4.), + priority: StrokePriority::GridStroke, + }, + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(1. + 2. + 4. + 8. + 16.), + length: Abs::pt(32.), + priority: StrokePriority::GridStroke, + }, + ], + // interrupted every time by colspans + vec![], + vec![LineSegment { + stroke, + offset: Abs::pt(0.), + length: Abs::pt(1. + 2. + 4. + 8. + 16. + 32.), + priority: StrokePriority::GridStroke, + }], + ]; + for (x, expected_splits) in expected_vline_splits.iter().enumerate() { + let tracks = rows.iter().map(|row| (row.y, row.height)); + assert_eq!( + expected_splits, + &generate_line_segments(&grid, tracks, x, &[], vline_stroke_at_row) + .collect::<Vec<_>>(), + ); + } + } + + #[test] + fn test_vline_splitting_with_gutter_and_per_cell_stroke() { + let stroke = Arc::new(Stroke::default()); + let grid = sample_grid_for_vlines(true); + let rows = &[ + RowPiece { height: Abs::pt(1.0), y: 0 }, + RowPiece { height: Abs::pt(2.0), y: 1 }, + RowPiece { height: Abs::pt(4.0), y: 2 }, + RowPiece { height: Abs::pt(8.0), y: 3 }, + RowPiece { height: Abs::pt(16.0), y: 4 }, + RowPiece { height: Abs::pt(32.0), y: 5 }, + RowPiece { height: Abs::pt(64.0), y: 6 }, + RowPiece { height: Abs::pt(128.0), y: 7 }, + RowPiece { height: Abs::pt(256.0), y: 8 }, + RowPiece { height: Abs::pt(512.0), y: 9 }, + RowPiece { height: Abs::pt(1024.0), y: 10 }, + ]; + // Stroke is per-cell so we skip gutter + let expected_vline_splits = &[ + // left border + vec![ + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(0.), + length: Abs::pt(1.), + priority: StrokePriority::GridStroke, + }, + // Covers the rowspan between (original) rows 1 and 2 + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(1. + 2.), + length: Abs::pt(4. + 8. + 16.), + priority: StrokePriority::GridStroke, + }, + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(1. + 2. + 4. + 8. + 16. + 32.), + length: Abs::pt(64.), + priority: StrokePriority::GridStroke, + }, + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(1. + 2. + 4. + 8. + 16. + 32. + 64. + 128.), + length: Abs::pt(256.), + priority: StrokePriority::GridStroke, + }, + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt( + 1. + 2. + 4. + 8. + 16. + 32. + 64. + 128. + 256. + 512., + ), + length: Abs::pt(1024.), + priority: StrokePriority::GridStroke, + }, + ], + // gutter line below + vec![ + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(0.), + length: Abs::pt(1.), + priority: StrokePriority::GridStroke, + }, + // Covers the rowspan between (original) rows 1 and 2 + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(1. + 2.), + length: Abs::pt(4. + 8. + 16.), + priority: StrokePriority::GridStroke, + }, + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(1. + 2. + 4. + 8. + 16. + 32.), + length: Abs::pt(64.), + priority: StrokePriority::GridStroke, + }, + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(1. + 2. + 4. + 8. + 16. + 32. + 64. + 128.), + length: Abs::pt(256.), + priority: StrokePriority::GridStroke, + }, + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt( + 1. + 2. + 4. + 8. + 16. + 32. + 64. + 128. + 256. + 512., + ), + length: Abs::pt(1024.), + priority: StrokePriority::GridStroke, + }, + ], + vec![ + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(0.), + length: Abs::pt(1.), + priority: StrokePriority::GridStroke, + }, + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(1. + 2.), + length: Abs::pt(4.), + priority: StrokePriority::GridStroke, + }, + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(1. + 2. + 4. + 8.), + length: Abs::pt(16.), + priority: StrokePriority::GridStroke, + }, + // Covers the rowspan between (original) rows 3 and 4 + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(1. + 2. + 4. + 8. + 16. + 32.), + length: Abs::pt(64. + 128. + 256.), + priority: StrokePriority::GridStroke, + }, + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt( + 1. + 2. + 4. + 8. + 16. + 32. + 64. + 128. + 256. + 512., + ), + length: Abs::pt(1024.), + priority: StrokePriority::GridStroke, + }, + ], + // gutter line below + // the two lines below are interrupted multiple times by colspans + vec![ + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(0.), + length: Abs::pt(1.), + priority: StrokePriority::GridStroke, + }, + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(1. + 2. + 4. + 8.), + length: Abs::pt(16.), + priority: StrokePriority::GridStroke, + }, + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt( + 1. + 2. + 4. + 8. + 16. + 32. + 64. + 128. + 256. + 512., + ), + length: Abs::pt(1024.), + priority: StrokePriority::GridStroke, + }, + ], + vec![ + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(0.), + length: Abs::pt(1.), + priority: StrokePriority::GridStroke, + }, + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(1. + 2. + 4. + 8.), + length: Abs::pt(16.), + priority: StrokePriority::GridStroke, + }, + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt( + 1. + 2. + 4. + 8. + 16. + 32. + 64. + 128. + 256. + 512., + ), + length: Abs::pt(1024.), + priority: StrokePriority::GridStroke, + }, + ], + // gutter line below + // the two lines below can only cross certain gutter rows, because + // all non-gutter cells in the following column are merged with + // cells from the previous column. + vec![], + vec![], + // right border + vec![ + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(0.), + length: Abs::pt(1.), + priority: StrokePriority::GridStroke, + }, + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(1. + 2.), + length: Abs::pt(4.), + priority: StrokePriority::GridStroke, + }, + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(1. + 2. + 4. + 8.), + length: Abs::pt(16.), + priority: StrokePriority::GridStroke, + }, + // Covers the rowspan between (original) rows 3 and 4 + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(1. + 2. + 4. + 8. + 16. + 32.), + length: Abs::pt(64. + 128. + 256.), + priority: StrokePriority::GridStroke, + }, + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt( + 1. + 2. + 4. + 8. + 16. + 32. + 64. + 128. + 256. + 512., + ), + length: Abs::pt(1024.), + priority: StrokePriority::GridStroke, + }, + ], + ]; + for (x, expected_splits) in expected_vline_splits.iter().enumerate() { + let tracks = rows.iter().map(|row| (row.y, row.height)); + assert_eq!( + expected_splits, + &generate_line_segments(&grid, tracks, x, &[], vline_stroke_at_row) + .collect::<Vec<_>>(), + ); + } + } + + #[test] + fn test_vline_splitting_with_gutter_and_explicit_vlines() { + let stroke = Arc::new(Stroke::default()); + let grid = sample_grid_for_vlines(true); + let rows = &[ + RowPiece { height: Abs::pt(1.0), y: 0 }, + RowPiece { height: Abs::pt(2.0), y: 1 }, + RowPiece { height: Abs::pt(4.0), y: 2 }, + RowPiece { height: Abs::pt(8.0), y: 3 }, + RowPiece { height: Abs::pt(16.0), y: 4 }, + RowPiece { height: Abs::pt(32.0), y: 5 }, + RowPiece { height: Abs::pt(64.0), y: 6 }, + RowPiece { height: Abs::pt(128.0), y: 7 }, + RowPiece { height: Abs::pt(256.0), y: 8 }, + RowPiece { height: Abs::pt(512.0), y: 9 }, + RowPiece { height: Abs::pt(1024.0), y: 10 }, + ]; + let expected_vline_splits = &[ + // left border + vec![LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(0.), + length: Abs::pt( + 1. + 2. + 4. + 8. + 16. + 32. + 64. + 128. + 256. + 512. + 1024., + ), + priority: StrokePriority::ExplicitLine, + }], + // gutter line below + vec![LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(0.), + length: Abs::pt( + 1. + 2. + 4. + 8. + 16. + 32. + 64. + 128. + 256. + 512. + 1024., + ), + priority: StrokePriority::ExplicitLine, + }], + vec![LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(0.), + length: Abs::pt( + 1. + 2. + 4. + 8. + 16. + 32. + 64. + 128. + 256. + 512. + 1024., + ), + priority: StrokePriority::ExplicitLine, + }], + // gutter line below + // the two lines below are interrupted multiple times by colspans + vec![ + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(0.), + length: Abs::pt(1. + 2.), + priority: StrokePriority::ExplicitLine, + }, + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(1. + 2. + 4.), + length: Abs::pt(8. + 16. + 32.), + priority: StrokePriority::ExplicitLine, + }, + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(1. + 2. + 4. + 8. + 16. + 32. + 64. + 128. + 256.), + length: Abs::pt(512. + 1024.), + priority: StrokePriority::ExplicitLine, + }, + ], + vec![ + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(0.), + length: Abs::pt(1. + 2.), + priority: StrokePriority::ExplicitLine, + }, + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(1. + 2. + 4.), + length: Abs::pt(8. + 16. + 32.), + priority: StrokePriority::ExplicitLine, + }, + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(1. + 2. + 4. + 8. + 16. + 32. + 64. + 128. + 256.), + length: Abs::pt(512. + 1024.), + priority: StrokePriority::ExplicitLine, + }, + ], + // gutter line below + // the two lines below can only cross certain gutter rows, because + // all non-gutter cells in the following column are merged with + // cells from the previous column. + vec![ + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(1.), + length: Abs::pt(2.), + priority: StrokePriority::ExplicitLine, + }, + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(1. + 2. + 4.), + length: Abs::pt(8.), + priority: StrokePriority::ExplicitLine, + }, + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(1. + 2. + 4. + 8. + 16.), + length: Abs::pt(32.), + priority: StrokePriority::ExplicitLine, + }, + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(1. + 2. + 4. + 8. + 16. + 32. + 64. + 128. + 256.), + length: Abs::pt(512.), + priority: StrokePriority::ExplicitLine, + }, + ], + vec![ + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(1.), + length: Abs::pt(2.), + priority: StrokePriority::ExplicitLine, + }, + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(1. + 2. + 4.), + length: Abs::pt(8.), + priority: StrokePriority::ExplicitLine, + }, + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(1. + 2. + 4. + 8. + 16.), + length: Abs::pt(32.), + priority: StrokePriority::ExplicitLine, + }, + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(1. + 2. + 4. + 8. + 16. + 32. + 64. + 128. + 256.), + length: Abs::pt(512.), + priority: StrokePriority::ExplicitLine, + }, + ], + // right border + vec![LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(0.), + length: Abs::pt( + 1. + 2. + 4. + 8. + 16. + 32. + 64. + 128. + 256. + 512. + 1024., + ), + priority: StrokePriority::ExplicitLine, + }], + ]; + for (x, expected_splits) in expected_vline_splits.iter().enumerate() { + let tracks = rows.iter().map(|row| (row.y, row.height)); + assert_eq!( + expected_splits, + &generate_line_segments( + &grid, + tracks, + x, + &[ + Line { + index: x, + start: 0, + end: None, + stroke: Some(stroke.clone()), + position: LinePosition::Before + }, + Line { + index: x, + start: 0, + end: None, + stroke: Some(stroke.clone()), + position: LinePosition::After + }, + ], + vline_stroke_at_row + ) + .collect::<Vec<_>>(), + ); + } + } + + fn sample_grid_for_hlines(gutters: bool) -> CellGrid<'static> { + const COLS: usize = 4; + const ROWS: usize = 9; + let entries = vec![ + // row 0 + Entry::Cell(cell_with_colspan_rowspan(1, 2)), + Entry::Cell(sample_cell()), + Entry::Cell(cell_with_colspan_rowspan(2, 2)), + Entry::Merged { parent: 2 }, + // row 1 + Entry::Merged { parent: 0 }, + Entry::Cell(sample_cell()), + Entry::Merged { parent: 2 }, + Entry::Merged { parent: 2 }, + // row 2 + Entry::Cell(sample_cell()), + Entry::Cell(sample_cell()), + Entry::Cell(sample_cell()), + Entry::Cell(sample_cell()), + // row 3 + Entry::Cell(cell_with_colspan_rowspan(4, 2)), + Entry::Merged { parent: 12 }, + Entry::Merged { parent: 12 }, + Entry::Merged { parent: 12 }, + // row 4 + Entry::Merged { parent: 12 }, + Entry::Merged { parent: 12 }, + Entry::Merged { parent: 12 }, + Entry::Merged { parent: 12 }, + // row 5 + Entry::Cell(sample_cell()), + Entry::Cell(cell_with_colspan_rowspan(1, 2)), + Entry::Cell(cell_with_colspan_rowspan(2, 1)), + Entry::Merged { parent: 22 }, + // row 6 + Entry::Cell(sample_cell()), + Entry::Merged { parent: 21 }, + Entry::Cell(sample_cell()), + Entry::Cell(sample_cell()), + // row 7 (adjacent rowspans covering the whole row) + Entry::Cell(cell_with_colspan_rowspan(2, 2)), + Entry::Merged { parent: 28 }, + Entry::Cell(cell_with_colspan_rowspan(2, 2)), + Entry::Merged { parent: 30 }, + // row 8 + Entry::Merged { parent: 28 }, + Entry::Merged { parent: 28 }, + Entry::Merged { parent: 30 }, + Entry::Merged { parent: 30 }, + ]; + CellGrid::new_internal( + Axes::with_x(&[Sizing::Auto; COLS]), + if gutters { + Axes::new(&[Sizing::Auto; COLS - 1], &[Sizing::Auto; ROWS - 1]) + } else { + Axes::default() + }, + vec![], + vec![], + None, + None, + entries, + ) + } + + #[test] + fn test_hline_splitting_without_gutter() { + let stroke = Arc::new(Stroke::default()); + let grid = sample_grid_for_hlines(false); + let columns = &[Abs::pt(1.), Abs::pt(2.), Abs::pt(4.), Abs::pt(8.)]; + // Assume all rows would be drawn in the same region, and are available. + let rows = grid + .rows + .iter() + .enumerate() + .map(|(y, _)| RowPiece { height: Abs::pt(f64::from(2u32.pow(y as u32))), y }) + .collect::<Vec<_>>(); + let expected_hline_splits = &[ + // top border + vec![LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(0.), + length: Abs::pt(1. + 2. + 4. + 8.), + priority: StrokePriority::GridStroke, + }], + // interrupted a few times by rowspans + vec![LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(1.), + length: Abs::pt(2.), + priority: StrokePriority::GridStroke, + }], + vec![LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(0.), + length: Abs::pt(1. + 2. + 4. + 8.), + priority: StrokePriority::GridStroke, + }], + vec![LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(0.), + length: Abs::pt(1. + 2. + 4. + 8.), + priority: StrokePriority::GridStroke, + }], + // interrupted every time by rowspans + vec![], + vec![LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(0.), + length: Abs::pt(1. + 2. + 4. + 8.), + priority: StrokePriority::GridStroke, + }], + // interrupted once by rowspan + vec![ + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(0.), + length: Abs::pt(1.), + priority: StrokePriority::GridStroke, + }, + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(1. + 2.), + length: Abs::pt(4. + 8.), + priority: StrokePriority::GridStroke, + }, + ], + vec![LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(0.), + length: Abs::pt(1. + 2. + 4. + 8.), + priority: StrokePriority::GridStroke, + }], + // interrupted every time by successive rowspans + vec![], + // bottom border + vec![LineSegment { + stroke, + offset: Abs::pt(0.), + length: Abs::pt(1. + 2. + 4. + 8.), + priority: StrokePriority::GridStroke, + }], + ]; + for (y, expected_splits) in expected_hline_splits.iter().enumerate() { + let tracks = columns.iter().copied().enumerate(); + assert_eq!( + expected_splits, + &generate_line_segments(&grid, tracks, y, &[], |grid, y, x, stroke| { + hline_stroke_at_column( + grid, + &rows, + y.checked_sub(1), + true, + y, + x, + stroke, + ) + }) + .collect::<Vec<_>>(), + ); + } + } + + #[test] + fn test_hline_splitting_with_gutter_and_explicit_hlines() { + let stroke = Arc::new(Stroke::default()); + let grid = sample_grid_for_hlines(true); + let columns = &[ + Abs::pt(1.0), + Abs::pt(2.0), + Abs::pt(4.0), + Abs::pt(8.0), + Abs::pt(16.0), + Abs::pt(32.0), + Abs::pt(64.0), + ]; + // Assume all rows would be drawn in the same region, and are available. + let rows = grid + .rows + .iter() + .enumerate() + .map(|(y, _)| RowPiece { height: Abs::pt(f64::from(2u32.pow(y as u32))), y }) + .collect::<Vec<_>>(); + let expected_hline_splits = &[ + // top border + vec![LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(0.), + length: Abs::pt(1. + 2. + 4. + 8. + 16. + 32. + 64.), + priority: StrokePriority::ExplicitLine, + }], + // gutter line below + // interrupted a few times by rowspans + vec![LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(1.), + length: Abs::pt(2. + 4. + 8.), + priority: StrokePriority::ExplicitLine, + }], + // interrupted a few times by rowspans + vec![LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(1.), + length: Abs::pt(2. + 4. + 8.), + priority: StrokePriority::ExplicitLine, + }], + // gutter line below + vec![LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(0.), + length: Abs::pt(1. + 2. + 4. + 8. + 16. + 32. + 64.), + priority: StrokePriority::ExplicitLine, + }], + vec![LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(0.), + length: Abs::pt(1. + 2. + 4. + 8. + 16. + 32. + 64.), + priority: StrokePriority::ExplicitLine, + }], + // gutter line below + vec![LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(0.), + length: Abs::pt(1. + 2. + 4. + 8. + 16. + 32. + 64.), + priority: StrokePriority::ExplicitLine, + }], + vec![LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(0.), + length: Abs::pt(1. + 2. + 4. + 8. + 16. + 32. + 64.), + priority: StrokePriority::ExplicitLine, + }], + // gutter line below + // interrupted every time by rowspans + vec![], + // interrupted every time by rowspans + vec![], + // gutter line below + vec![LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(0.), + length: Abs::pt(1. + 2. + 4. + 8. + 16. + 32. + 64.), + priority: StrokePriority::ExplicitLine, + }], + vec![LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(0.), + length: Abs::pt(1. + 2. + 4. + 8. + 16. + 32. + 64.), + priority: StrokePriority::ExplicitLine, + }], + // gutter line below + // interrupted once by rowspan + vec![ + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(0.), + length: Abs::pt(1. + 2.), + priority: StrokePriority::ExplicitLine, + }, + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(1. + 2. + 4.), + length: Abs::pt(8. + 16. + 32. + 64.), + priority: StrokePriority::ExplicitLine, + }, + ], + // interrupted once by rowspan + vec![ + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(0.), + length: Abs::pt(1. + 2.), + priority: StrokePriority::ExplicitLine, + }, + LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(1. + 2. + 4.), + length: Abs::pt(8. + 16. + 32. + 64.), + priority: StrokePriority::ExplicitLine, + }, + ], + // gutter line below + vec![LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(0.), + length: Abs::pt(1. + 2. + 4. + 8. + 16. + 32. + 64.), + priority: StrokePriority::ExplicitLine, + }], + vec![LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(0.), + length: Abs::pt(1. + 2. + 4. + 8. + 16. + 32. + 64.), + priority: StrokePriority::ExplicitLine, + }], + // gutter line below + // there are two consecutive rowspans, but the gutter column + // between them is free. + vec![LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(1. + 2. + 4.), + length: Abs::pt(8.), + priority: StrokePriority::ExplicitLine, + }], + vec![LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(1. + 2. + 4.), + length: Abs::pt(8.), + priority: StrokePriority::ExplicitLine, + }], + // bottom border + vec![LineSegment { + stroke: stroke.clone(), + offset: Abs::pt(0.), + length: Abs::pt(1. + 2. + 4. + 8. + 16. + 32. + 64.), + priority: StrokePriority::ExplicitLine, + }], + ]; + for (y, expected_splits) in expected_hline_splits.iter().enumerate() { + let tracks = columns.iter().copied().enumerate(); + assert_eq!( + expected_splits, + &generate_line_segments( + &grid, + tracks, + y, + &[ + Line { + index: y, + start: 0, + end: None, + stroke: Some(stroke.clone()), + position: LinePosition::Before + }, + Line { + index: y, + start: 0, + end: None, + stroke: Some(stroke.clone()), + position: LinePosition::After + }, + ], + |grid, y, x, stroke| hline_stroke_at_column( + grid, + &rows, + y.checked_sub(1), + true, + y, + x, + stroke + ) + ) + .collect::<Vec<_>>(), + ); + } + } + + #[test] + fn test_hline_splitting_considers_absent_rows() { + let grid = sample_grid_for_hlines(false); + let columns = &[Abs::pt(1.), Abs::pt(2.), Abs::pt(4.), Abs::pt(8.)]; + // Assume row 3 is absent (even though there's a rowspan between rows + // 3 and 4) + // This can happen if it is an auto row which turns out to be fully + // empty. + let rows = grid + .rows + .iter() + .enumerate() + .filter(|(y, _)| *y != 3) + .map(|(y, _)| RowPiece { height: Abs::pt(f64::from(2u32.pow(y as u32))), y }) + .collect::<Vec<_>>(); + + // Hline above row 4 is no longer blocked, since the rowspan is now + // effectively spanning just one row (at least, visibly). + assert_eq!( + &vec![LineSegment { + stroke: Arc::new(Stroke::default()), + offset: Abs::pt(0.), + length: Abs::pt(1. + 2. + 4. + 8.), + priority: StrokePriority::GridStroke + }], + &generate_line_segments( + &grid, + columns.iter().copied().enumerate(), + 4, + &[], + |grid, y, x, stroke| hline_stroke_at_column( + grid, + &rows, + if y == 4 { Some(2) } else { y.checked_sub(1) }, + true, + y, + x, + stroke + ) + ) + .collect::<Vec<_>>() + ); + } +} diff --git a/crates/typst-layout/src/grid/mod.rs b/crates/typst-layout/src/grid/mod.rs new file mode 100644 index 00000000..769bef8c --- /dev/null +++ b/crates/typst-layout/src/grid/mod.rs @@ -0,0 +1,416 @@ +mod cells; +mod layouter; +mod lines; +mod repeated; +mod rowspans; + +pub use self::cells::{Cell, CellGrid}; +pub use self::layouter::GridLayouter; + +use std::num::NonZeroUsize; +use std::sync::Arc; + +use ecow::eco_format; +use typst_library::diag::{SourceResult, Trace, Tracepoint}; +use typst_library::engine::Engine; +use typst_library::foundations::{Fold, Packed, Smart, StyleChain}; +use typst_library::introspection::Locator; +use typst_library::layout::{ + Abs, Alignment, Axes, Dir, Fragment, GridCell, GridChild, GridElem, GridItem, Length, + OuterHAlignment, OuterVAlignment, Regions, Rel, Sides, +}; +use typst_library::model::{TableCell, TableChild, TableElem, TableItem}; +use typst_library::text::TextElem; +use typst_library::visualize::{Paint, Stroke}; +use typst_syntax::Span; + +use self::cells::{ + LinePosition, ResolvableCell, ResolvableGridChild, ResolvableGridItem, +}; +use self::layouter::RowPiece; +use self::lines::{ + generate_line_segments, hline_stroke_at_column, vline_stroke_at_row, Line, + LineSegment, +}; +use self::repeated::{Footer, Header, Repeatable}; +use self::rowspans::{Rowspan, UnbreakableRowGroup}; + +/// Layout the grid. +#[typst_macros::time(span = elem.span())] +pub fn layout_grid( + elem: &Packed<GridElem>, + engine: &mut Engine, + locator: Locator, + styles: StyleChain, + regions: Regions, +) -> SourceResult<Fragment> { + let inset = elem.inset(styles); + let align = elem.align(styles); + let columns = elem.columns(styles); + let rows = elem.rows(styles); + let column_gutter = elem.column_gutter(styles); + let row_gutter = elem.row_gutter(styles); + let fill = elem.fill(styles); + let stroke = elem.stroke(styles); + + let tracks = Axes::new(columns.0.as_slice(), rows.0.as_slice()); + let gutter = Axes::new(column_gutter.0.as_slice(), row_gutter.0.as_slice()); + // Use trace to link back to the grid when a specific cell errors + let tracepoint = || Tracepoint::Call(Some(eco_format!("grid"))); + let resolve_item = |item: &GridItem| grid_item_to_resolvable(item, styles); + let children = elem.children().iter().map(|child| match child { + GridChild::Header(header) => ResolvableGridChild::Header { + repeat: header.repeat(styles), + span: header.span(), + items: header.children().iter().map(resolve_item), + }, + GridChild::Footer(footer) => ResolvableGridChild::Footer { + repeat: footer.repeat(styles), + span: footer.span(), + items: footer.children().iter().map(resolve_item), + }, + GridChild::Item(item) => { + ResolvableGridChild::Item(grid_item_to_resolvable(item, styles)) + } + }); + let grid = CellGrid::resolve( + tracks, + gutter, + locator, + children, + fill, + align, + &inset, + &stroke, + engine, + styles, + elem.span(), + ) + .trace(engine.world, tracepoint, elem.span())?; + + let layouter = GridLayouter::new(&grid, regions, styles, elem.span()); + + // Measure the columns and layout the grid row-by-row. + layouter.layout(engine) +} + +/// Layout the table. +#[typst_macros::time(span = elem.span())] +pub fn layout_table( + elem: &Packed<TableElem>, + engine: &mut Engine, + locator: Locator, + styles: StyleChain, + regions: Regions, +) -> SourceResult<Fragment> { + let inset = elem.inset(styles); + let align = elem.align(styles); + let columns = elem.columns(styles); + let rows = elem.rows(styles); + let column_gutter = elem.column_gutter(styles); + let row_gutter = elem.row_gutter(styles); + let fill = elem.fill(styles); + let stroke = elem.stroke(styles); + + let tracks = Axes::new(columns.0.as_slice(), rows.0.as_slice()); + let gutter = Axes::new(column_gutter.0.as_slice(), row_gutter.0.as_slice()); + // Use trace to link back to the table when a specific cell errors + let tracepoint = || Tracepoint::Call(Some(eco_format!("table"))); + let resolve_item = |item: &TableItem| table_item_to_resolvable(item, styles); + let children = elem.children().iter().map(|child| match child { + TableChild::Header(header) => ResolvableGridChild::Header { + repeat: header.repeat(styles), + span: header.span(), + items: header.children().iter().map(resolve_item), + }, + TableChild::Footer(footer) => ResolvableGridChild::Footer { + repeat: footer.repeat(styles), + span: footer.span(), + items: footer.children().iter().map(resolve_item), + }, + TableChild::Item(item) => { + ResolvableGridChild::Item(table_item_to_resolvable(item, styles)) + } + }); + let grid = CellGrid::resolve( + tracks, + gutter, + locator, + children, + fill, + align, + &inset, + &stroke, + engine, + styles, + elem.span(), + ) + .trace(engine.world, tracepoint, elem.span())?; + + let layouter = GridLayouter::new(&grid, regions, styles, elem.span()); + layouter.layout(engine) +} + +fn grid_item_to_resolvable( + item: &GridItem, + styles: StyleChain, +) -> ResolvableGridItem<Packed<GridCell>> { + match item { + GridItem::HLine(hline) => ResolvableGridItem::HLine { + y: hline.y(styles), + start: hline.start(styles), + end: hline.end(styles), + stroke: hline.stroke(styles), + span: hline.span(), + position: match hline.position(styles) { + OuterVAlignment::Top => LinePosition::Before, + OuterVAlignment::Bottom => LinePosition::After, + }, + }, + GridItem::VLine(vline) => ResolvableGridItem::VLine { + x: vline.x(styles), + start: vline.start(styles), + end: vline.end(styles), + stroke: vline.stroke(styles), + span: vline.span(), + position: match vline.position(styles) { + OuterHAlignment::Left if TextElem::dir_in(styles) == Dir::RTL => { + LinePosition::After + } + OuterHAlignment::Right if TextElem::dir_in(styles) == Dir::RTL => { + LinePosition::Before + } + OuterHAlignment::Start | OuterHAlignment::Left => LinePosition::Before, + OuterHAlignment::End | OuterHAlignment::Right => LinePosition::After, + }, + }, + GridItem::Cell(cell) => ResolvableGridItem::Cell(cell.clone()), + } +} + +fn table_item_to_resolvable( + item: &TableItem, + styles: StyleChain, +) -> ResolvableGridItem<Packed<TableCell>> { + match item { + TableItem::HLine(hline) => ResolvableGridItem::HLine { + y: hline.y(styles), + start: hline.start(styles), + end: hline.end(styles), + stroke: hline.stroke(styles), + span: hline.span(), + position: match hline.position(styles) { + OuterVAlignment::Top => LinePosition::Before, + OuterVAlignment::Bottom => LinePosition::After, + }, + }, + TableItem::VLine(vline) => ResolvableGridItem::VLine { + x: vline.x(styles), + start: vline.start(styles), + end: vline.end(styles), + stroke: vline.stroke(styles), + span: vline.span(), + position: match vline.position(styles) { + OuterHAlignment::Left if TextElem::dir_in(styles) == Dir::RTL => { + LinePosition::After + } + OuterHAlignment::Right if TextElem::dir_in(styles) == Dir::RTL => { + LinePosition::Before + } + OuterHAlignment::Start | OuterHAlignment::Left => LinePosition::Before, + OuterHAlignment::End | OuterHAlignment::Right => LinePosition::After, + }, + }, + TableItem::Cell(cell) => ResolvableGridItem::Cell(cell.clone()), + } +} + +impl ResolvableCell for Packed<TableCell> { + fn resolve_cell<'a>( + mut self, + x: usize, + y: usize, + fill: &Option<Paint>, + align: Smart<Alignment>, + inset: Sides<Option<Rel<Length>>>, + stroke: Sides<Option<Option<Arc<Stroke<Abs>>>>>, + breakable: bool, + locator: Locator<'a>, + styles: StyleChain, + ) -> Cell<'a> { + let cell = &mut *self; + let colspan = cell.colspan(styles); + let rowspan = cell.rowspan(styles); + let breakable = cell.breakable(styles).unwrap_or(breakable); + let fill = cell.fill(styles).unwrap_or_else(|| fill.clone()); + + let cell_stroke = cell.stroke(styles); + let stroke_overridden = + cell_stroke.as_ref().map(|side| matches!(side, Some(Some(_)))); + + // Using a typical 'Sides' fold, an unspecified side loses to a + // specified side. Additionally, when both are specified, an inner + // None wins over the outer Some, and vice-versa. When both are + // specified and Some, fold occurs, which, remarkably, leads to an Arc + // clone. + // + // In the end, we flatten because, for layout purposes, an unspecified + // cell stroke is the same as specifying 'none', so we equate the two + // concepts. + let stroke = cell_stroke.fold(stroke).map(Option::flatten); + cell.push_x(Smart::Custom(x)); + cell.push_y(Smart::Custom(y)); + cell.push_fill(Smart::Custom(fill.clone())); + cell.push_align(match align { + Smart::Custom(align) => { + Smart::Custom(cell.align(styles).map_or(align, |inner| inner.fold(align))) + } + // Don't fold if the table is using outer alignment. Use the + // cell's alignment instead (which, in the end, will fold with + // the outer alignment when it is effectively displayed). + Smart::Auto => cell.align(styles), + }); + cell.push_inset(Smart::Custom( + cell.inset(styles).map_or(inset, |inner| inner.fold(inset)), + )); + cell.push_stroke( + // Here we convert the resolved stroke to a regular stroke, however + // with resolved units (that is, 'em' converted to absolute units). + // We also convert any stroke unspecified by both the cell and the + // outer stroke ('None' in the folded stroke) to 'none', that is, + // all sides are present in the resulting Sides object accessible + // by show rules on table cells. + stroke.as_ref().map(|side| { + Some(side.as_ref().map(|cell_stroke| { + Arc::new((**cell_stroke).clone().map(Length::from)) + })) + }), + ); + cell.push_breakable(Smart::Custom(breakable)); + Cell { + body: self.pack(), + locator, + fill, + colspan, + rowspan, + stroke, + stroke_overridden, + breakable, + } + } + + fn x(&self, styles: StyleChain) -> Smart<usize> { + (**self).x(styles) + } + + fn y(&self, styles: StyleChain) -> Smart<usize> { + (**self).y(styles) + } + + fn colspan(&self, styles: StyleChain) -> NonZeroUsize { + (**self).colspan(styles) + } + + fn rowspan(&self, styles: StyleChain) -> NonZeroUsize { + (**self).rowspan(styles) + } + + fn span(&self) -> Span { + Packed::span(self) + } +} + +impl ResolvableCell for Packed<GridCell> { + fn resolve_cell<'a>( + mut self, + x: usize, + y: usize, + fill: &Option<Paint>, + align: Smart<Alignment>, + inset: Sides<Option<Rel<Length>>>, + stroke: Sides<Option<Option<Arc<Stroke<Abs>>>>>, + breakable: bool, + locator: Locator<'a>, + styles: StyleChain, + ) -> Cell<'a> { + let cell = &mut *self; + let colspan = cell.colspan(styles); + let rowspan = cell.rowspan(styles); + let breakable = cell.breakable(styles).unwrap_or(breakable); + let fill = cell.fill(styles).unwrap_or_else(|| fill.clone()); + + let cell_stroke = cell.stroke(styles); + let stroke_overridden = + cell_stroke.as_ref().map(|side| matches!(side, Some(Some(_)))); + + // Using a typical 'Sides' fold, an unspecified side loses to a + // specified side. Additionally, when both are specified, an inner + // None wins over the outer Some, and vice-versa. When both are + // specified and Some, fold occurs, which, remarkably, leads to an Arc + // clone. + // + // In the end, we flatten because, for layout purposes, an unspecified + // cell stroke is the same as specifying 'none', so we equate the two + // concepts. + let stroke = cell_stroke.fold(stroke).map(Option::flatten); + cell.push_x(Smart::Custom(x)); + cell.push_y(Smart::Custom(y)); + cell.push_fill(Smart::Custom(fill.clone())); + cell.push_align(match align { + Smart::Custom(align) => { + Smart::Custom(cell.align(styles).map_or(align, |inner| inner.fold(align))) + } + // Don't fold if the grid is using outer alignment. Use the + // cell's alignment instead (which, in the end, will fold with + // the outer alignment when it is effectively displayed). + Smart::Auto => cell.align(styles), + }); + cell.push_inset(Smart::Custom( + cell.inset(styles).map_or(inset, |inner| inner.fold(inset)), + )); + cell.push_stroke( + // Here we convert the resolved stroke to a regular stroke, however + // with resolved units (that is, 'em' converted to absolute units). + // We also convert any stroke unspecified by both the cell and the + // outer stroke ('None' in the folded stroke) to 'none', that is, + // all sides are present in the resulting Sides object accessible + // by show rules on grid cells. + stroke.as_ref().map(|side| { + Some(side.as_ref().map(|cell_stroke| { + Arc::new((**cell_stroke).clone().map(Length::from)) + })) + }), + ); + cell.push_breakable(Smart::Custom(breakable)); + Cell { + body: self.pack(), + locator, + fill, + colspan, + rowspan, + stroke, + stroke_overridden, + breakable, + } + } + + fn x(&self, styles: StyleChain) -> Smart<usize> { + (**self).x(styles) + } + + fn y(&self, styles: StyleChain) -> Smart<usize> { + (**self).y(styles) + } + + fn colspan(&self, styles: StyleChain) -> NonZeroUsize { + (**self).colspan(styles) + } + + fn rowspan(&self, styles: StyleChain) -> NonZeroUsize { + (**self).rowspan(styles) + } + + fn span(&self) -> Span { + Packed::span(self) + } +} diff --git a/crates/typst-layout/src/grid/repeated.rs b/crates/typst-layout/src/grid/repeated.rs new file mode 100644 index 00000000..972179da --- /dev/null +++ b/crates/typst-layout/src/grid/repeated.rs @@ -0,0 +1,192 @@ +use typst_library::diag::SourceResult; +use typst_library::engine::Engine; +use typst_library::layout::{Abs, Axes, Frame, Regions}; + +use super::layouter::GridLayouter; +use super::rowspans::UnbreakableRowGroup; + +/// A repeatable grid header. Starts at the first row. +pub struct Header { + /// The index after the last row included in this header. + pub end: usize, +} + +/// A repeatable grid footer. Stops at the last row. +pub struct Footer { + /// The first row included in this footer. + pub start: usize, +} + +/// A possibly repeatable grid object. +/// It still exists even when not repeatable, but must not have additional +/// considerations by grid layout, other than for consistency (such as making +/// a certain group of rows unbreakable). +pub enum Repeatable<T> { + Repeated(T), + NotRepeated(T), +} + +impl<T> Repeatable<T> { + /// Gets the value inside this repeatable, regardless of whether + /// it repeats. + pub fn unwrap(&self) -> &T { + match self { + Self::Repeated(repeated) => repeated, + Self::NotRepeated(not_repeated) => not_repeated, + } + } + + /// Returns `Some` if the value is repeated, `None` otherwise. + pub fn as_repeated(&self) -> Option<&T> { + match self { + Self::Repeated(repeated) => Some(repeated), + Self::NotRepeated(_) => None, + } + } +} + +impl<'a> GridLayouter<'a> { + /// Layouts the header's rows. + /// Skips regions as necessary. + pub fn layout_header( + &mut self, + header: &Header, + engine: &mut Engine, + disambiguator: usize, + ) -> SourceResult<()> { + let header_rows = + self.simulate_header(header, &self.regions, engine, disambiguator)?; + let mut skipped_region = false; + while self.unbreakable_rows_left == 0 + && !self.regions.size.y.fits(header_rows.height + self.footer_height) + && self.regions.may_progress() + { + // Advance regions without any output until we can place the + // header and the footer. + self.finish_region_internal(Frame::soft(Axes::splat(Abs::zero())), vec![]); + skipped_region = true; + } + + // Reset the header height for this region. + // It will be re-calculated when laying out each header row. + self.header_height = Abs::zero(); + + if let Some(Repeatable::Repeated(footer)) = &self.grid.footer { + if skipped_region { + // Simulate the footer again; the region's 'full' might have + // changed. + self.footer_height = self + .simulate_footer(footer, &self.regions, engine, disambiguator)? + .height; + } + } + + // Header is unbreakable. + // Thus, no risk of 'finish_region' being recursively called from + // within 'layout_row'. + self.unbreakable_rows_left += header.end; + for y in 0..header.end { + self.layout_row(y, engine, disambiguator)?; + } + Ok(()) + } + + /// Simulate the header's group of rows. + pub fn simulate_header( + &self, + header: &Header, + regions: &Regions<'_>, + engine: &mut Engine, + disambiguator: usize, + ) -> SourceResult<UnbreakableRowGroup> { + // Note that we assume the invariant that any rowspan in a header is + // fully contained within that header. Therefore, there won't be any + // unbreakable rowspans exceeding the header's rows, and we can safely + // assume that the amount of unbreakable rows following the first row + // in the header will be precisely the rows in the header. + self.simulate_unbreakable_row_group( + 0, + Some(header.end), + regions, + engine, + disambiguator, + ) + } + + /// Updates `self.footer_height` by simulating the footer, and skips to fitting region. + pub fn prepare_footer( + &mut self, + footer: &Footer, + engine: &mut Engine, + disambiguator: usize, + ) -> SourceResult<()> { + let footer_height = self + .simulate_footer(footer, &self.regions, engine, disambiguator)? + .height; + let mut skipped_region = false; + while self.unbreakable_rows_left == 0 + && !self.regions.size.y.fits(footer_height) + && self.regions.may_progress() + { + // Advance regions without any output until we can place the + // footer. + self.finish_region_internal(Frame::soft(Axes::splat(Abs::zero())), vec![]); + skipped_region = true; + } + + self.footer_height = if skipped_region { + // Simulate the footer again; the region's 'full' might have + // changed. + self.simulate_footer(footer, &self.regions, engine, disambiguator)? + .height + } else { + footer_height + }; + + Ok(()) + } + + /// Lays out all rows in the footer. + /// They are unbreakable. + pub fn layout_footer( + &mut self, + footer: &Footer, + engine: &mut Engine, + disambiguator: usize, + ) -> SourceResult<()> { + // Ensure footer rows have their own height available. + // Won't change much as we're creating an unbreakable row group + // anyway, so this is mostly for correctness. + self.regions.size.y += self.footer_height; + + let footer_len = self.grid.rows.len() - footer.start; + self.unbreakable_rows_left += footer_len; + for y in footer.start..self.grid.rows.len() { + self.layout_row(y, engine, disambiguator)?; + } + + Ok(()) + } + + // Simulate the footer's group of rows. + pub fn simulate_footer( + &self, + footer: &Footer, + regions: &Regions<'_>, + engine: &mut Engine, + disambiguator: usize, + ) -> SourceResult<UnbreakableRowGroup> { + // Note that we assume the invariant that any rowspan in a footer is + // fully contained within that footer. Therefore, there won't be any + // unbreakable rowspans exceeding the footer's rows, and we can safely + // assume that the amount of unbreakable rows following the first row + // in the footer will be precisely the rows in the footer. + self.simulate_unbreakable_row_group( + footer.start, + Some(self.grid.rows.len() - footer.start), + regions, + engine, + disambiguator, + ) + } +} diff --git a/crates/typst-layout/src/grid/rowspans.rs b/crates/typst-layout/src/grid/rowspans.rs new file mode 100644 index 00000000..03b4103f --- /dev/null +++ b/crates/typst-layout/src/grid/rowspans.rs @@ -0,0 +1,1217 @@ +use typst_library::diag::SourceResult; +use typst_library::engine::Engine; +use typst_library::foundations::Resolve; +use typst_library::layout::{Abs, Axes, Frame, Point, Region, Regions, Size, Sizing}; +use typst_utils::MaybeReverseIter; + +use super::layouter::{in_last_with_offset, points, Row, RowPiece}; +use super::repeated::Repeatable; +use super::{Cell, GridLayouter}; + +/// All information needed to layout a single rowspan. +pub struct Rowspan { + /// First column of this rowspan. + pub x: usize, + /// First row of this rowspan. + pub y: usize, + /// The disambiguator for laying out the cells. + pub disambiguator: usize, + /// Amount of rows spanned by the cell at (x, y). + pub rowspan: usize, + /// Whether all rows of the rowspan are part of an unbreakable row group. + /// This is true e.g. in headers and footers, regardless of what the user + /// specified for the parent cell's `breakable` field. + pub is_effectively_unbreakable: bool, + /// The horizontal offset of this rowspan in all regions. + pub dx: Abs, + /// The vertical offset of this rowspan in the first region. + pub dy: Abs, + /// The index of the first region this rowspan appears in. + pub first_region: usize, + /// The full height in the first region this rowspan appears in, for + /// relative sizing. + pub region_full: Abs, + /// The vertical space available for this rowspan in each region. + pub heights: Vec<Abs>, + /// The index of the largest resolved spanned row so far. + /// Once a spanned row is resolved and its height added to `heights`, this + /// number is increased. Older rows, even if repeated through e.g. a + /// header, will no longer contribute height to this rowspan. + /// + /// This is `None` if no spanned rows were resolved in `finish_region` yet. + pub max_resolved_row: Option<usize>, +} + +/// The output of the simulation of an unbreakable row group. +#[derive(Default)] +pub struct UnbreakableRowGroup { + /// The rows in this group of unbreakable rows. + /// Includes their indices and their predicted heights. + pub rows: Vec<(usize, Abs)>, + /// The total height of this row group. + pub height: Abs, +} + +/// Data used to measure a cell in an auto row. +pub struct CellMeasurementData<'layouter> { + /// The available width for the cell across all regions. + pub width: Abs, + /// The available height for the cell in its first region. + /// Infinite when the auto row is unbreakable. + pub height: Abs, + /// The backlog of heights available for the cell in later regions. + /// + /// When this is `None`, the `custom_backlog` field should be used instead. + /// That's because, otherwise, this field would have to contain a reference + /// to the `custom_backlog` field, which isn't possible in Rust without + /// resorting to unsafe hacks. + pub backlog: Option<&'layouter [Abs]>, + /// If the backlog needs to be built from scratch instead of reusing the + /// one at the current region, which is the case of a multi-region rowspan + /// (needs to join its backlog of already laid out heights with the current + /// backlog), then this vector will store the new backlog. + pub custom_backlog: Vec<Abs>, + /// The full height of the first region of the cell. + /// Infinite when the auto row is unbreakable. + pub full: Abs, + /// The height of the last repeated region to use in the measurement pod, + /// if any. + pub last: Option<Abs>, + /// The total height of previous rows spanned by the cell in the current + /// region (so far). + pub height_in_this_region: Abs, + /// The amount of previous regions spanned by the cell. + /// They are skipped for measurement purposes. + pub frames_in_previous_regions: usize, +} + +impl<'a> GridLayouter<'a> { + /// Layout a rowspan over the already finished regions, plus the current + /// region's frame and resolved rows, if it wasn't finished yet (because + /// we're being called from `finish_region`, but note that this function is + /// also called once after all regions are finished, in which case + /// `current_region_data` is `None`). + /// + /// We need to do this only once we already know the heights of all + /// spanned rows, which is only possible after laying out the last row + /// spanned by the rowspan (or some row immediately after the last one). + pub fn layout_rowspan( + &mut self, + rowspan_data: Rowspan, + current_region_data: Option<(&mut Frame, &[RowPiece])>, + engine: &mut Engine, + ) -> SourceResult<()> { + let Rowspan { + x, + y, + disambiguator, + rowspan, + is_effectively_unbreakable, + dx, + dy, + first_region, + region_full, + heights, + .. + } = rowspan_data; + let [first_height, backlog @ ..] = heights.as_slice() else { + // Nothing to layout. + return Ok(()); + }; + let first_column = self.rcols[x]; + let cell = self.grid.cell(x, y).unwrap(); + let width = self.cell_spanned_width(cell, x); + let dx = if self.is_rtl { dx - width + first_column } else { dx }; + + // Prepare regions. + let size = Size::new(width, *first_height); + let mut pod: Regions = Region::new(size, Axes::splat(true)).into(); + pod.backlog = backlog; + + if !is_effectively_unbreakable + && self.grid.rows[y..][..rowspan] + .iter() + .any(|spanned_row| spanned_row == &Sizing::Auto) + { + // If the rowspan spans an auto row and is breakable, it will see + // '100%' as the full page height, at least at its first region. + // This is consistent with how it is measured, and with how + // non-rowspan cells behave in auto rows. + pod.full = region_full; + } + + // Push the layouted frames directly into the finished frames. + let fragment = cell.layout(engine, disambiguator, self.styles, pod)?; + let (current_region, current_rrows) = current_region_data.unzip(); + for ((i, finished), frame) in self + .finished + .iter_mut() + .chain(current_region.into_iter()) + .skip(first_region) + .enumerate() + .zip(fragment) + { + let dy = if i == 0 { + // At first, we draw the rowspan starting at its expected + // vertical offset in the first region. + dy + } else { + // The rowspan continuation starts after the header (thus, + // at a position after the sum of the laid out header + // rows). + if let Some(Repeatable::Repeated(header)) = &self.grid.header { + let header_rows = self + .rrows + .get(i) + .map(Vec::as_slice) + .or(current_rrows) + .unwrap_or(&[]) + .iter() + .take_while(|row| row.y < header.end); + + header_rows.map(|row| row.height).sum() + } else { + // Without a header, start at the very top of the region. + Abs::zero() + } + }; + + finished.push_frame(Point::new(dx, dy), frame); + } + + Ok(()) + } + + /// Checks if a row contains the beginning of one or more rowspan cells. + /// If so, adds them to the rowspans vector. + pub fn check_for_rowspans(&mut self, disambiguator: usize, y: usize) { + // We will compute the horizontal offset of each rowspan in advance. + // For that reason, we must reverse the column order when using RTL. + let offsets = points(self.rcols.iter().copied().rev_if(self.is_rtl)); + for (x, dx) in (0..self.rcols.len()).rev_if(self.is_rtl).zip(offsets) { + let Some(cell) = self.grid.cell(x, y) else { + continue; + }; + let rowspan = self.grid.effective_rowspan_of_cell(cell); + if rowspan > 1 { + // Rowspan detected. We will lay it out later. + self.rowspans.push(Rowspan { + x, + y, + disambiguator, + rowspan, + // The field below will be updated in + // 'check_for_unbreakable_rows'. + is_effectively_unbreakable: !cell.breakable, + dx, + // The four fields below will be updated in 'finish_region'. + dy: Abs::zero(), + first_region: usize::MAX, + region_full: Abs::zero(), + heights: vec![], + max_resolved_row: None, + }); + } + } + } + + /// Checks if the upcoming rows will be grouped together under an + /// unbreakable row group, and, if so, advances regions until there is + /// enough space for them. This can be needed, for example, if there's an + /// unbreakable rowspan crossing those rows. + pub fn check_for_unbreakable_rows( + &mut self, + current_row: usize, + engine: &mut Engine, + ) -> SourceResult<()> { + if self.unbreakable_rows_left == 0 { + // By default, the amount of unbreakable rows starting at the + // current row is dynamic and depends on the amount of upcoming + // unbreakable cells (with or without a rowspan setting). + let mut amount_unbreakable_rows = None; + if let Some(Repeatable::NotRepeated(header)) = &self.grid.header { + if current_row < header.end { + // Non-repeated header, so keep it unbreakable. + amount_unbreakable_rows = Some(header.end); + } + } + if let Some(Repeatable::NotRepeated(footer)) = &self.grid.footer { + if current_row >= footer.start { + // Non-repeated footer, so keep it unbreakable. + amount_unbreakable_rows = Some(self.grid.rows.len() - footer.start); + } + } + + let row_group = self.simulate_unbreakable_row_group( + current_row, + amount_unbreakable_rows, + &self.regions, + engine, + 0, + )?; + + // Skip to fitting region. + while !self.regions.size.y.fits(row_group.height) + && !in_last_with_offset( + self.regions, + self.header_height + self.footer_height, + ) + { + self.finish_region(engine, false)?; + } + + // Update unbreakable rows left. + self.unbreakable_rows_left = row_group.rows.len(); + } + + if self.unbreakable_rows_left > 1 { + // Mark rowspans as effectively unbreakable where applicable + // (if all of their spanned rows would be in the same unbreakable + // row group). + // Not needed if only one unbreakable row is left, since, then, + // no rowspan will be effectively unbreakable, at least necessarily. + // Note that this function is called after 'check_for_rowspans' and + // potentially updates the amount of remaining unbreakable rows, so + // it wouldn't be accurate to only check for this condition in that + // function. We need to check here instead. + for rowspan_data in + self.rowspans.iter_mut().filter(|rowspan| rowspan.y == current_row) + { + rowspan_data.is_effectively_unbreakable |= + self.unbreakable_rows_left >= rowspan_data.rowspan; + } + } + + Ok(()) + } + + /// Simulates a group of unbreakable rows, starting with the index of the + /// first row in the group. If `amount_unbreakable_rows` is `None`, keeps + /// adding rows to the group until none have unbreakable cells in common. + /// Otherwise, adds specifically the given amount of rows to the group. + /// + /// This is used to figure out how much height the next unbreakable row + /// group (if any) needs. + pub fn simulate_unbreakable_row_group( + &self, + first_row: usize, + amount_unbreakable_rows: Option<usize>, + regions: &Regions<'_>, + engine: &mut Engine, + disambiguator: usize, + ) -> SourceResult<UnbreakableRowGroup> { + let mut row_group = UnbreakableRowGroup::default(); + let mut unbreakable_rows_left = amount_unbreakable_rows.unwrap_or(0); + for (y, row) in self.grid.rows.iter().enumerate().skip(first_row) { + if amount_unbreakable_rows.is_none() { + // When we don't set a fixed amount of unbreakable rows, + // determine the amount based on the rowspan of unbreakable + // cells in rows. + let additional_unbreakable_rows = self.check_for_unbreakable_cells(y); + unbreakable_rows_left = + unbreakable_rows_left.max(additional_unbreakable_rows); + } + if unbreakable_rows_left == 0 { + // This check is in case the first row does not have any + // unbreakable cells. Therefore, no unbreakable row group + // is formed. + break; + } + let height = match row { + Sizing::Rel(v) => v.resolve(self.styles).relative_to(regions.base().y), + + // No need to pass the regions to the auto row, since + // unbreakable auto rows are always measured with infinite + // height, ignore backlog, and do not invoke the rowspan + // simulation procedure at all. + Sizing::Auto => self + .measure_auto_row( + engine, + disambiguator, + y, + false, + unbreakable_rows_left, + Some(&row_group), + )? + .unwrap() + .first() + .copied() + .unwrap_or_else(Abs::zero), + // Fractional rows don't matter when calculating the space + // needed for unbreakable rows + Sizing::Fr(_) => Abs::zero(), + }; + row_group.height += height; + row_group.rows.push((y, height)); + unbreakable_rows_left -= 1; + if unbreakable_rows_left == 0 { + // This second check is necessary so we can tell distinct + // but consecutive unbreakable row groups apart. If the + // unbreakable row group ended at this row, we stop before + // checking the next one. + break; + } + } + + Ok(row_group) + } + + /// Checks if one or more of the cells at the given row are unbreakable. + /// If so, returns the largest rowspan among the unbreakable cells; + /// the spanned rows must, as a result, be laid out in the same region. + pub fn check_for_unbreakable_cells(&self, y: usize) -> usize { + (0..self.grid.cols.len()) + .filter_map(|x| self.grid.cell(x, y)) + .filter(|cell| !cell.breakable) + .map(|cell| self.grid.effective_rowspan_of_cell(cell)) + .max() + .unwrap_or(0) + } + + /// Used by `measure_auto_row` to gather data needed to measure the cell. + pub fn prepare_auto_row_cell_measurement( + &self, + parent: Axes<usize>, + cell: &Cell, + breakable: bool, + row_group_data: Option<&UnbreakableRowGroup>, + ) -> CellMeasurementData<'_> { + let rowspan = self.grid.effective_rowspan_of_cell(cell); + + // This variable is used to construct a custom backlog if the cell + // is a rowspan, or if headers or footers are used. When measuring, we + // join the heights from previous regions to the current backlog to + // form a rowspan's expected backlog. We also subtract the header's + // and footer's heights from all regions. + let mut custom_backlog: Vec<Abs> = vec![]; + + // This function is used to subtract the expected header and footer + // height from each upcoming region size in the current backlog and + // last region. + let mut subtract_header_footer_height_from_regions = || { + // Only breakable auto rows need to update their backlogs based + // on the presence of a header or footer, given that unbreakable + // auto rows don't depend on the backlog, as they only span one + // region. + if breakable + && (matches!(self.grid.header, Some(Repeatable::Repeated(_))) + || matches!(self.grid.footer, Some(Repeatable::Repeated(_)))) + { + // Subtract header and footer height from all upcoming regions + // when measuring the cell, including the last repeated region. + // + // This will update the 'custom_backlog' vector with the + // updated heights of the upcoming regions. + let mapped_regions = self.regions.map(&mut custom_backlog, |size| { + Size::new(size.x, size.y - self.header_height - self.footer_height) + }); + + // Callees must use the custom backlog instead of the current + // backlog, so we return 'None'. + return (None, mapped_regions.last); + } + + // No need to change the backlog or last region. + (Some(self.regions.backlog), self.regions.last) + }; + + // Each declaration, from top to bottom: + // 1. The height available to the cell in the first region. + // Usually, this will just be the size remaining in the current + // region. + // 2. The backlog of upcoming region heights to specify as + // available to the cell. + // 3. The full height of the first region of the cell. + // 4. Height of the last repeated region to use in the measurement pod. + // 5. The total height of the cell covered by previously spanned + // rows in this region. This is used by rowspans to be able to tell + // how much the auto row needs to expand. + // 6. The amount of frames laid out by this cell in previous + // regions. When the cell isn't a rowspan, this is always zero. + // These frames are skipped after measuring. + let height; + let backlog; + let full; + let last; + let height_in_this_region; + let frames_in_previous_regions; + + if rowspan == 1 { + // Not a rowspan, so the cell only occupies this row. Therefore: + // 1. When we measure the cell below, use the available height + // remaining in the region as the height it has available. + // However, if the auto row is unbreakable, measure with infinite + // height instead to see how much content expands. + // 2. Use the region's backlog and last region when measuring, + // however subtract the expected header and footer heights from + // each upcoming size, if there is a header or footer. + // 3. Use the same full region height. + // 4. No height occupied by this cell in this region so far. + // 5. Yes, this cell started in this region. + height = if breakable { self.regions.size.y } else { Abs::inf() }; + (backlog, last) = subtract_header_footer_height_from_regions(); + full = if breakable { self.regions.full } else { Abs::inf() }; + height_in_this_region = Abs::zero(); + frames_in_previous_regions = 0; + } else { + // Height of the rowspan covered by spanned rows in the current + // region. + let laid_out_height: Abs = self + .lrows + .iter() + .filter_map(|row| match row { + Row::Frame(frame, y, _) + if (parent.y..parent.y + rowspan).contains(y) => + { + Some(frame.height()) + } + // Either we have a row outside of the rowspan, or a + // fractional row, whose size we can't really guess. + _ => None, + }) + .sum(); + + // If we're currently simulating an unbreakable row group, also + // consider the height of previously spanned rows which are in + // the row group but not yet laid out. + let unbreakable_height: Abs = row_group_data + .into_iter() + .flat_map(|row_group| &row_group.rows) + .filter(|(y, _)| (parent.y..parent.y + rowspan).contains(y)) + .map(|(_, height)| height) + .sum(); + + height_in_this_region = laid_out_height + unbreakable_height; + + // Ensure we will measure the rowspan with the correct heights. + // For that, we will gather the total height spanned by this + // rowspan in previous regions. + if let Some((rowspan_full, [rowspan_height, rowspan_other_heights @ ..])) = + self.rowspans + .iter() + .find(|data| data.x == parent.x && data.y == parent.y) + .map(|data| (data.region_full, &*data.heights)) + { + // The rowspan started in a previous region (as it already + // has at least one region height). + // Therefore, its initial height will be the height in its + // first spanned region, and the backlog will be the + // remaining heights, plus the current region's size, plus + // the current backlog. + frames_in_previous_regions = rowspan_other_heights.len() + 1; + + let heights_up_to_current_region = rowspan_other_heights + .iter() + .copied() + .chain(std::iter::once(if breakable { + self.initial.y - self.header_height - self.footer_height + } else { + // When measuring unbreakable auto rows, infinite + // height is available for content to expand. + Abs::inf() + })); + + custom_backlog = if breakable { + // This auto row is breakable. Therefore, join the + // rowspan's already laid out heights with the current + // region's height and current backlog to ensure a good + // level of accuracy in the measurements. + let backlog = self + .regions + .backlog + .iter() + .map(|&size| size - self.header_height - self.footer_height); + + heights_up_to_current_region.chain(backlog).collect::<Vec<_>>() + } else { + // No extra backlog if this is an unbreakable auto row. + // Ensure, when measuring, that the rowspan can be laid + // out through all spanned rows which were already laid + // out so far, but don't go further than this region. + heights_up_to_current_region.collect::<Vec<_>>() + }; + + height = *rowspan_height; + backlog = None; + full = rowspan_full; + last = self + .regions + .last + .map(|size| size - self.header_height - self.footer_height); + } else { + // The rowspan started in the current region, as its vector + // of heights in regions is currently empty. + // Therefore, the initial height it has available will be + // the current available size, plus the size spanned in + // previous rows in this region (and/or unbreakable row + // group, if it's being simulated). + // The backlog and full will be that of the current region. + // However, use infinite height instead if we're measuring an + // unbreakable auto row. + height = if breakable { + height_in_this_region + self.regions.size.y + } else { + Abs::inf() + }; + (backlog, last) = subtract_header_footer_height_from_regions(); + full = if breakable { self.regions.full } else { Abs::inf() }; + frames_in_previous_regions = 0; + } + } + + let width = self.cell_spanned_width(cell, parent.x); + CellMeasurementData { + width, + height, + backlog, + custom_backlog, + full, + last, + height_in_this_region, + frames_in_previous_regions, + } + } + + /// Used in `measure_auto_row` to prepare a rowspan's `sizes` vector. + /// Returns `true` if we'll need to run a simulation to more accurately + /// expand the auto row based on the rowspan's demanded size, or `false` + /// otherwise. + #[allow(clippy::too_many_arguments)] + pub fn prepare_rowspan_sizes( + &self, + auto_row_y: usize, + sizes: &mut Vec<Abs>, + cell: &Cell, + parent_y: usize, + rowspan: usize, + unbreakable_rows_left: usize, + measurement_data: &CellMeasurementData<'_>, + ) -> bool { + if sizes.len() <= 1 + && sizes.first().map_or(true, |&first_frame_size| { + first_frame_size <= measurement_data.height_in_this_region + }) + { + // Ignore a rowspan fully covered by rows in previous + // regions and/or in the current region. + sizes.clear(); + return false; + } + if let Some(first_frame_size) = sizes.first_mut() { + // Subtract already covered height from the size requested + // by this rowspan to the auto row in the first region. + *first_frame_size = (*first_frame_size + - measurement_data.height_in_this_region) + .max(Abs::zero()); + } + + let last_spanned_row = parent_y + rowspan - 1; + + // When the rowspan is unbreakable, or all of its upcoming + // spanned rows are in the same unbreakable row group, its + // spanned gutter will certainly be in the same region as all + // of its other spanned rows, thus gutters won't be removed, + // and we can safely reduce how much the auto row expands by + // without using simulation. + let is_effectively_unbreakable_rowspan = + !cell.breakable || auto_row_y + unbreakable_rows_left > last_spanned_row; + + // If the rowspan doesn't end at this row and the grid has + // gutter, we will need to run a simulation to find out how + // much to expand this row by later. This is because gutters + // spanned by this rowspan might be removed if they appear + // around a pagebreak, so the auto row might have to expand a + // bit more to compensate for the missing gutter height. + // However, unbreakable rowspans aren't affected by that + // problem. + if auto_row_y != last_spanned_row + && !sizes.is_empty() + && self.grid.has_gutter + && !is_effectively_unbreakable_rowspan + { + return true; + } + + // We can only predict the resolved size of upcoming fixed-size + // rows, but not fractional rows. In the future, we might be + // able to simulate and circumvent the problem with fractional + // rows. Relative rows are currently always measured relative + // to the first region as well. + // We can ignore auto rows since this is the last spanned auto + // row. + let will_be_covered_height: Abs = self + .grid + .rows + .iter() + .skip(auto_row_y + 1) + .take(last_spanned_row - auto_row_y) + .map(|row| match row { + Sizing::Rel(v) => { + v.resolve(self.styles).relative_to(self.regions.base().y) + } + _ => Abs::zero(), + }) + .sum(); + + // Remove or reduce the sizes of the rowspan at the current or future + // regions where it will already be covered by further rows spanned by + // it. + subtract_end_sizes(sizes, will_be_covered_height); + + // No need to run a simulation for this rowspan. + false + } + + /// Performs a simulation to predict by how much height the last spanned + /// auto row will have to expand, given the current sizes of the auto row + /// in each region and the pending rowspans' data (parent Y, rowspan amount + /// and vector of requested sizes). + #[allow(clippy::too_many_arguments)] + pub fn simulate_and_measure_rowspans_in_auto_row( + &self, + y: usize, + resolved: &mut Vec<Abs>, + pending_rowspans: &[(usize, usize, Vec<Abs>)], + unbreakable_rows_left: usize, + row_group_data: Option<&UnbreakableRowGroup>, + mut disambiguator: usize, + engine: &mut Engine, + ) -> SourceResult<()> { + // To begin our simulation, we have to unify the sizes demanded by + // each rowspan into one simple vector of sizes, as if they were + // all a single rowspan. These sizes will be appended to + // 'resolved' once we finish our simulation. + let mut simulated_sizes: Vec<Abs> = vec![]; + let last_resolved_size = resolved.last().copied(); + let mut max_spanned_row = y; + for (parent_y, rowspan, sizes) in pending_rowspans { + let mut sizes = sizes.iter(); + for (target, size) in resolved.iter_mut().zip(&mut sizes) { + // First, we update the already resolved sizes as required + // by this rowspan. No need to simulate this since the auto row + // will already expand throughout already resolved regions. + // Our simulation, therefore, won't otherwise change already + // resolved sizes, other than, perhaps, the last one (at the + // last currently resolved region, at which we can expand). + target.set_max(*size); + } + for (simulated_target, rowspan_size) in + simulated_sizes.iter_mut().zip(&mut sizes) + { + // The remaining sizes are exclusive to rowspans, since + // other cells in this row didn't require as many regions. + // We will perform a simulation to see how much of these sizes + // does the auto row actually need to expand by, and how much + // is already covered by upcoming rows spanned by the rowspans. + simulated_target.set_max(*rowspan_size); + } + simulated_sizes.extend(sizes); + max_spanned_row = max_spanned_row.max(parent_y + rowspan - 1); + } + if simulated_sizes.is_empty() && resolved.last() == last_resolved_size.as_ref() { + // The rowspans already fit in the already resolved sizes. + // No need for simulation. + return Ok(()); + } + + // We will be updating the last resolved size (expanding the auto + // row) as needed. Therefore, consider it as part of the simulation. + // At the end, we push it back. + if let Some(modified_last_resolved_size) = resolved.pop() { + simulated_sizes.insert(0, modified_last_resolved_size); + } + + // Prepare regions for simulation. + // If we're currently inside an unbreakable row group simulation, + // subtract the current row group height from the available space + // when simulating rowspans in said group. + let mut simulated_regions = self.regions; + simulated_regions.size.y -= + row_group_data.map_or(Abs::zero(), |row_group| row_group.height); + + for _ in 0..resolved.len() { + // Ensure we start at the region where we will expand the auto + // row. + // Note that we won't accidentally call '.next()' once more than + // desired (we won't skip the last resolved frame, where we will + // expand) because we popped the last resolved size from the + // resolved vector, above. + simulated_regions.next(); + disambiguator += 1; + + // Subtract the initial header and footer height, since that's the + // height we used when subtracting from the region backlog's + // heights while measuring cells. + simulated_regions.size.y -= self.header_height + self.footer_height; + } + + if let Some(original_last_resolved_size) = last_resolved_size { + // We're now at the (current) last region of this auto row. + // Consider resolved height as already taken space. + simulated_regions.size.y -= original_last_resolved_size; + } + + // Now we run the simulation to check how much the auto row needs to + // grow to ensure that rowspans have the height they need. + let simulations_stabilized = self.run_rowspan_simulation( + y, + max_spanned_row, + simulated_regions, + &mut simulated_sizes, + engine, + last_resolved_size, + unbreakable_rows_left, + disambiguator, + )?; + + if !simulations_stabilized { + // If the simulation didn't stabilize above, we will just pretend + // all gutters were removed, as a best effort. That means the auto + // row will expand more than it normally should, but there isn't + // much we can do. + let will_be_covered_height = self + .grid + .rows + .iter() + .enumerate() + .skip(y + 1) + .take(max_spanned_row - y) + .filter(|(y, _)| !self.grid.is_gutter_track(*y)) + .map(|(_, row)| match row { + Sizing::Rel(v) => { + v.resolve(self.styles).relative_to(self.regions.base().y) + } + _ => Abs::zero(), + }) + .sum(); + + subtract_end_sizes(&mut simulated_sizes, will_be_covered_height); + } + + resolved.extend(simulated_sizes); + + Ok(()) + } + + /// Performs a simulation of laying out multiple rowspans (consolidated + /// into a single vector of simulated sizes) ending in a certain auto row + /// in order to find out how much the auto row will need to expand to cover + /// the rowspans' requested sizes, considering how much size has been + /// covered by other rows and by gutter between rows. + /// + /// For example, for a rowspan cell containing a block of 8pt of height + /// spanning rows (1pt, auto, 0.5pt, 0.5pt), with a gutter of 1pt between + /// each row, we have that the rows it spans provide 1pt + 0.5pt + 0.5pt + /// = 2pt of height, plus 1pt + 1pt + 1pt = 3pt of gutter, with a total of + /// 2pt + 3pt = 5pt of height already covered by fixed-size rows and + /// gutters. This means that the auto row must (under normal conditions) + /// expand by 3pt (8pt - 5pt) so that the rowspan has enough height across + /// rows to fully draw its contents. + /// + /// However, it's possible that the last row is sent to the next page to + /// respect a pagebreak, and then the 1pt gutter before it disappears. This + /// would lead to our rowspan having a height of 7pt available if we fail + /// to predict this situation when measuring the auto row. + /// + /// The algorithm below will, thus, attempt to simulate the layout of each + /// spanned row, considering the space available in the current page and in + /// upcoming pages (through the region backlog), in order to predict which + /// rows will be sent to a new page and thus have their preceding gutter + /// spacing removed (meaning the auto row has to grow a bit more). After + /// simulating, we subtract the total height spanned by upcoming rows and + /// gutter from the total rowspan height - this will be how much our auto + /// row has to expand. We then simulate again to check if, if the auto row + /// expanded by that amount, that would prompt the auto row to need to + /// expand even more, because expanding the auto row might cause some other + /// larger gutter spacing to disappear (leading to the rowspan having less + /// space available instead of more); if so, we update the amount to expand + /// and run the simulation again. Otherwise (if it should expand by the + /// same amount, meaning we predicted correctly, or by less, meaning the + /// auto row will be a bit larger than it should be, but that's a + /// compromise we're willing to accept), we conclude the simulation + /// (consider it stabilized) and return the result. + /// + /// Tries up to 5 times. If two consecutive simulations stabilize, then + /// we subtract the predicted expansion height ('amount_to_grow') from the + /// total height requested by rowspans (the 'requested_rowspan_height') to + /// obtain how much height is covered by upcoming rows, according to our + /// simulation, and the result of that operation is used to reduce or + /// remove heights from the end of the vector of simulated sizes, such that + /// the remaining heights are exactly how much the auto row should expand + /// by. Then, we return `true`. + /// + /// If the simulations don't stabilize (they return 5 different and + /// successively larger values), aborts and returns `false`. + #[allow(clippy::too_many_arguments)] + fn run_rowspan_simulation( + &self, + y: usize, + max_spanned_row: usize, + mut simulated_regions: Regions<'_>, + simulated_sizes: &mut Vec<Abs>, + engine: &mut Engine, + last_resolved_size: Option<Abs>, + unbreakable_rows_left: usize, + mut disambiguator: usize, + ) -> SourceResult<bool> { + // The max amount this row can expand will be the total size requested + // by rowspans which was not yet resolved. It is worth noting that, + // earlier, we pushed the last resolved size to 'simulated_sizes' as + // row expansion starts with it, so it's possible a rowspan requested + // to extend that size (we will see, through the simulation, if that's + // needed); however, we must subtract that resolved size from the total + // sum of sizes, as it was already resolved and thus the auto row will + // already grow by at least that much in the last resolved region (we + // would grow by the same size twice otherwise). + let requested_rowspan_height = + simulated_sizes.iter().sum::<Abs>() - last_resolved_size.unwrap_or_default(); + + // The amount the row will effectively grow by, according to the latest + // simulation. + let mut amount_to_grow = Abs::zero(); + + // Try to simulate up to 5 times. If it doesn't stabilize at a value + // which, when used and combined with upcoming spanned rows, covers all + // of the requested rowspan height, we give up. + for _attempt in 0..5 { + let rowspan_simulator = RowspanSimulator::new( + disambiguator, + simulated_regions, + self.header_height, + self.footer_height, + ); + + let total_spanned_height = rowspan_simulator.simulate_rowspan_layout( + y, + max_spanned_row, + amount_to_grow, + requested_rowspan_height, + unbreakable_rows_left, + self, + engine, + )?; + + // If the total height spanned by upcoming spanned rows plus the + // current amount we predict the auto row will have to grow (from + // the previous iteration) are larger than the size requested by + // rowspans, this means the auto row will grow enough in order to + // cover the requested rowspan height, so we stop the simulation. + // + // If that's not yet the case, we will simulate again and make the + // auto row grow even more, and do so until either the auto row has + // grown enough, or we tried to do so over 5 times. + // + // A flaw of this approach is that we consider rowspans' content to + // be contiguous. That is, we treat rowspans' requested heights as + // a simple number, instead of properly using the vector of + // requested heights in each region. This can lead to some + // weirdness when using multi-page rowspans with content that + // reacts to the amount of space available, including paragraphs. + // However, this is probably the best we can do for now. + if (total_spanned_height + amount_to_grow).fits(requested_rowspan_height) { + // Reduce sizes by the amount to be covered by upcoming spanned + // rows, which is equivalent to the amount that we don't grow. + // We reduce from the end as that's where the spanned rows will + // cover. The remaining sizes will all be covered by the auto + // row instead (which will grow by those sizes). + subtract_end_sizes( + simulated_sizes, + requested_rowspan_height - amount_to_grow, + ); + + if let Some(last_resolved_size) = last_resolved_size { + // Ensure the first simulated size is at least as large as + // the last resolved size (its initial value). As it was + // already resolved before, we must not reduce below the + // resolved size to avoid problems with non-rowspan cells. + if let Some(first_simulated_size) = simulated_sizes.first_mut() { + first_simulated_size.set_max(last_resolved_size); + } else { + simulated_sizes.push(last_resolved_size); + } + } + + return Ok(true); + } + + // For the next simulation, we will test if the auto row can grow + // by precisely how much rowspan height is not covered by upcoming + // spanned rows, according to the current simulation. + // We know that the new amount to grow is larger (and thus the + // auto row only expands between each simulation), because we + // checked above if + // 'total_spanned_height + (now old_)amount_to_grow >= requested_rowspan_height', + // which was false, so it holds that + // 'total_spanned_height + old_amount_to_grow < requested_rowspan_height' + // Thus, + // 'old_amount_to_grow < requested_rowspan_height - total_spanned_height' + // Therefore, by definition, 'old_amount_to_grow < amount_to_grow'. + let old_amount_to_grow = std::mem::replace( + &mut amount_to_grow, + requested_rowspan_height - total_spanned_height, + ); + + // We advance the 'regions' variable accordingly, so that, in the + // next simulation, we consider already grown space as final. + // That is, we effectively simulate how rows would be placed if the + // auto row grew by precisely the new value of 'amount_to_grow'. + let mut extra_amount_to_grow = amount_to_grow - old_amount_to_grow; + while extra_amount_to_grow > Abs::zero() + && simulated_regions.size.y < extra_amount_to_grow + { + extra_amount_to_grow -= simulated_regions.size.y.max(Abs::zero()); + simulated_regions.next(); + simulated_regions.size.y -= self.header_height + self.footer_height; + disambiguator += 1; + } + simulated_regions.size.y -= extra_amount_to_grow; + } + + // Simulation didn't succeed in 5 attempts. + Ok(false) + } +} + +/// Auxiliary structure holding state during rowspan simulation. +struct RowspanSimulator<'a> { + /// The number of finished regions. + finished: usize, + /// The state of regions during the simulation. + regions: Regions<'a>, + /// The height of the header in the currently simulated region. + header_height: Abs, + /// The height of the footer in the currently simulated region. + footer_height: Abs, + /// The total spanned height so far in the simulation. + total_spanned_height: Abs, + /// Height of the latest spanned gutter row in the simulation. + /// Zero if it was removed. + latest_spanned_gutter_height: Abs, +} + +impl<'a> RowspanSimulator<'a> { + /// Creates new rowspan simulation state with the given regions and initial + /// header and footer heights. Other fields should always start as zero. + fn new( + finished: usize, + regions: Regions<'a>, + header_height: Abs, + footer_height: Abs, + ) -> Self { + Self { + finished, + regions, + header_height, + footer_height, + total_spanned_height: Abs::zero(), + latest_spanned_gutter_height: Abs::zero(), + } + } + + /// Calculates the total spanned height of the rowspan. + /// Stops calculating if, at any point in the simulation, the value of + /// `total_spanned_height + amount_to_grow` becomes larger than + /// `requested_rowspan_height`, as the results are not going to become any + /// more useful after that point. + #[allow(clippy::too_many_arguments)] + fn simulate_rowspan_layout( + mut self, + y: usize, + max_spanned_row: usize, + amount_to_grow: Abs, + requested_rowspan_height: Abs, + mut unbreakable_rows_left: usize, + layouter: &GridLayouter<'_>, + engine: &mut Engine, + ) -> SourceResult<Abs> { + let spanned_rows = &layouter.grid.rows[y + 1..=max_spanned_row]; + for (offset, row) in spanned_rows.iter().enumerate() { + if (self.total_spanned_height + amount_to_grow).fits(requested_rowspan_height) + { + // Stop the simulation, as the combination of upcoming + // spanned rows (so far) and the current amount the auto + // row expands by has already fully covered the height the + // rowspans need. + return Ok(self.total_spanned_height); + } + let spanned_y = y + 1 + offset; + let is_gutter = layouter.grid.is_gutter_track(spanned_y); + + if unbreakable_rows_left == 0 { + // Simulate unbreakable row groups, and skip regions until + // they fit. There is no risk of infinite recursion, as + // no auto rows participate in the simulation, so the + // unbreakable row group simulator won't recursively call + // 'measure_auto_row' or (consequently) this function. + let row_group = layouter.simulate_unbreakable_row_group( + spanned_y, + None, + &self.regions, + engine, + 0, + )?; + while !self.regions.size.y.fits(row_group.height) + && !in_last_with_offset( + self.regions, + self.header_height + self.footer_height, + ) + { + self.finish_region(layouter, engine)?; + } + + unbreakable_rows_left = row_group.rows.len(); + } + + match row { + // Fixed-size spanned rows are what we are interested in. + // They contribute a fixed amount of height to our rowspan. + Sizing::Rel(v) => { + let height = + v.resolve(layouter.styles).relative_to(self.regions.base().y); + self.total_spanned_height += height; + if is_gutter { + self.latest_spanned_gutter_height = height; + } + + let mut skipped_region = false; + while unbreakable_rows_left == 0 + && !self.regions.size.y.fits(height) + && !in_last_with_offset( + self.regions, + self.header_height + self.footer_height, + ) + { + self.finish_region(layouter, engine)?; + + skipped_region = true; + } + + if !skipped_region || !is_gutter { + // No gutter at the top of a new region, so don't + // account for it if we just skipped a region. + self.regions.size.y -= height; + } + } + Sizing::Auto => { + // We only simulate for rowspans which end at the + // current auto row. Therefore, there won't be any + // further auto rows. + unreachable!(); + } + // For now, we ignore fractional rows on simulation. + Sizing::Fr(_) if is_gutter => { + self.latest_spanned_gutter_height = Abs::zero(); + } + Sizing::Fr(_) => {} + } + + unbreakable_rows_left = unbreakable_rows_left.saturating_sub(1); + } + + Ok(self.total_spanned_height) + } + + fn simulate_header_footer_layout( + &mut self, + layouter: &GridLayouter<'_>, + engine: &mut Engine, + ) -> SourceResult<()> { + // We can't just use the initial header/footer height on each region, + // because header/footer height might vary depending on region size if + // it contains rows with relative lengths. Therefore, we re-simulate + // headers and footers on each new region. + // It's true that, when measuring cells, we reduce each height in the + // backlog to consider the initial header and footer heights; however, + // our simulation checks what happens AFTER the auto row, so we can + // just use the original backlog from `self.regions`. + let disambiguator = self.finished; + let header_height = + if let Some(Repeatable::Repeated(header)) = &layouter.grid.header { + layouter + .simulate_header(header, &self.regions, engine, disambiguator)? + .height + } else { + Abs::zero() + }; + + let footer_height = + if let Some(Repeatable::Repeated(footer)) = &layouter.grid.footer { + layouter + .simulate_footer(footer, &self.regions, engine, disambiguator)? + .height + } else { + Abs::zero() + }; + + let mut skipped_region = false; + + // Skip until we reach a fitting region for both header and footer. + while !self.regions.size.y.fits(header_height + footer_height) + && self.regions.may_progress() + { + self.regions.next(); + self.finished += 1; + skipped_region = true; + } + + if let Some(Repeatable::Repeated(header)) = &layouter.grid.header { + self.header_height = if skipped_region { + // Simulate headers again, at the new region, as + // the full region height may change. + layouter + .simulate_header(header, &self.regions, engine, disambiguator)? + .height + } else { + header_height + }; + } + + if let Some(Repeatable::Repeated(footer)) = &layouter.grid.footer { + self.footer_height = if skipped_region { + // Simulate footers again, at the new region, as + // the full region height may change. + layouter + .simulate_footer(footer, &self.regions, engine, disambiguator)? + .height + } else { + footer_height + }; + } + + // Consume the header's and footer's heights from the new region, + // but don't consider them spanned. The rowspan does not go over the + // header or footer (as an invariant, any rowspans spanning any header + // or footer rows are fully contained within that header's or footer's rows). + self.regions.size.y -= self.header_height + self.footer_height; + + Ok(()) + } + + fn finish_region( + &mut self, + layouter: &GridLayouter<'_>, + engine: &mut Engine, + ) -> SourceResult<()> { + // If a row was pushed to the next region, the immediately + // preceding gutter row is removed. + self.total_spanned_height -= self.latest_spanned_gutter_height; + self.latest_spanned_gutter_height = Abs::zero(); + self.regions.next(); + self.finished += 1; + + self.simulate_header_footer_layout(layouter, engine) + } +} + +/// Subtracts some size from the end of a vector of sizes. +/// For example, subtracting 5pt from \[2pt, 1pt, 3pt\] will result in \[1pt\]. +fn subtract_end_sizes(sizes: &mut Vec<Abs>, mut subtract: Abs) { + while subtract > Abs::zero() && sizes.last().is_some_and(|&size| size <= subtract) { + subtract -= sizes.pop().unwrap(); + } + if subtract > Abs::zero() { + if let Some(last_size) = sizes.last_mut() { + *last_size -= subtract; + } + } +} |