1use std::{cmp::Ordering, fmt, ops::Range, rc::Rc, sync::Arc};
2
3use thiserror::Error;
4use unicode_segmentation::UnicodeSegmentation;
5
6use crate::{
7 AccessibilityRole, Element, ElementId, EventContext, FocusHandle, IntoElement, KeyBinding,
8 StateAccessor, ViewContext, VirtualList, div,
9};
10
11pub const MAX_PICKER_ITEMS: usize = 65_536;
13pub const MAX_PICKER_RESULTS: usize = 2_048;
15pub const MAX_PICKER_QUERY_GRAPHEMES: usize = 128;
17pub const MAX_PICKER_QUERY_BYTES: usize = 4 * 1024;
19pub const MAX_PICKER_ITEM_TEXT_BYTES: usize = 64 * 1024;
21pub const MAX_PICKER_TEXT_BYTES: usize = 16 * 1024 * 1024;
23
24const MAX_NORMALIZED_QUERY_CHARS: usize = MAX_PICKER_QUERY_GRAPHEMES * 4;
25const MAX_VISIBLE_PICKER_ROWS: usize = 64;
26const PICKER_KEY_CONTEXT: &str = "Picker";
27const INPUT_ID_TAG: u64 = 0x8b8b_a761_9a8c_4f3d;
28const ROW_ID_TAG: u64 = 0x53f7_b9c2_7651_0aa1;
29
30#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
32pub struct PickerPrevious;
33#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
35pub struct PickerNext;
36#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
38pub struct PickerPageUp;
39#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
41pub struct PickerPageDown;
42#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
44pub struct PickerFirst;
45#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
47pub struct PickerLast;
48#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
50pub struct PickerConfirm;
51
52pub fn picker_key_bindings() -> [KeyBinding; 7] {
57 [
58 KeyBinding::new("up", PickerPrevious, Some(PICKER_KEY_CONTEXT)),
59 KeyBinding::new("down", PickerNext, Some(PICKER_KEY_CONTEXT)),
60 KeyBinding::new("pageup", PickerPageUp, Some(PICKER_KEY_CONTEXT)),
61 KeyBinding::new("pagedown", PickerPageDown, Some(PICKER_KEY_CONTEXT)),
62 KeyBinding::new("platform-up", PickerFirst, Some(PICKER_KEY_CONTEXT)),
63 KeyBinding::new("platform-down", PickerLast, Some(PICKER_KEY_CONTEXT)),
64 KeyBinding::new("enter", PickerConfirm, Some(PICKER_KEY_CONTEXT)),
65 ]
66}
67
68#[derive(Clone, Debug)]
70pub struct PickerItem<T> {
71 id: Option<ElementId>,
72 label: Arc<str>,
73 detail: Option<Arc<str>>,
74 keywords: Arc<str>,
75 shortcut: Option<Arc<str>>,
76 value: T,
77 disabled: bool,
78}
79
80impl<T> PickerItem<T> {
81 pub fn new(label: impl Into<Arc<str>>, value: T) -> Self {
82 Self {
83 id: None,
84 label: label.into(),
85 detail: None,
86 keywords: Arc::from(""),
87 shortcut: None,
88 value,
89 disabled: false,
90 }
91 }
92
93 pub fn id(mut self, id: impl Into<ElementId>) -> Self {
95 self.id = Some(id.into());
96 self
97 }
98
99 pub fn detail(mut self, detail: impl Into<Arc<str>>) -> Self {
100 let detail = detail.into();
101 self.detail = (!detail.is_empty()).then_some(detail);
102 self
103 }
104
105 pub fn keywords(mut self, keywords: impl Into<Arc<str>>) -> Self {
107 self.keywords = keywords.into();
108 self
109 }
110
111 pub fn shortcut(mut self, shortcut: impl Into<Arc<str>>) -> Self {
112 let shortcut = shortcut.into();
113 self.shortcut = (!shortcut.is_empty()).then_some(shortcut);
114 self
115 }
116
117 pub fn disabled(mut self, disabled: bool) -> Self {
118 self.disabled = disabled;
119 self
120 }
121
122 pub fn label(&self) -> &Arc<str> {
123 &self.label
124 }
125
126 pub const fn stable_id(&self) -> Option<ElementId> {
127 self.id
128 }
129
130 pub fn detail_text(&self) -> Option<&Arc<str>> {
131 self.detail.as_ref()
132 }
133
134 pub fn search_keywords(&self) -> &Arc<str> {
135 &self.keywords
136 }
137
138 pub fn shortcut_text(&self) -> Option<&Arc<str>> {
139 self.shortcut.as_ref()
140 }
141
142 pub fn value(&self) -> &T {
143 &self.value
144 }
145
146 pub fn into_value(self) -> T {
147 self.value
148 }
149
150 pub fn is_disabled(&self) -> bool {
151 self.disabled
152 }
153}
154
155#[derive(Clone, Debug, Eq, Error, PartialEq)]
157pub enum PickerError {
158 #[error("a picker supports at most {limit} source items")]
159 TooManyItems { limit: usize },
160 #[error("picker item {index} has {bytes} bytes of searchable text; the limit is {limit}")]
161 ItemTextTooLong {
162 index: usize,
163 bytes: usize,
164 limit: usize,
165 },
166 #[error("picker searchable text uses {bytes} bytes; the total limit is {limit}")]
167 TextBudgetExceeded { bytes: usize, limit: usize },
168 #[error("picker item ID {id:?} is declared more than once")]
169 DuplicateId { id: ElementId },
170}
171
172#[derive(Clone, Copy, Debug, Default, Eq, PartialEq)]
174pub enum PickerFilterMode {
175 #[default]
177 Fuzzy,
178 Contains,
183 StartsWith,
185 None,
189}
190
191type PickerFilterFn = dyn Fn(&str, &str) -> bool;
206
207#[derive(Clone)]
208pub struct PickerFilter(Rc<PickerFilterFn>);
209
210impl PickerFilter {
211 pub fn new(filter: impl Fn(&str, &str) -> bool + 'static) -> Self {
212 Self(Rc::new(filter))
213 }
214
215 pub fn matches(&self, label: &str, query: &str) -> bool {
217 (self.0)(label, query)
218 }
219}
220
221impl fmt::Debug for PickerFilter {
222 fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
223 formatter
224 .debug_struct("PickerFilter")
225 .finish_non_exhaustive()
226 }
227}
228
229impl PartialEq for PickerFilter {
230 fn eq(&self, other: &Self) -> bool {
231 Rc::ptr_eq(&self.0, &other.0)
232 }
233}
234
235#[derive(Clone, Copy, Debug, PartialEq)]
241pub struct PickerLayout {
242 pub row_height: f32,
243 pub max_visible_rows: usize,
244}
245
246impl PickerLayout {
247 pub fn new(row_height: f32) -> Self {
248 Self {
249 row_height: finite_clamped(row_height, 24.0, 256.0, 48.0),
250 max_visible_rows: 9,
251 }
252 }
253
254 pub fn row_height(mut self, row_height: f32) -> Self {
255 self.row_height = finite_clamped(row_height, 24.0, 256.0, 48.0);
256 self
257 }
258
259 pub fn max_visible_rows(mut self, rows: usize) -> Self {
260 self.max_visible_rows = rows;
261 self.sanitized()
262 }
263
264 fn sanitized(mut self) -> Self {
265 self.row_height = finite_clamped(self.row_height, 24.0, 256.0, 48.0);
266 self.max_visible_rows = self.max_visible_rows.clamp(1, MAX_VISIBLE_PICKER_ROWS);
267 self
268 }
269}
270
271impl Default for PickerLayout {
272 fn default() -> Self {
273 Self::new(48.0)
274 }
275}
276
277#[derive(Clone, Debug)]
278struct MatchEntry {
279 source_index: usize,
280 score: i32,
281 label_ranges: Arc<[Range<usize>]>,
282}
283
284#[derive(Clone, Debug)]
286pub struct PickerMatch<'a, T> {
287 result_index: usize,
288 source_index: usize,
289 score: i32,
290 label_ranges: &'a Arc<[Range<usize>]>,
291 item: &'a PickerItem<T>,
292 selected: bool,
293}
294
295impl<'a, T> PickerMatch<'a, T> {
296 pub fn result_index(&self) -> usize {
297 self.result_index
298 }
299
300 pub fn source_index(&self) -> usize {
301 self.source_index
302 }
303
304 pub fn score(&self) -> i32 {
305 self.score
306 }
307
308 pub fn label_ranges(&self) -> &'a [Range<usize>] {
309 self.label_ranges
310 }
311
312 pub(crate) fn shared_label_ranges(&self) -> Arc<[Range<usize>]> {
313 self.label_ranges.clone()
314 }
315
316 pub fn item(&self) -> &'a PickerItem<T> {
317 self.item
318 }
319
320 pub fn is_selected(&self) -> bool {
321 self.selected
322 }
323}
324
325pub struct PickerState<T> {
330 items: Arc<[PickerItem<T>]>,
331 query: Arc<str>,
332 filter_mode: PickerFilterMode,
333 filter: Option<PickerFilter>,
334 matches: Vec<MatchEntry>,
335 total_match_count: usize,
336 selected_result: Option<usize>,
337 list: VirtualList,
338 layout: PickerLayout,
339 score_scratch: Vec<(i32, usize)>,
340}
341
342impl<T> fmt::Debug for PickerState<T> {
343 fn fmt(&self, formatter: &mut fmt::Formatter<'_>) -> fmt::Result {
344 formatter
345 .debug_struct("PickerState")
346 .field("items", &self.items.len())
347 .field("query", &self.query)
348 .field("filter_mode", &self.filter_mode)
349 .field("filter", &self.filter)
350 .field("matches", &self.matches.len())
351 .field("total_match_count", &self.total_match_count)
352 .field("selected_result", &self.selected_result)
353 .field("list", &self.list)
354 .field("layout", &self.layout)
355 .finish_non_exhaustive()
356 }
357}
358
359impl<T> PickerState<T> {
360 pub fn new(items: impl IntoIterator<Item = PickerItem<T>>) -> Result<Self, PickerError> {
361 let items = collect_picker_items(items)?;
362 let layout = PickerLayout::default();
363 let mut state = Self {
364 items: Arc::from(items),
365 query: Arc::from(""),
366 filter_mode: PickerFilterMode::Fuzzy,
367 filter: None,
368 matches: Vec::with_capacity(MAX_PICKER_RESULTS.min(256)),
369 total_match_count: 0,
370 selected_result: None,
371 list: VirtualList::new(0, layout.row_height).with_overscan(1),
372 layout,
373 score_scratch: Vec::new(),
374 };
375 state.rebuild_matches();
376 Ok(state)
377 }
378
379 pub fn with_layout(mut self, layout: PickerLayout) -> Self {
380 self.set_layout(layout);
381 self
382 }
383
384 pub const fn layout(&self) -> PickerLayout {
385 self.layout
386 }
387
388 pub fn set_layout(&mut self, layout: PickerLayout) -> bool {
389 let layout = layout.sanitized();
390 if self.layout == layout {
391 return false;
392 }
393 let row_height_changed = self.layout.row_height != layout.row_height;
394 self.layout = layout;
395 if row_height_changed {
396 let viewport_height = self.list.viewport_height();
397 self.list =
398 VirtualList::new(self.matches.len(), self.layout.row_height).with_overscan(1);
399 self.list.set_viewport_height(viewport_height);
400 if let Some(selected) = self.selected_result {
401 self.list.scroll_to_reveal(selected);
402 }
403 }
404 true
405 }
406
407 pub fn set_items(
408 &mut self,
409 items: impl IntoIterator<Item = PickerItem<T>>,
410 ) -> Result<(), PickerError> {
411 self.items = Arc::from(collect_picker_items(items)?);
412 self.rebuild_matches();
413 Ok(())
414 }
415
416 pub fn items(&self) -> &[PickerItem<T>] {
417 &self.items
418 }
419
420 pub(crate) fn shared_items(&self) -> Arc<[PickerItem<T>]> {
421 self.items.clone()
422 }
423
424 pub const fn filter_mode(&self) -> PickerFilterMode {
425 self.filter_mode
426 }
427
428 pub fn set_filter_mode(&mut self, filter_mode: PickerFilterMode) -> bool {
429 if self.filter_mode == filter_mode {
430 return false;
431 }
432 self.filter_mode = filter_mode;
433 self.rebuild_matches();
434 true
435 }
436
437 pub fn filter(&self) -> Option<&PickerFilter> {
439 self.filter.as_ref()
440 }
441
442 pub fn set_filter(&mut self, filter: Option<PickerFilter>) -> bool {
446 if self.filter == filter {
447 return false;
448 }
449 self.filter = filter;
450 self.rebuild_matches();
451 true
452 }
453
454 pub fn item_at(&self, source_index: usize) -> Option<&PickerItem<T>> {
455 self.items.get(source_index)
456 }
457
458 pub fn source_index_for_id(&self, id: impl Into<ElementId>) -> Option<usize> {
459 let id = id.into();
460 self.items
461 .iter()
462 .position(|item| item.stable_id() == Some(id))
463 }
464
465 pub fn query(&self) -> &Arc<str> {
466 &self.query
467 }
468
469 pub fn set_query(&mut self, query: &str) -> bool {
471 let query = bounded_query(query);
472 if self.query.as_ref() == query {
473 return false;
474 }
475 self.query = Arc::from(query);
476 self.rebuild_matches();
477 true
478 }
479
480 pub fn reset(&mut self) -> bool {
483 let changed = !self.query.is_empty()
484 || self.selected_result
485 != (0..self.matches.len()).find(|index| self.result_is_selectable(*index))
486 || self.list.scroll_offset() != 0.0;
487 self.query = Arc::from("");
488 self.rebuild_matches();
489 changed
490 }
491
492 pub fn result_count(&self) -> usize {
493 self.matches.len()
494 }
495
496 pub fn total_match_count(&self) -> usize {
497 self.total_match_count
498 }
499
500 pub fn results_truncated(&self) -> bool {
501 self.total_match_count > self.matches.len()
502 }
503
504 pub fn selected_result_index(&self) -> Option<usize> {
505 self.selected_result
506 }
507
508 pub fn selected_source_index(&self) -> Option<usize> {
509 self.selected_match().map(|matched| matched.source_index())
510 }
511
512 pub fn match_at(&self, result_index: usize) -> Option<PickerMatch<'_, T>> {
513 let entry = self.matches.get(result_index)?;
514 Some(PickerMatch {
515 result_index,
516 source_index: entry.source_index,
517 score: entry.score,
518 label_ranges: &entry.label_ranges,
519 item: &self.items[entry.source_index],
520 selected: self.selected_result == Some(result_index),
521 })
522 }
523
524 pub fn selected_match(&self) -> Option<PickerMatch<'_, T>> {
525 self.selected_result.and_then(|index| self.match_at(index))
526 }
527
528 pub fn selected_value(&self) -> Option<&T> {
529 self.selected_match().map(|matched| matched.item.value())
530 }
531
532 pub fn visible_matches(&self) -> impl Iterator<Item = PickerMatch<'_, T>> + '_ {
533 self.list
534 .visible_rows()
535 .range
536 .filter_map(move |index| self.match_at(index))
537 }
538
539 pub fn virtual_list(&self) -> &VirtualList {
540 &self.list
541 }
542
543 pub(crate) fn set_result_viewport_height(&mut self, height: f32) {
544 self.list.set_viewport_height(height);
545 }
546
547 pub fn select_result(&mut self, result_index: usize) -> bool {
548 if !self.result_is_selectable(result_index) {
549 return false;
550 }
551 let changed = self.selected_result != Some(result_index);
552 self.selected_result = Some(result_index);
553 self.list.scroll_to_reveal(result_index) || changed
554 }
555
556 pub fn select_source(&mut self, source_index: usize) -> bool {
557 self.matches
558 .iter()
559 .position(|entry| entry.source_index == source_index)
560 .is_some_and(|result_index| self.select_result(result_index))
561 }
562
563 pub fn select_next(&mut self) -> bool {
564 let Some(next) = self.next_selectable(true) else {
565 return false;
566 };
567 self.select_result(next)
568 }
569
570 pub fn select_previous(&mut self) -> bool {
571 let Some(previous) = self.next_selectable(false) else {
572 return false;
573 };
574 self.select_result(previous)
575 }
576
577 pub fn select_first(&mut self) -> bool {
578 let Some(first) = (0..self.matches.len()).find(|index| self.result_is_selectable(*index))
579 else {
580 return false;
581 };
582 self.select_result(first)
583 }
584
585 pub fn select_last(&mut self) -> bool {
586 let Some(last) = (0..self.matches.len())
587 .rev()
588 .find(|index| self.result_is_selectable(*index))
589 else {
590 return false;
591 };
592 self.select_result(last)
593 }
594
595 pub fn select_page_down(&mut self) -> bool {
596 self.select_page(true)
597 }
598
599 pub fn select_page_up(&mut self) -> bool {
600 self.select_page(false)
601 }
602
603 pub fn input_focus_handle(id: impl Into<ElementId>) -> FocusHandle {
608 FocusHandle::new(derived_picker_id(id.into(), INPUT_ID_TAG, 0))
609 }
610
611 #[allow(clippy::too_many_arguments)]
622 pub fn element<V, E, RenderRow, Activate>(
623 &mut self,
624 cx: &mut ViewContext<'_, V>,
625 id: impl Into<ElementId>,
626 label: impl Into<Arc<str>>,
627 access: fn(&mut V) -> &mut PickerState<T>,
628 input: Element,
629 empty: Element,
630 render_row: RenderRow,
631 activate: Activate,
632 ) -> Element
633 where
634 V: 'static,
635 T: Clone + 'static,
636 E: IntoElement,
637 RenderRow: FnMut(PickerMatch<'_, T>) -> E,
638 Activate: Fn(&mut V, T, &mut EventContext) + Clone + 'static,
639 {
640 self.element_with(
641 cx,
642 id,
643 label,
644 StateAccessor::from(access),
645 input,
646 empty,
647 render_row,
648 activate,
649 )
650 }
651
652 #[allow(clippy::too_many_arguments)]
657 pub fn element_with<V, E, RenderRow, Activate>(
658 &mut self,
659 cx: &mut ViewContext<'_, V>,
660 id: impl Into<ElementId>,
661 label: impl Into<Arc<str>>,
662 access_source: StateAccessor<V, PickerState<T>>,
663 input: Element,
664 empty: Element,
665 mut render_row: RenderRow,
666 activate: Activate,
667 ) -> Element
668 where
669 V: 'static,
670 T: Clone + 'static,
671 E: IntoElement,
672 RenderRow: FnMut(PickerMatch<'_, T>) -> E,
673 Activate: Fn(&mut V, T, &mut EventContext) + Clone + 'static,
674 {
675 let id = id.into();
676 let label = label.into();
677 let input_focus = Self::input_focus_handle(id);
678 let input_id = input_focus.id();
679 let layout = self.layout;
680 let visible_row_count = self.matches.len().min(layout.max_visible_rows);
681 let results_height = visible_row_count as f32 * layout.row_height;
682 self.list.set_viewport_height(results_height);
683 if let Some(selected) = self.selected_result {
684 self.list.scroll_to_reveal(selected);
685 }
686
687 let access = access_source.clone();
688 let query = cx.input_listener(input_id, move |view, value, cx| {
689 if access.get(view).set_query(value) {
690 cx.invalidate();
691 }
692 });
693 let access = access_source.clone();
694 let previous = cx.action_listener(id, move |view, _: &PickerPrevious, cx| {
695 if access.get(view).select_previous() {
696 cx.invalidate();
697 }
698 });
699 let access = access_source.clone();
700 let next = cx.action_listener(id, move |view, _: &PickerNext, cx| {
701 if access.get(view).select_next() {
702 cx.invalidate();
703 }
704 });
705 let access = access_source.clone();
706 let page_up = cx.action_listener(id, move |view, _: &PickerPageUp, cx| {
707 if access.get(view).select_page_up() {
708 cx.invalidate();
709 }
710 });
711 let access = access_source.clone();
712 let page_down = cx.action_listener(id, move |view, _: &PickerPageDown, cx| {
713 if access.get(view).select_page_down() {
714 cx.invalidate();
715 }
716 });
717 let access = access_source.clone();
718 let first = cx.action_listener(id, move |view, _: &PickerFirst, cx| {
719 if access.get(view).select_first() {
720 cx.invalidate();
721 }
722 });
723 let access = access_source.clone();
724 let last = cx.action_listener(id, move |view, _: &PickerLast, cx| {
725 if access.get(view).select_last() {
726 cx.invalidate();
727 }
728 });
729 let confirm_activate = activate.clone();
730 let access = access_source.clone();
731 let confirm = cx.action_listener(id, move |view, _: &PickerConfirm, cx| {
732 let value = access.get(view).selected_value().cloned();
733 if let Some(value) = value {
734 confirm_activate(view, value, cx);
735 }
736 });
737
738 let mut rows = Vec::with_capacity(self.list.visible_rows().len());
739 for result_index in self.list.visible_rows().range {
740 let entry = &self.matches[result_index];
741 let item = &self.items[entry.source_index];
742 let source_index = entry.source_index;
743 let row_id = derived_picker_id(
744 id,
745 ROW_ID_TAG,
746 item.stable_id()
747 .map_or(source_index as u64, ElementId::as_u64),
748 );
749 let selected = self.selected_result == Some(result_index);
750 let disabled = item.disabled;
751 let matched = PickerMatch {
752 result_index,
753 source_index,
754 score: entry.score,
755 label_ranges: &entry.label_ranges,
756 item,
757 selected,
758 };
759 let mut row = render_row(matched)
760 .into_element()
761 .id(row_id)
762 .disabled(disabled)
763 .selected(selected)
764 .accessibility_role(AccessibilityRole::MenuItem)
765 .accessibility_label(item.label.clone())
766 .tab_index(-1)
767 .absolute()
768 .top(result_index as f32 * layout.row_height - self.list.scroll_offset())
769 .left(0.0)
770 .w_full()
771 .h(layout.row_height)
772 .flex_none()
773 .app_region_no_drag()
774 .cursor_default();
775 if !disabled {
776 let clicked_value = item.value.clone();
777 let clicked_activate = activate.clone();
778 let access = access_source.clone();
779 let clicked = cx.listener(row_id, move |view, cx| {
780 access.get(view).select_source(source_index);
781 clicked_activate(view, clicked_value.clone(), cx);
782 });
783 row = row.on_click(clicked);
784 }
785 rows.push(row);
786 }
787
788 let results = if self.matches.is_empty() {
789 div()
790 .h(layout.row_height)
791 .w_full()
792 .accessibility_role(AccessibilityRole::List)
793 .child(empty)
794 } else {
795 div()
796 .relative()
797 .h(results_height)
798 .w_full()
799 .overflow_hidden()
800 .virtual_scroll(&self.list)
801 .accessibility_role(AccessibilityRole::List)
802 .children(rows)
803 };
804
805 div()
806 .focus_scope(FocusHandle::new(id))
807 .key_context(PICKER_KEY_CONTEXT)
808 .on_action(previous)
809 .on_action(next)
810 .on_action(page_up)
811 .on_action(page_down)
812 .on_action(first)
813 .on_action(last)
814 .on_action(confirm)
815 .accessibility_role(AccessibilityRole::Dialog)
816 .accessibility_label(label)
817 .flex_col()
818 .overflow_hidden()
819 .app_region_no_drag()
820 .child(
821 input
822 .id(input_id)
823 .track_focus(input_focus)
824 .auto_focus()
825 .on_input(query)
826 .max_length(MAX_PICKER_QUERY_GRAPHEMES)
827 .app_region_no_drag(),
828 )
829 .child(results)
830 }
831
832 fn rebuild_matches(&mut self) {
833 let normalized_query = normalized_query(&self.query);
834 self.score_scratch.clear();
835 let predicate_query: String = normalized_query.iter().collect();
836 if !normalized_query.is_empty()
837 && let Some(matching) = self.predicate_matches(&predicate_query)
838 {
839 self.total_match_count = matching.len();
840 self.matches.clear();
841 self.matches
842 .extend(
843 matching
844 .into_iter()
845 .take(MAX_PICKER_RESULTS)
846 .map(|source_index| MatchEntry {
847 source_index,
848 score: 0,
849 label_ranges: Arc::from([]),
850 }),
851 );
852 } else if normalized_query.is_empty() || self.filter_mode == PickerFilterMode::None {
853 self.total_match_count = self.items.len();
854 self.matches.clear();
855 self.matches
856 .extend(
857 (0..self.items.len().min(MAX_PICKER_RESULTS)).map(|source_index| MatchEntry {
858 source_index,
859 score: 0,
860 label_ranges: Arc::from([]),
861 }),
862 );
863 } else {
864 for (source_index, item) in self.items.iter().enumerate() {
865 if let Some(score) = fuzzy_match(item, &normalized_query, None) {
866 self.score_scratch.push((score, source_index));
867 }
868 }
869 self.total_match_count = self.score_scratch.len();
870 let result_limit = self.score_scratch.len().min(MAX_PICKER_RESULTS);
871 if self.score_scratch.len() > result_limit {
872 let items = &self.items;
873 self.score_scratch
874 .select_nth_unstable_by(result_limit, |left, right| {
875 compare_ranked(items, left, right)
876 });
877 self.score_scratch.truncate(result_limit);
878 }
879 let items = &self.items;
880 self.score_scratch
881 .sort_unstable_by(|left, right| compare_ranked(items, left, right));
882 self.matches.clear();
883 self.matches.reserve(
884 self.score_scratch
885 .len()
886 .min(MAX_PICKER_RESULTS)
887 .saturating_sub(self.matches.capacity()),
888 );
889 for &(score, source_index) in &self.score_scratch {
890 let mut ranges = Vec::with_capacity(normalized_query.len().min(16));
891 let recomputed = fuzzy_match(
892 &self.items[source_index],
893 &normalized_query,
894 Some(&mut ranges),
895 );
896 debug_assert_eq!(recomputed, Some(score));
897 self.matches.push(MatchEntry {
898 source_index,
899 score,
900 label_ranges: Arc::from(ranges),
901 });
902 }
903 }
904 self.list.set_len(self.matches.len());
905 self.list.scroll_to(0.0);
906 self.selected_result =
907 (0..self.matches.len()).find(|index| self.result_is_selectable(*index));
908 }
909
910 fn predicate_matches(&self, query: &str) -> Option<Vec<usize>> {
912 let keep: Box<dyn Fn(&str) -> bool> = match (&self.filter, self.filter_mode) {
913 (Some(filter), _) => {
914 let filter = filter.clone();
915 Box::new(move |label: &str| filter.matches(label, query))
916 }
917 (None, PickerFilterMode::Contains) => {
918 Box::new(move |label: &str| label.to_lowercase().contains(query))
919 }
920 (None, PickerFilterMode::StartsWith) => {
921 Box::new(move |label: &str| label.to_lowercase().starts_with(query))
922 }
923 (None, PickerFilterMode::Fuzzy | PickerFilterMode::None) => return None,
924 };
925 Some(
926 self.items
927 .iter()
928 .enumerate()
929 .filter(|(_, item)| keep(item.label()))
930 .map(|(source_index, _)| source_index)
931 .collect(),
932 )
933 }
934
935 fn result_is_selectable(&self, result_index: usize) -> bool {
936 self.matches
937 .get(result_index)
938 .is_some_and(|entry| !self.items[entry.source_index].disabled)
939 }
940
941 fn next_selectable(&self, forward: bool) -> Option<usize> {
942 if self.matches.is_empty() {
943 return None;
944 }
945 let len = self.matches.len();
946 let start = match (self.selected_result, forward) {
947 (Some(index), true) => (index + 1) % len,
948 (Some(index), false) => (index + len - 1) % len,
949 (None, true) => 0,
950 (None, false) => len - 1,
951 };
952 (0..len)
953 .map(|offset| {
954 if forward {
955 (start + offset) % len
956 } else {
957 (start + len - offset) % len
958 }
959 })
960 .find(|index| self.result_is_selectable(*index))
961 }
962
963 fn select_page(&mut self, forward: bool) -> bool {
964 if self.matches.is_empty() {
965 return false;
966 }
967 let page = (self.list.viewport_height() / self.layout.row_height)
968 .floor()
969 .max(1.0) as usize;
970 let current =
971 self.selected_result
972 .unwrap_or(if forward { 0 } else { self.matches.len() - 1 });
973 let target = if forward {
974 current.saturating_add(page).min(self.matches.len() - 1)
975 } else {
976 current.saturating_sub(page)
977 };
978 let candidates: Box<dyn Iterator<Item = usize>> = if forward {
979 Box::new((target..self.matches.len()).chain(0..target))
980 } else {
981 Box::new(
982 (0..=target)
983 .rev()
984 .chain((target + 1..self.matches.len()).rev()),
985 )
986 };
987 let Some(result) = candidates
988 .into_iter()
989 .find(|index| self.result_is_selectable(*index))
990 else {
991 return false;
992 };
993 self.select_result(result)
994 }
995}
996
997fn compare_ranked<T>(
998 items: &[PickerItem<T>],
999 left: &(i32, usize),
1000 right: &(i32, usize),
1001) -> Ordering {
1002 right
1003 .0
1004 .cmp(&left.0)
1005 .then_with(|| items[left.1].label.len().cmp(&items[right.1].label.len()))
1006 .then_with(|| left.1.cmp(&right.1))
1007}
1008
1009pub(crate) fn collect_picker_items<T>(
1010 items: impl IntoIterator<Item = PickerItem<T>>,
1011) -> Result<Vec<PickerItem<T>>, PickerError> {
1012 let iterator = items.into_iter();
1013 let mut collected = Vec::with_capacity(iterator.size_hint().0.min(MAX_PICKER_ITEMS));
1014 let mut stable_ids = Vec::with_capacity(collected.capacity().min(256));
1015 let mut total_bytes = 0usize;
1016 for (index, item) in iterator.enumerate() {
1017 if index == MAX_PICKER_ITEMS {
1018 return Err(PickerError::TooManyItems {
1019 limit: MAX_PICKER_ITEMS,
1020 });
1021 }
1022 let bytes = picker_item_text_bytes(&item);
1023 if bytes > MAX_PICKER_ITEM_TEXT_BYTES {
1024 return Err(PickerError::ItemTextTooLong {
1025 index,
1026 bytes,
1027 limit: MAX_PICKER_ITEM_TEXT_BYTES,
1028 });
1029 }
1030 total_bytes = total_bytes.saturating_add(bytes);
1031 if total_bytes > MAX_PICKER_TEXT_BYTES {
1032 return Err(PickerError::TextBudgetExceeded {
1033 bytes: total_bytes,
1034 limit: MAX_PICKER_TEXT_BYTES,
1035 });
1036 }
1037 if let Some(id) = item.stable_id() {
1038 stable_ids.push(id);
1039 }
1040 collected.push(item);
1041 }
1042 stable_ids.sort_unstable_by_key(|id| id.as_u64());
1043 if let Some(duplicate) = stable_ids.windows(2).find(|ids| ids[0] == ids[1]) {
1044 return Err(PickerError::DuplicateId { id: duplicate[0] });
1045 }
1046 Ok(collected)
1047}
1048
1049fn picker_item_text_bytes<T>(item: &PickerItem<T>) -> usize {
1050 item.label
1051 .len()
1052 .saturating_add(item.detail.as_ref().map_or(0, |detail| detail.len()))
1053 .saturating_add(item.keywords.len())
1054 .saturating_add(item.shortcut.as_ref().map_or(0, |shortcut| shortcut.len()))
1055}
1056
1057fn bounded_query(query: &str) -> &str {
1058 let mut byte_end = query.len().min(MAX_PICKER_QUERY_BYTES);
1059 while !query.is_char_boundary(byte_end) {
1060 byte_end -= 1;
1061 }
1062 let query = &query[..byte_end];
1063 query
1064 .grapheme_indices(true)
1065 .nth(MAX_PICKER_QUERY_GRAPHEMES)
1066 .map_or(query, |(offset, _)| &query[..offset])
1067}
1068
1069fn normalized_query(query: &str) -> Vec<char> {
1070 let mut normalized = Vec::with_capacity(query.len().min(MAX_NORMALIZED_QUERY_CHARS));
1071 let mut previous_space = true;
1072 for character in query.trim().chars() {
1073 for lower in character.to_lowercase() {
1074 let lower = if lower.is_whitespace() { ' ' } else { lower };
1075 if lower == ' ' && previous_space {
1076 continue;
1077 }
1078 normalized.push(lower);
1079 previous_space = lower == ' ';
1080 if normalized.len() == MAX_NORMALIZED_QUERY_CHARS {
1081 return normalized;
1082 }
1083 }
1084 }
1085 if normalized.last() == Some(&' ') {
1086 normalized.pop();
1087 }
1088 normalized
1089}
1090
1091fn fuzzy_match<T>(
1092 item: &PickerItem<T>,
1093 query: &[char],
1094 mut label_ranges: Option<&mut Vec<Range<usize>>>,
1095) -> Option<i32> {
1096 if query.is_empty() {
1097 return Some(0);
1098 }
1099
1100 let segments = [
1101 (item.label.as_ref(), true),
1102 (item.detail.as_deref().unwrap_or(""), false),
1103 (item.keywords.as_ref(), false),
1104 (item.shortcut.as_deref().unwrap_or(""), false),
1105 ];
1106 let mut query_index = 0usize;
1107 let mut ordinal = 0i32;
1108 let mut previous_match = None;
1109 let mut score = 0i32;
1110 let mut first_match_at_label_start = false;
1111 let mut every_match_in_label = true;
1112 let mut every_match_consecutive = true;
1113
1114 for (segment_index, (segment, is_label)) in segments.into_iter().enumerate() {
1115 if segment_index > 0 {
1116 if query[query_index] == ' ' {
1117 apply_fuzzy_match(
1118 &mut score,
1119 &mut previous_match,
1120 &mut every_match_consecutive,
1121 ordinal,
1122 true,
1123 false,
1124 );
1125 query_index += 1;
1126 if query_index == query.len() {
1127 break;
1128 }
1129 }
1130 ordinal += 1;
1131 }
1132 let mut previous_was_alphanumeric = false;
1133 let mut previous_was_space = true;
1134 for (byte_index, character) in segment.char_indices() {
1135 let boundary = !previous_was_alphanumeric;
1136 let original_range = byte_index..byte_index + character.len_utf8();
1137 let mut expansion_index = 0usize;
1138 for lower in character.to_lowercase() {
1139 let lower = if lower.is_whitespace() { ' ' } else { lower };
1140 if lower == ' ' && previous_was_space {
1141 continue;
1142 }
1143 previous_was_space = lower == ' ';
1144 if query[query_index] == lower {
1145 if query_index == 0 {
1146 first_match_at_label_start = is_label && byte_index == 0;
1147 }
1148 every_match_in_label &= is_label;
1149 apply_fuzzy_match(
1150 &mut score,
1151 &mut previous_match,
1152 &mut every_match_consecutive,
1153 ordinal,
1154 boundary && expansion_index == 0,
1155 is_label,
1156 );
1157 if is_label && let Some(ranges) = label_ranges.as_deref_mut() {
1158 push_coalesced_range(ranges, original_range.clone());
1159 }
1160 query_index += 1;
1161 if query_index == query.len() {
1162 break;
1163 }
1164 }
1165 ordinal += 1;
1166 expansion_index += 1;
1167 }
1168 previous_was_alphanumeric = character.is_alphanumeric();
1169 if query_index == query.len() {
1170 break;
1171 }
1172 }
1173 if query_index == query.len() {
1174 break;
1175 }
1176 }
1177
1178 if query_index != query.len() {
1179 return None;
1180 }
1181 if first_match_at_label_start {
1182 score += 420;
1183 }
1184 if every_match_in_label {
1185 score += 180;
1186 }
1187 if every_match_consecutive {
1188 score += 220;
1189 }
1190 score -= i32::try_from(item.label.chars().count().min(255)).unwrap_or(255);
1191 Some(score)
1192}
1193
1194fn apply_fuzzy_match(
1195 score: &mut i32,
1196 previous_match: &mut Option<i32>,
1197 every_match_consecutive: &mut bool,
1198 ordinal: i32,
1199 boundary: bool,
1200 in_label: bool,
1201) {
1202 *score += 1_000;
1203 if boundary {
1204 *score += 110;
1205 }
1206 if in_label {
1207 *score += 55;
1208 } else {
1209 *score -= 35;
1210 }
1211 if let Some(previous) = *previous_match {
1212 let gap = ordinal.saturating_sub(previous + 1);
1213 if gap == 0 {
1214 *score += 150;
1215 } else {
1216 *score -= gap.min(64) * 7;
1217 *every_match_consecutive = false;
1218 }
1219 } else {
1220 *score -= ordinal.min(128) * 3;
1221 }
1222 *previous_match = Some(ordinal);
1223}
1224
1225fn push_coalesced_range(ranges: &mut Vec<Range<usize>>, range: Range<usize>) {
1226 if let Some(previous) = ranges.last_mut()
1227 && range.start <= previous.end
1228 {
1229 previous.end = previous.end.max(range.end);
1230 return;
1231 }
1232 ranges.push(range);
1233}
1234
1235fn derived_picker_id(parent: ElementId, tag: u64, value: u64) -> ElementId {
1236 let mut hash = parent.as_u64() ^ tag ^ value.wrapping_mul(0x9e37_79b9_7f4a_7c15);
1237 hash ^= hash >> 30;
1238 hash = hash.wrapping_mul(0xbf58_476d_1ce4_e5b9);
1239 hash ^= hash >> 27;
1240 hash = hash.wrapping_mul(0x94d0_49bb_1331_11eb);
1241 hash ^= hash >> 31;
1242 if hash == parent.as_u64() {
1243 hash ^= tag;
1244 }
1245 ElementId::new(hash)
1246}
1247
1248fn finite_clamped(value: f32, minimum: f32, maximum: f32, fallback: f32) -> f32 {
1249 if value.is_finite() {
1250 value.clamp(minimum, maximum)
1251 } else {
1252 fallback.clamp(minimum, maximum)
1253 }
1254}
1255
1256#[cfg(test)]
1257mod tests {
1258 use super::*;
1259 use crate::{Application, Color, View, WindowOptions, text, text_input};
1260
1261 fn item(label: &str) -> PickerItem<usize> {
1262 PickerItem::new(label, 0)
1263 }
1264
1265 #[test]
1266 fn fuzzy_matching_ranks_prefixes_and_retains_unicode_safe_label_ranges() {
1267 let mut picker = PickerState::new([
1268 item("Close File"),
1269 item("Open File"),
1270 item("Öffnen").keywords("open file"),
1271 ])
1272 .unwrap();
1273
1274 assert!(picker.set_query("of"));
1275 let first = picker.match_at(0).unwrap();
1276 assert_eq!(first.item().label().as_ref(), "Open File");
1277 assert_eq!(first.label_ranges(), [0..1, 5..6]);
1278
1279 picker.set_query("öff");
1280 let first = picker.match_at(0).unwrap();
1281 assert_eq!(first.item().label().as_ref(), "Öffnen");
1282 assert_eq!(first.label_ranges().len(), 1);
1283 assert_eq!(first.label_ranges()[0], 0..4);
1284 assert!(
1285 first.label_ranges().iter().all(|range| first
1286 .item()
1287 .label()
1288 .is_char_boundary(range.start)
1289 && first.item().label().is_char_boundary(range.end))
1290 );
1291 }
1292
1293 #[test]
1294 fn metadata_matches_without_manufacturing_label_highlights() {
1295 let mut picker = PickerState::new([
1296 item("Preferences").keywords("settings xyzalias"),
1297 item("Settings Sync"),
1298 ])
1299 .unwrap();
1300 picker.set_query("xyzalias");
1301
1302 assert_eq!(picker.result_count(), 1);
1303 assert_eq!(
1304 picker.match_at(0).unwrap().item().label().as_ref(),
1305 "Preferences"
1306 );
1307 assert!(picker.match_at(0).unwrap().label_ranges().is_empty());
1308 }
1309
1310 #[test]
1311 fn filter_none_preserves_externally_filtered_source_order() {
1312 let mut picker = PickerState::new([
1313 item("Remote second"),
1314 item("Remote first"),
1315 item("Remote third"),
1316 ])
1317 .unwrap();
1318 assert!(picker.set_filter_mode(PickerFilterMode::None));
1319 assert!(picker.set_query("does not match locally"));
1320
1321 assert_eq!(picker.result_count(), 3);
1322 assert_eq!(picker.total_match_count(), 3);
1323 assert_eq!(
1324 picker.match_at(0).unwrap().item().label().as_ref(),
1325 "Remote second"
1326 );
1327 assert_eq!(picker.match_at(0).unwrap().score(), 0);
1328 assert!(picker.match_at(0).unwrap().label_ranges().is_empty());
1329 assert!(!picker.set_filter_mode(PickerFilterMode::None));
1330 assert!(picker.set_filter_mode(PickerFilterMode::Fuzzy));
1331 assert_eq!(picker.result_count(), 0);
1332 }
1333
1334 #[test]
1335 fn navigation_skips_disabled_results_wraps_and_reveals_selection() {
1336 let items = (0..20).map(|index| {
1337 PickerItem::new(format!("Command {index:02}"), index).disabled(index == 1)
1338 });
1339 let mut picker = PickerState::new(items).unwrap();
1340 picker
1341 .list
1342 .set_viewport_height(picker.layout.row_height * 3.0);
1343
1344 assert_eq!(picker.selected_result_index(), Some(0));
1345 assert!(picker.select_next());
1346 assert_eq!(picker.selected_result_index(), Some(2));
1347 assert!(picker.select_last());
1348 assert_eq!(picker.selected_value(), Some(&19));
1349 assert!(picker.list.scroll_offset() > 0.0);
1350 assert!(picker.select_next());
1351 assert_eq!(picker.selected_result_index(), Some(0));
1352 assert_eq!(picker.list.scroll_offset(), 0.0);
1353 }
1354
1355 #[test]
1356 fn reset_restores_empty_query_source_order_and_initial_selection() {
1357 let mut picker = PickerState::new([
1358 PickerItem::new("Alpha", 1),
1359 PickerItem::new("Beta", 2),
1360 PickerItem::new("Gamma", 3),
1361 ])
1362 .unwrap();
1363 picker.list.set_viewport_height(picker.layout.row_height);
1364 picker.set_query("gamma");
1365 assert_eq!(picker.selected_value(), Some(&3));
1366
1367 assert!(picker.reset());
1368 assert!(picker.query().is_empty());
1369 assert_eq!(picker.match_at(0).unwrap().item().label().as_ref(), "Alpha");
1370 assert_eq!(picker.selected_value(), Some(&1));
1371 assert_eq!(picker.list.scroll_offset(), 0.0);
1372 }
1373
1374 #[test]
1375 fn queries_and_ranked_results_are_hard_bounded() {
1376 let items = (0..MAX_PICKER_RESULTS + 10)
1377 .map(|index| PickerItem::new(format!("command {index}"), index));
1378 let mut picker = PickerState::new(items).unwrap();
1379 assert_eq!(picker.result_count(), MAX_PICKER_RESULTS);
1380 assert_eq!(picker.total_match_count(), MAX_PICKER_RESULTS + 10);
1381 assert!(picker.results_truncated());
1382
1383 let query = "🦀".repeat(MAX_PICKER_QUERY_GRAPHEMES + 10);
1384 picker.set_query(&query);
1385 assert_eq!(
1386 picker.query().graphemes(true).count(),
1387 MAX_PICKER_QUERY_GRAPHEMES
1388 );
1389
1390 let pathological_grapheme = format!("a{}", "\u{301}".repeat(MAX_PICKER_QUERY_BYTES));
1391 picker.set_query(&pathological_grapheme);
1392 assert!(picker.query().len() <= MAX_PICKER_QUERY_BYTES);
1393 assert!(pathological_grapheme.is_char_boundary(picker.query().len()));
1394 }
1395
1396 #[test]
1397 fn source_item_and_text_budgets_fail_before_unbounded_retention() {
1398 let too_many = (0..=MAX_PICKER_ITEMS).map(|index| PickerItem::new("x", index));
1399 assert_eq!(
1400 PickerState::new(too_many).unwrap_err(),
1401 PickerError::TooManyItems {
1402 limit: MAX_PICKER_ITEMS
1403 }
1404 );
1405
1406 let oversized = "x".repeat(MAX_PICKER_ITEM_TEXT_BYTES + 1);
1407 assert_eq!(
1408 PickerState::new([PickerItem::new(oversized, ())]).unwrap_err(),
1409 PickerError::ItemTextTooLong {
1410 index: 0,
1411 bytes: MAX_PICKER_ITEM_TEXT_BYTES + 1,
1412 limit: MAX_PICKER_ITEM_TEXT_BYTES,
1413 }
1414 );
1415
1416 assert_eq!(
1417 PickerState::new([
1418 PickerItem::new("Alpha", ()).id("duplicate"),
1419 PickerItem::new("Beta", ()).id("duplicate"),
1420 ])
1421 .unwrap_err(),
1422 PickerError::DuplicateId {
1423 id: "duplicate".into(),
1424 }
1425 );
1426 }
1427
1428 #[test]
1429 fn picker_bindings_are_scoped_and_cover_navigation_and_confirmation() {
1430 let bindings = picker_key_bindings();
1431 assert_eq!(bindings.len(), 7);
1432 assert!(
1433 bindings.iter().all(
1434 |binding| binding.context_predicate().is_some_and(|context| context
1435 .depth_of(&[crate::KeyContext::parse("Picker").unwrap()])
1436 .is_some())
1437 )
1438 );
1439 assert!(
1440 bindings
1441 .iter()
1442 .any(|binding| binding.action().downcast_ref::<PickerConfirm>().is_some())
1443 );
1444 }
1445
1446 struct PickerView {
1447 picker: PickerState<usize>,
1448 activated: Option<usize>,
1449 }
1450
1451 impl Default for PickerView {
1452 fn default() -> Self {
1453 Self {
1454 picker: PickerState::new([
1455 PickerItem::new("Alpha", 1),
1456 PickerItem::new("Beta", 2),
1457 PickerItem::new("Gamma", 3),
1458 ])
1459 .unwrap(),
1460 activated: None,
1461 }
1462 }
1463 }
1464
1465 impl PickerView {
1466 fn picker(view: &mut Self) -> &mut PickerState<usize> {
1467 &mut view.picker
1468 }
1469 }
1470
1471 impl View for PickerView {
1472 fn render(&mut self, cx: &mut ViewContext<'_, Self>) -> impl IntoElement {
1473 let query = self.picker.query().clone();
1474 self.picker
1475 .element(
1476 cx,
1477 "picker",
1478 "Test picker",
1479 Self::picker,
1480 text_input(query).h(42.0).bg(Color::rgb8(3, 4, 5)),
1481 div()
1482 .h(48.0)
1483 .bg(Color::rgb8(6, 7, 8))
1484 .child("Nothing found"),
1485 |matched| {
1486 div()
1487 .bg(if matched.is_selected() {
1488 Color::rgb8(9, 10, 11)
1489 } else {
1490 Color::TRANSPARENT
1491 })
1492 .child(text(matched.item().label().clone()))
1493 },
1494 |view, value, cx| {
1495 view.activated = Some(value);
1496 cx.invalidate();
1497 },
1498 )
1499 .w(280.0)
1500 .bg(Color::rgb8(12, 13, 14))
1501 }
1502 }
1503
1504 #[test]
1505 fn unstyled_picker_uses_caller_elements_and_existing_input_action_paths() {
1506 let (mut cx, view) = Application::new()
1507 .bind_keys(picker_key_bindings())
1508 .into_test_context(WindowOptions::default(), PickerView::default())
1509 .unwrap();
1510 let window = view.window_handle();
1511 assert_eq!(
1512 cx.focused(window).unwrap(),
1513 Some(PickerState::<usize>::input_focus_handle("picker").id())
1514 );
1515
1516 cx.simulate_keystrokes(window, "g enter").unwrap();
1517 assert_eq!(
1518 cx.read(view, |view| view.picker.query().clone())
1519 .unwrap()
1520 .as_ref(),
1521 "g"
1522 );
1523 assert_eq!(cx.read(view, |view| view.activated).unwrap(), Some(3));
1524
1525 let renders = cx.render_count(window).unwrap();
1526 cx.run_until_idle().unwrap();
1527 assert_eq!(cx.render_count(window).unwrap(), renders);
1528 }
1529
1530 #[test]
1531 fn layout_dimensions_are_sanitized_without_unbounded_visible_mounts() {
1532 let layout = PickerLayout::default()
1533 .row_height(-20.0)
1534 .max_visible_rows(usize::MAX);
1535 assert_eq!(layout.row_height, 24.0);
1536 assert_eq!(layout.max_visible_rows, MAX_VISIBLE_PICKER_ROWS);
1537 }
1538}