Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

epaint: Memoize individual lines during text layout #5411

Open
wants to merge 32 commits into
base: master
Choose a base branch
from
Open
Show file tree
Hide file tree
Changes from 17 commits
Commits
Show all changes
32 commits
Select commit Hold shift click to select a range
622b848
Fix typo
afishhh Nov 28, 2024
150c0f6
Cache individual lines of text in GalleyCache
afishhh Nov 28, 2024
db32a1e
Make Galleys share Rows and store their offsets
afishhh Nov 28, 2024
4e3f162
Fix lints
afishhh Nov 29, 2024
3de1723
Don't add leading space to more than one split layout section
afishhh Nov 29, 2024
f028154
Move cached-multiline-layout code into a helper function
afishhh Nov 29, 2024
bc86bec
Properly handle row repositioning
afishhh Nov 29, 2024
abbc561
Correctly handle empty lines
afishhh Nov 30, 2024
6d6bc3b
Respect first_row_min_height during multiline Galley layout
afishhh Nov 30, 2024
6147ff3
Round `PlacedRow` positions to pixels during multiline layout
afishhh Nov 30, 2024
66c83c3
Move `ends_with_newline` back into `Row`
afishhh Nov 30, 2024
1be24ba
Respect `LayoutJob::round_output_size_to_nearest_ui_point`
afishhh Nov 30, 2024
fd8413c
Simplify `layout_multiline` `loop` loop into a `while` loop
afishhh Nov 30, 2024
bbe5662
Fix `Row::ends_with_newline` docs, explain skipping of last galley row
afishhh Nov 30, 2024
110a9c3
Move some `PlacedRow` methods back to `Row`
afishhh Nov 30, 2024
139f286
Replace a hack with a proper implementation
afishhh Nov 30, 2024
e15b34b
Slightly simplify `paint_text_selection` code
afishhh Dec 1, 2024
c6592ec
Fix nits
afishhh Dec 4, 2024
25da822
Fix text horizontal alignment
afishhh Dec 5, 2024
40f237d
Add comment and check for newline before multiline layout
afishhh Dec 5, 2024
17a5f1f
Fix incorrect behavior with `LayoutJob::max_rows`
afishhh Dec 5, 2024
c094ee8
Merge branch 'emilk:master' into cache_galley_lines
afishhh Dec 7, 2024
3e1ed18
Add benchmark
afishhh Dec 11, 2024
ec9a408
Merge branch 'master' into cache_galley_lines
afishhh Dec 19, 2024
d2f75e9
Merge branch 'master' into cache_galley_lines
emilk Dec 28, 2024
2b53271
Better benchmark
emilk Jan 2, 2025
ba2ae9d
Merge branch 'master' into cache_galley_lines
emilk Jan 2, 2025
7fb85d1
Fix typos
emilk Jan 2, 2025
9fa294f
Split out long function
emilk Jan 2, 2025
77c9fd8
cleanup
emilk Jan 2, 2025
6b72d2f
Merge branch 'master' into cache_galley_lines
afishhh Jan 3, 2025
b36311a
Fix Glyph::pos doc comment
afishhh Jan 4, 2025
File filter

Filter by extension

Filter by extension

Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
6 changes: 3 additions & 3 deletions crates/egui/src/text_selection/accesskit_text.rs
Original file line number Diff line number Diff line change
Expand Up @@ -43,7 43,7 @@ pub fn update_accesskit_for_text_widget(
let row_id = parent_id.with(row_index);
ctx.accesskit_node_builder(row_id, |builder| {
builder.set_role(accesskit::Role::TextRun);
let rect = row.rect.translate(galley_pos.to_vec2());
let rect = row.rect().translate(galley_pos.to_vec2());
builder.set_bounds(accesskit::Rect {
x0: rect.min.x.into(),
y0: rect.min.y.into(),
Expand Down Expand Up @@ -74,14 74,14 @@ pub fn update_accesskit_for_text_widget(
let old_len = value.len();
value.push(glyph.chr);
character_lengths.push((value.len() - old_len) as _);
character_positions.push(glyph.pos.x - row.rect.min.x);
character_positions.push(glyph.pos.x - row.pos.x);
character_widths.push(glyph.advance_width);
}

if row.ends_with_newline {
value.push('\n');
character_lengths.push(1);
character_positions.push(row.rect.max.x - row.rect.min.x);
character_positions.push(row.size.x);
character_widths.push(0.0);
}
word_lengths.push((character_lengths.len() - last_word_start) as _);
Expand Down
9 changes: 6 additions & 3 deletions crates/egui/src/text_selection/label_text_selection.rs
Original file line number Diff line number Diff line change
Expand Up @@ -179,7 179,10 @@ impl LabelSelectionState {
if let epaint::Shape::Text(text_shape) = &mut shape.shape {
let galley = Arc::make_mut(&mut text_shape.galley);
for row_selection in row_selections {
if let Some(row) = galley.rows.get_mut(row_selection.row) {
if let Some(placed_row) =
galley.rows.get_mut(row_selection.row)
{
let row = Arc::make_mut(&mut placed_row.row);
for vertex_index in row_selection.vertex_indices {
if let Some(vertex) = row
.visuals
Expand Down Expand Up @@ -659,8 662,8 @@ fn selected_text(galley: &Galley, cursor_range: &CursorRange) -> String {
}

fn estimate_row_height(galley: &Galley) -> f32 {
if let Some(row) = galley.rows.first() {
row.rect.height()
if let Some(placed_row) = galley.rows.first() {
placed_row.height()
} else {
galley.size().y
}
Expand Down
9 changes: 5 additions & 4 deletions crates/egui/src/text_selection/visuals.rs
Original file line number Diff line number Diff line change
Expand Up @@ -31,11 31,12 @@ pub fn paint_text_selection(
let max = max.rcursor;

for ri in min.row..=max.row {
let row = &mut galley.rows[ri];
let row = Arc::make_mut(&mut galley.rows[ri].row);

let left = if ri == min.row {
row.x_offset(min.column)
} else {
row.rect.left()
0.0
};
let right = if ri == max.row {
row.x_offset(max.column)
Expand All @@ -45,10 46,10 @@ pub fn paint_text_selection(
} else {
0.0
};
row.rect.right() newline_size
row.size.x newline_size
};

let rect = Rect::from_min_max(pos2(left, row.min_y()), pos2(right, row.max_y()));
let rect = Rect::from_min_max(pos2(left, 0.0), pos2(right, row.size.y));
let mesh = &mut row.visuals.mesh;

// Time to insert the selection rectangle into the row mesh.
Expand Down
4 changes: 2 additions & 2 deletions crates/egui/src/widget_text.rs
Original file line number Diff line number Diff line change
Expand Up @@ -640,8 640,8 @@ impl WidgetText {
Self::RichText(text) => text.font_height(fonts, style),
Self::LayoutJob(job) => job.font_height(fonts),
Self::Galley(galley) => {
if let Some(row) = galley.rows.first() {
row.height()
if let Some(placed_row) = galley.rows.first() {
placed_row.height()
} else {
galley.size().y
}
Expand Down
10 changes: 5 additions & 5 deletions crates/egui/src/widgets/label.rs
Original file line number Diff line number Diff line change
@@ -1,8 1,8 @@
use std::sync::Arc;

use crate::{
epaint, pos2, text_selection, vec2, Align, Direction, FontSelection, Galley, Pos2, Response,
Sense, Stroke, TextWrapMode, Ui, Widget, WidgetInfo, WidgetText, WidgetType,
epaint, pos2, text_selection, Align, Direction, FontSelection, Galley, Pos2, Response, Sense,
Stroke, TextWrapMode, Ui, Widget, WidgetInfo, WidgetText, WidgetType,
};

use self::text_selection::LabelSelectionState;
Expand Down Expand Up @@ -194,10 194,10 @@ impl Label {
let pos = pos2(ui.max_rect().left(), ui.cursor().top());
assert!(!galley.rows.is_empty(), "Galleys are never empty");
// collect a response from many rows:
let rect = galley.rows[0].rect.translate(vec2(pos.x, pos.y));
let rect = galley.rows[0].rect().translate(pos.to_vec2());
let mut response = ui.allocate_rect(rect, sense);
for row in galley.rows.iter().skip(1) {
let rect = row.rect.translate(vec2(pos.x, pos.y));
for placed_row in galley.rows.iter().skip(1) {
let rect = placed_row.rect().translate(pos.to_vec2());
response |= ui.allocate_rect(rect, sense);
}
(pos, galley, response)
Expand Down
3 changes: 2 additions & 1 deletion crates/epaint/src/shape.rs
Original file line number Diff line number Diff line change
Expand Up @@ -433,7 433,8 @@ impl Shape {

// Scale text:
let galley = Arc::make_mut(&mut text_shape.galley);
for row in &mut galley.rows {
for placed_row in &mut galley.rows {
let row = Arc::make_mut(&mut placed_row.row);
row.visuals.mesh_bounds = transform.scaling * row.visuals.mesh_bounds;
for v in &mut row.visuals.mesh.vertices {
v.pos = Pos2::new(transform.scaling * v.pos.x, transform.scaling * v.pos.y);
Expand Down
3 changes: 2 additions & 1 deletion crates/epaint/src/shape_transform.rs
Original file line number Diff line number Diff line change
Expand Up @@ -88,7 88,8 @@ pub fn adjust_colors(

if !galley.is_empty() {
let galley = std::sync::Arc::make_mut(galley);
for row in &mut galley.rows {
for placed_row in &mut galley.rows {
let row = Arc::make_mut(&mut placed_row.row);
for vertex in &mut row.visuals.mesh.vertices {
adjust_color(&mut vertex.color);
}
Expand Down
2 changes: 1 addition & 1 deletion crates/epaint/src/stats.rs
Original file line number Diff line number Diff line change
Expand Up @@ -91,7 91,7 @@ impl AllocInfo {
galley.rows.iter().map(Self::from_galley_row).sum()
}

fn from_galley_row(row: &crate::text::Row) -> Self {
fn from_galley_row(row: &crate::text::PlacedRow) -> Self {
Self::from_mesh(&row.visuals.mesh) Self::from_slice(&row.glyphs)
}

Expand Down
6 changes: 4 additions & 2 deletions crates/epaint/src/tessellator.rs
Original file line number Diff line number Diff line change
Expand Up @@ -1783,11 1783,13 @@ impl Tessellator {
continue;
}

let final_pos = galley_pos row.pos.to_vec2();
afishhh marked this conversation as resolved.
Show resolved Hide resolved

let mut row_rect = row.visuals.mesh_bounds;
if *angle != 0.0 {
row_rect = row_rect.rotate_bb(rotator);
}
row_rect = row_rect.translate(galley_pos.to_vec2());
row_rect = row_rect.translate(final_pos.to_vec2());

if self.options.coarse_tessellation_culling && !self.clip_rect.intersects(row_rect) {
// culling individual lines of text is important, since a single `Shape::Text`
Expand Down Expand Up @@ -1836,7 1838,7 @@ impl Tessellator {
};

Vertex {
pos: galley_pos offset,
pos: final_pos offset,
uv: (uv.to_vec2() * uv_normalizer).to_pos2(),
color,
}
Expand Down
172 changes: 164 additions & 8 deletions crates/epaint/src/text/fonts.rs
Original file line number Diff line number Diff line change
Expand Up @@ -727,13 727,156 @@ struct GalleyCache {
}

impl GalleyCache {
fn layout_multiline(&mut self, fonts: &mut FontsImpl, job: LayoutJob) -> Galley {
afishhh marked this conversation as resolved.
Show resolved Hide resolved
let pixels_per_point = fonts.pixels_per_point;
let round_to_pixel =
move |point: f32| (point * pixels_per_point).round() / pixels_per_point;

let mut current_section = 0;
let mut current = 0;
let mut left_max_rows = job.wrap.max_rows;
let mut galleys = Vec::new();
let mut first_row_min_height = job.first_row_min_height;
while current != job.text.len() {
let end = job.text[current..]
.find('\n')
.map_or(job.text.len(), |i| i current 1);
let start = current;

let mut line_job = LayoutJob {
Comment on lines 803 to 809
Copy link
Owner

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This functions is very long.

I would love if we could break this up into parts, for instance:

let mut galleys = vec![];
for line_job in job.split_on_newlines() {
    …
}
Galley::concat(galleys)

Copy link
Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Should such LayoutJob::split_on_newlines and Galley::concat functions be public API or do we want to keep them private?

Copy link
Author

@afishhh afishhh Dec 5, 2024

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I looked into splitting out these functions but it's actually non trivial, for example the splitting actually has to do the layout while it is doing the splitting because it has to update LayoutJob::max_rows as more rows are being laid out. As for Galley::concat, it needs access to pixels_per_point for correct rounding so it'd be at the very least awkward as a public API (I guess you'd need to pass in Fonts?) and as a private one it could accept FontsImpl, it also needs access to the full LayoutJob so it can store it inside the Galley and also to check round_output_size_to_nearest_ui_point.

I think we could do something like a Galley::concat(fonts: &mut FontsImpl, job: LayoutJob, galleys: impl Iterator<Item = Galley>) -> Galley and keep splitting in GalleyCache::layout_multiline or split it out into a method of GalleyCache but it has to have access to GalleyCache so it can't be on LayoutJob. Also at that point I don't know whether scattering the implementation detail of FontsImpl into a Galley method is any more clean than keeping it in GalleyCache.

Maybe another solution would be to actually disable this line caching if LayoutJob::max_rows is finite, because in that scenario there's going to be more ways to invalidate the cached lines anyways and the performance benefits will be much more situational (any edit that will cause a line-count change will cause a re-layout of all subsequent lines). This could probably allow splitting out a LayoutJob::split_on_newlines method.

Copy link
Owner

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Splitting out the concatenation was pretty trivial:

9fa294f (#5560)

Copy link
Owner

@emilk emilk Jan 2, 2025

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I agree we can ignore max_rows for now (i.e. fall back to the old/slow path if it is set). Less bookkeeping of that and of elided

text: job.text[current..end].to_string(),
wrap: crate::text::TextWrapping {
max_rows: left_max_rows,
..job.wrap
},
sections: Vec::new(),
break_on_newline: true,
halign: job.halign,
justify: job.justify,
first_row_min_height,
round_output_size_to_nearest_ui_point: job.round_output_size_to_nearest_ui_point,
};
first_row_min_height = 0.0;

while current < end {
let mut s = &job.sections[current_section];
while s.byte_range.end <= current {
current_section = 1;
s = &job.sections[current_section];
}

assert!(s.byte_range.contains(&current));
let section_end = s.byte_range.end.min(end);
line_job.sections.push(crate::text::LayoutSection {
// Leading space should only be added to the first section
// if the there are multiple sections that will be created
// from splitting the current section.
leading_space: if current == s.byte_range.start {
s.leading_space
} else {
0.0
},
byte_range: current - start..section_end - start,
format: s.format.clone(),
});
current = section_end;
}

let galley = self.layout_component_line(fonts, line_job);
// This will prevent us from invalidating cache entries unnecessarily
if left_max_rows != usize::MAX {
left_max_rows -= galley.rows.len();
}
galleys.push(galley);

current = end;
}

let mut merged_galley = Galley {
job: Arc::new(job),
rows: Vec::new(),
elided: false,
rect: emath::Rect::ZERO,
mesh_bounds: emath::Rect::ZERO,
num_vertices: 0,
num_indices: 0,
pixels_per_point: fonts.pixels_per_point,
};

for (i, galley) in galleys.iter().enumerate() {
let current_offset = emath::vec2(0.0, merged_galley.rect.height());

let mut rows = galley.rows.iter();
// As documented in `Row::ends_with_newline`, a '\n' will always create a
// new `Row` immediately below the current one. Here it doesn't make sense
// for us to append this new row so we just ignore it.
if i != galleys.len() - 1 && !galley.elided {
let popped = rows.next_back();
debug_assert_eq!(popped.unwrap().row.glyphs.len(), 0);
}

merged_galley.rows.extend(rows.map(|placed_row| {
let mut new_pos = placed_row.pos current_offset;
new_pos.y = round_to_pixel(new_pos.y);
merged_galley.mesh_bounds = merged_galley
.mesh_bounds
.union(placed_row.visuals.mesh_bounds.translate(new_pos.to_vec2()));
merged_galley.rect = merged_galley
.rect
.union(emath::Rect::from_min_size(new_pos, placed_row.size));

super::PlacedRow {
row: placed_row.row.clone(),
pos: new_pos,
}
}));

merged_galley.num_vertices = galley.num_vertices;
merged_galley.num_indices = galley.num_indices;
if galley.elided {
merged_galley.elided = true;
break;
}
}

if merged_galley.job.round_output_size_to_nearest_ui_point {
super::round_output_size_to_nearest_ui_point(
&mut merged_galley.rect,
&merged_galley.job,
);
}

merged_galley
}

fn layout_component_line(&mut self, fonts: &mut FontsImpl, job: LayoutJob) -> Arc<Galley> {
let hash = crate::util::hash(&job);

match self.cache.entry(hash) {
std::collections::hash_map::Entry::Occupied(entry) => {
let cached = entry.into_mut();
cached.last_used = self.generation;
cached.galley.clone()
}
std::collections::hash_map::Entry::Vacant(entry) => {
let galley = super::layout(fonts, job.into());
let galley = Arc::new(galley);
entry.insert(CachedGalley {
last_used: self.generation,
galley: galley.clone(),
});
galley
}
}
}

fn layout(&mut self, fonts: &mut FontsImpl, mut job: LayoutJob) -> Arc<Galley> {
if job.wrap.max_width.is_finite() {
// Protect against rounding errors in egui layout code.

// Say the user asks to wrap at width 200.0.
// The text layout wraps, and reports that the final width was 196.0 points.
// This than trickles up the `Ui` chain and gets stored as the width for a tooltip (say).
// This then trickles up the `Ui` chain and gets stored as the width for a tooltip (say).
// On the next frame, this is then set as the max width for the tooltip,
// and we end up calling the text layout code again, this time with a wrap width of 196.0.
// Except, somewhere in the `Ui` chain with added margins etc, a rounding error was introduced,
Expand Down Expand Up @@ -762,13 905,26 @@ impl GalleyCache {
cached.galley.clone()
}
std::collections::hash_map::Entry::Vacant(entry) => {
let galley = super::layout(fonts, job.into());
let galley = Arc::new(galley);
entry.insert(CachedGalley {
last_used: self.generation,
galley: galley.clone(),
});
galley
if job.break_on_newline {
Copy link
Owner

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Maybe we should also only do this if the text is long enough and/or actually contains newline characters?

Copy link
Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I suppose we can check for a '\n', initially I was skeptical but the actual layout is way more expensive than this string find will cost us so it's probably fine.

Copy link
Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Added the newline part, I think adding a length check might not be worth it because it'd definitely make testing harder if an issue "only showed up if the text is longer than 1000 characters".

Copy link
Owner

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This deserves a comment

Copy link
Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I added a comment, let me know if you feel this is sufficient or if you had something else in mind.

let galley = self.layout_multiline(fonts, job);
let galley = Arc::new(galley);
self.cache.insert(
hash,
CachedGalley {
last_used: self.generation,
galley: galley.clone(),
},
);
galley
} else {
let galley = super::layout(fonts, job.into());
let galley = Arc::new(galley);
entry.insert(CachedGalley {
last_used: self.generation,
galley: galley.clone(),
});
galley
}
}
}
}
Expand Down
2 changes: 1 addition & 1 deletion crates/epaint/src/text/mod.rs
Original file line number Diff line number Diff line change
Expand Up @@ -14,7 14,7 @@ pub use {
FontData, FontDefinitions, FontFamily, FontId, FontInsert, FontPriority, FontTweak, Fonts,
FontsImpl, InsertFontFamily,
},
text_layout::layout,
text_layout::*,
text_layout_types::*,
};

Expand Down
Loading
Loading