#![deny(missing_debug_implementations)]
extern crate vlq;
pub mod comparators;
use comparators::ComparatorFunction;
use std::cmp;
use std::marker::PhantomData;
use std::mem;
use std::slice;
/// Errors that can occur during parsing.
#[derive(Copy, Clone, Debug)]
#[repr(u32)]
pub enum Error {
// NB: 0 is reserved for OK.
/// The mappings contained a negative line, column, source index, or name
/// index.
UnexpectedNegativeNumber = 1,
/// The mappings contained a number larger than `u32::MAX`.
UnexpectedlyBigNumber = 2,
/// Reached EOF while in the middle of parsing a VLQ.
VlqUnexpectedEof = 3,
/// Encountered an invalid base 64 character while parsing a VLQ.
VlqInvalidBase64 = 4,
/// VLQ encountered a number that, when decoded, would not fit in
/// an i64.
VlqOverflow = 5,
}
impl From<vlq::Error> for Error {
#[inline]
fn from(e: vlq::Error) -> Error {
match e {
vlq::Error::UnexpectedEof => Error::VlqUnexpectedEof,
vlq::Error::InvalidBase64(_) => Error::VlqInvalidBase64,
vlq::Error::Overflow => Error::VlqOverflow,
}
}
}
/// When doing fuzzy searching, whether to slide the next larger or next smaller
/// mapping from the queried location.
#[derive(Copy, Clone, Debug, PartialEq, Eq)]
#[repr(u32)]
pub enum Bias {
// XXX: make sure these values always match `mozilla/source-map`'s
// `SourceMapConsumer.{GreatestLower,LeastUpper}Bound` values!
/// Slide to the next smaller mapping.
GreatestLowerBound = 1,
/// Slide to the next larger mapping.
LeastUpperBound = 2,
}
impl Default for Bias {
#[inline]
fn default() -> Bias {
Bias::GreatestLowerBound
}
}
/// A trait for defining a set of RAII types that can observe the start and end
/// of various operations and queries we perform in their constructors and
/// destructors.
///
/// This is also implemented for `()` as the "null observer" that doesn't
/// actually do anything.
pub trait Observer: Default {
/// Observe the parsing of the `"mappings"` string.
type ParseMappings: Default;
/// Observe sorting parsed mappings by original location.
type SortByOriginalLocation: Default;
/// Observe sorting parsed mappings by generated location.
type SortByGeneratedLocation: Default;
/// Observe computing column spans.
type ComputeColumnSpans: Default;
/// Observe querying what the original location for some generated location
/// is.
type OriginalLocationFor: Default;
/// Observe querying what the generated location for some original location
/// is.
type GeneratedLocationFor: Default;
/// Observe querying what all generated locations for some original location
/// is.
type AllGeneratedLocationsFor: Default;
}
impl Observer for () {
type ParseMappings = ();
type SortByOriginalLocation = ();
type SortByGeneratedLocation = ();
type ComputeColumnSpans = ();
type OriginalLocationFor = ();
type GeneratedLocationFor = ();
type AllGeneratedLocationsFor = ();
}
#[derive(Debug)]
enum LazilySorted<T, F, O> {
Sorted(Vec<T>, PhantomData<F>, PhantomData<O>),
Unsorted(Vec<T>),
}
impl<T, F, O> LazilySorted<T, F, O>
where
F: comparators::ComparatorFunction<T>,
O: Default,
{
#[inline]
fn sort(&mut self) -> &[T] {
let me = mem::replace(self, LazilySorted::Unsorted(vec![]));
let items = match me {
LazilySorted::Sorted(items, ..) => items,
LazilySorted::Unsorted(mut items) => {
let _observer = O::default();
items.sort_unstable_by(F::compare);
items
}
};
*self = LazilySorted::Sorted(items, PhantomData, PhantomData);
unwrap(self.sorted())
}
#[inline]
fn unsorted(&mut self) -> Option<&mut Vec<T>> {
match *self {
LazilySorted::Unsorted(ref mut items) => Some(items),
LazilySorted::Sorted(..) => None,
}
}
#[inline]
fn sorted(&self) -> Option<&[T]> {
match *self {
LazilySorted::Sorted(ref items, ..) => Some(items),
LazilySorted::Unsorted(_) => None,
}
}
#[inline]
fn is_empty(&self) -> bool {
match *self {
LazilySorted::Sorted(ref items, ..) |
LazilySorted::Unsorted(ref items) => items.is_empty()
}
}
}
/// A parsed set of mappings that can be queried.
///
/// Constructed via `parse_mappings`.
#[derive(Debug)]
pub struct Mappings<O = ()>
where
O: Observer
{
by_generated: Vec<Mapping>,
computed_column_spans: bool,
observer: PhantomData<O>,
// The `by_original` field maps source index to mappings within that
// original source. This lets us essentially do bucket sort on a per-source
// basis, and also enables lazily sorting different source's mappings.
by_original: Option<Vec<LazilySorted<Mapping, comparators::ByOriginalLocationSameSource, O::SortByOriginalLocation>>>,
}
#[cfg(debug_assertions)]
fn unwrap<T>(o: Option<T>) -> T {
o.unwrap()
}
#[cfg(not(debug_assertions))]
#[inline]
fn unwrap<T>(o: Option<T>) -> T {
use std::process;
match o {
Some(t) => t,
None => process::abort(),
}
}
impl<O: Observer> Mappings<O> {
/// Get the full set of mappings, ordered by generated location.
#[inline]
pub fn by_generated_location(&self) -> &[Mapping] {
&self.by_generated
}
/// Compute the last generated column of each mapping.
///
/// After this method has been called, any mappings with
/// `last_generated_column == None` means that the mapping spans to the end
/// of the line.
#[inline]
pub fn compute_column_spans(&mut self) {
if self.computed_column_spans {
return;
}
self.compute_column_spans_slow_path();
}
#[inline(never)]
fn compute_column_spans_slow_path(&mut self) {
debug_assert!(!self.computed_column_spans);
let _observer = O::ComputeColumnSpans::default();
let mut by_generated = self.by_generated.iter_mut().peekable();
while let Some(this_mapping) = by_generated.next() {
if let Some(next_mapping) = by_generated.peek() {
if this_mapping.generated_line == next_mapping.generated_line {
this_mapping.last_generated_column = Some(next_mapping.generated_column);
}
}
}
self.computed_column_spans = true;
}
#[inline]
fn source_buckets(&mut self) -> &mut [LazilySorted<Mapping, comparators::ByOriginalLocationSameSource, O::SortByOriginalLocation>] {
if let Some(ref mut buckets) = self.by_original {
return buckets;
}
self.source_buckets_slow_path()
}
#[inline(never)]
fn source_buckets_slow_path(&mut self) -> &mut [LazilySorted<Mapping, comparators::ByOriginalLocationSameSource, O::SortByOriginalLocation>] {
debug_assert!(self.by_original.is_none());
self.compute_column_spans();
let _observer = O::SortByOriginalLocation::default();
let mut originals = vec![];
for m in self.by_generated.iter().filter(|m| m.original.is_some()) {
let source = unwrap(m.original.as_ref()).source as usize;
while originals.len() <= source {
originals.push(LazilySorted::Unsorted(vec![]));
}
unwrap(originals[source].unsorted()).push(m.clone());
}
self.by_original = Some(originals);
unwrap(self.by_original.as_mut().map(|x| &mut x[..]))
}
/// Get the set of mappings that have original location information for the
/// given source and ordered by original location.
#[inline]
pub fn by_original_source(&mut self, source: u32) -> &[Mapping] {
if let Some(ms) = self.source_buckets().get_mut(source as usize) {
ms.sort()
} else {
&[]
}
}
/// Iterate over all mappings that contain original location information,
/// sorted by their original location information.
#[inline]
pub fn by_original_location(&mut self) -> ByOriginalLocation<'_, O::SortByOriginalLocation> {
ByOriginalLocation {
buckets: self.source_buckets().iter_mut(),
this_bucket: [].iter(),
}
}
/// Get the mapping closest to the given generated location, if any exists.
pub fn original_location_for(
&self,
generated_line: u32,
generated_column: u32,
bias: Bias,
) -> Option<&Mapping> {
let _observer = O::OriginalLocationFor::default();
let by_generated = self.by_generated_location();
let position = by_generated.binary_search_by(|m| {
m.generated_line
.cmp(&generated_line)
.then(m.generated_column.cmp(&generated_column))
});
match position {
Ok(idx) => Some(&by_generated[idx]),
Err(idx) => match bias {
Bias::LeastUpperBound => by_generated.get(idx),
Bias::GreatestLowerBound => if idx == 0 {
None
} else {
by_generated.get(idx - 1)
},
},
}
}
/// Get the mapping closest to the given original location, if any exists.
pub fn generated_location_for(
&mut self,
source: u32,
original_line: u32,
original_column: u32,
bias: Bias,
) -> Option<&Mapping> {
let _observer = O::GeneratedLocationFor::default();
let position = {
let by_original = self.by_original_source(source);
by_original.binary_search_by(|m| {
let original = unwrap(m.original.as_ref());
original
.source
.cmp(&source)
.then(original.original_line.cmp(&original_line))
.then(original.original_column.cmp(&original_column))
})
};
let idx = match position {
Ok(idx) => return Some(&self.by_original_source(source)[idx]),
Err(idx) => idx,
};
match bias {
Bias::LeastUpperBound => if idx == self.by_original_source(source).len() {
// Slide down to the next source's set of mappings.
let mut source = source + 1;
while unwrap(self.by_original.as_ref())
.get(source as usize)
.map_or(false, |b| b.is_empty())
{
source += 1;
}
unwrap(self.by_original.as_mut())
.get_mut(source as usize)
.and_then(|ms| ms.sort().first())
} else {
self.by_original_source(source).get(idx)
},
Bias::GreatestLowerBound => if idx == 0 {
if source == 0 {
return None;
}
// Slide up to the previous source's set of mappings.
let mut source = source - 1;
while source > 0 && unwrap(self.by_original.as_ref())
.get(source as usize)
.map_or(false, |b| b.is_empty())
{
source -= 1;
}
unwrap(self.by_original.as_mut())
.get_mut(source as usize)
.and_then(|ms| ms.sort().first())
} else {
self.by_original_source(source).get(idx - 1)
},
}
}
/// Get all mappings at the given original location.
///
/// If `original_column` is `None`, get all mappings on the given source and
/// original line regardless what columns they have. If `original_column` is
/// `Some`, only return mappings for which all of source, original line, and
/// original column match.
pub fn all_generated_locations_for(
&mut self,
source: u32,
original_line: u32,
original_column: Option<u32>,
) -> AllGeneratedLocationsFor<'_> {
let _observer = O::AllGeneratedLocationsFor::default();
let query_column = original_column.unwrap_or(0);
let by_original = self.by_original_source(source);
let compare = |m: &Mapping| {
let original: &OriginalLocation = unwrap(m.original.as_ref());
debug_assert_eq!(unwrap(m.original.as_ref()).source, source);
original.original_line.cmp(&original_line)
.then(original.original_column.cmp(&query_column))
};
let idx = by_original.binary_search_by(&compare);
let mut idx = match idx {
Ok(idx) | Err(idx) => idx,
};
// If there are multiple mappings for this original location, the binary
// search gives no guarantees that this is the index for the first of
// them, so back up to the first.
while idx > 0 && compare(&by_original[idx - 1]) == cmp::Ordering::Equal {
idx -= 1;
}
let (mappings, original_line, original_column) = if idx < by_original.len() {
let orig = unwrap(by_original[idx].original.as_ref());
let mappings = by_original[idx..].iter();
// Fuzzy line matching only happens when we don't have a column.
let original_line = if original_column.is_some() {
original_line
} else {
orig.original_line
};
let original_column = if original_column.is_some() {
Some(orig.original_column)
} else {
None
};
(mappings, original_line, original_column)
} else {
([].iter(), original_line, original_column)
};
AllGeneratedLocationsFor {
mappings,
original_line,
original_column,
}
}
}
impl<O: Observer> Default for Mappings<O> {
#[inline]
fn default() -> Mappings<O> {
Mappings {
by_generated: vec![],
by_original: None,
computed_column_spans: false,
observer: PhantomData,
}
}
}
/// An iterator returned by `Mappings::by_original_location`.
#[derive(Debug)]
pub struct ByOriginalLocation<'a, O: 'a> {
buckets: slice::IterMut<'a, LazilySorted<Mapping, comparators::ByOriginalLocationSameSource, O>>,
this_bucket: slice::Iter<'a, Mapping>,
}
impl<'a, O: 'a + Default> Iterator for ByOriginalLocation<'a, O> {
type Item = &'a Mapping;
#[inline]
fn next(&mut self) -> Option<Self::Item> {
loop {
if let Some(m) = self.this_bucket.next() {
return Some(m);
}
if let Some(b) = self.buckets.next() {
self.this_bucket = b.sort().iter();
continue;
}
return None;
}
}
}
/// An iterator returned by `Mappings::all_generated_locations_for`.
#[derive(Debug)]
pub struct AllGeneratedLocationsFor<'a> {
mappings: slice::Iter<'a, Mapping>,
original_line: u32,
original_column: Option<u32>,
}
impl<'a> Iterator for AllGeneratedLocationsFor<'a> {
type Item = &'a Mapping;
#[inline]
fn next(&mut self) -> Option<Self::Item> {
match self.mappings.next() {
None => None,
Some(m) => {
let m_orig = unwrap(m.original.as_ref());
if m_orig.original_line != self.original_line {
return None;
}
if let Some(original_column) = self.original_column {
if m_orig.original_column != original_column {
return None;
}
}
Some(m)
}
}
}
}
/// A single bidirectional mapping.
///
/// Always contains generated location information.
///
/// Might contain original location information, and if so, might also have an
/// associated name.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Mapping {
/// The generated line.
pub generated_line: u32,
/// The generated column.
pub generated_column: u32,
/// The end column of this mapping's generated location span.
///
/// Before `Mappings::computed_column_spans` has been called, this is always
/// `None`. After `Mappings::computed_column_spans` has been called, it
/// either contains `Some` column at which the generated location ends
/// (exclusive), or it contains `None` if it spans until the end of the
/// generated line.
pub last_generated_column: Option<u32>,
/// The original location information, if any.
pub original: Option<OriginalLocation>,
}
impl Default for Mapping {
#[inline]
fn default() -> Mapping {
Mapping {
generated_line: 0,
generated_column: 0,
last_generated_column: None,
original: None,
}
}
}
/// Original location information within a mapping.
///
/// Contains a source filename, an original line, and an original column. Might
/// also contain an associated name.
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct OriginalLocation {
/// The source filename.
pub source: u32,
/// The original line.
pub original_line: u32,
/// The original column.
pub original_column: u32,
/// The associated name, if any.
pub name: Option<u32>,
}
#[inline]
fn is_mapping_separator(byte: u8) -> bool {
byte == b';' || byte == b','
}
#[inline]
fn read_relative_vlq<B>(previous: &mut u32, input: &mut B) -> Result<(), Error>
where
B: Iterator<Item = u8>,
{
let decoded = vlq::decode(input)?;
let (new, overflowed) = (*previous as i64).overflowing_add(decoded);
if overflowed || new > (u32::MAX as i64) {
return Err(Error::UnexpectedlyBigNumber);
}
if new < 0 {
return Err(Error::UnexpectedNegativeNumber);
}
*previous = new as u32;
Ok(())
}
/// Parse a source map's `"mappings"` string into a queryable `Mappings`
/// structure.
pub fn parse_mappings<O: Observer>(input: &[u8]) -> Result<Mappings<O>, Error> {
let _observer = O::ParseMappings::default();
let mut generated_line = 0;
let mut generated_column = 0;
let mut original_line = 0;
let mut original_column = 0;
let mut source = 0;
let mut name = 0;
let mut generated_line_start_index = 0;
let mut mappings = Mappings::default();
// `input.len() / 2` is the upper bound on how many mappings the string
// might contain. There would be some sequence like `A,A,A,...` or
// `A;A;A;...`.
let mut by_generated = Vec::with_capacity(input.len() / 2);
let mut input = input.iter().cloned().peekable();
while let Some(byte) = input.peek().cloned() {
match byte {
b';' => {
generated_line += 1;
generated_column = 0;
unwrap(input.next());
// Because mappings are sorted with regards to generated line
// due to the encoding format, and sorting by generated location
// starts by comparing generated line, we can sort only the
// smaller subsequence of this generated line's mappings and end
// up with a fully sorted array.
if generated_line_start_index < by_generated.len() {
let _observer = O::SortByGeneratedLocation::default();
by_generated[generated_line_start_index..].sort_unstable_by(comparators::ByGeneratedTail::compare);
generated_line_start_index = by_generated.len();
}
}
b',' => {
unwrap(input.next());
}
_ => {
let mut mapping = Mapping::default();
mapping.generated_line = generated_line;
// First is a generated column that is always present.
read_relative_vlq(&mut generated_column, &mut input)?;
mapping.generated_column = generated_column as u32;
// Read source, original line, and original column if the
// mapping has them.
mapping.original = if input.peek().cloned().map_or(true, is_mapping_separator) {
None
} else {
read_relative_vlq(&mut source, &mut input)?;
read_relative_vlq(&mut original_line, &mut input)?;
read_relative_vlq(&mut original_column, &mut input)?;
Some(OriginalLocation {
source: source,
original_line: original_line,
original_column: original_column,
name: if input.peek().cloned().map_or(true, is_mapping_separator) {
None
} else {
read_relative_vlq(&mut name, &mut input)?;
Some(name)
},
})
};
by_generated.push(mapping);
}
}
}
if generated_line_start_index < by_generated.len() {
let _observer = O::SortByGeneratedLocation::default();
by_generated[generated_line_start_index..].sort_unstable_by(comparators::ByGeneratedTail::compare);
}
mappings.by_generated = by_generated;
Ok(mappings)
}