summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/geom/length.rs5
-rw-r--r--src/layout/grid.rs10
-rw-r--r--src/layout/incremental.rs155
-rw-r--r--src/layout/mod.rs14
-rw-r--r--src/layout/pad.rs7
-rw-r--r--src/layout/par.rs21
-rw-r--r--src/layout/stack.rs13
-rw-r--r--tests/typeset.rs56
8 files changed, 245 insertions, 36 deletions
diff --git a/src/geom/length.rs b/src/geom/length.rs
index ecfe5616..08bf3111 100644
--- a/src/geom/length.rs
+++ b/src/geom/length.rs
@@ -108,6 +108,11 @@ impl Length {
self.raw + 1e-6 >= other.raw
}
+ /// Compares to lengths for whether they are approximately equal.
+ pub fn approx_eq(self, other: Self) -> bool {
+ self == other || (self - other).to_raw().abs() < 1e-6
+ }
+
/// Whether the length is zero.
pub fn is_zero(self) -> bool {
self.raw == 0.0
diff --git a/src/layout/grid.rs b/src/layout/grid.rs
index d2976502..996ce7c2 100644
--- a/src/layout/grid.rs
+++ b/src/layout/grid.rs
@@ -64,6 +64,8 @@ struct GridLayouter<'a> {
children: &'a [AnyNode],
/// The region to layout into.
regions: Regions,
+ /// The original expand state of the target region.
+ original_expand: Spec<bool>,
/// Resolved column sizes.
rcols: Vec<Length>,
/// The full main size of the current region.
@@ -135,7 +137,8 @@ impl<'a> GridLayouter<'a> {
let full = regions.current.get(main);
let rcols = vec![Length::zero(); cols.len()];
- // We use the regions only for auto row measurement.
+ // We use the regions only for auto row measurement and constraints.
+ let original_expand = regions.expand;
regions.expand = Gen::new(true, false).to_spec(main);
Self {
@@ -144,8 +147,9 @@ impl<'a> GridLayouter<'a> {
cols,
rows,
children: &grid.children,
- constraints: Constraints::new(regions.expand),
+ constraints: Constraints::new(original_expand),
regions,
+ original_expand,
rcols,
lrows: vec![],
full,
@@ -506,7 +510,7 @@ impl<'a> GridLayouter<'a> {
self.used.main = Length::zero();
self.fr = Fractional::zero();
self.finished.push(output.constrain(self.constraints));
- self.constraints = Constraints::new(self.regions.expand);
+ self.constraints = Constraints::new(self.original_expand);
}
/// Get the node in the cell in column `x` and row `y`.
diff --git a/src/layout/incremental.rs b/src/layout/incremental.rs
index a5c3cea3..e1d1ffba 100644
--- a/src/layout/incremental.rs
+++ b/src/layout/incremental.rs
@@ -7,13 +7,15 @@ use super::*;
pub struct LayoutCache {
/// Maps from node hashes to the resulting frames and regions in which the
/// frames are valid.
- pub frames: HashMap<u64, FramesEntry>,
+ pub frames: HashMap<u64, Vec<FramesEntry>>,
+ /// In how many compilations this cache has been used.
+ age: usize,
}
impl LayoutCache {
/// Create a new, empty layout cache.
pub fn new() -> Self {
- Self { frames: HashMap::new() }
+ Self { frames: HashMap::new(), age: 0 }
}
/// Clear the cache.
@@ -26,12 +28,68 @@ impl LayoutCache {
where
F: FnMut(usize) -> bool,
{
- self.frames.retain(|_, entry| f(entry.level));
+ for (_, hash_ident) in self.frames.iter_mut() {
+ hash_ident.retain(|entry| f(entry.level));
+ }
}
/// Amount of items in the cache.
pub fn len(&self) -> usize {
- self.frames.len()
+ self.frames.iter().map(|(_, e)| e.len()).sum()
+ }
+
+ /// Prepare the cache for the next round of compilation
+ pub fn turnaround(&mut self) {
+ self.age += 1;
+ for entry in self.frames.iter_mut().flat_map(|(_, x)| x.iter_mut()) {
+ for i in 0 .. (entry.temperature.len() - 1) {
+ entry.temperature[i] = entry.temperature[i + 1];
+ }
+ *entry.temperature.last_mut().unwrap() = Some(0);
+ }
+ }
+
+ /// What is the deepest level in the cache?
+ pub fn levels(&self) -> usize {
+ self.frames
+ .iter()
+ .flat_map(|(_, x)| x)
+ .map(|entry| entry.level + 1)
+ .max()
+ .unwrap_or(0)
+ }
+
+ /// Fetches the appropriate entry from the cache if there is any.
+ pub fn get(
+ &mut self,
+ hash: u64,
+ regions: Regions,
+ ) -> Option<Vec<Constrained<Rc<Frame>>>> {
+ self.frames.get_mut(&hash).and_then(|frames| {
+ for frame in frames {
+ let res = frame.check(regions.clone());
+ if res.is_some() {
+ return res;
+ }
+ }
+
+ None
+ })
+ }
+
+ /// Inserts a new frame set into the cache.
+ pub fn insert(
+ &mut self,
+ hash: u64,
+ frames: Vec<Constrained<Rc<Frame>>>,
+ level: usize,
+ ) {
+ let entry = FramesEntry::new(frames, level);
+ if let Some(variants) = self.frames.get_mut(&hash) {
+ variants.push(entry);
+ } else {
+ self.frames.insert(hash, vec![entry]);
+ }
}
}
@@ -42,19 +100,72 @@ pub struct FramesEntry {
pub frames: Vec<Constrained<Rc<Frame>>>,
/// How nested the frame was in the context is was originally appearing in.
pub level: usize,
+ /// How much the element was accessed during the last five compilations, the
+ /// most current one being the last element. `None` variants indicate that
+ /// the element is younger than five compilations.
+ temperature: [Option<usize>; 5],
}
impl FramesEntry {
+ /// Construct a new instance.
+ pub fn new(frames: Vec<Constrained<Rc<Frame>>>, level: usize) -> Self {
+ let mut temperature = [None; 5];
+ temperature[4] = Some(0);
+ Self { frames, level, temperature }
+ }
+
/// Checks if the cached [`Frame`] is valid for the given regions.
- pub fn check(&self, mut regions: Regions) -> Option<Vec<Constrained<Rc<Frame>>>> {
+ pub fn check(&mut self, mut regions: Regions) -> Option<Vec<Constrained<Rc<Frame>>>> {
for (i, frame) in self.frames.iter().enumerate() {
if (i != 0 && !regions.next()) || !frame.constraints.check(&regions) {
return None;
}
}
+ let tmp = self.temperature.get_mut(4).unwrap();
+ *tmp = Some(tmp.map_or(1, |x| x + 1));
+
Some(self.frames.clone())
}
+
+ /// Get the amount of compilation cycles this item has remained in the
+ /// cache.
+ pub fn age(&self) -> usize {
+ let mut age = 0;
+ for &temp in self.temperature.iter().rev() {
+ if temp.is_none() {
+ break;
+ }
+ age += 1;
+ }
+ age
+ }
+
+ /// Get the amount of consecutive cycles in which this item has not
+ /// been used.
+ pub fn cooldown(&self) -> usize {
+ let mut age = 0;
+ for (i, &temp) in self.temperature.iter().enumerate().rev() {
+ match temp {
+ Some(temp) => {
+ if temp > 0 {
+ return self.temperature.len() - 1 - i;
+ }
+ }
+ None => {
+ return age;
+ }
+ }
+ age += 1
+ }
+
+ age
+ }
+
+ /// Whether this element was used in the last compilation cycle.
+ pub fn hit(&self) -> bool {
+ self.temperature.last().unwrap().unwrap_or(0) != 0
+ }
}
#[derive(Debug, Copy, Clone, PartialEq)]
@@ -107,15 +218,22 @@ impl Constraints {
let base = regions.base.to_spec();
let current = regions.current.to_spec();
- current.eq_by(&self.min, |x, y| y.map_or(true, |y| x >= &y))
+ let res = current.eq_by(&self.min, |&x, y| y.map_or(true, |y| x.fits(y)))
&& current.eq_by(&self.max, |x, y| y.map_or(true, |y| x < &y))
- && current.eq_by(&self.exact, |x, y| y.map_or(true, |y| x == &y))
- && base.eq_by(&self.base, |x, y| y.map_or(true, |y| x == &y))
+ && current.eq_by(&self.exact, |&x, y| y.map_or(true, |y| x.approx_eq(y)))
+ && base.eq_by(&self.base, |&x, y| y.map_or(true, |y| x.approx_eq(y)));
+
+ res
}
/// Changes all constraints by adding the argument to them if they are set.
- pub fn mutate(&mut self, size: Size) {
- for x in &mut [self.min, self.max, self.exact, self.base] {
+ pub fn mutate(&mut self, size: Size, regions: &Regions) {
+ for x in std::array::IntoIter::new([
+ &mut self.min,
+ &mut self.max,
+ &mut self.exact,
+ &mut self.base,
+ ]) {
if let Some(horizontal) = x.horizontal.as_mut() {
*horizontal += size.width;
}
@@ -123,6 +241,23 @@ impl Constraints {
*vertical += size.height;
}
}
+
+ self.exact = zip(self.exact, regions.current.to_spec(), |_, o| o);
+ self.base = zip(self.base, regions.base.to_spec(), |_, o| o);
+ }
+}
+
+fn zip<F>(
+ one: Spec<Option<Length>>,
+ other: Spec<Length>,
+ mut f: F,
+) -> Spec<Option<Length>>
+where
+ F: FnMut(Length, Length) -> Length,
+{
+ Spec {
+ vertical: one.vertical.map(|r| f(r, other.vertical)),
+ horizontal: one.horizontal.map(|r| f(r, other.horizontal)),
}
}
diff --git a/src/layout/mod.rs b/src/layout/mod.rs
index 10c30f41..dc819a16 100644
--- a/src/layout/mod.rs
+++ b/src/layout/mod.rs
@@ -102,18 +102,10 @@ impl Layout for AnyNode {
regions: &Regions,
) -> Vec<Constrained<Rc<Frame>>> {
ctx.level += 1;
- let frames = ctx
- .cache
- .layout
- .frames
- .get(&self.hash)
- .and_then(|x| x.check(regions.clone()))
- .unwrap_or_else(|| {
+ let frames =
+ ctx.cache.layout.get(self.hash, regions.clone()).unwrap_or_else(|| {
let frames = self.node.layout(ctx, regions);
- ctx.cache.layout.frames.insert(self.hash, FramesEntry {
- frames: frames.clone(),
- level: ctx.level - 1,
- });
+ ctx.cache.layout.insert(self.hash, frames.clone(), ctx.level - 1);
frames
});
ctx.level -= 1;
diff --git a/src/layout/pad.rs b/src/layout/pad.rs
index 9d432e79..cfde0719 100644
--- a/src/layout/pad.rs
+++ b/src/layout/pad.rs
@@ -15,6 +15,7 @@ impl Layout for PadNode {
ctx: &mut LayoutContext,
regions: &Regions,
) -> Vec<Constrained<Rc<Frame>>> {
+ let original = regions.clone();
let mut regions = regions.map(|size| size - self.padding.resolve(size).size());
let mut frames = self.child.layout(ctx, &regions);
@@ -28,13 +29,13 @@ impl Layout for PadNode {
let prev = std::mem::take(&mut frame.item);
new.push_frame(origin, prev);
- frame.constraints.mutate(padding.size() * -1.0);
+ frame.constraints.mutate(padding.size(), &original);
if self.padding.left.is_relative() || self.padding.right.is_relative() {
- frame.constraints.base.horizontal = Some(regions.base.width);
+ frame.constraints.base.horizontal = Some(original.base.width);
}
if self.padding.top.is_relative() || self.padding.bottom.is_relative() {
- frame.constraints.base.vertical = Some(regions.base.height);
+ frame.constraints.base.vertical = Some(original.base.height);
}
regions.next();
diff --git a/src/layout/par.rs b/src/layout/par.rs
index 2208f9ee..0cf1cd23 100644
--- a/src/layout/par.rs
+++ b/src/layout/par.rs
@@ -213,10 +213,18 @@ impl<'a> ParLayouter<'a> {
while !stack.regions.current.height.fits(line.size.height)
&& !stack.regions.in_full_last()
{
- stack.constraints.max.vertical.set_min(line.size.height);
+ stack.constraints.max.vertical.set_min(
+ stack.full.height - stack.regions.current.height + line.size.height,
+ );
stack.finish_region(ctx);
}
+ if !stack.regions.current.height.fits(line.size.height)
+ && stack.regions.in_full_last()
+ {
+ stack.overflowing = true;
+ }
+
// If the line does not fit horizontally or we have a mandatory
// line break (i.e. due to "\n"), we push the line into the
// stack.
@@ -303,11 +311,13 @@ impl ParItem<'_> {
/// Stacks lines on top of each other.
struct LineStack<'a> {
line_spacing: Length,
+ full: Size,
regions: Regions,
size: Size,
lines: Vec<LineLayout<'a>>,
finished: Vec<Constrained<Rc<Frame>>>,
constraints: Constraints,
+ overflowing: bool,
}
impl<'a> LineStack<'a> {
@@ -316,10 +326,12 @@ impl<'a> LineStack<'a> {
Self {
line_spacing,
constraints: Constraints::new(regions.expand),
+ full: regions.current,
regions,
size: Size::zero(),
lines: vec![],
finished: vec![],
+ overflowing: false,
}
}
@@ -343,6 +355,12 @@ impl<'a> LineStack<'a> {
self.constraints.exact.horizontal = Some(self.regions.current.width);
}
+ if self.overflowing {
+ self.constraints.min.vertical = None;
+ self.constraints.max.vertical = None;
+ self.constraints.exact = self.full.to_spec().map(Some);
+ }
+
let mut output = Frame::new(self.size, self.size.height);
let mut offset = Length::zero();
let mut first = true;
@@ -362,6 +380,7 @@ impl<'a> LineStack<'a> {
self.finished.push(output.constrain(self.constraints));
self.regions.next();
+ self.full = self.regions.current;
self.constraints = Constraints::new(self.regions.expand);
self.size = Size::zero();
}
diff --git a/src/layout/stack.rs b/src/layout/stack.rs
index 2a0b2806..92a1337f 100644
--- a/src/layout/stack.rs
+++ b/src/layout/stack.rs
@@ -86,8 +86,8 @@ impl<'a> StackLayouter<'a> {
Self {
stack,
main,
+ constraints: Constraints::new(expand),
expand,
- constraints: Constraints::new(regions.expand),
regions,
full,
used: Gen::zero(),
@@ -145,7 +145,10 @@ impl<'a> StackLayouter<'a> {
while !self.regions.current.get(self.main).fits(size.main)
&& !self.regions.in_full_last()
{
- self.constraints.max.get_mut(self.main).set_min(size.main);
+ self.constraints
+ .max
+ .get_mut(self.main)
+ .set_min(size.main + self.used.main);
self.finish_region();
}
@@ -188,7 +191,9 @@ impl<'a> StackLayouter<'a> {
// Make sure the stack's size satisfies the aspect ratio.
if let Some(aspect) = self.stack.aspect {
- self.constraints.exact = self.regions.current.to_spec().map(Some);
+ self.constraints.exact = self.full.to_spec().map(Some);
+ self.constraints.min = Spec::splat(None);
+ self.constraints.max = Spec::splat(None);
let width = size
.width
.max(aspect.into_inner() * size.height)
@@ -244,6 +249,6 @@ impl<'a> StackLayouter<'a> {
self.used = Gen::zero();
self.ruler = Align::Start;
self.finished.push(output.constrain(self.constraints));
- self.constraints = Constraints::new(self.regions.expand);
+ self.constraints = Constraints::new(expand);
}
}
diff --git a/tests/typeset.rs b/tests/typeset.rs
index c5f31e61..9e0c9596 100644
--- a/tests/typeset.rs
+++ b/tests/typeset.rs
@@ -224,10 +224,8 @@ fn test_part(
state.page.size = Size::new(Length::pt(120.0), Length::inf());
state.page.margins = Sides::splat(Some(Length::pt(10.0).into()));
- // Clear cache between tests (for now).
- cache.layout.clear();
-
- let mut pass = typst::typeset(loader, cache, Some(src_path), &src, &scope, state);
+ let mut pass =
+ typst::typeset(loader, cache, Some(src_path), &src, &scope, state.clone());
if !compare_ref {
pass.output.clear();
@@ -266,6 +264,56 @@ fn test_part(
}
}
+ let reference_cache = cache.layout.clone();
+ for level in 0 .. reference_cache.levels() {
+ cache.layout = reference_cache.clone();
+ cache.layout.retain(|x| x == level);
+ if cache.layout.frames.is_empty() {
+ continue;
+ }
+
+ cache.layout.turnaround();
+
+ let mut cached_result =
+ typst::typeset(loader, cache, Some(src_path), &src, &scope, state.clone());
+
+ if !compare_ref {
+ cached_result.output.clear();
+ }
+
+ let misses: Vec<_> = cache
+ .layout
+ .frames
+ .iter()
+ .flat_map(|(_, e)| e)
+ .filter(|e| e.level == level && !e.hit() && e.age() == 2)
+ .collect();
+
+ if !misses.is_empty() {
+ ok = false;
+ let mut miss_count = 0;
+ for miss in misses {
+ dbg!(miss.frames.iter().map(|f| f.constraints).collect::<Vec<_>>());
+ miss_count += 1;
+ }
+ println!(
+ " Recompilation had {} cache misses on level {} (Subtest {}) ❌",
+ miss_count, level, i
+ );
+ }
+
+ if cached_result != pass {
+ ok = false;
+ println!(
+ " Recompilation of subtest {} differs from clean pass ❌",
+ i
+ );
+ }
+ }
+
+ cache.layout = reference_cache;
+ cache.layout.turnaround();
+
(ok, compare_ref, pass.output)
}
generated by cgit v1.2.3 (git 2.25.1) at 2026-03-15 12:07:58 +0000