gwseq-io 0.2.1

//! The read-name tokeniser.
//!
//! Reference: `docs/cram_codecs_v3.1.md` §5.
//!
//! Read names are structured — `I17_08765:2:123:61541:01763#9` — and the
//! structure repeats down the file. So a name is cut into tokens by position
//! (`I17_08765:`, `2`, `:`, `123`, …), each *column* of tokens becomes its own
//! byte stream, and each stream is entropy-coded on its own. A name is then
//! encoded as differences from an earlier name: this token matches, this one is
//! the previous value plus three, this whole name is a duplicate of the one
//! four back.
//!
//! §5 calls it "a format within a format", which is exactly right — this is a
//! container of up to 128 × 13 sub-streams, each a complete rANS N×16 or
//! arithmetic-coded stream. It is only ever used for the `RN` data series.
//!
//! # What the streams are indexed by
//!
//! `B[position][type]`. Position 0 is the per-name meta-data — is this name a
//! duplicate, and of which earlier one — and positions 1 upward are the tokens
//! of the name itself. The *type* stream at a position says what kind each
//! token is, and that in turn says which of the other streams at that position
//! its value comes from. A position whose type stream would be "one real type
//! then nothing but MATCH" is left out of the file entirely and rebuilt here.

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

use super::{arith, rans4x16, ByteReader, MAX_CODEC_LEN};

/// Token types, §5's table.
mod token {
    pub const TYPE: u8 = 0;
    pub const STRING: u8 = 1;
    pub const CHAR: u8 = 2;
    pub const DIGITS0: u8 = 3;
    pub const DZLEN: u8 = 4;
    pub const DUP: u8 = 5;
    pub const DIFF: u8 = 6;
    pub const DIGITS: u8 = 7;
    pub const DELTA: u8 = 8;
    pub const DELTA0: u8 = 9;
    pub const MATCH: u8 = 10;
    pub const END: u8 = 12;
    /// One past the last type, which is how wide the per-position array is.
    pub const COUNT: usize = 13;
}

/// §5: "A maximum of 128 tokens are permitted within any single read name."
const MAX_POSITIONS: usize = 128;

/// A decoded sub-stream and how far into it we have read.
#[derive(Debug, Default, Clone)]
struct TokenStream {
    data: Vec<u8>,
    pos: usize,
}

impl TokenStream {
    fn u8(&mut self, path: &str) -> Result<u8> {
        let byte = *self
            .data
            .get(self.pos)
            .ok_or_else(|| Error::corrupt(path, 0, "a name token stream ran out mid-name"))?;
        self.pos += 1;
        Ok(byte)
    }

    fn u32(&mut self, path: &str) -> Result<u32> {
        let end = self.pos + 4;
        let bytes = self
            .data
            .get(self.pos..end)
            .ok_or_else(|| Error::corrupt(path, 0, "a name token stream ran out mid-value"))?;
        self.pos = end;
        Ok(u32::from_le_bytes(bytes.try_into().expect("four bytes")))
    }

    /// A NUL-terminated string, the terminator consumed but not returned.
    fn string(&mut self, path: &str) -> Result<&[u8]> {
        let rest = &self.data[self.pos.min(self.data.len())..];
        let end = memchr::memchr(0, rest)
            .ok_or_else(|| Error::corrupt(path, 0, "a name token string with no terminator"))?;
        self.pos += end + 1;
        Ok(&rest[..end])
    }
}

/// Every sub-stream, by position and type.
struct Streams {
    /// `positions[p][type]`, allocated only as far as the file goes.
    positions: Vec<[TokenStream; token::COUNT]>,
}

impl Streams {
    fn get(&mut self, position: usize, kind: u8, path: &str) -> Result<&mut TokenStream> {
        self.positions
            .get_mut(position)
            .and_then(|slot| slot.get_mut(kind as usize))
            .ok_or_else(|| {
                Error::corrupt(
                    path,
                    0,
                    format!(
                        "a read name wants token stream ({position}, {kind}), which the block \
                         does not carry"
                    ),
                )
            })
    }
}

/// Every name in the block, and every token of every name, in three buffers.
///
/// A token is a range of `bytes`; a name is its tokens written one after
/// another, so a name is a range of `bytes` too — which means the names being
/// built *are* the block's output and nothing is copied out at the end.
///
/// The obvious shape is a `Vec<u8>` per name beside a `Vec<Vec<u8>>` of its
/// tokens, and that is what this was. It costs an allocation per token, about
/// eleven per name, and it keeps every one of them alive until the block ends,
/// because §5 lets a name match against *any* earlier name in the block — a
/// hundred thousand live `Vec`s for a block of ten thousand names. Measured on
/// a ten-million-read CRAM 3.1 file, that was 85% of every allocation the whole
/// reader made: 13.6 allocations per record against 2.1 for the same reads with
/// their names gzipped instead.
#[derive(Default)]
struct Arena {
    /// Every name, NUL-terminated, in order. The block's output.
    bytes: Vec<u8>,
    /// `(start, end)` into `bytes`, for every token of every name in turn.
    spans: Vec<(u32, u32)>,
    names: Vec<Name>,
}

/// Where one name's bytes and tokens are.
#[derive(Clone, Copy)]
struct Name {
    /// Index into [`Arena::spans`] of this name's first token.
    tokens: u32,
    /// How many tokens it has, the `END` included — §5 numbers them from one,
    /// so token `p` of this name is `spans[tokens + p - 1]`.
    count: u32,
    /// The name itself in `bytes`, without its terminator.
    start: u32,
    end: u32,
}

impl Arena {
    /// The span of token `position` of name `previous`, for the token types
    /// that are expressed against an earlier name.
    fn earlier(
        &self,
        previous: usize,
        n: usize,
        position: usize,
        path: &str,
    ) -> Result<(u32, u32)> {
        // `previous == n` is how the first name in a block is written (a
        // `DIFF` of zero); §5 forbids MATCH and DELTA there, and this is what
        // enforces it — those types are the only ones that reach for it.
        if previous == n {
            return Err(Error::corrupt(
                path,
                0,
                "the first read name of a block uses a match or delta token, which \
                 has nothing to refer to",
            ));
        }
        let name = self.names.get(previous).ok_or_else(|| {
            Error::corrupt(path, 0, format!("a read name refers to name {previous}"))
        })?;
        if position == 0 || position > name.count as usize {
            return Err(Error::corrupt(
                path,
                0,
                format!("a read name matches token {position} of a name that has no such token"),
            ));
        }
        Ok(self.spans[name.tokens as usize + position - 1])
    }
}

/// Decode a name-tokeniser block into NUL-terminated names.
pub fn decode(data: &[u8], path: &str, offset: u64) -> Result<Vec<u8>> {
    let mut reader = ByteReader::new(data, path, offset);
    let uncompressed_len = reader.u32()? as usize;
    let n_names = reader.u32()? as usize;
    let use_arith = reader.u8()? != 0;

    if uncompressed_len > MAX_CODEC_LEN {
        return Err(Error::corrupt(
            path,
            offset,
            format!("a name block declaring {uncompressed_len} bytes, past this reader's ceiling"),
        ));
    }
    // Each name costs at least its terminator, so this bounds the name count by
    // something the file has already committed to — before anything is
    // allocated per name.
    if n_names > uncompressed_len {
        return Err(Error::corrupt(
            path,
            offset,
            format!("a name block of {n_names} names in {uncompressed_len} bytes"),
        ));
    }

    let mut streams = read_token_streams(&mut reader, n_names, use_arith, path, offset)?;

    let mut arena = Arena {
        bytes: Vec::with_capacity(uncompressed_len.min(1 << 22)),
        // A name is at least its `DIFF`, one token and an `END`, so this is an
        // under-estimate rather than a promise.
        spans: Vec::with_capacity(n_names.saturating_mul(4).min(1 << 22)),
        names: Vec::with_capacity(n_names),
    };
    for n in 0..n_names {
        decode_name(n, &mut streams, &mut arena, path)?;
    }
    Ok(arena.bytes)
}

/// §5's `DecodeTokenByteStreams`.
fn read_token_streams(
    reader: &mut ByteReader<'_>,
    n_names: usize,
    use_arith: bool,
    path: &str,
    offset: u64,
) -> Result<Streams> {
    let mut positions: Vec<[TokenStream; token::COUNT]> = Vec::new();
    // §5 walks positions with a counter that starts before the first, so the
    // "new position" flag on the very first entry brings it to zero.
    let mut position: usize = usize::MAX;
    while !reader.is_empty() {
        let ttype = reader.u8()?;
        let is_new_position = ttype & 128 != 0;
        let is_duplicate = ttype & 64 != 0;
        let kind = ttype & 63;
        if kind as usize >= token::COUNT {
            return Err(Error::corrupt(
                path,
                offset,
                format!("a name token stream of type {kind}, which §5 does not define"),
            ));
        }

        if is_new_position {
            position = position.wrapping_add(1);
            if position >= MAX_POSITIONS {
                return Err(Error::corrupt(
                    path,
                    offset,
                    format!("a read name of more than {MAX_POSITIONS} tokens"),
                ));
            }
            positions.resize_with(position + 1, Default::default);
            // A position whose type stream is one real type then nothing but
            // MATCH is not written down. It is recognisable because the first
            // stream at a new position is not the type stream, and it is
            // rebuilt here rather than special-cased at every use.
            if kind != token::TYPE {
                // One real type then nothing but MATCH — and no entries at all
                // for a block that declares no names, which a corrupt one can.
                let mut synthetic = vec![token::MATCH; n_names];
                if let Some(first) = synthetic.first_mut() {
                    *first = kind;
                }
                positions[position][token::TYPE as usize] = TokenStream {
                    data: synthetic,
                    pos: 0,
                };
            }
        }
        if position == usize::MAX {
            return Err(Error::corrupt(
                path,
                offset,
                "a name token stream before any position was opened",
            ));
        }

        let decoded = if is_duplicate {
            let from_position = reader.u8()? as usize;
            let from_kind = reader.u8()? as usize;
            positions
                .get(from_position)
                .and_then(|slot| slot.get(from_kind))
                .ok_or_else(|| {
                    Error::corrupt(
                        path,
                        offset,
                        format!(
                            "a name token stream duplicating ({from_position}, {from_kind}), \
                             which comes later or not at all"
                        ),
                    )
                })?
                .data
                .clone()
        } else {
            let compressed_len = reader.length()?;
            let bytes = reader.take(compressed_len)?;
            if use_arith {
                arith::decode(bytes, path, offset)?
            } else {
                rans4x16::decode(bytes, path, offset)?
            }
        };
        positions[position][kind as usize] = TokenStream {
            data: decoded,
            pos: 0,
        };
    }
    Ok(Streams { positions })
}

/// §5's `DecodeSingleName`.
fn decode_name(n: usize, streams: &mut Streams, arena: &mut Arena, path: &str) -> Result<()> {
    let kind = streams.get(0, token::TYPE, path)?.u8(path)?;
    // §5: position 0 says whether this name duplicates an earlier one or
    // differs from it, and nothing else.
    if kind != token::DUP && kind != token::DIFF {
        return Err(Error::corrupt(
            path,
            0,
            format!("read name {n} opens with token type {kind}, which is neither DUP nor DIFF"),
        ));
    }
    let distance = streams.get(0, kind, path)?.u32(path)? as usize;
    // The name this one is expressed against, which is not in general the one
    // before it.
    let previous = n.checked_sub(distance).ok_or_else(|| {
        Error::corrupt(
            path,
            0,
            format!("read name {n} refers back {distance}, past the start of the block"),
        )
    })?;

    if kind == token::DUP {
        if previous == n {
            return Err(Error::corrupt(
                path,
                0,
                format!("read name {n} is marked a duplicate of itself"),
            ));
        }
        let source = *arena.names.get(previous).ok_or_else(|| {
            Error::corrupt(path, 0, format!("a read name duplicates name {previous}"))
        })?;
        // The bytes are copied, because they are the output. The token spans
        // are shared rather than copied: a later name may match against this
        // duplicate as readily as against the original, and the two hold the
        // same bytes, so the original's spans read the same either way.
        let start = arena.bytes.len() as u32;
        arena
            .bytes
            .extend_from_within(source.start as usize..source.end as usize);
        let end = arena.bytes.len() as u32;
        arena.names.push(Name {
            tokens: source.tokens,
            count: source.count,
            start,
            end,
        });
        arena.bytes.push(0);
        return Ok(());
    }

    let tokens = arena.spans.len() as u32;
    let start = arena.bytes.len() as u32;
    let mut count = 0u32;
    let mut position = 1usize;
    loop {
        if position >= MAX_POSITIONS {
            return Err(Error::corrupt(
                path,
                0,
                format!("a read name of more than {MAX_POSITIONS} tokens"),
            ));
        }
        let kind = streams.get(position, token::TYPE, path)?.u8(path)?;
        let from = arena.bytes.len() as u32;
        match kind {
            token::CHAR => {
                let byte = streams.get(position, token::CHAR, path)?.u8(path)?;
                arena.bytes.push(byte);
            }
            token::STRING => {
                let text = streams.get(position, token::STRING, path)?.string(path)?;
                arena.bytes.extend_from_slice(text);
            }
            token::DIGITS => {
                let value = streams.get(position, token::DIGITS, path)?.u32(path)?;
                push_digits(&mut arena.bytes, value);
            }
            token::DIGITS0 => {
                let value = streams.get(position, token::DIGITS0, path)?.u32(path)?;
                let width = streams.get(position, token::DZLEN, path)?.u8(path)? as usize;
                push_padded(&mut arena.bytes, value, width);
            }
            token::DELTA => {
                let span = arena.earlier(previous, n, position, path)?;
                let base = parse_number(&arena.bytes[span.0 as usize..span.1 as usize], path)?;
                let step = u32::from(streams.get(position, token::DELTA, path)?.u8(path)?);
                push_digits(&mut arena.bytes, base.wrapping_add(step));
            }
            token::DELTA0 => {
                let span = arena.earlier(previous, n, position, path)?;
                let base = parse_number(&arena.bytes[span.0 as usize..span.1 as usize], path)?;
                // §5: DELTA0 takes its width from the token it follows rather
                // than reading a DZLEN of its own.
                let width = (span.1 - span.0) as usize;
                let step = u32::from(streams.get(position, token::DELTA0, path)?.u8(path)?);
                push_padded(&mut arena.bytes, base.wrapping_add(step), width);
            }
            token::MATCH => {
                let span = arena.earlier(previous, n, position, path)?;
                arena
                    .bytes
                    .extend_from_within(span.0 as usize..span.1 as usize);
            }
            // NOP, END, and anything else contribute nothing. NOP exists only
            // to keep positions lined up between names.
            _ => {}
        }
        arena.spans.push((from, arena.bytes.len() as u32));
        count += 1;
        position += 1;
        if kind == token::END {
            break;
        }
    }

    let end = arena.bytes.len() as u32;
    arena.names.push(Name {
        tokens,
        count,
        start,
        end,
    });
    // §5: END adds a nul, and `ulen` counts one terminator per name.
    arena.bytes.push(0);
    Ok(())
}

/// A `u32` as decimal digits, appended.
fn push_digits(out: &mut Vec<u8>, value: u32) {
    // Ten digits is the widest `u32`.
    let mut digits = [0u8; 10];
    let mut rest = value;
    let mut at = digits.len();
    loop {
        at -= 1;
        digits[at] = b'0' + (rest % 10) as u8;
        rest /= 10;
        if rest == 0 {
            break;
        }
    }
    out.extend_from_slice(&digits[at..]);
}

/// The same, left-padded with zeros to `width` — and never truncated to it: a
/// number wider than its field keeps all of its digits.
fn push_padded(out: &mut Vec<u8>, value: u32, width: usize) {
    let start = out.len();
    push_digits(out, value);
    let written = out.len() - start;
    if let Some(pad) = width.checked_sub(written).filter(|pad| *pad > 0) {
        out.resize(out.len() + pad, b'0');
        // The zeros went on the end; this brings them to the front.
        out[start..].rotate_right(pad);
    }
}

/// The numeric value of a token a delta is measured from.
fn parse_number(token: &[u8], path: &str) -> Result<u32> {
    let mut value: u32 = 0;
    if token.is_empty() {
        return Err(Error::corrupt(
            path,
            0,
            "a read name delta against a token with no digits in it",
        ));
    }
    for &byte in token {
        if !byte.is_ascii_digit() {
            return Err(Error::corrupt(
                path,
                0,
                "a read name delta against a token that is not a number",
            ));
        }
        value = value.wrapping_mul(10).wrapping_add(u32::from(byte - b'0'));
    }
    Ok(value)
}

#[cfg(test)]
mod tests {
    use super::*;

    /// Build a tokeniser block from token streams given per (position, type),
    /// with every sub-stream stored uncompressed.
    struct Builder {
        n_names: usize,
        entries: Vec<(usize, u8, Vec<u8>)>,
    }

    impl Builder {
        fn new(n_names: usize) -> Self {
            Self {
                n_names,
                entries: Vec::new(),
            }
        }

        fn stream(mut self, position: usize, kind: u8, data: Vec<u8>) -> Self {
            self.entries.push((position, kind, data));
            self
        }

        fn build(self, uncompressed_len: usize) -> Vec<u8> {
            let mut out = Vec::new();
            out.extend_from_slice(&(uncompressed_len as u32).to_le_bytes());
            out.extend_from_slice(&(self.n_names as u32).to_le_bytes());
            out.push(0); // rANS, not arithmetic
            let mut last_position = usize::MAX;
            for (position, kind, data) in self.entries {
                let mut ttype = kind;
                if position != last_position {
                    ttype |= 128;
                    last_position = position;
                }
                out.push(ttype);
                // The sub-stream: a rANS N×16 `Cat` stream, which is the
                // format's own way of saying "stored plainly".
                let mut sub = vec![32u8]; // CAT
                let mut len = data.len() as u32;
                let mut groups = Vec::new();
                loop {
                    groups.push((len & 0x7f) as u8);
                    len >>= 7;
                    if len == 0 {
                        break;
                    }
                }
                for (i, group) in groups.iter().enumerate().rev() {
                    sub.push(if i == 0 { *group } else { group | 0x80 });
                }
                sub.extend_from_slice(&data);

                let mut clen = sub.len() as u32;
                let mut groups = Vec::new();
                loop {
                    groups.push((clen & 0x7f) as u8);
                    clen >>= 7;
                    if clen == 0 {
                        break;
                    }
                }
                for (i, group) in groups.iter().enumerate().rev() {
                    out.push(if i == 0 { *group } else { group | 0x80 });
                }
                out.extend_from_slice(&sub);
            }
            out
        }
    }

    fn names(decoded: &[u8]) -> Vec<String> {
        decoded
            .split(|b| *b == 0)
            .filter(|s| !s.is_empty())
            .map(|s| String::from_utf8_lossy(s).into_owned())
            .collect()
    }

    /// The specification's own example, tokenised the way §5 describes it:
    /// a shared prefix, a matching field, two numbers that differ, and a
    /// constant suffix.
    #[test]
    fn the_spec_example_names_rebuild_from_their_columns() {
        let block = Builder::new(3)
            // Position 0: every name a DIFF, at distances 0, 1, 1.
            .stream(0, token::TYPE, vec![token::DIFF; 3])
            .stream(0, token::DIFF, {
                let mut v = Vec::new();
                for d in [0u32, 1, 1] {
                    v.extend_from_slice(&d.to_le_bytes());
                }
                v
            })
            // Position 1: the shared prefix, matched after the first name.
            .stream(
                1,
                token::TYPE,
                vec![token::STRING, token::MATCH, token::MATCH],
            )
            .stream(1, token::STRING, b"I17_08765:2:\0".to_vec())
            // Position 2: 123, 123, 124 — a digit then two deltas.
            .stream(
                2,
                token::TYPE,
                vec![token::DIGITS, token::MATCH, token::DELTA],
            )
            .stream(2, token::DIGITS, 123u32.to_le_bytes().to_vec())
            .stream(2, token::DELTA, vec![1])
            // Position 3: a colon, matched.
            .stream(
                3,
                token::TYPE,
                vec![token::CHAR, token::MATCH, token::MATCH],
            )
            .stream(3, token::CHAR, b":".to_vec())
            // Position 4: three unrelated numbers.
            .stream(4, token::TYPE, vec![token::DIGITS; 3])
            .stream(4, token::DIGITS, {
                let mut v = Vec::new();
                for d in [61541u32, 1636, 45613] {
                    v.extend_from_slice(&d.to_le_bytes());
                }
                v
            })
            .stream(
                5,
                token::TYPE,
                vec![token::CHAR, token::MATCH, token::MATCH],
            )
            .stream(5, token::CHAR, b":".to_vec())
            // Position 6: numbers with leading zeros.
            .stream(6, token::TYPE, vec![token::DIGITS0; 3])
            .stream(6, token::DIGITS0, {
                let mut v = Vec::new();
                for d in [1763u32, 8611, 16161] {
                    v.extend_from_slice(&d.to_le_bytes());
                }
                v
            })
            .stream(6, token::DZLEN, vec![5, 5, 5])
            .stream(
                7,
                token::TYPE,
                vec![token::STRING, token::MATCH, token::MATCH],
            )
            .stream(7, token::STRING, b"#9\0".to_vec())
            .stream(8, token::TYPE, vec![token::END; 3])
            .build(3 * 29);

        let decoded = decode(&block, "test", 0).expect("decodes");
        assert_eq!(
            names(&decoded),
            vec![
                "I17_08765:2:123:61541:01763#9",
                "I17_08765:2:123:1636:08611#9",
                "I17_08765:2:124:45613:16161#9",
            ]
        );
    }

    /// A position whose types are "one real type then all MATCH" is left out of
    /// the file, and has to be rebuilt from the fact that the position's first
    /// stream is not a type stream.
    #[test]
    fn a_missing_type_stream_is_rebuilt_as_one_type_then_matches() {
        let block = Builder::new(3)
            .stream(0, token::TYPE, vec![token::DIFF; 3])
            .stream(0, token::DIFF, {
                let mut v = Vec::new();
                for d in [0u32, 1, 1] {
                    v.extend_from_slice(&d.to_le_bytes());
                }
                v
            })
            // No TYPE stream at position 1 at all: STRING comes first.
            .stream(1, token::STRING, b"read\0".to_vec())
            .stream(2, token::TYPE, vec![token::END; 3])
            .build(3 * 5);
        assert_eq!(
            names(&decode(&block, "test", 0).expect("decodes")),
            vec!["read", "read", "read"]
        );
    }

    #[test]
    fn a_duplicate_name_copies_the_one_it_names() {
        let block = Builder::new(3)
            .stream(0, token::TYPE, vec![token::DIFF, token::DIFF, token::DUP])
            .stream(0, token::DIFF, {
                let mut v = Vec::new();
                for d in [0u32, 1] {
                    v.extend_from_slice(&d.to_le_bytes());
                }
                v
            })
            // The third name duplicates the one two back — the first.
            .stream(0, token::DUP, 2u32.to_le_bytes().to_vec())
            .stream(1, token::TYPE, vec![token::STRING, token::STRING])
            .stream(1, token::STRING, b"aaa\0bbb\0".to_vec())
            .stream(2, token::TYPE, vec![token::END; 2])
            .build(12);
        assert_eq!(
            names(&decode(&block, "test", 0).expect("decodes")),
            vec!["aaa", "bbb", "aaa"]
        );
    }

    /// A name may match against a duplicate, so a duplicate has to carry the
    /// tokens of whatever it duplicated and not just its bytes.
    #[test]
    fn a_name_can_match_against_a_duplicate() {
        let block = Builder::new(4)
            .stream(
                0,
                token::TYPE,
                vec![token::DIFF, token::DIFF, token::DUP, token::DIFF],
            )
            .stream(0, token::DIFF, {
                let mut v = Vec::new();
                // The first differs from itself, the second from the first,
                // and the fourth from the third — which is the duplicate.
                for d in [0u32, 1, 1] {
                    v.extend_from_slice(&d.to_le_bytes());
                }
                v
            })
            // The third duplicates the one two back — the first.
            .stream(0, token::DUP, 2u32.to_le_bytes().to_vec())
            .stream(
                1,
                token::TYPE,
                vec![token::STRING, token::STRING, token::MATCH],
            )
            .stream(1, token::STRING, b"aaa\0bbb\0".to_vec())
            .stream(2, token::TYPE, vec![token::END, token::END, token::CHAR])
            .stream(2, token::CHAR, vec![b'X'])
            .stream(3, token::TYPE, vec![token::END])
            .build(17);
        assert_eq!(
            names(&decode(&block, "test", 0).expect("decodes")),
            vec!["aaa", "bbb", "aaa", "aaaX"]
        );
    }

    /// `DELTA0` takes its width from the token it follows rather than storing
    /// one, which is the only place a length is inherited.
    #[test]
    fn delta0_keeps_the_width_of_the_token_it_follows() {
        let block = Builder::new(2)
            .stream(0, token::TYPE, vec![token::DIFF; 2])
            .stream(0, token::DIFF, {
                let mut v = Vec::new();
                for d in [0u32, 1] {
                    v.extend_from_slice(&d.to_le_bytes());
                }
                v
            })
            .stream(1, token::TYPE, vec![token::DIGITS0, token::DELTA0])
            .stream(1, token::DIGITS0, 98u32.to_le_bytes().to_vec())
            .stream(1, token::DZLEN, vec![5])
            .stream(1, token::DELTA0, vec![3])
            .stream(2, token::TYPE, vec![token::END; 2])
            .build(12);
        // 00098, then +3 keeping five digits.
        assert_eq!(
            names(&decode(&block, "test", 0).expect("decodes")),
            vec!["00098", "00101"]
        );
    }

    /// §5 forbids MATCH and DELTA on the first name, which has nothing to refer
    /// to. A file that does it anyway must not read its own half-built token.
    #[test]
    fn a_first_name_that_matches_is_refused_rather_than_read_from_itself() {
        let block = Builder::new(1)
            .stream(0, token::TYPE, vec![token::DIFF])
            .stream(0, token::DIFF, 0u32.to_le_bytes().to_vec())
            .stream(1, token::TYPE, vec![token::MATCH])
            .stream(2, token::TYPE, vec![token::END])
            .build(4);
        assert!(decode(&block, "test", 0).is_err());
    }

    #[test]
    fn a_name_duplicating_itself_is_refused_rather_than_looping() {
        let block = Builder::new(1)
            .stream(0, token::TYPE, vec![token::DUP])
            .stream(0, token::DUP, 0u32.to_le_bytes().to_vec())
            .build(4);
        assert!(decode(&block, "test", 0).is_err());
    }

    #[test]
    fn left_padding_never_truncates_a_number_wider_than_its_field() {
        let padded = |value, width| {
            let mut out = Vec::new();
            push_padded(&mut out, value, width);
            out
        };
        assert_eq!(padded(123, 5), b"00123");
        assert_eq!(padded(123, 3), b"123");
        assert_eq!(padded(123, 0), b"123");
        assert_eq!(padded(0, 2), b"00");
        // Appended, not written: whatever was already there stays put, which
        // is the whole reason these go straight into the name buffer.
        let mut out = b"name:".to_vec();
        push_padded(&mut out, 7, 3);
        assert_eq!(out, b"name:007");
    }

    #[test]
    fn digits_are_written_without_a_string_in_between() {
        let digits = |value| {
            let mut out = Vec::new();
            push_digits(&mut out, value);
            out
        };
        assert_eq!(digits(0), b"0");
        assert_eq!(digits(7), b"7");
        assert_eq!(digits(4_294_967_295), b"4294967295");
    }
}