diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/geom/length.rs | 5 | ||||
| -rw-r--r-- | src/layout/grid.rs | 10 | ||||
| -rw-r--r-- | src/layout/incremental.rs | 173 | ||||
| -rw-r--r-- | src/layout/mod.rs | 14 | ||||
| -rw-r--r-- | src/layout/pad.rs | 11 | ||||
| -rw-r--r-- | src/layout/par.rs | 35 | ||||
| -rw-r--r-- | src/layout/stack.rs | 31 |
7 files changed, 235 insertions, 44 deletions
diff --git a/src/geom/length.rs b/src/geom/length.rs index ecfe5616..951cef4f 100644 --- a/src/geom/length.rs +++ b/src/geom/length.rs @@ -108,6 +108,11 @@ impl Length { self.raw + 1e-6 >= other.raw } + /// Compares two 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..33fce064 100644 --- a/src/layout/grid.rs +++ b/src/layout/grid.rs @@ -56,6 +56,8 @@ struct GridLayouter<'a> { cross: SpecAxis, /// The axis of the main direction. main: SpecAxis, + /// The original expand state of the target region. + expand: Spec<bool>, /// The column tracks including gutter tracks. cols: Vec<TrackSizing>, /// The row tracks including gutter tracks. @@ -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 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(expand), regions, + 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.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..9eda0402 100644 --- a/src/layout/incremental.rs +++ b/src/layout/incremental.rs @@ -1,4 +1,5 @@ -use std::{collections::HashMap, ops::Deref}; +use std::collections::{hash_map::Entry, HashMap}; +use std::ops::Deref; use super::*; @@ -6,14 +7,18 @@ use super::*; #[derive(Default, Debug, Clone)] pub struct LayoutCache { /// Maps from node hashes to the resulting frames and regions in which the - /// frames are valid. - pub frames: HashMap<u64, FramesEntry>, + /// frames are valid. The right hand side of the hash map is a vector of + /// results because across one or more compilations, multiple different + /// layouts of the same node may have been requested. + 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. @@ -21,42 +26,143 @@ impl LayoutCache { self.frames.clear(); } + /// Amount of items in the cache. + pub fn len(&self) -> usize { + self.frames.iter().map(|(_, e)| e.len()).sum() + } + /// Retains all elements for which the closure on the level returns `true`. pub fn retain<F>(&mut self, mut f: F) where F: FnMut(usize) -> bool, { - self.frames.retain(|_, entry| f(entry.level)); + for (_, entries) in self.frames.iter_mut() { + entries.retain(|entry| f(entry.level)); + } } - /// Amount of items in the cache. - pub fn len(&self) -> usize { - self.frames.len() + /// 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 + 1] = entry.temperature[i]; + } + entry.temperature[0] = 0; + entry.age += 1; + } + } + + /// The amount of levels stored 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); + match self.frames.entry(hash) { + Entry::Occupied(o) => o.into_mut().push(entry), + Entry::Vacant(v) => { + v.insert(vec![entry]); + } + } } } -#[derive(Debug, Clone)] /// Cached frames from past layouting. +#[derive(Debug, Clone)] pub struct FramesEntry { /// The cached frames for a node. pub frames: Vec<Constrained<Rc<Frame>>>, /// How nested the frame was in the context is was originally appearing in. pub level: usize, + /// For how long the element already exists. + age: usize, + /// How much the element was accessed during the last five compilations, the + /// most recent one being the first element. + temperature: [usize; 5], } impl FramesEntry { + /// Construct a new instance. + pub fn new(frames: Vec<Constrained<Rc<Frame>>>, level: usize) -> Self { + Self { + frames, + level, + age: 1, + temperature: [0; 5], + } + } + /// 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(®ions) { return None; } } + self.temperature[0] += 1; + Some(self.frames.clone()) } + + /// Get the amount of compilation cycles this item has remained in the + /// cache. + pub fn age(&self) -> usize { + self.age + } + + /// Get the amount of consecutive cycles in which this item has not + /// been used. + pub fn cooldown(&self) -> usize { + let mut cycle = 0; + for &temp in &self.temperature[.. self.age] { + if temp > 0 { + return cycle; + } + cycle += 1; + } + + cycle + } + + /// Whether this element was used in the last compilation cycle. + pub fn hit(&self) -> bool { + self.temperature[0] != 0 + } } +/// Describe regions that match them. #[derive(Debug, Copy, Clone, PartialEq)] pub struct Constraints { /// The minimum available length in the region. @@ -107,25 +213,40 @@ 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)) + 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))) } - /// 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] { - if let Some(horizontal) = x.horizontal.as_mut() { + /// Changes all constraints by adding the `size` to them if they are `Some`. + pub fn mutate(&mut self, size: Size, regions: &Regions) { + for spec in std::array::IntoIter::new([ + &mut self.min, + &mut self.max, + &mut self.exact, + &mut self.base, + ]) { + if let Some(horizontal) = spec.horizontal.as_mut() { *horizontal += size.width; } - if let Some(vertical) = x.vertical.as_mut() { + if let Some(vertical) = spec.vertical.as_mut() { *vertical += size.height; } } + + let current = regions.current.to_spec(); + let base = regions.base.to_spec(); + + self.exact.horizontal.set_if_some(current.horizontal); + self.exact.vertical.set_if_some(current.vertical); + self.base.horizontal.set_if_some(base.horizontal); + self.base.vertical.set_if_some(base.vertical); } } +/// Carries an item that only applies to certain regions and the constraints +/// that describe these regions. #[derive(Debug, Copy, Clone, PartialEq)] pub struct Constrained<T> { pub item: T, @@ -140,9 +261,19 @@ impl<T> Deref for Constrained<T> { } } +/// Extends length-related options by providing convenience methods for setting +/// minimum and maximum lengths on them, even if they are `None`. pub trait OptionExt { + // Sets `other` as the value if the Option is `None` or if it contains a + // value larger than `other`. fn set_min(&mut self, other: Length); + + // Sets `other` as the value if the Option is `None` or if it contains a + // value smaller than `other`. fn set_max(&mut self, other: Length); + + /// Sets `other` as the value if the Option is `Some`. + fn set_if_some(&mut self, other: Length); } impl OptionExt for Option<Length> { @@ -159,4 +290,10 @@ impl OptionExt for Option<Length> { None => *self = Some(other), } } + + fn set_if_some(&mut self, other: Length) { + if self.is_some() { + *self = Some(other); + } + } } 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..9461f3ff 100644 --- a/src/layout/pad.rs +++ b/src/layout/pad.rs @@ -15,9 +15,11 @@ impl Layout for PadNode { ctx: &mut LayoutContext, regions: &Regions, ) -> Vec<Constrained<Rc<Frame>>> { - let mut regions = regions.map(|size| size - self.padding.resolve(size).size()); - - let mut frames = self.child.layout(ctx, ®ions); + let mut regions = regions.clone(); + let mut frames = self.child.layout( + ctx, + ®ions.map(|size| size - self.padding.resolve(size).size()), + ); for frame in &mut frames { let padded = solve(self.padding, frame.size); @@ -28,7 +30,7 @@ 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(), ®ions); if self.padding.left.is_relative() || self.padding.right.is_relative() { frame.constraints.base.horizontal = Some(regions.base.width); @@ -40,6 +42,7 @@ impl Layout for PadNode { regions.next(); *Rc::make_mut(&mut frame.item) = new; } + frames } } diff --git a/src/layout/par.rs b/src/layout/par.rs index 2208f9ee..45eefe29 100644 --- a/src/layout/par.rs +++ b/src/layout/par.rs @@ -190,6 +190,7 @@ impl<'a> ParLayouter<'a> { // line cannot be broken up further. if !stack.regions.current.fits(line.size) { if let Some((last_line, last_end)) = last.take() { + // The region must not fit this line for the result to be valid. if !stack.regions.current.width.fits(line.size.width) { stack.constraints.max.horizontal.set_min(line.size.width); } @@ -213,10 +214,31 @@ 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); + // Again, the line must not fit. It would if the space taken up + // plus the line height would fit, therefore the constraint + // below. + stack + .constraints + .max + .vertical + .set_min(stack.size.height + line.size.height); stack.finish_region(ctx); } + // If the line does not fit vertically, we start a new region. + while !stack.regions.current.height.fits(line.size.height) { + if stack.regions.in_full_last() { + stack.overflowing = true; + break; + } + + stack + .constraints + .max + .vertical + .set_min(stack.size.height + line.size.height); + stack.finish_region(ctx); + } // 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 +325,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 +340,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 +369,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 +394,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..fa5fd584 100644 --- a/src/layout/stack.rs +++ b/src/layout/stack.rs @@ -62,6 +62,8 @@ struct StackLayouter<'a> { ruler: Align, /// The constraints for the current region. constraints: Constraints, + /// Whether the last region can fit all the remaining content. + overflowing: bool, /// Offset, alignment and frame for all children that fit into the current /// region. The exact positions are not known yet. frames: Vec<(Length, Gen<Align>, Rc<Frame>)>, @@ -87,11 +89,12 @@ impl<'a> StackLayouter<'a> { stack, main, expand, - constraints: Constraints::new(regions.expand), regions, full, used: Gen::zero(), ruler: Align::Start, + constraints: Constraints::new(expand), + overflowing: false, frames: vec![], finished: vec![], } @@ -142,10 +145,16 @@ impl<'a> StackLayouter<'a> { } // Find a fitting region. - 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); + while !self.regions.current.get(self.main).fits(size.main) { + if self.regions.in_full_last() { + self.overflowing = true; + break; + } + + self.constraints + .max + .get_mut(self.main) + .set_min(self.used.main + size.main); self.finish_region(); } @@ -188,7 +197,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) @@ -198,6 +209,12 @@ impl<'a> StackLayouter<'a> { size = Size::new(width, width / aspect.into_inner()); } + 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(size, size.height); let mut first = true; @@ -244,6 +261,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); } } |