verstamp 0.1.0

An explicit version tag in the byte stream, plus a forward migration chain, for binary formats that can't describe themselves.
Documentation
//! The forward migration chain.
//!
//! A [`Chain`] routes a framed stream to exactly one decoder, then folds the
//! result forward through one migration per version until it reaches the
//! current type. Old bytes climb the chain; current bytes decode in place.
//!
//! Build a chain from a [`Frame`](crate::wire::Frame): start with
//! [`at`](crate::wire::Frame::at) for the oldest version, add
//! [`then`](Chain::then) for each newer version, and finish with
//! [`done`](Chain::done).

use std::cmp::Ordering;

use crate::error::{BoxError, Error};

/// One forward migration step.
///
/// Implement this to say how a value grows from the previous version into this
/// one. The chain calls [`migrate`](Migrate::migrate) whenever it decoded an
/// older payload and needs to carry it forward.
///
/// The associated [`From`](Migrate::From) type names the type a step migrates
/// from, so each step runs `From` into `Self` and there is no reverse. Whether
/// that direction points at newer versions is a convention you keep: the
/// compiler checks the shape of the step, not which version is newer.
///
/// ```
/// use verstamp::Migrate;
///
/// struct V1 { volume: u8 }
/// struct V2 { volume: u8, muted: bool }
///
/// impl Migrate for V2 {
///     type From = V1;
///     fn migrate(old: V1) -> V2 {
///         V2 { volume: old.volume, muted: false }
///     }
/// }
/// ```
pub trait Migrate {
    /// The previous version this type migrates from.
    type From;

    /// Turn a value of the previous version into this one.
    fn migrate(from: Self::From) -> Self;
}

/// Adapt a tail-returning decoder into the `(value, bytes_consumed)` shape that
/// [`at`](crate::wire::Frame::at) and [`then`](Chain::then) expect.
///
/// Some decoders report what they read by handing back the unconsumed tail
/// rather than a count. [`postcard::take_from_bytes`] returns `(T, &[u8])`,
/// where the slice is the suffix of the input it did not touch. `from_tail`
/// turns that suffix into the count `payload.len() - tail.len()`. A tail that is
/// not a suffix of the payload is rejected by the trailing-byte check.
///
/// ```
/// use verstamp::{from_tail, frame, read};
///
/// // The shape `postcard::take_from_bytes` has: the value, plus the leftover
/// // tail it did not read.
/// fn take_u16(b: &[u8]) -> Result<(u16, &[u8]), &'static str> {
///     if b.len() < 2 {
///         return Err("short");
///     }
///     Ok((u16::from_be_bytes([b[0], b[1]]), &b[2..]))
/// }
///
/// let bytes = frame(1, &[0x12, 0x34]);
/// let n: u16 = read(&bytes)?.at(1, from_tail(take_u16)).done()?;
/// assert_eq!(n, 0x1234);
/// # Ok::<(), verstamp::Error>(())
/// ```
///
/// If the wrapped decoder leaves bytes in the tail, the count comes up short and
/// the chain reports [`Error::TrailingBytes`] instead of returning the value.
///
/// [`postcard::take_from_bytes`]: https://docs.rs/postcard/1/postcard/fn.take_from_bytes.html
pub fn from_tail<T, E, F>(decode: F) -> impl FnOnce(&[u8]) -> Result<(T, usize), E>
where
    F: FnOnce(&[u8]) -> Result<(T, &[u8]), E>,
{
    move |bytes: &[u8]| decode(bytes).map(|(value, tail)| (value, consumed_from_tail(bytes, tail)))
}

/// Count the bytes of `payload` a decoder consumed, given the `tail` it handed
/// back.
///
/// The count is `payload.len() - tail.len()` when `tail` is a suffix of
/// `payload`: its end lines up with the end of `payload` and its start does not
/// precede it. A slice that fails either test reports a count the trailing-byte
/// check rejects, even when `payload` is empty. The comparison is over addresses
/// only; no pointer is dereferenced.
fn consumed_from_tail(payload: &[u8], tail: &[u8]) -> usize {
    let payload_start = payload.as_ptr() as usize;
    let payload_end = payload_start.wrapping_add(payload.len());
    let tail_start = tail.as_ptr() as usize;
    let tail_end = tail_start.wrapping_add(tail.len());
    if tail_start >= payload_start && tail_end == payload_end {
        tail_start - payload_start
    } else if payload.is_empty() {
        // A foreign tail on an empty payload cannot report 0 consumed: that
        // would equal the payload length and pass the trailing-byte check.
        1
    } else {
        0
    }
}

/// What the chain knows about the tag so far.
enum State<T> {
    /// The tag is newer than every version registered up to this point.
    Pending,
    /// The tag fell below the oldest version, or into a gap between versions.
    Gap,
    /// The tag matched at or below this point; carry the (possibly failed) value.
    Decoded(Result<T, Error>),
}

/// A migration chain in progress.
///
/// Each [`then`](Chain::then) advances the target type from the previous
/// version to the next. `T` is always the type reached so far, and
/// [`done`](Chain::done) returns that type.
#[must_use = "a chain does nothing until you call `done`"]
pub struct Chain<'a, T> {
    tag: u16,
    payload: &'a [u8],
    state: State<T>,
    known: Vec<u16>,
    top: u16,
}

impl<'a, T> Chain<'a, T> {
    /// Start a chain at its oldest version. Called by
    /// [`Frame::at`](crate::wire::Frame::at).
    pub(crate) fn seed<F, E>(tag: u16, payload: &'a [u8], version: u16, decode: F) -> Chain<'a, T>
    where
        F: FnOnce(&[u8]) -> Result<(T, usize), E>,
        E: Into<BoxError>,
    {
        let state = match tag.cmp(&version) {
            Ordering::Equal => State::Decoded(finish_decode(version, payload, decode)),
            Ordering::Less => State::Gap,
            Ordering::Greater => State::Pending,
        };
        Chain {
            tag,
            payload,
            state,
            known: vec![version],
            top: version,
        }
    }

    /// Add the next version, migrating from the previous one via [`Migrate`].
    ///
    /// If the tag is older than `version`, `decode` never runs and the value
    /// carried so far is lifted with [`U::migrate`](Migrate::migrate). If the
    /// tag equals `version`, `decode` runs here instead and no migration is
    /// applied. Newer tags keep looking.
    ///
    /// Register versions in strictly increasing order: `version` must be greater
    /// than every version added before it.
    ///
    /// # Panics
    ///
    /// Panics under the same condition as [`then_with`](Chain::then_with): a
    /// `version` not greater than every version already registered.
    ///
    /// ```
    /// use verstamp::Migrate;
    /// # #[derive(Debug, PartialEq)]
    /// struct V1 { level: u8 }
    /// # #[derive(Debug, PartialEq)]
    /// struct V2 { level: u8, hardcore: bool }
    /// impl Migrate for V2 {
    ///     type From = V1;
    ///     fn migrate(v1: V1) -> V2 { V2 { level: v1.level, hardcore: false } }
    /// }
    ///
    /// let old = verstamp::frame(1, &[5]);
    /// let current: V2 = verstamp::read(&old)?
    ///     .at(1, |b| {
    ///         if b.is_empty() {
    ///             return Err("short");
    ///         }
    ///         Ok::<_, &str>((V1 { level: b[0] }, 1))
    ///     })
    ///     .then(2, |b| {
    ///         if b.len() < 2 {
    ///             return Err("short");
    ///         }
    ///         Ok::<_, &str>((V2 { level: b[0], hardcore: b[1] != 0 }, 2))
    ///     })
    ///     .done()?;
    /// assert_eq!(current, V2 { level: 5, hardcore: false });
    /// # Ok::<(), verstamp::Error>(())
    /// ```
    pub fn then<U, F, E>(self, version: u16, decode: F) -> Chain<'a, U>
    where
        U: Migrate<From = T>,
        F: FnOnce(&[u8]) -> Result<(U, usize), E>,
        E: Into<BoxError>,
    {
        self.then_with(version, decode, U::migrate)
    }

    /// Add the next version with an explicit migration closure instead of the
    /// [`Migrate`] trait.
    ///
    /// Use this when the next type is foreign, so you cannot implement
    /// [`Migrate`] on it, or when an inline closure reads better than a trait
    /// impl. The routing rules are identical to [`then`](Chain::then), including
    /// that `version` must be greater than every version added before it.
    ///
    /// # Panics
    ///
    /// Panics if `version` is not greater than every version already registered.
    /// A version added out of order, or a duplicate, would be unreachable, so it
    /// is rejected here rather than silently dropped.
    ///
    /// ```
    /// let old = verstamp::frame(1, &[5]);
    /// let doubled: u32 = verstamp::read(&old)?
    ///     .at(1, |b| {
    ///         if b.is_empty() {
    ///             return Err("short");
    ///         }
    ///         Ok::<_, &str>((b[0] as u32, 1))
    ///     })
    ///     .then_with(2, |b| {
    ///         if b.is_empty() {
    ///             return Err("short");
    ///         }
    ///         Ok::<_, &str>((b[0] as u32, 1))
    ///     }, |v: u32| v * 2)
    ///     .done()?;
    /// assert_eq!(doubled, 10);
    /// # Ok::<(), verstamp::Error>(())
    /// ```
    pub fn then_with<U, F, E, M>(self, version: u16, decode: F, migrate: M) -> Chain<'a, U>
    where
        F: FnOnce(&[u8]) -> Result<(U, usize), E>,
        E: Into<BoxError>,
        M: FnOnce(T) -> U,
    {
        assert!(
            version > self.top,
            "verstamp: version {version} registered out of order; each `then` or \
             `then_with` must use a version greater than every earlier one \
             (highest so far is {})",
            self.top
        );
        let state = match self.state {
            // Already matched at a lower version: keep lifting forward.
            State::Decoded(carried) => State::Decoded(carried.map(migrate)),
            // A hole in the version range stays a hole.
            State::Gap => State::Gap,
            // Still hunting for the tag among newer versions.
            State::Pending => match self.tag.cmp(&version) {
                Ordering::Equal => State::Decoded(finish_decode(version, self.payload, decode)),
                Ordering::Less => State::Gap,
                Ordering::Greater => State::Pending,
            },
        };
        let mut known = self.known;
        known.push(version);
        Chain {
            tag: self.tag,
            payload: self.payload,
            state,
            known,
            top: self.top.max(version),
        }
    }

    /// Finish the chain and produce the current value.
    ///
    /// Routing resolves to one of three outcomes: the tag matched a registered
    /// version (the decoded, fully migrated value, or the decoder's error); the
    /// tag was newer than every registered version
    /// ([`Error::ForwardIncompatible`]); or the tag was older than the oldest or
    /// fell in a gap ([`Error::UnknownVersion`]).
    ///
    /// ```
    /// # #[derive(Debug)]
    /// # struct V1;
    /// // A version-2 stream read by a chain that only knows version 1.
    /// let bytes = verstamp::frame(2, b"x");
    /// let err = verstamp::read(&bytes)?
    ///     .at(1, |_b| Ok::<_, &str>((V1, 1)))
    ///     .done()
    ///     .unwrap_err();
    /// assert!(matches!(
    ///     err,
    ///     verstamp::Error::ForwardIncompatible { found: 2, current: 1 }
    /// ));
    /// # Ok::<(), verstamp::Error>(())
    /// ```
    ///
    /// # Errors
    ///
    /// Returns [`Error::ForwardIncompatible`] if the tag is newer than every
    /// registered version, or [`Error::UnknownVersion`] if it is older than the
    /// oldest or falls in a gap. If the tag matched a version, returns whatever
    /// that decoder produced: [`Error::Decode`] if the decoder failed, or
    /// [`Error::TrailingBytes`] if it did not consume the whole payload.
    pub fn done(self) -> Result<T, Error> {
        match self.state {
            State::Decoded(result) => result,
            State::Pending => Err(Error::ForwardIncompatible {
                found: self.tag,
                current: self.top,
            }),
            State::Gap => Err(Error::UnknownVersion {
                found: self.tag,
                known: self.known,
            }),
        }
    }
}

/// Run a decoder and enforce full consumption of the payload.
///
/// This is where the trailing-byte guarantee lives: a decoder that reports
/// consuming fewer (or more) bytes than the payload holds is rejected rather
/// than trusted.
fn finish_decode<T, F, E>(version: u16, payload: &[u8], decode: F) -> Result<T, Error>
where
    F: FnOnce(&[u8]) -> Result<(T, usize), E>,
    E: Into<BoxError>,
{
    match decode(payload) {
        Ok((value, consumed)) if consumed == payload.len() => Ok(value),
        Ok((_, consumed)) => Err(Error::TrailingBytes {
            version,
            consumed,
            total: payload.len(),
        }),
        Err(e) => Err(Error::Decode {
            version,
            source: e.into(),
        }),
    }
}