1#![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#[derive(Copy, Clone, Debug)]
62#[repr(u32)]
63pub enum Error {
64 UnexpectedNegativeNumber = 1,
68
69 UnexpectedlyBigNumber = 2,
71
72 VlqUnexpectedEof = 3,
74
75 VlqInvalidBase64 = 4,
77
78 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#[derive(Copy, Clone, Debug, PartialEq, Eq)]
97#[repr(u32)]
98pub enum Bias {
99 GreatestLowerBound = 1,
103
104 LeastUpperBound = 2,
106}
107
108impl Default for Bias {
109 #[inline]
110 fn default() -> Bias {
111 Bias::GreatestLowerBound
112 }
113}
114
115pub trait Observer: Default {
122 type ParseMappings: Default;
124
125 type SortByOriginalLocation: Default;
127
128 type SortByGeneratedLocation: Default;
130
131 type ComputeColumnSpans: Default;
133
134 type OriginalLocationFor: Default;
137
138 type GeneratedLocationFor: Default;
141
142 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#[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 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 #[inline]
244 pub fn by_generated_location(&self) -> &[Mapping] {
245 &self.by_generated
246 }
247
248 #[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 #[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 #[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 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 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 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 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 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 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 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#[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#[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#[derive(Clone, Debug, PartialEq, Eq)]
573pub struct Mapping {
574 pub generated_line: u32,
576
577 pub generated_column: u32,
579
580 pub last_generated_column: Option<u32>,
588
589 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#[derive(Clone, Debug, PartialEq, Eq)]
610pub struct OriginalLocation {
611 pub source: u32,
613
614 pub original_line: u32,
616
617 pub original_column: u32,
619
620 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
648pub 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 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 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 read_relative_vlq(&mut generated_column, &mut input)?;
697 mapping.generated_column = generated_column as u32;
698
699 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}