gpui-ce 0.3.0

use crate::SharedString;
use anyhow::{Context as _, Result};
use std::fmt;

/// The names and values that describe one element, for matching key bindings.
///
/// An element sets its context with [`InteractiveElement::key_context`](crate::InteractiveElement::key_context),
/// and GPUI collects the contexts along the focus path into a stack. A binding's
/// [predicate](KeyBindingContextPredicate) is then matched against that stack. A context holds
/// identifiers, such as `Editor`, and key-value pairs, such as `mode=full`.
///
/// # Examples
///
/// ```
/// # use gpui::{KeyContext, SharedString};
/// let context = KeyContext::parse("Editor mode=full").unwrap();
/// assert!(context.contains("Editor"));
/// assert_eq!(context.get("mode"), Some(&SharedString::from("full")));
/// assert_eq!(context.get("Editor"), None);
/// ```
#[derive(Clone, Default, Eq, PartialEq, Hash)]
pub struct KeyContext(Vec<ContextEntry>);

#[derive(Clone, Debug, Eq, PartialEq, Hash)]
/// One identifier or key-value pair in a [`KeyContext`].
pub struct ContextEntry {
    /// The identifier, or the key of a key-value pair.
    pub key: SharedString,
    /// The value of a key-value pair, or `None` for a plain identifier.
    pub value: Option<SharedString>,
}

impl<'a> TryFrom<&'a str> for KeyContext {
    type Error = anyhow::Error;

    fn try_from(value: &'a str) -> Result<Self> {
        Self::parse(value)
    }
}

impl KeyContext {
    /// Creates an empty context that already has an `os` entry for the current platform.
    ///
    /// The value is `macos`, `linux`, `windows` or `unknown`, so a binding can use
    /// `os == macos` to apply on one platform only.
    pub fn new_with_defaults() -> Self {
        let mut context = Self::default();
        #[cfg(target_os = "macos")]
        context.set("os", "macos");
        #[cfg(any(target_os = "linux", target_os = "freebsd"))]
        context.set("os", "linux");
        #[cfg(target_os = "windows")]
        context.set("os", "windows");
        #[cfg(not(any(
            target_os = "macos",
            target_os = "linux",
            target_os = "freebsd",
            target_os = "windows"
        )))]
        context.set("os", "unknown");
        context
    }

    /// Returns the first identifier without a value, which names the element in
    /// the usual context convention. Returns `None` if there is no identifier.
    pub fn primary(&self) -> Option<&ContextEntry> {
        self.0.iter().find(|p| p.value.is_none())
    }

    /// Returns every entry except the one [`primary`](Self::primary) returns.
    pub fn secondary(&self) -> impl Iterator<Item = &ContextEntry> {
        let primary = self.primary();
        self.0.iter().filter(move |&p| Some(p) != primary)
    }

    /// Parses a context such as `Editor` or `Editor mode=full`.
    ///
    /// The text is a list of entries separated by whitespace. Each entry is either an identifier,
    /// such as `Editor`, or a key-value pair written `key=value` or `key = value`. Identifier
    /// characters are letters, digits, `_` and `-`. An entry whose key is already present is
    /// ignored, so the first one wins. Returns an error for text that isn't a list of such
    /// entries, such as `.` or `=insert`.
    ///
    /// This takes entries only. Operators such as `&&` and `>` aren't part of this format. Use
    /// [`KeyBindingContextPredicate::parse`] to write a predicate.
    ///
    /// # Examples
    ///
    /// ```
    /// # use gpui::{KeyContext, SharedString};
    /// let context = KeyContext::parse("Panel Editor mode = insert").unwrap();
    /// assert!(context.contains("Panel"));
    /// assert_eq!(context.primary().unwrap().key, SharedString::from("Panel"));
    /// ```
    pub fn parse(source: &str) -> Result<Self> {
        let mut context = Self::default();
        let source = skip_whitespace(source);
        Self::parse_expr(source, &mut context)?;
        Ok(context)
    }

    fn parse_expr(mut source: &str, context: &mut Self) -> Result<()> {
        if source.is_empty() {
            return Ok(());
        }

        let key = source
            .chars()
            .take_while(|c| is_identifier_char(*c))
            .collect::<String>();
        // Without this, an unexpected character makes no progress and recurses forever.
        anyhow::ensure!(
            !key.is_empty(),
            "expected a context identifier at {source:?}"
        );
        source = skip_whitespace(&source[key.len()..]);
        if let Some(suffix) = source.strip_prefix('=') {
            source = skip_whitespace(suffix);
            let value = source
                .chars()
                .take_while(|c| is_identifier_char(*c))
                .collect::<String>();
            source = skip_whitespace(&source[value.len()..]);
            context.set(key, value);
        } else {
            context.add(key);
        }

        Self::parse_expr(source, context)
    }

    /// Returns whether this context has no entries.
    pub fn is_empty(&self) -> bool {
        self.0.is_empty()
    }

    /// Removes every entry.
    pub fn clear(&mut self) {
        self.0.clear();
    }

    /// Adds each entry of `other` whose key this context doesn't already have.
    pub fn extend(&mut self, other: &Self) {
        for entry in &other.0 {
            if !self.contains(&entry.key) {
                self.0.push(entry.clone());
            }
        }
    }

    /// Adds an identifier, unless this context already has an entry with that key.
    pub fn add<I: Into<SharedString>>(&mut self, identifier: I) {
        let key = identifier.into();

        if !self.contains(&key) {
            self.0.push(ContextEntry { key, value: None })
        }
    }

    /// Adds a key-value pair, unless this context already has an entry with that key.
    pub fn set<S1: Into<SharedString>, S2: Into<SharedString>>(&mut self, key: S1, value: S2) {
        let key = key.into();
        if !self.contains(&key) {
            self.0.push(ContextEntry {
                key,
                value: Some(value.into()),
            })
        }
    }

    /// Returns whether this context has an entry with `key`, whether or not that entry has a value.
    pub fn contains(&self, key: &str) -> bool {
        self.0.iter().any(|entry| entry.key.as_ref() == key)
    }

    /// Returns the value of the first entry with `key`. Returns `None` if there is no such entry,
    /// or if the entry is a plain identifier.
    pub fn get(&self, key: &str) -> Option<&SharedString> {
        self.0
            .iter()
            .find(|entry| entry.key.as_ref() == key)?
            .value
            .as_ref()
    }
}

impl fmt::Debug for KeyContext {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        let mut entries = self.0.iter().peekable();
        while let Some(entry) = entries.next() {
            if let Some(ref value) = entry.value {
                write!(f, "{}={}", entry.key, value)?;
            } else {
                write!(f, "{}", entry.key)?;
            }
            if entries.peek().is_some() {
                write!(f, " ")?;
            }
        }
        Ok(())
    }
}

/// A condition on the key context stack that decides whether a binding applies.
///
/// A predicate is written in a small language, such as `Editor && mode == insert`, and is
/// evaluated against the [`KeyContext`]s on the focus path. Build one with
/// [`KeyBindingContextPredicate::parse`].
///
/// `Display` writes the predicate in the same syntax. It adds parentheses around `||` inside `&&`
/// and around negated groups. Descendant expressions are written without parentheses around their
/// operands, so add parentheses yourself when combining `>` with `&&` or `||` in text that must
/// round-trip through [`parse`](Self::parse).
///
/// # Examples
///
/// ```
/// # use gpui::{KeyBindingContextPredicate, KeyContext};
/// let predicate = KeyBindingContextPredicate::parse("Editor && mode == insert").unwrap();
/// assert_eq!(predicate.to_string(), "Editor && mode == insert");
///
/// let stack = [
///     KeyContext::parse("Workspace").unwrap(),
///     KeyContext::parse("Editor mode=insert").unwrap(),
/// ];
/// assert_eq!(predicate.depth_of(&stack), Some(2));
/// ```
#[derive(Clone, Debug, Eq, PartialEq, Hash)]
pub enum KeyBindingContextPredicate {
    /// Matches a context that has an entry named by the identifier, with or without a value.
    Identifier(SharedString),
    /// Matches a context whose entry for the key has the given value. Written `key == value`.
    Equal(SharedString, SharedString),
    /// Matches unless the context's entry for the key has the given value. Written `key != value`.
    /// Also matches when the context has no entry for the key.
    NotEqual(SharedString, SharedString),
    /// Matches when the first predicate matches an ancestor context and the second matches the
    /// contexts beneath it. Written `parent > child`.
    Descendant(
        Box<KeyBindingContextPredicate>,
        Box<KeyBindingContextPredicate>,
    ),
    /// Matches when the inner predicate doesn't match. Written `!inner`.
    Not(Box<KeyBindingContextPredicate>),
    /// Matches when both predicates match. Written `left && right`.
    And(
        Box<KeyBindingContextPredicate>,
        Box<KeyBindingContextPredicate>,
    ),
    /// Matches when either predicate matches. Written `left || right`.
    Or(
        Box<KeyBindingContextPredicate>,
        Box<KeyBindingContextPredicate>,
    ),
}

impl fmt::Display for KeyBindingContextPredicate {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        match self {
            Self::Identifier(name) => write!(f, "{name}"),
            Self::Equal(left, right) => write!(f, "{left} == {right}"),
            Self::NotEqual(left, right) => write!(f, "{left} != {right}"),
            Self::Descendant(parent, child) => write!(f, "{parent} > {child}"),
            Self::Not(pred) => match pred.as_ref() {
                Self::Identifier(name) => write!(f, "!{name}"),
                _ => write!(f, "!({pred})"),
            },
            Self::And(..) => self.fmt_joined(f, " && ", LogicalOperator::And, |node| {
                matches!(node, Self::Or(..))
            }),
            Self::Or(..) => self.fmt_joined(f, " || ", LogicalOperator::Or, |node| {
                matches!(node, Self::And(..))
            }),
        }
    }
}

impl KeyBindingContextPredicate {
    /// Parses a predicate such as `Editor && !ReadOnly` or `Panel > Editor`.
    ///
    /// The grammar, from the tightest-binding rule to the loosest, is:
    ///
    /// - **Atoms.** An identifier, such as `Editor`, matches a context with that name. An identifier
    ///   is letters, digits, `_` and `-`. The characters `>`, `<`, `~`, `"` and `?` can also
    ///   appear after the first character, so write `Panel > Editor` with spaces. The text
    ///   `Panel>Editor` is one identifier.
    /// - **Parentheses.** `( ... )` groups a predicate.
    /// - **Negation.** `!` applies to the atom or parenthesized group after it, so `!a && b` is
    ///   `(!a) && b`. Use `!(a && b)` to negate a group.
    /// - **Equality.** `key == value` and `key != value` compare the value of an entry. Both sides
    ///   must be plain identifiers, so `mode == "full"` is an error.
    /// - **`&&`** binds tighter than **`||`**. So `a || b && c` is `a || (b && c)`.
    /// - **Descendant.** `parent > child` binds loosest, so `a && b > c` is `(a && b) > c`. It is
    ///   left-associative: `A > B > C` is `(A > B) > C`.
    ///
    /// The keymap guide has the same rules as a table.
    ///
    /// # Errors
    ///
    /// Returns an error for an unbalanced parenthesis, a missing operand, an operator the grammar
    /// doesn't have, a `==` or `!=` whose operands aren't identifiers, or any leftover text.
    ///
    /// # Examples
    ///
    /// ```
    /// # use gpui::KeyBindingContextPredicate;
    /// let predicate = KeyBindingContextPredicate::parse("Pane > (Editor || Terminal) && !ReadOnly")
    ///     .unwrap();
    /// assert_eq!(predicate.to_string(), "Pane > (Editor || Terminal) && !ReadOnly");
    /// assert!(KeyBindingContextPredicate::parse("mode == \"full\"").is_err());
    /// ```
    ///
    /// See [contexts](crate::_documentation::concepts::contexts) and
    /// [keyboard input](crate::_documentation::guides::keyboard) for when contexts apply.
    pub fn parse(source: &str) -> Result<Self> {
        let source = skip_whitespace(source);
        let (predicate, rest) = Self::parse_expr(source, 0)?;
        if let Some(next) = rest.chars().next() {
            anyhow::bail!("unexpected character '{next:?}'");
        } else {
            Ok(predicate)
        }
    }

    /// Returns the deepest depth at which the predicate matches `contexts`, or `None` if it
    /// matches none.
    ///
    /// A depth `d` means the predicate matches the first `d` contexts, with the `d`th as the
    /// deepest one that identifiers and `==` look at. The keymap uses this depth to rank bindings:
    /// a deeper match wins. A predicate that matches only at a shallower depth is returned at that
    /// depth.
    ///
    /// # Examples
    ///
    /// ```
    /// # use gpui::{KeyBindingContextPredicate, KeyContext};
    /// let predicate = KeyBindingContextPredicate::parse("Workspace").unwrap();
    /// let stack = [
    ///     KeyContext::parse("Workspace").unwrap(),
    ///     KeyContext::parse("Editor").unwrap(),
    /// ];
    /// assert_eq!(predicate.depth_of(&stack), Some(1));
    /// assert_eq!(predicate.depth_of(&stack[1..]), None);
    /// ```
    pub fn depth_of(&self, contexts: &[KeyContext]) -> Option<usize> {
        for depth in (0..=contexts.len()).rev() {
            let context_slice = &contexts[0..depth];
            if self.eval_inner(context_slice, contexts) {
                return Some(depth);
            }
        }
        None
    }

    /// Returns whether the predicate matches the whole of `contexts`, which is ordered from the
    /// root to the focused element.
    #[allow(unused)]
    pub fn eval(&self, contexts: &[KeyContext]) -> bool {
        self.eval_inner(contexts, contexts)
    }

    /// Returns whether the predicate matches the prefix `contexts`, ordered from the root to the
    /// focused element. `all_contexts` is the full stack, which `!` checks against.
    ///
    /// Callers that want the whole stack use [`eval`](Self::eval). [`depth_of`](Self::depth_of)
    /// calls this with each prefix.
    pub fn eval_inner(&self, contexts: &[KeyContext], all_contexts: &[KeyContext]) -> bool {
        let Some(context) = contexts.last() else {
            return false;
        };
        match self {
            Self::Identifier(name) => context.contains(name),
            Self::Equal(left, right) => context
                .get(left)
                .map(|value| value == right)
                .unwrap_or(false),
            Self::NotEqual(left, right) => context
                .get(left)
                .map(|value| value != right)
                .unwrap_or(true),
            Self::Not(pred) => {
                for i in 0..all_contexts.len() {
                    if pred.eval_inner(&all_contexts[..=i], all_contexts) {
                        return false;
                    }
                }
                true
            }
            // Workspace > Pane > Editor
            //
            // Pane > (Pane > Editor) // should match?
            // (Pane > Pane) > Editor // should not match?
            // Pane > !Workspace <-- should match?
            // !Workspace        <-- shouldn't match?
            Self::Descendant(parent, child) => {
                for i in 0..contexts.len() - 1 {
                    // [Workspace >  Pane], [Editor]
                    if parent.eval_inner(&contexts[..=i], all_contexts) {
                        if !child.eval_inner(&contexts[i + 1..], &contexts[i + 1..]) {
                            return false;
                        }
                        return true;
                    }
                }
                false
            }
            Self::And(left, right) => {
                left.eval_inner(contexts, all_contexts) && right.eval_inner(contexts, all_contexts)
            }
            Self::Or(left, right) => {
                left.eval_inner(contexts, all_contexts) || right.eval_inner(contexts, all_contexts)
            }
        }
    }

    /// Returns whether every context that `other` matches is also matched by `self`.
    ///
    /// The check is conservative. `true` is certain, but `false` means only that this check
    /// couldn't show it. The keymap uses it to check whether a disabling binding's context covers
    /// the context of the binding it disables.
    ///
    /// # Examples
    ///
    /// ```
    /// # use gpui::KeyBindingContextPredicate;
    /// let editor = KeyBindingContextPredicate::parse("Editor").unwrap();
    /// let editor_and_vim = KeyBindingContextPredicate::parse("Editor && vim_mode").unwrap();
    /// assert!(editor.is_superset(&editor_and_vim));
    /// assert!(!editor_and_vim.is_superset(&editor));
    /// ```
    pub fn is_superset(&self, other: &Self) -> bool {
        if self == other {
            return true;
        }

        if let KeyBindingContextPredicate::Or(left, right) = self {
            return left.is_superset(other) || right.is_superset(other);
        }

        match other {
            KeyBindingContextPredicate::Descendant(_, child) => self.is_superset(child),
            KeyBindingContextPredicate::And(left, right) => {
                self.is_superset(left) || self.is_superset(right)
            }
            KeyBindingContextPredicate::Identifier(_) => false,
            KeyBindingContextPredicate::Equal(_, _) => false,
            KeyBindingContextPredicate::NotEqual(_, _) => false,
            KeyBindingContextPredicate::Not(_) => false,
            KeyBindingContextPredicate::Or(_, _) => false,
        }
    }

    fn parse_expr(mut source: &str, min_precedence: u32) -> anyhow::Result<(Self, &str)> {
        type Op = fn(
            KeyBindingContextPredicate,
            KeyBindingContextPredicate,
        ) -> Result<KeyBindingContextPredicate>;

        let (mut predicate, rest) = Self::parse_primary(source)?;
        source = rest;

        'parse: loop {
            for (operator, precedence, constructor) in [
                (">", PRECEDENCE_CHILD, Self::new_child as Op),
                ("&&", PRECEDENCE_AND, Self::new_and as Op),
                ("||", PRECEDENCE_OR, Self::new_or as Op),
                ("==", PRECEDENCE_EQ, Self::new_eq as Op),
                ("!=", PRECEDENCE_EQ, Self::new_neq as Op),
            ] {
                if source.starts_with(operator) && precedence >= min_precedence {
                    source = skip_whitespace(&source[operator.len()..]);
                    let (right, rest) = Self::parse_expr(source, precedence + 1)?;
                    predicate = constructor(predicate, right)?;
                    source = rest;
                    continue 'parse;
                }
            }
            break;
        }

        Ok((predicate, source))
    }

    fn parse_primary(mut source: &str) -> anyhow::Result<(Self, &str)> {
        let next = source.chars().next().context("unexpected end")?;
        match next {
            '(' => {
                source = skip_whitespace(&source[1..]);
                let (predicate, rest) = Self::parse_expr(source, 0)?;
                let stripped = rest.strip_prefix(')').context("expected a ')'")?;
                source = skip_whitespace(stripped);
                Ok((predicate, source))
            }
            '!' => {
                let source = skip_whitespace(&source[1..]);
                let (predicate, source) = Self::parse_expr(source, PRECEDENCE_NOT)?;
                Ok((KeyBindingContextPredicate::Not(Box::new(predicate)), source))
            }
            _ if is_identifier_char(next) => {
                let len = source
                    .find(|c: char| !is_identifier_char(c) && !is_vim_operator_char(c))
                    .unwrap_or(source.len());
                let (identifier, rest) = source.split_at(len);
                source = skip_whitespace(rest);
                Ok((
                    KeyBindingContextPredicate::Identifier(identifier.to_string().into()),
                    source,
                ))
            }
            _ if is_vim_operator_char(next) => {
                let (operator, rest) = source.split_at(1);
                source = skip_whitespace(rest);
                Ok((
                    KeyBindingContextPredicate::Identifier(operator.to_string().into()),
                    source,
                ))
            }
            _ => anyhow::bail!("unexpected character '{next:?}'"),
        }
    }

    fn new_or(self, other: Self) -> Result<Self> {
        Ok(Self::Or(Box::new(self), Box::new(other)))
    }

    fn new_and(self, other: Self) -> Result<Self> {
        Ok(Self::And(Box::new(self), Box::new(other)))
    }

    fn new_child(self, other: Self) -> Result<Self> {
        Ok(Self::Descendant(Box::new(self), Box::new(other)))
    }

    fn new_eq(self, other: Self) -> Result<Self> {
        if let (Self::Identifier(left), Self::Identifier(right)) = (self, other) {
            Ok(Self::Equal(left, right))
        } else {
            anyhow::bail!("operands of == must be identifiers");
        }
    }

    fn new_neq(self, other: Self) -> Result<Self> {
        if let (Self::Identifier(left), Self::Identifier(right)) = (self, other) {
            Ok(Self::NotEqual(left, right))
        } else {
            anyhow::bail!("operands of != must be identifiers");
        }
    }

    fn fmt_joined(
        &self,
        f: &mut fmt::Formatter<'_>,
        separator: &str,
        operator: LogicalOperator,
        needs_parens: impl Fn(&Self) -> bool + Copy,
    ) -> fmt::Result {
        let mut first = true;
        self.fmt_joined_inner(f, separator, operator, needs_parens, &mut first)
    }

    fn fmt_joined_inner(
        &self,
        f: &mut fmt::Formatter<'_>,
        separator: &str,
        operator: LogicalOperator,
        needs_parens: impl Fn(&Self) -> bool + Copy,
        first: &mut bool,
    ) -> fmt::Result {
        match (operator, self) {
            (LogicalOperator::And, Self::And(left, right))
            | (LogicalOperator::Or, Self::Or(left, right)) => {
                left.fmt_joined_inner(f, separator, operator, needs_parens, first)?;
                right.fmt_joined_inner(f, separator, operator, needs_parens, first)
            }
            (_, node) => {
                if !*first {
                    f.write_str(separator)?;
                }
                *first = false;

                if needs_parens(node) {
                    write!(f, "({node})")
                } else {
                    write!(f, "{node}")
                }
            }
        }
    }
}

#[derive(Clone, Copy)]
enum LogicalOperator {
    And,
    Or,
}

const PRECEDENCE_CHILD: u32 = 1;
const PRECEDENCE_OR: u32 = 2;
const PRECEDENCE_AND: u32 = 3;
const PRECEDENCE_EQ: u32 = 4;
const PRECEDENCE_NOT: u32 = 5;

fn is_identifier_char(c: char) -> bool {
    c.is_alphanumeric() || c == '_' || c == '-'
}

fn is_vim_operator_char(c: char) -> bool {
    c == '>' || c == '<' || c == '~' || c == '"' || c == '?'
}

fn skip_whitespace(source: &str) -> &str {
    let len = source
        .find(|c: char| !c.is_whitespace())
        .unwrap_or(source.len());
    &source[len..]
}

#[cfg(test)]
mod tests {
    use core::slice;

    use super::*;
    use crate as gpui;
    use KeyBindingContextPredicate::*;

    #[test]
    fn test_actions_definition() {
        {
            actions!(test_only, [A, B, C, D, E, F, G]);
        }

        {
            actions!(
                test_only,
                [
                    H, I, J, K, L, M, N, // Don't wrap, test the trailing comma
                ]
            );
        }
    }

    #[test]
    fn test_parse_context() {
        let mut expected = KeyContext::default();
        expected.add("baz");
        expected.set("foo", "bar");
        assert_eq!(KeyContext::parse("baz foo=bar").unwrap(), expected);
        assert_eq!(KeyContext::parse("baz foo = bar").unwrap(), expected);
        assert_eq!(
            KeyContext::parse("  baz foo   =   bar baz").unwrap(),
            expected
        );
        assert_eq!(KeyContext::parse(" baz foo = bar").unwrap(), expected);
    }

    #[test]
    fn test_parse_malformed_context() {
        for source in [
            ".",
            "Editor && enabled",
            "=insert",
            "mode==insert",
            "mode=\"insert\"",
        ] {
            assert!(KeyContext::parse(source).is_err(), "accepted {source:?}");
        }
        assert!(KeyContext::parse(" \n ").unwrap().is_empty());
    }

    #[test]
    fn test_parse_identifiers() {
        // Identifiers
        assert_eq!(
            KeyBindingContextPredicate::parse("abc12").unwrap(),
            Identifier("abc12".into())
        );
        assert_eq!(
            KeyBindingContextPredicate::parse("_1a").unwrap(),
            Identifier("_1a".into())
        );
    }

    #[test]
    fn test_parse_negations() {
        assert_eq!(
            KeyBindingContextPredicate::parse("!abc").unwrap(),
            Not(Box::new(Identifier("abc".into())))
        );
        assert_eq!(
            KeyBindingContextPredicate::parse(" ! ! abc").unwrap(),
            Not(Box::new(Not(Box::new(Identifier("abc".into())))))
        );
    }

    #[test]
    fn test_parse_equality_operators() {
        assert_eq!(
            KeyBindingContextPredicate::parse("a == b").unwrap(),
            Equal("a".into(), "b".into())
        );
        assert_eq!(
            KeyBindingContextPredicate::parse("c!=d").unwrap(),
            NotEqual("c".into(), "d".into())
        );
        assert_eq!(
            KeyBindingContextPredicate::parse("c == !d")
                .unwrap_err()
                .to_string(),
            "operands of == must be identifiers"
        );
    }

    #[test]
    fn test_parse_boolean_operators() {
        assert_eq!(
            KeyBindingContextPredicate::parse("a || b").unwrap(),
            Or(
                Box::new(Identifier("a".into())),
                Box::new(Identifier("b".into()))
            )
        );
        assert_eq!(
            KeyBindingContextPredicate::parse("a || !b && c").unwrap(),
            Or(
                Box::new(Identifier("a".into())),
                Box::new(And(
                    Box::new(Not(Box::new(Identifier("b".into())))),
                    Box::new(Identifier("c".into()))
                ))
            )
        );
        assert_eq!(
            KeyBindingContextPredicate::parse("a && b || c&&d").unwrap(),
            Or(
                Box::new(And(
                    Box::new(Identifier("a".into())),
                    Box::new(Identifier("b".into()))
                )),
                Box::new(And(
                    Box::new(Identifier("c".into())),
                    Box::new(Identifier("d".into()))
                ))
            )
        );
        assert_eq!(
            KeyBindingContextPredicate::parse("a == b && c || d == e && f").unwrap(),
            Or(
                Box::new(And(
                    Box::new(Equal("a".into(), "b".into())),
                    Box::new(Identifier("c".into()))
                )),
                Box::new(And(
                    Box::new(Equal("d".into(), "e".into())),
                    Box::new(Identifier("f".into()))
                ))
            )
        );
        assert_eq!(
            KeyBindingContextPredicate::parse("a && b && c && d").unwrap(),
            And(
                Box::new(And(
                    Box::new(And(
                        Box::new(Identifier("a".into())),
                        Box::new(Identifier("b".into()))
                    )),
                    Box::new(Identifier("c".into())),
                )),
                Box::new(Identifier("d".into()))
            ),
        );
    }

    #[test]
    fn test_parse_parenthesized_expressions() {
        assert_eq!(
            KeyBindingContextPredicate::parse("a && (b == c || d != e)").unwrap(),
            And(
                Box::new(Identifier("a".into())),
                Box::new(Or(
                    Box::new(Equal("b".into(), "c".into())),
                    Box::new(NotEqual("d".into(), "e".into())),
                )),
            ),
        );
        assert_eq!(
            KeyBindingContextPredicate::parse(" ( a || b ) ").unwrap(),
            Or(
                Box::new(Identifier("a".into())),
                Box::new(Identifier("b".into())),
            )
        );
    }

    #[test]
    fn test_is_superset() {
        assert_is_superset("editor", "editor", true);
        assert_is_superset("editor", "workspace", false);

        assert_is_superset("editor", "editor && vim_mode", true);
        assert_is_superset("editor", "mode == full && editor", true);
        assert_is_superset("editor && mode == full", "editor", false);

        assert_is_superset("editor", "something > editor", true);
        assert_is_superset("editor", "editor > menu", false);

        assert_is_superset("foo || bar || baz", "bar", true);
        assert_is_superset("foo || bar || baz", "quux", false);

        #[track_caller]
        fn assert_is_superset(a: &str, b: &str, result: bool) {
            let a = KeyBindingContextPredicate::parse(a).unwrap();
            let b = KeyBindingContextPredicate::parse(b).unwrap();
            assert_eq!(a.is_superset(&b), result, "({a:?}).is_superset({b:?})");
        }
    }

    #[test]
    fn test_child_operator() {
        let predicate = KeyBindingContextPredicate::parse("parent > child").unwrap();

        let parent_context = KeyContext::try_from("parent").unwrap();
        let child_context = KeyContext::try_from("child").unwrap();

        let contexts = vec![parent_context.clone(), child_context.clone()];
        assert!(predicate.eval(&contexts));

        let grandparent_context = KeyContext::try_from("grandparent").unwrap();

        let contexts = vec![
            grandparent_context,
            parent_context.clone(),
            child_context.clone(),
        ];
        assert!(predicate.eval(&contexts));

        let other_context = KeyContext::try_from("other").unwrap();

        let contexts = vec![other_context.clone(), child_context.clone()];
        assert!(!predicate.eval(&contexts));

        let contexts = vec![parent_context.clone(), other_context, child_context.clone()];
        assert!(predicate.eval(&contexts));

        assert!(!predicate.eval(&[]));
        assert!(!predicate.eval(slice::from_ref(&child_context)));
        assert!(!predicate.eval(&[parent_context]));

        let zany_predicate = KeyBindingContextPredicate::parse("child > child").unwrap();
        assert!(!zany_predicate.eval(slice::from_ref(&child_context)));
        assert!(zany_predicate.eval(&[child_context.clone(), child_context]));
    }

    #[test]
    fn test_not_operator() {
        let not_predicate = KeyBindingContextPredicate::parse("!editor").unwrap();
        let editor_context = KeyContext::try_from("editor").unwrap();
        let workspace_context = KeyContext::try_from("workspace").unwrap();
        let parent_context = KeyContext::try_from("parent").unwrap();
        let child_context = KeyContext::try_from("child").unwrap();

        assert!(not_predicate.eval(slice::from_ref(&workspace_context)));
        assert!(!not_predicate.eval(slice::from_ref(&editor_context)));
        assert!(!not_predicate.eval(&[editor_context.clone(), workspace_context.clone()]));
        assert!(!not_predicate.eval(&[workspace_context.clone(), editor_context.clone()]));

        let complex_not = KeyBindingContextPredicate::parse("!editor && workspace").unwrap();
        assert!(complex_not.eval(slice::from_ref(&workspace_context)));
        assert!(!complex_not.eval(&[editor_context.clone(), workspace_context.clone()]));

        let not_mode_predicate = KeyBindingContextPredicate::parse("!(mode == full)").unwrap();
        let mut mode_context = KeyContext::default();
        mode_context.set("mode", "full");
        assert!(!not_mode_predicate.eval(&[mode_context.clone()]));

        let mut other_mode_context = KeyContext::default();
        other_mode_context.set("mode", "partial");
        assert!(not_mode_predicate.eval(&[other_mode_context]));

        let not_descendant = KeyBindingContextPredicate::parse("!(parent > child)").unwrap();
        assert!(not_descendant.eval(slice::from_ref(&parent_context)));
        assert!(not_descendant.eval(slice::from_ref(&child_context)));
        assert!(!not_descendant.eval(&[parent_context.clone(), child_context.clone()]));

        let not_descendant = KeyBindingContextPredicate::parse("parent > !child").unwrap();
        assert!(!not_descendant.eval(slice::from_ref(&parent_context)));
        assert!(!not_descendant.eval(slice::from_ref(&child_context)));
        assert!(!not_descendant.eval(&[parent_context, child_context]));

        let double_not = KeyBindingContextPredicate::parse("!!editor").unwrap();
        assert!(double_not.eval(slice::from_ref(&editor_context)));
        assert!(!double_not.eval(slice::from_ref(&workspace_context)));

        // Test complex descendant cases
        let workspace_context = KeyContext::try_from("Workspace").unwrap();
        let pane_context = KeyContext::try_from("Pane").unwrap();
        let editor_context = KeyContext::try_from("Editor").unwrap();

        // Workspace > Pane > Editor
        let workspace_pane_editor = vec![
            workspace_context.clone(),
            pane_context.clone(),
            editor_context.clone(),
        ];

        // Pane > (Pane > Editor) - should not match
        let pane_pane_editor = KeyBindingContextPredicate::parse("Pane > (Pane > Editor)").unwrap();
        assert!(!pane_pane_editor.eval(&workspace_pane_editor));

        let workspace_pane_editor_predicate =
            KeyBindingContextPredicate::parse("Workspace > Pane > Editor").unwrap();
        assert!(workspace_pane_editor_predicate.eval(&workspace_pane_editor));

        // (Pane > Pane) > Editor - should not match
        let pane_pane_then_editor =
            KeyBindingContextPredicate::parse("(Pane > Pane) > Editor").unwrap();
        assert!(!pane_pane_then_editor.eval(&workspace_pane_editor));

        // Pane > !Workspace - should match
        let pane_not_workspace = KeyBindingContextPredicate::parse("Pane > !Workspace").unwrap();
        assert!(pane_not_workspace.eval(&[pane_context.clone(), editor_context.clone()]));
        assert!(!pane_not_workspace.eval(&[pane_context.clone(), workspace_context.clone()]));

        // !Workspace - shouldn't match when Workspace is in the context
        let not_workspace = KeyBindingContextPredicate::parse("!Workspace").unwrap();
        assert!(!not_workspace.eval(slice::from_ref(&workspace_context)));
        assert!(not_workspace.eval(slice::from_ref(&pane_context)));
        assert!(not_workspace.eval(slice::from_ref(&editor_context)));
        assert!(!not_workspace.eval(&workspace_pane_editor));
    }

    // MARK: - Display

    #[test]
    fn test_context_display() {
        fn ident(s: &str) -> Box<KeyBindingContextPredicate> {
            Box::new(Identifier(SharedString::new(s)))
        }
        fn eq(a: &str, b: &str) -> Box<KeyBindingContextPredicate> {
            Box::new(Equal(SharedString::new(a), SharedString::new(b)))
        }
        fn not_eq(a: &str, b: &str) -> Box<KeyBindingContextPredicate> {
            Box::new(NotEqual(SharedString::new(a), SharedString::new(b)))
        }
        fn and(
            a: Box<KeyBindingContextPredicate>,
            b: Box<KeyBindingContextPredicate>,
        ) -> Box<KeyBindingContextPredicate> {
            Box::new(And(a, b))
        }
        fn or(
            a: Box<KeyBindingContextPredicate>,
            b: Box<KeyBindingContextPredicate>,
        ) -> Box<KeyBindingContextPredicate> {
            Box::new(Or(a, b))
        }
        fn descendant(
            a: Box<KeyBindingContextPredicate>,
            b: Box<KeyBindingContextPredicate>,
        ) -> Box<KeyBindingContextPredicate> {
            Box::new(Descendant(a, b))
        }
        fn not(a: Box<KeyBindingContextPredicate>) -> Box<KeyBindingContextPredicate> {
            Box::new(Not(a))
        }

        let test_cases = [
            (ident("a"), "a"),
            (eq("a", "b"), "a == b"),
            (not_eq("a", "b"), "a != b"),
            (descendant(ident("a"), ident("b")), "a > b"),
            (not(ident("a")), "!a"),
            (not_eq("a", "b"), "a != b"),
            (descendant(ident("a"), ident("b")), "a > b"),
            (not(and(ident("a"), ident("b"))), "!(a && b)"),
            (not(or(ident("a"), ident("b"))), "!(a || b)"),
            (and(ident("a"), ident("b")), "a && b"),
            (and(and(ident("a"), ident("b")), ident("c")), "a && b && c"),
            (or(ident("a"), ident("b")), "a || b"),
            (or(or(ident("a"), ident("b")), ident("c")), "a || b || c"),
            (or(ident("a"), and(ident("b"), ident("c"))), "a || (b && c)"),
            (
                and(
                    and(
                        and(ident("a"), eq("b", "c")),
                        not(descendant(ident("d"), ident("e"))),
                    ),
                    eq("f", "g"),
                ),
                "a && b == c && !(d > e) && f == g",
            ),
            (
                and(and(ident("a"), or(ident("b"), ident("c"))), ident("d")),
                "a && (b || c) && d",
            ),
            (
                or(or(ident("a"), and(ident("b"), ident("c"))), ident("d")),
                "a || (b && c) || d",
            ),
        ];

        for (predicate, expected) in test_cases {
            let actual = predicate.to_string();
            assert_eq!(actual, expected);
            let parsed = KeyBindingContextPredicate::parse(&actual).unwrap();
            assert_eq!(parsed, *predicate);
        }
    }
}