mod cursor;mod tree_map; use arrayvec::ArrayVec;pub use cursor::{Cursor, FilterCursor, Iter};use rayon::iter::{IndexedParallelIterator, IntoParallelIterator, ParallelIterator as _};use std::marker::PhantomData;use std::mem;use std::{cmp::Ordering, fmt, iter::FromIterator, sync::Arc};pub use tree_map::{MapSeekTarget, TreeMap, TreeSet};use ztracing::instrument; #[cfg(test)]pub const TREE_BASE: usize = 2;#[cfg(not(test))]pub const TREE_BASE: usize = 6; /// An item that can be stored in a [`SumTree`]////// Must be summarized by a type that implements [`Summary`]pub trait Item: Clone {    type Summary: Summary;     fn summary(&self, cx: <Self::Summary as Summary>::Context<'_>) -> Self::Summary;} /// An [`Item`] whose summary has a specific key that can be used to identify itpub trait KeyedItem: Item {    type Key: for<'a> Dimension<'a, Self::Summary> + Ord;     fn key(&self) -> Self::Key;} /// A type that describes the Sum of all [`Item`]s in a subtree of the [`SumTree`]////// Each Summary type can have multiple [`Dimension`]s that it measures,/// which can be used to navigate the treepub trait Summary: Clone {    type Context<'a>: Copy;    fn zero<'a>(cx: Self::Context<'a>) -> Self;    fn add_summary<'a>(&mut self, summary: &Self, cx: Self::Context<'a>);} pub trait ContextLessSummary: Clone {    fn zero() -> Self;    fn add_summary(&mut self, summary: &Self);} impl<T: ContextLessSummary> Summary for T {    type Context<'a> = ();     fn zero<'a>((): ()) -> Self {        T::zero()    }     fn add_summary<'a>(&mut self, summary: &Self, (): ()) {        T::add_summary(self, summary)    }} #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]pub struct NoSummary; /// Catch-all implementation for when you need something that implements [`Summary`] without a specific type./// We implement it on a `NoSummary` instead of re-using `()`, as that avoids blanket impl collisions with `impl<T: Summary> Dimension for T`/// (as we also need unit type to be a fill-in dimension)impl ContextLessSummary for NoSummary {    fn zero() -> Self {        NoSummary    }     fn add_summary(&mut self, _: &Self) {}} /// Each [`Summary`] type can have more than one [`Dimension`] type that it measures.////// You can use dimensions to seek to a specific location in the [`SumTree`]////// # Example:/// Zed's rope has a `TextSummary` type that summarizes lines, characters, and bytes./// Each of these are different dimensions we may want to seek topub trait Dimension<'a, S: Summary>: Clone {    fn zero(cx: S::Context<'_>) -> Self;     fn add_summary(&mut self, summary: &'a S, cx: S::Context<'_>);    #[must_use]    fn with_added_summary(mut self, summary: &'a S, cx: S::Context<'_>) -> Self {        self.add_summary(summary, cx);        self    }     fn from_summary(summary: &'a S, cx: S::Context<'_>) -> Self {        let mut dimension = Self::zero(cx);        dimension.add_summary(summary, cx);        dimension    }} impl<'a, T: Summary> Dimension<'a, T> for T {    fn zero(cx: T::Context<'_>) -> Self {        Summary::zero(cx)    }     fn add_summary(&mut self, summary: &'a T, cx: T::Context<'_>) {        Summary::add_summary(self, summary, cx);    }} pub trait SeekTarget<'a, S: Summary, D: Dimension<'a, S>> {    fn cmp(&self, cursor_location: &D, cx: S::Context<'_>) -> Ordering;} impl<'a, S: Summary, D: Dimension<'a, S> + Ord> SeekTarget<'a, S, D> for D {    fn cmp(&self, cursor_location: &Self, _: S::Context<'_>) -> Ordering {        Ord::cmp(self, cursor_location)    }} impl<'a, T: Summary> Dimension<'a, T> for () {    fn zero(_: T::Context<'_>) -> Self {}     fn add_summary(&mut self, _: &'a T, _: T::Context<'_>) {}} #[derive(Clone, Copy, Debug, Default, PartialEq, Eq, PartialOrd, Ord)]pub struct Dimensions<D1, D2, D3 = ()>(pub D1, pub D2, pub D3); impl<'a, T: Summary, D1: Dimension<'a, T>, D2: Dimension<'a, T>, D3: Dimension<'a, T>>    Dimension<'a, T> for Dimensions<D1, D2, D3>{    fn zero(cx: T::Context<'_>) -> Self {        Dimensions(D1::zero(cx), D2::zero(cx), D3::zero(cx))    }     fn add_summary(&mut self, summary: &'a T, cx: T::Context<'_>) {        self.0.add_summary(summary, cx);        self.1.add_summary(summary, cx);        self.2.add_summary(summary, cx);    }} impl<'a, S, D1, D2, D3> SeekTarget<'a, S, Dimensions<D1, D2, D3>> for D1where    S: Summary,    D1: SeekTarget<'a, S, D1> + Dimension<'a, S>,    D2: Dimension<'a, S>,    D3: Dimension<'a, S>,{    fn cmp(&self, cursor_location: &Dimensions<D1, D2, D3>, cx: S::Context<'_>) -> Ordering {        self.cmp(&cursor_location.0, cx)    }} /// Bias is used to settle ambiguities when determining positions in an ordered sequence.////// The primary use case is for text, where Bias influences/// which character an offset or anchor is associated with.////// # Examples/// Given the buffer `AˇBCD`:/// - The offset of the cursor is 1/// - [Bias::Left] would attach the cursor to the character `A`/// - [Bias::Right] would attach the cursor to the character `B`////// Given the buffer `A«BCˇ»D`:/// - The offset of the cursor is 3, and the selection is from 1 to 3/// - The left anchor of the selection has [Bias::Right], attaching it to the character `B`/// - The right anchor of the selection has [Bias::Left], attaching it to the character `C`////// Given the buffer `{ˇ<...>`, where `<...>` is a folded region:/// - The display offset of the cursor is 1, but the offset in the buffer is determined by the bias/// - [Bias::Left] would attach the cursor to the character `{`, with a buffer offset of 1/// - [Bias::Right] would attach the cursor to the first character of the folded region,///   and the buffer offset would be the offset of the first character of the folded region#[derive(Copy, Clone, Eq, PartialEq, PartialOrd, Ord, Debug, Hash, Default)]pub enum Bias {    /// Attach to the character on the left    #[default]    Left,    /// Attach to the character on the right    Right,} impl Bias {    pub fn invert(self) -> Self {        match self {            Self::Left => Self::Right,            Self::Right => Self::Left,        }    }} /// A B+ tree in which each leaf node contains `Item`s of type `T` and a `Summary`s for each `Item`./// Each internal node contains a `Summary` of the items in its subtree.////// The maximum number of items per node is `TREE_BASE * 2`.////// Any [`Dimension`] supported by the [`Summary`] type can be used to seek to a specific location in the tree.#[derive(Clone)]pub struct SumTree<T: Item>(Arc<Node<T>>); impl<T> fmt::Debug for SumTree<T>where    T: fmt::Debug + Item,    T::Summary: fmt::Debug,{    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {        f.debug_tuple("SumTree").field(&self.0).finish()    }} impl<T: Item> SumTree<T> {    pub fn new(cx: <T::Summary as Summary>::Context<'_>) -> Self {        SumTree(Arc::new(Node::Leaf {            summary: <T::Summary as Summary>::zero(cx),            items: ArrayVec::new(),            item_summaries: ArrayVec::new(),        }))    }     /// Useful in cases where the item type has a non-trivial context type, but the zero value of the summary type doesn't depend on that context.    pub fn from_summary(summary: T::Summary) -> Self {        SumTree(Arc::new(Node::Leaf {            summary,            items: ArrayVec::new(),            item_summaries: ArrayVec::new(),        }))    }     pub fn from_item(item: T, cx: <T::Summary as Summary>::Context<'_>) -> Self {        let mut tree = Self::new(cx);        tree.push(item, cx);        tree    }     pub fn from_iter<I: IntoIterator<Item = T>>(        iter: I,        cx: <T::Summary as Summary>::Context<'_>,    ) -> Self {        let mut nodes = Vec::new();         let mut iter = iter.into_iter().fuse().peekable();        while iter.peek().is_some() {            let items: ArrayVec<T, { 2 * TREE_BASE }> = iter.by_ref().take(2 * TREE_BASE).collect();            let item_summaries: ArrayVec<T::Summary, { 2 * TREE_BASE }> =                items.iter().map(|item| item.summary(cx)).collect();             let mut summary = item_summaries[0].clone();            for item_summary in &item_summaries[1..] {                <T::Summary as Summary>::add_summary(&mut summary, item_summary, cx);            }             nodes.push(SumTree(Arc::new(Node::Leaf {                summary,                items,                item_summaries,            })));        }         let mut parent_nodes = Vec::new();        let mut height = 0;        while nodes.len() > 1 {            height += 1;            let mut current_parent_node = None;            for child_node in nodes.drain(..) {                let parent_node = current_parent_node.get_or_insert_with(|| {                    SumTree(Arc::new(Node::Internal {                        summary: <T::Summary as Summary>::zero(cx),                        height,                        child_summaries: ArrayVec::new(),                        child_trees: ArrayVec::new(),                    }))                });                let Node::Internal {                    summary,                    child_summaries,                    child_trees,                    ..                } = Arc::get_mut(&mut parent_node.0).unwrap()                else {                    unreachable!()                };                let child_summary = child_node.summary();                <T::Summary as Summary>::add_summary(summary, child_summary, cx);                child_summaries.push(child_summary.clone());                child_trees.push(child_node);                 if child_trees.len() == 2 * TREE_BASE {                    parent_nodes.extend(current_parent_node.take());                }            }            parent_nodes.extend(current_parent_node.take());            mem::swap(&mut nodes, &mut parent_nodes);        }         if nodes.is_empty() {            Self::new(cx)        } else {            debug_assert_eq!(nodes.len(), 1);            nodes.pop().unwrap()        }    }     pub fn from_par_iter<I, Iter>(iter: I, cx: <T::Summary as Summary>::Context<'_>) -> Self    where        I: IntoParallelIterator<Iter = Iter>,        Iter: IndexedParallelIterator<Item = T>,        T: Send + Sync,        T::Summary: Send + Sync,        for<'a> <T::Summary as Summary>::Context<'a>: Sync,    {        let mut nodes = iter            .into_par_iter()            .chunks(2 * TREE_BASE)            .map(|items| {                let items: ArrayVec<T, { 2 * TREE_BASE }> = items.into_iter().collect();                let item_summaries: ArrayVec<T::Summary, { 2 * TREE_BASE }> =                    items.iter().map(|item| item.summary(cx)).collect();                let mut summary = item_summaries[0].clone();                for item_summary in &item_summaries[1..] {                    <T::Summary as Summary>::add_summary(&mut summary, item_summary, cx);                }                SumTree(Arc::new(Node::Leaf {                    summary,                    items,                    item_summaries,                }))            })            .collect::<Vec<_>>();         let mut height = 0;        while nodes.len() > 1 {            height += 1;            nodes = nodes                .into_par_iter()                .chunks(2 * TREE_BASE)                .map(|child_nodes| {                    let child_trees: ArrayVec<SumTree<T>, { 2 * TREE_BASE }> =                        child_nodes.into_iter().collect();                    let child_summaries: ArrayVec<T::Summary, { 2 * TREE_BASE }> = child_trees                        .iter()                        .map(|child_tree| child_tree.summary().clone())                        .collect();                    let mut summary = child_summaries[0].clone();                    for child_summary in &child_summaries[1..] {                        <T::Summary as Summary>::add_summary(&mut summary, child_summary, cx);                    }                    SumTree(Arc::new(Node::Internal {                        height,                        summary,                        child_summaries,                        child_trees,                    }))                })                .collect::<Vec<_>>();        }         if nodes.is_empty() {            Self::new(cx)        } else {            debug_assert_eq!(nodes.len(), 1);            nodes.pop().unwrap()        }    }     #[allow(unused)]    pub fn items<'a>(&'a self, cx: <T::Summary as Summary>::Context<'a>) -> Vec<T> {        let mut items = Vec::new();        let mut cursor = self.cursor::<()>(cx);        cursor.next();        while let Some(item) = cursor.item() {            items.push(item.clone());            cursor.next();        }        items    }     pub fn iter(&self) -> Iter<'_, T> {        Iter::new(self)    }     /// A more efficient version of `Cursor::new()` + `Cursor::seek()` + `Cursor::item()`.    ///    /// Only returns the item that exactly has the target match.    #[instrument(skip_all)]    pub fn find_exact<'a, 'slf, D, Target>(        &'slf self,        cx: <T::Summary as Summary>::Context<'a>,        target: &Target,        bias: Bias,    ) -> (D, D, Option<&'slf T>)    where        D: Dimension<'slf, T::Summary>,        Target: SeekTarget<'slf, T::Summary, D>,    {        let tree_end = D::zero(cx).with_added_summary(self.summary(), cx);        let comparison = target.cmp(&tree_end, cx);        if comparison == Ordering::Greater || (comparison == Ordering::Equal && bias == Bias::Right)        {            return (tree_end.clone(), tree_end, None);        }         let mut pos = D::zero(cx);        return match Self::find_recurse::<_, _, true>(cx, target, bias, &mut pos, self) {            Some((item, end)) => (pos, end, Some(item)),            None => (pos.clone(), pos, None),        };    }     /// A more efficient version of `Cursor::new()` + `Cursor::seek()` + `Cursor::item()`    #[instrument(skip_all)]    pub fn find<'a, 'slf, D, Target>(        &'slf self,        cx: <T::Summary as Summary>::Context<'a>,        target: &Target,        bias: Bias,    ) -> (D, D, Option<&'slf T>)    where        D: Dimension<'slf, T::Summary>,        Target: SeekTarget<'slf, T::Summary, D>,    {        let tree_end = D::zero(cx).with_added_summary(self.summary(), cx);        let comparison = target.cmp(&tree_end, cx);        if comparison == Ordering::Greater || (comparison == Ordering::Equal && bias == Bias::Right)        {            return (tree_end.clone(), tree_end, None);        }         let mut pos = D::zero(cx);        return match Self::find_recurse::<_, _, false>(cx, target, bias, &mut pos, self) {            Some((item, end)) => (pos, end, Some(item)),            None => (pos.clone(), pos, None),        };    }     fn find_recurse<'tree, 'a, D, Target, const EXACT: bool>(        cx: <T::Summary as Summary>::Context<'a>,        target: &Target,        bias: Bias,        position: &mut D,        this: &'tree SumTree<T>,    ) -> Option<(&'tree T, D)>    where        D: Dimension<'tree, T::Summary>,        Target: SeekTarget<'tree, T::Summary, D>,    {        match &*this.0 {            Node::Internal {                child_summaries,                child_trees,                ..            } => {                for (child_tree, child_summary) in child_trees.iter().zip(child_summaries) {                    let child_end = position.clone().with_added_summary(child_summary, cx);                     let comparison = target.cmp(&child_end, cx);                    let target_in_child = comparison == Ordering::Less                        || (comparison == Ordering::Equal && bias == Bias::Left);                    if target_in_child {                        return Self::find_recurse::<D, Target, EXACT>(                            cx, target, bias, position, child_tree,                        );                    }                    *position = child_end;                }            }            Node::Leaf {                items,                item_summaries,                ..            } => {                for (item, item_summary) in items.iter().zip(item_summaries) {                    let mut child_end = position.clone();                    child_end.add_summary(item_summary, cx);                     let comparison = target.cmp(&child_end, cx);                    let entry_found = if EXACT {                        comparison == Ordering::Equal                    } else {                        comparison == Ordering::Less                            || (comparison == Ordering::Equal && bias == Bias::Left)                    };                    if entry_found {                        return Some((item, child_end));                    }                     *position = child_end;                }            }        }        None    }     pub fn cursor<'a, 'b, D>(        &'a self,        cx: <T::Summary as Summary>::Context<'b>,    ) -> Cursor<'a, 'b, T, D>    where        D: Dimension<'a, T::Summary>,    {

Lines 1–500 of 1745. Load more