guise/data/

tree.rs

//! `TreeView` — a hierarchical list with expandable branches (gpui entity).
//!
//! Nodes are plain [`TreeNode`] values; the view owns expansion state and a
//! single selection, and emits [`TreeViewEvent`] on select / toggle / activate.
//! Branches show a rotating chevron and rows indent per depth; arrow keys walk
//! the visible rows (right expands or steps into a branch, left collapses or
//! steps to the parent) and Enter activates the selection.
//!
//! ```ignore
//! let tree = cx.new(|cx| {
//!     TreeView::new(cx)
//!         .nodes(vec![
//!             TreeNode::new("src", "src")
//!                 .child(TreeNode::new("main", "main.rs"))
//!                 .child(TreeNode::new("lib", "lib.rs")),
//!             TreeNode::new("readme", "README.md"),
//!         ])
//!         .expand("src")
//! });
//! cx.subscribe(&tree, |_this, _tree, event: &TreeViewEvent, _cx| match event {
//!     TreeViewEvent::Selected(id) => println!("selected {id}"),
//!     TreeViewEvent::Toggled(id, open) => println!("{id} expanded: {open}"),
//!     TreeViewEvent::Activated(id) => println!("activated {id}"),
//! })
//! .detach();
//! ```

use std::collections::HashSet;
use std::ops::Range;

use gpui::prelude::*;
use gpui::{
    div, px, uniform_list, AnyElement, ClickEvent, Context, EventEmitter, FocusHandle, IntoElement,
    KeyDownEvent, MouseButton, MouseDownEvent, Pixels, Point, ScrollStrategy, SharedString,
    UniformListScrollHandle, Window,
};

use crate::devtools::Probed;
use crate::icon::{Glyph, Icon, IconName};
use crate::reactive::Signal;
use crate::theme::{theme, Size};

/// One node in a [`TreeView`]. A node with children is a branch (chevron +
/// folder icon); a node without children is a leaf (file icon).
#[derive(Debug, Clone)]
pub struct TreeNode {
    /// Stable identifier — carried by every [`TreeViewEvent`].
    pub id: SharedString,
    /// The text shown on the row.
    pub label: SharedString,
    /// Optional glyph shown before the label. Defaults to a folder/file glyph
    /// picked by branch/leaf.
    pub icon: Option<IconName>,
    /// Child nodes; empty means leaf.
    pub children: Vec<TreeNode>,
}

impl TreeNode {
    pub fn new(id: impl Into<SharedString>, label: impl Into<SharedString>) -> Self {
        TreeNode {
            id: id.into(),
            label: label.into(),
            icon: None,
            children: Vec::new(),
        }
    }

    /// Override the row glyph (defaults to folder/file by branch/leaf).
    pub fn icon(mut self, icon: IconName) -> Self {
        self.icon = Some(icon);
        self
    }

    /// Append one child node.
    pub fn child(mut self, child: TreeNode) -> Self {
        self.children.push(child);
        self
    }

    /// Append several child nodes.
    pub fn children(mut self, children: impl IntoIterator<Item = TreeNode>) -> Self {
        self.children.extend(children);
        self
    }

    /// A node with no children.
    pub fn is_leaf(&self) -> bool {
        self.children.is_empty()
    }
}

/// Emitted by [`TreeView`]. All variants carry the node id.
#[derive(Debug, Clone)]
pub enum TreeViewEvent {
    /// The selection moved to this node.
    Selected(SharedString),
    /// A branch was expanded (`true`) or collapsed (`false`).
    Toggled(SharedString, bool),
    /// Enter or double-click on a node.
    Activated(SharedString),
    /// A node was right-clicked, with the window coordinates of the click.
    ///
    /// Pass the point straight to [`ContextMenu::show`](crate::ContextMenu::show).
    /// The node is selected first, so a menu built from the current selection
    /// and one built from this id agree.
    ContextMenu(SharedString, Point<Pixels>),
}

/// One visible (not hidden by a collapsed ancestor) row, in paint order.
#[derive(Debug, Clone, PartialEq)]
struct VisibleRow {
    id: SharedString,
    label: SharedString,
    icon: Option<IconName>,
    depth: usize,
    is_branch: bool,
    expanded: bool,
}

/// Depth-first flatten of the nodes whose ancestors are all expanded.
fn flatten_visible(
    nodes: &[TreeNode],
    expanded: &HashSet<SharedString>,
    depth: usize,
    out: &mut Vec<VisibleRow>,
) {
    for node in nodes {
        let is_branch = !node.children.is_empty();
        let is_expanded = is_branch && expanded.contains(&node.id);
        out.push(VisibleRow {
            id: node.id.clone(),
            label: node.label.clone(),
            icon: node.icon,
            depth,
            is_branch,
            expanded: is_expanded,
        });
        if is_expanded {
            flatten_visible(&node.children, expanded, depth + 1, out);
        }
    }
}

/// The visible rows for a node list + expanded set.
fn visible(nodes: &[TreeNode], expanded: &HashSet<SharedString>) -> Vec<VisibleRow> {
    let mut out = Vec::new();
    flatten_visible(nodes, expanded, 0, &mut out);
    out
}

/// Every branch id in the tree (for `default_expanded`).
fn collect_branch_ids(nodes: &[TreeNode], out: &mut HashSet<SharedString>) {
    for node in nodes {
        if !node.children.is_empty() {
            out.insert(node.id.clone());
            collect_branch_ids(&node.children, out);
        }
    }
}

/// What a horizontal arrow key does, in visible-row terms.
#[derive(Debug, Clone, Copy, PartialEq, Eq)]
enum KeyMove {
    /// Move the selection to this visible index.
    To(usize),
    /// Expand (`true`) or collapse (`false`) the branch at this index.
    Set(usize, bool),
    /// Nothing to do.
    None,
}

/// Down-arrow target: first row when nothing is selected, else clamp below.
fn step_down(len: usize, current: Option<usize>) -> Option<usize> {
    match (len, current) {
        (0, _) => None,
        (_, None) => Some(0),
        (len, Some(i)) => Some((i + 1).min(len - 1)),
    }
}

/// Up-arrow target: last row when nothing is selected, else clamp above.
fn step_up(len: usize, current: Option<usize>) -> Option<usize> {
    match (len, current) {
        (0, _) => None,
        (len, None) => Some(len - 1),
        (_, Some(i)) => Some(i.saturating_sub(1)),
    }
}

/// Right arrow: expand a collapsed branch, step into an expanded one.
fn step_right(rows: &[VisibleRow], current: usize) -> KeyMove {
    let Some(row) = rows.get(current) else {
        return KeyMove::None;
    };
    if !row.is_branch {
        return KeyMove::None;
    }
    if !row.expanded {
        return KeyMove::Set(current, true);
    }
    match rows.get(current + 1) {
        Some(next) if next.depth == row.depth + 1 => KeyMove::To(current + 1),
        _ => KeyMove::None,
    }
}

/// Left arrow: collapse an expanded branch, else step to the parent.
fn step_left(rows: &[VisibleRow], current: usize) -> KeyMove {
    let Some(row) = rows.get(current) else {
        return KeyMove::None;
    };
    if row.is_branch && row.expanded {
        return KeyMove::Set(current, false);
    }
    if row.depth == 0 {
        return KeyMove::None;
    }
    // The parent is the nearest preceding row one level up.
    (0..current)
        .rev()
        .find(|&i| rows[i].depth + 1 == row.depth)
        .map(KeyMove::To)
        .unwrap_or(KeyMove::None)
}

/// A hierarchical list. Create with `cx.new(|cx| TreeView::new(cx).nodes(...))`.
pub struct TreeView {
    nodes: Vec<TreeNode>,
    expanded: HashSet<SharedString>,
    selected: Option<SharedString>,
    expand_all: bool,
    focus: FocusHandle,
    height: Option<f32>,
    scroll: UniformListScrollHandle,
}

impl EventEmitter<TreeViewEvent> for TreeView {}

impl TreeView {
    pub fn new(cx: &mut Context<Self>) -> Self {
        TreeView {
            nodes: Vec::new(),
            expanded: HashSet::new(),
            selected: None,
            expand_all: false,
            focus: cx.focus_handle(),
            height: None,
            scroll: UniformListScrollHandle::new(),
        }
    }

    /// Fix the view height (px) and virtualize: only the rows in view are
    /// built each frame, so huge trees stay cheap. Keyboard selection scrolls
    /// into view.
    pub fn height(mut self, height: f32) -> Self {
        self.height = Some(height.max(0.0));
        self
    }

    /// Set the tree data.
    pub fn nodes(mut self, nodes: Vec<TreeNode>) -> Self {
        self.nodes = nodes;
        if self.expand_all {
            collect_branch_ids(&self.nodes, &mut self.expanded);
        }
        self
    }

    /// Drive the tree data from a `Signal<Vec<TreeNode>>`: the view adopts the
    /// signal's nodes now and re-reads them on every signal change. Expansion
    /// and selection survive data updates (they are keyed by node id).
    pub fn bind_nodes(mut self, signal: &Signal<Vec<TreeNode>>, cx: &mut Context<Self>) -> Self {
        self.nodes = signal.get(cx);
        if self.expand_all {
            collect_branch_ids(&self.nodes, &mut self.expanded);
        }
        cx.observe(signal.entity(), |this, observed, cx| {
            this.nodes = observed.read(cx).clone();
            // `default_expanded(true)` promises expand-all for nodes assigned
            // later too, so new branches join the expanded set here.
            if this.expand_all {
                collect_branch_ids(&this.nodes, &mut this.expanded);
            }
            cx.notify();
        })
        .detach();
        self
    }

    /// Expand the branch with this id (construction-time; users toggle live).
    pub fn expand(mut self, id: impl Into<SharedString>) -> Self {
        self.expanded.insert(id.into());
        self
    }

    /// Collapse the branch with this id.
    pub fn collapse(mut self, id: impl Into<SharedString>) -> Self {
        self.expanded.remove(&id.into());
        self
    }

    /// Start with every branch expanded. Applies to the current nodes and to
    /// nodes assigned later via [`nodes`](Self::nodes) / [`bind_nodes`](Self::bind_nodes).
    pub fn default_expanded(mut self, expanded: bool) -> Self {
        self.expand_all = expanded;
        if expanded {
            collect_branch_ids(&self.nodes, &mut self.expanded);
        }
        self
    }

    /// The ids of every expanded branch, sorted for determinism.
    pub fn expanded_ids(&self) -> Vec<SharedString> {
        let mut ids: Vec<SharedString> = self.expanded.iter().cloned().collect();
        ids.sort();
        ids
    }

    /// The id of the selected node, if any.
    pub fn selected_id(&self) -> Option<SharedString> {
        self.selected.clone()
    }

    /// Move the selection, emit, repaint. No-op when already selected.
    fn select(&mut self, id: SharedString, cx: &mut Context<Self>) {
        if self.selected.as_ref() == Some(&id) {
            return;
        }
        self.selected = Some(id.clone());
        cx.emit(TreeViewEvent::Selected(id));
        cx.notify();
    }

    /// Flip a branch open/closed.
    fn toggle(&mut self, id: SharedString, cx: &mut Context<Self>) {
        let open = !self.expanded.contains(&id);
        self.set_expanded(id, open, cx);
    }

    /// Set a branch's expansion, emit, repaint. No-op when unchanged.
    fn set_expanded(&mut self, id: SharedString, open: bool, cx: &mut Context<Self>) {
        let changed = if open {
            self.expanded.insert(id.clone())
        } else {
            self.expanded.remove(&id)
        };
        if changed {
            cx.emit(TreeViewEvent::Toggled(id, open));
            cx.notify();
        }
    }

    /// Carry out a [`KeyMove`] against the current visible rows.
    fn apply(&mut self, mv: KeyMove, rows: &[VisibleRow], cx: &mut Context<Self>) {
        match mv {
            KeyMove::To(i) => {
                self.select(rows[i].id.clone(), cx);
                self.reveal(i);
            }
            KeyMove::Set(i, open) => self.set_expanded(rows[i].id.clone(), open, cx),
            KeyMove::None => {}
        }
    }

    /// Scroll the visible row at `i` into view (virtualized mode only).
    fn reveal(&mut self, i: usize) {
        if self.height.is_some() {
            self.scroll.scroll_to_item(i, ScrollStrategy::Top);
        }
    }

    fn on_key(&mut self, event: &KeyDownEvent, _window: &mut Window, cx: &mut Context<Self>) {
        let rows = visible(&self.nodes, &self.expanded);
        if rows.is_empty() {
            return;
        }
        let current = self
            .selected
            .as_ref()
            .and_then(|id| rows.iter().position(|row| &row.id == id));

        let handled = match event.keystroke.key.as_str() {
            "down" => {
                if let Some(i) = step_down(rows.len(), current) {
                    self.select(rows[i].id.clone(), cx);
                    self.reveal(i);
                }
                true
            }
            "up" => {
                if let Some(i) = step_up(rows.len(), current) {
                    self.select(rows[i].id.clone(), cx);
                    self.reveal(i);
                }
                true
            }
            "right" => match current {
                Some(i) => {
                    self.apply(step_right(&rows, i), &rows, cx);
                    true
                }
                None => false,
            },
            "left" => match current {
                Some(i) => {
                    self.apply(step_left(&rows, i), &rows, cx);
                    true
                }
                None => false,
            },
            "enter" => match self.selected.clone() {
                Some(id) => {
                    cx.emit(TreeViewEvent::Activated(id));
                    true
                }
                None => false,
            },
            _ => false,
        };
        if handled {
            cx.stop_propagation();
        }
    }
}

impl TreeView {
    /// Build the visible rows in `range` (the whole tree when not
    /// virtualized, just the viewport slice when it is).
    fn render_rows(&mut self, range: Range<usize>, cx: &mut Context<Self>) -> Vec<AnyElement> {
        let t = theme(cx);
        let text = t.text().hsla();
        let dimmed = t.dimmed().hsla();
        let accent = t.primary().hsla();
        let surface_hover = t.surface_hover().hsla();
        let selected_bg = t.primary().alpha(0.12);
        let indent = t.spacing(Size::Md);
        let radius = t.radius(Size::Sm);
        let font = t.font_size(Size::Sm);

        let rows = visible(&self.nodes, &self.expanded);
        let selected = self.selected.clone();

        let mut out = Vec::with_capacity(range.len());
        for i in range {
            let Some(row) = rows.get(i) else { break };
            let is_selected = selected.as_ref() == Some(&row.id);
            let is_branch = row.is_branch;
            let id = row.id.clone();
            let menu_id = row.id.clone();
            let hover_bg = if is_selected {
                selected_bg
            } else {
                surface_hover
            };

            // Fixed-width chevron cell so branch and leaf labels align.
            let mut chevron = div()
                .w(px(16.0))
                .flex()
                .items_center()
                .justify_center()
                .text_color(dimmed);
            if is_branch {
                chevron = chevron.child(Glyph::from(if row.expanded {
                    IconName::ChevronDown
                } else {
                    IconName::ChevronRight
                }));
            }

            let fallback = if is_branch {
                IconName::Menu
            } else {
                IconName::Dot
            };
            let glyph = row.icon.unwrap_or(fallback);
            let icon = div()
                .text_color(if is_selected { accent } else { dimmed })
                .child(Icon::new(glyph).size(Size::Xs));

            let mut el = div()
                .id(("guise-tree-row", i))
                .flex()
                .items_center()
                .gap(px(6.0))
                .pl(px(6.0 + indent * row.depth as f32))
                .pr(px(8.0))
                .py(px(4.0))
                .rounded(px(radius))
                .text_size(px(font))
                .text_color(text)
                .hover(move |s| s.bg(hover_bg))
                .child(chevron)
                .child(icon)
                .child(row.label.clone())
                .on_click(cx.listener(move |this, ev: &ClickEvent, _window, cx| {
                    this.select(id.clone(), cx);
                    if ev.click_count() > 1 {
                        cx.emit(TreeViewEvent::Activated(id.clone()));
                    } else if is_branch {
                        this.toggle(id.clone(), cx);
                    }
                }))
                .on_mouse_down(
                    MouseButton::Right,
                    cx.listener(move |this, ev: &MouseDownEvent, _window, cx| {
                        // Select first: right-clicking a row the user can see
                        // highlighted is what every file manager does, and it
                        // keeps a selection-driven menu honest.
                        this.select(menu_id.clone(), cx);
                        cx.emit(TreeViewEvent::ContextMenu(menu_id.clone(), ev.position));
                        cx.stop_propagation();
                    }),
                );
            if is_selected {
                el = el.bg(selected_bg);
            }
            out.push(el.into_any_element());
        }
        out
    }
}

impl Render for TreeView {
    fn render(&mut self, _window: &mut Window, cx: &mut Context<Self>) -> impl IntoElement {
        let count = visible(&self.nodes, &self.expanded).len();

        let root = div()
            .id("guise-treeview")
            .track_focus(&self.focus)
            .on_key_down(cx.listener(Self::on_key))
            .on_mouse_down(
                MouseButton::Left,
                cx.listener(|this, _ev, window, cx| {
                    window.focus(&this.focus);
                    cx.notify();
                }),
            )
            .flex()
            .flex_col();

        let element = if let Some(height) = self.height {
            root.child(
                uniform_list(
                    "guise-treeview-rows",
                    count,
                    cx.processor(|this, range: Range<usize>, _window, cx| {
                        this.render_rows(range, cx)
                    }),
                )
                .h(px(height))
                .w_full()
                .track_scroll(self.scroll.clone()),
            )
        } else {
            root.gap(px(2.0)).children(self.render_rows(0..count, cx))
        };

        element.probe("TreeView")
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    fn sample() -> Vec<TreeNode> {
        vec![
            TreeNode::new("src", "src")
                .child(TreeNode::new("main", "main.rs"))
                .child(TreeNode::new("data", "data").child(TreeNode::new("tree", "tree.rs"))),
            TreeNode::new("readme", "README.md"),
        ]
    }

    fn expanded(ids: &[&'static str]) -> HashSet<SharedString> {
        ids.iter().map(|id| SharedString::from(*id)).collect()
    }

    fn ids(rows: &[VisibleRow]) -> Vec<&str> {
        rows.iter().map(|row| row.id.as_ref()).collect()
    }

    #[test]
    fn collapsed_tree_shows_only_roots() {
        let rows = visible(&sample(), &expanded(&[]));
        assert_eq!(ids(&rows), ["src", "readme"]);
        assert!(rows[0].is_branch && !rows[0].expanded);
        assert!(!rows[1].is_branch);
    }

    #[test]
    fn expanded_branches_flatten_depth_first() {
        let rows = visible(&sample(), &expanded(&["src", "data"]));
        assert_eq!(ids(&rows), ["src", "main", "data", "tree", "readme"]);
        let depths: Vec<usize> = rows.iter().map(|row| row.depth).collect();
        assert_eq!(depths, [0, 1, 1, 2, 0]);
        assert!(rows[2].expanded);
    }

    #[test]
    fn collapsed_parent_hides_expanded_descendants() {
        // "data" is expanded but its parent "src" is not, so it stays hidden.
        let rows = visible(&sample(), &expanded(&["data"]));
        assert_eq!(ids(&rows), ["src", "readme"]);
    }

    #[test]
    fn up_and_down_clamp_at_the_edges() {
        assert_eq!(step_down(3, None), Some(0));
        assert_eq!(step_down(3, Some(1)), Some(2));
        assert_eq!(step_down(3, Some(2)), Some(2));
        assert_eq!(step_up(3, None), Some(2));
        assert_eq!(step_up(3, Some(1)), Some(0));
        assert_eq!(step_up(3, Some(0)), Some(0));
        assert_eq!(step_down(0, None), None);
        assert_eq!(step_up(0, Some(1)), None);
    }

    #[test]
    fn right_expands_then_steps_into_the_branch() {
        let closed = visible(&sample(), &expanded(&[]));
        assert_eq!(step_right(&closed, 0), KeyMove::Set(0, true));

        let open = visible(&sample(), &expanded(&["src"]));
        assert_eq!(step_right(&open, 0), KeyMove::To(1));
        // Leaf rows don't react to right.
        assert_eq!(step_right(&open, 1), KeyMove::None);
    }

    #[test]
    fn left_collapses_then_walks_to_the_parent() {
        let rows = visible(&sample(), &expanded(&["src", "data"]));
        // Expanded branch collapses in place.
        assert_eq!(step_left(&rows, 0), KeyMove::Set(0, false));
        // A child moves to its parent, skipping same-depth siblings.
        assert_eq!(step_left(&rows, 1), KeyMove::To(0));
        assert_eq!(step_left(&rows, 3), KeyMove::To(2));
        // A collapsed root has nowhere to go.
        assert_eq!(step_left(&rows, 4), KeyMove::None);
    }

    #[test]
    fn branch_ids_cover_nested_branches_only() {
        let mut out = HashSet::new();
        collect_branch_ids(&sample(), &mut out);
        assert_eq!(out, expanded(&["src", "data"]));
    }
}