open-gpui 0.2.0

//! Accessibility support, provided by [AccessKit][accesskit].
//!
//! There are user-facing guide-level docs [here](crate::_accessibility).
//!
//! ## Architecture
//!
//! ```text
//!                              ┌────────────────────────────────┐   ┌─────────────────────┐
//!                           ┌─▶│ AccessKit Adapter (MacOS)      │◀─▶│ MacOS System APIs   │
//!                           │  └────────────────────────────────┘   └─────────────────────┘
//!                           │
//! ┌──────┐   ┌───────────┐  │  ┌────────────────────────────────┐   ┌─────────────────────┐
//! │ GPUI │◀─▶│ AccessKit │◀─┼─▶│ AccessKit Adapter (Windows)    │◀─▶│ Windows System APIs │
//! └──────┘   └───────────┘  │  └────────────────────────────────┘   └─────────────────────┘
//!                           │
//!                           │  ┌────────────────────────────────┐   ┌─────────────────────┐
//!                           └─▶│ AccessKit Adapter (Linux)      │◀─▶│ dbus                │
//!                              └────────────────────────────────┘   └─────────────────────┘
//! ```
//!
//! In order for GPUI apps to be usable for people using assistive technology,
//! we must do a few things:
//! - Inform the system when the UI changes meaningfully. This includes:
//!   - Reporting new/removed/changed UI elements
//!   - *Not* reporting irrelevant UI changes, e.g. an invisible `div()` being
//!     added.
//!   - Reporting the appearance and capabilities of each UI element. For example:
//!     - What does this piece of text say?
//!     - How far along is this progress bar?
//!     - Can this node be focused?
//!     - Can this node have a value directly assigned? (e.g. a slider)
//! - Allowing the system to interact with the UI by dispatching actions to
//!   nodes. Note that AccessKit has its own [`Action`] type, which is not the
//!   [`crate::Action`] trait.
//! - Activate and deactivate accessibility features when requested by the
//!   system.
//!
//! Activating and deactivating at the right time is trivial, so I won't go into
//! detail here. The other two are almost orthogonal in implementation.
//!
//! The state for both lives in the [`A11y`] struct in this module.
//!
//! ### Reporting UI changes
//!
//! Every frame, we build a [`TreeUpdate`] and send it to the platform-specific
//! adapter. A [`TreeUpdate`] is a representation of a subset of the UI tree.
//! When the adapter receives the update, it diffs it against the previous
//! update, and calls platform-specific APIs to inform screen readers about the
//! changes. Nodes may have been created, destroyed, or updated.
//!
//! Each node has an ID, and this ID *should* be stable across frames. If a
//! node's ID changes, then, from AccessKit's point of view, it is a different
//! node.
//!
//! We derive the node ID from the [`GlobalElementId`] in
//! [`GlobalElementId::accesskit_node_id`]. Nodes without [`GlobalElementId`]s
//! cannot produce an AccessKit [`NodeId`], and so are not included in the
//! accessibility tree. We try to warn when using accessibility APIs on
//! [`div()`] without setting an ID.
//!
//! This all happens in [`Drawable::prepaint`]. The [`A11y`] struct maintains a
//! stack of nodes during prepainting, which we can use to calculate the
//! [`NodeId`]s, and record parent-child relationships. Once all [`Element`]s in
//! a frame have been prepainted, we send the resulting [`TreeUpdate`] object to
//! the adapter and the screen reader can announce the changes.
//!
//! ### Responding to actions
//!  
//! On adapter creation, we provide a callback to the adapter, which can be used
//! to dispatch actions. This callback forwards to [`A11y::action_listeners`], a
//! mapping from [`NodeId`]s to action handlers (basically just `Box<dyn
//! Fn()>`).
//!
//! This is populated in:
//! - [`Window::on_a11y_action`], which is called by:
//! - [`Interactivity::paint`], which is called by:
//! - [`InteractiveElement::on_a11y_action`], which is a public-facing API
//!
//! These are cleared at the start of a frame, and re-populated during painting.
//!
//! [`Element`]: crate::Element
//! [`GlobalElementId`]: crate::GlobalElementId
//! [`div()`]: crate::div
//! [`Interactivity::paint`]: crate::Interactivity::paint
//! [`InteractiveElement::on_a11y_action`]: crate::InteractiveElement::on_a11y_action
//! [`NodeId`]: accesskit::NodeId
//! [`Drawable::prepaint`]: crate::Drawable::prepaint

use crate::{App, Bounds, FocusId, Pixels, Window};
use accesskit::{Action, NodeId, TreeUpdate};
use open_gpui_collections::{FxHashMap, FxHashSet};
use smallvec::SmallVec;
use std::sync::{
    Arc,
    atomic::{AtomicBool, Ordering},
};

/// The fixed AccessKit node ID used for the root of every window's a11y tree.
pub(crate) const ROOT_NODE_ID: NodeId = NodeId(0);

/// A listener for an accessibility action on a specific node.
pub(crate) type A11yActionListener =
    Box<dyn FnMut(Option<&accesskit::ActionData>, &mut Window, &mut App) + 'static>;

/// Per-window accessibility state.
///
/// Manages the AccessKit tree that is built each frame and the mappings
/// needed to dispatch incoming action requests back to the right elements.
pub(crate) struct A11y {
    /// Whether accessibility has been [forcibly disabled] for this window.
    ///
    /// [forcibly disabled]: crate::Application::new_inaccessible
    force_disabled: bool,
    /// Whether a11y features have been requested by the system.
    ///
    /// Updated by AccessKit using callbacks provided to the adapter. Can change
    /// halfway through a frame.
    active_flag: Arc<AtomicBool>,
    /// Whether a11y features are active for *this specific frame*.
    ///
    /// At the start of each frame, we load [`Self::active_flag`] (using
    /// [`Self::sync_active_flag`]) and use this to determine whether we
    /// should construct a [`TreeUpdate`] for this frame. It's important that
    /// this value is stable within a frame, because the builder API exposed by
    /// this type maintains a stack of nodes and each must be pushed and popped
    /// exactly once.
    ///
    /// At the end of the frame, we re-call [`Self::sync_active_flag`] to
    /// determine whether we should actually send the finished [`TreeUpdate`].
    active_this_frame: bool,
    pub(crate) nodes: A11yNodeBuilder,
    pub(crate) focus_ids: FxHashMap<NodeId, FocusId>,
    pub(crate) node_bounds: FxHashMap<NodeId, Bounds<Pixels>>,
    pub(crate) action_listeners: FxHashMap<NodeId, Vec<(Action, A11yActionListener)>>,
}

impl A11y {
    pub(crate) fn new(active_flag: Arc<AtomicBool>, force_disabled: bool) -> Self {
        Self {
            force_disabled,
            active_flag,
            active_this_frame: false,
            nodes: A11yNodeBuilder::new(),
            focus_ids: FxHashMap::default(),
            node_bounds: FxHashMap::default(),
            action_listeners: FxHashMap::default(),
        }
    }

    /// Ensures that [`Self::is_active`] returns up to date information.
    ///
    /// See the docs for [`Self::active_flag`] and [`Self::active_this_frame`]
    /// for more commentary.
    pub(crate) fn sync_active_flag(&mut self) {
        self.active_this_frame = !self.force_disabled && self.active_flag.load(Ordering::SeqCst);
    }

    pub(crate) fn is_active(&self) -> bool {
        self.active_this_frame
    }

    /// Clear per-frame state and push the root node to start a new frame.
    pub(crate) fn begin_frame(&mut self) {
        self.focus_ids.clear();
        self.node_bounds.clear();
        self.action_listeners.clear();
        self.nodes.begin_frame();
    }

    /// Finalize the tree and produce a [`TreeUpdate`] for the platform adapter.
    pub(crate) fn end_frame(&mut self) -> TreeUpdate {
        let tree_update = self.nodes.finalize();

        // Open GPUI currently doesn't set any a11y APIs on *any* UI elements, so a
        // tree with nodes other than the root indicates a bug in the
        // `TreeUpdate`-producing logic.
        //
        // Remove this when adding aria attributes.
        if tree_update.nodes.len() > 1 {
            log::warn!(
                "expected an empty a11y tree update (only the root node), but got {} nodes; Open GPUI has no accessible UI elements yet",
                tree_update.nodes.len()
            );
        }

        tree_update
    }
}

pub(crate) struct A11yNodeBuilder {
    ids_stack: SmallVec<[NodeId; 16]>,
    nodes_stack: SmallVec<[accesskit::Node; 16]>,
    /// This is the exact type required by accesskit, so we can't just make it a
    /// `HashMap<NodeId, Node>` to remove the need for `seen_ids`
    all_nodes: Vec<(NodeId, accesskit::Node)>,
    seen_ids: FxHashSet<NodeId>,
    focus: NodeId,
    #[cfg(debug_assertions)]
    has_set_focus: bool,
}

impl A11yNodeBuilder {
    fn new() -> Self {
        Self {
            ids_stack: SmallVec::new(),
            nodes_stack: SmallVec::new(),
            all_nodes: Vec::new(),
            seen_ids: FxHashSet::default(),
            focus: ROOT_NODE_ID,
            #[cfg(debug_assertions)]
            has_set_focus: false,
        }
    }

    /// Push a new node onto the stack. It becomes a child of the current
    /// top-of-stack node.
    ///
    /// Returns `true` if the node was successfully pushed.
    pub(crate) fn push(&mut self, id: NodeId, node: accesskit::Node) -> bool {
        debug_assert!(!self.ids_stack.is_empty(), "push called before push_root");

        if !self.seen_ids.insert(id) {
            debug_assert!(
                false,
                "Duplicate a11y node id: {id:?}. In a release build, this node would be silently discarded from the a11y tree."
            );
            // We need to return `false` here because inserting a duplicate
            // node will cause a panic in accesskit
            return false;
        }

        if let Some(parent) = self.nodes_stack.last_mut() {
            parent.push_child(id);
        }
        self.ids_stack.push(id);
        self.nodes_stack.push(node);
        true
    }

    /// Pop the current node off the stack and finalize it into the all_nodes
    /// list.
    pub(crate) fn pop(&mut self) {
        debug_assert!(self.ids_stack.len() > 1, "pop would remove the root node");

        if let (Some(id), Some(node)) = (self.ids_stack.pop(), self.nodes_stack.pop()) {
            self.all_nodes.push((id, node));
        }
    }

    /// Push the root node to start a new frame.
    fn begin_frame(&mut self) {
        self.all_nodes.clear();
        self.ids_stack.clear();
        self.nodes_stack.clear();
        self.seen_ids.clear();
        #[cfg(debug_assertions)]
        {
            self.has_set_focus = false;
        }
        let root_node = accesskit::Node::new(accesskit::Role::Window);

        self.ids_stack.push(ROOT_NODE_ID);
        self.nodes_stack.push(root_node);
        self.focus = ROOT_NODE_ID;
    }

    /// Returns whether a node with the given ID has been pushed in this frame.
    pub(crate) fn has_node(&self, id: NodeId) -> bool {
        id == ROOT_NODE_ID || self.seen_ids.contains(&id)
    }

    /// Set the focused node for this frame.
    pub(crate) fn set_focus(&mut self, id: NodeId) {
        #[cfg(debug_assertions)]
        {
            debug_assert!(
                !self.has_set_focus,
                "set_focus called more than once in a single frame"
            );
            self.has_set_focus = true;
        }
        self.focus = id;
    }

    fn finalize(&mut self) -> TreeUpdate {
        // Stack should contain only the root node
        debug_assert_eq!(self.ids_stack.len(), 1);
        debug_assert_eq!(self.ids_stack[0], ROOT_NODE_ID);

        if self.ids_stack.len() != 1 {
            log::error!(
                "a11y: Stack imbalance at end of frame: expected 1 (root), got {}. \
                 Some elements may have pushed without popping.",
                self.ids_stack.len()
            );
        }

        // Pop remaining nodes (should just be the root).
        while !self.ids_stack.is_empty() {
            if let (Some(id), Some(node)) = (self.ids_stack.pop(), self.nodes_stack.pop()) {
                self.all_nodes.push((id, node));
            }
        }

        let nodes = std::mem::take(&mut self.all_nodes);
        let update = TreeUpdate {
            nodes,
            tree: Some(accesskit::Tree::new(ROOT_NODE_ID)),
            tree_id: accesskit::TreeId::ROOT,
            focus: self.focus,
        };

        Self::repair_tree_update(update)
    }

    /// Accesskit panics on invalid [`TreeUpdate`]s. This function defensively
    /// checks invariants that accesskit panics on, and tries to fix them.
    fn repair_tree_update(mut update: TreeUpdate) -> TreeUpdate {
        let node_ids: FxHashSet<NodeId> = update.nodes.iter().map(|(id, _)| *id).collect();

        // Focus must point to a node in the tree.
        if !node_ids.contains(&update.focus) {
            log::error!(
                "a11y: Focused node {:?} is not in the tree ({} nodes). \
                 Falling back to root. This is a bug in the a11y tree builder.",
                update.focus,
                update.nodes.len()
            );
            update.focus = ROOT_NODE_ID;
        }

        macro_rules! repair_node_id_slice {
            ($node:ident, $id:ident, $getter:ident, $setter:ident) => {
                if let Some(valid) =
                    filter_node_id_slice($id, stringify!($getter), $node.$getter(), &node_ids)
                {
                    $node.$setter(valid);
                }
            };
        }

        macro_rules! repair_node_id {
            ($node:ident, $id:ident, $getter:ident, $clearer:ident) => {
                if let Some(reference) = $node.$getter()
                    && !node_ids.contains(&reference)
                {
                    log_invalid_node_id_reference($id, stringify!($getter), reference);
                    $node.$clearer();
                }
            };
        }

        for (id, node) in &mut update.nodes {
            repair_node_id_slice!(node, id, children, set_children);
            repair_node_id_slice!(node, id, controls, set_controls);
            repair_node_id_slice!(node, id, details, set_details);
            repair_node_id_slice!(node, id, described_by, set_described_by);
            repair_node_id_slice!(node, id, flow_to, set_flow_to);
            repair_node_id_slice!(node, id, labelled_by, set_labelled_by);
            repair_node_id_slice!(node, id, owns, set_owns);
            repair_node_id_slice!(node, id, radio_group, set_radio_group);

            repair_node_id!(node, id, active_descendant, clear_active_descendant);
            repair_node_id!(node, id, error_message, clear_error_message);
            repair_node_id!(node, id, in_page_link_target, clear_in_page_link_target);
            repair_node_id!(node, id, member_of, clear_member_of);
            repair_node_id!(node, id, next_on_line, clear_next_on_line);
            repair_node_id!(node, id, previous_on_line, clear_previous_on_line);
            repair_node_id!(node, id, popup_for, clear_popup_for);
        }

        update
    }
}

fn log_invalid_node_id_reference(node_id: &NodeId, property: &'static str, reference: NodeId) {
    log::error!(
        "a11y: Node {:?} references {} node {:?} not present in the tree. \
         Stripping invalid reference.",
        node_id,
        property,
        reference
    );
}

fn filter_node_id_slice(
    node_id: &NodeId,
    property: &'static str,
    references: &[NodeId],
    node_ids: &FxHashSet<NodeId>,
) -> Option<Vec<NodeId>> {
    if references
        .iter()
        .all(|reference| node_ids.contains(reference))
    {
        return None;
    }

    let invalid_count = references
        .iter()
        .filter(|reference| !node_ids.contains(reference))
        .count();
    log::error!(
        "a11y: Node {:?} references {} {} nodes not present in the tree. \
         Stripping invalid references.",
        node_id,
        invalid_count,
        property
    );
    Some(
        references
            .iter()
            .copied()
            .filter(|reference| node_ids.contains(reference))
            .collect(),
    )
}

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

    #[test]
    fn repair_tree_update_strips_invalid_node_references() {
        let valid_label = NodeId(2);
        let missing = NodeId(99);
        let mut root = accesskit::Node::new(accesskit::Role::Window);
        let mut button = accesskit::Node::new(accesskit::Role::Button);
        let label = accesskit::Node::new(accesskit::Role::Label);

        root.set_children([NodeId(1), missing]);
        button.set_controls([valid_label, missing]);
        button.set_labelled_by([valid_label, missing]);
        button.set_active_descendant(missing);

        let update = accesskit::TreeUpdate {
            nodes: vec![
                (ROOT_NODE_ID, root),
                (NodeId(1), button),
                (valid_label, label),
            ],
            tree: Some(accesskit::Tree::new(ROOT_NODE_ID)),
            tree_id: accesskit::TreeId::ROOT,
            focus: missing,
        };

        let repaired = A11yNodeBuilder::repair_tree_update(update);
        let root = repaired
            .nodes
            .iter()
            .find(|(id, _)| *id == ROOT_NODE_ID)
            .map(|(_, node)| node)
            .unwrap();
        let button = repaired
            .nodes
            .iter()
            .find(|(id, _)| *id == NodeId(1))
            .map(|(_, node)| node)
            .unwrap();

        assert_eq!(repaired.focus, ROOT_NODE_ID);
        assert_eq!(root.children(), &[NodeId(1)]);
        assert_eq!(button.controls(), &[valid_label]);
        assert_eq!(button.labelled_by(), &[valid_label]);
        assert_eq!(button.active_descendant(), None);
    }

    #[test]
    fn repair_tree_update_preserves_valid_node_references() {
        let button_id = NodeId(1);
        let label_id = NodeId(2);
        let controlled_id = NodeId(3);
        let mut root = accesskit::Node::new(accesskit::Role::Window);
        let mut button = accesskit::Node::new(accesskit::Role::Button);
        let label = accesskit::Node::new(accesskit::Role::Label);
        let controlled = accesskit::Node::new(accesskit::Role::List);

        root.set_children([button_id, label_id, controlled_id]);
        button.set_controls([controlled_id]);
        button.set_labelled_by([label_id]);
        button.set_active_descendant(controlled_id);

        let update = accesskit::TreeUpdate {
            nodes: vec![
                (ROOT_NODE_ID, root),
                (button_id, button),
                (label_id, label),
                (controlled_id, controlled),
            ],
            tree: Some(accesskit::Tree::new(ROOT_NODE_ID)),
            tree_id: accesskit::TreeId::ROOT,
            focus: button_id,
        };

        let repaired = A11yNodeBuilder::repair_tree_update(update);
        let root = repaired
            .nodes
            .iter()
            .find(|(id, _)| *id == ROOT_NODE_ID)
            .map(|(_, node)| node)
            .unwrap();
        let button = repaired
            .nodes
            .iter()
            .find(|(id, _)| *id == button_id)
            .map(|(_, node)| node)
            .unwrap();

        assert_eq!(repaired.focus, button_id);
        assert_eq!(root.children(), &[button_id, label_id, controlled_id]);
        assert_eq!(button.controls(), &[controlled_id]);
        assert_eq!(button.labelled_by(), &[label_id]);
        assert_eq!(button.active_descendant(), Some(controlled_id));
    }

    #[test]
    fn repair_tree_update_clears_invalid_single_node_references() {
        let input_id = NodeId(1);
        let missing_error = NodeId(42);
        let missing_popup = NodeId(43);
        let mut root = accesskit::Node::new(accesskit::Role::Window);
        let mut input = accesskit::Node::new(accesskit::Role::TextInput);

        root.set_children([input_id]);
        input.set_error_message(missing_error);
        input.set_popup_for(missing_popup);

        let update = accesskit::TreeUpdate {
            nodes: vec![(ROOT_NODE_ID, root), (input_id, input)],
            tree: Some(accesskit::Tree::new(ROOT_NODE_ID)),
            tree_id: accesskit::TreeId::ROOT,
            focus: input_id,
        };

        let repaired = A11yNodeBuilder::repair_tree_update(update);
        let input = repaired
            .nodes
            .iter()
            .find(|(id, _)| *id == input_id)
            .map(|(_, node)| node)
            .unwrap();

        assert_eq!(repaired.focus, input_id);
        assert_eq!(input.error_message(), None);
        assert_eq!(input.popup_for(), None);
    }
}