1use crate::{
2 color::Color,
3 fonts::{FontId, GlyphId, Underline},
4 geometry::{
5 rect::RectF,
6 vector::{vec2f, Vector2F},
7 },
8 platform, scene, FontSystem, PaintContext,
9};
10use ordered_float::OrderedFloat;
11use parking_lot::{Mutex, RwLock, RwLockUpgradableReadGuard};
12use smallvec::SmallVec;
13use std::{
14 borrow::Borrow,
15 collections::HashMap,
16 hash::{Hash, Hasher},
17 iter,
18 sync::Arc,
19};
20
21pub struct TextLayoutCache {
22 prev_frame: Mutex<HashMap<CacheKeyValue, Arc<LineLayout>>>,
23 curr_frame: RwLock<HashMap<CacheKeyValue, Arc<LineLayout>>>,
24 fonts: Arc<dyn platform::FontSystem>,
25}
26
27#[derive(Copy, Clone, Debug, PartialEq, Eq)]
28pub struct RunStyle {
29 pub color: Color,
30 pub font_id: FontId,
31 pub underline: Option<Underline>,
32}
33
34impl TextLayoutCache {
35 pub fn new(fonts: Arc<dyn platform::FontSystem>) -> Self {
36 Self {
37 prev_frame: Mutex::new(HashMap::new()),
38 curr_frame: RwLock::new(HashMap::new()),
39 fonts,
40 }
41 }
42
43 pub fn finish_frame(&self) {
44 let mut prev_frame = self.prev_frame.lock();
45 let mut curr_frame = self.curr_frame.write();
46 std::mem::swap(&mut *prev_frame, &mut *curr_frame);
47 curr_frame.clear();
48 }
49
50 pub fn layout_str<'a>(
51 &'a self,
52 text: &'a str,
53 font_size: f32,
54 runs: &'a [(usize, RunStyle)],
55 ) -> Line {
56 let key = &CacheKeyRef {
57 text,
58 font_size: OrderedFloat(font_size),
59 runs,
60 } as &dyn CacheKey;
61 let curr_frame = self.curr_frame.upgradable_read();
62 if let Some(layout) = curr_frame.get(key) {
63 return Line::new(layout.clone(), runs);
64 }
65
66 let mut curr_frame = RwLockUpgradableReadGuard::upgrade(curr_frame);
67 if let Some((key, layout)) = self.prev_frame.lock().remove_entry(key) {
68 curr_frame.insert(key, layout.clone());
69 Line::new(layout.clone(), runs)
70 } else {
71 let layout = Arc::new(self.fonts.layout_line(text, font_size, runs));
72 let key = CacheKeyValue {
73 text: text.into(),
74 font_size: OrderedFloat(font_size),
75 runs: SmallVec::from(runs),
76 };
77 curr_frame.insert(key, layout.clone());
78 Line::new(layout, runs)
79 }
80 }
81}
82
83trait CacheKey {
84 fn key<'a>(&'a self) -> CacheKeyRef<'a>;
85}
86
87impl<'a> PartialEq for (dyn CacheKey + 'a) {
88 fn eq(&self, other: &dyn CacheKey) -> bool {
89 self.key() == other.key()
90 }
91}
92
93impl<'a> Eq for (dyn CacheKey + 'a) {}
94
95impl<'a> Hash for (dyn CacheKey + 'a) {
96 fn hash<H: Hasher>(&self, state: &mut H) {
97 self.key().hash(state)
98 }
99}
100
101#[derive(Eq, PartialEq)]
102struct CacheKeyValue {
103 text: String,
104 font_size: OrderedFloat<f32>,
105 runs: SmallVec<[(usize, RunStyle); 1]>,
106}
107
108impl CacheKey for CacheKeyValue {
109 fn key<'a>(&'a self) -> CacheKeyRef<'a> {
110 CacheKeyRef {
111 text: &self.text.as_str(),
112 font_size: self.font_size,
113 runs: self.runs.as_slice(),
114 }
115 }
116}
117
118impl Hash for CacheKeyValue {
119 fn hash<H: Hasher>(&self, state: &mut H) {
120 self.key().hash(state);
121 }
122}
123
124impl<'a> Borrow<dyn CacheKey + 'a> for CacheKeyValue {
125 fn borrow(&self) -> &(dyn CacheKey + 'a) {
126 self as &dyn CacheKey
127 }
128}
129
130#[derive(Copy, Clone)]
131struct CacheKeyRef<'a> {
132 text: &'a str,
133 font_size: OrderedFloat<f32>,
134 runs: &'a [(usize, RunStyle)],
135}
136
137impl<'a> CacheKey for CacheKeyRef<'a> {
138 fn key<'b>(&'b self) -> CacheKeyRef<'b> {
139 *self
140 }
141}
142
143impl<'a> PartialEq for CacheKeyRef<'a> {
144 fn eq(&self, other: &Self) -> bool {
145 self.text == other.text
146 && self.font_size == other.font_size
147 && self.runs.len() == other.runs.len()
148 && self.runs.iter().zip(other.runs.iter()).all(
149 |((len_a, style_a), (len_b, style_b))| {
150 len_a == len_b && style_a.font_id == style_b.font_id
151 },
152 )
153 }
154}
155
156impl<'a> Hash for CacheKeyRef<'a> {
157 fn hash<H: Hasher>(&self, state: &mut H) {
158 self.text.hash(state);
159 self.font_size.hash(state);
160 for (len, style_id) in self.runs {
161 len.hash(state);
162 style_id.font_id.hash(state);
163 }
164 }
165}
166
167#[derive(Default, Debug)]
168pub struct Line {
169 layout: Arc<LineLayout>,
170 style_runs: SmallVec<[(u32, Color, Option<Underline>); 32]>,
171}
172
173#[derive(Default, Debug)]
174pub struct LineLayout {
175 pub width: f32,
176 pub ascent: f32,
177 pub descent: f32,
178 pub runs: Vec<Run>,
179 pub len: usize,
180 pub font_size: f32,
181}
182
183#[derive(Debug)]
184pub struct Run {
185 pub font_id: FontId,
186 pub glyphs: Vec<Glyph>,
187}
188
189#[derive(Clone, Debug)]
190pub struct Glyph {
191 pub id: GlyphId,
192 pub position: Vector2F,
193 pub index: usize,
194}
195
196impl Line {
197 fn new(layout: Arc<LineLayout>, runs: &[(usize, RunStyle)]) -> Self {
198 let mut style_runs = SmallVec::new();
199 for (len, style) in runs {
200 style_runs.push((*len as u32, style.color, style.underline));
201 }
202 Self { layout, style_runs }
203 }
204
205 pub fn runs(&self) -> &[Run] {
206 &self.layout.runs
207 }
208
209 pub fn width(&self) -> f32 {
210 self.layout.width
211 }
212
213 pub fn font_size(&self) -> f32 {
214 self.layout.font_size
215 }
216
217 pub fn x_for_index(&self, index: usize) -> f32 {
218 for run in &self.layout.runs {
219 for glyph in &run.glyphs {
220 if glyph.index >= index {
221 return glyph.position.x();
222 }
223 }
224 }
225 self.layout.width
226 }
227
228 pub fn font_for_index(&self, index: usize) -> Option<FontId> {
229 for run in &self.layout.runs {
230 for glyph in &run.glyphs {
231 if glyph.index >= index {
232 return Some(run.font_id);
233 }
234 }
235 }
236
237 None
238 }
239
240 pub fn index_for_x(&self, x: f32) -> Option<usize> {
241 if x >= self.layout.width {
242 None
243 } else {
244 for run in self.layout.runs.iter().rev() {
245 for glyph in run.glyphs.iter().rev() {
246 if glyph.position.x() <= x {
247 return Some(glyph.index);
248 }
249 }
250 }
251 Some(0)
252 }
253 }
254
255 pub fn paint(
256 &self,
257 origin: Vector2F,
258 visible_bounds: RectF,
259 line_height: f32,
260 cx: &mut PaintContext,
261 ) {
262 let padding_top = (line_height - self.layout.ascent - self.layout.descent) / 2.;
263 let baseline_offset = vec2f(0., padding_top + self.layout.ascent);
264
265 let mut style_runs = self.style_runs.iter();
266 let mut run_end = 0;
267 let mut color = Color::black();
268 let mut underline = None;
269
270 for run in &self.layout.runs {
271 let max_glyph_width = cx
272 .font_cache
273 .bounding_box(run.font_id, self.layout.font_size)
274 .x();
275
276 for glyph in &run.glyphs {
277 let glyph_origin = origin + baseline_offset + glyph.position;
278 if glyph_origin.x() > visible_bounds.upper_right().x() {
279 break;
280 }
281
282 let mut finished_underline = None;
283 if glyph.index >= run_end {
284 if let Some((run_len, run_color, run_underline)) = style_runs.next() {
285 if let Some((_, underline_style)) = underline {
286 if *run_underline != Some(underline_style) {
287 finished_underline = underline.take();
288 }
289 }
290 if let Some(run_underline) = run_underline {
291 underline.get_or_insert((
292 vec2f(
293 glyph_origin.x(),
294 origin.y() + baseline_offset.y() + 0.618 * self.layout.descent,
295 ),
296 *run_underline,
297 ));
298 }
299
300 run_end += *run_len as usize;
301 color = *run_color;
302 } else {
303 run_end = self.layout.len;
304 color = Color::black();
305 finished_underline = underline.take();
306 }
307 }
308
309 if glyph_origin.x() + max_glyph_width < visible_bounds.origin().x() {
310 continue;
311 }
312
313 if let Some((underline_origin, underline_style)) = finished_underline {
314 cx.scene.push_underline(scene::Underline {
315 origin: underline_origin,
316 width: glyph_origin.x() - underline_origin.x(),
317 thickness: underline_style.thickness.into(),
318 color: underline_style.color,
319 squiggly: underline_style.squiggly,
320 });
321 }
322
323 cx.scene.push_glyph(scene::Glyph {
324 font_id: run.font_id,
325 font_size: self.layout.font_size,
326 id: glyph.id,
327 origin: glyph_origin,
328 color,
329 });
330 }
331 }
332
333 if let Some((underline_start, underline_style)) = underline.take() {
334 let line_end_x = origin.x() + self.layout.width;
335 cx.scene.push_underline(scene::Underline {
336 origin: underline_start,
337 width: line_end_x - underline_start.x(),
338 color: underline_style.color,
339 thickness: underline_style.thickness.into(),
340 squiggly: underline_style.squiggly,
341 });
342 }
343 }
344
345 pub fn paint_wrapped(
346 &self,
347 origin: Vector2F,
348 visible_bounds: RectF,
349 line_height: f32,
350 boundaries: impl IntoIterator<Item = ShapedBoundary>,
351 cx: &mut PaintContext,
352 ) {
353 let padding_top = (line_height - self.layout.ascent - self.layout.descent) / 2.;
354 let baseline_origin = vec2f(0., padding_top + self.layout.ascent);
355
356 let mut boundaries = boundaries.into_iter().peekable();
357 let mut color_runs = self.style_runs.iter();
358 let mut color_end = 0;
359 let mut color = Color::black();
360
361 let mut glyph_origin = vec2f(0., 0.);
362 let mut prev_position = 0.;
363 for run in &self.layout.runs {
364 for (glyph_ix, glyph) in run.glyphs.iter().enumerate() {
365 if boundaries.peek().map_or(false, |b| b.glyph_ix == glyph_ix) {
366 boundaries.next();
367 glyph_origin = vec2f(0., glyph_origin.y() + line_height);
368 } else {
369 glyph_origin.set_x(glyph_origin.x() + glyph.position.x() - prev_position);
370 }
371 prev_position = glyph.position.x();
372
373 if glyph.index >= color_end {
374 if let Some(next_run) = color_runs.next() {
375 color_end += next_run.0 as usize;
376 color = next_run.1;
377 } else {
378 color_end = self.layout.len;
379 color = Color::black();
380 }
381 }
382
383 let glyph_bounds = RectF::new(
384 origin + glyph_origin,
385 cx.font_cache
386 .bounding_box(run.font_id, self.layout.font_size),
387 );
388 if glyph_bounds.intersects(visible_bounds) {
389 cx.scene.push_glyph(scene::Glyph {
390 font_id: run.font_id,
391 font_size: self.layout.font_size,
392 id: glyph.id,
393 origin: glyph_bounds.origin() + baseline_origin,
394 color,
395 });
396 }
397 }
398 }
399 }
400}
401
402impl Run {
403 pub fn glyphs(&self) -> &[Glyph] {
404 &self.glyphs
405 }
406}
407
408#[derive(Copy, Clone, Debug, PartialEq, Eq)]
409pub struct Boundary {
410 pub ix: usize,
411 pub next_indent: u32,
412}
413
414#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
415pub struct ShapedBoundary {
416 pub run_ix: usize,
417 pub glyph_ix: usize,
418}
419
420impl Boundary {
421 fn new(ix: usize, next_indent: u32) -> Self {
422 Self { ix, next_indent }
423 }
424}
425
426pub struct LineWrapper {
427 font_system: Arc<dyn FontSystem>,
428 pub(crate) font_id: FontId,
429 pub(crate) font_size: f32,
430 cached_ascii_char_widths: [f32; 128],
431 cached_other_char_widths: HashMap<char, f32>,
432}
433
434impl LineWrapper {
435 pub const MAX_INDENT: u32 = 256;
436
437 pub fn new(font_id: FontId, font_size: f32, font_system: Arc<dyn FontSystem>) -> Self {
438 Self {
439 font_system,
440 font_id,
441 font_size,
442 cached_ascii_char_widths: [f32::NAN; 128],
443 cached_other_char_widths: HashMap::new(),
444 }
445 }
446
447 pub fn wrap_line<'a>(
448 &'a mut self,
449 line: &'a str,
450 wrap_width: f32,
451 ) -> impl Iterator<Item = Boundary> + 'a {
452 let mut width = 0.0;
453 let mut first_non_whitespace_ix = None;
454 let mut indent = None;
455 let mut last_candidate_ix = 0;
456 let mut last_candidate_width = 0.0;
457 let mut last_wrap_ix = 0;
458 let mut prev_c = '\0';
459 let mut char_indices = line.char_indices();
460 iter::from_fn(move || {
461 while let Some((ix, c)) = char_indices.next() {
462 if c == '\n' {
463 continue;
464 }
465
466 if self.is_boundary(prev_c, c) && first_non_whitespace_ix.is_some() {
467 last_candidate_ix = ix;
468 last_candidate_width = width;
469 }
470
471 if c != ' ' && first_non_whitespace_ix.is_none() {
472 first_non_whitespace_ix = Some(ix);
473 }
474
475 let char_width = self.width_for_char(c);
476 width += char_width;
477 if width > wrap_width && ix > last_wrap_ix {
478 if let (None, Some(first_non_whitespace_ix)) = (indent, first_non_whitespace_ix)
479 {
480 indent = Some(
481 Self::MAX_INDENT.min((first_non_whitespace_ix - last_wrap_ix) as u32),
482 );
483 }
484
485 if last_candidate_ix > 0 {
486 last_wrap_ix = last_candidate_ix;
487 width -= last_candidate_width;
488 last_candidate_ix = 0;
489 } else {
490 last_wrap_ix = ix;
491 width = char_width;
492 }
493
494 let indent_width =
495 indent.map(|indent| indent as f32 * self.width_for_char(' '));
496 width += indent_width.unwrap_or(0.);
497
498 return Some(Boundary::new(last_wrap_ix, indent.unwrap_or(0)));
499 }
500 prev_c = c;
501 }
502
503 None
504 })
505 }
506
507 pub fn wrap_shaped_line<'a>(
508 &'a mut self,
509 str: &'a str,
510 line: &'a Line,
511 wrap_width: f32,
512 ) -> impl Iterator<Item = ShapedBoundary> + 'a {
513 let mut first_non_whitespace_ix = None;
514 let mut last_candidate_ix = None;
515 let mut last_candidate_x = 0.0;
516 let mut last_wrap_ix = ShapedBoundary {
517 run_ix: 0,
518 glyph_ix: 0,
519 };
520 let mut last_wrap_x = 0.;
521 let mut prev_c = '\0';
522 let mut glyphs = line
523 .runs()
524 .iter()
525 .enumerate()
526 .flat_map(move |(run_ix, run)| {
527 run.glyphs()
528 .iter()
529 .enumerate()
530 .map(move |(glyph_ix, glyph)| {
531 let character = str[glyph.index..].chars().next().unwrap();
532 (
533 ShapedBoundary { run_ix, glyph_ix },
534 character,
535 glyph.position.x(),
536 )
537 })
538 })
539 .peekable();
540
541 iter::from_fn(move || {
542 while let Some((ix, c, x)) = glyphs.next() {
543 if c == '\n' {
544 continue;
545 }
546
547 if self.is_boundary(prev_c, c) && first_non_whitespace_ix.is_some() {
548 last_candidate_ix = Some(ix);
549 last_candidate_x = x;
550 }
551
552 if c != ' ' && first_non_whitespace_ix.is_none() {
553 first_non_whitespace_ix = Some(ix);
554 }
555
556 let next_x = glyphs.peek().map_or(line.width(), |(_, _, x)| *x);
557 let width = next_x - last_wrap_x;
558 if width > wrap_width && ix > last_wrap_ix {
559 if let Some(last_candidate_ix) = last_candidate_ix.take() {
560 last_wrap_ix = last_candidate_ix;
561 last_wrap_x = last_candidate_x;
562 } else {
563 last_wrap_ix = ix;
564 last_wrap_x = x;
565 }
566
567 return Some(last_wrap_ix);
568 }
569 prev_c = c;
570 }
571
572 None
573 })
574 }
575
576 fn is_boundary(&self, prev: char, next: char) -> bool {
577 (prev == ' ') && (next != ' ')
578 }
579
580 #[inline(always)]
581 fn width_for_char(&mut self, c: char) -> f32 {
582 if (c as u32) < 128 {
583 let mut width = self.cached_ascii_char_widths[c as usize];
584 if width.is_nan() {
585 width = self.compute_width_for_char(c);
586 self.cached_ascii_char_widths[c as usize] = width;
587 }
588 width
589 } else {
590 let mut width = self
591 .cached_other_char_widths
592 .get(&c)
593 .copied()
594 .unwrap_or(f32::NAN);
595 if width.is_nan() {
596 width = self.compute_width_for_char(c);
597 self.cached_other_char_widths.insert(c, width);
598 }
599 width
600 }
601 }
602
603 fn compute_width_for_char(&self, c: char) -> f32 {
604 self.font_system
605 .layout_line(
606 &c.to_string(),
607 self.font_size,
608 &[(
609 1,
610 RunStyle {
611 font_id: self.font_id,
612 color: Default::default(),
613 underline: None,
614 },
615 )],
616 )
617 .width
618 }
619}
620
621#[cfg(test)]
622mod tests {
623 use super::*;
624 use crate::fonts::{Properties, Weight};
625
626 #[crate::test(self)]
627 fn test_wrap_line(cx: &mut crate::MutableAppContext) {
628 let font_cache = cx.font_cache().clone();
629 let font_system = cx.platform().fonts();
630 let family = font_cache.load_family(&["Courier"]).unwrap();
631 let font_id = font_cache.select_font(family, &Default::default()).unwrap();
632
633 let mut wrapper = LineWrapper::new(font_id, 16., font_system);
634 assert_eq!(
635 wrapper
636 .wrap_line("aa bbb cccc ddddd eeee", 72.0)
637 .collect::<Vec<_>>(),
638 &[
639 Boundary::new(7, 0),
640 Boundary::new(12, 0),
641 Boundary::new(18, 0)
642 ],
643 );
644 assert_eq!(
645 wrapper
646 .wrap_line("aaa aaaaaaaaaaaaaaaaaa", 72.0)
647 .collect::<Vec<_>>(),
648 &[
649 Boundary::new(4, 0),
650 Boundary::new(11, 0),
651 Boundary::new(18, 0)
652 ],
653 );
654 assert_eq!(
655 wrapper.wrap_line(" aaaaaaa", 72.).collect::<Vec<_>>(),
656 &[
657 Boundary::new(7, 5),
658 Boundary::new(9, 5),
659 Boundary::new(11, 5),
660 ]
661 );
662 assert_eq!(
663 wrapper
664 .wrap_line(" ", 72.)
665 .collect::<Vec<_>>(),
666 &[
667 Boundary::new(7, 0),
668 Boundary::new(14, 0),
669 Boundary::new(21, 0)
670 ]
671 );
672 assert_eq!(
673 wrapper
674 .wrap_line(" aaaaaaaaaaaaaa", 72.)
675 .collect::<Vec<_>>(),
676 &[
677 Boundary::new(7, 0),
678 Boundary::new(14, 3),
679 Boundary::new(18, 3),
680 Boundary::new(22, 3),
681 ]
682 );
683 }
684
685 #[crate::test(self, retries = 5)]
686 fn test_wrap_shaped_line(cx: &mut crate::MutableAppContext) {
687 // This is failing intermittently on CI and we don't have time to figure it out
688 let font_cache = cx.font_cache().clone();
689 let font_system = cx.platform().fonts();
690 let text_layout_cache = TextLayoutCache::new(font_system.clone());
691
692 let family = font_cache.load_family(&["Helvetica"]).unwrap();
693 let font_id = font_cache.select_font(family, &Default::default()).unwrap();
694 let normal = RunStyle {
695 font_id,
696 color: Default::default(),
697 underline: None,
698 };
699 let bold = RunStyle {
700 font_id: font_cache
701 .select_font(
702 family,
703 &Properties {
704 weight: Weight::BOLD,
705 ..Default::default()
706 },
707 )
708 .unwrap(),
709 color: Default::default(),
710 underline: None,
711 };
712
713 let text = "aa bbb cccc ddddd eeee";
714 let line = text_layout_cache.layout_str(
715 text,
716 16.0,
717 &[(4, normal), (5, bold), (6, normal), (1, bold), (7, normal)],
718 );
719
720 let mut wrapper = LineWrapper::new(font_id, 16., font_system);
721 assert_eq!(
722 wrapper
723 .wrap_shaped_line(&text, &line, 72.0)
724 .collect::<Vec<_>>(),
725 &[
726 ShapedBoundary {
727 run_ix: 1,
728 glyph_ix: 3
729 },
730 ShapedBoundary {
731 run_ix: 2,
732 glyph_ix: 3
733 },
734 ShapedBoundary {
735 run_ix: 4,
736 glyph_ix: 2
737 }
738 ],
739 );
740 }
741}