egui/memory/
mod.rs

1#![warn(missing_docs)] // Let's keep this file well-documented.` to memory.rs
2
3use std::num::NonZeroUsize;
4
5use ahash::{HashMap, HashSet};
6use epaint::emath::TSTransform;
7
8use crate::{
9    EventFilter, Id, IdMap, LayerId, Order, Pos2, Rangef, RawInput, Rect, Style, Vec2, ViewportId,
10    ViewportIdMap, ViewportIdSet, area, vec2,
11};
12
13mod theme;
14pub use theme::{Theme, ThemePreference};
15
16// ----------------------------------------------------------------------------
17
18/// The data that egui persists between frames.
19///
20/// This includes window positions and sizes,
21/// how far the user has scrolled in a [`ScrollArea`](crate::ScrollArea) etc.
22///
23/// If you want this to persist when closing your app, you should serialize [`Memory`] and store it.
24/// For this you need to enable the `persistence`.
25///
26/// If you want to store data for your widgets, you should look at [`Memory::data`]
27#[derive(Clone, Debug)]
28#[cfg_attr(feature = "persistence", derive(serde::Deserialize, serde::Serialize))]
29#[cfg_attr(feature = "persistence", serde(default))]
30pub struct Memory {
31    /// Global egui options.
32    pub options: Options,
33
34    /// This map stores some superficial state for all widgets with custom [`Id`]s.
35    ///
36    /// This includes storing whether a [`crate::CollapsingHeader`] is open, how far scrolled a
37    /// [`crate::ScrollArea`] is, where the cursor in a [`crate::TextEdit`] is, etc.
38    ///
39    /// This is NOT meant to store any important data. Store that in your own structures!
40    ///
41    /// Each read clones the data, so keep your values cheap to clone.
42    /// If you want to store a lot of data, you should wrap it in `Arc<Mutex<…>>` so it is cheap to clone.
43    ///
44    /// This will be saved between different program runs if you use the `persistence` feature.
45    ///
46    /// To store a state common for all your widgets (a singleton), use [`Id::NULL`] as the key.
47    pub data: crate::util::IdTypeMap,
48
49    // ------------------------------------------
50    /// Can be used to cache computations from one frame to another.
51    ///
52    /// This is for saving CPU time when you have something that may take 1-100ms to compute.
53    /// Very slow operations (>100ms) should instead be done async (i.e. in another thread)
54    /// so as not to lock the UI thread.
55    ///
56    /// ```
57    /// use egui::cache::{ComputerMut, FrameCache};
58    ///
59    /// #[derive(Default)]
60    /// struct CharCounter {}
61    /// impl ComputerMut<&str, usize> for CharCounter {
62    ///     fn compute(&mut self, s: &str) -> usize {
63    ///         s.chars().count() // you probably want to cache something more expensive than this
64    ///     }
65    /// }
66    /// type CharCountCache<'a> = FrameCache<usize, CharCounter>;
67    ///
68    /// # let mut ctx = egui::Context::default();
69    /// ctx.memory_mut(|mem| {
70    ///     let cache = mem.caches.cache::<CharCountCache<'_>>();
71    ///     assert_eq!(cache.get("hello"), 5);
72    /// });
73    /// ```
74    #[cfg_attr(feature = "persistence", serde(skip))]
75    pub caches: crate::cache::CacheStorage,
76
77    // ------------------------------------------
78    /// new fonts that will be applied at the start of the next frame
79    #[cfg_attr(feature = "persistence", serde(skip))]
80    pub(crate) new_font_definitions: Option<epaint::text::FontDefinitions>,
81
82    /// add new font that will be applied at the start of the next frame
83    #[cfg_attr(feature = "persistence", serde(skip))]
84    pub(crate) add_fonts: Vec<epaint::text::FontInsert>,
85
86    // Current active viewport
87    #[cfg_attr(feature = "persistence", serde(skip))]
88    pub(crate) viewport_id: ViewportId,
89
90    #[cfg_attr(feature = "persistence", serde(skip))]
91    everything_is_visible: bool,
92
93    /// Transforms per layer.
94    ///
95    /// Instead of using this directly, use:
96    /// * [`crate::Context::set_transform_layer`]
97    /// * [`crate::Context::layer_transform_to_global`]
98    /// * [`crate::Context::layer_transform_from_global`]
99    pub to_global: HashMap<LayerId, TSTransform>,
100
101    // -------------------------------------------------
102    // Per-viewport:
103    areas: ViewportIdMap<Areas>,
104
105    #[cfg_attr(feature = "persistence", serde(skip))]
106    pub(crate) interactions: ViewportIdMap<InteractionState>,
107
108    #[cfg_attr(feature = "persistence", serde(skip))]
109    pub(crate) focus: ViewportIdMap<Focus>,
110
111    /// Which popup-window is open on a viewport (if any)?
112    /// Could be a combo box, color picker, menu, etc.
113    /// Optionally stores the position of the popup (usually this would be the position where
114    /// the user clicked).
115    /// If position is [`None`], the popup position will be calculated based on some configuration
116    /// (e.g. relative to some other widget).
117    #[cfg_attr(feature = "persistence", serde(skip))]
118    popups: ViewportIdMap<OpenPopup>,
119}
120
121impl Default for Memory {
122    fn default() -> Self {
123        let mut slf = Self {
124            options: Default::default(),
125            data: Default::default(),
126            caches: Default::default(),
127            new_font_definitions: Default::default(),
128            interactions: Default::default(),
129            focus: Default::default(),
130            viewport_id: Default::default(),
131            areas: Default::default(),
132            to_global: Default::default(),
133            popups: Default::default(),
134            everything_is_visible: Default::default(),
135            add_fonts: Default::default(),
136        };
137        slf.interactions.entry(slf.viewport_id).or_default();
138        slf.areas.entry(slf.viewport_id).or_default();
139        slf
140    }
141}
142
143#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
144enum FocusDirection {
145    /// Select the widget closest above the current focused widget.
146    Up,
147
148    /// Select the widget to the right of the current focused widget.
149    Right,
150
151    /// Select the widget below the current focused widget.
152    Down,
153
154    /// Select the widget to the left of the current focused widget.
155    Left,
156
157    /// Select the previous widget that had focus.
158    Previous,
159
160    /// Select the next widget that wants focus.
161    Next,
162
163    /// Don't change focus.
164    #[default]
165    None,
166}
167
168impl FocusDirection {
169    fn is_cardinal(&self) -> bool {
170        match self {
171            Self::Up | Self::Right | Self::Down | Self::Left => true,
172
173            Self::Previous | Self::Next | Self::None => false,
174        }
175    }
176}
177
178// ----------------------------------------------------------------------------
179
180/// Some global options that you can read and write.
181///
182/// See also [`crate::style::DebugOptions`].
183#[derive(Clone, Debug, PartialEq)]
184#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
185#[cfg_attr(feature = "serde", serde(default))]
186pub struct Options {
187    /// The default style for new [`Ui`](crate::Ui):s in dark mode.
188    #[cfg_attr(feature = "serde", serde(skip))]
189    pub dark_style: std::sync::Arc<Style>,
190
191    /// The default style for new [`Ui`](crate::Ui):s in light mode.
192    #[cfg_attr(feature = "serde", serde(skip))]
193    pub light_style: std::sync::Arc<Style>,
194
195    /// Preference for selection between dark and light [`crate::Context::style`]
196    /// as the active style used by all subsequent windows, panels, etc.
197    ///
198    /// Default: `ThemePreference::System`.
199    pub theme_preference: ThemePreference,
200
201    /// Which theme to use in case [`Self::theme_preference`] is [`ThemePreference::System`]
202    /// and egui fails to detect the system theme.
203    ///
204    /// Default: [`crate::Theme::Dark`].
205    pub fallback_theme: Theme,
206
207    /// The current system theme, used to choose between
208    /// dark and light style in case [`Self::theme_preference`] is [`ThemePreference::System`].
209    #[cfg_attr(feature = "serde", serde(skip))]
210    pub(crate) system_theme: Option<Theme>,
211
212    /// Global zoom factor of the UI.
213    ///
214    /// This is used to calculate the `pixels_per_point`
215    /// for the UI as `pixels_per_point = zoom_fator * native_pixels_per_point`.
216    ///
217    /// The default is 1.0. Increase it to make all UI elements larger.
218    ///
219    /// You should call [`crate::Context::set_zoom_factor`]
220    /// instead of modifying this directly!
221    pub zoom_factor: f32,
222
223    /// If `true`, egui will change the scale of the ui ([`crate::Context::zoom_factor`]) when the user
224    /// presses Cmd+Plus, Cmd+Minus or Cmd+0, just like in a browser.
225    ///
226    /// This is `true` by default.
227    ///
228    /// On the web-backend of `eframe` this is set to false by default,
229    /// so that the zoom shortcuts are handled exclusively by the browser,
230    /// which will change the `native_pixels_per_point` (`devicePixelRatio`).
231    /// You can still zoom egui independently by calling [`crate::Context::set_zoom_factor`],
232    /// which will be applied on top of the browsers global zoom.
233    #[cfg_attr(feature = "serde", serde(skip))]
234    pub zoom_with_keyboard: bool,
235
236    /// Controls the tessellator.
237    pub tessellation_options: epaint::TessellationOptions,
238
239    /// If any widget moves or changes id, repaint everything.
240    ///
241    /// It is recommended you keep this OFF, as it may
242    /// lead to endless repaints for an unknown reason. See
243    /// (<https://github.com/rerun-io/rerun/issues/5018>).
244    pub repaint_on_widget_change: bool,
245
246    /// Maximum number of passes to run in one frame.
247    ///
248    /// Set to `1` for pure single-pass immediate mode.
249    /// Set to something larger than `1` to allow multi-pass when needed.
250    ///
251    /// Default is `2`. This means sometimes a frame will cost twice as much,
252    /// but usually only rarely (e.g. when showing a new panel for the first time).
253    ///
254    /// egui will usually only ever run one pass, even if `max_passes` is large.
255    ///
256    /// If this is `1`, [`crate::Context::request_discard`] will be ignored.
257    ///
258    /// Multi-pass is supported by [`crate::Context::run`].
259    ///
260    /// See [`crate::Context::request_discard`] for more.
261    pub max_passes: NonZeroUsize,
262
263    /// This is a signal to any backend that we want the [`crate::PlatformOutput::events`] read out loud.
264    ///
265    /// The only change to egui is that labels can be focused by pressing tab.
266    ///
267    /// Screen readers are an experimental feature of egui, and not supported on all platforms.
268    /// `eframe` only supports it on web.
269    ///
270    /// Consider using [AccessKit](https://github.com/AccessKit/accesskit) instead,
271    /// which is supported by `eframe`.
272    pub screen_reader: bool,
273
274    /// If true, the most common glyphs (ASCII) are pre-rendered to the texture atlas.
275    ///
276    /// Only the fonts in [`Style::text_styles`] will be pre-cached.
277    ///
278    /// This can lead to fewer texture operations, but may use up the texture atlas quicker
279    /// if you are changing [`Style::text_styles`], or have a lot of text styles.
280    pub preload_font_glyphs: bool,
281
282    /// Check reusing of [`Id`]s, and show a visual warning on screen when one is found.
283    ///
284    /// By default this is `true` in debug builds.
285    pub warn_on_id_clash: bool,
286
287    /// Options related to input state handling.
288    pub input_options: crate::input_state::InputOptions,
289
290    /// If `true`, `egui` will discard the loaded image data after
291    /// the texture is loaded onto the GPU to reduce memory usage.
292    ///
293    /// In modern GPU rendering, the texture data is not required after the texture is loaded.
294    ///
295    /// This is beneficial when using a large number or resolution of images and there is no need to
296    /// retain the image data, potentially saving a significant amount of memory.
297    ///
298    /// The drawback is that it becomes impossible to serialize the loaded images or render in non-GPU systems.
299    ///
300    /// Default is `false`.
301    pub reduce_texture_memory: bool,
302}
303
304impl Default for Options {
305    fn default() -> Self {
306        Self {
307            dark_style: std::sync::Arc::new(Theme::Dark.default_style()),
308            light_style: std::sync::Arc::new(Theme::Light.default_style()),
309            theme_preference: Default::default(),
310            fallback_theme: Theme::Dark,
311            system_theme: None,
312            zoom_factor: 1.0,
313            zoom_with_keyboard: true,
314            tessellation_options: Default::default(),
315            repaint_on_widget_change: false,
316            max_passes: NonZeroUsize::new(2).unwrap(),
317            screen_reader: false,
318            preload_font_glyphs: true,
319            warn_on_id_clash: cfg!(debug_assertions),
320
321            // Input:
322            input_options: Default::default(),
323            reduce_texture_memory: false,
324        }
325    }
326}
327
328impl Options {
329    pub(crate) fn begin_pass(&mut self, new_raw_input: &RawInput) {
330        self.system_theme = new_raw_input.system_theme;
331    }
332
333    /// The currently active theme (may depend on the system theme).
334    pub(crate) fn theme(&self) -> Theme {
335        match self.theme_preference {
336            ThemePreference::Dark => Theme::Dark,
337            ThemePreference::Light => Theme::Light,
338            ThemePreference::System => self.system_theme.unwrap_or(self.fallback_theme),
339        }
340    }
341
342    pub(crate) fn style(&self) -> &std::sync::Arc<Style> {
343        match self.theme() {
344            Theme::Dark => &self.dark_style,
345            Theme::Light => &self.light_style,
346        }
347    }
348
349    pub(crate) fn style_mut(&mut self) -> &mut std::sync::Arc<Style> {
350        match self.theme() {
351            Theme::Dark => &mut self.dark_style,
352            Theme::Light => &mut self.light_style,
353        }
354    }
355}
356
357impl Options {
358    /// Show the options in the ui.
359    pub fn ui(&mut self, ui: &mut crate::Ui) {
360        let theme = self.theme();
361
362        let Self {
363            dark_style, // covered above
364            light_style,
365            theme_preference,
366            fallback_theme: _,
367            system_theme: _,
368            zoom_factor: _, // TODO(emilk)
369            zoom_with_keyboard,
370            tessellation_options,
371            repaint_on_widget_change,
372            max_passes,
373            screen_reader: _, // needs to come from the integration
374            preload_font_glyphs: _,
375            warn_on_id_clash,
376            input_options,
377            reduce_texture_memory,
378        } = self;
379
380        use crate::Widget as _;
381        use crate::containers::CollapsingHeader;
382
383        CollapsingHeader::new("⚙ Options")
384            .default_open(false)
385            .show(ui, |ui| {
386                ui.horizontal(|ui| {
387                    ui.label("Max passes:");
388                    ui.add(crate::DragValue::new(max_passes).range(0..=10));
389                });
390
391                ui.checkbox(
392                    repaint_on_widget_change,
393                    "Repaint if any widget moves or changes id",
394                );
395
396                ui.checkbox(
397                    zoom_with_keyboard,
398                    "Zoom with keyboard (Cmd +, Cmd -, Cmd 0)",
399                );
400
401                ui.checkbox(warn_on_id_clash, "Warn if two widgets have the same Id");
402
403                ui.checkbox(reduce_texture_memory, "Reduce texture memory");
404            });
405
406        CollapsingHeader::new("🎑 Style")
407            .default_open(true)
408            .show(ui, |ui| {
409                theme_preference.radio_buttons(ui);
410
411                let style = std::sync::Arc::make_mut(match theme {
412                    Theme::Dark => dark_style,
413                    Theme::Light => light_style,
414                });
415                style.ui(ui);
416            });
417
418        CollapsingHeader::new("✒ Painting")
419            .default_open(false)
420            .show(ui, |ui| {
421                tessellation_options.ui(ui);
422                ui.vertical_centered(|ui| {
423                    crate::reset_button(ui, tessellation_options, "Reset paint settings");
424                });
425            });
426
427        CollapsingHeader::new("🖱 Input")
428            .default_open(false)
429            .show(ui, |ui| {
430                input_options.ui(ui);
431            });
432
433        ui.vertical_centered(|ui| crate::reset_button(ui, self, "Reset all"));
434    }
435}
436
437// ----------------------------------------------------------------------------
438
439/// The state of the interaction in egui,
440/// i.e. what is being dragged.
441///
442/// Say there is a button in a scroll area.
443/// If the user clicks the button, the button should click.
444/// If the user drags the button we should scroll the scroll area.
445/// Therefore, when the mouse is pressed, we register both the button
446/// and the scroll area (as `click_id`/`drag_id`).
447/// If the user releases the button without moving the mouse, we register it as a click on `click_id`.
448/// If the cursor moves too much, we clear the `click_id` and start passing move events to `drag_id`.
449#[derive(Clone, Debug, Default)]
450pub(crate) struct InteractionState {
451    /// A widget interested in clicks that has a mouse press on it.
452    pub potential_click_id: Option<Id>,
453
454    /// A widget interested in drags that has a mouse press on it.
455    ///
456    /// Note that this is set as soon as the mouse is pressed,
457    /// so the widget may not yet be marked as "dragged"
458    /// as that can only happen after the mouse has moved a bit
459    /// (at least if the widget is interesated in both clicks and drags).
460    pub potential_drag_id: Option<Id>,
461}
462
463/// Keeps tracks of what widget has keyboard focus
464#[derive(Clone, Debug, Default)]
465pub(crate) struct Focus {
466    /// The widget with keyboard focus (i.e. a text input field).
467    focused_widget: Option<FocusWidget>,
468
469    /// The ID of a widget that had keyboard focus during the previous frame.
470    id_previous_frame: Option<Id>,
471
472    /// The ID of a widget to give the focus to in the next frame.
473    id_next_frame: Option<Id>,
474
475    #[cfg(feature = "accesskit")]
476    id_requested_by_accesskit: Option<accesskit::NodeId>,
477
478    /// If set, the next widget that is interested in focus will automatically get it.
479    /// Probably because the user pressed Tab.
480    give_to_next: bool,
481
482    /// The last widget interested in focus.
483    last_interested: Option<Id>,
484
485    /// Set when looking for widget with navigational keys like arrows, tab, shift+tab.
486    focus_direction: FocusDirection,
487
488    /// The top-most modal layer from the previous frame.
489    top_modal_layer: Option<LayerId>,
490
491    /// The top-most modal layer from the current frame.
492    top_modal_layer_current_frame: Option<LayerId>,
493
494    /// A cache of widget IDs that are interested in focus with their corresponding rectangles.
495    focus_widgets_cache: IdMap<Rect>,
496}
497
498/// The widget with focus.
499#[derive(Clone, Copy, Debug)]
500struct FocusWidget {
501    pub id: Id,
502    pub filter: EventFilter,
503}
504
505impl FocusWidget {
506    pub fn new(id: Id) -> Self {
507        Self {
508            id,
509            filter: Default::default(),
510        }
511    }
512}
513
514impl InteractionState {
515    /// Are we currently clicking or dragging an egui widget?
516    pub fn is_using_pointer(&self) -> bool {
517        self.potential_click_id.is_some() || self.potential_drag_id.is_some()
518    }
519}
520
521impl Focus {
522    /// Which widget currently has keyboard focus?
523    pub fn focused(&self) -> Option<Id> {
524        self.focused_widget.as_ref().map(|w| w.id)
525    }
526
527    fn begin_pass(&mut self, new_input: &crate::data::input::RawInput) {
528        self.id_previous_frame = self.focused();
529        if let Some(id) = self.id_next_frame.take() {
530            self.focused_widget = Some(FocusWidget::new(id));
531        }
532        let event_filter = self.focused_widget.map(|w| w.filter).unwrap_or_default();
533
534        #[cfg(feature = "accesskit")]
535        {
536            self.id_requested_by_accesskit = None;
537        }
538
539        self.focus_direction = FocusDirection::None;
540
541        for event in &new_input.events {
542            if !event_filter.matches(event) {
543                if let crate::Event::Key {
544                    key,
545                    pressed: true,
546                    modifiers,
547                    ..
548                } = event
549                {
550                    if let Some(cardinality) = match key {
551                        crate::Key::ArrowUp => Some(FocusDirection::Up),
552                        crate::Key::ArrowRight => Some(FocusDirection::Right),
553                        crate::Key::ArrowDown => Some(FocusDirection::Down),
554                        crate::Key::ArrowLeft => Some(FocusDirection::Left),
555
556                        crate::Key::Tab => {
557                            if modifiers.shift {
558                                Some(FocusDirection::Previous)
559                            } else {
560                                Some(FocusDirection::Next)
561                            }
562                        }
563                        crate::Key::Escape => {
564                            self.focused_widget = None;
565                            Some(FocusDirection::None)
566                        }
567                        _ => None,
568                    } {
569                        self.focus_direction = cardinality;
570                    }
571                }
572            }
573
574            #[cfg(feature = "accesskit")]
575            {
576                if let crate::Event::AccessKitActionRequest(accesskit::ActionRequest {
577                    action: accesskit::Action::Focus,
578                    target,
579                    data: None,
580                }) = event
581                {
582                    self.id_requested_by_accesskit = Some(*target);
583                }
584            }
585        }
586    }
587
588    pub(crate) fn end_pass(&mut self, used_ids: &IdMap<Rect>) {
589        if self.focus_direction.is_cardinal() {
590            if let Some(found_widget) = self.find_widget_in_direction(used_ids) {
591                self.focused_widget = Some(FocusWidget::new(found_widget));
592            }
593        }
594
595        if let Some(focused_widget) = self.focused_widget {
596            // Allow calling `request_focus` one frame and not using it until next frame
597            let recently_gained_focus = self.id_previous_frame != Some(focused_widget.id);
598
599            if !recently_gained_focus && !used_ids.contains_key(&focused_widget.id) {
600                // Dead-mans-switch: the widget with focus has disappeared!
601                self.focused_widget = None;
602            }
603        }
604
605        self.top_modal_layer = self.top_modal_layer_current_frame.take();
606    }
607
608    pub(crate) fn had_focus_last_frame(&self, id: Id) -> bool {
609        self.id_previous_frame == Some(id)
610    }
611
612    fn interested_in_focus(&mut self, id: Id) {
613        #[cfg(feature = "accesskit")]
614        {
615            if self.id_requested_by_accesskit == Some(id.accesskit_id()) {
616                self.focused_widget = Some(FocusWidget::new(id));
617                self.id_requested_by_accesskit = None;
618                self.give_to_next = false;
619                self.reset_focus();
620            }
621        }
622
623        // The rect is updated at the end of the frame.
624        self.focus_widgets_cache
625            .entry(id)
626            .or_insert(Rect::EVERYTHING);
627
628        if self.give_to_next && !self.had_focus_last_frame(id) {
629            self.focused_widget = Some(FocusWidget::new(id));
630            self.give_to_next = false;
631        } else if self.focused() == Some(id) {
632            if self.focus_direction == FocusDirection::Next {
633                self.focused_widget = None;
634                self.give_to_next = true;
635                self.reset_focus();
636            } else if self.focus_direction == FocusDirection::Previous {
637                self.id_next_frame = self.last_interested; // frame-delay so gained_focus works
638                self.reset_focus();
639            }
640        } else if self.focus_direction == FocusDirection::Next
641            && self.focused_widget.is_none()
642            && !self.give_to_next
643        {
644            // nothing has focus and the user pressed tab - give focus to the first widgets that wants it:
645            self.focused_widget = Some(FocusWidget::new(id));
646            self.reset_focus();
647        } else if self.focus_direction == FocusDirection::Previous
648            && self.focused_widget.is_none()
649            && !self.give_to_next
650        {
651            // nothing has focus and the user pressed Shift+Tab - give focus to the last widgets that wants it:
652            self.focused_widget = self.last_interested.map(FocusWidget::new);
653            self.reset_focus();
654        }
655
656        self.last_interested = Some(id);
657    }
658
659    fn set_modal_layer(&mut self, layer_id: LayerId) {
660        self.top_modal_layer_current_frame = Some(layer_id);
661    }
662
663    pub(crate) fn top_modal_layer(&self) -> Option<LayerId> {
664        self.top_modal_layer
665    }
666
667    fn reset_focus(&mut self) {
668        self.focus_direction = FocusDirection::None;
669    }
670
671    fn find_widget_in_direction(&mut self, new_rects: &IdMap<Rect>) -> Option<Id> {
672        // NOTE: `new_rects` here include some widgets _not_ interested in focus.
673
674        /// * negative if `a` is left of `b`
675        /// * positive if `a` is right of `b`
676        /// * zero if the ranges overlap significantly
677        fn range_diff(a: Rangef, b: Rangef) -> f32 {
678            let has_significant_overlap = a.intersection(b).span() >= 0.5 * b.span().min(a.span());
679            if has_significant_overlap {
680                0.0
681            } else {
682                a.center() - b.center()
683            }
684        }
685
686        let current_focused = self.focused_widget?;
687
688        // In what direction we are looking for the next widget.
689        let search_direction = match self.focus_direction {
690            FocusDirection::Up => Vec2::UP,
691            FocusDirection::Right => Vec2::RIGHT,
692            FocusDirection::Down => Vec2::DOWN,
693            FocusDirection::Left => Vec2::LEFT,
694            _ => {
695                return None;
696            }
697        };
698
699        // Update cache with new rects
700        self.focus_widgets_cache.retain(|id, old_rect| {
701            if let Some(new_rect) = new_rects.get(id) {
702                *old_rect = *new_rect;
703                true // Keep the item
704            } else {
705                false // Remove the item
706            }
707        });
708
709        let current_rect = self.focus_widgets_cache.get(&current_focused.id)?;
710
711        let mut best_score = f32::INFINITY;
712        let mut best_id = None;
713
714        for (candidate_id, candidate_rect) in &self.focus_widgets_cache {
715            if *candidate_id == current_focused.id {
716                continue;
717            }
718
719            // There is a lot of room for improvement here.
720            let to_candidate = vec2(
721                range_diff(candidate_rect.x_range(), current_rect.x_range()),
722                range_diff(candidate_rect.y_range(), current_rect.y_range()),
723            );
724
725            let acos_angle = to_candidate.normalized().dot(search_direction);
726
727            // Only interested in widgets that fall in a 90° cone (±45°)
728            // of the search direction.
729            let is_in_search_cone = 0.5_f32.sqrt() <= acos_angle;
730            if is_in_search_cone {
731                let distance = to_candidate.length();
732
733                // There is a lot of room for improvement here.
734                let score = distance / (acos_angle * acos_angle);
735
736                if score < best_score {
737                    best_score = score;
738                    best_id = Some(*candidate_id);
739                }
740            }
741        }
742
743        best_id
744    }
745}
746
747impl Memory {
748    pub(crate) fn begin_pass(&mut self, new_raw_input: &RawInput, viewports: &ViewportIdSet) {
749        profiling::function_scope!();
750
751        self.viewport_id = new_raw_input.viewport_id;
752
753        // Cleanup
754        self.interactions.retain(|id, _| viewports.contains(id));
755        self.areas.retain(|id, _| viewports.contains(id));
756        self.popups.retain(|id, _| viewports.contains(id));
757
758        self.areas.entry(self.viewport_id).or_default();
759
760        // self.interactions  is handled elsewhere
761
762        self.options.begin_pass(new_raw_input);
763
764        self.focus
765            .entry(self.viewport_id)
766            .or_default()
767            .begin_pass(new_raw_input);
768    }
769
770    pub(crate) fn end_pass(&mut self, used_ids: &IdMap<Rect>) {
771        self.caches.update();
772        self.areas_mut().end_pass();
773        self.focus_mut().end_pass(used_ids);
774
775        // Clean up abandoned popups.
776        if let Some(popup) = self.popups.get_mut(&self.viewport_id) {
777            if popup.open_this_frame {
778                popup.open_this_frame = false;
779            } else {
780                self.popups.remove(&self.viewport_id);
781            }
782        }
783    }
784
785    pub(crate) fn set_viewport_id(&mut self, viewport_id: ViewportId) {
786        self.viewport_id = viewport_id;
787    }
788
789    /// Access memory of the [`Area`](crate::containers::area::Area)s, such as `Window`s.
790    pub fn areas(&self) -> &Areas {
791        self.areas
792            .get(&self.viewport_id)
793            .expect("Memory broken: no area for the current viewport")
794    }
795
796    /// Access memory of the [`Area`](crate::containers::area::Area)s, such as `Window`s.
797    pub fn areas_mut(&mut self) -> &mut Areas {
798        self.areas.entry(self.viewport_id).or_default()
799    }
800
801    /// Top-most layer at the given position.
802    pub fn layer_id_at(&self, pos: Pos2) -> Option<LayerId> {
803        self.areas()
804            .layer_id_at(pos, &self.to_global)
805            .and_then(|layer_id| {
806                if self.is_above_modal_layer(layer_id) {
807                    Some(layer_id)
808                } else {
809                    self.top_modal_layer()
810                }
811            })
812    }
813
814    /// The currently set transform of a layer.
815    #[deprecated = "Use `Context::layer_transform_to_global` instead"]
816    pub fn layer_transforms(&self, layer_id: LayerId) -> Option<TSTransform> {
817        self.to_global.get(&layer_id).copied()
818    }
819
820    /// An iterator over all layers. Back-to-front, top is last.
821    pub fn layer_ids(&self) -> impl ExactSizeIterator<Item = LayerId> + '_ {
822        self.areas().order().iter().copied()
823    }
824
825    /// Check if the layer had focus last frame.
826    /// returns `true` if the layer had focus last frame, but not this one.
827    pub fn had_focus_last_frame(&self, id: Id) -> bool {
828        self.focus().and_then(|f| f.id_previous_frame) == Some(id)
829    }
830
831    /// Check if the layer lost focus last frame.
832    /// returns `true` if the layer lost focus last frame, but not this one.
833    pub(crate) fn lost_focus(&self, id: Id) -> bool {
834        self.had_focus_last_frame(id) && !self.has_focus(id)
835    }
836
837    /// Check if the layer gained focus this frame.
838    /// returns `true` if the layer gained focus this frame, but not last one.
839    pub(crate) fn gained_focus(&self, id: Id) -> bool {
840        !self.had_focus_last_frame(id) && self.has_focus(id)
841    }
842
843    /// Does this widget have keyboard focus?
844    ///
845    /// This function does not consider whether the UI as a whole (e.g. window)
846    /// has the keyboard focus. That makes this function suitable for deciding
847    /// widget state that should not be disrupted if the user moves away from
848    /// the window and back.
849    #[inline(always)]
850    pub fn has_focus(&self, id: Id) -> bool {
851        self.focused() == Some(id)
852    }
853
854    /// Which widget has keyboard focus?
855    pub fn focused(&self) -> Option<Id> {
856        self.focus().and_then(|f| f.focused())
857    }
858
859    /// Set an event filter for a widget.
860    ///
861    /// This allows you to control whether the widget will loose focus
862    /// when the user presses tab, arrow keys, or escape.
863    ///
864    /// You must first give focus to the widget before calling this.
865    pub fn set_focus_lock_filter(&mut self, id: Id, event_filter: EventFilter) {
866        if self.had_focus_last_frame(id) && self.has_focus(id) {
867            if let Some(focused) = &mut self.focus_mut().focused_widget {
868                if focused.id == id {
869                    focused.filter = event_filter;
870                }
871            }
872        }
873    }
874
875    /// Give keyboard focus to a specific widget.
876    /// See also [`crate::Response::request_focus`].
877    #[inline(always)]
878    pub fn request_focus(&mut self, id: Id) {
879        self.focus_mut().focused_widget = Some(FocusWidget::new(id));
880    }
881
882    /// Surrender keyboard focus for a specific widget.
883    /// See also [`crate::Response::surrender_focus`].
884    #[inline(always)]
885    pub fn surrender_focus(&mut self, id: Id) {
886        let focus = self.focus_mut();
887        if focus.focused() == Some(id) {
888            focus.focused_widget = None;
889        }
890    }
891
892    /// Returns true if
893    /// - this layer is the top-most modal layer or above it
894    /// - there is no modal layer
895    pub fn is_above_modal_layer(&self, layer_id: LayerId) -> bool {
896        if let Some(modal_layer) = self.focus().and_then(|f| f.top_modal_layer) {
897            matches!(
898                self.areas().compare_order(layer_id, modal_layer),
899                std::cmp::Ordering::Equal | std::cmp::Ordering::Greater
900            )
901        } else {
902            true
903        }
904    }
905
906    /// Does this layer allow interaction?
907    /// Returns true if
908    ///  - the layer is not behind a modal layer
909    ///  - the [`Order`] allows interaction
910    pub fn allows_interaction(&self, layer_id: LayerId) -> bool {
911        let is_above_modal_layer = self.is_above_modal_layer(layer_id);
912        let ordering_allows_interaction = layer_id.order.allow_interaction();
913        is_above_modal_layer && ordering_allows_interaction
914    }
915
916    /// Register this widget as being interested in getting keyboard focus.
917    /// This will allow the user to select it with tab and shift-tab.
918    /// This is normally done automatically when handling interactions,
919    /// but it is sometimes useful to pre-register interest in focus,
920    /// e.g. before deciding which type of underlying widget to use,
921    /// as in the [`crate::DragValue`] widget, so a widget can be focused
922    /// and rendered correctly in a single frame.
923    ///
924    /// Pass in the `layer_id` of the layer that the widget is in.
925    #[inline(always)]
926    pub fn interested_in_focus(&mut self, id: Id, layer_id: LayerId) {
927        if !self.allows_interaction(layer_id) {
928            return;
929        }
930        self.focus_mut().interested_in_focus(id);
931    }
932
933    /// Limit focus to widgets on the given layer and above.
934    /// If this is called multiple times per frame, the top layer wins.
935    pub fn set_modal_layer(&mut self, layer_id: LayerId) {
936        if let Some(current) = self.focus().and_then(|f| f.top_modal_layer_current_frame) {
937            if matches!(
938                self.areas().compare_order(layer_id, current),
939                std::cmp::Ordering::Less
940            ) {
941                return;
942            }
943        }
944
945        self.focus_mut().set_modal_layer(layer_id);
946    }
947
948    /// Get the top modal layer (from the previous frame).
949    pub fn top_modal_layer(&self) -> Option<LayerId> {
950        self.focus()?.top_modal_layer()
951    }
952
953    /// Stop editing the active [`TextEdit`](crate::TextEdit) (if any).
954    #[inline(always)]
955    pub fn stop_text_input(&mut self) {
956        self.focus_mut().focused_widget = None;
957    }
958
959    /// Forget window positions, sizes etc.
960    /// Can be used to auto-layout windows.
961    pub fn reset_areas(&mut self) {
962        for area in self.areas.values_mut() {
963            *area = Default::default();
964        }
965    }
966
967    /// Obtain the previous rectangle of an area.
968    pub fn area_rect(&self, id: impl Into<Id>) -> Option<Rect> {
969        self.areas().get(id.into()).map(|state| state.rect())
970    }
971
972    pub(crate) fn interaction(&self) -> &InteractionState {
973        self.interactions
974            .get(&self.viewport_id)
975            .expect("Failed to get interaction")
976    }
977
978    pub(crate) fn interaction_mut(&mut self) -> &mut InteractionState {
979        self.interactions.entry(self.viewport_id).or_default()
980    }
981
982    pub(crate) fn focus(&self) -> Option<&Focus> {
983        self.focus.get(&self.viewport_id)
984    }
985
986    pub(crate) fn focus_mut(&mut self) -> &mut Focus {
987        self.focus.entry(self.viewport_id).or_default()
988    }
989}
990
991/// State of an open popup.
992#[derive(Clone, Copy, Debug)]
993struct OpenPopup {
994    /// Id of the popup.
995    id: Id,
996
997    /// Optional position of the popup.
998    pos: Option<Pos2>,
999
1000    /// Whether this popup was still open this frame. Otherwise it's considered abandoned and `Memory::popup` will be cleared.
1001    open_this_frame: bool,
1002}
1003
1004impl OpenPopup {
1005    /// Create a new `OpenPopup`.
1006    fn new(id: Id, pos: Option<Pos2>) -> Self {
1007        Self {
1008            id,
1009            pos,
1010            open_this_frame: true,
1011        }
1012    }
1013}
1014
1015/// ## Deprecated popup API
1016/// Use [`crate::Popup`] instead.
1017impl Memory {
1018    /// Is the given popup open?
1019    #[deprecated = "Use Popup::is_id_open instead"]
1020    pub fn is_popup_open(&self, popup_id: Id) -> bool {
1021        self.popups
1022            .get(&self.viewport_id)
1023            .is_some_and(|state| state.id == popup_id)
1024            || self.everything_is_visible()
1025    }
1026
1027    /// Is any popup open?
1028    #[deprecated = "Use Popup::is_any_open instead"]
1029    pub fn any_popup_open(&self) -> bool {
1030        self.popups.contains_key(&self.viewport_id) || self.everything_is_visible()
1031    }
1032
1033    /// Open the given popup and close all others.
1034    ///
1035    /// Note that you must call `keep_popup_open` on subsequent frames as long as the popup is open.
1036    #[deprecated = "Use Popup::open_id instead"]
1037    pub fn open_popup(&mut self, popup_id: Id) {
1038        self.popups
1039            .insert(self.viewport_id, OpenPopup::new(popup_id, None));
1040    }
1041
1042    /// Popups must call this every frame while open.
1043    ///
1044    /// This is needed because in some cases popups can go away without `close_popup` being
1045    /// called. For example, when a context menu is open and the underlying widget stops
1046    /// being rendered.
1047    #[deprecated = "Use Popup::show instead"]
1048    pub fn keep_popup_open(&mut self, popup_id: Id) {
1049        if let Some(state) = self.popups.get_mut(&self.viewport_id) {
1050            if state.id == popup_id {
1051                state.open_this_frame = true;
1052            }
1053        }
1054    }
1055
1056    /// Open the popup and remember its position.
1057    #[deprecated = "Use Popup with PopupAnchor::Position instead"]
1058    pub fn open_popup_at(&mut self, popup_id: Id, pos: impl Into<Option<Pos2>>) {
1059        self.popups
1060            .insert(self.viewport_id, OpenPopup::new(popup_id, pos.into()));
1061    }
1062
1063    /// Get the position for this popup.
1064    #[deprecated = "Use Popup::position_of_id instead"]
1065    pub fn popup_position(&self, id: Id) -> Option<Pos2> {
1066        self.popups
1067            .get(&self.viewport_id)
1068            .and_then(|state| if state.id == id { state.pos } else { None })
1069    }
1070
1071    /// Close any currently open popup.
1072    #[deprecated = "Use Popup::close_all instead"]
1073    pub fn close_all_popups(&mut self) {
1074        self.popups.clear();
1075    }
1076
1077    /// Close the given popup, if it is open.
1078    ///
1079    /// See also [`Self::close_all_popups`] if you want to close any / all currently open popups.
1080    #[deprecated = "Use Popup::close_id instead"]
1081    pub fn close_popup(&mut self, popup_id: Id) {
1082        #[expect(deprecated)]
1083        if self.is_popup_open(popup_id) {
1084            self.popups.remove(&self.viewport_id);
1085        }
1086    }
1087
1088    /// Toggle the given popup between closed and open.
1089    ///
1090    /// Note: At most, only one popup can be open at a time.
1091    #[deprecated = "Use Popup::toggle_id instead"]
1092    pub fn toggle_popup(&mut self, popup_id: Id) {
1093        #[expect(deprecated)]
1094        if self.is_popup_open(popup_id) {
1095            self.close_popup(popup_id);
1096        } else {
1097            self.open_popup(popup_id);
1098        }
1099    }
1100}
1101
1102impl Memory {
1103    /// If true, all windows, menus, tooltips, etc., will be visible at once.
1104    ///
1105    /// This is useful for testing, benchmarking, pre-caching, etc.
1106    ///
1107    /// Experimental feature!
1108    #[inline(always)]
1109    pub fn everything_is_visible(&self) -> bool {
1110        self.everything_is_visible
1111    }
1112
1113    /// If true, all windows, menus, tooltips etc are to be visible at once.
1114    ///
1115    /// This is useful for testing, benchmarking, pre-caching, etc.
1116    ///
1117    /// Experimental feature!
1118    pub fn set_everything_is_visible(&mut self, value: bool) {
1119        self.everything_is_visible = value;
1120    }
1121}
1122
1123// ----------------------------------------------------------------------------
1124
1125/// Map containing the index of each layer in the order list, for quick lookups.
1126type OrderMap = HashMap<LayerId, usize>;
1127
1128/// Keeps track of [`Area`](crate::containers::area::Area)s, which are free-floating [`Ui`](crate::Ui)s.
1129/// These [`Area`](crate::containers::area::Area)s can be in any [`Order`].
1130#[derive(Clone, Debug, Default)]
1131#[cfg_attr(feature = "serde", derive(serde::Deserialize, serde::Serialize))]
1132#[cfg_attr(feature = "serde", serde(default))]
1133pub struct Areas {
1134    areas: IdMap<area::AreaState>,
1135
1136    visible_areas_last_frame: ahash::HashSet<LayerId>,
1137    visible_areas_current_frame: ahash::HashSet<LayerId>,
1138
1139    // ----------------------------
1140    // Everything below this is general to all layers, not just areas.
1141    // TODO(emilk): move this to a separate struct.
1142    /// Back-to-front,  top is last.
1143    order: Vec<LayerId>,
1144
1145    /// Inverse of [`Self::order`], calculated at the end of the frame.
1146    order_map: OrderMap,
1147
1148    /// When an area wants to be on top, it is assigned here.
1149    /// This is used to reorder the layers at the end of the frame.
1150    /// If several layers want to be on top, they will keep their relative order.
1151    /// This means closing three windows and then reopening them all in one frame
1152    /// results in them being sent to the top and keeping their previous internal order.
1153    wants_to_be_on_top: ahash::HashSet<LayerId>,
1154
1155    /// The sublayers that each layer has.
1156    ///
1157    /// The parent sublayer is moved directly above the child sublayers in the ordering.
1158    sublayers: ahash::HashMap<LayerId, HashSet<LayerId>>,
1159}
1160
1161impl Areas {
1162    pub(crate) fn count(&self) -> usize {
1163        self.areas.len()
1164    }
1165
1166    pub(crate) fn get(&self, id: Id) -> Option<&area::AreaState> {
1167        self.areas.get(&id)
1168    }
1169
1170    /// All layers back-to-front, top is last.
1171    pub(crate) fn order(&self) -> &[LayerId] {
1172        &self.order
1173    }
1174
1175    /// Compare the order of two layers, based on the order list from last frame.
1176    ///
1177    /// May return [`std::cmp::Ordering::Equal`] if the layers are not in the order list.
1178    pub(crate) fn compare_order(&self, a: LayerId, b: LayerId) -> std::cmp::Ordering {
1179        // Sort by layer `order` first and use `order_map` to resolve disputes.
1180        // If `order_map` only contains one layer ID, then the other one will be
1181        // lower because `None < Some(x)`.
1182        match a.order.cmp(&b.order) {
1183            std::cmp::Ordering::Equal => self.order_map.get(&a).cmp(&self.order_map.get(&b)),
1184            cmp => cmp,
1185        }
1186    }
1187
1188    pub(crate) fn set_state(&mut self, layer_id: LayerId, state: area::AreaState) {
1189        self.visible_areas_current_frame.insert(layer_id);
1190        self.areas.insert(layer_id.id, state);
1191        if !self.order.contains(&layer_id) {
1192            self.order.push(layer_id);
1193        }
1194    }
1195
1196    /// Top-most layer at the given position.
1197    pub fn layer_id_at(
1198        &self,
1199        pos: Pos2,
1200        layer_to_global: &HashMap<LayerId, TSTransform>,
1201    ) -> Option<LayerId> {
1202        for layer in self.order.iter().rev() {
1203            if self.is_visible(layer) {
1204                if let Some(state) = self.areas.get(&layer.id) {
1205                    let mut rect = state.rect();
1206                    if state.interactable {
1207                        if let Some(to_global) = layer_to_global.get(layer) {
1208                            rect = *to_global * rect;
1209                        }
1210
1211                        if rect.contains(pos) {
1212                            return Some(*layer);
1213                        }
1214                    }
1215                }
1216            }
1217        }
1218        None
1219    }
1220
1221    pub fn visible_last_frame(&self, layer_id: &LayerId) -> bool {
1222        self.visible_areas_last_frame.contains(layer_id)
1223    }
1224
1225    pub fn is_visible(&self, layer_id: &LayerId) -> bool {
1226        self.visible_areas_last_frame.contains(layer_id)
1227            || self.visible_areas_current_frame.contains(layer_id)
1228    }
1229
1230    pub fn visible_layer_ids(&self) -> ahash::HashSet<LayerId> {
1231        self.visible_areas_last_frame
1232            .iter()
1233            .copied()
1234            .chain(self.visible_areas_current_frame.iter().copied())
1235            .collect()
1236    }
1237
1238    pub(crate) fn visible_windows(&self) -> impl Iterator<Item = (LayerId, &area::AreaState)> {
1239        self.visible_layer_ids()
1240            .into_iter()
1241            .filter(|layer| layer.order == crate::Order::Middle)
1242            .filter(|&layer| !self.is_sublayer(&layer))
1243            .filter_map(|layer| Some((layer, self.get(layer.id)?)))
1244    }
1245
1246    pub fn move_to_top(&mut self, layer_id: LayerId) {
1247        self.visible_areas_current_frame.insert(layer_id);
1248        self.wants_to_be_on_top.insert(layer_id);
1249
1250        if !self.order.contains(&layer_id) {
1251            self.order.push(layer_id);
1252        }
1253    }
1254
1255    /// Mark the `child` layer as a sublayer of `parent`.
1256    ///
1257    /// Sublayers are moved directly above the parent layer at the end of the frame. This is mainly
1258    /// intended for adding a new [Area](crate::Area) inside a [Window](crate::Window).
1259    ///
1260    /// This currently only supports one level of nesting. If `parent` is a sublayer of another
1261    /// layer, the behavior is unspecified.
1262    ///
1263    /// The two layers must have the same [`LayerId::order`].
1264    pub fn set_sublayer(&mut self, parent: LayerId, child: LayerId) {
1265        debug_assert_eq!(
1266            parent.order, child.order,
1267            "DEBUG ASSERT: Trying to set sublayers across layers of different order ({:?}, {:?}), which is currently undefined behavior in egui",
1268            parent.order, child.order
1269        );
1270
1271        self.sublayers.entry(parent).or_default().insert(child);
1272
1273        // Make sure the layers are in the order list:
1274        if !self.order.contains(&parent) {
1275            self.order.push(parent);
1276        }
1277        if !self.order.contains(&child) {
1278            self.order.push(child);
1279        }
1280    }
1281
1282    pub fn top_layer_id(&self, order: Order) -> Option<LayerId> {
1283        self.order
1284            .iter()
1285            .filter(|layer| layer.order == order && !self.is_sublayer(layer))
1286            .next_back()
1287            .copied()
1288    }
1289
1290    /// If this layer is the sublayer of another layer, return the parent.
1291    pub fn parent_layer(&self, layer_id: LayerId) -> Option<LayerId> {
1292        self.sublayers.iter().find_map(|(parent, children)| {
1293            if children.contains(&layer_id) {
1294                Some(*parent)
1295            } else {
1296                None
1297            }
1298        })
1299    }
1300
1301    /// All the child layers of this layer.
1302    pub fn child_layers(&self, layer_id: LayerId) -> impl Iterator<Item = LayerId> + '_ {
1303        self.sublayers.get(&layer_id).into_iter().flatten().copied()
1304    }
1305
1306    pub(crate) fn is_sublayer(&self, layer: &LayerId) -> bool {
1307        self.parent_layer(*layer).is_some()
1308    }
1309
1310    pub(crate) fn end_pass(&mut self) {
1311        let Self {
1312            visible_areas_last_frame,
1313            visible_areas_current_frame,
1314            order,
1315            wants_to_be_on_top,
1316            sublayers,
1317            ..
1318        } = self;
1319
1320        std::mem::swap(visible_areas_last_frame, visible_areas_current_frame);
1321        visible_areas_current_frame.clear();
1322
1323        order.sort_by_key(|layer| (layer.order, wants_to_be_on_top.contains(layer)));
1324        wants_to_be_on_top.clear();
1325
1326        // For all layers with sublayers, put the sublayers directly after the parent layer:
1327        let sublayers = std::mem::take(sublayers);
1328        for (parent, children) in sublayers {
1329            let mut moved_layers = vec![parent];
1330            order.retain(|l| {
1331                if children.contains(l) {
1332                    moved_layers.push(*l);
1333                    false
1334                } else {
1335                    true
1336                }
1337            });
1338            let Some(parent_pos) = order.iter().position(|l| l == &parent) else {
1339                continue;
1340            };
1341            order.splice(parent_pos..=parent_pos, moved_layers);
1342        }
1343
1344        self.order_map = self
1345            .order
1346            .iter()
1347            .enumerate()
1348            .map(|(i, id)| (*id, i))
1349            .collect();
1350    }
1351}
1352
1353// ----------------------------------------------------------------------------
1354
1355#[test]
1356fn memory_impl_send_sync() {
1357    fn assert_send_sync<T: Send + Sync>() {}
1358    assert_send_sync::<Memory>();
1359}
1360
1361#[test]
1362fn order_map_total_ordering() {
1363    let mut layers = [
1364        LayerId::new(Order::Tooltip, Id::new("a")),
1365        LayerId::new(Order::Background, Id::new("b")),
1366        LayerId::new(Order::Background, Id::new("c")),
1367        LayerId::new(Order::Tooltip, Id::new("d")),
1368        LayerId::new(Order::Background, Id::new("e")),
1369        LayerId::new(Order::Background, Id::new("f")),
1370        LayerId::new(Order::Tooltip, Id::new("g")),
1371    ];
1372    let mut areas = Areas::default();
1373
1374    // skip some of the layers
1375    for &layer in &layers[3..] {
1376        areas.set_state(layer, crate::AreaState::default());
1377    }
1378    areas.end_pass(); // sort layers
1379
1380    // Sort layers
1381    layers.sort_by(|&a, &b| areas.compare_order(a, b));
1382
1383    // Assert that `areas.compare_order()` forms a total ordering
1384    let mut equivalence_classes = vec![0];
1385    let mut i = 0;
1386    for l in layers.windows(2) {
1387        assert!(l[0].order <= l[1].order, "does not follow LayerId.order");
1388        if areas.compare_order(l[0], l[1]) != std::cmp::Ordering::Equal {
1389            i += 1;
1390        }
1391        equivalence_classes.push(i);
1392    }
1393    assert_eq!(layers.len(), equivalence_classes.len());
1394    for (&l1, c1) in std::iter::zip(&layers, &equivalence_classes) {
1395        for (&l2, c2) in std::iter::zip(&layers, &equivalence_classes) {
1396            assert_eq!(
1397                c1.cmp(c2),
1398                areas.compare_order(l1, l2),
1399                "not a total ordering",
1400            );
1401        }
1402    }
1403}