use crate::glue::Glue;
use crate::node::{
BoxNode, GlueNode, GlueSource, InsNode, Node, Scaled, AWFUL_BAD, DEPLORABLE, EJECT_PENALTY,
INF_BAD, INF_PENALTY, MAX_DIMEN,
};
use crate::pack::{badness, vpack, vpackage, x_over_n, Spec, Tolerances, NATURAL};
use std::collections::{BTreeMap, VecDeque};
#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
pub struct Totals {
pub height: Scaled,
pub stretch: [Scaled; 4],
pub shrink: Scaled,
}
impl Totals {
fn has_infinite_stretch(&self) -> bool {
self.stretch[1] != 0 || self.stretch[2] != 0 || self.stretch[3] != 0
}
fn add(&mut self, spec: &Glue) {
let order = spec.stretch_order.clamp(0, 3) as usize;
self.stretch[order] += spec.stretch;
self.shrink += spec.shrink;
}
fn infinite_shrink(spec: &Glue) -> bool {
spec.shrink_order != 0 && spec.shrink != 0
}
}
fn page_badness(totals: &Totals, h: Scaled) -> i64 {
if totals.height < h {
return match totals.has_infinite_stretch() {
true => 0,
false => badness(h - totals.height, totals.stretch[0]),
};
}
if totals.height - h > totals.shrink {
return AWFUL_BAD;
}
badness(totals.height - h, totals.shrink)
}
pub const END_PENALTY: i64 = -0o10_000_000_000_i64;
fn cost(b: i64, pi: i64) -> i64 {
if b >= AWFUL_BAD {
return b;
}
if pi <= EJECT_PENALTY {
return pi;
}
match b < INF_BAD {
true => b + pi,
false => DEPLORABLE,
}
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub struct Break {
pub place: Option<usize>,
pub height_plus_depth: Scaled,
pub cost: i64,
pub infinite_shrink: bool,
}
enum Step {
Legal(i64),
UpdateHeights,
NotFound,
}
pub fn vert_break(list: &[Node], h: Scaled, d: Scaled) -> Break {
let mut totals = Totals::default();
let mut prev_dp: Scaled = 0;
let mut least_cost = AWFUL_BAD;
let mut best_place: Option<usize> = None;
let mut best_hpd: Scaled = 0;
let mut infinite_shrink = false;
let mut prev_p: usize = 0;
let mut p: usize = 0;
loop {
let step = match list.get(p) {
None => Step::Legal(EJECT_PENALTY),
Some(Node::Box(_)) | Some(Node::Rule(_)) => {
let (bh, bd) = height_and_depth(&list[p]);
totals.height += prev_dp + bh;
prev_dp = bd;
Step::NotFound
}
Some(Node::Whatsit(_)) => Step::NotFound,
Some(Node::Glue(_)) => match list[prev_p].precedes_break() {
true => Step::Legal(0),
false => Step::UpdateHeights,
},
Some(Node::Kern { .. }) => match list.get(p + 1).map(Node::type_code) {
Some(10) => Step::Legal(0),
_ => Step::UpdateHeights,
},
Some(Node::Penalty(pi)) => Step::Legal(*pi),
Some(Node::Mark(_)) | Some(Node::Ins(_)) => Step::NotFound,
Some(_) => Step::NotFound,
};
if let Step::Legal(pi) = step {
if pi < INF_PENALTY {
let b = page_badness(&totals, h);
let c = cost(b, pi);
if c <= least_cost {
best_place = match p < list.len() {
true => Some(p),
false => None,
};
least_cost = c;
best_hpd = totals.height + prev_dp;
}
if b == AWFUL_BAD || pi <= EJECT_PENALTY {
break;
}
}
}
let glue_or_kern = matches!(list.get(p).map(Node::type_code), Some(10) | Some(11));
let update = matches!(step, Step::UpdateHeights)
|| (glue_or_kern && !matches!(step, Step::NotFound));
if update {
match &list[p] {
Node::Kern { width, .. } => {
totals.height += prev_dp + width;
}
Node::Glue(g) => {
totals.add(&g.spec);
infinite_shrink |= Totals::infinite_shrink(&g.spec);
totals.height += prev_dp + g.spec.natural;
}
_ => {}
}
prev_dp = 0;
}
if prev_dp > d {
totals.height += prev_dp - d;
prev_dp = d;
}
prev_p = p;
p += 1;
}
Break {
place: best_place,
height_plus_depth: best_hpd,
cost: least_cost,
infinite_shrink,
}
}
fn height_and_depth(node: &Node) -> (Scaled, Scaled) {
match node {
Node::Box(b) => (b.height, b.depth),
Node::Rule(r) => (r.height, r.depth),
_ => (0, 0),
}
}
pub fn prune_page_top(list: Vec<Node>, split_top_skip: Glue) -> Vec<Node> {
let mut out: Vec<Node> = Vec::with_capacity(list.len() + 1);
let mut pruning = true;
for node in list {
if !pruning {
out.push(node);
continue;
}
match &node {
Node::Box(_) | Node::Rule(_) => {
let (height, _) = height_and_depth(&node);
let natural = (split_top_skip.natural - height).max(0);
out.push(Node::Glue(GlueNode::param(
Glue {
natural,
..split_top_skip
},
GlueSource::SplitTopSkip,
)));
out.push(node);
pruning = false;
}
Node::Whatsit(_) | Node::Mark(_) | Node::Ins(_) => out.push(node),
_ => {}
}
}
out
}
#[derive(Clone, Debug)]
pub struct Split {
pub extracted: BoxNode,
pub remainder: Option<BoxNode>,
pub first_mark: Option<String>,
pub bot_mark: Option<String>,
}
pub fn vsplit(
boxed: BoxNode,
h: Scaled,
split_max_depth: Scaled,
split_top_skip: Glue,
tol: Tolerances,
) -> Option<Split> {
if !boxed.vertical {
return None;
}
let list = boxed.list;
let brk = vert_break(&list, h, split_max_depth);
let cut = brk.place.unwrap_or(list.len());
let mut first_mark: Option<String> = None;
let mut bot_mark: Option<String> = None;
let mut head: Vec<Node> = Vec::with_capacity(cut);
let mut tail: Vec<Node> = Vec::new();
for (i, node) in list.into_iter().enumerate() {
if i < cut {
if let Node::Mark(text) = &node {
if first_mark.is_none() {
first_mark = Some(text.clone());
}
bot_mark = Some(text.clone());
}
head.push(node);
} else {
tail.push(node);
}
}
let rest = prune_page_top(tail, split_top_skip);
let remainder = match rest.is_empty() {
true => None,
false => Some(vpack(rest, NATURAL, tol).node),
};
let extracted = vpackage(head, Spec::Exactly(h), split_max_depth, tol).node;
Some(Split {
extracted,
remainder,
first_mark,
bot_mark,
})
}
#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Debug, Default)]
pub enum Contents {
#[default]
Empty,
InsertsOnly,
BoxThere,
}
#[derive(Clone, Copy, Debug, Default)]
pub struct InsertClass {
pub count: i64,
pub dimen: Scaled,
pub skip: Glue,
}
#[derive(Clone, Debug)]
struct PageIns {
number: u8,
split_up: bool,
height: Scaled,
broken_ptr: Option<usize>,
broken_ins: Option<usize>,
last_ins_ptr: Option<usize>,
best_ins_ptr: Option<usize>,
}
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum PageDimen {
Goal,
Total,
Stretch(usize),
Shrink,
Depth,
}
#[derive(Clone, Debug)]
pub struct PageParams {
pub vsize: Scaled,
pub max_depth: Scaled,
pub top_skip: Glue,
pub split_top_skip: Glue,
pub split_max_depth: Scaled,
pub holding_inserts: i64,
pub max_dead_cycles: i64,
pub tolerances: Tolerances,
pub inserts: BTreeMap<u8, InsertClass>,
}
impl Default for PageParams {
fn default() -> PageParams {
let pt = |n: i64| n * crate::dimen::UNITY;
PageParams {
vsize: crate::dimen::to_scaled(8, crate::dimen::round_decimals("9"), "in")
.unwrap_or(pt(643)),
max_depth: pt(4),
top_skip: Glue::fixed(pt(10)),
split_top_skip: Glue::fixed(pt(10)),
split_max_depth: MAX_DIMEN,
holding_inserts: 0,
max_dead_cycles: 25,
tolerances: Tolerances::plain(),
inserts: BTreeMap::new(),
}
}
}
#[derive(Clone, Debug)]
pub enum Fired {
ShipOut(BoxNode),
Output {
page: BoxNode,
output_penalty: i64,
dead_cycles: i64,
},
}
pub struct PageBuilder {
pub params: PageParams,
page: Vec<Node>,
contrib: VecDeque<Node>,
contents: Contents,
totals: Totals,
page_goal: Scaled,
page_depth: Scaled,
page_max_depth: Scaled,
best_page_break: Option<usize>,
least_page_cost: i64,
best_size: Scaled,
page_ins: Vec<PageIns>,
insert_penalties: i64,
output_active: bool,
dead_cycles: i64,
output_penalty: i64,
pub has_output_routine: bool,
pub top_mark: Option<String>,
pub first_mark: Option<String>,
pub bot_mark: Option<String>,
pub boxes: BTreeMap<u8, BoxNode>,
pub last_glue: Option<Glue>,
pub last_penalty: i64,
pub last_kern: Scaled,
pub reports: Vec<String>,
}
impl PageBuilder {
pub fn new(params: PageParams) -> PageBuilder {
let mut b = PageBuilder {
params,
page: Vec::new(),
contrib: VecDeque::new(),
contents: Contents::Empty,
totals: Totals::default(),
page_goal: 0,
page_depth: 0,
page_max_depth: 0,
best_page_break: None,
least_page_cost: AWFUL_BAD,
best_size: 0,
page_ins: Vec::new(),
insert_penalties: 0,
output_active: false,
dead_cycles: 0,
output_penalty: INF_PENALTY,
has_output_routine: false,
top_mark: None,
first_mark: None,
bot_mark: None,
boxes: BTreeMap::new(),
last_glue: None,
last_penalty: 0,
last_kern: 0,
reports: Vec::new(),
};
b.start_new_page();
b
}
pub fn page_goal(&self) -> Scaled {
self.page_goal
}
pub fn page_total(&self) -> Scaled {
self.totals.height
}
pub fn page_stretch(&self, order: usize) -> Scaled {
self.totals.stretch[order.min(3)]
}
pub fn page_shrink(&self) -> Scaled {
self.totals.shrink
}
pub fn page_depth(&self) -> Scaled {
self.page_depth
}
pub fn set_page_so_far(&mut self, which: PageDimen, value: Scaled) {
match which {
PageDimen::Goal => self.page_goal = value,
PageDimen::Total => self.totals.height = value,
PageDimen::Stretch(order) => self.totals.stretch[order.min(3)] = value,
PageDimen::Shrink => self.totals.shrink = value,
PageDimen::Depth => self.page_depth = value,
}
}
pub fn page_so_far(&self, which: PageDimen) -> Scaled {
match which {
PageDimen::Goal => self.page_goal,
PageDimen::Total => self.totals.height,
PageDimen::Stretch(order) => self.totals.stretch[order.min(3)],
PageDimen::Shrink => self.totals.shrink,
PageDimen::Depth => self.page_depth,
}
}
pub fn insert_penalties(&self) -> i64 {
self.insert_penalties
}
pub fn output_penalty(&self) -> i64 {
self.output_penalty
}
pub fn dead_cycles(&self) -> i64 {
self.dead_cycles
}
pub fn contents(&self) -> Contents {
self.contents
}
pub fn current_page(&self) -> &[Node] {
&self.page
}
pub fn contributions_pending(&self) -> bool {
!self.contrib.is_empty()
}
pub fn contribute(&mut self, nodes: Vec<Node>) -> Vec<Fired> {
self.contrib.extend(nodes);
self.build_page()
}
pub fn finish(&mut self) -> Vec<Fired> {
let mut fired = self.contribute(vec![
Node::Box(BoxNode::null()),
Node::Glue(GlueNode::new(Glue {
stretch: crate::dimen::UNITY,
stretch_order: 2,
..Glue::default()
})),
Node::Penalty(END_PENALTY),
]);
fired.extend(self.build_page());
fired
}
fn start_new_page(&mut self) {
self.contents = Contents::Empty;
self.page.clear();
self.last_glue = None;
self.last_penalty = 0;
self.last_kern = 0;
self.page_depth = 0;
self.page_max_depth = 0;
}
fn freeze_page_specs(&mut self, s: Contents) {
self.contents = s;
self.page_goal = self.params.vsize;
self.page_max_depth = self.params.max_depth;
self.page_depth = 0;
self.totals = Totals::default();
self.least_page_cost = AWFUL_BAD;
}
fn build_page(&mut self) -> Vec<Fired> {
let mut fired = Vec::new();
if self.output_active {
return fired;
}
while !self.contrib.is_empty() {
let Some(node) = self.contrib.pop_front() else {
break;
};
self.record_last(&node);
match self.move_to_page(node) {
Move::Linked => {}
Move::Discarded => {}
Move::Wait(node) => {
self.contrib.push_front(node);
return fired;
}
Move::Fire(node) => {
let out = self.fire_up(Some(node));
fired.push(out);
if self.output_active {
return fired;
}
}
}
}
fired
}
fn record_last(&mut self, node: &Node) {
self.last_penalty = 0;
self.last_kern = 0;
self.last_glue = None;
match node {
Node::Glue(g) => self.last_glue = Some(g.spec),
Node::Penalty(p) => self.last_penalty = *p,
Node::Kern { width, .. } => self.last_kern = *width,
_ => {}
}
}
fn move_to_page(&mut self, node: Node) -> Move {
let pi = match &node {
Node::Box(_) | Node::Rule(_) => {
if self.contents < Contents::BoxThere {
if self.contents == Contents::Empty {
self.freeze_page_specs(Contents::BoxThere);
} else {
self.contents = Contents::BoxThere;
}
let (height, _) = height_and_depth(&node);
let natural = (self.params.top_skip.natural - height).max(0);
let skip = Node::Glue(GlueNode::param(
Glue {
natural,
..self.params.top_skip
},
GlueSource::TopSkip,
));
self.contrib.push_front(node);
self.contrib.push_front(skip);
return Move::Discarded;
}
let (height, depth) = height_and_depth(&node);
self.totals.height += self.page_depth + height;
self.page_depth = depth;
return self.contribute_node(node);
}
Node::Whatsit(_) | Node::Mark(_) => return self.contribute_node(node),
Node::Ins(ins) => {
let ins = ins.clone();
self.append_insertion(&ins);
return self.contribute_node(node);
}
Node::Glue(g) => {
if self.contents < Contents::BoxThere {
return Move::Discarded;
}
match self.page.last().map(Node::precedes_break) {
Some(true) => Some(0),
_ => {
self.update_heights(&Node::Glue(g.clone()));
return self.contribute_node(node);
}
}
}
Node::Kern { .. } => {
if self.contents < Contents::BoxThere {
return Move::Discarded;
}
match self.contrib.front().map(Node::type_code) {
None => return Move::Wait(node),
Some(10) => Some(0),
_ => {
self.update_heights(&node);
return self.contribute_node(node);
}
}
}
Node::Penalty(p) => match self.contents < Contents::BoxThere {
true => return Move::Discarded,
false => Some(*p),
},
_ => return self.contribute_node(node),
};
if let Some(pi) = pi {
if pi < INF_PENALTY {
let b = self.break_badness();
let mut c = cost(b, pi);
if self.insert_penalties >= 10000 {
c = AWFUL_BAD;
}
if c <= self.least_page_cost {
self.best_page_break = Some(self.page.len());
self.best_size = self.page_goal;
self.least_page_cost = c;
for r in &mut self.page_ins {
r.best_ins_ptr = r.last_ins_ptr;
}
}
if c == AWFUL_BAD || pi <= EJECT_PENALTY {
return Move::Fire(node);
}
}
}
if matches!(node.type_code(), 10 | 11) {
self.update_heights(&node);
}
self.contribute_node(node)
}
fn break_badness(&self) -> i64 {
page_badness(&self.totals, self.page_goal)
}
fn update_heights(&mut self, node: &Node) {
match node {
Node::Kern { width, .. } => self.totals.height += self.page_depth + width,
Node::Glue(g) => {
self.totals.add(&g.spec);
if Totals::infinite_shrink(&g.spec) {
self.reports
.push("Infinite glue shrinkage found on current page".into());
}
self.totals.height += self.page_depth + g.spec.natural;
}
_ => return,
}
self.page_depth = 0;
}
fn contribute_node(&mut self, node: Node) -> Move {
if self.page_depth > self.page_max_depth {
self.totals.height += self.page_depth - self.page_max_depth;
self.page_depth = self.page_max_depth;
}
self.page.push(node);
Move::Linked
}
fn append_insertion(&mut self, p: &InsNode) {
if self.contents == Contents::Empty {
self.freeze_page_specs(Contents::InsertsOnly);
}
let n = p.number;
let class = self.params.inserts.get(&n).copied().unwrap_or_default();
let here = self.page.len();
if !self.page_ins.iter().any(|r| r.number == n) {
let held = self
.boxes
.get(&n)
.map(BoxNode::height_plus_depth)
.unwrap_or(0);
let h = match class.count == 1000 {
true => held,
false => x_over_n(held, 1000) * class.count,
};
self.page_goal -= h + class.skip.natural;
self.totals.add(&class.skip);
if Totals::infinite_shrink(&class.skip) {
self.reports
.push(format!("Infinite glue shrinkage inserted from \\skip{n}"));
}
self.page_ins.push(PageIns {
number: n,
split_up: false,
height: held,
broken_ptr: None,
broken_ins: None,
last_ins_ptr: None,
best_ins_ptr: None,
});
self.page_ins.sort_by_key(|r| r.number);
}
let index = self
.page_ins
.iter()
.position(|r| r.number == n)
.expect("the record was just made");
if self.page_ins[index].split_up {
self.insert_penalties += p.float_cost;
return;
}
self.page_ins[index].last_ins_ptr = Some(here);
let delta = self.page_goal - self.totals.height - self.page_depth + self.totals.shrink;
let h = match class.count == 1000 {
true => p.height,
false => x_over_n(p.height, 1000) * class.count,
};
let r_height = self.page_ins[index].height;
if (h <= 0 || h <= delta) && p.height + r_height <= class.dimen {
self.page_goal -= h;
self.page_ins[index].height += p.height;
return;
}
let mut w = match class.count <= 0 {
true => MAX_DIMEN,
false => {
let w = self.page_goal - self.totals.height - self.page_depth;
match class.count == 1000 {
true => w,
false => x_over_n(w, class.count) * 1000,
}
}
};
if w > class.dimen - r_height {
w = class.dimen - r_height;
}
let brk = vert_break(&p.list, w, p.depth);
self.page_ins[index].height += brk.height_plus_depth;
let mut charged = brk.height_plus_depth;
if class.count != 1000 {
charged = x_over_n(charged, 1000) * class.count;
}
self.page_goal -= charged;
self.page_ins[index].split_up = true;
self.page_ins[index].broken_ptr = brk.place;
self.page_ins[index].broken_ins = Some(here);
self.insert_penalties += match brk.place.and_then(|i| p.list.get(i)) {
Some(Node::Penalty(pen)) => *pen,
Some(_) => 0,
None => EJECT_PENALTY,
};
}
fn fire_up(&mut self, mut contributing: Option<Node>) -> Fired {
let cut = self.best_page_break.unwrap_or(self.page.len());
let penalty_at_break = {
let node = match cut < self.page.len() {
true => self.page.get_mut(cut),
false => contributing.as_mut(),
};
match node {
Some(Node::Penalty(p)) => {
let value = *p;
*p = INF_PENALTY;
Some(value)
}
_ => None,
}
};
self.output_penalty = penalty_at_break.unwrap_or(INF_PENALTY);
if self.bot_mark.is_some() {
self.top_mark = self.bot_mark.clone();
self.first_mark = None;
}
self.insert_penalties = 0;
let mut page = std::mem::take(&mut self.page);
let leftover: Vec<Node> = page.split_off(cut.min(page.len()));
let mut held_over: Vec<Node> = Vec::new();
let mut kept: Vec<Node> = Vec::with_capacity(page.len());
for (i, node) in page.into_iter().enumerate() {
match node {
Node::Ins(ins) if self.params.holding_inserts <= 0 => {
if self.place_insertion(i, ins.clone()) {
self.insert_penalties += 1;
held_over.push(Node::Ins(ins));
}
}
Node::Mark(text) => {
if self.first_mark.is_none() {
self.first_mark = Some(text.clone());
}
self.bot_mark = Some(text.clone());
kept.push(Node::Mark(text));
}
other => kept.push(other),
}
}
let mut back: VecDeque<Node> = leftover.into();
if let Some(node) = contributing {
back.push_back(node);
}
back.append(&mut self.contrib);
self.contrib = back;
let quiet = Tolerances {
vbadness: INF_BAD,
vfuzz: MAX_DIMEN,
..self.params.tolerances
};
let page = vpackage(
kept,
Spec::Exactly(self.best_size),
self.page_max_depth,
quiet,
)
.node;
self.boxes.insert(255, page.clone());
self.start_new_page();
self.page = held_over;
self.page_ins.clear();
self.best_page_break = None;
self.least_page_cost = AWFUL_BAD;
if self.first_mark.is_none() {
self.first_mark = self.top_mark.clone();
}
if self.top_mark.is_none() {
self.top_mark = self.first_mark.clone();
}
if self.has_output_routine && self.dead_cycles < self.params.max_dead_cycles {
self.output_active = true;
self.dead_cycles += 1;
return Fired::Output {
page,
output_penalty: self.output_penalty,
dead_cycles: self.dead_cycles,
};
}
let held = std::mem::take(&mut self.page);
let mut back: VecDeque<Node> = held.into();
back.append(&mut self.contrib);
self.contrib = back;
self.boxes.remove(&255);
Fired::ShipOut(page)
}
fn place_insertion(&mut self, at: usize, p: InsNode) -> bool {
let n = p.number;
let Some(index) = self.page_ins.iter().position(|r| r.number == n) else {
return true;
};
if self.page_ins[index].best_ins_ptr.is_none() {
return true;
}
let is_last = self.page_ins[index].best_ins_ptr == Some(at);
let split_here = self.page_ins[index].split_up
&& self.page_ins[index].broken_ins == Some(at)
&& self.page_ins[index].broken_ptr.is_some();
let mut material = p.list;
let mut wait = false;
if is_last && split_here {
let cut = self.page_ins[index].broken_ptr.unwrap_or(material.len());
let rest = material.split_off(cut.min(material.len()));
let rest = prune_page_top(rest, p.split_top_skip);
if !rest.is_empty() {
wait = true;
}
}
let target = self.boxes.entry(n).or_insert_with(BoxNode::null);
target.vertical = true;
target.list.append(&mut material);
if is_last {
let taken = self.boxes.remove(&n).unwrap_or_else(BoxNode::null);
let packed = vpack(taken.list, NATURAL, self.params.tolerances);
self.boxes.insert(n, packed.node);
self.page_ins[index].best_ins_ptr = None;
}
wait
}
pub fn resume_output(&mut self, built: Vec<Node>) -> Vec<Fired> {
self.output_active = false;
self.insert_penalties = 0;
if self.boxes.remove(&255).is_some() {
self.reports
.push("Output routine didn't use all of \\box255".into());
}
self.page.extend(built);
let held = std::mem::take(&mut self.page);
let mut back: VecDeque<Node> = held.into();
back.append(&mut self.contrib);
self.contrib = back;
self.build_page()
}
pub fn shipped(&mut self) {
self.dead_cycles = 0;
}
}
enum Move {
Linked,
Discarded,
Wait(Node),
Fire(Node),
}
#[derive(Clone, Copy, Debug, Default)]
pub struct ParPenalties {
pub inter_line: i64,
pub club: i64,
pub widow: i64,
pub broken: i64,
}
impl ParPenalties {
pub fn latex() -> ParPenalties {
ParPenalties {
inter_line: 0,
club: 150,
widow: 150,
broken: 100,
}
}
}
pub fn interline_penalty(
line: usize,
total: usize,
disc_break: bool,
p: ParPenalties,
) -> Option<i64> {
if line + 1 >= total {
return None;
}
let mut pen = p.inter_line;
if line == 0 {
pen += p.club;
}
if line + 2 == total {
pen += p.widow;
}
if disc_break {
pen += p.broken;
}
match pen {
0 => None,
pen => Some(pen),
}
}
#[cfg(test)]
mod tests {
use super::*;
use crate::dimen::UNITY;
use crate::pack::Baselines;
fn pt(n: i64) -> Scaled {
n * UNITY
}
fn line(height: Scaled, depth: Scaled) -> Node {
Node::Box(BoxNode {
width: pt(100),
height,
depth,
..BoxNode::null()
})
}
fn skip(natural: Scaled, stretch: Scaled, shrink: Scaled) -> Node {
Node::Glue(GlueNode::new(Glue {
natural,
stretch,
shrink,
..Glue::default()
}))
}
fn column(n: usize) -> Vec<Node> {
let mut list = Vec::new();
for i in 0..n {
if i > 0 {
list.push(skip(pt(2), pt(1), pt(1)));
}
list.push(line(pt(10), 0));
}
list
}
#[test]
fn vert_break_picks_the_cheapest_place_not_the_last_that_fits() {
let list = column(5);
let brk = vert_break(&list, pt(34), pt(4));
assert_eq!(brk.place, Some(5));
assert_eq!(brk.cost, 0);
assert_eq!(brk.height_plus_depth, pt(34));
let brk = vert_break(&list, pt(30), pt(4));
assert_eq!(brk.place, Some(3));
}
#[test]
fn a_list_that_starts_with_glue_cannot_be_broken_at_it() {
let list = vec![skip(pt(20), 0, 0), line(pt(10), 0)];
let brk = vert_break(&list, 0, pt(4));
assert_eq!(brk.place, None);
}
#[test]
fn a_forced_penalty_ends_the_search_where_it_stands() {
let mut list = column(5);
list.insert(2, Node::Penalty(EJECT_PENALTY));
let brk = vert_break(&list, pt(100), pt(4));
assert_eq!(brk.place, Some(2));
assert_eq!(brk.cost, EJECT_PENALTY);
}
#[test]
fn nobreak_is_not_a_breakpoint_at_any_cost() {
let mut list = column(4);
list.insert(3, Node::Penalty(INF_PENALTY));
let brk = vert_break(&list, pt(22), pt(4));
assert_ne!(brk.place, Some(3));
assert_ne!(brk.place, Some(4));
}
#[test]
fn infinite_stretch_makes_a_short_page_perfect() {
let column = |filler: Glue| {
vec![
line(pt(10), 0),
Node::Glue(GlueNode::new(filler)),
line(pt(10), 0),
Node::Glue(GlueNode::new(Glue::default())),
line(pt(500), 0),
]
};
let vfil = Glue {
stretch: UNITY,
stretch_order: 1,
..Glue::default()
};
let brk = vert_break(&column(vfil), pt(100), pt(4));
assert_eq!(brk.place, Some(3));
assert_eq!(brk.cost, 0);
let brk = vert_break(&column(Glue::default()), pt(100), pt(4));
assert_eq!(brk.place, Some(3));
assert_eq!(brk.cost, DEPLORABLE);
}
#[test]
fn pruning_a_page_top_replaces_the_glue_with_splittopskip() {
let list = vec![
skip(pt(2), pt(1), 0),
Node::Penalty(50),
line(pt(7), pt(1)),
skip(pt(2), 0, 0),
];
let pruned = prune_page_top(list, Glue::fixed(pt(10)));
assert_eq!(pruned.len(), 3);
let Node::Glue(g) = &pruned[0] else {
panic!("splittopskip is a glue node");
};
assert_eq!(g.spec.natural, pt(3));
assert_eq!(g.source, GlueSource::SplitTopSkip);
assert_eq!(g.spec.natural + pt(7), pt(10));
}
#[test]
fn splittopskip_never_backspaces() {
let pruned = prune_page_top(vec![line(pt(30), 0)], Glue::fixed(pt(10)));
let Node::Glue(g) = &pruned[0] else {
panic!("splittopskip is a glue node");
};
assert_eq!(g.spec.natural, 0);
}
#[test]
fn vsplit_cuts_a_box_in_two_and_reports_its_marks() {
let mut list = column(5);
list.insert(0, Node::Mark("first".into()));
list.insert(4, Node::Mark("second".into()));
let boxed = vpack(list, NATURAL, Tolerances::plain()).node;
let split = vsplit(
boxed,
pt(34),
pt(4),
Glue::fixed(pt(10)),
Tolerances::plain(),
)
.expect("a vbox splits");
assert_eq!(split.extracted.height, pt(34));
assert_eq!(split.first_mark.as_deref(), Some("first"));
assert_eq!(split.bot_mark.as_deref(), Some("second"));
let rest = split.remainder.expect("something was left");
assert!(rest.height > 0);
}
#[test]
fn vsplit_refuses_an_hbox() {
let boxed = crate::pack::hpack(Vec::new(), NATURAL, Tolerances::plain(), None).node;
assert!(vsplit(
boxed,
pt(10),
pt(4),
Glue::fixed(pt(10)),
Tolerances::plain()
)
.is_none());
}
#[test]
fn topskip_puts_the_first_baseline_where_it_belongs() {
let params = PageParams {
vsize: pt(200),
top_skip: Glue::fixed(pt(10)),
..PageParams::default()
};
let mut builder = PageBuilder::new(params);
builder.contribute(vec![line(pt(7), pt(2))]);
let page = builder.current_page();
assert_eq!(page.len(), 2);
let Node::Glue(g) = &page[0] else {
panic!("\\topskip is a glue node");
};
assert_eq!(g.source, GlueSource::TopSkip);
assert_eq!(g.spec.natural, pt(3));
assert_eq!(builder.page_total(), pt(10));
assert_eq!(builder.page_depth(), pt(2));
assert_eq!(builder.page_goal(), pt(200));
}
#[test]
fn glue_before_the_first_box_is_thrown_away() {
let mut builder = PageBuilder::new(PageParams {
vsize: pt(200),
..PageParams::default()
});
builder.contribute(vec![
skip(pt(50), 0, 0),
Node::Penalty(100),
line(pt(10), 0),
]);
assert_eq!(builder.contents(), Contents::BoxThere);
assert_eq!(builder.current_page().len(), 2);
assert_eq!(builder.page_total(), pt(10));
}
#[test]
fn a_forced_break_ships_the_page_at_once() {
let mut builder = PageBuilder::new(PageParams {
vsize: pt(500),
max_depth: pt(4),
top_skip: Glue::fixed(pt(10)),
..PageParams::default()
});
let mut nodes = column(3);
nodes.push(Node::Penalty(EJECT_PENALTY));
nodes.extend(column(2));
let fired = builder.contribute(nodes);
assert_eq!(fired.len(), 1);
let Fired::ShipOut(page) = &fired[0] else {
panic!("with no \\output the page ships");
};
assert_eq!(page.height, pt(500));
assert_eq!(builder.output_penalty(), EJECT_PENALTY);
assert_eq!(builder.page_total(), pt(10 + 2 + 10));
assert_eq!(builder.current_page().len(), 4);
}
#[test]
fn an_overfull_page_breaks_at_the_best_place_already_seen() {
let mut builder = PageBuilder::new(PageParams {
vsize: pt(34),
max_depth: pt(4),
top_skip: Glue::fixed(pt(10)),
..PageParams::default()
});
let fired = builder.contribute(column(6));
assert_eq!(fired.len(), 1);
let Fired::ShipOut(page) = &fired[0] else {
panic!("with no \\output the page ships");
};
assert_eq!(page.height, pt(34));
assert_eq!(page.list.len(), 6);
}
#[test]
fn assigning_to_pagegoal_moves_the_break() {
let mut builder = PageBuilder::new(PageParams {
vsize: pt(34),
max_depth: pt(4),
top_skip: Glue::fixed(pt(10)),
..PageParams::default()
});
assert!(builder.contribute(vec![line(pt(10), 0)]).is_empty());
assert_eq!(builder.page_goal(), pt(34));
builder.set_page_so_far(PageDimen::Goal, pt(46));
assert_eq!(builder.page_so_far(PageDimen::Goal), pt(46));
let mut rest = Vec::new();
for _ in 0..5 {
rest.push(skip(pt(2), pt(1), pt(1)));
rest.push(line(pt(10), 0));
}
let fired = builder.contribute(rest);
assert_eq!(fired.len(), 1);
let Fired::ShipOut(page) = &fired[0] else {
panic!("with no \\output the page ships");
};
assert_eq!(page.height, pt(46));
assert_eq!(page.list.len(), 8);
}
#[test]
fn an_output_routine_gets_box255_and_hands_back_a_list() {
let mut builder = PageBuilder::new(PageParams {
vsize: pt(34),
max_depth: pt(4),
top_skip: Glue::fixed(pt(10)),
..PageParams::default()
});
builder.has_output_routine = true;
let fired = builder.contribute(column(6));
assert_eq!(fired.len(), 1);
let Fired::Output {
page, dead_cycles, ..
} = &fired[0]
else {
panic!("an \\output routine was set");
};
assert_eq!(page.height, pt(34));
assert_eq!(*dead_cycles, 1);
assert!(builder.boxes.contains_key(&255));
builder.boxes.remove(&255);
builder.shipped();
let fired = builder.resume_output(Vec::new());
assert_eq!(builder.dead_cycles(), 0);
assert!(fired.is_empty());
assert_eq!(builder.page_total(), pt(34));
let fired = builder.finish();
assert_eq!(fired.len(), 1);
let Fired::Output { page, .. } = &fired[0] else {
panic!("the routine is still set");
};
assert_eq!(page.height, pt(34));
}
#[test]
fn the_three_marks_say_what_was_on_the_page() {
let mut builder = PageBuilder::new(PageParams {
vsize: pt(34),
max_depth: pt(4),
top_skip: Glue::fixed(pt(10)),
..PageParams::default()
});
let page_of = |marks: [&str; 2]| {
vec![
line(pt(10), 0),
Node::Mark(marks[0].into()),
skip(pt(2), pt(1), pt(1)),
line(pt(10), 0),
Node::Mark(marks[1].into()),
skip(pt(2), pt(1), pt(1)),
line(pt(10), 0),
Node::Penalty(EJECT_PENALTY),
]
};
let fired = builder.contribute(page_of(["A", "B"]));
assert_eq!(fired.len(), 1);
assert_eq!(builder.first_mark.as_deref(), Some("A"));
assert_eq!(builder.bot_mark.as_deref(), Some("B"));
assert_eq!(builder.top_mark.as_deref(), Some("A"));
let fired = builder.contribute(page_of(["C", "D"]));
assert_eq!(fired.len(), 1);
assert_eq!(builder.top_mark.as_deref(), Some("B"));
assert_eq!(builder.first_mark.as_deref(), Some("C"));
assert_eq!(builder.bot_mark.as_deref(), Some("D"));
}
#[test]
fn an_insertion_reduces_the_page_goal_by_what_it_takes() {
let mut inserts = BTreeMap::new();
inserts.insert(
1,
InsertClass {
count: 1000,
dimen: pt(200),
skip: Glue::fixed(pt(5)),
},
);
let mut builder = PageBuilder::new(PageParams {
vsize: pt(200),
max_depth: pt(4),
top_skip: Glue::fixed(pt(10)),
inserts,
..PageParams::default()
});
builder.contribute(vec![
line(pt(10), 0),
Node::Ins(InsNode {
number: 1,
height: pt(20),
depth: pt(4),
float_cost: 100,
split_top_skip: Glue::fixed(pt(10)),
list: vec![line(pt(20), 0)],
}),
]);
assert_eq!(builder.page_goal(), pt(200 - 5 - 20));
}
#[test]
fn a_fired_page_leaves_its_insertions_in_their_boxes() {
let mut inserts = BTreeMap::new();
inserts.insert(
1,
InsertClass {
count: 1000,
dimen: pt(200),
skip: Glue::fixed(pt(5)),
},
);
let mut builder = PageBuilder::new(PageParams {
vsize: pt(100),
max_depth: pt(4),
top_skip: Glue::fixed(pt(10)),
inserts,
..PageParams::default()
});
let fired = builder.contribute(vec![
line(pt(10), 0),
Node::Ins(InsNode {
number: 1,
height: pt(20),
depth: 0,
float_cost: 100,
split_top_skip: Glue::fixed(pt(10)),
list: vec![line(pt(20), 0)],
}),
skip(pt(2), pt(1), pt(1)),
line(pt(10), 0),
Node::Penalty(EJECT_PENALTY),
]);
assert_eq!(fired.len(), 1);
let Fired::ShipOut(page) = &fired[0] else {
panic!("with no \\output the page ships");
};
assert!(!page.list.iter().any(|n| matches!(n, Node::Ins(_))));
let footnotes = builder.boxes.get(&1).expect("\\box1 holds the footnote");
assert!(footnotes.vertical);
assert_eq!(footnotes.height, pt(20));
}
#[test]
fn widow_and_club_penalties_land_where_tex_puts_them() {
let p = ParPenalties::latex();
assert_eq!(interline_penalty(0, 2, false, p), Some(300));
assert_eq!(interline_penalty(1, 2, false, p), None);
assert_eq!(interline_penalty(0, 4, false, p), Some(150));
assert_eq!(interline_penalty(1, 4, false, p), None);
assert_eq!(interline_penalty(2, 4, false, p), Some(150));
assert_eq!(interline_penalty(3, 4, false, p), None);
assert_eq!(interline_penalty(1, 4, true, p), Some(100));
assert_eq!(interline_penalty(0, 1, false, p), None);
}
#[test]
fn a_widow_penalty_moves_the_break_a_line_earlier() {
let baselines = Baselines {
baseline_skip: Glue {
natural: pt(12),
stretch: pt(6),
..Glue::default()
},
..Baselines::plain()
};
let refuse_widows = ParPenalties {
widow: 10000,
club: 10000,
..ParPenalties::latex()
};
let make = |penalties: Option<ParPenalties>| {
let mut list = Vec::new();
let mut prev_depth = crate::node::IGNORE_DEPTH;
for i in 0..4 {
crate::pack::append_to_vlist(
&mut list,
BoxNode {
width: pt(100),
height: pt(10),
..BoxNode::null()
},
&mut prev_depth,
baselines,
);
if let Some(p) = penalties {
if let Some(pen) = interline_penalty(i, 4, false, p) {
list.push(Node::Penalty(pen));
}
}
}
list
};
let brk = vert_break(&make(None), pt(34), pt(4));
assert_eq!(brk.place, Some(5));
assert_eq!(brk.cost, 0);
let penalised = vert_break(&make(Some(refuse_widows)), pt(34), pt(4));
assert_eq!(penalised.place, Some(4));
assert_eq!(penalised.cost, badness(pt(12), pt(6)));
assert_eq!(penalised.cost, 800);
}
}