revision/

walk.rs

//! Structured, selective decoding of revisioned encodings.
//!
//! The [`WalkRevisioned`] trait lets callers progress element-by-element through
//! revisioned bytes, deciding per-element whether to **decode**, **skip**, or
//! **walk into** further structure. This sits between [`DeserializeRevisioned`]
//! (decode everything into a value) and [`SkipRevisioned`] (consume bytes
//! without producing a value).
//!
//! [`DeserializeRevisioned`]: crate::DeserializeRevisioned
//! [`SkipRevisioned`]: crate::SkipRevisioned
//!
//! # Shapes
//!
//! Walkers are shape-specific:
//!
//! - [`LeafWalker`] — primitives that have no internal structure (e.g.
//!   `u32`, `String`); only `decode` or `skip` are meaningful.
//! - [`OptionWalker`] — `Option<T>`; peek the tag, then optionally walk into
//!   the payload.
//! - [`ResultWalker`] — `Result<T, E>`; peek the variant, then walk into
//!   either side.
//! - [`SeqWalker`] — homogeneous sequences (`Vec`, `HashSet`, …); iterate
//!   items, skip/decode/walk per item.
//! - [`MapWalker`] — keyed sequences (`HashMap`, `BTreeMap`, …); iterate
//!   entries, skip/decode key + value individually.
//! - Per-type walkers generated by `#[revisioned(...)]` for structs/enums.
//!
//! # Wire format invariants
//!
//! - `#[revisioned(...)]` types prefix their body with a `u16` revision header.
//! - Enums then encode a `u32` variant discriminant.
//! - Sequences encode `usize len` then elements.
//! - Maps encode `usize len` then `(key, value)` pairs.
//!
//! Walkers honour these invariants and read the relevant prefix in
//! `walk_revisioned` before returning so the caller can step over the body.

use std::cmp::Ordering;
use std::io::Read;
use std::marker::PhantomData;

use crate::slice_reader::BorrowedReader;
use crate::{DeserializeRevisioned, Error, Revisioned, SkipRevisioned};

// -----------------------------------------------------------------------------
// Trait
// -----------------------------------------------------------------------------

/// Structured, element-by-element traversal of revisioned bytes.
///
/// `walk_revisioned` consumes the revision-level prefix (e.g. the `u16`
/// revision tag emitted by the derive macro for `#[revisioned(...)]` types)
/// and returns a shape-specific walker positioned at the start of the body.
///
/// The associated walker type carries `&'r mut R` and any decoding state. Once
/// dropped (or `finish`-ed), the reader is positioned past the encoded value.
///
/// # Example
///
/// ```ignore
/// use revision::{DeserializeRevisioned, WalkRevisioned, prelude::*};
///
/// let mut reader = bytes.as_slice();
/// let mut entries = <std::collections::BTreeMap<String, u32>>::walk_revisioned(&mut reader)?;
/// while let Some(mut entry) = entries.next_entry()? {
///     let key: String = entry.decode_key()?;
///     if key == "score" {
///         let value: u32 = entry.decode_value()?;
///         println!("score = {}", value);
///     } else {
///         entry.skip_value()?;
///     }
/// }
/// ```
pub trait WalkRevisioned: Revisioned {
	/// Walker produced by [`walk_revisioned`](Self::walk_revisioned).
	///
	/// The walker borrows the reader for `'r` and exposes shape-specific
	/// progression methods.
	type Walker<'r, R: BorrowedReader + 'r>;

	/// Read the type's revision-level prefix and return a walker positioned at
	/// the start of the body.
	///
	/// The reader must be slice-backed ([`BorrowedReader`]). Callers with a
	/// `File` or `TcpStream` should buffer the payload into a `Vec<u8>` first
	/// — revisioned compounds carry their byte-length up front, so the full
	/// payload has to be present before a walk can begin anyway. Walking on a
	/// slice-backed source lets the optimised wire format borrow variant
	/// bodies and indexed payloads directly, avoiding per-walk allocations.
	fn walk_revisioned<'r, R: BorrowedReader>(
		reader: &'r mut R,
	) -> Result<Self::Walker<'r, R>, Error>;
}

// -----------------------------------------------------------------------------
// Zero-copy peek primitives
// -----------------------------------------------------------------------------

/// Marker for revisioned types whose wire format is `usize len || raw bytes`.
///
/// Types implementing this trait can have their wire payload **peeked as
/// `&[u8]`** from a [`BorrowedReader`] without allocating. Walker methods
/// such as [`LeafWalker::with_bytes`], [`MapWalker::find_bytes`],
/// [`MapEntry::with_key_bytes`] / [`MapEntry::with_value_bytes`], and
/// [`SeqItem::with_bytes`] are gated on this trait so callers can compare,
/// hash, or copy the wire bytes without paying for an intermediate
/// `String` / `Vec<u8>` / `Bytes`.
///
/// The trait does **not** apply to derived `#[revisioned(...)]` types,
/// which prepend a `u16` revision header to their body. Only types whose
/// `SerializeRevisioned` impl writes `usize` then raw bytes qualify; this
/// includes the standard string- and bytes-shaped types
/// (`String`, `&str`, `Box<str>`, `Arc<str>`, `Cow<'_, str>`, `Vec<u8>`,
/// `Vec<i8>`, `PathBuf`) and feature-gated types like `bytes::Bytes`.
///
/// Downstream crates can opt their newtypes in by adding a one-line impl
/// (e.g. `impl LengthPrefixedBytes for MyId {}`) when the newtype's
/// `SerializeRevisioned` ultimately writes `usize len || raw bytes`.
///
/// Marking a type incorrectly — when its encoding is **not** exactly that
/// layout — will mis-parse under [`LeafWalker::with_bytes`],
/// [`MapWalker::find_bytes`], and related helpers; the trait is a **trusted**
/// wire-shape contract, not validated at runtime beyond normal deserialization.
/// That is the same class of hazard as an incorrect manual [`Revisioned`]
/// implementation: the library cannot prove the marker matches the bytes.
pub trait LengthPrefixedBytes: Revisioned {}

impl LengthPrefixedBytes for String {}
// `str` is `?Sized`, so a `LeafWalker<'_, str, R>` cannot exist in
// practice — this impl is here so the `Cow<'_, T>` blanket impl below
// can apply to `Cow<'_, str>` (whose `T::Owned` is `String`).
impl LengthPrefixedBytes for str {}
impl LengthPrefixedBytes for std::sync::Arc<str> {}
impl LengthPrefixedBytes for Box<str> {}
impl LengthPrefixedBytes for std::path::PathBuf {}
impl LengthPrefixedBytes for Vec<u8> {}
impl LengthPrefixedBytes for Vec<i8> {}

impl<T> LengthPrefixedBytes for std::borrow::Cow<'_, T>
where
	T: ToOwned + Revisioned,
	T::Owned: LengthPrefixedBytes,
{
}

#[cfg(feature = "bytes")]
impl LengthPrefixedBytes for bytes::Bytes {}

/// Peek a length-prefixed byte payload at the reader's current position
/// and pass it to `f` as a borrowed slice; advance the reader past the
/// bytes once `f` returns.
///
/// Used by [`LeafWalker::with_bytes`], [`MapEntry::with_key_bytes`] /
/// [`with_value_bytes`](MapEntry::with_value_bytes), [`SeqItem::with_bytes`],
/// and [`MapWalker::find_bytes`]. Each of those methods is just a thin
/// wrapper around this helper plus the appropriate cursor / counter
/// bookkeeping.
///
/// **Panic safety:** if `f` panics, the reader is left positioned between
/// the consumed length prefix and the un-advanced body bytes. The reader is
/// in a corrupt state and should not be reused after the unwind. In the
/// usual case where a panic ends use of the reader this does not matter.
#[inline]
pub(crate) fn with_length_prefixed_bytes<R, F, T>(reader: &mut R, f: F) -> Result<T, Error>
where
	R: BorrowedReader,
	F: FnOnce(&[u8]) -> T,
{
	let len = usize::deserialize_revisioned(reader)?;
	let result = {
		let bytes = reader.peek_bytes(len)?;
		f(bytes)
	};
	reader.advance(len)?;
	Ok(result)
}

// -----------------------------------------------------------------------------
// LeafWalker — primitives and length-prefixed scalars
// -----------------------------------------------------------------------------

/// Walker for a primitive (or otherwise structurally opaque) revisioned type.
///
/// Only `decode` and `skip` are meaningful; there is no internal structure to
/// step through.
pub struct LeafWalker<'r, T, R: BorrowedReader + 'r> {
	reader: &'r mut R,
	_marker: PhantomData<fn() -> T>,
}

impl<'r, T, R: BorrowedReader + 'r> LeafWalker<'r, T, R> {
	/// Construct a leaf walker; intended for use by [`WalkRevisioned`] impls.
	#[inline]
	pub fn new(reader: &'r mut R) -> Self {
		Self {
			reader,
			_marker: PhantomData,
		}
	}

	/// Decode the value, advancing the reader past it.
	#[inline]
	pub fn decode(self) -> Result<T, Error>
	where
		T: DeserializeRevisioned,
	{
		T::deserialize_revisioned(self.reader)
	}

	/// Skip the value, advancing the reader past it.
	#[inline]
	pub fn skip(self) -> Result<(), Error>
	where
		T: SkipRevisioned,
	{
		T::skip_revisioned(self.reader)
	}

	/// Walk into the value as a structured walker. Equivalent to calling
	/// `T::walk_revisioned` directly on the underlying reader; provided so
	/// `LeafWalker` doubles as a "pre-walk handle" that lets the caller
	/// choose between decoding, skipping, or descending without committing
	/// up front.
	#[inline]
	pub fn walk(self) -> Result<T::Walker<'r, R>, Error>
	where
		T: WalkRevisioned,
	{
		T::walk_revisioned(self.reader)
	}

	/// Borrow the underlying reader. Useful for hand-rolled walkers that need
	/// to read auxiliary state before continuing.
	#[inline]
	pub fn reader(&mut self) -> &mut R {
		self.reader
	}

	/// Surrender the underlying reader without consuming the value.
	#[inline]
	pub fn into_reader(self) -> &'r mut R {
		self.reader
	}
}

impl<'r, T, R> LeafWalker<'r, T, R>
where
	T: LengthPrefixedBytes,
	R: BorrowedReader + 'r,
{
	/// Inspect the leaf's wire bytes without allocating, calling `f` with
	/// a slice borrowed from the underlying buffer; the reader is
	/// advanced past the bytes after `f` returns.
	///
	/// Only available when the underlying reader is slice-backed
	/// ([`BorrowedReader`]) and the value's wire format is exactly
	/// `usize len || raw bytes` ([`LengthPrefixedBytes`]). For decoded
	/// access use [`decode`](Self::decode); for fall-through advancement
	/// use [`skip`](Self::skip).
	#[inline]
	pub fn with_bytes<F, U>(self, f: F) -> Result<U, Error>
	where
		F: FnOnce(&[u8]) -> U,
	{
		with_length_prefixed_bytes(self.reader, f)
	}
}

// -----------------------------------------------------------------------------
// OptionWalker — Option<T>
// -----------------------------------------------------------------------------

/// Walker for `Option<T>`.
///
/// The wire format is a `u8` tag (`0` = `None`, `1` = `Some`) followed by an
/// inner `T` payload when present.
pub struct OptionWalker<'r, T, R: BorrowedReader + 'r> {
	reader: &'r mut R,
	tag: u8,
	_marker: PhantomData<fn() -> T>,
}

impl<'r, T, R: BorrowedReader + 'r> OptionWalker<'r, T, R> {
	/// Construct an option walker. Reads the `u8` tag from `reader`.
	#[inline]
	pub fn new(reader: &'r mut R) -> Result<Self, Error> {
		let tag = u8::deserialize_revisioned(reader)?;
		match tag {
			0 | 1 => Ok(Self {
				reader,
				tag,
				_marker: PhantomData,
			}),
			v => Err(Error::Deserialize(format!("Invalid option value {v}"))),
		}
	}

	/// `true` when the value is `Some(_)` and the inner walker can be entered.
	#[inline]
	pub fn is_some(&self) -> bool {
		self.tag == 1
	}

	/// `true` when the value is `None`.
	#[inline]
	pub fn is_none(&self) -> bool {
		self.tag == 0
	}

	/// Decode the value, advancing the reader past it.
	#[inline]
	pub fn decode(self) -> Result<Option<T>, Error>
	where
		T: DeserializeRevisioned,
	{
		match self.tag {
			0 => Ok(None),
			1 => Ok(Some(T::deserialize_revisioned(self.reader)?)),
			v => Err(Error::Deserialize(format!("Invalid option value {v}"))),
		}
	}

	/// Skip the value, advancing the reader past it.
	#[inline]
	pub fn skip(self) -> Result<(), Error>
	where
		T: SkipRevisioned,
	{
		if self.tag == 1 {
			T::skip_revisioned(self.reader)?;
		}
		Ok(())
	}

	/// Walk into the `Some(_)` payload. Returns an error if the value is `None`.
	#[inline]
	pub fn into_some(self) -> Result<T::Walker<'r, R>, Error>
	where
		T: WalkRevisioned,
	{
		match self.tag {
			0 => Err(Error::Deserialize("Cannot walk into None payload".into())),
			1 => T::walk_revisioned(self.reader),
			v => Err(Error::Deserialize(format!("Invalid option value {v}"))),
		}
	}
}

// -----------------------------------------------------------------------------
// ResultWalker — Result<T, E>
// -----------------------------------------------------------------------------

/// Walker for `Result<T, E>`.
///
/// The wire format is a `u32` tag (`0` = `Ok(T)`, `1` = `Err(E)`) followed by
/// the corresponding payload.
pub struct ResultWalker<'r, T, E, R: BorrowedReader + 'r> {
	reader: &'r mut R,
	tag: u32,
	_marker: PhantomData<fn() -> Result<T, E>>,
}

impl<'r, T, E, R: BorrowedReader + 'r> ResultWalker<'r, T, E, R> {
	/// Construct a result walker. Reads the `u32` variant tag from `reader`.
	#[inline]
	pub fn new(reader: &'r mut R) -> Result<Self, Error> {
		let tag = u32::deserialize_revisioned(reader)?;
		match tag {
			0 | 1 => Ok(Self {
				reader,
				tag,
				_marker: PhantomData,
			}),
			v => Err(Error::Deserialize(format!("Unknown Result variant index {v}"))),
		}
	}

	/// `true` when the value is `Ok(_)`.
	#[inline]
	pub fn is_ok(&self) -> bool {
		self.tag == 0
	}

	/// `true` when the value is `Err(_)`.
	#[inline]
	pub fn is_err(&self) -> bool {
		self.tag == 1
	}

	/// Decode the value, advancing the reader past it.
	#[inline]
	pub fn decode(self) -> Result<Result<T, E>, Error>
	where
		T: DeserializeRevisioned,
		E: DeserializeRevisioned,
	{
		match self.tag {
			0 => Ok(Ok(T::deserialize_revisioned(self.reader)?)),
			1 => Ok(Err(E::deserialize_revisioned(self.reader)?)),
			v => Err(Error::Deserialize(format!("Unknown Result variant index {v}"))),
		}
	}

	/// Skip the value, advancing the reader past it.
	#[inline]
	pub fn skip(self) -> Result<(), Error>
	where
		T: SkipRevisioned,
		E: SkipRevisioned,
	{
		match self.tag {
			0 => T::skip_revisioned(self.reader),
			1 => E::skip_revisioned(self.reader),
			v => Err(Error::Deserialize(format!("Unknown Result variant index {v}"))),
		}
	}

	/// Walk into the `Ok(_)` payload. Errors if the value is `Err`.
	#[inline]
	pub fn into_ok(self) -> Result<T::Walker<'r, R>, Error>
	where
		T: WalkRevisioned,
	{
		match self.tag {
			0 => T::walk_revisioned(self.reader),
			1 => Err(Error::Deserialize("Cannot walk into Err as Ok".into())),
			v => Err(Error::Deserialize(format!("Unknown Result variant index {v}"))),
		}
	}

	/// Walk into the `Err(_)` payload. Errors if the value is `Ok`.
	#[inline]
	pub fn into_err(self) -> Result<E::Walker<'r, R>, Error>
	where
		E: WalkRevisioned,
	{
		match self.tag {
			0 => Err(Error::Deserialize("Cannot walk into Ok as Err".into())),
			1 => E::walk_revisioned(self.reader),
			v => Err(Error::Deserialize(format!("Unknown Result variant index {v}"))),
		}
	}
}

// -----------------------------------------------------------------------------
// SeqWalker — Vec<T>, HashSet<T>, BTreeSet<T>, BinaryHeap<T>, …
// -----------------------------------------------------------------------------

/// Walker for a homogeneous sequence (length-prefix followed by `T` elements).
///
/// All collections whose [`SerializeRevisioned`] writes `usize len || T per
/// element` use this walker — `HashSet<T>`, `BTreeSet<T>`, `BinaryHeap<T>`,
/// `imbl::{Vector, OrdSet, HashSet}`, and `Vec<T>` for non-bulk element
/// types.
///
/// **Caveat for `Vec<T>` only:** with the `specialised-vectors` feature
/// (enabled by default), [`Vec<T>`](crate::implementations::vecs) uses a
/// compact bulk layout for primitive numeric types, `bool`, and (when the
/// optional `uuid` / `rust_decimal` features are enabled) `uuid::Uuid` /
/// `rust_decimal::Decimal`. [`Vec<T>::walk_revisioned`] rejects those
/// element types up front; sets and heaps are unaffected because they
/// always use per-element framing.
///
/// [`SerializeRevisioned`]: crate::SerializeRevisioned
pub struct SeqWalker<'r, T, R: BorrowedReader + 'r> {
	reader: &'r mut R,
	remaining: usize,
	_marker: PhantomData<fn() -> T>,
}

impl<'r, T, R: BorrowedReader + 'r> SeqWalker<'r, T, R> {
	/// Construct a sequence walker. Reads the `usize` length prefix.
	#[inline]
	pub fn new(reader: &'r mut R) -> Result<Self, Error> {
		let len = usize::deserialize_revisioned(reader)?;
		Ok(Self {
			reader,
			remaining: len,
			_marker: PhantomData,
		})
	}

	/// Number of items still to be visited.
	#[inline]
	pub fn remaining(&self) -> usize {
		self.remaining
	}

	/// Yield the next item handle, if any.
	///
	/// The returned [`SeqItem`] borrows the walker until it is consumed
	/// (`decode`, `skip`, or `walk`).
	#[inline]
	pub fn next_item(&mut self) -> Option<SeqItem<'_, 'r, T, R>> {
		if self.remaining == 0 {
			None
		} else {
			Some(SeqItem {
				walker: self,
			})
		}
	}

	/// Skip every remaining item.
	#[inline]
	pub fn skip_remaining(mut self) -> Result<(), Error>
	where
		T: SkipRevisioned,
	{
		while self.remaining > 0 {
			T::skip_revisioned(self.reader)?;
			self.remaining -= 1;
		}
		Ok(())
	}
}

/// One item position inside a [`SeqWalker`].
pub struct SeqItem<'a, 'r, T, R: BorrowedReader + 'r> {
	walker: &'a mut SeqWalker<'r, T, R>,
}

impl<'a, 'r, T, R: BorrowedReader + 'r> SeqItem<'a, 'r, T, R> {
	/// Decode this item.
	#[inline]
	pub fn decode(self) -> Result<T, Error>
	where
		T: DeserializeRevisioned,
	{
		let v = T::deserialize_revisioned(self.walker.reader)?;
		self.walker.remaining -= 1;
		Ok(v)
	}

	/// Skip this item.
	#[inline]
	pub fn skip(self) -> Result<(), Error>
	where
		T: SkipRevisioned,
	{
		T::skip_revisioned(self.walker.reader)?;
		self.walker.remaining -= 1;
		Ok(())
	}

	/// Walk into this item, returning a sub-walker borrowing the parent.
	///
	/// The parent walker cannot advance until the returned walker is dropped
	/// or consumed. After it is dropped, the next call to
	/// [`SeqWalker::next_item`] yields the following item.
	#[inline]
	pub fn walk(self) -> Result<T::Walker<'a, R>, Error>
	where
		T: WalkRevisioned,
	{
		let walker = T::walk_revisioned(self.walker.reader)?;
		self.walker.remaining -= 1;
		Ok(walker)
	}
}

impl<'a, 'r, T, R> SeqItem<'a, 'r, T, R>
where
	T: LengthPrefixedBytes,
	R: BorrowedReader + 'r,
{
	/// Inspect the item's wire bytes without allocating, calling `f` with
	/// a slice borrowed from the underlying buffer; the reader is
	/// advanced past the item once `f` returns and the seq walker's
	/// remaining counter is decremented.
	///
	/// Useful for searching sorted sequences (`Vec<String>`,
	/// `BTreeSet<Bytes>`, …) by byte compare without paying for a
	/// per-item decode allocation.
	#[inline]
	pub fn with_bytes<F, U>(self, f: F) -> Result<U, Error>
	where
		F: FnOnce(&[u8]) -> U,
	{
		let result = with_length_prefixed_bytes(self.walker.reader, f)?;
		self.walker.remaining -= 1;
		Ok(result)
	}
}

// -----------------------------------------------------------------------------
// MapWalker — HashMap<K, V>, BTreeMap<K, V>, …
// -----------------------------------------------------------------------------

/// Walker for a `(K, V)` map (length-prefix followed by alternating
/// key/value encodings).
pub struct MapWalker<'r, K, V, R: BorrowedReader + 'r> {
	reader: &'r mut R,
	remaining: usize,
	_marker: PhantomData<fn() -> (K, V)>,
}

/// Where the cursor sits within a single [`MapEntry`] iteration.
#[derive(Clone, Copy, Debug, Eq, PartialEq)]
enum MapCursor {
	/// Reader is positioned at the start of the key.
	BeforeKey,
	/// Reader is positioned at the start of the value.
	BeforeValue,
}

impl<'r, K, V, R: BorrowedReader + 'r> MapWalker<'r, K, V, R> {
	/// Construct a map walker. Reads the `usize` length prefix.
	#[inline]
	pub fn new(reader: &'r mut R) -> Result<Self, Error> {
		let len = usize::deserialize_revisioned(reader)?;
		Ok(Self {
			reader,
			remaining: len,
			_marker: PhantomData,
		})
	}

	/// Number of entries still to be visited.
	#[inline]
	pub fn remaining(&self) -> usize {
		self.remaining
	}

	/// Borrow the next entry, if any.
	///
	/// The caller must consume the returned [`MapEntry`] (call one of
	/// `decode_value`, `skip_value`, or `walk_value`) before calling
	/// `next_entry` again. Forgetting to consume the entry's value is a
	/// programming error: the next entry will start mid-payload.
	#[inline]
	pub fn next_entry(&mut self) -> Option<MapEntry<'_, 'r, K, V, R>> {
		if self.remaining == 0 {
			None
		} else {
			Some(MapEntry {
				walker: self,
				cursor: MapCursor::BeforeKey,
			})
		}
	}

	/// Skip every remaining entry.
	#[inline]
	pub fn skip_remaining(mut self) -> Result<(), Error>
	where
		K: SkipRevisioned,
		V: SkipRevisioned,
	{
		while self.remaining > 0 {
			K::skip_revisioned(self.reader)?;
			V::skip_revisioned(self.reader)?;
			self.remaining -= 1;
		}
		Ok(())
	}

	/// Linear search by **decoded** key, returning a value handle for the
	/// matching entry or `None` if no entry passes `predicate`.
	///
	/// **Sorted maps only:** The predicate is compared with **encoded key order**
	/// as visited on the wire (the order [`BTreeMap`](std::collections::BTreeMap)
	/// serialises). Using this on bytes produced from a [`HashMap`](std::collections::HashMap)
	/// while assuming lexicographic or sorted-key ordering is invalid: you may match
	/// the wrong entry or drop the tail under `Ordering::Greater` while the true key
	/// still appears later in the stream.
	///
	/// The returned [`LeafWalker`] is positioned at the start of the value's
	/// encoding (i.e. the type-level prefix has not been read yet); the
	/// caller can then call `decode`, `skip`, or `walk` on it.
	///
	/// Every strictly preceding entry (full key and value) is skipped.
	/// For the matching entry, only the key has been read off the wire;
	/// the value remains for the leaf walker. Entries that sort **after**
	/// the matched key stay on the reader, but this method consumes `self`,
	/// so you cannot call [`next_entry`](Self::next_entry) afterward — there
	/// is no way to resume the same [`MapWalker`]. Prefer streaming iteration
	/// if you must handle one hit then walk the tail.
	///
	/// On `None` (no match) the entire remainder of the map is consumed.
	#[inline]
	pub fn find<F>(mut self, mut predicate: F) -> Result<Option<LeafWalker<'r, V, R>>, Error>
	where
		K: DeserializeRevisioned + SkipRevisioned,
		V: SkipRevisioned,
		F: FnMut(&K) -> Ordering,
	{
		while self.remaining > 0 {
			let key = K::deserialize_revisioned(self.reader)?;
			match predicate(&key) {
				Ordering::Less => {
					V::skip_revisioned(self.reader)?;
					self.remaining -= 1;
				}
				Ordering::Equal => {
					return Ok(Some(LeafWalker::new(self.reader)));
				}
				Ordering::Greater => {
					V::skip_revisioned(self.reader)?;
					self.remaining -= 1;
					while self.remaining > 0 {
						K::skip_revisioned(self.reader)?;
						V::skip_revisioned(self.reader)?;
						self.remaining -= 1;
					}
					return Ok(None);
				}
			}
		}
		Ok(None)
	}
}

impl<'r, K, V, R> MapWalker<'r, K, V, R>
where
	K: LengthPrefixedBytes + SkipRevisioned,
	V: SkipRevisioned,
	R: BorrowedReader + 'r,
{
	/// Linear search by **byte-borrowed** key, returning a value handle for
	/// the matching entry or `None` if no entry passes `predicate`.
	///
	/// Inherits the **sorted-map** requirement from [`find`](Self::find): wire
	/// visit order must match the predicate's assumed ordering (see
	/// [`find`](Self::find)).
	///
	/// Sibling of [`find`](Self::find) for keys whose wire format is
	/// exactly `usize len || raw bytes` ([`LengthPrefixedBytes`]). Each
	/// visited key is presented to `predicate` as a borrowed `&[u8]`
	/// without being decoded into `K`, so a 128-key scan over a
	/// `BTreeMap<Strand, _>` does zero allocations regardless of key
	/// length.
	///
	/// Behaviour identical to [`find`](Self::find) otherwise: the
	/// `Less / Equal / Greater` control flow assumes the underlying map
	/// is sorted by key; `Equal` returns a leaf at the matched value and
	/// consumes `self` (see [`find`](Self::find)); on no-match the entire
	/// remainder is consumed.
	#[inline]
	pub fn find_bytes<F>(mut self, mut predicate: F) -> Result<Option<LeafWalker<'r, V, R>>, Error>
	where
		F: FnMut(&[u8]) -> Ordering,
	{
		while self.remaining > 0 {
			let key_len = usize::deserialize_revisioned(self.reader)?;
			let cmp = {
				let key_bytes = self.reader.peek_bytes(key_len)?;
				predicate(key_bytes)
			};
			self.reader.advance(key_len)?;
			match cmp {
				Ordering::Less => {
					V::skip_revisioned(self.reader)?;
					self.remaining -= 1;
				}
				Ordering::Equal => {
					return Ok(Some(LeafWalker::new(self.reader)));
				}
				Ordering::Greater => {
					V::skip_revisioned(self.reader)?;
					self.remaining -= 1;
					while self.remaining > 0 {
						K::skip_revisioned(self.reader)?;
						V::skip_revisioned(self.reader)?;
						self.remaining -= 1;
					}
					return Ok(None);
				}
			}
		}
		Ok(None)
	}
}

/// One key+value pair inside a [`MapWalker`].
///
/// The cursor is positioned at the start of the key. The caller must first
/// handle the key (`decode_key` or `skip_key`) and then the value
/// (`decode_value`, `skip_value`, or `walk_value`). `decode_pair` and
/// `skip_pair` shortcut both at once.
///
/// Calling methods out of order returns [`Error::Deserialize`] in all builds
/// (not only debug builds), without advancing the reader when the check fails
/// before I/O.
pub struct MapEntry<'a, 'r, K, V, R: BorrowedReader + 'r> {
	walker: &'a mut MapWalker<'r, K, V, R>,
	cursor: MapCursor,
}

impl<'a, 'r, K, V, R: BorrowedReader + 'r> MapEntry<'a, 'r, K, V, R> {
	fn expect_cursor(&self, expected: MapCursor, operation: &'static str) -> Result<(), Error> {
		if self.cursor != expected {
			return Err(Error::Deserialize(format!(
				"MapEntry: invalid cursor for {operation} (expected {expected:?}, found {:?})",
				self.cursor,
			)));
		}
		Ok(())
	}

	/// Decode the key. The cursor advances to the value.
	#[inline]
	pub fn decode_key(&mut self) -> Result<K, Error>
	where
		K: DeserializeRevisioned,
	{
		self.expect_cursor(MapCursor::BeforeKey, "decode_key")?;
		let k = K::deserialize_revisioned(self.walker.reader)?;
		self.cursor = MapCursor::BeforeValue;
		Ok(k)
	}

	/// Skip the key. The cursor advances to the value.
	#[inline]
	pub fn skip_key(&mut self) -> Result<(), Error>
	where
		K: SkipRevisioned,
	{
		self.expect_cursor(MapCursor::BeforeKey, "skip_key")?;
		K::skip_revisioned(self.walker.reader)?;
		self.cursor = MapCursor::BeforeValue;
		Ok(())
	}

	/// Decode the value (key must already be consumed).
	#[inline]
	pub fn decode_value(self) -> Result<V, Error>
	where
		V: DeserializeRevisioned,
	{
		self.expect_cursor(MapCursor::BeforeValue, "decode_value")?;
		let v = V::deserialize_revisioned(self.walker.reader)?;
		self.walker.remaining -= 1;
		Ok(v)
	}

	/// Skip the value (key must already be consumed).
	#[inline]
	pub fn skip_value(self) -> Result<(), Error>
	where
		V: SkipRevisioned,
	{
		self.expect_cursor(MapCursor::BeforeValue, "skip_value")?;
		V::skip_revisioned(self.walker.reader)?;
		self.walker.remaining -= 1;
		Ok(())
	}

	/// Walk into the value. The parent map walker is borrowed for the
	/// returned walker's lifetime.
	#[inline]
	pub fn walk_value(self) -> Result<V::Walker<'a, R>, Error>
	where
		V: WalkRevisioned,
	{
		self.expect_cursor(MapCursor::BeforeValue, "walk_value")?;
		let w = V::walk_revisioned(self.walker.reader)?;
		self.walker.remaining -= 1;
		Ok(w)
	}

	/// Decode key and value together, advancing past the entry.
	#[inline]
	pub fn decode_pair(mut self) -> Result<(K, V), Error>
	where
		K: DeserializeRevisioned,
		V: DeserializeRevisioned,
	{
		let key = self.decode_key()?;
		let value = self.decode_value()?;
		Ok((key, value))
	}

	/// Skip key and value together, advancing past the entry.
	#[inline]
	pub fn skip_pair(mut self) -> Result<(), Error>
	where
		K: SkipRevisioned,
		V: SkipRevisioned,
	{
		self.skip_key()?;
		self.skip_value()
	}
}

impl<'a, 'r, K, V, R> MapEntry<'a, 'r, K, V, R>
where
	R: BorrowedReader + 'r,
{
	/// Inspect the entry's key as raw wire bytes without allocating.
	///
	/// Available when the key type's wire format is `usize len || raw
	/// bytes` ([`LengthPrefixedBytes`]) and the reader is slice-backed
	/// ([`BorrowedReader`]). The cursor advances past the key once `f`
	/// returns; the caller must then handle the value
	/// (`decode_value` / `skip_value` / `walk_value`).
	///
	/// Cheaper sibling of [`decode_key`](Self::decode_key) for the
	/// common case "compare key bytes against a needle and decide what
	/// to do with the value".
	#[inline]
	pub fn with_key_bytes<F, U>(&mut self, f: F) -> Result<U, Error>
	where
		K: LengthPrefixedBytes,
		F: FnOnce(&[u8]) -> U,
	{
		self.expect_cursor(MapCursor::BeforeKey, "with_key_bytes")?;
		let result = with_length_prefixed_bytes(self.walker.reader, f)?;
		self.cursor = MapCursor::BeforeValue;
		Ok(result)
	}

	/// Inspect the entry's value as raw wire bytes without allocating
	/// (key must already be consumed).
	///
	/// Available when the value type's wire format is `usize len || raw
	/// bytes` ([`LengthPrefixedBytes`]) and the reader is slice-backed
	/// ([`BorrowedReader`]). Consumes the entry; the entry's
	/// `remaining` counter is decremented.
	///
	/// Cheaper sibling of [`decode_value`](Self::decode_value) for the
	/// "filter map by value bytes" pattern.
	#[inline]
	pub fn with_value_bytes<F, U>(self, f: F) -> Result<U, Error>
	where
		V: LengthPrefixedBytes,
		F: FnOnce(&[u8]) -> U,
	{
		self.expect_cursor(MapCursor::BeforeValue, "with_value_bytes")?;
		let result = with_length_prefixed_bytes(self.walker.reader, f)?;
		self.walker.remaining -= 1;
		Ok(result)
	}
}

// -----------------------------------------------------------------------------
// StructWalker — generic positional walker for `#[revisioned(...)]` structs.
//
// The walker tracks the wire revision and a logical field index (`position`).
// After [`StructWalker::walk`], that counter advances even though the nested
// walker still owns the remainder of that field on the wire until dropped.
// -----------------------------------------------------------------------------

/// Generic walker for revisioned structs.
///
/// Field-type information is supplied by the caller per call rather than
/// stored in the walker. The caller is responsible for invoking field methods
/// in the wire order and matching the schema at the wire revision.
///
/// [`position`](Self::position) counts fields **started** (`decode`, `skip`, or
/// `walk`), not necessarily bytes fully consumed when the last operation was
/// [`walk`](Self::walk).
pub struct StructWalker<'r, R: BorrowedReader + 'r> {
	reader: &'r mut R,
	revision: u16,
	position: u32,
}

impl<'r, R: BorrowedReader + 'r> StructWalker<'r, R> {
	/// Construct a struct walker. The caller must already have read the
	/// type-level revision header.
	#[inline]
	pub fn new(reader: &'r mut R, revision: u16) -> Self {
		Self {
			reader,
			revision,
			position: 0,
		}
	}

	/// Wire revision of the encoded value being walked.
	#[inline]
	pub fn revision(&self) -> u16 {
		self.revision
	}

	/// Count of fields for which [`decode`](Self::decode), [`skip`](Self::skip),
	/// or [`walk`](Self::walk) has succeeded in wire order (starts at `0`;
	/// increments by one per call).
	///
	/// This tracks which schema slot you will touch next; it does **not** imply
	/// the previous field's bytes are fully past on the reader when that field was
	/// opened with [`walk`](Self::walk). In that case [`position`](Self::position)
	/// bumps as soon as the nested walker is constructed, while the child still
	/// borrows the reader for the rest of that field until it is dropped.
	#[inline]
	pub fn position(&self) -> u32 {
		self.position
	}

	/// Decode the next field as type `T`.
	#[inline]
	pub fn decode<T: DeserializeRevisioned>(&mut self) -> Result<T, Error> {
		let v = T::deserialize_revisioned(self.reader)?;
		self.position += 1;
		Ok(v)
	}

	/// Skip the next field as type `T`.
	#[inline]
	pub fn skip<T: SkipRevisioned>(&mut self) -> Result<(), Error> {
		T::skip_revisioned(self.reader)?;
		self.position += 1;
		Ok(())
	}

	/// Walk into the next field as type `T`. The returned walker borrows
	/// from `&mut self`; the parent walker can resume after it is dropped.
	///
	/// [`position`](Self::position) increments when this returns `Ok`, before the
	/// nested walker consumes the field payload — do not treat a higher position
	/// as “the reader has left that field” until the child walker finishes.
	#[inline]
	pub fn walk<T: WalkRevisioned>(&mut self) -> Result<T::Walker<'_, R>, Error> {
		let w = T::walk_revisioned(self.reader)?;
		self.position += 1;
		Ok(w)
	}

	/// Consume the struct walker and walk into the next field as type `T`,
	/// transferring ownership of the underlying reader to the returned
	/// walker. Subsequent fields cannot be walked.
	#[inline]
	pub fn into_walk<T: WalkRevisioned>(self) -> Result<T::Walker<'r, R>, Error> {
		T::walk_revisioned(self.reader)
	}

	/// Borrow the underlying reader. Useful for hand-rolled walkers needing
	/// auxiliary reads.
	#[inline]
	pub fn reader(&mut self) -> &mut R {
		self.reader
	}

	/// Surrender the underlying reader after the caller has manually
	/// consumed every remaining field.
	#[inline]
	pub fn into_reader(self) -> &'r mut R {
		self.reader
	}
}

// -----------------------------------------------------------------------------
// EnumWalker — generic walker for `#[revisioned(...)]` enums.
//
// Reads the `u32` variant discriminant on construction; the caller dispatches
// on it and supplies the payload type to `decode`, `skip`, or `into_walk`.
// -----------------------------------------------------------------------------

/// Generic walker for revisioned enums.
///
/// On construction the walker reads the `u32` variant discriminant. The
/// caller dispatches on `discriminant()` (or via a derive-generated table)
/// and supplies the appropriate payload type to one of the consume methods.
pub struct EnumWalker<'r, R: BorrowedReader + 'r> {
	reader: &'r mut R,
	revision: u16,
	discriminant: u32,
}

impl<'r, R: BorrowedReader + 'r> EnumWalker<'r, R> {
	/// Construct an enum walker. Reads the `u32` variant discriminant from
	/// `reader`. The caller must already have read the type-level revision
	/// header.
	#[inline]
	pub fn new(reader: &'r mut R, revision: u16) -> Result<Self, Error> {
		let discriminant = u32::deserialize_revisioned(reader)?;
		Ok(Self {
			reader,
			revision,
			discriminant,
		})
	}

	/// Wire revision of the encoded value being walked.
	#[inline]
	pub fn revision(&self) -> u16 {
		self.revision
	}

	/// Variant discriminant on the wire.
	#[inline]
	pub fn discriminant(&self) -> u32 {
		self.discriminant
	}

	/// Decode the variant payload as type `T`. Caller must supply the type
	/// matching the variant at this discriminant.
	#[inline]
	pub fn decode<T: DeserializeRevisioned>(self) -> Result<T, Error> {
		T::deserialize_revisioned(self.reader)
	}

	/// Skip the variant payload as type `T`.
	#[inline]
	pub fn skip<T: SkipRevisioned>(self) -> Result<(), Error> {
		T::skip_revisioned(self.reader)
	}

	/// Walk into the variant payload as type `T`, transferring ownership
	/// of the underlying reader to the returned walker.
	#[inline]
	pub fn into_walk<T: WalkRevisioned>(self) -> Result<T::Walker<'r, R>, Error> {
		T::walk_revisioned(self.reader)
	}

	/// Borrow the underlying reader.
	#[inline]
	pub fn reader(&mut self) -> &mut R {
		self.reader
	}

	/// Surrender the underlying reader without consuming the payload.
	#[inline]
	pub fn into_reader(self) -> &'r mut R {
		self.reader
	}
}

// -----------------------------------------------------------------------------
// Convenience walkers used by enums (Option/Result already specialised above)
// -----------------------------------------------------------------------------

/// Internal helper that reads the `u32` discriminant of an enum body and
/// hands the reader back. Intended for hand-rolled walkers; the derive macro
/// emits the same prelude inline.
#[inline]
pub fn read_enum_discriminant<R: Read>(reader: &mut R) -> Result<u32, Error> {
	u32::deserialize_revisioned(reader)
}