rhaiper-map 0.1.0

Resolve Source Map v3 positions without std, for tracing Rhai runtime errors on-device
Documentation
//! Base64 VLQ, the integer encoding used by the `mappings` field of a Source Map v3.
//!
//! Values are zig-zag encoded (sign in the low bit), then emitted five bits at a time, least
//! significant group first, with bit 6 (`0x20`) set on every group but the last.

use alloc::string::String;

const ALPHABET: &[u8; 64] = b"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
const CONTINUATION: u32 = 0b10_0000;
const VALUE_MASK: u32 = 0b01_1111;

/// Appends `value` to `out`.
pub fn encode(value: i64, out: &mut String) {
    let mut bits = if value < 0 {
        (value.unsigned_abs() << 1) | 1
    } else {
        (value as u64) << 1
    };
    loop {
        let mut digit = (bits as u32) & VALUE_MASK;
        bits >>= 5;
        if bits > 0 {
            digit |= CONTINUATION;
        }
        out.push(ALPHABET[digit as usize] as char);
        if bits == 0 {
            return;
        }
    }
}

fn digit_of(ch: u8) -> Option<u32> {
    let value = match ch {
        b'A'..=b'Z' => ch - b'A',
        b'a'..=b'z' => ch - b'a' + 26,
        b'0'..=b'9' => ch - b'0' + 52,
        b'+' => 62,
        b'/' => 63,
        _ => return None,
    };
    Some(value as u32)
}

/// Reads VLQ values out of one mapping segment.
pub struct Decoder<'a> {
    bytes: &'a [u8],
    cursor: usize,
}

impl<'a> Decoder<'a> {
    pub fn new(segment: &'a str) -> Self {
        Self {
            bytes: segment.as_bytes(),
            cursor: 0,
        }
    }

    pub fn is_done(&self) -> bool {
        self.cursor >= self.bytes.len()
    }

    /// Reads the next value, or `None` if the segment is exhausted or malformed.
    pub fn next_value(&mut self) -> Option<i64> {
        let mut result: u64 = 0;
        let mut shift = 0;
        loop {
            let ch = *self.bytes.get(self.cursor)?;
            self.cursor += 1;
            let digit = digit_of(ch)?;
            // Refuse to shift past the width we can represent rather than wrapping.
            if shift > 63 {
                return None;
            }
            result |= u64::from(digit & VALUE_MASK) << shift;
            shift += 5;
            if digit & CONTINUATION == 0 {
                break;
            }
        }
        let magnitude = (result >> 1) as i64;
        Some(if result & 1 == 1 {
            -magnitude
        } else {
            magnitude
        })
    }
}

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

    fn round_trip(value: i64) {
        let mut s = String::new();
        encode(value, &mut s);
        let mut d = Decoder::new(&s);
        assert_eq!(d.next_value(), Some(value), "encoded as {s:?}");
        assert!(d.is_done(), "{s:?} had trailing data");
    }

    #[test]
    fn round_trips() {
        for value in [
            0, 1, -1, 15, 16, -16, 17, 511, 512, -512, 1_000_000, -1_000_000,
        ] {
            round_trip(value);
        }
    }

    #[test]
    fn matches_known_encodings() {
        // Values from the Source Map v3 specification's worked examples.
        let mut s = String::new();
        encode(0, &mut s);
        assert_eq!(s, "A");
        s.clear();
        encode(1, &mut s);
        assert_eq!(s, "C");
        s.clear();
        encode(-1, &mut s);
        assert_eq!(s, "D");
        s.clear();
        encode(16, &mut s);
        assert_eq!(s, "gB");
    }

    #[test]
    fn rejects_invalid_characters() {
        assert_eq!(Decoder::new("*").next_value(), None);
        assert_eq!(Decoder::new("").next_value(), None);
        // Truncated continuation.
        assert_eq!(Decoder::new("g").next_value(), None);
    }

    #[test]
    fn decodes_multiple_fields() {
        let mut s = String::new();
        for v in [0, 0, 5, 12] {
            encode(v, &mut s);
        }
        let mut d = Decoder::new(&s);
        let got: alloc::vec::Vec<i64> = core::iter::from_fn(|| d.next_value()).collect();
        assert_eq!(got, [0, 0, 5, 12].to_vec());
    }
}