ailloli_ui_editor/layout/paragraph_metrics.rs
1//! Cached paragraph dimensions, revision metadata, and prefix-sum lookup.
2
3use std::collections::HashMap;
4use std::ops::Range;
5
6use super::layout_cache::LayoutCacheKey;
7
8/// Cached metrics for one logical paragraph under one layout configuration.
9///
10/// Width and height are logical pixels, `line_count` counts shaped visual lines,
11/// and `local_version` mirrors the source paragraph revision.
12///
13/// # Examples
14///
15/// ```
16/// use ailloli_ui_editor::layout::ParagraphMetrics;
17/// let metrics = ParagraphMetrics { width: 80.0, height: 36.0, line_count: 2, local_version: 7 };
18/// assert_eq!(metrics.line_count, 2);
19/// ```
20#[derive(Debug, Clone, Copy, PartialEq)]
21pub struct ParagraphMetrics {
22 /// Maximum shaped line width in logical pixels.
23 pub width: f32,
24 /// Complete paragraph visual height in logical pixels.
25 pub height: f32,
26 /// Number of shaped visual lines, normally at least one.
27 pub line_count: usize,
28 /// Source paragraph revision from which these metrics were computed.
29 pub local_version: u64,
30}
31
32/// Aggregate metadata from the most recent layout pass.
33///
34/// A first pass has no prior revision set and therefore reports
35/// `dirty_range == None`. Later changes use a half-open paragraph-index range;
36/// a changed paragraph count marks `0..paragraph_count` dirty.
37///
38/// # Examples
39///
40/// ```
41/// use ailloli_ui_core::Rect;
42/// use ailloli_ui_editor::{layout::{build_visible_text_layout, LayoutCache, ParagraphMetricsCache}, EditorConfig, EditorStyle, EditorViewport};
43/// use ailloli_ui_text::{TextBuffer, TextEditState, TextSystem};
44/// let buffer = TextBuffer::from_string("a\nb");
45/// let viewport = EditorViewport::new(Rect::new(0.0, 0.0, 100.0, 60.0), EditorConfig::default(), &TextEditState::new());
46/// let (mut layouts, mut metrics, mut text_system) = (LayoutCache::default(), ParagraphMetricsCache::default(), TextSystem::new());
47/// build_visible_text_layout(&buffer, viewport, EditorStyle::default(), &mut layouts, &mut metrics, &mut text_system);
48/// assert_eq!(metrics.metadata().unwrap().paragraph_count, 2);
49/// ```
50#[derive(Debug, Clone, PartialEq)]
51pub struct ParagraphMetricsMetadata {
52 /// Number of logical paragraphs observed in the last pass.
53 pub paragraph_count: usize,
54 /// Smallest half-open range whose stored revisions changed, if any.
55 pub dirty_range: Option<Range<usize>>,
56 /// Maximum paragraph revision, or zero for no paragraphs.
57 pub local_version: u64,
58 /// Sum of visible paragraph heights in logical pixels.
59 pub total_height: f32,
60 /// Maximum visible paragraph width in logical pixels.
61 pub max_width: f32,
62 /// Per-paragraph revisions retained for the next difference calculation.
63 revisions: Vec<u64>,
64}
65
66/// Cache hit/miss counts for one visible-layout build.
67///
68/// # Examples
69///
70/// ```
71/// use ailloli_ui_editor::layout::ParagraphMetricsStats;
72/// let stats = ParagraphMetricsStats::default();
73/// assert_eq!((stats.hits, stats.misses), (0, 0));
74/// ```
75#[derive(Debug, Clone, Copy, PartialEq, Eq, Default)]
76pub struct ParagraphMetricsStats {
77 /// Paragraph metric entries reused from the cache.
78 pub hits: usize,
79 /// Paragraph metric entries computed and inserted.
80 pub misses: usize,
81}
82
83/// Per-engine paragraph metrics cache.
84///
85/// Metrics are indexed by the same geometry key as layouts. Aggregate metadata
86/// is absent until a visible-layout build completes.
87///
88/// # Examples
89///
90/// ```
91/// use ailloli_ui_editor::layout::ParagraphMetricsCache;
92/// let cache = ParagraphMetricsCache::default();
93/// assert!(cache.metadata().is_none());
94/// ```
95#[derive(Debug, Clone, Default)]
96pub struct ParagraphMetricsCache {
97 /// Per-layout-key paragraph metrics.
98 metrics: HashMap<LayoutCacheKey, ParagraphMetrics>,
99 /// Aggregate information from the last completed build.
100 metadata: Option<ParagraphMetricsMetadata>,
101}
102
103/// Resolves, updates, and invalidates paragraph metrics.
104impl ParagraphMetricsCache {
105 /// Returns a copied metrics entry for an internal layout key.
106 ///
107 /// # Examples
108 ///
109 /// ```
110 /// use ailloli_ui_core::Rect;
111 /// use ailloli_ui_editor::{layout::{build_visible_text_layout, LayoutCache, ParagraphMetricsCache}, EditorConfig, EditorStyle, EditorViewport};
112 /// use ailloli_ui_text::{TextBuffer, TextEditState, TextSystem};
113 /// let buffer = TextBuffer::from_string("cached");
114 /// let viewport = EditorViewport::new(Rect::new(0.0, 0.0, 100.0, 50.0), EditorConfig::default(), &TextEditState::new());
115 /// let (mut layouts, mut metrics, mut system) = (LayoutCache::default(), ParagraphMetricsCache::default(), TextSystem::new());
116 /// build_visible_text_layout(&buffer, viewport, EditorStyle::default(), &mut layouts, &mut metrics, &mut system);
117 /// let second = build_visible_text_layout(&buffer, viewport, EditorStyle::default(), &mut layouts, &mut metrics, &mut system);
118 /// assert!(second.metrics_stats.hits >= 1);
119 /// ```
120 pub(crate) fn get(&self, key: &LayoutCacheKey) -> Option<ParagraphMetrics> {
121 self.metrics.get(key).copied()
122 }
123
124 /// Inserts or replaces metrics for an internal layout key.
125 ///
126 /// # Examples
127 ///
128 /// ```
129 /// use ailloli_ui_editor::layout::ParagraphMetricsCache;
130 /// let cache = ParagraphMetricsCache::default();
131 /// assert!(cache.metadata().is_none()); // public layout builders populate entries
132 /// ```
133 pub(crate) fn insert(&mut self, key: LayoutCacheKey, metrics: ParagraphMetrics) {
134 self.metrics.insert(key, metrics);
135 }
136
137 /// Replaces aggregate metadata and computes its revision difference.
138 ///
139 /// `revisions` should yield exactly `paragraph_count` entries, but the
140 /// method does not enforce that invariant. Heights and widths are stored
141 /// verbatim. `local_version` becomes the maximum revision or zero.
142 ///
143 /// # Examples
144 ///
145 /// ```
146 /// use ailloli_ui_core::Rect;
147 /// use ailloli_ui_editor::{layout::{build_visible_text_layout, LayoutCache, ParagraphMetricsCache}, EditorConfig, EditorStyle, EditorViewport};
148 /// use ailloli_ui_text::{TextBuffer, TextEditState, TextSystem};
149 /// let buffer = TextBuffer::from_string("one\ntwo");
150 /// let viewport = EditorViewport::new(Rect::new(0.0, 0.0, 120.0, 60.0), EditorConfig::default(), &TextEditState::new());
151 /// let (mut layouts, mut metrics, mut system) = (LayoutCache::default(), ParagraphMetricsCache::default(), TextSystem::new());
152 /// let visible = build_visible_text_layout(&buffer, viewport, EditorStyle::default(), &mut layouts, &mut metrics, &mut system);
153 /// assert_eq!(metrics.metadata().unwrap().total_height, visible.content_size.h);
154 /// ```
155 pub(crate) fn update_metadata(
156 &mut self,
157 paragraph_count: usize,
158 revisions: impl Iterator<Item = u64>,
159 total_height: f32,
160 max_width: f32,
161 ) {
162 let revisions: Vec<_> = revisions.collect();
163 let dirty_range = self.metadata.as_ref().and_then(|previous| {
164 if previous.paragraph_count != paragraph_count {
165 return Some(0..paragraph_count);
166 }
167 let mut first = None;
168 let mut last = 0;
169 for (idx, revision) in revisions.iter().enumerate() {
170 if previous.revisions.get(idx).copied() != Some(*revision) {
171 first.get_or_insert(idx);
172 last = idx + 1;
173 }
174 }
175 first.map(|start| start..last)
176 });
177 let local_version = revisions.iter().copied().max().unwrap_or(0);
178 self.metadata = Some(ParagraphMetricsMetadata {
179 paragraph_count,
180 dirty_range,
181 local_version,
182 total_height,
183 max_width,
184 revisions,
185 });
186 }
187
188 /// Returns aggregate metadata from the last completed layout build.
189 ///
190 /// Returns `None` before the first build and after [`Self::clear`].
191 ///
192 /// # Examples
193 ///
194 /// ```
195 /// use ailloli_ui_editor::layout::ParagraphMetricsCache;
196 /// assert!(ParagraphMetricsCache::default().metadata().is_none());
197 /// ```
198 pub fn metadata(&self) -> Option<&ParagraphMetricsMetadata> {
199 self.metadata.as_ref()
200 }
201
202 /// Removes all per-paragraph metrics and aggregate metadata.
203 ///
204 /// # Examples
205 ///
206 /// ```
207 /// use ailloli_ui_editor::layout::ParagraphMetricsCache;
208 /// let mut cache = ParagraphMetricsCache::default();
209 /// cache.clear();
210 /// assert!(cache.metadata().is_none());
211 /// ```
212 pub fn clear(&mut self) {
213 self.metrics.clear();
214 self.metadata = None;
215 }
216}
217
218/// Prefix-sum index used to map vertical offsets to paragraph indices.
219///
220/// [`FenwickTree::lower_bound`] assumes finite, non-negative values so prefix
221/// sums are monotonic; construction does not validate this invariant.
222///
223/// # Examples
224///
225/// ```
226/// use ailloli_ui_editor::layout::FenwickTree;
227/// let tree = FenwickTree::from_values(&[10.0, 20.0, 30.0]);
228/// assert_eq!(tree.prefix_sum(2), 30.0);
229/// ```
230#[derive(Debug, Clone, PartialEq)]
231pub struct FenwickTree {
232 /// Original values, retained for length and diagnostics.
233 values: Vec<f32>,
234 /// One-based Fenwick partial sums with a zero sentinel at index zero.
235 tree: Vec<f32>,
236}
237
238/// Builds and queries prefix sums.
239impl FenwickTree {
240 /// Builds a tree in `O(n log n)` from copied values.
241 ///
242 /// An empty slice is valid and produces a zero-length index.
243 ///
244 /// # Examples
245 ///
246 /// ```
247 /// use ailloli_ui_editor::layout::FenwickTree;
248 /// assert_eq!(FenwickTree::from_values(&[]).prefix_sum(9), 0.0);
249 /// assert_eq!(FenwickTree::from_values(&[2.0, 3.0]).prefix_sum(2), 5.0);
250 /// ```
251 pub fn from_values(values: &[f32]) -> Self {
252 let mut tree = Self {
253 values: values.to_vec(),
254 tree: vec![0.0; values.len() + 1],
255 };
256 for (idx, value) in values.iter().copied().enumerate() {
257 tree.add(idx, value);
258 }
259 tree
260 }
261
262 /// Returns the sum of values before `end`.
263 ///
264 /// `end` is clamped to the number of values. Queries take `O(log n)` time.
265 ///
266 /// # Examples
267 ///
268 /// ```
269 /// use ailloli_ui_editor::layout::FenwickTree;
270 /// let tree = FenwickTree::from_values(&[2.0, 3.0, 5.0]);
271 /// assert_eq!(tree.prefix_sum(0), 0.0);
272 /// assert_eq!(tree.prefix_sum(usize::MAX), 10.0);
273 /// ```
274 pub fn prefix_sum(&self, end: usize) -> f32 {
275 let mut idx = end.min(self.values.len());
276 let mut sum = 0.0;
277 while idx > 0 {
278 sum += self.tree[idx];
279 idx &= idx - 1;
280 }
281 sum
282 }
283
284 /// Locates the zero-based value whose cumulative end reaches `target`.
285 ///
286 /// Non-positive targets return zero. A target greater than the total sum
287 /// returns the number of values. Equality belongs to the preceding value,
288 /// which matches viewport offsets on a paragraph's lower edge. Queries take
289 /// `O(log n)` time and require non-negative finite values for meaningful
290 /// ordering.
291 ///
292 /// # Examples
293 ///
294 /// ```
295 /// use ailloli_ui_editor::layout::FenwickTree;
296 /// let tree = FenwickTree::from_values(&[10.0, 20.0, 30.0]);
297 /// assert_eq!(tree.lower_bound(0.0), 0);
298 /// assert_eq!(tree.lower_bound(10.0), 0);
299 /// assert_eq!(tree.lower_bound(10.5), 1);
300 /// assert_eq!(tree.lower_bound(60.5), 3);
301 /// ```
302 pub fn lower_bound(&self, target: f32) -> usize {
303 if target <= 0.0 {
304 return 0;
305 }
306 let mut idx = 0usize;
307 let mut bit = 1usize;
308 while bit < self.values.len() {
309 bit <<= 1;
310 }
311 let mut sum = 0.0;
312 while bit > 0 {
313 let next = idx + bit;
314 if next <= self.values.len() && sum + self.tree[next] < target {
315 sum += self.tree[next];
316 idx = next;
317 }
318 bit >>= 1;
319 }
320 idx.min(self.values.len())
321 }
322
323 /// Adds a delta to one value and its covering Fenwick nodes.
324 fn add(&mut self, idx: usize, delta: f32) {
325 let mut tree_idx = idx + 1;
326 while tree_idx < self.tree.len() {
327 self.tree[tree_idx] += delta;
328 tree_idx += tree_idx & (!tree_idx + 1);
329 }
330 }
331}