leveldb/database/

iterator.rs

//! LevelDB iterators
//!
//! Iteration is one of the most important parts of LevelDB. This module provides
//! Iterators to iterate over key, values and pairs of both.
//!
//! Use the `Iterable` trait methods to create iterator instances. For convenience,
//! various Iterator type aliases are provided.
//!
//! Furthermore, policies can be used to control iteration behavior:
//!
//! ```ignore
//! // Basic iterator with default policy
//! let iter: KeyIterator<'_> = database.iter(ReadOptions::new());
//!
//! // Iterator with custom policy
//! let policy = BoundedKeyPolicy::new(Some(start_key), Some(end_key));
//! let bounded_iter: EntryIterator<'_, _> = database.iter_with_policy(ReadOptions::new(), policy);
//! ```
use super::Database;
use super::error::Error;
use super::options::{ReadOptions, c_readoptions};
use super::slice::Slice;
use crate::binding::{
    leveldb_create_iterator, leveldb_iter_destroy, leveldb_iter_get_error, leveldb_iter_key,
    leveldb_iter_next, leveldb_iter_prev, leveldb_iter_seek, leveldb_iter_seek_to_first,
    leveldb_iter_seek_to_last, leveldb_iter_valid, leveldb_iter_value, leveldb_iterator_t,
    leveldb_readoptions_destroy,
};
use libc::{c_char, size_t};
use std::iter;
use std::marker::PhantomData;

#[allow(missing_docs)]
struct RawIterator {
    ptr: *mut leveldb_iterator_t,
}

#[allow(missing_docs)]
impl Drop for RawIterator {
    fn drop(&mut self) {
        unsafe { leveldb_iter_destroy(self.ptr) }
    }
}

/// Marker types of iterators return key only
pub struct KeyType;
/// Marker types of iterators return value only
pub struct ValueType;
/// Marker types of iterators return key & value pair
pub struct EntryType;

/// Marker types for iterating direction: front to back through block data
pub struct Forward;
/// Marker types for iterating direction: back to front through block data
pub struct Backward;

/// Trait for providing context for policy to make decisions
pub trait Context<'a> {
    /// Get the current key as a slice that borrows from the iterator
    ///
    /// # Safety
    ///
    /// ## Iterator Validity Requirement
    /// Use `valid()` to check iterator state before calling this method.
    ///
    /// ## Lifetime Safety
    /// The returned slice borrows data directly from the LevelDB iterator without copying.
    /// The data is only valid until the iterator is advanced to the next position or destroyed.
    ///
    /// The caller must ensure that the returned slice does not outlive the iterator
    /// or any operation that would advance the iterator (such as calling `next()`, `seek()`, etc.).
    /// To keep the data longer, the slice should be cloned.
    ///
    /// ## Performance
    /// This method provides zero-copy access to LevelDB data for maximum performance.
    /// Get the current key as a slice
    unsafe fn key(&self) -> Option<Slice<'a>>;

    /// Get the current value as a slice that borrows from the iterator
    ///
    /// # Safety
    ///
    /// ## Iterator Validity Requirement
    /// Use `valid()` to check iterator state before calling this method.
    ///
    /// ## Lifetime Safety
    /// The returned slice borrows data directly from the LevelDB iterator without copying.
    /// The data is only valid until the iterator is advanced to the next position or destroyed.
    ///
    /// The caller must ensure that the returned slice does not outlive the iterator
    /// or any operation that would advance the iterator (such as calling `next()`, `seek()`, etc.).
    /// To keep the data longer, the slice should be cloned.
    ///
    /// ## Performance
    /// This method provides zero-copy access to LevelDB data for maximum performance.
    unsafe fn value(&self) -> Option<Slice<'a>>;

    /// Get the current key-value pair as slices that borrow from the iterator
    ///
    /// # Safety
    ///
    /// ## Iterator Validity Requirement
    /// Use `valid()` to check iterator state before calling this method.
    ///
    /// ## Lifetime Safety
    /// The returned slices borrow data directly from the LevelDB iterator without copying.
    /// The data is only valid until the iterator is advanced to the next position or destroyed.
    ///
    /// The caller must ensure that the returned slices do not outlive the iterator
    /// or any operation that would advance the iterator (such as calling `next()`, `seek()`, etc.).
    /// To keep the data longer, the slice should be cloned.
    ///
    /// ## Performance
    /// This method provides zero-copy access to LevelDB data for maximum performance.
    unsafe fn entry(&self) -> Option<(Slice<'a>, Slice<'a>)>;
}

/// Trait for LevelDB iterator operations
pub trait LevelDBIterator<'a>: Context<'a> {
    /// Check if iterator is valid
    fn valid(&self) -> bool;

    /// Seek to specific key
    fn seek(&self, key: &Slice);

    /// Seek to the first key
    fn seek_to_first(&self);

    /// Seek to the last key
    fn seek_to_last(&self);

    /// Get the error message if the iterator is invalid
    fn get_error(&self) -> Option<Error>;
}

/// Policy for controlling iterator behavior
///
/// This trait defines how iterators should behave during iteration,
/// including when to stop and whether to seek to the beginning at start.
pub trait Policy {
    /// Determines if iteration should continue based on current context
    fn should_continue(&self, context: &dyn Context) -> bool;

    /// Determines if iterator should seek to beginning at start, default is true
    fn should_seek_begin(&self) -> bool {
        true
    }
}

/// Default iteration policy with no bounds (iterates over all data)
pub struct DefaultPolicy;

impl DefaultPolicy {
    pub fn new() -> Self {
        Self
    }
}

impl Default for DefaultPolicy {
    fn default() -> Self {
        Self::new()
    }
}

impl Policy for DefaultPolicy {
    fn should_continue(&self, _context: &dyn Context) -> bool {
        true
    }
}

/// Policy for bounded key iteration with from/to bounds.
///
/// This policy restricts iteration to a specific key range.
///
/// **Important**: When using `BoundedKeyPolicy`, the method `seek()` must be called explicitly
/// before starting iteration. This policy does not automatically seek to the beginning position.
pub struct BoundedKeyPolicy<'a> {
    from: Option<Slice<'a>>,
    to: Option<Slice<'a>>,
}

impl<'a> BoundedKeyPolicy<'a> {
    pub fn new(from: Option<Slice<'a>>, to: Option<Slice<'a>>) -> Self {
        Self { from, to }
    }
}

impl<'a> Policy for BoundedKeyPolicy<'a> {
    fn should_continue(&self, context: &dyn Context) -> bool {
        if let Some(key) = unsafe { context.key() } {
            if let Some(from) = &self.from
                && key < *from
            {
                return false;
            }
            if let Some(to) = &self.to
                && key >= *to
            {
                return false;
            }
        }
        true
    }

    fn should_seek_begin(&self) -> bool {
        false
    }
}

/// A fully unified iterator over the LevelDB keyspace.
///
/// The iteration direction is determined by the generic parameters `D`.
/// The return type is determined by the generic parameters `T`.
/// The iteration policy is determined by parameter `P`.
/// This provides static dispatch for direction-specific, type-specific, and policy-specific operations.
pub struct Iterator<'a, T = KeyType, D = Forward, P = DefaultPolicy> {
    iter: RawIterator,
    started: bool,
    stopped: bool,
    policy: P,
    // Iterator accesses the Database through a leveldb_iter_t pointer
    // but needs to hold the reference for lifetime tracking
    #[allow(dead_code)]
    database: PhantomData<&'a Database>,
    _return_type: PhantomData<T>,
    _direction: PhantomData<D>,
}

// Private methods for this crate only
impl<'a, T, D, P> Iterator<'a, T, D, P> {
    /// Core factory method to create iterator with specified direction and policy
    fn new(
        database: &'a Database,
        options: ReadOptions<'a>,
        policy: P,
        _direction: PhantomData<D>,
        _return_type: PhantomData<T>,
    ) -> Self {
        unsafe {
            let c_readoptions = c_readoptions(&options);
            let ptr = leveldb_create_iterator(database.database.ptr, c_readoptions);
            leveldb_readoptions_destroy(c_readoptions);

            Iterator {
                iter: RawIterator { ptr },
                started: false,
                stopped: false,
                policy,
                database: PhantomData,
                _return_type: PhantomData,
                _direction: PhantomData,
            }
        }
    }

    /// Get the raw iterator pointer
    #[inline]
    fn raw_iterator(&self) -> *mut leveldb_iterator_t {
        self.iter.ptr
    }

    #[inline]
    fn move_forward(&self) {
        unsafe { leveldb_iter_next(self.raw_iterator()) }
    }

    #[inline]
    fn move_backward(&self) {
        unsafe { leveldb_iter_prev(self.raw_iterator()) }
    }
}

impl<'a, T, D, P> Context<'a> for Iterator<'a, T, D, P> {
    #[inline]
    unsafe fn key(&self) -> Option<Slice<'a>> {
        unsafe {
            let length: size_t = 0;
            let value = leveldb_iter_key(self.raw_iterator(), &length) as *const u8;
            if value.is_null() || length == 0 {
                None
            } else {
                let data = std::slice::from_raw_parts(value, length);
                Some(Slice::from(data))
            }
        }
    }

    #[inline]
    unsafe fn value(&self) -> Option<Slice<'a>> {
        unsafe {
            let length: size_t = 0;
            let value = leveldb_iter_value(self.raw_iterator(), &length) as *const u8;
            if value.is_null() || length == 0 {
                None
            } else {
                let data = std::slice::from_raw_parts(value, length);
                Some(Slice::from(data))
            }
        }
    }

    #[inline]
    unsafe fn entry(&self) -> Option<(Slice<'a>, Slice<'a>)> {
        unsafe {
            match (self.key(), self.value()) {
                (Some(key), Some(value)) => Some((key, value)),
                _ => None,
            }
        }
    }
}

/// Macro to implement Iterator trait for different
/// - return types
/// - directions
/// - policies
macro_rules! impl_iterator {
    ($T:ty, $Item:ty, $ItemFn:ident, $D:ty, $MoveFn:ident, $SeekInitFn:ident, $SeekLastFn:ident) => {
        impl<'a, P: Policy> iter::Iterator for Iterator<'a, $T, $D, P> {
            type Item = $Item;

            #[inline]
            fn next(&mut self) -> Option<Self::Item> {
                if self.advance() {
                    unsafe { self.$ItemFn() }
                } else {
                    None
                }
            }
        }

        impl<'a, P: Policy> Iterator<'a, $T, $D, P> {
            /// Return the last element of the iterator
            ///
            /// The returned slice borrows data directly from the LevelDB iterator without copying.
            /// The data is only valid until the iterator is advanced to the next position or destroyed.
            ///
            /// # Safety
            /// The caller must ensure that the returned slice does not outlive the iterator
            /// or any operation that would advance the iterator (such as calling `next()`).
            /// To keep the data longer, the slice should be cloned.
            ///
            /// # Performance
            /// This method provides zero-copy access to LevelDB data for maximum performance
            #[inline]
            pub fn last(&mut self) -> Result<Option<$Item>, Error> {
                self.$SeekLastFn();
                if self.valid() {
                    Ok(unsafe { self.$ItemFn() })
                } else {
                    match self.get_error() {
                        Some(e) => Err(e),
                        None => Ok(None),
                    }
                }
            }

            #[inline]
            fn advance(&mut self) -> bool {
                if self.stopped {
                    return false;
                }
                if !self.started {
                    if self.policy.should_seek_begin() {
                        self.$SeekInitFn();
                    }
                    self.started = true;
                } else {
                    // Subsequent calls: move to next position
                    self.$MoveFn();
                }
                // Check if current position is valid and should continue
                self.stopped = !self.valid() || !self.policy.should_continue(self);
                !self.stopped
            }
        }
    };
}

impl<'a, T, D, P: Policy> LevelDBIterator<'a> for Iterator<'a, T, D, P> {
    #[inline]
    fn valid(&self) -> bool {
        unsafe { leveldb_iter_valid(self.raw_iterator()) != 0 }
    }

    #[inline]
    fn seek(&self, key: &Slice) {
        unsafe {
            let key = key.as_bytes();
            leveldb_iter_seek(
                self.raw_iterator(),
                key.as_ptr() as *mut c_char,
                key.len() as size_t,
            );
        }
    }

    #[inline]
    fn seek_to_first(&self) {
        unsafe { leveldb_iter_seek_to_first(self.raw_iterator()) }
    }

    #[inline]
    fn seek_to_last(&self) {
        unsafe { leveldb_iter_seek_to_last(self.raw_iterator()) }
    }

    #[inline]
    fn get_error(&self) -> Option<Error> {
        unsafe {
            let mut errptr: *mut c_char = std::ptr::null_mut();
            leveldb_iter_get_error(self.raw_iterator(), &mut errptr);

            if errptr.is_null() {
                None
            } else {
                Some(Error::new_from_char(errptr))
            }
        }
    }
}

// Apply macro to generate Iterator implementations
// For different types: key, value & entry
macro_rules! impl_iterators_for_direction {
    ($MoveFn:ident, $SeekInitFn:ident, $SeekLastFn:ident, $Dir:ty) => {
        impl_iterator!(
            KeyType,
            Slice<'a>,
            key,
            $Dir,
            $MoveFn,
            $SeekInitFn,
            $SeekLastFn
        );
        impl_iterator!(
            ValueType,
            Slice<'a>,
            value,
            $Dir,
            $MoveFn,
            $SeekInitFn,
            $SeekLastFn
        );
        impl_iterator!(
            EntryType,
            (Slice<'a>, Slice<'a>),
            entry,
            $Dir,
            $MoveFn,
            $SeekInitFn,
            $SeekLastFn
        );
    };
}
// For 2 different directions
impl_iterators_for_direction!(move_forward, seek_to_first, seek_to_last, Forward);
impl_iterators_for_direction!(move_backward, seek_to_last, seek_to_first, Backward);

pub type KeyIterator<'a, P = DefaultPolicy> = Iterator<'a, KeyType, Forward, P>;
pub type ValueIterator<'a, P = DefaultPolicy> = Iterator<'a, ValueType, Forward, P>;
pub type EntryIterator<'a, P = DefaultPolicy> = Iterator<'a, EntryType, Forward, P>;
pub type KeyIteratorRev<'a, P = DefaultPolicy> = Iterator<'a, KeyType, Backward, P>;
pub type ValueIteratorRev<'a, P = DefaultPolicy> = Iterator<'a, ValueType, Backward, P>;
pub type EntryIteratorRev<'a, P = DefaultPolicy> = Iterator<'a, EntryType, Backward, P>;

/// A trait to provide various iterators of LevelDB instance.
///
/// This trait provides a unified interface for creating different types of iterators
/// over LevelDB data. The API is designed to be flexible while maintaining type safety
/// and performance.
///
/// # Iterator Types
///
/// There are three main iterator types, each defined by `T` type parameter:
///
/// - **EntryIterator** (`EntryType`): Iterates over key-value pairs `(K, V)`
/// - **KeyIterator** (`KeyType`): Iterates over keys only `K`
/// - **ValueIterator** (`ValueType`): Iterates over values only `V`
///
/// # Direction
///
/// The direction is controlled by `D` type parameter:
///
/// - **Forward** (`Forward`): Iterates from smallest to largest key
/// - **Backward** (`Backward`): Iterates from largest to smallest key
///
/// # Policies
///
/// Policies control iteration behavior and bounds. For example:
///
/// - **DefaultPolicy**: No bounds, iterates over all data
/// - **BoundedKeyPolicy**: Iterates within specified key bounds
///
/// # Usage Examples
///
/// ## Basic Entry Iteration
///
/// ```ignore
/// // Forward iteration over all key-value pairs
/// let iter: EntryIterator<'_> = database.iter(ReadOptions::new());
///
/// // Backward iteration over all key-value pairs
/// let iter: EntryIteratorRev<'_> = database.iter(ReadOptions::new());
/// ```
///
/// ## Key-Only Iteration
///
/// ```ignore
/// // Forward iteration over keys only
/// let iter: KeyIterator<'_> = database.iter(ReadOptions::new());
///
/// // Backward iteration over keys only
/// let iter: KeyIteratorRev<'_> = database.iter(ReadOptions::new());
/// ```
///
/// ## Value-Only Iteration
///
/// ```ignore
/// // Forward iteration over values only
/// let iter: ValueIterator<'_> = database.iter(ReadOptions::new());
///
/// // Backward iteration over values only
/// let iter: ValueIteratorRev<'_> = database.iter(ReadOptions::new());
/// ```
pub trait Iterable<'a> {
    /// Create an iterator with specified type, direction, and policy
    /// Specify return type for correctness of inference
    ///
    /// This is the most flexible method that allows complete control over iterator behavior,
    /// with custom policies.
    ///
    /// # Parameters
    ///
    /// - `options`: Read options for the iterator
    /// - `policy`: Iteration policy (bounds, filtering, etc.)
    ///
    /// # Returns
    ///
    /// An iterator with the specified type, direction, and policy.
    ///
    /// # Example
    ///
    /// ```ignore
    /// let begin = Slice::from(&b"key1"[..]);
    /// let end = Slice::from(&b"key9"[..]);
    /// let policy = BoundedKeyPolicy::new(Some(begin), Some(end));
    ///
    /// // Bounded entry iteration
    /// let iter: KeyIterator<'_, _>  = database.iter_with_policy(ReadOptions::new(), policy);
    ///
    /// // Remember to seek to the start position for bounded iteration
    /// iter.seek(&begin);
    /// ```
    fn iter_with_policy<T, D, P: Policy>(
        &'a self,
        options: ReadOptions<'a>,
        policy: P,
    ) -> Iterator<'a, T, D, P>;

    /// Create an iterator with specified type and direction, using DefaultPolicy
    ///
    /// This is a convenience method that uses the `DefaultPolicy`.
    ///
    /// Note: The default iterator type is `KeyIterator` for key-only iteration.
    /// Use explicit type annotation for other iterator types.
    ///
    /// # Parameters
    ///
    /// - `options`: Read options for the iterator
    ///
    /// # Returns
    ///
    /// An iterator with the specified type and direction, using DefaultPolicy.
    ///
    /// # Example
    ///
    /// ```ignore
    /// let policy = BoundedKeyPolicy::new(
    ///     Some(Slice::from(&b"start"[..])),
    ///     Some(Slice::from(&b"end"[..]))
    /// );
    /// let iter: EntryIterator<'_, _> = database.iter_with_policy(ReadOptions::new(), policy);
    /// ```
    fn iter<T, D>(&'a self, options: ReadOptions<'a>) -> Iterator<'a, T, D, DefaultPolicy> {
        self.iter_with_policy(options, DefaultPolicy)
    }
}

impl<'a> Iterable<'a> for Database {
    fn iter_with_policy<T, D, P: Policy>(
        &'a self,
        options: ReadOptions<'a>,
        policy: P,
    ) -> Iterator<'a, T, D, P> {
        Iterator::new(self, options, policy, PhantomData, PhantomData)
    }
}