nearest/

list.rs

use core::{fmt, iter::FusedIterator, marker::PhantomData};

use crate::{Flat, Patch, emitter::Pos};

/// A linked list of `T` values stored in a [`Region`](crate::Region).
///
/// # Layout
///
/// `#[repr(C)]` — 8 bytes, `align_of::<i32>()` alignment:
///
/// | Offset | Field  | Type  | Description                             |
/// |--------|--------|-------|-----------------------------------------|
/// | 0      | `head` | `i32` | Self-relative offset to first segment   |
/// | 4      | `len`  | `u32` | TOTAL element count across all segments |
///
/// When `len == 0`, `head` is `0` (no valid segment). When non-empty, `head` is
/// a self-relative offset from the `head` field itself to the first `Segment<T>`.
///
/// `NearList<T>` is **not** `Copy` or `Clone` — moving it would invalidate the
/// self-relative offset.
///
/// After [`trim`](crate::Region::trim), all elements live in a single contiguous
/// segment for cache-friendly iteration.
///
/// # Segment chain
///
/// A non-empty list consists of one or more `Segment<T>` nodes linked by
/// self-relative `next` pointers (`next == 0` terminates the chain). Each
/// segment stores a contiguous array of `T` values immediately after its
/// header.
///
/// Mutation operations ([`splice_list`], [`push_front`], [`extend_list`]) may
/// produce multi-segment lists. [`trim`](crate::Region::trim) compacts all
/// segments into one, restoring O(1) indexing and cache-friendly iteration.
///
/// # Soundness
///
/// **Provenance**: Segment walking uses `with_exposed_provenance` to
/// follow self-relative `next` pointers, recovering the allocation's
/// provenance exposed by `AlignedBuf::grow`. Same pattern as `Near<T>`.
///
/// **Invariant**: `len == 0` ⟺ `head == 0`. Enforced by all list-patching
/// methods which write both fields atomically.
///
/// [`splice_list`]: crate::Session::splice_list
/// [`push_front`]: crate::Session::push_front
/// [`extend_list`]: crate::Session::extend_list
#[repr(C)]
pub struct NearList<T> {
  head: i32,
  len: u32,
  _type: PhantomData<T>,
}

// SAFETY: NearList<T> contains only i32, u32, and PhantomData — no Drop, no heap.
// T: Flat bound enables self-sufficient deep_copy/validate that walk segments
// and handle elements. Coinductive trait resolution handles recursive types.
unsafe impl<T: Flat> Flat for NearList<T> {
  unsafe fn deep_copy(&self, p: &mut impl Patch, at: Pos) {
    let len = self.len;
    if len == 0 {
      // SAFETY: Caller guarantees `at` was allocated for `NearList<T>`.
      unsafe { p.patch_list_header::<T>(at, Pos::ZERO, 0) };
      return;
    }
    let seg_pos = p.alloc_segment::<T>(len);
    let values_off = size_of::<Segment<T>>();
    for (i, elem) in self.iter().enumerate() {
      // SAFETY: seg_pos was just allocated with space for `len` elements.
      unsafe { elem.deep_copy(p, seg_pos.offset(values_off + i * size_of::<T>())) };
    }
    // SAFETY: Caller guarantees `at` was allocated for `NearList<T>`.
    unsafe { p.patch_list_header::<T>(at, seg_pos, len) };
  }

  fn validate(addr: usize, buf: &[u8]) -> Result<(), crate::ValidateError> {
    crate::validate::validate_list_impl::<T>(addr, buf)
  }

  fn validate_option(addr: usize, buf: &[u8]) -> Result<(), crate::ValidateError> {
    crate::ValidateError::check::<Option<Self>>(addr, buf)?;
    let disc = buf[addr];
    match disc {
      0 => Ok(()), // None
      1 => {
        let inner = addr + core::mem::offset_of!(Option<Self>, Some.0);
        crate::validate::validate_list_impl::<T>(inner, buf)
      }
      _ => Err(crate::ValidateError::InvalidDiscriminant { addr, value: disc, max: 1 }),
    }
  }
}

/// A contiguous segment of values in a [`NearList`]. Stored in the Region buffer.
///
/// # Layout
///
/// `#[repr(C)]` — 8 bytes header + `len * size_of::<T>()` values:
///
/// | Offset                       | Field     | Type    | Description                          |
/// |------------------------------|-----------|---------|--------------------------------------|
/// | 0                            | `next`    | `i32`   | Self-relative offset to next segment |
/// | 4                            | `len`     | `u32`   | Number of values in this segment     |
/// | `size_of::<Segment<T>>()`    | values... | `[T]`   | Contiguous values                    |
///
/// `next == 0` indicates the end of the segment chain. Values are accessed by
/// pointer arithmetic from the segment address: the first value is at
/// `segment_addr + size_of::<Segment<T>>()`, subsequent values are contiguous
/// at `+ i * size_of::<T>()`.
#[repr(C)]
pub struct Segment<T> {
  pub(crate) next: i32,
  pub(crate) len: u32,
  pub(crate) _values: [T; 0],
}

impl<T: Flat> NearList<T> {
  /// Returns the number of elements.
  ///
  /// # Examples
  ///
  /// ```
  /// use nearest::{Flat, NearList, Region, empty, list};
  ///
  /// #[derive(Flat)]
  /// struct Root { items: NearList<u32> }
  ///
  /// let region = Region::new(Root::make(list([1u32, 2, 3])));
  /// assert_eq!(region.items.len(), 3);
  ///
  /// let empty_region = Region::new(Root::make(empty()));
  /// assert_eq!(empty_region.items.len(), 0);
  /// ```
  #[must_use]
  pub const fn len(&self) -> usize {
    self.len as usize
  }

  /// Returns `true` if the list has no elements.
  ///
  /// # Examples
  ///
  /// ```
  /// use nearest::{Flat, NearList, Region, empty, list};
  ///
  /// #[derive(Flat)]
  /// struct Root { items: NearList<u32> }
  ///
  /// let region = Region::new(Root::make(empty()));
  /// assert!(region.items.is_empty());
  ///
  /// let region = Region::new(Root::make(list([1u32])));
  /// assert!(!region.items.is_empty());
  /// ```
  #[must_use]
  pub const fn is_empty(&self) -> bool {
    self.len == 0
  }

  /// Returns the raw head offset (for internal Session use).
  pub(crate) const fn head_offset(&self) -> i32 {
    self.head
  }

  /// Returns the number of segments in the chain.
  ///
  /// After [`trim`](crate::Region::trim), this is always 0 (empty) or 1.
  ///
  /// # Examples
  ///
  /// ```
  /// use nearest::{Flat, NearList, Region, list};
  ///
  /// #[derive(Flat)]
  /// struct Root { items: NearList<u32> }
  ///
  /// let mut region = Region::new(Root::make(list([1u32, 2, 3])));
  /// assert_eq!(region.items.segment_count(), 1);
  ///
  /// // push_front adds a new segment.
  /// region.session(|s| {
  ///   let items = s.nav(s.root(), |r| &r.items);
  ///   s.push_front(items, 0u32);
  /// });
  /// assert_eq!(region.items.segment_count(), 2);
  ///
  /// // trim consolidates into one segment.
  /// region.trim();
  /// assert_eq!(region.items.segment_count(), 1);
  /// ```
  #[must_use]
  pub fn segment_count(&self) -> usize {
    if self.len == 0 {
      return 0;
    }
    let mut count = 1usize;
    let mut seg_addr =
      core::ptr::from_ref(&self.head).cast::<u8>().addr().wrapping_add_signed(self.head as isize);
    loop {
      // SAFETY: seg_addr points to a valid Segment<T> in the region buffer.
      let seg = unsafe { &*core::ptr::with_exposed_provenance::<Segment<T>>(seg_addr) };
      if seg.next == 0 {
        break;
      }
      seg_addr =
        core::ptr::from_ref(&seg.next).cast::<u8>().addr().wrapping_add_signed(seg.next as isize);
      count += 1;
    }
    count
  }

  /// Returns a reference to the last element, or `None` if empty.
  ///
  /// **O(n)**: requires full traversal of the segment chain to find the
  /// last segment, then indexes its final element.
  ///
  /// # Examples
  ///
  /// ```
  /// use nearest::{Flat, NearList, Region, empty, list};
  ///
  /// #[derive(Flat)]
  /// struct Root { items: NearList<u32> }
  ///
  /// let region = Region::new(Root::make(list([10u32, 20, 30])));
  /// assert_eq!(region.items.last(), Some(&30));
  ///
  /// let region = Region::new(Root::make(empty()));
  /// assert_eq!(region.items.last(), None);
  /// ```
  #[must_use]
  pub fn last(&self) -> Option<&T> {
    if self.len == 0 {
      return None;
    }
    // Walk the segment chain to the last segment.
    let mut seg_addr =
      core::ptr::from_ref(&self.head).cast::<u8>().addr().wrapping_add_signed(self.head as isize);
    loop {
      // SAFETY: seg_addr points to a valid Segment<T> in the region buffer.
      let seg = unsafe { &*core::ptr::with_exposed_provenance::<Segment<T>>(seg_addr) };
      if seg.next == 0 {
        // This is the last segment. Return its final element.
        let last_idx = seg.len as usize - 1;
        let val_addr =
          seg_addr.wrapping_add(size_of::<Segment<T>>()).wrapping_add(last_idx * size_of::<T>());
        // SAFETY: val_addr points to a valid T within the last segment.
        return Some(unsafe { &*core::ptr::with_exposed_provenance::<T>(val_addr) });
      }
      seg_addr =
        core::ptr::from_ref(&seg.next).cast::<u8>().addr().wrapping_add_signed(seg.next as isize);
    }
  }

  /// Returns `true` if the list contains an element equal to the given value.
  ///
  /// # Examples
  ///
  /// ```
  /// use nearest::{Flat, NearList, Region, empty, list};
  ///
  /// #[derive(Flat)]
  /// struct Root { items: NearList<u32> }
  ///
  /// let region = Region::new(Root::make(list([1u32, 2, 3])));
  /// assert!(region.items.contains(&2));
  /// assert!(!region.items.contains(&4));
  ///
  /// let region = Region::new(Root::make(empty()));
  /// assert!(!region.items.contains(&1));
  /// ```
  #[must_use]
  pub fn contains(&self, item: &T) -> bool
  where
    T: PartialEq,
  {
    self.iter().any(|x| x == item)
  }

  /// Returns a reference to the first element, or `None` if empty.
  ///
  /// # Examples
  ///
  /// ```
  /// use nearest::{Flat, NearList, Region, empty, list};
  ///
  /// #[derive(Flat)]
  /// struct Root { items: NearList<u32> }
  ///
  /// let region = Region::new(Root::make(list([10u32, 20])));
  /// assert_eq!(region.items.first(), Some(&10));
  ///
  /// let region = Region::new(Root::make(empty()));
  /// assert_eq!(region.items.first(), None);
  /// ```
  #[must_use]
  pub fn first(&self) -> Option<&T> {
    if self.len == 0 {
      return None;
    }
    // SAFETY: head offset was written by the emitter, pointing to a valid Segment<T>.
    // The first value is at seg_addr + size_of::<Segment<T>>().
    unsafe {
      let addr =
        core::ptr::from_ref(&self.head).cast::<u8>().addr().wrapping_add_signed(self.head as isize);
      let val_ptr =
        core::ptr::with_exposed_provenance::<T>(addr.wrapping_add(size_of::<Segment<T>>()));
      Some(&*val_ptr)
    }
  }

  /// Returns an iterator over the elements.
  ///
  /// Construction is O(1). Within a segment, iteration is contiguous (`ptr.add(1)`).
  /// At segment boundaries, follows `next` pointers to the next segment.
  /// After [`trim`](crate::Region::trim), iteration is pure array traversal.
  ///
  /// # Examples
  ///
  /// ```
  /// use nearest::{Flat, NearList, Region, list};
  ///
  /// #[derive(Flat)]
  /// struct Root { items: NearList<u32> }
  ///
  /// let region = Region::new(Root::make(list([10u32, 20, 30])));
  /// let sum: u32 = region.items.iter().sum();
  /// assert_eq!(sum, 60);
  ///
  /// // Also works with for-in (via IntoIterator for &NearList<T>).
  /// let mut count = 0;
  /// for item in &region.items {
  ///   count += 1;
  ///   assert!(*item >= 10);
  /// }
  /// assert_eq!(count, 3);
  /// ```
  #[must_use]
  pub fn iter(&self) -> NearListIter<'_, T> {
    if self.len == 0 {
      return NearListIter {
        current_value: core::ptr::null(),
        remaining_in_seg: 0,
        current_seg: core::ptr::null(),
        remaining_total: 0,
        _type: PhantomData,
      };
    }
    // SAFETY: head offset was written by the emitter, pointing to a valid Segment<T>.
    let seg_addr =
      core::ptr::from_ref(&self.head).cast::<u8>().addr().wrapping_add_signed(self.head as isize);
    let seg_ptr = core::ptr::with_exposed_provenance::<Segment<T>>(seg_addr);
    // SAFETY: `seg_ptr` points to a valid `Segment<T>` in the region buffer,
    // reached via the head offset written by the emitter.
    let seg = unsafe { &*seg_ptr };
    let val_ptr =
      core::ptr::with_exposed_provenance::<T>(seg_addr.wrapping_add(size_of::<Segment<T>>()));
    NearListIter {
      current_value: val_ptr,
      remaining_in_seg: seg.len,
      current_seg: seg_ptr,
      remaining_total: self.len,
      _type: PhantomData,
    }
  }
}

/// Iterator over the elements of a [`NearList`].
///
/// Within a segment, values are contiguous (pointer increment). At segment
/// boundaries, follows the `next` pointer to the next segment.
///
/// Implements [`ExactSizeIterator`] and [`FusedIterator`]. Does **not**
/// implement [`DoubleEndedIterator`] because `NearList` uses a singly-linked
/// segment chain — reverse traversal would require hidden allocation or
/// O(n) per `next_back()` call, which conflicts with the library's
/// predictable-performance, no-hidden-allocation philosophy. Use
/// [`NearList::last`] for O(segments) access to the final element.
pub struct NearListIter<'a, T: Flat> {
  current_value: *const T,
  remaining_in_seg: u32,
  current_seg: *const Segment<T>,
  remaining_total: u32,
  _type: PhantomData<&'a T>,
}

impl<'a, T: Flat> Iterator for NearListIter<'a, T> {
  type Item = &'a T;

  fn next(&mut self) -> Option<&'a T> {
    if self.remaining_total == 0 {
      return None;
    }

    // If current segment is exhausted, advance to the next segment.
    if self.remaining_in_seg == 0 {
      // SAFETY: remaining_total > 0 guarantees a next segment exists.
      unsafe {
        let seg = &*self.current_seg;
        let next_addr =
          core::ptr::from_ref(&seg.next).cast::<u8>().addr().wrapping_add_signed(seg.next as isize);
        self.current_seg = core::ptr::with_exposed_provenance::<Segment<T>>(next_addr);
        let new_seg = &*self.current_seg;
        self.remaining_in_seg = new_seg.len;
        self.current_value =
          core::ptr::with_exposed_provenance::<T>(next_addr.wrapping_add(size_of::<Segment<T>>()));
      }
    }

    // SAFETY: current_value points to a valid T within the current segment.
    unsafe {
      let val = &*self.current_value;
      self.remaining_total -= 1;
      self.remaining_in_seg -= 1;
      // Advance to the next value in the segment (contiguous).
      // For ZSTs, add(1) is a no-op on the address, which is correct.
      self.current_value = self.current_value.add(1);
      Some(val)
    }
  }

  fn size_hint(&self) -> (usize, Option<usize>) {
    let r = self.remaining_total as usize;
    (r, Some(r))
  }
}

impl<T: Flat> ExactSizeIterator for NearListIter<'_, T> {}

/// `NearListIter` always returns `None` once exhausted — it never resumes
/// yielding elements after `remaining_total` reaches zero.
impl<T: Flat> FusedIterator for NearListIter<'_, T> {}

impl<'a, T: Flat> IntoIterator for &'a NearList<T> {
  type Item = &'a T;
  type IntoIter = NearListIter<'a, T>;

  fn into_iter(self) -> Self::IntoIter {
    self.iter()
  }
}

impl<T: Flat + PartialEq> PartialEq for NearList<T> {
  fn eq(&self, other: &Self) -> bool {
    self.len() == other.len() && self.iter().zip(other.iter()).all(|(a, b)| a == b)
  }
}

impl<T: Flat + Eq> Eq for NearList<T> {}

impl<T: Flat + fmt::Debug> fmt::Debug for NearList<T> {
  fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    f.debug_list().entries(self.iter()).finish()
  }
}

impl<T: Flat + fmt::Display> fmt::Display for NearList<T> {
  fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
    f.write_str("[")?;
    for (i, item) in self.iter().enumerate() {
      if i > 0 {
        f.write_str(", ")?;
      }
      fmt::Display::fmt(item, f)?;
    }
    f.write_str("]")
  }
}

impl<T: Flat> NearList<T> {
  /// Returns a reference to the element at `index`, or `None` if out of bounds.
  ///
  /// **O(1)** when all elements are in a single segment (always true after
  /// [`trim`](crate::Region::trim)). Falls back to O(n) segment walk otherwise.
  ///
  /// # Examples
  ///
  /// ```
  /// use nearest::{Flat, NearList, Region, list};
  ///
  /// #[derive(Flat)]
  /// struct Root { items: NearList<u32> }
  ///
  /// let region = Region::new(Root::make(list([10u32, 20, 30])));
  /// assert_eq!(region.items.get(0), Some(&10));
  /// assert_eq!(region.items.get(2), Some(&30));
  /// assert_eq!(region.items.get(3), None);
  /// ```
  #[must_use]
  pub fn get(&self, index: usize) -> Option<&T> {
    if index >= self.len as usize {
      return None;
    }
    // SAFETY: head offset was written by the emitter, pointing to a valid Segment<T>.
    unsafe {
      let seg_addr =
        core::ptr::from_ref(&self.head).cast::<u8>().addr().wrapping_add_signed(self.head as isize);
      let seg = &*core::ptr::with_exposed_provenance::<Segment<T>>(seg_addr);
      // Fast path: all elements in first segment (always true after trim).
      if (seg.len as usize) > index {
        let val_addr =
          seg_addr.wrapping_add(size_of::<Segment<T>>()).wrapping_add(index * size_of::<T>());
        return Some(&*core::ptr::with_exposed_provenance::<T>(val_addr));
      }
    }
    // Slow path: multi-segment walk.
    self.iter().nth(index)
  }
}

impl<T: Flat> core::ops::Index<usize> for NearList<T> {
  type Output = T;

  /// Access the element at `index`.
  ///
  /// **O(1)** when all elements are in a single segment (always true after
  /// [`trim`](crate::Region::trim)). Falls back to O(n) segment walk otherwise.
  ///
  /// # Panics
  ///
  /// Panics if `index >= self.len()`.
  fn index(&self, index: usize) -> &T {
    self.get(index).expect("NearList index out of bounds")
  }
}