source_map_mappings/
lib.rs

1/*!
2
3[![](https://docs.rs/source-map-mappings/badge.svg)](https://docs.rs/source-map-mappings/) [![](https://img.shields.io/crates/v/source-map-mappings.svg)](https://crates.io/crates/source-map-mappings) [![](https://img.shields.io/crates/d/source-map-mappings.png)](https://crates.io/crates/source-map-mappings) [![Build Status](https://travis-ci.org/fitzgen/source-map-mappings.png?branch=master)](https://travis-ci.org/fitzgen/source-map-mappings)
4
5Parse the `"mappings"` string from a source map.
6
7This is intended to be compiled to WebAssembly and eventually used from the
8[`mozilla/source-map`][source-map] library. This is **not** a general purpose
9source maps library.
10
11[source-map]: https://github.com/mozilla/source-map
12
13* [Documentation](#documentation)
14* [License](#license)
15* [Contributing](#contributing)
16
17## Documentation
18
19[📚 Documentation on `docs.rs` 📚][docs]
20
21[docs]: https://docs.rs/source-map-mappings
22
23## License
24
25Licensed under either of
26
27 * [Apache License, Version 2.0](http://www.apache.org/licenses/LICENSE-2.0)
28
29 * [MIT license](http://opensource.org/licenses/MIT)
30
31at your option.
32
33## Contributing
34
35See
36[CONTRIBUTING.md](https://github.com/fitzgen/source-map-mappings/blob/master/CONTRIBUTING.md)
37for hacking.
38
39Unless you explicitly state otherwise, any contribution intentionally submitted
40for inclusion in the work by you, as defined in the Apache-2.0 license, shall be
41dual licensed as above, without any additional terms or conditions.
42
43 */
44
45#![deny(missing_debug_implementations)]
46#![deny(missing_docs)]
47
48extern crate rand;
49extern crate vlq;
50
51pub mod comparators;
52
53use comparators::ComparatorFunction;
54use std::cmp;
55use std::marker::PhantomData;
56use std::mem;
57use std::slice;
58use std::u32;
59
60/// Errors that can occur during parsing.
61#[derive(Copy, Clone, Debug)]
62#[repr(u32)]
63pub enum Error {
64    // NB: 0 is reserved for OK.
65    /// The mappings contained a negative line, column, source index, or name
66    /// index.
67    UnexpectedNegativeNumber = 1,
68
69    /// The mappings contained a number larger than `u32::MAX`.
70    UnexpectedlyBigNumber = 2,
71
72    /// Reached EOF while in the middle of parsing a VLQ.
73    VlqUnexpectedEof = 3,
74
75    /// Encountered an invalid base 64 character while parsing a VLQ.
76    VlqInvalidBase64 = 4,
77
78    /// VLQ encountered a number that, when decoded, would not fit in
79    /// an i64.
80    VlqOverflow = 5,
81}
82
83impl From<vlq::Error> for Error {
84    #[inline]
85    fn from(e: vlq::Error) -> Error {
86        match e {
87            vlq::Error::UnexpectedEof => Error::VlqUnexpectedEof,
88            vlq::Error::InvalidBase64(_) => Error::VlqInvalidBase64,
89            vlq::Error::Overflow => Error::VlqOverflow,
90        }
91    }
92}
93
94/// When doing fuzzy searching, whether to slide the next larger or next smaller
95/// mapping from the queried location.
96#[derive(Copy, Clone, Debug, PartialEq, Eq)]
97#[repr(u32)]
98pub enum Bias {
99    // XXX: make sure these values always match `mozilla/source-map`'s
100    // `SourceMapConsumer.{GreatestLower,LeastUpper}Bound` values!
101    /// Slide to the next smaller mapping.
102    GreatestLowerBound = 1,
103
104    /// Slide to the next larger mapping.
105    LeastUpperBound = 2,
106}
107
108impl Default for Bias {
109    #[inline]
110    fn default() -> Bias {
111        Bias::GreatestLowerBound
112    }
113}
114
115/// A trait for defining a set of RAII types that can observe the start and end
116/// of various operations and queries we perform in their constructors and
117/// destructors.
118///
119/// This is also implemented for `()` as the "null observer" that doesn't
120/// actually do anything.
121pub trait Observer: Default {
122    /// Observe the parsing of the `"mappings"` string.
123    type ParseMappings: Default;
124
125    /// Observe sorting parsed mappings by original location.
126    type SortByOriginalLocation: Default;
127
128    /// Observe sorting parsed mappings by generated location.
129    type SortByGeneratedLocation: Default;
130
131    /// Observe computing column spans.
132    type ComputeColumnSpans: Default;
133
134    /// Observe querying what the original location for some generated location
135    /// is.
136    type OriginalLocationFor: Default;
137
138    /// Observe querying what the generated location for some original location
139    /// is.
140    type GeneratedLocationFor: Default;
141
142    /// Observe querying what all generated locations for some original location
143    /// is.
144    type AllGeneratedLocationsFor: Default;
145}
146
147impl Observer for () {
148    type ParseMappings = ();
149    type SortByOriginalLocation = ();
150    type SortByGeneratedLocation = ();
151    type ComputeColumnSpans = ();
152    type OriginalLocationFor = ();
153    type GeneratedLocationFor = ();
154    type AllGeneratedLocationsFor = ();
155}
156
157#[derive(Debug)]
158enum LazilySorted<T, F, O> {
159    Sorted(Vec<T>, PhantomData<F>, PhantomData<O>),
160    Unsorted(Vec<T>),
161}
162
163impl<T, F, O> LazilySorted<T, F, O>
164where
165    F: comparators::ComparatorFunction<T>,
166    O: Default,
167{
168    #[inline]
169    fn sort(&mut self) -> &[T] {
170        let me = mem::replace(self, LazilySorted::Unsorted(vec![]));
171        let items = match me {
172            LazilySorted::Sorted(items, ..) => items,
173            LazilySorted::Unsorted(mut items) => {
174                let _observer = O::default();
175                items.sort_unstable_by(F::compare);
176                items
177            }
178        };
179        mem::replace(self, LazilySorted::Sorted(items, PhantomData, PhantomData));
180        unwrap(self.sorted())
181    }
182
183    #[inline]
184    fn unsorted(&mut self) -> Option<&mut Vec<T>> {
185        match *self {
186            LazilySorted::Unsorted(ref mut items) => Some(items),
187            LazilySorted::Sorted(..) => None,
188        }
189    }
190
191    #[inline]
192    fn sorted(&self) -> Option<&[T]> {
193        match *self {
194            LazilySorted::Sorted(ref items, ..) => Some(items),
195            LazilySorted::Unsorted(_) => None,
196        }
197    }
198
199    #[inline]
200    fn is_empty(&self) -> bool {
201        match *self {
202            LazilySorted::Sorted(ref items, ..) |
203            LazilySorted::Unsorted(ref items) => items.is_empty()
204        }
205    }
206}
207
208/// A parsed set of mappings that can be queried.
209///
210/// Constructed via `parse_mappings`.
211#[derive(Debug)]
212pub struct Mappings<O = ()>
213where
214    O: Observer
215{
216    by_generated: Vec<Mapping>,
217    computed_column_spans: bool,
218    observer: O,
219
220    // The `by_original` field maps source index to mappings within that
221    // original source. This lets us essentially do bucket sort on a per-source
222    // basis, and also enables lazily sorting different source's mappings.
223    by_original: Option<Vec<LazilySorted<Mapping, comparators::ByOriginalLocationSameSource, O::SortByOriginalLocation>>>,
224}
225
226#[cfg(debug_assertions)]
227fn unwrap<T>(o: Option<T>) -> T {
228    o.unwrap()
229}
230
231#[cfg(not(debug_assertions))]
232#[inline]
233fn unwrap<T>(o: Option<T>) -> T {
234    use std::process;
235    match o {
236        Some(t) => t,
237        None => process::abort(),
238    }
239}
240
241impl<O: Observer> Mappings<O> {
242    /// Get the full set of mappings, ordered by generated location.
243    #[inline]
244    pub fn by_generated_location(&self) -> &[Mapping] {
245        &self.by_generated
246    }
247
248    /// Compute the last generated column of each mapping.
249    ///
250    /// After this method has been called, any mappings with
251    /// `last_generated_column == None` means that the mapping spans to the end
252    /// of the line.
253    #[inline]
254    pub fn compute_column_spans(&mut self) {
255        if self.computed_column_spans {
256            return;
257        }
258        self.compute_column_spans_slow_path();
259    }
260
261    #[inline(never)]
262    fn compute_column_spans_slow_path(&mut self) {
263        debug_assert!(!self.computed_column_spans);
264
265        let _observer = O::ComputeColumnSpans::default();
266
267        let mut by_generated = self.by_generated.iter_mut().peekable();
268        while let Some(this_mapping) = by_generated.next() {
269            if let Some(next_mapping) = by_generated.peek() {
270                if this_mapping.generated_line == next_mapping.generated_line {
271                    this_mapping.last_generated_column = Some(next_mapping.generated_column);
272                }
273            }
274        }
275
276        self.computed_column_spans = true;
277    }
278
279    #[inline]
280    fn source_buckets(&mut self) -> &mut [LazilySorted<Mapping, comparators::ByOriginalLocationSameSource, O::SortByOriginalLocation>] {
281        if let Some(ref mut buckets) = self.by_original {
282            return buckets;
283        }
284        self.source_buckets_slow_path()
285    }
286
287    #[inline(never)]
288    fn source_buckets_slow_path(&mut self) -> &mut [LazilySorted<Mapping, comparators::ByOriginalLocationSameSource, O::SortByOriginalLocation>] {
289        debug_assert!(self.by_original.is_none());
290
291        self.compute_column_spans();
292
293        let _observer = O::SortByOriginalLocation::default();
294
295        let mut originals = vec![];
296        for m in self.by_generated.iter().filter(|m| m.original.is_some()) {
297            let source = unwrap(m.original.as_ref()).source as usize;
298            while originals.len() <= source {
299                originals.push(LazilySorted::Unsorted(vec![]));
300            }
301            unwrap(originals[source].unsorted()).push(m.clone());
302        }
303
304        self.by_original = Some(originals);
305        unwrap(self.by_original.as_mut().map(|x| &mut x[..]))
306    }
307
308    /// Get the set of mappings that have original location information for the
309    /// given source and ordered by original location.
310    #[inline]
311    pub fn by_original_source(&mut self, source: u32) -> &[Mapping] {
312        if let Some(ms) = self.source_buckets().get_mut(source as usize) {
313            ms.sort()
314        } else {
315            &[]
316        }
317    }
318
319    /// Iterate over all mappings that contain original location information,
320    /// sorted by their original location information.
321    #[inline]
322    pub fn by_original_location(&mut self) -> ByOriginalLocation<O::SortByOriginalLocation> {
323        ByOriginalLocation {
324            buckets: self.source_buckets().iter_mut(),
325            this_bucket: [].iter(),
326        }
327    }
328
329    /// Get the mapping closest to the given generated location, if any exists.
330    pub fn original_location_for(
331        &self,
332        generated_line: u32,
333        generated_column: u32,
334        bias: Bias,
335    ) -> Option<&Mapping> {
336        let _observer = O::OriginalLocationFor::default();
337
338        let by_generated = self.by_generated_location();
339
340        let position = by_generated.binary_search_by(|m| {
341            m.generated_line
342                .cmp(&generated_line)
343                .then(m.generated_column.cmp(&generated_column))
344        });
345
346        match position {
347            Ok(idx) => Some(&by_generated[idx]),
348            Err(idx) => match bias {
349                Bias::LeastUpperBound => by_generated.get(idx),
350                Bias::GreatestLowerBound => if idx == 0 {
351                    None
352                } else {
353                    by_generated.get(idx - 1)
354                },
355            },
356        }
357    }
358
359    /// Get the mapping closest to the given original location, if any exists.
360    pub fn generated_location_for(
361        &mut self,
362        source: u32,
363        original_line: u32,
364        original_column: u32,
365        bias: Bias,
366    ) -> Option<&Mapping> {
367        let _observer = O::GeneratedLocationFor::default();
368
369        let position = {
370            let by_original = self.by_original_source(source);
371
372            by_original.binary_search_by(|m| {
373                let original = unwrap(m.original.as_ref());
374                original
375                    .source
376                    .cmp(&source)
377                    .then(original.original_line.cmp(&original_line))
378                    .then(original.original_column.cmp(&original_column))
379            })
380        };
381
382        let idx = match position {
383            Ok(idx) => return Some(&self.by_original_source(source)[idx]),
384            Err(idx) => idx,
385        };
386
387        match bias {
388            Bias::LeastUpperBound => if idx == self.by_original_source(source).len() {
389                // Slide down to the next source's set of mappings.
390                let mut source = source + 1;
391                while unwrap(self.by_original.as_ref())
392                    .get(source as usize)
393                    .map_or(false, |b| b.is_empty())
394                {
395                    source += 1;
396                }
397                unwrap(self.by_original.as_mut())
398                    .get_mut(source as usize)
399                    .and_then(|ms| ms.sort().first())
400            } else {
401                self.by_original_source(source).get(idx)
402            },
403
404            Bias::GreatestLowerBound => if idx == 0 {
405                if source == 0 {
406                    return None;
407                }
408
409                // Slide up to the previous source's set of mappings.
410                let mut source = source - 1;
411                while source > 0 && unwrap(self.by_original.as_ref())
412                    .get(source as usize)
413                    .map_or(false, |b| b.is_empty())
414                {
415                    source -= 1;
416                }
417                unwrap(self.by_original.as_mut())
418                    .get_mut(source as usize)
419                    .and_then(|ms| ms.sort().first())
420            } else {
421                self.by_original_source(source).get(idx - 1)
422            },
423        }
424    }
425
426    /// Get all mappings at the given original location.
427    ///
428    /// If `original_column` is `None`, get all mappings on the given source and
429    /// original line regardless what columns they have. If `original_column` is
430    /// `Some`, only return mappings for which all of source, original line, and
431    /// original column match.
432    pub fn all_generated_locations_for(
433        &mut self,
434        source: u32,
435        original_line: u32,
436        original_column: Option<u32>,
437    ) -> AllGeneratedLocationsFor {
438        let _observer = O::AllGeneratedLocationsFor::default();
439
440        let query_column = original_column.unwrap_or(0);
441
442        let by_original = self.by_original_source(source);
443
444        let compare = |m: &Mapping| {
445            let original: &OriginalLocation = unwrap(m.original.as_ref());
446            debug_assert_eq!(unwrap(m.original.as_ref()).source, source);
447            original.original_line.cmp(&original_line)
448                .then(original.original_column.cmp(&query_column))
449        };
450
451        let idx = by_original.binary_search_by(&compare);
452        let mut idx = match idx {
453            Ok(idx) | Err(idx) => idx,
454        };
455
456        // If there are multiple mappings for this original location, the binary
457        // search gives no guarantees that this is the index for the first of
458        // them, so back up to the first.
459        while idx > 0 && compare(&by_original[idx - 1]) == cmp::Ordering::Equal {
460            idx -= 1;
461        }
462
463        let (mappings, original_line, original_column) = if idx < by_original.len() {
464            let orig = unwrap(by_original[idx].original.as_ref());
465            let mappings = by_original[idx..].iter();
466
467            // Fuzzy line matching only happens when we don't have a column.
468            let original_line = if original_column.is_some() {
469                original_line
470            } else {
471                orig.original_line
472            };
473
474            let original_column = if original_column.is_some() {
475                Some(orig.original_column)
476            } else {
477                None
478            };
479
480            (mappings, original_line, original_column)
481        } else {
482            ([].iter(), original_line, original_column)
483        };
484
485        AllGeneratedLocationsFor {
486            mappings,
487            original_line,
488            original_column,
489        }
490    }
491}
492
493impl<O: Observer> Default for Mappings<O> {
494    #[inline]
495    fn default() -> Mappings<O> {
496        Mappings {
497            by_generated: vec![],
498            by_original: None,
499            computed_column_spans: false,
500            observer: Default::default(),
501        }
502    }
503}
504
505/// An iterator returned by `Mappings::by_original_location`.
506#[derive(Debug)]
507pub struct ByOriginalLocation<'a, O: 'a> {
508    buckets: slice::IterMut<'a, LazilySorted<Mapping, comparators::ByOriginalLocationSameSource, O>>,
509    this_bucket: slice::Iter<'a, Mapping>,
510}
511
512impl<'a, O: 'a + Default> Iterator for ByOriginalLocation<'a, O> {
513    type Item = &'a Mapping;
514
515    #[inline]
516    fn next(&mut self) -> Option<Self::Item> {
517        loop {
518            if let Some(m) = self.this_bucket.next() {
519                return Some(m);
520            }
521
522            if let Some(b) = self.buckets.next() {
523                self.this_bucket = b.sort().iter();
524                continue;
525            }
526
527            return None;
528        }
529    }
530}
531
532/// An iterator returned by `Mappings::all_generated_locations_for`.
533#[derive(Debug)]
534pub struct AllGeneratedLocationsFor<'a> {
535    mappings: slice::Iter<'a, Mapping>,
536    original_line: u32,
537    original_column: Option<u32>,
538}
539
540impl<'a> Iterator for AllGeneratedLocationsFor<'a> {
541    type Item = &'a Mapping;
542
543    #[inline]
544    fn next(&mut self) -> Option<Self::Item> {
545        match self.mappings.next() {
546            None => None,
547            Some(m) => {
548                let m_orig = unwrap(m.original.as_ref());
549
550                if m_orig.original_line != self.original_line {
551                    return None;
552                }
553
554                if let Some(original_column) = self.original_column {
555                    if m_orig.original_column != original_column {
556                        return None;
557                    }
558                }
559
560                Some(m)
561            }
562        }
563    }
564}
565
566/// A single bidirectional mapping.
567///
568/// Always contains generated location information.
569///
570/// Might contain original location information, and if so, might also have an
571/// associated name.
572#[derive(Clone, Debug, PartialEq, Eq)]
573pub struct Mapping {
574    /// The generated line.
575    pub generated_line: u32,
576
577    /// The generated column.
578    pub generated_column: u32,
579
580    /// The end column of this mapping's generated location span.
581    ///
582    /// Before `Mappings::computed_column_spans` has been called, this is always
583    /// `None`. After `Mappings::computed_column_spans` has been called, it
584    /// either contains `Some` column at which the generated location ends
585    /// (exclusive), or it contains `None` if it spans until the end of the
586    /// generated line.
587    pub last_generated_column: Option<u32>,
588
589    /// The original location information, if any.
590    pub original: Option<OriginalLocation>,
591}
592
593impl Default for Mapping {
594    #[inline]
595    fn default() -> Mapping {
596        Mapping {
597            generated_line: 0,
598            generated_column: 0,
599            last_generated_column: None,
600            original: None,
601        }
602    }
603}
604
605/// Original location information within a mapping.
606///
607/// Contains a source filename, an original line, and an original column. Might
608/// also contain an associated name.
609#[derive(Clone, Debug, PartialEq, Eq)]
610pub struct OriginalLocation {
611    /// The source filename.
612    pub source: u32,
613
614    /// The original line.
615    pub original_line: u32,
616
617    /// The original column.
618    pub original_column: u32,
619
620    /// The associated name, if any.
621    pub name: Option<u32>,
622}
623
624#[inline]
625fn is_mapping_separator(byte: u8) -> bool {
626    byte == b';' || byte == b','
627}
628
629#[inline]
630fn read_relative_vlq<B>(previous: &mut u32, input: &mut B) -> Result<(), Error>
631where
632    B: Iterator<Item = u8>,
633{
634    let decoded = vlq::decode(input)?;
635    let (new, overflowed) = (*previous as i64).overflowing_add(decoded);
636    if overflowed || new > (u32::MAX as i64) {
637        return Err(Error::UnexpectedlyBigNumber);
638    }
639
640    if new < 0 {
641        return Err(Error::UnexpectedNegativeNumber);
642    }
643
644    *previous = new as u32;
645    Ok(())
646}
647
648/// Parse a source map's `"mappings"` string into a queryable `Mappings`
649/// structure.
650pub fn parse_mappings<O: Observer>(input: &[u8]) -> Result<Mappings<O>, Error> {
651    let _observer = O::ParseMappings::default();
652
653    let mut generated_line = 0;
654    let mut generated_column = 0;
655    let mut original_line = 0;
656    let mut original_column = 0;
657    let mut source = 0;
658    let mut name = 0;
659    let mut generated_line_start_index = 0;
660
661    let mut mappings = Mappings::default();
662
663    // `input.len() / 2` is the upper bound on how many mappings the string
664    // might contain. There would be some sequence like `A,A,A,...` or
665    // `A;A;A;...`.
666    let mut by_generated = Vec::with_capacity(input.len() / 2);
667
668    let mut input = input.iter().cloned().peekable();
669
670    while let Some(byte) = input.peek().cloned() {
671        match byte {
672            b';' => {
673                generated_line += 1;
674                generated_column = 0;
675                unwrap(input.next());
676
677                // Because mappings are sorted with regards to generated line
678                // due to the encoding format, and sorting by generated location
679                // starts by comparing generated line, we can sort only the
680                // smaller subsequence of this generated line's mappings and end
681                // up with a fully sorted array.
682                if generated_line_start_index < by_generated.len() {
683                    let _observer = O::SortByGeneratedLocation::default();
684                    by_generated[generated_line_start_index..].sort_unstable_by(comparators::ByGeneratedTail::compare);
685                    generated_line_start_index = by_generated.len();
686                }
687            }
688            b',' => {
689                unwrap(input.next());
690            }
691            _ => {
692                let mut mapping = Mapping::default();
693                mapping.generated_line = generated_line;
694
695                // First is a generated column that is always present.
696                read_relative_vlq(&mut generated_column, &mut input)?;
697                mapping.generated_column = generated_column as u32;
698
699                // Read source, original line, and original column if the
700                // mapping has them.
701                mapping.original = if input.peek().cloned().map_or(true, is_mapping_separator) {
702                    None
703                } else {
704                    read_relative_vlq(&mut source, &mut input)?;
705                    read_relative_vlq(&mut original_line, &mut input)?;
706                    read_relative_vlq(&mut original_column, &mut input)?;
707
708                    Some(OriginalLocation {
709                        source: source,
710                        original_line: original_line,
711                        original_column: original_column,
712                        name: if input.peek().cloned().map_or(true, is_mapping_separator) {
713                            None
714                        } else {
715                            read_relative_vlq(&mut name, &mut input)?;
716                            Some(name)
717                        },
718                    })
719                };
720
721                by_generated.push(mapping);
722            }
723        }
724    }
725
726    if generated_line_start_index < by_generated.len() {
727        let _observer = O::SortByGeneratedLocation::default();
728        by_generated[generated_line_start_index..].sort_unstable_by(comparators::ByGeneratedTail::compare);
729    }
730
731    mappings.by_generated = by_generated;
732    Ok(mappings)
733}