duat_core/buffer/

history.rs

//! The history for a [`Text`].
//!
//! The [`History`] is composed of [`Moment`]s, each having a list of
//! [`Change`]s. Whenever you [`undo`]/[`redo`], you are
//! undoing/redoing a whole [`Moment`], with all of its [`Change`]s,
//! all at once.
//!
//! This permits Vim style undoing (one [`Change`] per [`Moment`]) as
//! well as Kakoune style undoing (multiple [`Change`]s per
//! [`Moment`]).
//!
//! [`undo`]: crate::text::TextMut::undo
//! [`redo`]: crate::text::TextMut::redo
use std::{
    iter::{Chain, Enumerate},
    marker::PhantomData,
    ops::Range,
    sync::{Arc, Mutex},
};

use bincode::{Decode, Encode};
use gap_buf::GapBuffer;

use super::{Point, Text};
use crate::{
    Ns, Ranges,
    buffer::Buffer,
    text::{Strs, TextRange},
    utils::{add_shifts as add, merging_range_by_guess_and_lazy_shift},
};

/// The history of edits, contains all moments.
#[derive(Debug)]
pub struct History {
    // Moments in regard to undoing/redoing.
    new_moment: Moment,
    undo_redo_moments: Vec<Moment>,
    cur_moment: usize,
    // Moments in regard to namespaces.
    unread_moments: Mutex<Vec<(Ns, Moment)>>,
    ranges_to_update: Arc<Mutex<(Vec<(Ns, Ranges)>, usize)>>,
    // The moment where a [`Buffer`] was saved.
    //
    // [`Buffer`]: crate::buffer::Buffer
    saved_moment: Option<usize>,
}

impl History {
    /// Returns a new `History`.
    #[allow(clippy::new_without_default)]
    pub fn new(text: &Strs) -> Self {
        Self {
            new_moment: Moment::new(),
            undo_redo_moments: Vec::new(),
            cur_moment: 0,
            unread_moments: Mutex::new(Vec::new()),
            ranges_to_update: Arc::new(Mutex::new((Vec::new(), text.len()))),
            saved_moment: None,
        }
    }

    /// Adds a [`Change`] to the [`History`].
    pub fn apply_change(
        &mut self,
        guess_i: Option<usize>,
        change: Change<'static, String>,
    ) -> usize {
        let mut ranges_to_update = self.ranges_to_update.lock().unwrap();
        let (ranges_to_update, buf_len) = &mut *ranges_to_update;
        *buf_len = buf_len.saturating_add_signed(change.shift()[0] as isize);

        for (_, ranges) in ranges_to_update.iter_mut() {
            ranges.shift_by(
                change.start().byte(),
                change.added_end().byte() as i32 - change.taken_end().byte() as i32,
            );

            let range = change.added_range();
            ranges.add(range.start.byte()..range.end.byte());
        }

        let unread_moments = self.unread_moments.get_mut().unwrap();
        for (_, moment) in unread_moments.iter_mut() {
            moment.add_change(guess_i, change.clone());
        }

        self.new_moment.add_change(guess_i, change)
    }

    /// Declares that the current moment is complete and starts a
    /// new one.
    pub fn new_moment(&mut self) {
        if self.new_moment.is_empty() {
            return;
        }

        self.undo_redo_moments.truncate(self.cur_moment);

        if let Some(saved_moment) = self.saved_moment
            && saved_moment >= self.cur_moment
        {
            self.saved_moment = None;
        }

        self.undo_redo_moments
            .push(std::mem::take(&mut self.new_moment));
        self.cur_moment += 1;
    }

    /// Redoes the next [`Moment`], returning its [`Change`]s.
    ///
    /// Applying these [`Change`]s in the order that they're given
    /// will result in a correct redoing.
    pub(crate) fn move_forward(
        &mut self,
    ) -> Option<(impl ExactSizeIterator<Item = Change<'_>>, bool)> {
        self.new_moment();
        if self.cur_moment == self.undo_redo_moments.len() {
            None
        } else {
            self.cur_moment += 1;

            let mut ranges_to_update = self.ranges_to_update.lock().unwrap();
            let unread_moments = self.unread_moments.get_mut().unwrap();

            let iter = self.undo_redo_moments[self.cur_moment - 1]
                .iter()
                .enumerate()
                .map(move |(i, change)| {
                    let (ranges_to_update, buf_len) = &mut *ranges_to_update;
                    *buf_len = buf_len.saturating_add_signed(change.shift()[0] as isize);

                    for (_, ranges) in ranges_to_update.iter_mut() {
                        ranges.shift_by(
                            change.start().byte(),
                            change.added_end().byte() as i32 - change.taken_end().byte() as i32,
                        );

                        let range = change.added_range();
                        ranges.add(range.start.byte()..range.end.byte());
                    }

                    for (_, moment) in unread_moments.iter_mut() {
                        moment.add_change(Some(i), change.to_string_change());
                    }

                    change
                });

            let is_saved = self.saved_moment.is_some_and(|m| m == self.cur_moment);
            Some((iter, is_saved))
        }
    }

    /// Undoes a [`Moment`], returning its reversed [`Change`]s.
    ///
    /// These [`Change`]s will already be shifted corectly, such that
    /// applying them in sequential order, without further
    /// modifications, will result in a correct undoing.
    pub(crate) fn move_backwards(
        &mut self,
    ) -> Option<(impl ExactSizeIterator<Item = Change<'_>>, bool)> {
        self.new_moment();
        if self.cur_moment == 0 {
            None
        } else {
            self.cur_moment -= 1;

            let mut ranges_to_update = self.ranges_to_update.lock().unwrap();
            let unread_moments = self.unread_moments.get_mut().unwrap();

            let iter = self.undo_redo_moments[self.cur_moment]
                .iter()
                .undone()
                .enumerate()
                .map(move |(i, change)| {
                    let (ranges_to_update, buf_len) = &mut *ranges_to_update;
                    *buf_len = buf_len.saturating_add_signed(change.shift()[0] as isize);

                    for (_, ranges) in ranges_to_update.iter_mut() {
                        ranges.shift_by(
                            change.start().byte(),
                            change.added_end().byte() as i32 - change.taken_end().byte() as i32,
                        );

                        let range = change.added_range();
                        ranges.add(range.start.byte()..range.end.byte());
                    }

                    for (_, moment) in unread_moments.iter_mut() {
                        moment.add_change(Some(i), change.to_string_change());
                    }

                    change
                });

            let is_saved = self.saved_moment.is_some_and(|m| m == self.cur_moment);
            Some((iter, is_saved))
        }
    }

    /// Declares that the current state of the [`Text`] was saved on
    /// disk.
    pub(super) fn declare_saved(&mut self) {
        self.saved_moment = Some(self.cur_moment)
    }
}

impl<Context> Decode<Context> for History {
    fn decode<D: bincode::de::Decoder<Context = Context>>(
        decoder: &mut D,
    ) -> Result<Self, bincode::error::DecodeError> {
        Ok(History {
            new_moment: Decode::decode(decoder)?,
            undo_redo_moments: Decode::decode(decoder)?,
            cur_moment: Decode::decode(decoder)?,
            unread_moments: Mutex::new(Vec::new()),
            ranges_to_update: Arc::new(Mutex::new((Vec::new(), usize::decode(decoder)?))),
            saved_moment: Decode::decode(decoder)?,
        })
    }
}

bincode::impl_borrow_decode!(History);

impl Encode for History {
    fn encode<E: bincode::enc::Encoder>(
        &self,
        encoder: &mut E,
    ) -> Result<(), bincode::error::EncodeError> {
        self.new_moment.encode(encoder)?;
        self.undo_redo_moments.encode(encoder)?;
        self.cur_moment.encode(encoder)?;
        self.ranges_to_update.lock().unwrap().1.encode(encoder)?;
        self.saved_moment.encode(encoder)
    }
}

/// A moment in history, which may contain changes, or may just
/// contain selections.
///
/// It also contains information about how to print the buffer, so
/// that going back in time is less jarring.
#[derive(Default, Clone, Debug)]
pub struct Moment {
    changes: GapBuffer<Change<'static, String>>,
    shift_state: (usize, [i32; 3]),
}

impl Moment {
    /// Returns a new `Moment`.
    const fn new() -> Self {
        Self {
            changes: GapBuffer::new(),
            shift_state: (0, [0; 3]),
        }
    }
}

impl<Context> Decode<Context> for Moment {
    fn decode<D: bincode::de::Decoder<Context = Context>>(
        decoder: &mut D,
    ) -> Result<Self, bincode::error::DecodeError> {
        Ok(Moment {
            changes: Decode::decode(decoder)?,
            shift_state: Decode::decode(decoder)?,
        })
    }
}

impl<'de, Context> bincode::BorrowDecode<'de, Context> for Moment {
    fn borrow_decode<D: bincode::de::BorrowDecoder<'de, Context = Context>>(
        decoder: &mut D,
    ) -> Result<Self, bincode::error::DecodeError> {
        Ok(Moment {
            changes: Decode::decode(decoder)?,
            shift_state: Decode::decode(decoder)?,
        })
    }
}

impl Encode for Moment {
    fn encode<E: bincode::enc::Encoder>(
        &self,
        encoder: &mut E,
    ) -> Result<(), bincode::error::EncodeError> {
        self.changes.encode(encoder)?;
        self.shift_state.encode(encoder)
    }
}

impl Moment {
    /// First try to merge this change with as many changes as
    /// possible, then add it in.
    pub(crate) fn add_change(
        &mut self,
        guess_i: Option<usize>,
        mut change: Change<'static, String>,
    ) -> usize {
        let new_shift = change.shift();
        let (from, shift) = self.shift_state;

        // The range of changes that will be drained.
        let m_range = merging_range_by_guess_and_lazy_shift(
            (&self.changes, self.changes.len()),
            (guess_i.unwrap_or(0), [change.start(), change.taken_end()]),
            (from, shift, [0; 3], Point::shift_by),
            (Change::start, Change::added_end),
        );

        // If sh_from < c_range.end, I need to shift the changes between the
        // two, so that they match the shifting of the changes before sh_from.
        if from < m_range.end && shift != [0; 3] {
            for change in self.changes.range_mut(from..m_range.end).iter_mut() {
                change.shift_by(shift);
            }
        // Otherwise, the shifting will happen in reverse, and `from`
        // will be moved backwards until the point where m_range ends.
        // This is better for localized Changes.
        } else if from > m_range.end && shift != [0; 3] {
            for change in self.changes.range_mut(m_range.end..from).iter_mut() {
                change.shift_by(shift.map(|i| -i));
            }
        }

        match m_range.len() {
            1 => {
                let old = std::mem::replace(&mut self.changes[m_range.start], change);
                self.changes[m_range.start].try_merge(old);
            }
            _ => {
                let changes: Vec<_> = self.changes.drain(m_range.clone()).collect();
                for c in changes.into_iter().rev() {
                    change.try_merge(c);
                }
                self.changes.insert(m_range.start, change);
            }
        }

        if m_range.start + 1 < self.changes.len() {
            self.shift_state = (m_range.start + 1, add(shift, new_shift));
        } else {
            self.shift_state = (0, [0; 3]);
        }

        m_range.start
    }

    /// An [`ExactSizeIterator`] over the [`Change`]s in this
    /// `Moment`.
    pub fn iter(&self) -> Changes<'_> {
        Changes {
            moment: self,
            iter: self.changes.iter().enumerate(),
            undo_shift: None,
        }
    }

    /// Returns the number of [`Change`]s in this `Moment`.
    pub fn len(&self) -> usize {
        self.changes.len()
    }

    /// Wether there are any [`Change`]s in this `Moment`.
    ///
    /// This can happen when creating a [`Moment::default`].
    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }
}

/// A change in a buffer, with a start, taken text, and added text.
#[derive(Default, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
pub struct Change<'h, S = &'h str> {
    start: [i32; 3],
    added: S,
    taken: S,
    added_end: [i32; 3],
    taken_end: [i32; 3],
    _ghost: PhantomData<&'h str>,
}

impl Change<'static, String> {
    /// Returns a new [Change].
    pub fn new(edit: impl ToString, range: Range<Point>, text: &Text) -> Self {
        let added = {
            let edit = edit.to_string();
            // A '\n' must be kept at the end, no matter what.
            if (range.start == text.end_point() || range.end == text.end_point())
                && !edit.ends_with('\n')
            {
                edit + "\n"
            } else {
                edit
            }
        };

        let taken = text[range.clone()].to_string();
        let added_end = add(
            range.start.as_signed(),
            Point::end_point_of(&added).as_signed(),
        );
        Change {
            start: range.start.as_signed(),
            added,
            taken,
            added_end,
            taken_end: range.end.as_signed(),
            _ghost: PhantomData,
        }
    }

    /// Returns a copyable [`Change`].
    pub fn as_ref(&self) -> Change<'_, &str> {
        Change {
            start: self.start,
            added: &self.added,
            taken: &self.taken,
            added_end: self.added_end,
            taken_end: self.taken_end,
            _ghost: PhantomData,
        }
    }

    /// In this function, it is assumed that `self` happened
    /// _after_ `newer`.
    ///
    /// If the merger fails, the older [`Change`] will be returned;
    pub fn try_merge(&mut self, mut older: Self) {
        if has_start_of(older.added_range(), self.taken_range()) {
            let fixed_end = older.added_end().min(self.taken_end());

            let start = sub(self.start, older.start);
            let end = sub(fixed_end.as_signed(), older.start);
            let range = start[0] as usize..end[0] as usize;
            older.added.replace_range(range, &self.added);

            let range = (fixed_end.byte() - self.start[0] as usize)..;

            older.taken.push_str(&self.taken[range]);

            *self = older;
        } else if has_start_of(self.taken_range(), older.added_range()) {
            let fixed_end = self.taken_end().min(older.added_end());

            let start = sub(older.start, self.start);
            let end = sub(fixed_end.as_signed(), self.start);
            let range = start[0] as usize..end[0] as usize;
            self.taken.replace_range(range, &older.taken);

            let range = (fixed_end.byte() - older.start[0] as usize)..;

            self.added.push_str(&older.added[range]);
        } else {
            panic!("Changes chosen that don't interact");
        }
        self.added_end = add(self.start, Point::end_point_of(&self.added).as_signed());
        self.taken_end = add(self.start, Point::end_point_of(&self.taken).as_signed());
    }
}

impl<'h> Change<'h> {
    /// Creates a [`Change<String>`] from a [`Change<&str>`].
    pub fn to_string_change(&self) -> Change<'static, String> {
        Change {
            start: self.start,
            added: self.added.to_string(),
            taken: self.taken.to_string(),
            added_end: self.added_end,
            taken_end: self.taken_end,
            _ghost: PhantomData,
        }
    }

    /// Returns a new copyable [`Change`] from an insertion.
    pub fn str_insert(added_str: &'h str, start: Point) -> Self {
        Self {
            start: start.as_signed(),
            added: added_str,
            taken: "",
            added_end: (start + Point::end_point_of(added_str)).as_signed(),
            taken_end: start.as_signed(),
            _ghost: PhantomData,
        }
    }
}

impl<'s, S: std::borrow::Borrow<str>> Change<'s, S> {
    /// Returns a reversed version of this [`Change`].
    pub fn reverse(self) -> Self {
        Self {
            start: self.start,
            added: self.taken,
            taken: self.added,
            added_end: self.taken_end,
            taken_end: self.added_end,
            _ghost: PhantomData,
        }
    }

    /// Gets a [`Range<Point>`], from the start to the end of the
    /// affected lines.
    ///
    /// For example, if you make an edit that transforms lines `1..=3`
    /// to lines `1..=5`, this function will return a [`Range`] that
    /// starts at the beginning of line 1, and ends at the end of line
    /// 5.
    ///
    /// # Note
    ///
    /// This end of this range will come _after_ the last `\n`,
    /// which means that, in that example, said point would have a
    /// [`Point::line`] value equal to 6, _not_ 5, since it
    /// represents both the end of line 5, and the beginning of line
    /// 6.
    #[track_caller]
    pub fn line_range(&self, strs: &Strs) -> Range<Point> {
        let full = strs.full();
        let start = full.point_at_coords(self.start[2] as usize, 0);
        if self.added_end[2] as usize == full.end_point().line() {
            start..full.end_point()
        } else {
            let end_line = full.line(self.added_end[2] as usize);
            start..end_line.range().end
        }
    }

    /// The [`Point`] at the start of the change.
    pub fn start(&self) -> Point {
        to_point(self.start)
    }

    /// Returns the end of the `Change`, before it was applied.
    pub fn taken_end(&self) -> Point {
        to_point(self.taken_end)
    }

    /// Returns the end of the `Change`, after it was applied.
    pub fn added_end(&self) -> Point {
        to_point(self.added_end)
    }

    /// Returns the taken [`Range`].
    pub fn taken_range(&self) -> Range<Point> {
        self.start()..self.taken_end()
    }

    /// Returns the added [`Range`].
    pub fn added_range(&self) -> Range<Point> {
        self.start()..self.added_end()
    }

    /// The text that was taken on this `Change`.
    pub fn added_str(&self) -> &str {
        self.added.borrow()
    }

    /// The text that was added by this `Change`.
    pub fn taken_str(&self) -> &str {
        self.taken.borrow()
    }

    /// The ending byte column before this `Change` took place.
    ///
    /// You shouldn't call `change.end_point().byte_col(strs)` because
    /// that will calculate the byte column with the new state of the
    /// [`Text`], when you should be doing so with the _old_ state.
    ///
    /// This function does that for you.
    pub fn taken_byte_col(&self, strs: &Strs) -> usize {
        let taken_str = self.taken_str();
        if taken_str.ends_with('\n') {
            return 0;
        }

        let mut lines = taken_str.split_inclusive('\n');
        let len = lines.next_back().map(str::len).unwrap_or(0);

        if taken_str.contains('\n') {
            len
        } else {
            self.start().byte_col(strs) + len
        }
    }

    /// The ending char column before thiss `Change` took place.
    ///
    /// You shouldn't call `change.end_point().char_col(strs)` because
    /// that will calculate the byte column with the new state of the
    /// [`Text`], when you should be doing so with the _old_ state.
    ///
    /// This function does that for you.
    pub fn taken_char_col(&self, strs: &Strs) -> usize {
        let taken_str = self.taken_str();
        if taken_str.ends_with('\n') {
            return 0;
        }

        let mut lines = taken_str.split_inclusive('\n');
        let len = lines.next_back().into_iter().flat_map(str::chars).count();

        if taken_str.contains('\n') {
            len
        } else {
            self.start().char_col(strs) + len
        }
    }

    /// The total shift caused by this `Change`.
    pub fn shift(&self) -> [i32; 3] {
        [
            self.added_end[0] - self.taken_end[0],
            self.added_end[1] - self.taken_end[1],
            self.added_end[2] - self.taken_end[2],
        ]
    }

    /// Shifts the `Change` by a "signed point".
    pub(crate) fn shift_by(&mut self, shift: [i32; 3]) {
        self.start = add(self.start, shift);
        self.added_end = add(self.added_end, shift);
        self.taken_end = add(self.taken_end, shift);
    }
}

impl<'s, S: std::fmt::Debug> std::fmt::Debug for Change<'s, S> {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        struct DebugArray([i32; 3]);

        impl std::fmt::Debug for DebugArray {
            fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
                write!(f, "{:?}", self.0)
            }
        }

        f.debug_struct("Change")
            .field("start", &DebugArray(self.start))
            .field("added", &self.added)
            .field("taken", &self.taken)
            .field("added_end", &DebugArray(self.added_end))
            .field("taken_end", &DebugArray(self.taken_end))
            .field("_ghost", &self._ghost)
            .finish()
    }
}

impl<Context> Decode<Context> for Change<'static, String> {
    fn decode<D: bincode::de::Decoder<Context = Context>>(
        decoder: &mut D,
    ) -> Result<Self, bincode::error::DecodeError> {
        Ok(Self {
            start: Decode::decode(decoder)?,
            added: Decode::decode(decoder)?,
            taken: Decode::decode(decoder)?,
            added_end: Decode::decode(decoder)?,
            taken_end: Decode::decode(decoder)?,
            _ghost: PhantomData,
        })
    }
}

impl<'de, Context> bincode::BorrowDecode<'de, Context> for Change<'static, String> {
    fn borrow_decode<D: bincode::de::BorrowDecoder<'de, Context = Context>>(
        decoder: &mut D,
    ) -> Result<Self, bincode::error::DecodeError> {
        Ok(Self {
            start: Decode::decode(decoder)?,
            added: Decode::decode(decoder)?,
            taken: Decode::decode(decoder)?,
            added_end: Decode::decode(decoder)?,
            taken_end: Decode::decode(decoder)?,
            _ghost: PhantomData,
        })
    }
}

impl Encode for Change<'static, String> {
    fn encode<E: bincode::enc::Encoder>(
        &self,
        encoder: &mut E,
    ) -> Result<(), bincode::error::EncodeError> {
        Encode::encode(&self.start, encoder)?;
        Encode::encode(&self.added, encoder)?;
        Encode::encode(&self.taken, encoder)?;
        Encode::encode(&self.added_end, encoder)?;
        Encode::encode(&self.taken_end, encoder)?;
        Ok(())
    }
}

impl Buffer {
    /// Get the latest [`Moment`] for a given [namespace]
    ///
    /// This `Moment` contains every change that took place since the
    /// last call with the same `Ns`. On the first call, it is assumed
    /// that you don't care about previous [`Change`]s, so the
    /// returned `Moment` will be empty.
    ///
    /// This means that, in order to use this properly, you might want
    /// to add a hook like this:
    ///
    /// ```rust
    /// # duat_core::doc_duat!(duat);
    /// use duat::prelude::*;
    /// let my_plugin_ns = Ns::new();
    ///
    /// hook::add::<BufferOpened>(move |pa, buffer| _ = buffer.read(pa).moment_for(my_plugin_ns));
    /// ```
    ///
    /// This way, you "register" the [`Buffer`], telling it "yes, I
    /// henceforth care about the future `Changes`".
    ///
    /// # Note: Why is this necessary?
    ///
    /// You might reason that the first call to this function should
    /// return a [`Moment`] with all prior [`Change`]s.
    ///
    /// However, one thing to note is that
    ///
    /// [namespace]: crate::Ns
    pub fn moment_for(&self, ns: Ns) -> Moment {
        let mut unread = self.history.unread_moments.lock().unwrap();
        if let Some((_, moment)) = unread.iter_mut().find(|(other, _)| *other == ns) {
            std::mem::take(moment)
        } else {
            unread.push((ns, Moment::new()));
            Moment::new()
        }
    }

    /// Returns a struct that keeps track of which byte ranges need to
    /// be updated for a given [`Ns`].
    pub fn ranges_to_update_for(&self, ns: Ns) -> RangesToUpdate {
        let mut ranges_to_update = self.history.ranges_to_update.lock().unwrap();
        let (ranges_to_update, _) = &mut *ranges_to_update;

        let idx = if let Some(idx) = ranges_to_update
            .iter_mut()
            .position(|(other, _)| *other == ns)
        {
            idx
        } else {
            ranges_to_update.push((ns, Ranges::new(0..self.text.len())));
            ranges_to_update.len() - 1
        };

        RangesToUpdate {
            list: self.history.ranges_to_update.clone(),
            idx,
        }
    }
}

/// If `lhs` contains the start of `rhs`.
fn has_start_of(lhs: Range<Point>, rhs: Range<Point>) -> bool {
    lhs.start <= rhs.start && rhs.start <= lhs.end
}

/// Subtracts two `i32` arrays.
fn sub(lhs: [i32; 3], rhs: [i32; 3]) -> [i32; 3] {
    [lhs[0] - rhs[0], lhs[1] - rhs[1], lhs[2] - rhs[2]]
}

/// Converts an `[i32; 3]` to a [`Point`].
fn to_point(signed: [i32; 3]) -> Point {
    Point::from_raw(signed[0] as usize, signed[1] as usize, signed[2] as usize)
}

/// An [`Iterator`] over the [`Change`]s of a [`Moment`].
#[doc(hidden)]
#[derive(Debug, Clone)]
pub struct Changes<'m> {
    moment: &'m Moment,
    iter: Enumerate<
        Chain<
            std::slice::Iter<'m, Change<'static, String>>,
            std::slice::Iter<'m, Change<'static, String>>,
        >,
    >,
    undo_shift: Option<[i32; 3]>,
}

impl<'m> Changes<'m> {
    /// Converts this [`Iterator`] to one over the undone version of
    /// the [`Change`]s.
    ///
    /// It also resets iteration to the start, so that you aren't
    /// iterating over "done" and "undone" versions of the `Change`s
    /// at once.
    ///
    /// Normally, [`Change::taken_str`] is the `&str` that was taken
    /// from the [`Text`] by this [`Change`]. This method assumes that
    /// you are undoing changes, so the `Change::taken_str` will now
    /// be the `&str` that was _added_ after the `Change`, and
    /// [`Change::added_str`] will be the `&str` that was taken.
    ///
    /// This method can be useful if you want to modify a [`Strs`] in
    /// order to check out what it used to look like.
    pub fn undone(self) -> Self {
        Self {
            iter: self.moment.changes.iter().enumerate(),
            undo_shift: Some([0; 3]),
            ..self
        }
    }
}

impl<'m> Iterator for Changes<'m> {
    type Item = Change<'m>;

    fn next(&mut self) -> Option<Self::Item> {
        let change = self.iter.next().map(|(i, change)| {
            let (from, shift) = self.moment.shift_state;
            let mut change = change.as_ref();
            if i >= from {
                change.shift_by(shift);
            }
            change
        })?;

        Some(if let Some(undo_shift) = self.undo_shift.as_mut() {
            let mut change = change.reverse();
            change.shift_by(*undo_shift);
            *undo_shift = add(*undo_shift, change.shift());

            change
        } else {
            change
        })
    }

    fn size_hint(&self) -> (usize, Option<usize>) {
        self.iter.size_hint()
    }
}

impl<'h> ExactSizeIterator for Changes<'h> {}

/// A list of [`Range<usize>`]s of byte indices in a [`Buffer`] that
/// need to be updated.
///
/// The recommended way to use this struct is the following:
///
/// - Firstly, this should all probably happen in the
///   [`BufferUpdated`] hook, which is called right before printing to
///   the screen.
/// - In it, you can call [`Handle::full_printed_range`] or
///   [`Handle::printed_line_ranges`]. This is to get only the ranges
///   that are visible, conserving cpu resources.
/// - Then, with the received ranges, you can call
///   [`RangesToUpdate::cutoff`], [`intersecting`], or
///   [`select_from`], in order to filter out which ranges need to be
///   updated.
/// - If updating the ranges was successfull, you can call
///   [`RangesToUpdate::update_on`] or [`update_intersecting`], in
///   order to declare those ranges as updated, removing them from the
///   list.
///
/// This is the general standardized loop which allows efficient
/// plugins to update things only when necessary.
///
/// Some things to note:
///
/// - [`Change`]s applied to the `Buffer`'s [`Text`] are automatically
///   added to the `RangesToUpdate`.
/// - By calling `Handle::printed_line_ranges` and passing the list to
///   `RangesToUpdate::select_from`, you can effectively obtain all
///   lines that have changed on screen, which is a frequently used
///   pattern.
///
/// [`BufferUpdated`]: crate::hook::BufferUpdated
/// [`Handle::full_printed_range`]: crate::context::Handle::full_printed_range
/// [`Handle::printed_line_ranges`]: crate::context::Handle::printed_line_ranges
/// [`intersecting`]: RangesToUpdate::intersecting
/// [`select_from`]: RangesToUpdate::select_from
/// [`update_intersecting`]: RangesToUpdate::update_intersecting
pub struct RangesToUpdate {
    list: Arc<Mutex<(Vec<(Ns, Ranges)>, usize)>>,
    idx: usize,
}

impl RangesToUpdate {
    /// Adds ranges to the list of those that need updating.
    ///
    /// Later on, when duat prints on a range that intersects with
    /// these, you can call [`Handle::full_printed_range`] or
    /// [`Handle::printed_line_ranges`] in order to get visible
    /// ranges, and then call [`RangesToUpdate::cutoff`], or
    /// [`intersecting`], or [`select_from`], in order to get the
    /// ranges that need updating, which will include these ones that
    /// were added by this method, as well as those relating to the
    /// changes that took place in the [`Buffer`].
    ///
    /// Returns `true` if any range was added at all.
    ///
    /// [`Handle::full_printed_range`]: crate::context::Handle::full_printed_range
    /// [`Handle::printed_line_ranges`]: crate::context::Handle::printed_line_ranges
    /// [`intersecting`]: Self::intersecting
    /// [`select_from`]: Self::select_from
    #[track_caller]
    pub fn add_ranges(&self, to_add: impl IntoIterator<Item = impl TextRange>) -> bool {
        let mut ranges = self.list.lock().unwrap();
        let (ranges, buf_len) = &mut *ranges;
        let (_, ranges) = &mut ranges[self.idx];

        let mut has_changed = false;
        for range in to_add {
            has_changed |= ranges.add(range.to_range(*buf_len));
        }
        has_changed
    }

    /// Declares that the ranges given by the iterator have been
    /// updated.
    ///
    /// The visible iterator here should come from one of the methods
    /// on the [`Handle<Buffer>`] which returns some list of visible
    /// ranges. These include [`Handle::full_printed_range`] or
    /// [`Handle::printed_line_ranges`]. You can, of course, also
    /// feed only part of these lists, or some other arbitrary
    /// range, in order to declare those updated too.
    ///
    /// This function will then assume that you have successfully
    /// updated the ranges and will cut these out of the list. This
    /// will remove the intersections between the ranges that need to
    /// be updated and those of the iterator.
    ///
    /// It will _not_ completely remove ranges that partially
    /// intersect those of the iterator, only truncating them. If you
    /// want that behavior, see [`update_intersecting`]
    ///
    /// [`Handle<Buffer>`]: crate::context::Handle
    /// [`Handle::full_printed_range`]: crate::context::Handle::full_printed_range
    /// [`Handle::printed_line_ranges`]: crate::context::Handle::printed_line_ranges
    /// [`update_intersecting`]: Self::update_intersecting
    pub fn update_on(&self, visible: impl IntoIterator<Item = impl TextRange>) -> bool {
        let mut ranges = self.list.lock().unwrap();
        let (ranges, _) = &mut *ranges;
        let (_, ranges) = &mut ranges[self.idx];

        let mut has_changed = false;
        for range in visible {
            let range = range.to_range(u32::MAX as usize);
            has_changed |= ranges.remove_on(range).count() > 0;
        }
        has_changed
    }

    /// Declares that any range intersecting with any of those on the
    /// iterator has been updated.
    ///
    /// The visible iterator here should come from one of the methods
    /// on the [`Handle<Buffer>`] which returns some list of visible
    /// ranges. These include [`Handle::full_printed_range`] or
    /// [`Handle::printed_line_ranges`]. You can, of course, also
    /// feed only part of these lists, or some other arbitrary
    /// range, in order to declare those updated too.
    ///
    /// If you want a method that only removes the intersection with
    /// the ranges that need updating, see [`update_on`].
    ///
    /// [`Handle<Buffer>`]: crate::context::Handle
    /// [`Handle::full_printed_range`]: crate::context::Handle::full_printed_range
    /// [`Handle::printed_line_ranges`]: crate::context::Handle::printed_line_ranges
    /// [`update_on`]: Self::update_on
    pub fn update_intersecting(&self, visible: impl IntoIterator<Item = impl TextRange>) -> bool {
        let mut ranges = self.list.lock().unwrap();
        let (ranges, _) = &mut *ranges;
        let (_, ranges) = &mut ranges[self.idx];

        let mut has_changed = false;
        for range in visible {
            let range = range.to_range(u32::MAX as usize);
            has_changed |= ranges.remove_intersecting(range).count() > 0;
        }
        has_changed
    }

    /// Returns a list of intersections between the ranges that need
    /// updating and those from an iterator.
    ///
    /// The visible iterator here should come from one of the methods
    /// on the [`Handle<Buffer>`] which returns some list of visible
    /// ranges. These include [`Handle::full_printed_range`] or
    /// [`Handle::printed_line_ranges`]. You can, of course, also
    /// feed only part of these lists, or some other arbitrary
    /// range, in order to declare those updated too.
    ///
    /// Note that this returns only the intersecting bits. If you want
    /// a list of all ranges that at least partially intersect, see
    /// [`intersecting`]. If you want to do the opposite, i.e., select
    /// all ranges from the iterator that intersect with those from
    /// the list, see [`select_from`].
    ///
    /// This method is useful if you don't need update full lines,
    /// since it will only care about the ranges that have actually
    /// changed, which aren't full lines most of the time.
    /// [`select_from`] is more useful for updating full lines, since
    /// you can generate a list of printed lines from
    /// [`Handle::printed_line_ranges`], and select from those
    /// only the ranges that have had changes in them. This pattern is
    /// used, for example, by `duat-treesitter`.
    ///
    /// [`Handle<Buffer>`]: crate::context::Handle
    /// [`Handle::full_printed_range`]: crate::context::Handle::full_printed_range
    /// [`Handle::printed_line_ranges`]: crate::context::Handle::printed_line_ranges
    /// [`intersecting`]: Self::intersecting
    /// [`select_from`]: Self::select_from
    pub fn cutoff(&self, list: impl IntoIterator<Item = impl TextRange>) -> Vec<Range<usize>> {
        let mut ranges = self.list.lock().unwrap();
        let (ranges, _) = &mut *ranges;
        let (_, ranges) = &mut ranges[self.idx];

        list.into_iter()
            .flat_map(|range| ranges.iter_over(range.to_range(u32::MAX as usize)))
            .collect()
    }

    /// Returns a list of all ranges that intersect with those from an
    /// iterator.
    ///
    /// The visible iterator here should come from one of the methods
    /// on the [`Handle<Buffer>`] which returns some list of visible
    /// ranges. These include [`Handle::full_printed_range`] or
    /// [`Handle::printed_line_ranges`]. You can, of course, also
    /// feed only part of these lists, or some other arbitrary
    /// range, in order to declare those updated too.
    ///
    /// Note that this returns the full ranges, not just the parts
    /// that intersect. If you want a list of only the
    /// intersections, see [`cutoff`]. If you want to select the
    /// ranges in the iterator that intersect with those from the
    /// list, see [`select_from`].
    ///
    /// [`Handle<Buffer>`]: crate::context::Handle
    /// [`Handle::full_printed_range`]: crate::context::Handle::full_printed_range
    /// [`Handle::printed_line_ranges`]: crate::context::Handle::printed_line_ranges
    /// [`cutoff`]: Self::cutoff
    /// [`select_from`]: Self::select_from
    pub fn intersecting(
        &self,
        list: impl IntoIterator<Item = impl TextRange>,
    ) -> Vec<Range<usize>> {
        let mut ranges = self.list.lock().unwrap();
        let (ranges, _) = &mut *ranges;
        let (_, ranges) = &mut ranges[self.idx];

        let mut intersecting = Vec::new();

        // There will almost never be more than 50 or so ranges in here, so
        // it's ok to be a little inefficient.
        // Feel free to optimize this if you wish to.
        for range in list {
            for range in ranges.iter_intersecting(range.to_range(u32::MAX as usize)) {
                if !intersecting.contains(&range) {
                    intersecting.push(range);
                }
            }
        }

        intersecting.sort_unstable_by(|lhs, rhs| lhs.start.cmp(&rhs.start));
        intersecting
    }

    /// Filters an iterator to a list of ranges that intersect with
    /// those that need updating.
    ///
    /// The visible iterator here should come from one of the methods
    /// on the [`Handle<Buffer>`] which returns some list of visible
    /// ranges. These include [`Handle::full_printed_range`] or
    /// [`Handle::printed_line_ranges`]. You can, of course, also
    /// feed only part of these lists, or some other arbitrary
    /// range, in order to declare those updated too.
    ///
    /// This method is really useful if you want to update on full
    /// lines, but only do so if the lines have actually changed. If
    /// the lines have had changes, those will be in the
    /// [`RangesToUpdate`]. This method will check if the range of a
    /// line intersects with the ranges that need updating. If that is
    /// the case, that line will be kept in the returned [`Vec`].
    ///
    /// If you want a method that returns only the ranges that have
    /// actually changed, check out [`cutoff`]. If you want a method
    /// that that returns any range from the list that intersects with
    /// those of the iterator, check out [`intersecting`].
    ///
    /// [`Handle<Buffer>`]: crate::context::Handle
    /// [`Handle::full_printed_range`]: crate::context::Handle::full_printed_range
    /// [`Handle::printed_line_ranges`]: crate::context::Handle::printed_line_ranges
    /// [`cutoff`]: Self::cutoff
    /// [`intersecting`]: Self::intersecting
    pub fn select_from(&self, list: impl IntoIterator<Item = impl TextRange>) -> Vec<Range<usize>> {
        let mut ranges = self.list.lock().unwrap();
        let (ranges, _) = &mut *ranges;
        let (_, ranges) = &mut ranges[self.idx];

        // There will almost never be more than 50 or so ranges in here, so
        // it's ok to be a little inefficient.
        // Feel free to optimize this if you wish to.
        list.into_iter()
            .filter_map(|range| {
                let range = range.to_range(u32::MAX as usize);
                ranges
                    .iter_intersecting(range.clone())
                    .next()
                    .map(|_| range)
            })
            .collect()
    }
}

impl std::fmt::Debug for RangesToUpdate {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("RangesToUpdate")
            .field("ranges", &*self.list.lock().unwrap())
            .finish_non_exhaustive()
    }
}