sourcemap/

types.rs

use std::borrow::Cow;
use std::cmp::Ordering;
use std::collections::BTreeSet;
use std::fmt;
use std::io::{Read, Write};
use std::path::Path;
use std::sync::Arc;

use crate::builder::SourceMapBuilder;
use crate::decoder::{decode, decode_slice};
use crate::encoder::encode;
use crate::errors::{Error, Result};
use crate::hermes::SourceMapHermes;
use crate::sourceview::SourceView;
use crate::utils::{find_common_prefix, greatest_lower_bound};

use debugid::DebugId;

/// Controls the `SourceMap::rewrite` behavior
///
/// Default configuration:
///
/// * `with_names`: true
/// * `with_source_contents`: true
/// * `load_local_source_contents`: false
#[derive(Debug, Clone)]
pub struct RewriteOptions<'a> {
    /// If enabled, names are kept in the rewritten sourcemap.
    pub with_names: bool,
    /// If enabled source contents are kept in the sourcemap.
    pub with_source_contents: bool,
    /// If enabled local source contents that are not in the
    /// file are automatically inlined.
    #[cfg(any(unix, windows, target_os = "redox"))]
    pub load_local_source_contents: bool,
    /// The base path to the used for source reference resolving
    /// when loading local source contents is used.
    pub base_path: Option<&'a Path>,
    /// Optionally strips common prefixes from the sources.  If
    /// an item in the list is set to `~` then the common prefix
    /// of all sources is stripped.
    pub strip_prefixes: &'a [&'a str],
}

impl<'a> Default for RewriteOptions<'a> {
    fn default() -> RewriteOptions<'a> {
        RewriteOptions {
            with_names: true,
            with_source_contents: true,
            #[cfg(any(unix, windows, target_os = "redox"))]
            load_local_source_contents: false,
            base_path: None,
            strip_prefixes: &[][..],
        }
    }
}

/// Represents the result of a decode operation
///
/// This represents either an actual sourcemap or a source map index.
/// Usually the two things are too distinct to provide a common
/// interface however for token lookup and writing back into a writer
/// general methods are provided.
#[derive(Debug, Clone)]
pub enum DecodedMap {
    /// Indicates a regular sourcemap
    Regular(SourceMap),
    /// Indicates a sourcemap index
    Index(SourceMapIndex),
    /// Indicates a sourcemap as generated by Metro+Hermes, as used by react-native
    Hermes(SourceMapHermes),
}

impl DecodedMap {
    /// Alias for `decode`.
    pub fn from_reader<R: Read>(rdr: R) -> Result<DecodedMap> {
        decode(rdr)
    }

    /// Writes a decoded sourcemap to a writer.
    pub fn to_writer<W: Write>(&self, w: W) -> Result<()> {
        match *self {
            DecodedMap::Regular(ref sm) => encode(sm, w),
            DecodedMap::Index(ref smi) => encode(smi, w),
            DecodedMap::Hermes(ref smh) => encode(smh, w),
        }
    }

    /// Shortcut to look up a token on either an index or a
    /// regular sourcemap.  This method can only be used if
    /// the contained index actually contains embedded maps
    /// or it will not be able to look up anything.
    pub fn lookup_token(&self, line: u32, col: u32) -> Option<Token<'_>> {
        match *self {
            DecodedMap::Regular(ref sm) => sm.lookup_token(line, col),
            DecodedMap::Index(ref smi) => smi.lookup_token(line, col),
            DecodedMap::Hermes(ref smh) => smh.lookup_token(line, col),
        }
    }

    /// Returns the original function name.
    ///
    /// `minified_name` and `source_view` are not always necessary.  For
    /// instance hermes source maps can provide this information without
    /// access to the original sources.
    pub fn get_original_function_name(
        &self,
        line: u32,
        col: u32,
        minified_name: Option<&str>,
        source_view: Option<&SourceView>,
    ) -> Option<&str> {
        match *self {
            DecodedMap::Regular(ref sm) => {
                sm.get_original_function_name(line, col, minified_name?, source_view?)
            }
            DecodedMap::Index(ref smi) => {
                smi.get_original_function_name(line, col, minified_name?, source_view?)
            }
            DecodedMap::Hermes(ref smh) => {
                if line != 0 {
                    return None;
                }
                smh.get_original_function_name(col)
            }
        }
    }
}

/// Represents a raw token
///
/// Raw tokens are used internally to represent the sourcemap
/// in a memory efficient way.  If you construct sourcemaps yourself
/// then you need to create these objects, otherwise they are invisible
/// to you as a user.
#[derive(PartialEq, Eq, Copy, Clone, Debug)]
pub struct RawToken {
    /// the destination (minified) line number (0-indexed)
    pub dst_line: u32,
    /// the destination (minified) column number (0-indexed)
    pub dst_col: u32,
    /// the source line number (0-indexed)
    pub src_line: u32,
    /// the source line column (0-indexed)
    pub src_col: u32,
    /// source identifier
    pub src_id: u32,
    /// name identifier (`!0` in case there is no associated name)
    pub name_id: u32,

    /// If true, this token is a range token.
    ///
    /// See <https://github.com/tc39/source-map-rfc/blob/main/proposals/range-mappings.md>
    pub is_range: bool,
}

/// Represents a token from a sourcemap
#[derive(Copy, Clone)]
pub struct Token<'a> {
    raw: &'a RawToken,
    pub(crate) sm: &'a SourceMap,
    pub(crate) idx: usize,
    offset: u32,
}

impl<'a> Token<'a> {
    /// The sourcemap this token is linked to.
    pub fn sourcemap(&self) -> &'a SourceMap {
        self.sm
    }
}

impl PartialEq for Token<'_> {
    fn eq(&self, other: &Token<'_>) -> bool {
        self.raw == other.raw
    }
}

impl Eq for Token<'_> {}

impl PartialOrd for Token<'_> {
    fn partial_cmp(&self, other: &Token<'_>) -> Option<Ordering> {
        Some(self.cmp(other))
    }
}

impl Ord for Token<'_> {
    fn cmp(&self, other: &Token<'_>) -> Ordering {
        macro_rules! try_cmp {
            ($a:expr, $b:expr) => {
                match $a.cmp(&$b) {
                    Ordering::Equal => {}
                    x => {
                        return x;
                    }
                }
            };
        }
        try_cmp!(self.get_dst_line(), other.get_dst_line());
        try_cmp!(self.get_dst_col(), other.get_dst_col());
        try_cmp!(self.get_source(), other.get_source());
        try_cmp!(self.get_src_line(), other.get_src_line());
        try_cmp!(self.get_src_col(), other.get_src_col());
        try_cmp!(self.get_name(), other.get_name());
        try_cmp!(self.is_range(), other.is_range());

        Ordering::Equal
    }
}

impl<'a> Token<'a> {
    /// get the destination (minified) line number
    pub fn get_dst_line(&self) -> u32 {
        self.raw.dst_line
    }

    /// get the destination (minified) column number
    pub fn get_dst_col(&self) -> u32 {
        self.raw.dst_col
    }

    /// get the destination line and column
    pub fn get_dst(&self) -> (u32, u32) {
        (self.get_dst_line(), self.get_dst_col())
    }

    /// get the source line number
    pub fn get_src_line(&self) -> u32 {
        self.raw.src_line
    }

    /// get the source column number
    pub fn get_src_col(&self) -> u32 {
        self.raw.src_col.saturating_add(self.offset)
    }

    /// get the source line and column
    pub fn get_src(&self) -> (u32, u32) {
        (self.get_src_line(), self.get_src_col())
    }

    /// Return the source ID of the token
    pub fn get_src_id(&self) -> u32 {
        self.raw.src_id
    }

    /// get the source if it exists as string
    pub fn get_source(&self) -> Option<&'a str> {
        if self.raw.src_id == !0 {
            None
        } else {
            self.sm.get_source(self.raw.src_id)
        }
    }

    /// Is there a source for this token?
    pub fn has_source(&self) -> bool {
        self.raw.src_id != !0
    }

    /// get the name if it exists as string
    pub fn get_name(&self) -> Option<&'a str> {
        if self.raw.name_id == !0 {
            None
        } else {
            self.sm.get_name(self.raw.name_id)
        }
    }

    /// returns `true` if a name exists, `false` otherwise
    pub fn has_name(&self) -> bool {
        self.get_name().is_some()
    }

    /// Return the name ID of the token
    pub fn get_name_id(&self) -> u32 {
        self.raw.name_id
    }

    /// Converts the token into a debug tuple in the form
    /// `(source, src_line, src_col, name)`
    pub fn to_tuple(&self) -> (&'a str, u32, u32, Option<&'a str>) {
        (
            self.get_source().unwrap_or(""),
            self.get_src_line(),
            self.get_src_col(),
            self.get_name(),
        )
    }

    /// Get the underlying raw token
    pub fn get_raw_token(&self) -> RawToken {
        *self.raw
    }

    /// Returns the referenced source view.
    pub fn get_source_view(&self) -> Option<&SourceView> {
        self.sm.get_source_view(self.get_src_id())
    }

    /// If true, this token is a range token.
    ///
    /// See <https://github.com/tc39/source-map-rfc/blob/main/proposals/range-mappings.md>
    pub fn is_range(&self) -> bool {
        self.raw.is_range
    }
}

/// Iterates over all tokens in a sourcemap
pub struct TokenIter<'a> {
    i: &'a SourceMap,
    next_idx: usize,
}

impl TokenIter<'_> {
    pub fn seek(&mut self, line: u32, col: u32) -> bool {
        let token = self.i.lookup_token(line, col);
        match token {
            Some(token) => {
                self.next_idx = token.idx + 1;
                true
            }
            None => false,
        }
    }
}

impl<'a> Iterator for TokenIter<'a> {
    type Item = Token<'a>;

    fn next(&mut self) -> Option<Token<'a>> {
        self.i.get_token(self.next_idx).inspect(|_| {
            self.next_idx += 1;
        })
    }
}

/// Iterates over all sources in a sourcemap
pub struct SourceIter<'a> {
    i: &'a SourceMap,
    next_idx: u32,
}

impl<'a> Iterator for SourceIter<'a> {
    type Item = &'a str;

    fn next(&mut self) -> Option<&'a str> {
        self.i.get_source(self.next_idx).inspect(|_| {
            self.next_idx += 1;
        })
    }
}

/// Iterates over all source contents in a sourcemap
pub struct SourceContentsIter<'a> {
    i: &'a SourceMap,
    next_idx: u32,
}

impl<'a> Iterator for SourceContentsIter<'a> {
    type Item = Option<&'a str>;

    fn next(&mut self) -> Option<Option<&'a str>> {
        if self.next_idx >= self.i.get_source_count() {
            None
        } else {
            let rv = Some(self.i.get_source_contents(self.next_idx));
            self.next_idx += 1;
            rv
        }
    }
}

/// Iterates over all tokens in a sourcemap
pub struct NameIter<'a> {
    i: &'a SourceMap,
    next_idx: u32,
}

impl<'a> Iterator for NameIter<'a> {
    type Item = &'a str;

    fn next(&mut self) -> Option<&'a str> {
        self.i.get_name(self.next_idx).inspect(|_| {
            self.next_idx += 1;
        })
    }
}

impl fmt::Debug for Token<'_> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(f, "<Token {self:#}>")
    }
}

impl fmt::Display for Token<'_> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        write!(
            f,
            "{}:{}:{}{}",
            self.get_source().unwrap_or("<unknown>"),
            self.get_src_line(),
            self.get_src_col(),
            self.get_name()
                .map(|x| format!(" name={x}"))
                .unwrap_or_default()
        )?;
        if f.alternate() {
            write!(
                f,
                " ({}:{}){}",
                self.get_dst_line(),
                self.get_dst_col(),
                if self.is_range() { " (range)" } else { "" }
            )?;
        }
        Ok(())
    }
}

/// Represents a section in a sourcemap index
#[derive(Debug, Clone)]
pub struct SourceMapSection {
    offset: (u32, u32),
    url: Option<String>,
    map: Option<Box<DecodedMap>>,
}

/// Iterates over all sections in a sourcemap index
pub struct SourceMapSectionIter<'a> {
    i: &'a SourceMapIndex,
    next_idx: u32,
}

impl<'a> Iterator for SourceMapSectionIter<'a> {
    type Item = &'a SourceMapSection;

    fn next(&mut self) -> Option<&'a SourceMapSection> {
        self.i.get_section(self.next_idx).inspect(|_| {
            self.next_idx += 1;
        })
    }
}

/// Represents a sourcemap index in memory
#[derive(Debug, Clone)]
pub struct SourceMapIndex {
    file: Option<String>,
    sections: Vec<SourceMapSection>,
    x_facebook_offsets: Option<Vec<Option<u32>>>,
    x_metro_module_paths: Option<Vec<String>>,
}

/// Represents a sourcemap in memory
///
/// This is always represents a regular "non-indexed" sourcemap.  Particularly
/// in case the `from_reader` method is used an index sourcemap will be
/// rejected with an error on reading.
#[derive(Clone, Debug)]
pub struct SourceMap {
    pub(crate) file: Option<Arc<str>>,
    pub(crate) tokens: Vec<RawToken>,
    pub(crate) names: Vec<Arc<str>>,
    pub(crate) source_root: Option<Arc<str>>,
    pub(crate) sources: Vec<Arc<str>>,
    pub(crate) sources_prefixed: Option<Vec<Arc<str>>>,
    pub(crate) sources_content: Vec<Option<SourceView>>,
    pub(crate) ignore_list: BTreeSet<u32>,
    pub(crate) debug_id: Option<DebugId>,
}

impl SourceMap {
    /// Creates a sourcemap from a reader over a JSON stream in UTF-8
    /// format.  Optionally a "garbage header" as defined by the
    /// sourcemap draft specification is supported.  In case an indexed
    /// sourcemap is encountered an error is returned.
    ///
    /// ```rust
    /// use sourcemap::SourceMap;
    /// let input: &[_] = b"{
    ///     \"version\":3,
    ///     \"sources\":[\"coolstuff.js\"],
    ///     \"names\":[\"x\",\"alert\"],
    ///     \"mappings\":\"AAAA,GAAIA,GAAI,EACR,IAAIA,GAAK,EAAG,CACVC,MAAM\"
    /// }";
    /// let sm = SourceMap::from_reader(input).unwrap();
    /// ```
    ///
    /// While sourcemaps objects permit some modifications, it's generally
    /// not possible to modify tokens after they have been added.  For
    /// creating sourcemaps from scratch or for general operations for
    /// modifying a sourcemap have a look at the `SourceMapBuilder`.
    pub fn from_reader<R: Read>(rdr: R) -> Result<SourceMap> {
        match decode(rdr)? {
            DecodedMap::Regular(sm) => Ok(sm),
            _ => Err(Error::IncompatibleSourceMap),
        }
    }

    /// Writes a sourcemap into a writer.
    ///
    /// Note that this operation will generate an equivalent sourcemap to the
    /// one that was generated on load however there might be small differences
    /// in the generated JSON and layout. For instance `sourceRoot` will not
    /// be set as upon parsing of the sourcemap the sources will already be
    /// expanded.
    ///
    /// ```rust
    /// # use sourcemap::SourceMap;
    /// # let input: &[_] = b"{
    /// #     \"version\":3,
    /// #     \"sources\":[\"coolstuff.js\"],
    /// #     \"names\":[\"x\",\"alert\"],
    /// #     \"mappings\":\"AAAA,GAAIA,GAAI,EACR,IAAIA,GAAK,EAAG,CACVC,MAAM\"
    /// # }";
    /// let sm = SourceMap::from_reader(input).unwrap();
    /// let mut output : Vec<u8> = vec![];
    /// sm.to_writer(&mut output).unwrap();
    /// ```
    pub fn to_writer<W: Write>(&self, w: W) -> Result<()> {
        encode(self, w)
    }

    /// Encode a sourcemap into a data url.
    ///
    /// ```rust
    /// # use sourcemap::SourceMap;
    /// # let input: &[_] = b"{
    /// #     \"version\":3,
    /// #     \"sources\":[\"coolstuff.js\"],
    /// #     \"names\":[\"x\",\"alert\"],
    /// #     \"mappings\":\"AAAA,GAAIA,GAAI,EACR,IAAIA,GAAK,EAAG,CACVC,MAAM\"
    /// # }";
    /// let sm = SourceMap::from_reader(input).unwrap();
    /// sm.to_data_url().unwrap();
    /// ```
    pub fn to_data_url(&self) -> Result<String> {
        let mut buf = vec![];
        encode(self, &mut buf)?;
        let b64 = base64_simd::Base64::STANDARD.encode_to_boxed_str(&buf);
        Ok(format!(
            "data:application/json;charset=utf-8;base64,{}",
            b64
        ))
    }

    /// Creates a sourcemap from a reader over a JSON byte slice in UTF-8
    /// format.  Optionally a "garbage header" as defined by the
    /// sourcemap draft specification is supported.  In case an indexed
    /// sourcemap is encountered an error is returned.
    ///
    /// ```rust
    /// use sourcemap::SourceMap;
    /// let input: &[_] = b"{
    ///     \"version\":3,
    ///     \"sources\":[\"coolstuff.js\"],
    ///     \"names\":[\"x\",\"alert\"],
    ///     \"mappings\":\"AAAA,GAAIA,GAAI,EACR,IAAIA,GAAK,EAAG,CACVC,MAAM\"
    /// }";
    /// let sm = SourceMap::from_slice(input).unwrap();
    /// ```
    pub fn from_slice(slice: &[u8]) -> Result<SourceMap> {
        match decode_slice(slice)? {
            DecodedMap::Regular(sm) => Ok(sm),
            _ => Err(Error::IncompatibleSourceMap),
        }
    }

    /// Constructs a new sourcemap from raw components.
    ///
    /// - `file`: an optional filename of the sourcemap
    /// - `tokens`: a list of raw tokens
    /// - `names`: a vector of names
    /// - `sources` a vector of source filenames
    /// - `sources_content` optional source contents
    /// - `ignore_list` optional list of source indexes for devtools to ignore
    pub fn new(
        file: Option<Arc<str>>,
        mut tokens: Vec<RawToken>,
        names: Vec<Arc<str>>,
        sources: Vec<Arc<str>>,
        sources_content: Option<Vec<Option<Arc<str>>>>,
    ) -> SourceMap {
        tokens.sort_unstable_by_key(|t| (t.dst_line, t.dst_col));
        SourceMap {
            file,
            tokens,
            names,
            source_root: None,
            sources,
            sources_prefixed: None,
            sources_content: sources_content
                .unwrap_or_default()
                .into_iter()
                .map(|opt| opt.map(SourceView::new))
                .collect(),
            ignore_list: BTreeSet::default(),
            debug_id: None,
        }
    }

    /// Returns the embedded debug id.
    pub fn get_debug_id(&self) -> Option<DebugId> {
        self.debug_id
    }

    /// Sets a new value for the debug id.
    pub fn set_debug_id(&mut self, debug_id: Option<DebugId>) {
        self.debug_id = debug_id
    }

    /// Returns the embedded filename in case there is one.
    pub fn get_file(&self) -> Option<&str> {
        self.file.as_deref()
    }

    /// Sets a new value for the file.
    pub fn set_file<T: Into<Arc<str>>>(&mut self, value: Option<T>) {
        self.file = value.map(Into::into);
    }

    /// Returns the embedded source_root in case there is one.
    pub fn get_source_root(&self) -> Option<&str> {
        self.source_root.as_deref()
    }

    fn prefix_source(source_root: &str, source: &str) -> Arc<str> {
        let source_root = source_root.strip_suffix('/').unwrap_or(source_root);
        let is_valid = !source.is_empty()
            && (source.starts_with('/')
                || source.starts_with("http:")
                || source.starts_with("https:"));

        if is_valid {
            source.into()
        } else {
            format!("{source_root}/{source}").into()
        }
    }

    /// Sets a new value for the source_root.
    pub fn set_source_root<T: Into<Arc<str>>>(&mut self, value: Option<T>) {
        self.source_root = value.map(Into::into);

        match self.source_root.as_deref().filter(|rs| !rs.is_empty()) {
            Some(source_root) => {
                let sources_prefixed = self
                    .sources
                    .iter()
                    .map(|source| Self::prefix_source(source_root, source))
                    .collect();
                self.sources_prefixed = Some(sources_prefixed)
            }
            None => self.sources_prefixed = None,
        }
    }

    pub fn add_to_ignore_list(&mut self, src_id: u32) {
        self.ignore_list.insert(src_id);
    }

    pub fn ignore_list(&self) -> impl Iterator<Item = &u32> {
        self.ignore_list.iter()
    }

    /// Looks up a token by its index.
    pub fn get_token(&self, idx: usize) -> Option<Token<'_>> {
        self.tokens.get(idx).map(|raw| Token {
            raw,
            sm: self,
            idx,
            offset: 0,
        })
    }

    /// Returns the number of tokens in the sourcemap.
    pub fn get_token_count(&self) -> u32 {
        self.tokens.len() as u32
    }

    /// Returns an iterator over the tokens.
    pub fn tokens(&self) -> TokenIter<'_> {
        TokenIter {
            i: self,
            next_idx: 0,
        }
    }

    /// Looks up the closest token to a given 0-indexed line and column.
    pub fn lookup_token(&self, line: u32, col: u32) -> Option<Token<'_>> {
        let (idx, raw) =
            greatest_lower_bound(&self.tokens, &(line, col), |t| (t.dst_line, t.dst_col))?;

        let mut token = Token {
            raw,
            sm: self,
            idx,
            offset: 0,
        };

        if token.is_range() {
            token.offset = col - token.get_dst_col();
        }

        Some(token)
    }

    /// Given a location, name and minified source file resolve a minified
    /// name to an original function name.
    ///
    /// This invokes some guesswork and requires access to the original minified
    /// source.  This will not yield proper results for anonymous functions or
    /// functions that do not have clear function names.  (For instance it's
    /// recommended that dotted function names are not passed to this
    /// function).
    pub fn get_original_function_name(
        &self,
        line: u32,
        col: u32,
        minified_name: &str,
        sv: &SourceView,
    ) -> Option<&str> {
        self.lookup_token(line, col)
            .and_then(|token| sv.get_original_function_name(token, minified_name))
    }

    /// Returns the number of sources in the sourcemap.
    pub fn get_source_count(&self) -> u32 {
        self.sources.len() as u32
    }

    /// Looks up a source for a specific index.
    pub fn get_source(&self, idx: u32) -> Option<&str> {
        let sources = self.sources_prefixed.as_deref().unwrap_or(&self.sources);
        sources.get(idx as usize).map(|x| &x[..])
    }

    /// Sets a new source value for an index.  This cannot add new
    /// sources.
    ///
    /// This panics if a source is set that does not exist.
    pub fn set_source(&mut self, idx: u32, value: &str) {
        self.sources[idx as usize] = value.into();

        if let Some(sources_prefixed) = self.sources_prefixed.as_mut() {
            // If sources_prefixed is `Some`, we must have a nonempty `source_root`.
            sources_prefixed[idx as usize] =
                Self::prefix_source(self.source_root.as_deref().unwrap(), value);
        }
    }

    /// Iterates over all sources
    pub fn sources(&self) -> SourceIter<'_> {
        SourceIter {
            i: self,
            next_idx: 0,
        }
    }

    /// Returns the sources content as source view.
    pub fn get_source_view(&self, idx: u32) -> Option<&SourceView> {
        self.sources_content
            .get(idx as usize)
            .and_then(Option::as_ref)
    }

    /// Looks up the content for a source.
    pub fn get_source_contents(&self, idx: u32) -> Option<&str> {
        self.sources_content
            .get(idx as usize)
            .and_then(Option::as_ref)
            .map(SourceView::source)
    }

    /// Sets source contents for a source.
    pub fn set_source_contents(&mut self, idx: u32, value: Option<&str>) {
        if self.sources_content.len() != self.sources.len() {
            self.sources_content.resize(self.sources.len(), None);
        }
        self.sources_content[idx as usize] = value.map(|x| SourceView::from_string(x.to_string()));
    }

    /// Iterates over all source contents
    pub fn source_contents(&self) -> SourceContentsIter<'_> {
        SourceContentsIter {
            i: self,
            next_idx: 0,
        }
    }

    /// Returns an iterator over the names.
    pub fn names(&self) -> NameIter<'_> {
        NameIter {
            i: self,
            next_idx: 0,
        }
    }

    /// Returns the number of names in the sourcemap.
    pub fn get_name_count(&self) -> u32 {
        self.names.len() as u32
    }

    /// Returns true if there are any names in the map.
    pub fn has_names(&self) -> bool {
        !self.names.is_empty()
    }

    /// Looks up a name for a specific index.
    pub fn get_name(&self, idx: u32) -> Option<&str> {
        self.names.get(idx as usize).map(|x| &x[..])
    }

    /// Removes all names from the sourcemap.
    pub fn remove_names(&mut self) {
        self.names.clear();
    }

    /// This rewrites the sourcemap according to the provided rewrite
    /// options.
    ///
    /// The default behavior is to just deduplicate the sourcemap, something
    /// that automatically takes place.  This for instance can be used to
    /// slightly compress sourcemaps if certain data is not wanted.
    ///
    /// ```rust
    /// use sourcemap::{SourceMap, RewriteOptions};
    /// # let input: &[_] = b"{
    /// #     \"version\":3,
    /// #     \"sources\":[\"coolstuff.js\"],
    /// #     \"names\":[\"x\",\"alert\"],
    /// #     \"mappings\":\"AAAA,GAAIA,GAAI,EACR,IAAIA,GAAK,EAAG,CACVC,MAAM\"
    /// # }";
    /// let sm = SourceMap::from_slice(input).unwrap();
    /// let new_sm = sm.rewrite(&RewriteOptions {
    ///     with_names: false,
    ///     ..Default::default()
    /// });
    /// ```
    pub fn rewrite(self, options: &RewriteOptions<'_>) -> Result<SourceMap> {
        Ok(self.rewrite_with_mapping(options)?.0)
    }

    /// Same as `rewrite`, except also returns a remapping index for deduplicated `sources`.
    pub(crate) fn rewrite_with_mapping(
        self,
        options: &RewriteOptions<'_>,
    ) -> Result<(SourceMap, Vec<u32>)> {
        let mut builder = SourceMapBuilder::new(self.get_file());
        builder.set_debug_id(self.debug_id);

        for token in self.tokens() {
            let raw = builder.add_token(&token, options.with_names);
            if raw.src_id != !0
                && options.with_source_contents
                && !builder.has_source_contents(raw.src_id)
            {
                builder
                    .set_source_contents(raw.src_id, self.get_source_contents(token.get_src_id()));
            }
        }

        #[cfg(any(unix, windows, target_os = "redox"))]
        {
            if options.load_local_source_contents {
                builder.load_local_source_contents(options.base_path)?;
            }
        }

        let mut prefixes = vec![];
        let mut need_common_prefix = false;
        for &prefix in options.strip_prefixes.iter() {
            if prefix == "~" {
                need_common_prefix = true;
            } else {
                prefixes.push(prefix.to_string());
            }
        }
        if need_common_prefix {
            if let Some(prefix) = find_common_prefix(self.sources.iter().map(AsRef::as_ref)) {
                prefixes.push(prefix);
            }
        }
        if !prefixes.is_empty() {
            builder.strip_prefixes(&prefixes);
        }

        let mapping = builder.take_mapping();

        let sm = builder.into_sourcemap();

        Ok((sm, mapping))
    }

    /// Adjusts the mappings in `self` using the mappings in `adjustment`.
    ///
    /// Here is the intended use case for this function:
    /// * You have a source file (for example, minified JS) `foo.js` and a
    ///   corresponding sourcemap `foo.js.map`.
    /// * You modify `foo.js` in some way and generate a sourcemap `transform.js.map`
    ///   representing this modification. This can be done using `magic-string`, for example.
    /// * You want a sourcemap that is "like" `foo.js.map`, but takes the changes you made to `foo.js` into account.
    ///
    /// Then `foo.js.map.adjust_mappings(transform.js.map)` is the desired sourcemap.
    ///
    /// This function assumes that `adjustment` contains no relevant information except for mappings.
    ///  All information about sources and names is copied from `self`.
    ///
    /// Note that the resulting sourcemap will be at most as fine-grained as `self.`.
    pub fn adjust_mappings(&mut self, adjustment: &Self) {
        // The algorithm works by going through the tokens in `self` in order and adjusting
        // them depending on the token in `adjustment` they're "covered" by.
        // For example:
        // Let `l` be a token in `adjustment` mapping `(17, 23)` to `(8, 30)` and let
        // `r₁ : (8, 28) -> (102, 35)`, `r₂ : (8, 40) -> (102, 50)`, and
        // `r₃ : (9, 10) -> (103, 12)` be the tokens in `self` that fall in the range of `l`.
        // `l` offsets these tokens by `(+9, -7)`, so `r₁, … , r₃` must be offset by the same
        // amount. Thus, the adjusted sourcemap will contain the tokens
        // `c₁ : (17, 23) -> (102, 35)`, `c₂ : (17, 33) -> (102, 50)`, and
        // `c3 : (18, 3) -> (103, 12)`.
        //
        // Or, in diagram form:
        //
        //    (17, 23)                                    (position in the edited source file)
        //    ↓ l
        //    (8, 30)
        // (8, 28)        (8, 40)        (9, 10)          (positions in the original source file)
        // ↓ r₁           ↓ r₂           ↓ r₃
        // (102, 35)      (102, 50)      (103, 12)        (positions in the target file)
        //
        // becomes
        //
        //    (17, 23)       (17, 33)       (18, 3)       (positions in the edited source file)
        //    ↓ c₁           ↓ c₂           ↓ c₃
        //    (102, 35)      (102, 50)      (103, 12)     (positions in the target file)

        // Helper struct that makes it easier to compare tokens by the start and end
        // of the range they cover.
        #[derive(Debug, Clone, Copy)]
        struct Range {
            start: (u32, u32),
            end: (u32, u32),
            value: RawToken,
        }

        /// Turns a list of tokens into a list of ranges, using the provided `key` function to determine the order of the tokens.
        fn create_ranges(
            mut tokens: Vec<RawToken>,
            key: fn(&RawToken) -> (u32, u32),
        ) -> Vec<Range> {
            tokens.sort_unstable_by_key(key);

            let mut token_iter = tokens.into_iter().peekable();
            let mut ranges = Vec::new();

            while let Some(t) = token_iter.next() {
                let start = key(&t);
                let next_start = token_iter.peek().map_or((u32::MAX, u32::MAX), key);
                // A token extends either to the start of the next token or the end of the line, whichever comes sooner
                let end = std::cmp::min(next_start, (start.0, u32::MAX));
                ranges.push(Range {
                    start,
                    end,
                    value: t,
                });
            }

            ranges
        }

        // Turn `self.tokens` and `adjustment.tokens` into vectors of ranges so we have easy access to
        // both start and end.
        // We want to compare `self` and `adjustment` tokens by line/column numbers in the "original source" file.
        // These line/column numbers are the `dst_line/col` for
        // the `self` tokens and `src_line/col` for the `adjustment` tokens.
        let self_tokens = std::mem::take(&mut self.tokens);
        let original_ranges = create_ranges(self_tokens, |t| (t.dst_line, t.dst_col));
        let adjustment_ranges =
            create_ranges(adjustment.tokens.clone(), |t| (t.src_line, t.src_col));

        let mut original_ranges_iter = original_ranges.iter();

        let mut original_range = match original_ranges_iter.next() {
            Some(r) => r,
            None => return,
        };

        // Iterate over `adjustment_ranges` (sorted by `src_line/col`). For each such range, consider
        // all `original_ranges` which overlap with it.
        'outer: for &adjustment_range in &adjustment_ranges {
            // The `adjustment_range` offsets lines and columns by a certain amount. All `original_ranges`
            // it covers will get the same offset.
            let (line_diff, col_diff) = (
                adjustment_range.value.dst_line as i32 - adjustment_range.value.src_line as i32,
                adjustment_range.value.dst_col as i32 - adjustment_range.value.src_col as i32,
            );

            // Skip `original_ranges` that are entirely before the `adjustment_range`.
            while original_range.end <= adjustment_range.start {
                match original_ranges_iter.next() {
                    Some(r) => original_range = r,
                    None => break 'outer,
                }
            }

            // At this point `original_range.end` > `adjustment_range.start`

            // Iterate over `original_ranges` that fall at least partially within the `adjustment_range`.
            while original_range.start < adjustment_range.end {
                // If `original_range` started before `adjustment_range`, cut off the token's start.
                let (dst_line, dst_col) =
                    std::cmp::max(original_range.start, adjustment_range.start);
                let mut token = RawToken {
                    dst_line,
                    dst_col,
                    ..original_range.value
                };

                token.dst_line = (token.dst_line as i32 + line_diff) as u32;
                token.dst_col = (token.dst_col as i32 + col_diff) as u32;

                self.tokens.push(token);

                if original_range.end >= adjustment_range.end {
                    // There are surely no more `original_ranges` for this `adjustment_range`.
                    // Break the loop without advancing the `original_range`.
                    break;
                } else {
                    //  Advance the `original_range`.
                    match original_ranges_iter.next() {
                        Some(r) => original_range = r,
                        None => break 'outer,
                    }
                }
            }
        }

        self.tokens
            .sort_unstable_by_key(|t| (t.dst_line, t.dst_col));
    }
}

impl SourceMapIndex {
    /// Creates a sourcemap index from a reader over a JSON stream in UTF-8
    /// format.  Optionally a "garbage header" as defined by the
    /// sourcemap draft specification is supported.  In case a regular
    /// sourcemap is encountered an error is returned.
    pub fn from_reader<R: Read>(rdr: R) -> Result<SourceMapIndex> {
        match decode(rdr)? {
            DecodedMap::Index(smi) => Ok(smi),
            _ => Err(Error::IncompatibleSourceMap),
        }
    }

    /// Writes a sourcemap index into a writer.
    pub fn to_writer<W: Write>(&self, w: W) -> Result<()> {
        encode(self, w)
    }

    /// Creates a sourcemap index from a reader over a JSON byte slice in UTF-8
    /// format.  Optionally a "garbage header" as defined by the
    /// sourcemap draft specification is supported.  In case a regular
    /// sourcemap is encountered an error is returned.
    pub fn from_slice(slice: &[u8]) -> Result<SourceMapIndex> {
        match decode_slice(slice)? {
            DecodedMap::Index(smi) => Ok(smi),
            _ => Err(Error::IncompatibleSourceMap),
        }
    }

    /// Constructs a new sourcemap index from raw components.
    ///
    /// - `file`: an optional filename of the index
    /// - `sections`: a vector of source map index sections
    pub fn new(file: Option<String>, sections: Vec<SourceMapSection>) -> SourceMapIndex {
        SourceMapIndex {
            file,
            sections,
            x_facebook_offsets: None,
            x_metro_module_paths: None,
        }
    }

    /// Constructs a new sourcemap index from raw components including the
    /// facebook RAM bundle extensions.
    ///
    /// - `file`: an optional filename of the index
    /// - `sections`: a vector of source map index sections
    /// - `x_facebook_offsets`: a vector of facebook offsets
    /// - `x_metro_module_paths`: a vector of metro module paths
    pub fn new_ram_bundle_compatible(
        file: Option<String>,
        sections: Vec<SourceMapSection>,
        x_facebook_offsets: Option<Vec<Option<u32>>>,
        x_metro_module_paths: Option<Vec<String>>,
    ) -> SourceMapIndex {
        SourceMapIndex {
            file,
            sections,
            x_facebook_offsets,
            x_metro_module_paths,
        }
    }

    /// Returns the embedded filename in case there is one.
    pub fn get_file(&self) -> Option<&str> {
        self.file.as_ref().map(|x| &x[..])
    }

    /// Sets a new value for the file.
    pub fn set_file(&mut self, value: Option<&str>) {
        self.file = value.map(str::to_owned);
    }

    /// Returns the number of sections in this index
    pub fn get_section_count(&self) -> u32 {
        self.sections.len() as u32
    }

    /// Looks up a single section and returns it
    pub fn get_section(&self, idx: u32) -> Option<&SourceMapSection> {
        self.sections.get(idx as usize)
    }

    /// Looks up a single section and returns it as a mutable ref
    pub fn get_section_mut(&mut self, idx: u32) -> Option<&mut SourceMapSection> {
        self.sections.get_mut(idx as usize)
    }

    /// Iterates over all sections
    pub fn sections(&self) -> SourceMapSectionIter<'_> {
        SourceMapSectionIter {
            i: self,
            next_idx: 0,
        }
    }

    /// Given a location, name and minified source file resolve a minified
    /// name to an original function name.
    ///
    /// This invokes some guesswork and requires access to the original minified
    /// source.  This will not yield proper results for anonymous functions or
    /// functions that do not have clear function names.  (For instance it's
    /// recommended that dotted function names are not passed to this
    /// function).
    pub fn get_original_function_name(
        &self,
        line: u32,
        col: u32,
        minified_name: &str,
        sv: &SourceView,
    ) -> Option<&str> {
        self.lookup_token(line, col)
            .and_then(|token| sv.get_original_function_name(token, minified_name))
    }

    /// Looks up the closest token to a given line and column.
    ///
    /// This requires that the referenced sourcemaps are actually loaded.
    /// If a sourcemap is encountered that is not embedded but just
    /// externally referenced it is silently skipped.
    pub fn lookup_token(&self, line: u32, col: u32) -> Option<Token<'_>> {
        let (_section_idx, section) =
            greatest_lower_bound(&self.sections, &(line, col), SourceMapSection::get_offset)?;
        let map = section.get_sourcemap()?;
        let (off_line, off_col) = section.get_offset();
        map.lookup_token(
            line - off_line,
            if line == off_line { col - off_col } else { col },
        )
    }

    /// Flattens an indexed sourcemap into a regular one.  This requires
    /// that all referenced sourcemaps are attached.
    pub fn flatten(&self) -> Result<SourceMap> {
        let mut builder = SourceMapBuilder::new(self.get_file());

        for section in self.sections() {
            let (off_line, off_col) = section.get_offset();
            let map = match section.get_sourcemap() {
                Some(map) => match map {
                    DecodedMap::Regular(sm) => Cow::Borrowed(sm),
                    DecodedMap::Index(idx) => Cow::Owned(idx.flatten()?),
                    DecodedMap::Hermes(smh) => Cow::Borrowed(&smh.sm),
                },
                None => {
                    return Err(Error::CannotFlatten(format!(
                        "Section has an unresolved \
                         sourcemap: {}",
                        section.get_url().unwrap_or("<unknown url>")
                    )));
                }
            };

            for token in map.tokens() {
                let dst_col = if token.get_dst_line() == 0 {
                    token.get_dst_col() + off_col
                } else {
                    token.get_dst_col()
                };
                let raw = builder.add(
                    token.get_dst_line() + off_line,
                    dst_col,
                    token.get_src_line(),
                    token.get_src_col(),
                    token.get_source(),
                    token.get_name(),
                    token.is_range(),
                );
                if token.get_source().is_some() && !builder.has_source_contents(raw.src_id) {
                    builder.set_source_contents(
                        raw.src_id,
                        map.get_source_contents(token.get_src_id()),
                    );
                }
                if map.ignore_list.contains(&token.get_src_id()) {
                    builder.add_to_ignore_list(raw.src_id);
                }
            }
        }

        Ok(builder.into_sourcemap())
    }

    /// Flattens an indexed sourcemap into a regular one and automatically
    /// rewrites it.  This is more useful than plain flattening as this will
    /// cause the sourcemap to be properly deduplicated.
    pub fn flatten_and_rewrite(self, options: &RewriteOptions<'_>) -> Result<SourceMap> {
        self.flatten()?.rewrite(options)
    }

    /// Returns `true` if this sourcemap is for a RAM bundle.
    pub fn is_for_ram_bundle(&self) -> bool {
        self.x_facebook_offsets.is_some() && self.x_metro_module_paths.is_some()
    }

    /// Returns embeded x-facebook-offset values.
    pub fn x_facebook_offsets(&self) -> Option<&[Option<u32>]> {
        self.x_facebook_offsets.as_ref().map(|x| &x[..])
    }

    /// Returns embedded metro module paths.
    pub fn x_metro_module_paths(&self) -> Option<&[String]> {
        self.x_metro_module_paths.as_ref().map(|x| &x[..])
    }
}

impl SourceMapSection {
    /// Create a new sourcemap index section
    ///
    /// - `offset`: offset as line and column
    /// - `url`: optional URL of where the sourcemap is located
    /// - `map`: an optional already resolved internal sourcemap
    pub fn new(
        offset: (u32, u32),
        url: Option<String>,
        map: Option<DecodedMap>,
    ) -> SourceMapSection {
        SourceMapSection {
            offset,
            url,
            map: map.map(Box::new),
        }
    }

    /// Returns the offset line
    pub fn get_offset_line(&self) -> u32 {
        self.offset.0
    }

    /// Returns the offset column
    pub fn get_offset_col(&self) -> u32 {
        self.offset.1
    }

    /// Returns the offset as tuple
    pub fn get_offset(&self) -> (u32, u32) {
        self.offset
    }

    /// Returns the URL of the referenced map if available
    pub fn get_url(&self) -> Option<&str> {
        self.url.as_deref()
    }

    /// Updates the URL for this section.
    pub fn set_url(&mut self, value: Option<&str>) {
        self.url = value.map(str::to_owned);
    }

    /// Returns a reference to the embedded sourcemap if available
    pub fn get_sourcemap(&self) -> Option<&DecodedMap> {
        self.map.as_ref().map(Box::as_ref)
    }

    /// Returns a reference to the embedded sourcemap if available
    pub fn get_sourcemap_mut(&mut self) -> Option<&mut DecodedMap> {
        self.map.as_mut().map(Box::as_mut)
    }

    /// Replaces the embedded sourcemap
    pub fn set_sourcemap(&mut self, sm: Option<DecodedMap>) {
        self.map = sm.map(Box::new);
    }
}

#[cfg(test)]
mod tests {
    use super::{RewriteOptions, SourceMap};
    use debugid::DebugId;

    #[test]
    fn test_rewrite_debugid() {
        let input: &[_] = br#"{
         "version":3,
         "sources":["coolstuff.js"],
         "names":["x","alert"],
         "mappings":"AAAA,GAAIA,GAAI,EACR,IAAIA,GAAK,EAAG,CACVC,MAAM",
         "debug_id":"00000000-0000-0000-0000-000000000000"
     }"#;

        let sm = SourceMap::from_slice(input).unwrap();

        assert_eq!(sm.debug_id, Some(DebugId::default()));

        let new_sm = sm
            .rewrite(&RewriteOptions {
                with_names: false,
                ..Default::default()
            })
            .unwrap();

        assert_eq!(new_sm.debug_id, Some(DebugId::default()));
    }

    #[test]
    fn test_debugid_alias() {
        let input: &[_] = br#"{
         "version":3,
         "sources":["coolstuff.js"],
         "names":["x","alert"],
         "mappings":"AAAA,GAAIA,GAAI,EACR,IAAIA,GAAK,EAAG,CACVC,MAAM",
         "debug_id":"00000000-0000-0000-0000-000000000000",
         "debugId": "11111111-1111-1111-1111-111111111111"
     }"#;

        let sm = SourceMap::from_slice(input).unwrap();

        assert_eq!(sm.debug_id, Some(DebugId::default()));
    }

    #[test]
    fn test_adjust_mappings_injection() {
        // A test that `adjust_mappings` does what it's supposed to for debug id injection.
        //
        // For each bundler:
        // * `bundle.js` and `bundle.js.map` are taken from https://github.com/kamilogorek/sourcemaps-playground/.
        // * `injected.bundle.js` and `injected.bundle.js.map` were created using the function`fixup_js_file` in `sentry-cli`.
        //   `injected.bundle.js.map` maps from `injected.bundle.js` to `bundle.js`.
        // * `composed.bundle.js.map` is the result of calling `adjust_mappings` on `bundle.js.map` and `injected.bundle.js.map`.
        //
        // If everything is working as intended, `composed.bundle.js.map` is a (good) sourcemap from `injected.bundle.js` to
        // the original sources. To verify that this is indeed the case, you can compare `bundle.js` / `bundle.js.map` with
        // `injected.bundle.js` / `composed.bundle.js.map` using https://sokra.github.io/source-map-visualization/#custom.
        //
        // NB: In the case of `rspack`, the sourcemap generated by the bundler is *horrible*. It's probably not useful, but
        // `adjust_mappings` preserves it as far as it goes.
        for bundler in ["esbuild", "rollup", "vite", "webpack", "rspack"] {
            let original_map_file = std::fs::File::open(format!(
                "tests/fixtures/adjust_mappings/{bundler}.bundle.js.map"
            ))
            .unwrap();

            let injected_map_file = std::fs::File::open(format!(
                "tests/fixtures/adjust_mappings/{bundler}-injected.bundle.js.map"
            ))
            .unwrap();

            let composed_map_file = std::fs::File::open(format!(
                "tests/fixtures/adjust_mappings/{bundler}-composed.bundle.js.map"
            ))
            .unwrap();

            let mut original_map = SourceMap::from_reader(original_map_file).unwrap();
            let injected_map = SourceMap::from_reader(injected_map_file).unwrap();
            let composed_map = SourceMap::from_reader(composed_map_file).unwrap();
            original_map.adjust_mappings(&injected_map);

            assert_eq!(
                original_map.tokens, composed_map.tokens,
                "bundler = {bundler}"
            );
        }
    }

    #[test]
    fn test_roundtrip() {
        let sm = br#"{
            "version": 3,
            "file": "foo.js",
            "sources": [
                "./bar.js",
                "./baz.js"
            ],
            "sourceRoot": "webpack:///",
            "sourcesContent": [null, null],
            "names": [],
            "mappings": ""
        }"#;

        let sm = SourceMap::from_slice(sm).unwrap();
        let mut out = Vec::new();
        sm.to_writer(&mut out).unwrap();

        let sm_new = SourceMap::from_slice(&out).unwrap();
        assert_eq!(sm_new.sources, sm.sources);
    }

    mod prop {
        //! This module exists to test the following property:
        //!
        //! Let `s` be a string.
        //! 1. Edit `s` with `magic-string` in such a way that edits (insertions, deletions) only happen *within* lines.
        //!    Call the resulting string `t` and the sourcemap relating the two `m₁`.
        //! 2. Further edit `t` with `magic-string` so that only *whole* lines are edited (inserted, deleted, prepended, appended).
        //!    Call the resulting string `u` and the sourcemap relating `u` to `t` `m₂`.
        //! 3. Do (1) and (2) in one go. The resulting string should still be `u`. Call the sourcemap
        //!    relating `u` and `s` `m₃`.
        //!
        //! Then `SourceMap::adjust_mappings(m₁, m₂) = m₃`.
        //!
        //! Or, in diagram form:
        //!
        //! u  -----m₂--------> t  -----m₁--------> s
        //! | -----------------m₃-----------------> |
        //!
        //! For the sake of simplicty, all input strings are 10 lines by 10 columns of the characters a-z.
        use magic_string::MagicString;
        use proptest::prelude::*;

        use crate::SourceMap;

        /// An edit in the first batch (only within a line).
        #[derive(Debug, Clone)]
        enum FirstEdit {
            /// Insert a string at a column.
            Insert(u32, String),
            /// Delete from one column to the other.
            Delete(i64, i64),
        }

        impl FirstEdit {
            /// Applies an edit to the given line in the given `MagicString`.
            fn apply(&self, line: usize, ms: &mut MagicString) {
                // Every line is 11 bytes long, counting the newline.
                let line_offset = line * 11;
                match self {
                    FirstEdit::Insert(col, s) => {
                        ms.append_left(line_offset as u32 + *col, s).unwrap();
                    }
                    FirstEdit::Delete(start, end) => {
                        ms.remove(line_offset as i64 + *start, line_offset as i64 + *end)
                            .unwrap();
                    }
                }
            }
        }

        /// Find the start and end index of the n'th line in the given string
        /// (including the terminating newline, if there is one).
        fn nth_line_start_end(n: usize, s: &str) -> (usize, usize) {
            let line = s.lines().nth(n).unwrap();
            let start = line.as_ptr() as usize - s.as_ptr() as usize;
            // All lines except line 9 have a final newline.
            let end = if n == 9 {
                start + line.len()
            } else {
                start + line.len() + 1
            };
            (start, end)
        }

        /// An edit in the second batch (only whole lines).
        #[derive(Debug, Clone)]
        enum SecondEdit {
            /// Prepends a string.
            Prepend(String),
            /// Appends a string.
            Append(String),
            /// Inserts a string at a given line.
            Insert(usize, String),
            /// Deletes a a line.
            Delete(usize),
        }

        impl SecondEdit {
            /// Applies an edit to a `MagicString`.
            ///
            /// This must know the original string (which unfortunately can't be extracted from a `MagicString`)
            /// to find line boundaries.
            fn apply(&self, orig: &str, ms: &mut MagicString) {
                match self {
                    SecondEdit::Prepend(s) => {
                        ms.prepend(s).unwrap();
                    }
                    SecondEdit::Append(s) => {
                        ms.append(s).unwrap();
                    }
                    SecondEdit::Insert(line, s) => {
                        let (start, _) = nth_line_start_end(*line, orig);
                        ms.prepend_left(start as u32, s).unwrap();
                    }
                    SecondEdit::Delete(line) => {
                        let (start, end) = nth_line_start_end(*line, orig);
                        ms.remove(start as i64, end as i64).unwrap();
                    }
                }
            }
        }

        /// Produces a random 10x10 grid of the characters a-z.
        fn starting_string() -> impl Strategy<Value = String> {
            (vec!["[a-z]{10}"; 10]).prop_map(|v| v.join("\n"))
        }

        /// Produces a random first-batch edit.
        fn first_edit() -> impl Strategy<Value = FirstEdit> {
            prop_oneof![
                (1u32..9, "[a-z]{5}").prop_map(|(c, s)| FirstEdit::Insert(c, s)),
                (1i64..10)
                    .prop_flat_map(|end| (0..end, Just(end)))
                    .prop_map(|(a, b)| FirstEdit::Delete(a, b))
            ]
        }

        /// Produces a random sequence of first-batch edits, one per line.
        ///
        /// Thus, each line will either have an insertion or a deletion.
        fn first_edit_sequence() -> impl Strategy<Value = Vec<FirstEdit>> {
            let mut vec = Vec::with_capacity(10);

            for _ in 0..10 {
                vec.push(first_edit())
            }

            vec
        }

        /// Produces a random sequence of second-batch edits, one per line.
        ///
        /// Each edit may delete a line, insert a line, or prepend or append something
        /// to the whole string. No two edits operate on the same line. The order of the edits is random.
        fn second_edit_sequence() -> impl Strategy<Value = Vec<SecondEdit>> {
            let edits = (0..10)
                .map(|i| {
                    prop_oneof![
                        "[a-z\n]{12}".prop_map(SecondEdit::Prepend),
                        "[a-z\n]{12}".prop_map(SecondEdit::Append),
                        "[a-z\n]{11}\n".prop_map(move |s| SecondEdit::Insert(i, s)),
                        Just(SecondEdit::Delete(i)),
                    ]
                })
                .collect::<Vec<_>>();

            edits.prop_shuffle()
        }

        proptest! {
            #[test]
            fn test_composition_identity(
                input in starting_string(),
                first_edits in first_edit_sequence(),
                second_edits in second_edit_sequence(),
            ) {

                // Do edits in two batches and generate two sourcemaps

                let mut ms1 = MagicString::new(&input);

                for (line, first_edit) in first_edits.iter().enumerate() {
                    first_edit.apply(line, &mut ms1);
                }

                let first_map = ms1.generate_map(Default::default()).unwrap().to_string().unwrap();
                let mut first_map = SourceMap::from_slice(first_map.as_bytes()).unwrap();

                let transformed_input = ms1.to_string();

                let mut ms2 = MagicString::new(&transformed_input);

                for second_edit in second_edits.iter() {
                    second_edit.apply(&transformed_input, &mut ms2);
                }

                let output_1 = ms2.to_string();

                let second_map = ms2.generate_map(Default::default()).unwrap().to_string().unwrap();
                let second_map = SourceMap::from_slice(second_map.as_bytes()).unwrap();

                // Do edits again in one batch and generate one big sourcemap

                let mut ms3 = MagicString::new(&input);

                for (line, first_edit) in first_edits.iter().enumerate() {
                    first_edit.apply(line, &mut ms3);
                }

                for second_edit in second_edits.iter() {
                    second_edit.apply(&input, &mut ms3);
                }

                let output_2 = ms3.to_string();

                let third_map = ms3.generate_map(Default::default()).unwrap().to_string().unwrap();
                let third_map = SourceMap::from_slice(third_map.as_bytes()).unwrap();

                // Both methods must produce the same output
                assert_eq!(output_1, output_2);

                first_map.adjust_mappings(&second_map);

                assert_eq!(first_map.tokens, third_map.tokens);
            }
        }
    }
}