rolldown_sourcemap 1.2.18

mod source;
mod source_joiner;

use std::borrow::Cow;

use oxc_sourcemap::{SourceMapParts, Token};

pub use oxc_sourcemap::{JSONSourceMap, OwnedSourceMap, SourceMapBuilder, SourcemapVisualizer};
pub use source_joiner::SourceJoiner;

/// Rolldown always stores and produces owned sourcemaps, so we alias the
/// lifetime-parameterized `oxc_sourcemap::SourceMap` to its `'static` form.
pub type SourceMap = oxc_sourcemap::SourceMap<'static>;

pub use crate::source::{Source, SourceMapSource};

/// Strips the first `lines` destination lines from the sourcemap, decrementing all remaining
/// destination line numbers accordingly. Used to re-anchor a sourcemap after removing a
/// prefix (e.g. a shebang line) from the generated code.
///
/// Reuses the map's existing allocations: strings are moved, and the token buffer is mutated
/// in place unless tokens have to be dropped (only when some token maps into the stripped
/// prefix, which rolldown's own maps never do — prepended text carries no tokens).
pub fn adjust_sourcemap_dst_lines(sourcemap: SourceMap, lines: u32) -> SourceMap {
  if lines == 0 {
    return sourcemap;
  }

  let shift = |token: &Token| {
    Token::new(
      token.get_dst_line() - lines,
      token.get_dst_col(),
      token.get_src_line(),
      token.get_src_col(),
      token.get_source_id(),
      token.get_name_id(),
    )
  };

  let mut parts = sourcemap.into_parts();
  if parts.tokens.iter().any(|t| t.get_dst_line() < lines) {
    parts.tokens = parts.tokens.iter().filter(|t| t.get_dst_line() >= lines).map(shift).collect();
  } else {
    for token in &mut parts.tokens {
      *token = shift(token);
    }
  }
  // The chunk boundaries and VLQ baselines in `token_chunks` describe the pre-shift tokens.
  parts.token_chunks = None;

  SourceMap::from_parts(parts)
}

/// Builds an empty sourcemap with no tokens, sources, names, or contents.
pub fn empty_sourcemap() -> SourceMap {
  SourceMap::new(None, vec![], None, vec![], vec![], Box::new([]), None)
}

// <https://github.com/rollup/rollup/blob/master/src/utils/collapseSourcemaps.ts>
//
// Input maps may borrow their strings (e.g. a codegen map borrowing the source it was
// printed from) — the output is always owned, since it copies every string it keeps.
// This lets callers collapse a freshly generated map without `into_owned`-ing it first.
pub fn collapse_sourcemaps(sourcemap_chain: &[&oxc_sourcemap::SourceMap<'_>]) -> SourceMap {
  debug_assert!(sourcemap_chain.len() > 1);
  if sourcemap_chain.len() == 1 {
    // If there's only one sourcemap, return it as is.
    return sourcemap_chain[0].clone().into_owned();
  }
  let tokens = remap_chain(sourcemap_chain, &mut []);
  let (sources, source_contents) = copy_sources(sourcemap_chain[0], None);
  let names = copy_names(sourcemap_chain, None);
  SourceMap::new(None, names, None, sources, source_contents, tokens, None)
}

/// Like `collapse_sourcemaps`, but keeps only the sources and names that a traced token
/// references, as Rollup's `traceMappings()` does. So a map with no mappings (e.g. a transform's
/// `{ mappings: '' }`) cuts out the code before it. A chain of one map is traced too, but it
/// keeps its other fields, such as `sourceRoot`, as `getCombinedSourcemap` did before.
///
/// The result copies only the strings that it keeps. The token ids change only when an item that
/// goes comes before an item that stays, or when a token has an id out of range.
pub fn collapse_sourcemaps_traced(sourcemap_chain: &[&oxc_sourcemap::SourceMap<'_>]) -> SourceMap {
  if let [map] = sourcemap_chain {
    return trace_single_map(map);
  }
  let first_map = sourcemap_chain.first().expect("sourcemap_chain should not be empty");
  let name_count: usize = sourcemap_chain.iter().map(|map| map.get_names().len()).sum();
  // The last flag is for the name ids out of range. A chain without names marks no names.
  let mut name_used = if name_count == 0 { Vec::new() } else { vec![false; name_count + 1] };
  let mut tokens = remap_chain(sourcemap_chain, &mut name_used);
  let name_out_of_range = name_used.pop();
  let (mut stack_flags, mut heap_flags) = ([false; 64], Vec::new());
  let source_used = source_flags(first_map.get_sources().len(), &mut stack_flags, &mut heap_flags);
  let scan = scan_sources(tokens.iter().copied(), source_used);
  let every_name_used = name_used.iter().all(|&used| used);
  let source_used = (!scan.every_source_used).then_some(&*source_used);
  if source_used.is_some() || !every_name_used {
    // A chain without names has no flag for the ids out of range, because each of its name ids
    // is out of range. This block runs for it only when a source goes, and then the scan read
    // every token.
    let name_out_of_range = name_out_of_range.unwrap_or(scan.has_name_id);
    let new_ids = NewIds::new(source_used, scan.source_out_of_range, &name_used, name_out_of_range);
    if !new_ids.keeps_ids() {
      for token in &mut tokens {
        *token = new_ids.apply(*token);
      }
    }
  }
  let (sources, source_contents) = copy_sources(first_map, source_used);
  let names = copy_names(sourcemap_chain, (!every_name_used).then_some(&name_used));
  SourceMap::new(None, names, None, sources, source_contents, tokens, None)
}

/// One map has nothing to remap. When a token references every source and name, the map is copied
/// as is. Otherwise, the copy keeps the other fields, but not `token_chunks`.
fn trace_single_map(map: &oxc_sourcemap::SourceMap<'_>) -> SourceMap {
  let (mut stack_flags, mut heap_flags) = ([false; 64], Vec::new());
  let source_used = source_flags(map.get_sources().len(), &mut stack_flags, &mut heap_flags);
  let scan = scan_sources(map.get_tokens(), source_used);
  let (name_used, name_out_of_range) = if map.get_names().len() == 0 {
    // Each name id is out of range, so the name scan is not necessary. The result is used only
    // when a source goes, and then the source scan read every token.
    (Vec::new(), scan.has_name_id)
  } else {
    mark_names(map)
  };
  let every_name_used = name_used.iter().all(|&used| used);
  if scan.every_source_used && every_name_used {
    return map.clone().into_owned();
  }
  let source_used = (!scan.every_source_used).then_some(&*source_used);
  let new_ids = NewIds::new(source_used, scan.source_out_of_range, &name_used, name_out_of_range);
  let (sources, source_contents) = copy_sources(map, source_used);
  let ignore_list = map.get_ignore_list().map(|ids| match source_used {
    Some(used) => {
      let source_ids = renumber_used(used);
      ids.iter().filter_map(|&id| new_id(&source_ids, id)).collect()
    }
    None => ids.to_vec(),
  });
  SourceMap::from_parts(SourceMapParts {
    file: map.get_file().map(owned),
    names: copy_names(std::slice::from_ref(&map), (!every_name_used).then_some(&name_used)),
    source_root: map.get_source_root().map(owned),
    sources,
    source_contents,
    tokens: if new_ids.keeps_ids() {
      map.get_tokens().collect()
    } else {
      map.get_tokens().map(|token| new_ids.apply(token)).collect()
    },
    // The VLQ baselines in `token_chunks` describe the old ids.
    token_chunks: None,
    ignore_list,
    debug_id: map.get_debug_id().map(owned),
  })
}

/// Returns one flag for each of `count` sources. Most maps have few sources, so the flags usually
/// fit in `stack`.
fn source_flags<'a>(
  count: usize,
  stack: &'a mut [bool; 64],
  heap: &'a mut Vec<bool>,
) -> &'a mut [bool] {
  if count <= stack.len() {
    &mut stack[..count]
  } else {
    heap.resize(count, false);
    heap
  }
}

/// What `scan_sources` found in the tokens that it read.
struct SourceScan {
  /// A token references each source.
  every_source_used: bool,
  /// A token has a source id out of range.
  source_out_of_range: bool,
  /// A token has a name id.
  has_name_id: bool,
}

/// Marks the sources that the tokens reference. The scan stops when every source is marked, so it
/// reads every token only when a source goes. A module map usually has one source, so the scan
/// usually stops at its first mapped token.
fn scan_sources(tokens: impl Iterator<Item = Token>, used: &mut [bool]) -> SourceScan {
  let mut unmarked = used.len();
  let mut source_out_of_range = false;
  let mut has_name_id = false;
  for token in tokens {
    if unmarked == 0 {
      break;
    }
    has_name_id |= token.get_name_id().is_some();
    if let Some(id) = token.get_source_id() {
      match used.get_mut(id as usize) {
        Some(flag) => unmarked -= usize::from(!std::mem::replace(flag, true)),
        None => source_out_of_range = true,
      }
    }
  }
  SourceScan { every_source_used: unmarked == 0, source_out_of_range, has_name_id }
}

/// Returns which names the tokens of `map` reference, and `true` when a token has a name id out of
/// range.
fn mark_names(map: &oxc_sourcemap::SourceMap<'_>) -> (Vec<bool>, bool) {
  let name_count = map.get_names().len();
  // Flag `name_count` is for the ids out of range, and the flag after it is for the tokens
  // without a name, so the loop needs no branch.
  let mut used = vec![false; name_count + 2];
  for token in map.get_tokens() {
    used[token.get_name_id().map_or(name_count + 1, |id| (id as usize).min(name_count))] = true;
  }
  let out_of_range = used[name_count];
  used.truncate(name_count);
  (used, out_of_range)
}

/// Returns `true` when the new ids change a token's id. The kept items keep their ids when they
/// come before the items that go, and no token has an id out of range.
fn ids_change(used: &[bool], out_of_range: bool) -> bool {
  out_of_range || used.iter().skip_while(|&&used| used).any(|&used| used)
}

/// The new ids of the tokens. A table is `None` when the tokens keep those ids.
struct NewIds {
  sources: Option<Vec<Option<u32>>>,
  names: Option<Vec<Option<u32>>>,
}

impl NewIds {
  /// `source_used` is `None` when every source stays.
  fn new(
    source_used: Option<&[bool]>,
    source_out_of_range: bool,
    name_used: &[bool],
    name_out_of_range: bool,
  ) -> Self {
    Self {
      sources: source_used.filter(|used| ids_change(used, source_out_of_range)).map(renumber_used),
      names: ids_change(name_used, name_out_of_range).then(|| renumber_used(name_used)),
    }
  }

  fn keeps_ids(&self) -> bool {
    self.sources.is_none() && self.names.is_none()
  }

  /// A token loses an id that points to a dropped item or out of range.
  fn apply(&self, token: Token) -> Token {
    let renumber = |ids: Option<&[Option<u32>]>, id: Option<u32>| {
      ids.map_or(id, |ids| id.and_then(|id| new_id(ids, id)))
    };
    Token::new(
      token.get_dst_line(),
      token.get_dst_col(),
      token.get_src_line(),
      token.get_src_col(),
      renumber(self.sources.as_deref(), token.get_source_id()),
      renumber(self.names.as_deref(), token.get_name_id()),
    )
  }
}

fn new_id(ids: &[Option<u32>], id: u32) -> Option<u32> {
  ids.get(id as usize).copied().flatten()
}

/// Maps each old id to its new id, or to `None` when the item is dropped.
fn renumber_used(used: &[bool]) -> Vec<Option<u32>> {
  let mut next_id = 0;
  used
    .iter()
    .map(|&used| {
      used.then(|| {
        let id = next_id;
        next_id += 1;
        id
      })
    })
    .collect()
}

fn owned(value: &str) -> Cow<'static, str> {
  Cow::Owned(value.to_owned())
}

/// Returns the item when its flag is set.
fn kept<T>((item, &used): (T, &bool)) -> Option<T> {
  used.then_some(item)
}

/// Copies the names of every map in chain order. With `used`, it copies only the marked names.
fn copy_names(
  sourcemap_chain: &[&oxc_sourcemap::SourceMap<'_>],
  used: Option<&[bool]>,
) -> Vec<Cow<'static, str>> {
  let Some(used) = used else {
    let mut names =
      Vec::with_capacity(sourcemap_chain.iter().map(|map| map.get_names().len()).sum());
    for map in sourcemap_chain {
      names.extend(map.get_names().map(owned));
    }
    return names;
  };
  let mut names = Vec::with_capacity(used.iter().filter(|&&used| used).count());
  let all_names = sourcemap_chain.iter().flat_map(|map| map.get_names());
  names.extend(all_names.zip(used).filter_map(kept).map(owned));
  names
}

/// Copies the sources of `map` and their contents. With `used`, it copies only the marked sources,
/// and it drops the contents past the last source.
fn copy_sources(
  map: &oxc_sourcemap::SourceMap<'_>,
  used: Option<&[bool]>,
) -> (Vec<Cow<'static, str>>, Vec<Option<Cow<'static, str>>>) {
  let Some(used) = used else {
    return (
      map.get_sources().map(owned).collect(),
      map.get_source_contents().map(|content| content.map(owned)).collect(),
    );
  };
  (
    map.get_sources().zip(used).filter_map(kept).map(owned).collect(),
    map
      .get_source_contents()
      .zip(used)
      .filter_map(kept)
      .map(|content| content.map(owned))
      .collect(),
  )
}

/// Remaps the last map's tokens through the earlier maps. A name id in the result points into the
/// names of every map, in chain order. When `name_used` is not empty, the remap also marks the
/// names that a traced token references. Its last flag is then for the ids out of range.
fn remap_chain(
  sourcemap_chain: &[&oxc_sourcemap::SourceMap<'_>],
  name_used: &mut [bool],
) -> Box<[Token]> {
  let (last_map, chain_without_last) =
    sourcemap_chain.split_last().expect("sourcemap_chain should not be empty");

  // A token's name id in the result is `local_id + offset`, where `offset` counts the names of
  // the maps before its map.
  let mut offset = 0;
  // Pre-compute lookup tables paired with their offsets in reverse order so we avoid reversing
  // on every token lookup.
  let mut chain_with_offsets: Vec<_> = chain_without_last
    .iter()
    .map(|sourcemap| {
      let map_offset = offset;
      #[expect(clippy::cast_possible_truncation)]
      let name_count = sourcemap.get_names().len() as u32;
      offset += name_count;
      (*sourcemap, sourcemap.generate_lookup_table(), map_offset)
    })
    .collect();
  chain_with_offsets.reverse();
  let last_offset = offset;

  // `last_offset` counts the names of every map before the last one. When it is 0, no traced
  // token can carry a name, so the remap loop skips the per-step name tracking. A chain without
  // names also skips the marks.
  let remap = match (last_offset == 0, name_used.is_empty()) {
    (true, true) => remap_tokens::<false, false>,
    (true, false) => remap_tokens::<false, true>,
    (false, true) => remap_tokens::<true, false>,
    (false, false) => remap_tokens::<true, true>,
  };
  remap(last_map, &chain_with_offsets, last_offset, name_used)
}

/// Remaps `last_map`'s tokens through `chain`, the earlier maps with the nearest one first.
/// `TRACK_NAMES` and `MARK_NAMES` are consts so that a chain without names, or a collapse that
/// does not mark names in `name_used`, compiles without that work. With `MARK_NAMES`, `name_used`
/// has one flag for each name and one more flag for the ids out of range.
fn remap_tokens<const TRACK_NAMES: bool, const MARK_NAMES: bool>(
  last_map: &oxc_sourcemap::SourceMap<'_>,
  chain: &[(&oxc_sourcemap::SourceMap<'_>, Vec<&[Token]>, u32)],
  last_offset: u32,
  name_used: &mut [bool],
) -> Box<[Token]> {
  let source_view_tokens = last_map.get_source_view_tokens();
  let mut remapped = Vec::with_capacity(source_view_tokens.size_hint().0);
  let mut dst_line = None;
  let mut has_mapping = false;
  let mut is_mapped = false;
  let mut leading_unmapped = None;

  for token in source_view_tokens {
    if dst_line != Some(token.get_dst_line()) {
      dst_line = Some(token.get_dst_line());
      has_mapping = false;
      is_mapped = false;
      leading_unmapped = None;
    }

    let unmapped_token = || Token::new(token.get_dst_line(), token.get_dst_col(), 0, 0, None, None);
    let mapped_token = (|| {
      token.get_source_id()?;

      let mut original_token = token;
      let mut name_id = token.get_name_id().map(|id| id + last_offset);
      for (sourcemap, lookup_table, offset) in chain {
        let traced = sourcemap.lookup_source_view_token_approx(
          lookup_table,
          original_token.get_src_line(),
          original_token.get_src_col(),
        )?;
        traced.get_source_id()?;
        if TRACK_NAMES {
          // Prefer the name from this (earlier) map; otherwise carry forward the downstream one.
          name_id = traced.get_name_id().map(|id| id + offset).or(name_id);
        }
        original_token = traced;
      }

      if MARK_NAMES {
        if let Some(id) = name_id {
          // An id out of range marks the last flag.
          let out_of_range = name_used.len() - 1;
          if let Some(used) = name_used.get_mut((id as usize).min(out_of_range)) {
            *used = true;
          }
        }
      }
      Some(Token::new(
        token.get_dst_line(),
        token.get_dst_col(),
        original_token.get_src_line(),
        original_token.get_src_col(),
        original_token.get_source_id(),
        name_id,
      ))
    })();

    if let Some(mapped_token) = mapped_token {
      if !has_mapping {
        // Keep a leading unmapped segment when this line later becomes mapped. Approximate
        // lookups clamp positions before the first segment, so dropping it would extend the
        // first mapping backwards during another composition.
        if let Some(leading_unmapped) = leading_unmapped.take() {
          remapped.push(leading_unmapped);
        }
        has_mapping = true;
      }
      remapped.push(mapped_token);
      is_mapped = true;
    } else if is_mapped {
      // One segment is enough to terminate the mapped range. Further misses on this line remain
      // unmapped without additional tokens.
      remapped.push(unmapped_token());
      is_mapped = false;
    } else if !has_mapping && leading_unmapped.is_none() {
      // Defer this segment until the line produces a mapping. A wholly unmapped line needs no
      // tokens, but a leading unmapped range before a later mapping must remain explicit.
      leading_unmapped = Some(unmapped_token());
    }
  }

  remapped.into_boxed_slice()
}

#[test]
fn test_collapse_sourcemaps() {
  use crate::{SourceJoiner, SourceMapSource, collapse_sourcemaps};
  use oxc::{
    allocator::Allocator,
    codegen::{Codegen, CodegenOptions, CodegenReturn, CommentOptions},
    parser::Parser,
    span::SourceType,
  };
  use oxc_sourcemap::SourcemapVisualizer;

  let allocator = Allocator::default();

  let mut source_joiner = SourceJoiner::default();

  let filename = "foo.js".to_string();
  let source_text = "const foo = 1; console.log(foo);\n".to_string();
  let source_type = SourceType::from_path(&filename).unwrap();
  let ret1 = Parser::new(&allocator, &source_text, source_type).parse();
  let CodegenReturn { map, code, .. } = Codegen::new()
    .with_options(CodegenOptions {
      comments: CommentOptions { normal: false, ..CommentOptions::default() },
      source_map_path: Some(filename.into()),
      ..CodegenOptions::default()
    })
    .build(&ret1.program);
  source_joiner.append_source(SourceMapSource::new(code, map.unwrap().into_owned()));

  let filename = "bar.js".to_string();
  let source_text = "const bar = 2; console.log(bar);\n".to_string();
  let ret2: oxc::parser::ParserReturn = Parser::new(&allocator, &source_text, source_type).parse();
  let CodegenReturn { map, code, .. } = Codegen::new()
    .with_options(CodegenOptions {
      source_map_path: Some(filename.into()),
      ..CodegenOptions::default()
    })
    .build(&ret2.program);
  source_joiner.append_source(SourceMapSource::new(code, map.unwrap().into_owned()));

  let (source_text, source_map) = source_joiner.join();

  let mut sourcemap_chain = vec![];

  sourcemap_chain.push(source_map.as_ref().unwrap());

  let filename = "chunk.js".to_string();
  let ret3 = Parser::new(&allocator, &source_text, source_type).parse();
  let CodegenReturn { map, code, .. } = Codegen::new()
    .with_options(CodegenOptions {
      comments: CommentOptions { normal: false, ..CommentOptions::default() },
      source_map_path: Some(filename.into()),
      ..CodegenOptions::default()
    })
    .build(&ret3.program);
  let map = map.unwrap().into_owned();
  sourcemap_chain.push(&map);

  let map = collapse_sourcemaps(&sourcemap_chain);
  assert_eq!(
    SourcemapVisualizer::new(&code, &map).get_text(),
    r#"- foo.js
(0:0) "const " --> (0:0) "const "
(0:6) "foo = " --> (0:6) "foo = "
(0:12) "1; " --> (0:12) "1;\n"
(0:15) "console." --> (1:0) "console."
(0:23) "log(" --> (1:8) "log("
(0:27) "foo" --> (1:12) "foo"
(0:30) ");\n" --> (1:15) ");\n"
- bar.js
(0:0) "const " --> (2:0) "const "
(0:6) "bar = " --> (2:6) "bar = "
(0:12) "2; " --> (2:12) "2;\n"
(0:15) "console." --> (3:0) "console."
(0:23) "log(" --> (3:8) "log("
(0:27) "bar" --> (3:12) "bar"
(0:30) ");\n" --> (3:15) ");\n"
"#
  );
}

#[test]
fn test_collapse_sourcemaps_clamps_before_first_token_on_a_line() {
  use oxc_sourcemap::SourceMapBuilder;

  let mut detailed_builder = SourceMapBuilder::default();
  let original_source = detailed_builder.add_source_and_content("original.js", "  target();\n");
  detailed_builder.add_token(0, 2, 0, 2, Some(original_source), None);
  let detailed_map = detailed_builder.into_sourcemap().into_owned();

  let mut coarse_builder = SourceMapBuilder::default();
  let intermediate_source = coarse_builder.add_source_and_content("intermediate.js", "target();\n");
  coarse_builder.add_token(0, 0, 0, 0, Some(intermediate_source), None);
  let coarse_map = coarse_builder.into_sourcemap().into_owned();

  let collapsed = collapse_sourcemaps(&[&detailed_map, &coarse_map]);
  let tokens = collapsed.get_tokens().collect::<Vec<_>>();

  assert_eq!(tokens.len(), 1, "a coarse token before the line's first detailed token must survive");
  assert_eq!((tokens[0].get_dst_line(), tokens[0].get_dst_col()), (0, 0));
  assert_eq!((tokens[0].get_src_line(), tokens[0].get_src_col()), (0, 2));
  assert_eq!(tokens[0].get_source_id(), Some(0));
  assert_eq!(collapsed.get_sources().collect::<Vec<_>>(), ["original.js"]);
}

#[test]
fn test_collapse_sourcemaps_preserves_an_explicitly_unmapped_final_boundary() {
  use oxc_sourcemap::SourceMapBuilder;

  let mut detailed_builder = SourceMapBuilder::default();
  let original_source = detailed_builder.add_source_and_content("original.js", "mapped unmapped\n");
  detailed_builder.add_token(0, 0, 0, 0, Some(original_source), None);
  let detailed_map = detailed_builder.into_sourcemap().into_owned();

  let mut final_builder = SourceMapBuilder::default();
  let intermediate_source =
    final_builder.add_source_and_content("intermediate.js", "mapped unmapped\n");
  final_builder.add_token(0, 0, 0, 0, Some(intermediate_source), None);
  final_builder.add_token(0, 5, 0, 0, None, None);
  let final_map = final_builder.into_sourcemap().into_owned();

  let collapsed = collapse_sourcemaps(&[&detailed_map, &final_map]);
  let lookup_table = collapsed.generate_lookup_table();

  assert_eq!(collapsed.get_tokens().count(), 2);
  assert_eq!(collapsed.lookup_token(&lookup_table, 0, 4).unwrap().get_source_id(), Some(0));
  assert_eq!(collapsed.lookup_token(&lookup_table, 0, 5).unwrap().get_source_id(), None);
  assert_eq!(collapsed.lookup_token(&lookup_table, 0, 9).unwrap().get_source_id(), None);
}

#[test]
fn test_collapse_sourcemaps_preserves_an_explicitly_unmapped_intermediate_boundary() {
  use oxc_sourcemap::SourceMapBuilder;

  let mut detailed_builder = SourceMapBuilder::default();
  let original_source = detailed_builder.add_source_and_content("original.js", "mapped unmapped\n");
  detailed_builder.add_token(0, 0, 0, 0, Some(original_source), None);
  let detailed_map = detailed_builder.into_sourcemap().into_owned();

  let mut intermediate_builder = SourceMapBuilder::default();
  let detailed_source =
    intermediate_builder.add_source_and_content("detailed.js", "mapped unmapped\n");
  intermediate_builder.add_token(0, 0, 0, 0, Some(detailed_source), None);
  intermediate_builder.add_token(0, 5, 0, 0, None, None);
  let intermediate_map = intermediate_builder.into_sourcemap().into_owned();

  let mut outer_builder = SourceMapBuilder::default();
  let intermediate_source =
    outer_builder.add_source_and_content("intermediate.js", "mapped unmapped\n");
  outer_builder.add_token(0, 0, 0, 0, Some(intermediate_source), None);
  outer_builder.add_token(0, 5, 0, 5, Some(intermediate_source), None);
  let outer_map = outer_builder.into_sourcemap().into_owned();

  let collapsed = collapse_sourcemaps(&[&detailed_map, &intermediate_map, &outer_map]);
  let lookup_table = collapsed.generate_lookup_table();

  assert_eq!(collapsed.get_tokens().count(), 2);
  assert_eq!(collapsed.lookup_token(&lookup_table, 0, 4).unwrap().get_source_id(), Some(0));
  assert_eq!(collapsed.lookup_token(&lookup_table, 0, 5).unwrap().get_source_id(), None);
  assert_eq!(collapsed.lookup_token(&lookup_table, 0, 9).unwrap().get_source_id(), None);
}

/// Test for https://github.com/vitejs/vite/issues/20721
#[test]
fn test_collapse_sourcemaps_preserves_boundary_when_trace_has_no_mapping() {
  use oxc_sourcemap::SourceMapBuilder;

  let mut detailed_builder = SourceMapBuilder::default();
  let original_source = detailed_builder.add_source_and_content("original.js", "mapped\n");
  detailed_builder.add_token(0, 0, 0, 0, Some(original_source), None);
  let detailed_map = detailed_builder.into_sourcemap().into_owned();

  let mut outer_builder = SourceMapBuilder::default();
  let intermediate_source =
    outer_builder.add_source_and_content("intermediate.js", "mapped\ngenerated\n");
  outer_builder.add_token(0, 0, 0, 0, Some(intermediate_source), None);
  outer_builder.add_token(0, 5, 1, 0, Some(intermediate_source), None);
  outer_builder.add_token(0, 6, 1, 1, Some(intermediate_source), None);
  let outer_map = outer_builder.into_sourcemap().into_owned();

  let collapsed = collapse_sourcemaps(&[&detailed_map, &outer_map]);
  let lookup_table = collapsed.generate_lookup_table();

  assert_eq!(collapsed.get_tokens().count(), 2);
  assert_eq!(collapsed.lookup_token(&lookup_table, 0, 4).unwrap().get_source_id(), Some(0));
  assert_eq!(collapsed.lookup_token(&lookup_table, 0, 5).unwrap().get_source_id(), None);
  assert_eq!(collapsed.lookup_token(&lookup_table, 0, 9).unwrap().get_source_id(), None);
}

#[test]
fn test_collapse_sourcemaps_preserves_leading_unmapped_range_before_mapping() {
  use oxc_sourcemap::SourceMapBuilder;

  let mut detailed_builder = SourceMapBuilder::default();
  let original_source = detailed_builder.add_source_and_content("original.js", "mapped\n");
  detailed_builder.add_token(0, 0, 0, 0, None, None);
  detailed_builder.add_token(0, 5, 0, 0, Some(original_source), None);
  let detailed_map = detailed_builder.into_sourcemap().into_owned();

  let mut outer_builder = SourceMapBuilder::default();
  let intermediate_source =
    outer_builder.add_source_and_content("intermediate.js", "unmapped mapped\n");
  outer_builder.add_token(0, 0, 0, 0, Some(intermediate_source), None);
  outer_builder.add_token(0, 5, 0, 5, Some(intermediate_source), None);
  let outer_map = outer_builder.into_sourcemap().into_owned();

  let collapsed = collapse_sourcemaps(&[&detailed_map, &outer_map]);
  let lookup_table = collapsed.generate_lookup_table();

  assert_eq!(collapsed.get_tokens().count(), 2);
  assert_eq!(collapsed.lookup_token(&lookup_table, 0, 0).unwrap().get_source_id(), None);
  assert_eq!(collapsed.lookup_token(&lookup_table, 0, 5).unwrap().get_source_id(), Some(0));
}

/// Test for https://github.com/rollup/rollup/issues/5955
#[test]
fn test_collapse_sourcemaps_with_coarse_segments() {
  use oxc_sourcemap::SourceMap;

  fn get_loc(mut pos: usize, code: &str) -> (u32, u32) {
    for (line_idx, line) in code.lines().enumerate() {
      if pos <= line.len() {
        #[expect(clippy::cast_possible_truncation)]
        return (line_idx as u32, pos as u32);
      }
      pos -= line.len() + 1; // +1 for newline
    }
    panic!("position out of bounds");
  }

  let original_code = "import { useEffect } from 'react';

export function App() {
  useEffect(() => {
    console.log('ReplayAnalyze');
  }, []);

  return <div>{'.'}</div>;
}
";
  let transformed_code = r#"import{jsx}from"react/jsx-runtime";import{useEffect}from"react";export function App(){return useEffect((()=>{console.log("ReplayAnalyze")}),[]),jsx("div",{children:"."})}"#;

  // spellchecker:off
  let esbuild_map_json = r#"{
    "version": 3,
    "sources": ["<stdin>"],
    "sourcesContent": ["import { useEffect } from 'react';\n\nexport function App() {\n  useEffect(() => {\n    console.log('ReplayAnalyze');\n  }, []);\n\n  return <div>{'.'}</div>;\n}\n"],
    "mappings": "AAOS;AAPT,SAAS,iBAAiB;AAEnB,gBAAS,MAAM;AACpB,YAAU,MAAM;AACd,YAAQ,IAAI,eAAe;AAAA,EAC7B,GAAG,CAAC,CAAC;AAEL,SAAO,oBAAC,SAAK,eAAI;AACnB;",
    "names": []
  }"#;
  // spellchecker:on
  let esbuild_map = SourceMap::from_json_string(esbuild_map_json).unwrap();

  // spellchecker:off
  let terser_map_json = r#"{
    "version": 3,
    "names": ["jsx", "useEffect", "App", "console", "log", "children"],
    "sources": ["0"],
    "sourcesContent": ["import { jsx } from \"react/jsx-runtime\";\nimport { useEffect } from \"react\";\nexport function App() {\n  useEffect(() => {\n    console.log(\"ReplayAnalyze\");\n  }, []);\n  return /* @__PURE__ */ jsx(\"div\", { children: \".\" });\n}\n"],
    "mappings": "OAASA,QAAW,2BACXC,cAAiB,eACnB,SAASC,MAId,OAHAD,WAAU,KACRE,QAAQC,IAAI,gBAAgB,GAC3B,IACoBJ,IAAI,MAAO,CAAEK,SAAU,KAChD"
  }"#;
  // spellchecker:on
  let terser_map = SourceMap::from_json_string(terser_map_json).unwrap();

  let collapsed = collapse_sourcemaps(&[&esbuild_map, &terser_map]);
  let collapsed_lookup_table = collapsed.generate_lookup_table();

  let generated_loc = get_loc(transformed_code.find("return").unwrap(), transformed_code);
  let original_loc = collapsed
    .lookup_source_view_token(&collapsed_lookup_table, generated_loc.0, generated_loc.1)
    .map(|token| (token.get_src_line(), token.get_src_col()));
  assert_eq!(
    original_loc,
    Some(get_loc(original_code.find("return").unwrap(), original_code)),
    "collapsed sourcemap should map 'return' in transformed code back to original source"
  );
}

/// Names introduced only by the last map in the chain must survive collapsing.
#[test]
fn test_collapse_sourcemaps_preserves_last_map_names() {
  use oxc_sourcemap::SourceMapBuilder;

  let mut first_builder = SourceMapBuilder::default();
  let first_source_id =
    first_builder.set_source_and_content("source.ts", "function topLevelDemo() {}");
  first_builder.add_token(0, 0, 0, 0, Some(first_source_id), None);
  first_builder.add_token(0, 9, 0, 9, Some(first_source_id), None);
  let first_map = first_builder.into_sourcemap();

  let mut last_builder = SourceMapBuilder::default();
  let last_source_id =
    last_builder.set_source_and_content("bundle.js", "function topLevelDemo() {}");
  let top_level_demo = last_builder.add_name("topLevelDemo");
  last_builder.add_token(0, 0, 0, 0, Some(last_source_id), None);
  last_builder.add_token(0, 9, 0, 9, Some(last_source_id), Some(top_level_demo));
  let last_map = last_builder.into_sourcemap();

  let collapsed = collapse_sourcemaps(&[&first_map, &last_map]);
  let lookup = collapsed.generate_lookup_table();
  let token =
    collapsed.lookup_source_view_token(&lookup, 0, 9).expect("token at generated position (0:9)");
  assert_eq!(token.get_name().map(AsRef::as_ref), Some("topLevelDemo"));
}

/// In a 3-map chain, a name from a middle map (e.g. an intermediate transform) must survive
/// when neither the first nor the last map names the corresponding position.
#[test]
fn test_collapse_sourcemaps_preserves_middle_map_names() {
  use oxc_sourcemap::SourceMapBuilder;

  let mut first_builder = SourceMapBuilder::default();
  let first_source_id = first_builder.set_source_and_content("source.ts", "const foo = 1");
  first_builder.add_token(0, 6, 0, 6, Some(first_source_id), None);
  let first_map = first_builder.into_sourcemap();

  let mut middle_builder = SourceMapBuilder::default();
  let middle_source_id = middle_builder.set_source_and_content("first.js", "const foo = 1");
  let foo = middle_builder.add_name("foo");
  middle_builder.add_token(0, 6, 0, 6, Some(middle_source_id), Some(foo));
  let middle_map = middle_builder.into_sourcemap();

  let mut last_builder = SourceMapBuilder::default();
  let last_source_id = last_builder.set_source_and_content("middle.js", "const foo = 1");
  last_builder.add_token(0, 6, 0, 6, Some(last_source_id), None);
  let last_map = last_builder.into_sourcemap();

  let collapsed = collapse_sourcemaps(&[&first_map, &middle_map, &last_map]);
  let lookup = collapsed.generate_lookup_table();
  let token =
    collapsed.lookup_source_view_token(&lookup, 0, 6).expect("token at generated position (0:6)");
  assert_eq!(token.get_name().map(AsRef::as_ref), Some("foo"));
}

/// When both maps name a position, prefer the first map's (the earlier original).
#[test]
fn test_collapse_sourcemaps_prefers_first_map_name() {
  use oxc_sourcemap::SourceMapBuilder;

  let mut first_builder = SourceMapBuilder::default();
  let first_source_id =
    first_builder.set_source_and_content("source.ts", "const DEBUG_BUILD = true");
  let debug_build = first_builder.add_name("DEBUG_BUILD");
  first_builder.add_token(0, 6, 0, 6, Some(first_source_id), Some(debug_build));
  let first_map = first_builder.into_sourcemap();

  let mut last_builder = SourceMapBuilder::default();
  let last_source_id =
    last_builder.set_source_and_content("bundle.js", "const DEBUG_BUILD$1 = true");
  let intermediate = last_builder.add_name("DEBUG_BUILD$1");
  last_builder.add_token(0, 6, 0, 6, Some(last_source_id), Some(intermediate));
  let last_map = last_builder.into_sourcemap();

  let collapsed = collapse_sourcemaps(&[&first_map, &last_map]);
  let lookup = collapsed.generate_lookup_table();
  let token =
    collapsed.lookup_source_view_token(&lookup, 0, 6).expect("token at generated position (0:6)");
  assert_eq!(token.get_name().map(AsRef::as_ref), Some("DEBUG_BUILD"));
}

#[test]
fn test_collapse_sourcemaps_traced_drops_unreferenced_sources_and_names() {
  let traced = |json: &str| {
    let map = oxc_sourcemap::SourceMap::from_json_string(json).unwrap();
    collapse_sourcemaps_traced(&[&map]).to_json_string()
  };
  // `b.js` and the name `x` have no token, so they go. The kept items keep their order.
  assert_eq!(
    traced(
      r#"{"version":3,"names":["x","y"],"sources":["a.js","b.js","c.js"],"sourcesContent":["a","b","c"],"mappings":"AAAA,EEAAC"}"#
    ),
    r#"{"version":3,"names":["y"],"sources":["a.js","c.js"],"sourcesContent":["a","c"],"mappings":"AAAA,ECAAA"}"#
  );
  // The only source has a token, but the name `x` still goes.
  assert_eq!(
    traced(
      r#"{"version":3,"names":["x","y"],"sources":["a.js"],"sourcesContent":["a"],"mappings":"AAAAC"}"#
    ),
    r#"{"version":3,"names":["y"],"sources":["a.js"],"sourcesContent":["a"],"mappings":"AAAAA"}"#
  );
  // Everything has a token, so the map stays the same.
  let kept =
    r#"{"version":3,"names":["y"],"sources":["a.js"],"sourcesContent":["a"],"mappings":"AAAAA"}"#;
  assert_eq!(traced(kept), kept);
}

/// The earlier map's name wins, so the later map's name for the same position goes.
#[test]
fn test_collapse_sourcemaps_traced_drops_overridden_names() {
  use oxc_sourcemap::SourceMapBuilder;

  let mut first_builder = SourceMapBuilder::default();
  let first_source_id =
    first_builder.set_source_and_content("source.ts", "const DEBUG_BUILD = true");
  let debug_build = first_builder.add_name("DEBUG_BUILD");
  first_builder.add_token(0, 6, 0, 6, Some(first_source_id), Some(debug_build));
  let first_map = first_builder.into_sourcemap();

  let mut last_builder = SourceMapBuilder::default();
  let last_source_id =
    last_builder.set_source_and_content("bundle.js", "const DEBUG_BUILD$1 = true");
  let intermediate = last_builder.add_name("DEBUG_BUILD$1");
  last_builder.add_token(0, 6, 0, 6, Some(last_source_id), Some(intermediate));
  let last_map = last_builder.into_sourcemap();

  let collapsed = collapse_sourcemaps_traced(&[&first_map, &last_map]);
  assert_eq!(collapsed.get_names().collect::<Vec<_>>(), ["DEBUG_BUILD"]);
  let token = collapsed.get_tokens().last().unwrap();
  assert_eq!((token.get_source_id(), token.get_name_id()), (Some(0), Some(0)));
}

/// Vite's `css-sourcemap` playground reads a Sass map with `"sourceRoot": ""` back through
/// `getCombinedSourcemap`.
#[test]
fn test_collapse_sourcemaps_traced_keeps_single_map_fields() {
  let parse = |json: &str| oxc_sourcemap::SourceMap::from_json_string(json).unwrap().into_owned();
  // Every source has a token, so the map stays the same.
  let kept = parse(
    r#"{"version":3,"sourceRoot":"","names":[],"sources":["a.sass","b.sass"],"sourcesContent":["a","b"],"mappings":"AAAA,ECAA"}"#,
  );
  assert_eq!(collapse_sourcemaps_traced(&[&kept]).to_json_string(), kept.to_json_string());
  // `b.js` has no token, so it goes. `sourceRoot` stays, and `ignoreList` follows the new ids.
  let dropped = collapse_sourcemaps_traced(&[&parse(
    r#"{"version":3,"sourceRoot":"src/","names":[],"sources":["a.js","b.js","c.js"],"sourcesContent":["a","b","c"],"ignoreList":[1,2],"mappings":"AAAA,EEAA"}"#,
  )]);
  assert_eq!(dropped.get_source_root(), Some("src/"));
  assert_eq!(dropped.get_sources().collect::<Vec<_>>(), ["a.js", "c.js"]);
  assert_eq!(dropped.get_ignore_list(), Some([1].as_slice()));
  assert_eq!(dropped.get_tokens().last().unwrap().get_source_id(), Some(1));
}

#[test]
fn test_collapse_sourcemaps_traced_beyond_stack_flags() {
  // 70 sources do not fit the 64 stack flags, so the source check takes the heap path.
  let sources: Vec<String> = (0..70).map(|i| format!("s{i}.js")).collect();
  let mut builder = oxc_sourcemap::SourceMapBuilder::default();
  let source_ids: Vec<u32> =
    sources.iter().map(|source| builder.add_source_and_content(source, "")).collect();
  builder.add_name("unused");
  let used = builder.add_name("used");
  builder.add_token(0, 0, 0, 0, Some(source_ids[69]), Some(used));
  let map = builder.into_sourcemap();
  let dropped = collapse_sourcemaps_traced(&[&map]);
  assert_eq!(dropped.get_sources().collect::<Vec<_>>(), ["s69.js"]);
  assert_eq!(dropped.get_names().collect::<Vec<_>>(), ["used"]);
  let token = dropped.get_tokens().next().unwrap();
  assert_eq!((token.get_source_id(), token.get_name_id()), (Some(0), Some(0)));
}