1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
/*!

[![](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)

Parse the `"mappings"` string from a source map.

This is intended to be compiled to WebAssembly and eventually used from the
[`mozilla/source-map`][source-map] library. This is **not** a general purpose
source maps library.

[source-map]: https://github.com/mozilla/source-map

* [Documentation](#documentation)
* [License](#license)
* [Contributing](#contributing)

## Documentation

[📚 Documentation on `docs.rs` 📚][docs]

[docs]: https://docs.rs/source-map-mappings

## License

Licensed under either of

 * [Apache License, Version 2.0](http://www.apache.org/licenses/LICENSE-2.0)

 * [MIT license](http://opensource.org/licenses/MIT)

at your option.

## Contributing

See
[CONTRIBUTING.md](https://github.com/fitzgen/source-map-mappings/blob/master/CONTRIBUTING.md)
for hacking.

Unless you explicitly state otherwise, any contribution intentionally submitted
for inclusion in the work by you, as defined in the Apache-2.0 license, shall be
dual licensed as above, without any additional terms or conditions.

 */

#![deny(missing_debug_implementations)]
#![deny(missing_docs)]

extern crate rand;
extern crate vlq;

pub mod comparators;

use comparators::ComparatorFunction;
use std::cmp;
use std::marker::PhantomData;
use std::mem;
use std::slice;
use std::u32;

/// 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
            }
        };
        mem::replace(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: 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: Default::default(),
        }
    }
}

/// 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)
}