anystack 0.6.0-alpha.3

//! Iterators over [`Frame`]s.

use alloc::{vec, vec::Vec};
use core::{
    fmt,
    iter::FusedIterator,
    slice::{Iter, IterMut},
};

use crate::Frame;

/// Helper function, which is used in both [`Frames`] and [`FramesMut`].
///
/// To traverse the frames, the following algorithm is used:
/// Given a list of iterators, take the last iterator, and use items from it until the iterator has
/// been exhausted. If that is the case (it returned `None`), remove the iterator from the list,
/// and continue with the next iterator until all iterators are exhausted.
///
/// # Example
///
/// ```text
/// 1) Out: - Stack: [A, G]
/// 2) Out: A Stack: [G] [B, C]
/// 3) Out: B Stack: [G] [E] [C, D]
/// 4) Out: C Stack: [G] [E] [D]
/// 4) Out: D Stack: [G] [E]
/// 5) Out: E Stack: [G] [F]
/// 6) Out: F Stack: [G]
/// 7) Out: G Stack: [H]
/// 8) Out: H Stack: -
/// ```
fn next<I: Iterator<Item = T>, T>(iter: &mut Vec<I>) -> Option<T> {
    let out;
    loop {
        let last = iter.last_mut()?;

        if let Some(next) = last.next() {
            out = next;
            break;
        }

        // exhausted, therefore cannot be used anymore.
        iter.pop();
    }

    Some(out)
}

/// Iterator over the [`Frame`] stack of a [`Report`].
///
/// This uses an implementation of the Pre-Order, NLR Depth-First Search algorithm to resolve the
/// tree.
///
/// Use [`Report::frames()`] to create this iterator.
///
/// # Example
///
/// This shows in numbers the index of the different depths, using this it's possible to linearize
/// all frames and sort topologically, meaning that this ensures no child ever is before its parent.
///
/// Iterating the following report will return the frames in alphabetical order:
///
/// ```text
/// A
/// ╰┬▶ B
///  │  ╰┬▶ C
///  │   ╰▶ D
///  ╰▶ E
///     ╰─▶ F
/// G
/// ╰─▶ H
/// ```
///
/// [`Report`]: crate::Report
/// [`Report::frames()`]: crate::Report::frames
#[must_use]
#[derive(Clone)]
pub struct Frames<'r> {
    stack: Vec<Iter<'r, Frame>>,
}

impl<'r> Frames<'r> {
    pub(crate) fn new(frames: &'r [Frame]) -> Self {
        Self {
            stack: vec![frames.iter()],
        }
    }
}

impl<'r> Iterator for Frames<'r> {
    type Item = &'r Frame;

    fn next(&mut self) -> Option<Self::Item> {
        let frame = next(&mut self.stack)?;

        self.stack.push(frame.sources().iter());
        Some(frame)
    }
}

impl FusedIterator for Frames<'_> {}

impl fmt::Debug for Frames<'_> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_list().entries(self.clone()).finish()
    }
}

/// Iterator over the mutable [`Frame`] stack of a [`Report`].
///
/// Use [`Report::frames_mut()`] to create this iterator.
///
/// [`Report`]: crate::Report
/// [`Report::frames_mut()`]: crate::Report::frames_mut
#[must_use]
pub struct FramesMut<'r> {
    stack: Vec<IterMut<'r, Frame>>,
}

impl<'r> FramesMut<'r> {
    pub(crate) fn new(frames: &'r mut [Frame]) -> Self {
        Self {
            stack: vec![frames.iter_mut()],
        }
    }
}

impl<'r> Iterator for FramesMut<'r> {
    type Item = &'r mut Frame;

    fn next(&mut self) -> Option<Self::Item> {
        let frame = next(&mut self.stack)?;
        let frame: *mut Frame = frame;

        // SAFETY:
        // We require both mutable access to the frame for all sources (as a mutable iterator) and
        // we need to return the mutable frame itself. We will never access the same value twice,
        // and only store their mutable iterator until the next `next()` call. This function acts
        // like a dynamic chain of multiple `IterMut`. The borrow checker is unable to prove that
        // subsequent calls to `next()` won't access the same data.
        // NB: It's almost never possible to implement a mutable iterator without `unsafe`.
        unsafe {
            self.stack.push((*frame).sources_mut().iter_mut());

            Some(&mut *frame)
        }
    }
}

impl FusedIterator for FramesMut<'_> {}