use std::collections::VecDeque;
use super::block::{Block, SplitOutcome};
const HEADING_MIN_FOLLOW_LINES: usize = 3;
fn retract_from(current: &mut Vec<Block>, from: usize, work: &mut VecDeque<Block>) {
let drained: Vec<Block> = current.drain(from..).collect();
for b in drained.into_iter().rev() {
work.push_front(b);
}
}
fn retract_heading_at(current: &mut Vec<Block>, heading_idx: usize, work: &mut VecDeque<Block>) {
let from = if heading_idx > 0 && current[heading_idx - 1].is_spacer() {
heading_idx - 1
} else {
heading_idx
};
retract_from(current, from, work);
}
fn last_content_index(current: &[Block]) -> Option<usize> {
current.iter().rposition(|b| !b.is_spacer())
}
fn heading_has_enough_followers(after: &[Block]) -> bool {
let after: Vec<&Block> = after.iter().filter(|b| !b.is_spacer()).collect();
if after.is_empty() {
return false;
}
if after.iter().any(|b| b.is_substantial_follower()) {
return true;
}
let lines: usize = after.iter().map(|b| b.text_line_count()).sum();
lines >= HEADING_MIN_FOLLOW_LINES
}
fn retract_orphan_trailing(current: &mut Vec<Block>, work: &mut VecDeque<Block>, page_budget: f32) {
loop {
let Some(i) = last_content_index(current) else {
return;
};
let next_h = work
.front()
.map(|b| b.height + b.space_after)
.unwrap_or(0.0);
if current[i].is_heading() {
let from = if i > 0 && current[i - 1].is_spacer() {
i - 1
} else {
i
};
if from == 0 {
break; }
let group_h: f32 = current[from..]
.iter()
.map(|b| b.height + b.space_after)
.sum();
if group_h + next_h > page_budget {
break;
}
retract_heading_at(current, i, work);
continue;
}
if work.front().is_some_and(Block::is_list_item) && !current[i].is_list_item() {
if let Some(h) = current[..i].iter().rposition(|b| b.is_heading())
&& !heading_has_enough_followers(¤t[h + 1..i + 1])
{
let from = if h > 0 && current[h - 1].is_spacer() {
h - 1
} else {
h
};
if from == 0 {
break;
}
let group_h: f32 = current[from..=i]
.iter()
.map(|b| b.height + b.space_after)
.sum();
if group_h + next_h > page_budget {
break;
}
retract_heading_at(current, h, work);
continue;
}
if i == 0 {
break;
}
let group_h = current[i].height + current[i].space_after;
if group_h + next_h > page_budget {
break;
}
retract_from(current, i, work);
continue;
}
if let Some(h) = current.iter().rposition(|b| b.is_heading())
&& !heading_has_enough_followers(¤t[h + 1..])
{
let from = if h > 0 && current[h - 1].is_spacer() {
h - 1
} else {
h
};
if from == 0 {
break;
}
let group_h: f32 = current[from..]
.iter()
.map(|b| b.height + b.space_after)
.sum();
if group_h + next_h > page_budget {
break;
}
retract_heading_at(current, h, work);
continue;
}
break;
}
}
#[allow(clippy::type_complexity)]
fn refresh_after_retract(
current: &[Block],
pool_for: &mut dyn FnMut(&[u32]) -> (f32, Vec<Block>),
body_height: &mut f32,
pool_height: &mut f32,
pool_blocks: &mut Vec<Block>,
numbers: &mut Vec<u32>,
) {
*body_height = current.iter().map(|b| b.height + b.space_after).sum();
numbers.clear();
for b in current {
b.collect_footnote_numbers(numbers);
}
let (h, blocks) = if numbers.is_empty() {
(0.0, Vec::new())
} else {
pool_for(numbers)
};
*pool_height = h;
*pool_blocks = blocks;
}
pub fn paginate_with_footnotes(
blocks: Vec<Block>,
page_budget: f32,
first_page_budget: f32,
num_columns: u8,
pool_for: impl FnMut(&[u32]) -> (f32, Vec<Block>),
) -> Vec<(Vec<Block>, Vec<Block>)> {
if num_columns <= 1 {
return paginate_with_footnotes_single(blocks, page_budget, first_page_budget, pool_for);
}
paginate_with_footnotes_multi(
blocks,
page_budget,
first_page_budget,
num_columns,
pool_for,
)
}
fn paginate_with_footnotes_single(
blocks: Vec<Block>,
page_budget: f32,
first_page_budget: f32,
mut pool_for: impl FnMut(&[u32]) -> (f32, Vec<Block>),
) -> Vec<(Vec<Block>, Vec<Block>)> {
let mut pages: Vec<(Vec<Block>, Vec<Block>)> = Vec::new();
let mut current: Vec<Block> = Vec::new();
let mut current_body_height = 0.0_f32;
let mut current_pool_height = 0.0_f32;
let mut current_pool_blocks: Vec<Block> = Vec::new();
let mut current_numbers: Vec<u32> = Vec::new();
let mut work: VecDeque<Block> = blocks.into();
let flush = |pages: &mut Vec<(Vec<Block>, Vec<Block>)>,
current: &mut Vec<Block>,
pool: &mut Vec<Block>,
body_height: &mut f32,
pool_height: &mut f32,
numbers: &mut Vec<u32>| {
let body = std::mem::take(current);
let pool_blocks = std::mem::take(pool);
pages.push((body, pool_blocks));
*body_height = 0.0;
*pool_height = 0.0;
numbers.clear();
};
while let Some(block) = work.pop_front() {
if matches!(block.draw, super::block::BlockDraw::PageBreak) {
if !current.is_empty() {
retract_orphan_trailing(&mut current, &mut work, page_budget);
refresh_after_retract(
¤t,
&mut pool_for,
&mut current_body_height,
&mut current_pool_height,
&mut current_pool_blocks,
&mut current_numbers,
);
if !current.is_empty() {
flush(
&mut pages,
&mut current,
&mut current_pool_blocks,
&mut current_body_height,
&mut current_pool_height,
&mut current_numbers,
);
}
}
continue;
}
let needed = block.height + block.space_after;
let budget = if pages.is_empty() {
first_page_budget
} else {
page_budget
};
let mut new_calls = Vec::new();
block.collect_footnote_numbers(&mut new_calls);
let (speculative_pool_h, speculative_pool) = if new_calls.is_empty() {
(current_pool_height, current_pool_blocks.clone())
} else {
let mut combined = current_numbers.clone();
combined.extend_from_slice(&new_calls);
pool_for(&combined)
};
if current_body_height + needed + speculative_pool_h <= budget {
current_body_height += needed;
current_pool_height = speculative_pool_h;
current_pool_blocks = speculative_pool;
current_numbers.extend(new_calls);
current.push(block);
continue;
}
let remaining = budget - current_body_height - speculative_pool_h;
match block.try_split(remaining.max(0.0)) {
SplitOutcome::Whole(b) => {
current_body_height += b.height + b.space_after;
current_pool_height = speculative_pool_h;
current_pool_blocks = speculative_pool;
current_numbers.extend(new_calls);
current.push(b);
}
SplitOutcome::Split(head, mut tail) => {
let mut head_calls = Vec::new();
head.collect_footnote_numbers(&mut head_calls);
let mut combined = current_numbers.clone();
combined.extend_from_slice(&head_calls);
let (pool_h, pool_blocks) = pool_for(&combined);
current_pool_height = pool_h;
current_pool_blocks = pool_blocks;
current_numbers = combined;
current.push(head);
tail.height = match &tail.draw {
super::block::BlockDraw::Text(s) => s.height(),
_ => tail.height,
};
work.push_front(tail);
retract_orphan_trailing(&mut current, &mut work, page_budget);
refresh_after_retract(
¤t,
&mut pool_for,
&mut current_body_height,
&mut current_pool_height,
&mut current_pool_blocks,
&mut current_numbers,
);
if !current.is_empty() {
flush(
&mut pages,
&mut current,
&mut current_pool_blocks,
&mut current_body_height,
&mut current_pool_height,
&mut current_numbers,
);
}
}
SplitOutcome::NoFit(b) => {
if !current.is_empty() {
work.push_front(b);
retract_orphan_trailing(&mut current, &mut work, page_budget);
refresh_after_retract(
¤t,
&mut pool_for,
&mut current_body_height,
&mut current_pool_height,
&mut current_pool_blocks,
&mut current_numbers,
);
if !current.is_empty() {
flush(
&mut pages,
&mut current,
&mut current_pool_blocks,
&mut current_body_height,
&mut current_pool_height,
&mut current_numbers,
);
}
} else {
let h = b.height + b.space_after;
let mut block_calls = Vec::new();
b.collect_footnote_numbers(&mut block_calls);
let (pool_h, pool_blocks) = if block_calls.is_empty() {
(0.0, Vec::new())
} else {
pool_for(&block_calls)
};
current_pool_height = pool_h;
current_pool_blocks = pool_blocks;
current_numbers.extend(block_calls);
current.push(b);
current_body_height = h;
}
}
}
}
if !current.is_empty() {
pages.push((current, current_pool_blocks));
}
pages
}
struct MultiColumnState {
col_heights: Vec<f32>,
active_col: usize,
}
impl MultiColumnState {
fn new(num_columns: u8) -> Self {
let n = num_columns.max(1) as usize;
Self {
col_heights: vec![0.0; n],
active_col: 0,
}
}
fn body_used(&self) -> f32 {
self.col_heights.iter().copied().fold(0.0_f32, f32::max)
}
fn remaining_for(&self, block: &Block, budget: f32, pool_h: f32) -> f32 {
if block.column_span {
budget - self.body_used() - pool_h
} else {
budget - self.col_heights[self.active_col] - pool_h
}
}
fn place(&mut self, block: &Block, needed: f32) {
if block.column_span {
let new_h = self.body_used() + needed;
self.col_heights.fill(new_h);
self.active_col = 0;
} else {
self.col_heights[self.active_col] += needed;
}
}
fn assign_column(&self, block: &mut Block) {
block.page_column = if block.column_span {
0
} else {
self.active_col as u8
};
}
fn advance_column(&mut self) -> bool {
if self.active_col + 1 < self.col_heights.len() {
self.active_col += 1;
true
} else {
false
}
}
fn reset(&mut self) {
self.col_heights.fill(0.0);
self.active_col = 0;
}
fn recompute_from(&mut self, current: &[Block]) {
self.reset();
for b in current {
let needed = b.height + b.space_after;
if b.column_span {
let new_h = self.body_used() + needed;
self.col_heights.fill(new_h);
self.active_col = 0;
} else {
let col = (b.page_column as usize).min(self.col_heights.len() - 1);
self.col_heights[col] += needed;
self.active_col = col;
}
}
}
}
fn paginate_with_footnotes_multi(
blocks: Vec<Block>,
page_budget: f32,
first_page_budget: f32,
num_columns: u8,
mut pool_for: impl FnMut(&[u32]) -> (f32, Vec<Block>),
) -> Vec<(Vec<Block>, Vec<Block>)> {
let mut pages: Vec<(Vec<Block>, Vec<Block>)> = Vec::new();
let mut current: Vec<Block> = Vec::new();
let mut mc = MultiColumnState::new(num_columns);
let mut current_pool_height = 0.0_f32;
let mut current_pool_blocks: Vec<Block> = Vec::new();
let mut current_numbers: Vec<u32> = Vec::new();
let mut work: VecDeque<Block> = blocks.into();
let flush = |pages: &mut Vec<(Vec<Block>, Vec<Block>)>,
current: &mut Vec<Block>,
pool: &mut Vec<Block>,
mc: &mut MultiColumnState,
pool_height: &mut f32,
numbers: &mut Vec<u32>| {
let body = std::mem::take(current);
let pool_blocks = std::mem::take(pool);
pages.push((body, pool_blocks));
mc.reset();
*pool_height = 0.0;
numbers.clear();
};
while let Some(mut block) = work.pop_front() {
if matches!(block.draw, super::block::BlockDraw::PageBreak) {
if !current.is_empty() {
retract_orphan_trailing(&mut current, &mut work, page_budget);
mc.recompute_from(¤t);
let mut unused_body = 0.0;
refresh_after_retract(
¤t,
&mut pool_for,
&mut unused_body,
&mut current_pool_height,
&mut current_pool_blocks,
&mut current_numbers,
);
if !current.is_empty() {
flush(
&mut pages,
&mut current,
&mut current_pool_blocks,
&mut mc,
&mut current_pool_height,
&mut current_numbers,
);
}
}
continue;
}
let needed = block.height + block.space_after;
let budget = if pages.is_empty() {
first_page_budget
} else {
page_budget
};
let mut new_calls = Vec::new();
block.collect_footnote_numbers(&mut new_calls);
let (speculative_pool_h, speculative_pool) = if new_calls.is_empty() {
(current_pool_height, current_pool_blocks.clone())
} else {
let mut combined = current_numbers.clone();
combined.extend_from_slice(&new_calls);
pool_for(&combined)
};
if needed
<= mc
.remaining_for(&block, budget, speculative_pool_h)
.max(0.0)
{
mc.assign_column(&mut block);
mc.place(&block, needed);
current_pool_height = speculative_pool_h;
current_pool_blocks = speculative_pool;
current_numbers.extend(new_calls);
current.push(block);
continue;
}
let remaining = mc.remaining_for(&block, budget, speculative_pool_h);
match block.try_split(remaining.max(0.0)) {
SplitOutcome::Whole(b) => {
let mut b = b;
mc.assign_column(&mut b);
mc.place(&b, b.height + b.space_after);
current_pool_height = speculative_pool_h;
current_pool_blocks = speculative_pool;
current_numbers.extend(new_calls);
current.push(b);
}
SplitOutcome::Split(head, mut tail) => {
let mut head = head;
mc.assign_column(&mut head);
mc.place(&head, head.height + head.space_after);
let mut head_calls = Vec::new();
head.collect_footnote_numbers(&mut head_calls);
let mut combined = current_numbers.clone();
combined.extend_from_slice(&head_calls);
let (pool_h, pool_blocks) = pool_for(&combined);
current_pool_height = pool_h;
current_pool_blocks = pool_blocks;
current_numbers = combined;
current.push(head);
tail.height = match &tail.draw {
super::block::BlockDraw::Text(s) => s.height(),
_ => tail.height,
};
work.push_front(tail);
retract_orphan_trailing(&mut current, &mut work, page_budget);
mc.recompute_from(¤t);
let mut dummy_body = 0.0;
refresh_after_retract(
¤t,
&mut pool_for,
&mut dummy_body,
&mut current_pool_height,
&mut current_pool_blocks,
&mut current_numbers,
);
if !current.is_empty() {
flush(
&mut pages,
&mut current,
&mut current_pool_blocks,
&mut mc,
&mut current_pool_height,
&mut current_numbers,
);
}
}
SplitOutcome::NoFit(b) => {
if !current.is_empty() {
work.push_front(b);
retract_orphan_trailing(&mut current, &mut work, page_budget);
mc.recompute_from(¤t);
let mut dummy_body = 0.0;
refresh_after_retract(
¤t,
&mut pool_for,
&mut dummy_body,
&mut current_pool_height,
&mut current_pool_blocks,
&mut current_numbers,
);
if !current.is_empty() {
flush(
&mut pages,
&mut current,
&mut current_pool_blocks,
&mut mc,
&mut current_pool_height,
&mut current_numbers,
);
}
} else if mc.advance_column() {
work.push_front(b);
} else {
let mut b = b;
mc.assign_column(&mut b);
mc.place(&b, needed);
let mut block_calls = Vec::new();
b.collect_footnote_numbers(&mut block_calls);
let (pool_h, pool_blocks) = if block_calls.is_empty() {
(0.0, Vec::new())
} else {
pool_for(&block_calls)
};
current_pool_height = pool_h;
current_pool_blocks = pool_blocks;
current_numbers.extend(block_calls);
current.push(b);
}
}
}
}
if !current.is_empty() {
pages.push((current, current_pool_blocks));
}
pages
}
pub fn paginate(blocks: Vec<Block>, page_budget: f32) -> Vec<Vec<Block>> {
let mut pages: Vec<Vec<Block>> = Vec::new();
let mut current: Vec<Block> = Vec::new();
let mut current_height = 0.0_f32;
let mut work: VecDeque<Block> = blocks.into();
while let Some(block) = work.pop_front() {
let needed = block.height + block.space_after;
if current_height + needed <= page_budget {
current_height += needed;
current.push(block);
continue;
}
let remaining = page_budget - current_height;
match block.try_split(remaining) {
SplitOutcome::Whole(b) => {
current_height += b.height + b.space_after;
current.push(b);
}
SplitOutcome::Split(head, tail) => {
current.push(head);
work.push_front(tail);
retract_orphan_trailing(&mut current, &mut work, page_budget);
current_height = current.iter().map(|b| b.height + b.space_after).sum();
if !current.is_empty() {
pages.push(std::mem::take(&mut current));
current_height = 0.0;
}
}
SplitOutcome::NoFit(b) => {
if !current.is_empty() {
work.push_front(b);
retract_orphan_trailing(&mut current, &mut work, page_budget);
current_height = current.iter().map(|b| b.height + b.space_after).sum();
if !current.is_empty() {
pages.push(std::mem::take(&mut current));
current_height = 0.0;
}
} else {
let h = b.height + b.space_after;
current.push(b);
current_height = h;
}
}
}
}
if !current.is_empty() {
pages.push(current);
}
pages
}
#[cfg(test)]
mod tests {
use super::*;
use crate::render::block::{BlockDraw, OutlineEntry};
use krilla::color::rgb;
fn filler(h: f32) -> Block {
Block {
height: h,
space_after: 0.0,
draw: BlockDraw::Rule {
x: 0.0,
width: 10.0,
thickness: 1.0,
color: rgb::Color::new(0, 0, 0),
},
outline: None,
anchor_id: None,
tag_role: None,
page_column: 0,
column_span: false,
}
}
fn heading_block(h: f32, space_after: f32) -> Block {
let mut b = filler(h);
b.space_after = space_after;
b.outline = Some(OutlineEntry {
level: 2,
text: "Heading".into(),
});
b
}
fn list_item_block(h: f32, space_after: f32) -> Block {
use parley::{FontContext, LayoutContext};
let mut font_cx = FontContext::new();
let mut layout_cx = LayoutContext::new();
let builder = layout_cx.ranged_builder(&mut font_cx, "", 1.0, true);
let mut layout: parley::Layout<rgb::Color> = builder.build("");
layout.break_all_lines(None);
Block {
height: h,
space_after,
draw: BlockDraw::ListItem {
marker: layout,
marker_text: "•".into(),
marker_x: 0.0,
body: Vec::new(),
ordered: false,
badge: None,
check: None,
},
outline: None,
anchor_id: None,
tag_role: None,
page_column: 0,
column_span: false,
}
}
fn callout_block(h: f32, space_after: f32) -> Block {
Block {
height: h,
space_after,
draw: BlockDraw::BoxedGroup {
x: 0.0,
width: 100.0,
background: None,
border: None,
accent_left: None,
accent_width: 0.0,
padding: 0.0,
children: Vec::new(),
icon: None,
top_rule: None,
bottom_rule: None,
},
outline: None,
anchor_id: None,
tag_role: None,
page_column: 0,
column_span: false,
}
}
#[test]
fn does_not_break_after_heading_alone() {
let blocks = vec![
filler(70.0),
heading_block(20.0, 8.0),
list_item_block(40.0, 4.0),
];
let pages = paginate(blocks, 100.0);
assert_eq!(pages.len(), 2);
assert!(
pages[0]
.iter()
.all(|b| !b.is_heading() && !b.is_list_item())
);
assert!(pages[1][0].is_heading());
assert!(pages[1][1].is_list_item());
}
#[test]
fn heading_plus_callout_allows_page_break() {
let blocks = vec![
filler(40.0),
heading_block(18.0, 6.0),
callout_block(30.0, 4.0),
filler(50.0),
];
let pages = paginate(blocks, 100.0);
assert_eq!(pages.len(), 2);
assert!(pages[0].iter().any(|b| b.is_heading()));
assert!(pages[0].iter().any(|b| b.is_boxed_text_block()));
assert!(pages[1].iter().all(|b| !b.is_heading()));
}
#[test]
fn does_not_break_before_list_start() {
let blocks = vec![
filler(70.0),
filler(20.0), list_item_block(40.0, 4.0),
];
let pages = paginate(blocks, 100.0);
assert_eq!(pages.len(), 2, "lead-in must stay with the list");
assert!(pages[1].iter().any(|b| b.is_list_item()));
assert_eq!(pages[0].len(), 1);
assert_eq!(pages[1].len(), 2);
}
#[test]
fn heading_plus_short_lead_in_moves_with_list() {
let blocks = vec![
filler(50.0),
heading_block(18.0, 6.0),
filler(12.0), list_item_block(40.0, 4.0),
];
let pages = paginate(blocks, 100.0);
assert_eq!(
pages.len(),
2,
"heading + short lead-in must move with the list"
);
assert!(pages[1][0].is_heading());
assert!(pages[1].iter().any(|b| b.is_list_item()));
}
}