lib/parser.dart - source_maps - Git at Google

 // Copyright (c) 2013, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.

 /// Contains the top-level function to parse source maps version 3.
 library source_maps.parser;

 import 'dart:collection';
 import 'dart:convert';

 import 'package:path/path.dart' as path;
 import 'package:source_span/source_span.dart';

 import 'builder.dart' as builder;
 import 'src/source_map_span.dart';
 import 'src/utils.dart';
 import 'src/vlq.dart';

 /// Parses a source map directly from a json string.
 ///
 /// [mapUrl], which may be either a [String] or a [Uri], indicates the URL of
 /// the source map file itself. If it's passed, any URLs in the source
 /// map will be interpreted as relative to this URL when generating spans.
 // TODO(sigmund): evaluate whether other maps should have the json parsed, or
 // the string represenation.
 // TODO(tjblasi): Ignore the first line of [jsonMap] if the JSON safety string
 // `)]}'` begins the string representation of the map.
 Mapping parse(String jsonMap, {Map<String, Map> otherMaps, mapUrl}) =>
     parseJson(JSON.decode(jsonMap), otherMaps: otherMaps, mapUrl: mapUrl);

 /// Parses a source map or source map bundle directly from a json string.
 ///
 /// [mapUrl], which may be either a [String] or a [Uri], indicates the URL of
 /// the source map file itself. If it's passed, any URLs in the source
 /// map will be interpreted as relative to this URL when generating spans.
 Mapping parseExtended(String jsonMap, {Map<String, Map> otherMaps, mapUrl}) =>
     parseJsonExtended(JSON.decode(jsonMap),
         otherMaps: otherMaps, mapUrl: mapUrl);

 /// Parses a source map or source map bundle.
 ///
 /// [mapUrl], which may be either a [String] or a [Uri], indicates the URL of
 /// the source map file itself. If it's passed, any URLs in the source
 /// map will be interpreted as relative to this URL when generating spans.
 Mapping parseJsonExtended(/*List|Map*/ json,
     {Map<String, Map> otherMaps, mapUrl}) {
   if (json is List) {
     return new MappingBundle.fromJson(json, mapUrl: mapUrl);
   }
   return parseJson(json as Map);
 }

 /// Parses a source map
 ///
 /// [mapUrl], which may be either a [String] or a [Uri], indicates the URL of
 /// the source map file itself. If it's passed, any URLs in the source
 /// map will be interpreted as relative to this URL when generating spans.
 Mapping parseJson(Map map, {Map<String, Map> otherMaps, mapUrl}) {
   if (map['version'] != 3) {
     throw new ArgumentError('unexpected source map version: ${map["version"]}. '
         'Only version 3 is supported.');
   }

   if (map.containsKey('sections')) {
     if (map.containsKey('mappings') ||
         map.containsKey('sources') ||
         map.containsKey('names')) {
       throw new FormatException('map containing "sections" '
           'cannot contain "mappings", "sources", or "names".');
     }
     return new MultiSectionMapping.fromJson(map['sections'], otherMaps,
         mapUrl: mapUrl);
   }
   return new SingleMapping.fromJson(map, mapUrl: mapUrl);
 }

 /// A mapping parsed out of a source map.
 abstract class Mapping {
   /// Returns the span associated with [line] and [column].
   ///
   /// [uri] is the optional location of the output file to find the span for
   /// to disambiguate cases where a mapping may have different mappings for
   /// different output files.
   SourceMapSpan spanFor(int line, int column,
       {Map<String, SourceFile> files, String uri});

   /// Returns the span associated with [location].
   SourceMapSpan spanForLocation(SourceLocation location,
       {Map<String, SourceFile> files}) {
     return spanFor(location.line, location.column,
         uri: location.sourceUrl?.toString(), files: files);
   }
 }

 /// A meta-level map containing sections.
 class MultiSectionMapping extends Mapping {
   /// For each section, the start line offset.
   final List<int> _lineStart = <int>[];

   /// For each section, the start column offset.
   final List<int> _columnStart = <int>[];

   /// For each section, the actual source map information, which is not adjusted
   /// for offsets.
   final List<Mapping> _maps = <Mapping>[];

   /// Creates a section mapping from json.
   MultiSectionMapping.fromJson(List sections, Map<String, Map> otherMaps,
       {mapUrl}) {
     for (var section in sections) {
       var offset = section['offset'];
       if (offset == null) throw new FormatException('section missing offset');

       var line = section['offset']['line'];
       if (line == null) throw new FormatException('offset missing line');

       var column = section['offset']['column'];
       if (column == null) throw new FormatException('offset missing column');

       _lineStart.add(line);
       _columnStart.add(column);

       var url = section['url'];
       var map = section['map'];

       if (url != null && map != null) {
         throw new FormatException("section can't use both url and map entries");
       } else if (url != null) {
         if (otherMaps == null || otherMaps[url] == null) {
           throw new FormatException(
               'section contains refers to $url, but no map was '
               'given for it. Make sure a map is passed in "otherMaps"');
         }
         _maps.add(parseJson(otherMaps[url], otherMaps: otherMaps, mapUrl: url));
       } else if (map != null) {
         _maps.add(parseJson(map, otherMaps: otherMaps, mapUrl: mapUrl));
       } else {
         throw new FormatException('section missing url or map');
       }
     }
     if (_lineStart.length == 0) {
       throw new FormatException('expected at least one section');
     }
   }

   int _indexFor(line, column) {
     for (int i = 0; i < _lineStart.length; i++) {
       if (line < _lineStart[i]) return i - 1;
       if (line == _lineStart[i] && column < _columnStart[i]) return i - 1;
     }
     return _lineStart.length - 1;
   }

   SourceMapSpan spanFor(int line, int column,
       {Map<String, SourceFile> files, String uri}) {
     // TODO(jacobr): perhaps verify that targetUrl matches the actual uri
     // or at least ends in the same file name.
     int index = _indexFor(line, column);
     return _maps[index].spanFor(
         line - _lineStart[index], column - _columnStart[index],
         files: files);
   }

   String toString() {
     var buff = new StringBuffer("$runtimeType : [");
     for (int i = 0; i < _lineStart.length; i++) {
       buff
         ..write('(')
         ..write(_lineStart[i])
         ..write(',')
         ..write(_columnStart[i])
         ..write(':')
         ..write(_maps[i])
         ..write(')');
     }
     buff.write(']');
     return buff.toString();
   }
 }

 class MappingBundle extends Mapping {
   Map<String, SingleMapping> _mappings = {};

   MappingBundle.fromJson(List json, {String mapUrl}) {
     for (var map in json) {
       var mapping = parseJson(map, mapUrl: mapUrl) as SingleMapping;
       var targetUrl = mapping.targetUrl;
       _mappings[targetUrl] = mapping;
     }
   }

   /// Encodes the Mapping mappings as a json map.
   List toJson() => _mappings.values.map((v) => v.toJson()).toList();

   String toString() {
     var buff = new StringBuffer();
     for (var map in _mappings.values) {
       buff.write(map.toString());
     }
     return buff.toString();
   }

   SourceMapSpan spanFor(int line, int column,
       {Map<String, SourceFile> files, String uri}) {
     if (uri == null) {
       throw new ArgumentError.notNull('uri');
     }
     if (_mappings.containsKey(uri)) {
       return _mappings[uri].spanFor(line, column, files: files, uri: uri);
     }
     // Fall back to looking up the source map on just the basename.
     var name = path.basename(uri.toString());
     if (_mappings.containsKey(name)) {
       return _mappings[name].spanFor(line, column, files: files, uri: name);
     }

     // Note: when there is no source map for an uri, this behaves like an
     // identity function, returning the requested location as the result.

     // Create a mock offset for the output location. We compute it in terms
     // of the input line and column to minimize the chances that two different
     // line and column locations are mapped to the same offset.
     var offset = line * 1000000 + column;
     var location = new SourceLocation(offset,
         line: line, column: column, sourceUrl: Uri.parse(uri));
     return new SourceMapSpan(location, location, "");
   }
 }

 /// A map containing direct source mappings.
 class SingleMapping extends Mapping {
   /// Source urls used in the mapping, indexed by id.
   final List<String> urls;

   /// Source names used in the mapping, indexed by id.
   final List<String> names;

   /// Entries indicating the beginning of each span.
   final List<TargetLineEntry> lines;

   /// Url of the target file.
   String targetUrl;

   /// Source root prepended to all entries in [urls].
   String sourceRoot;

   final Uri _mapUrl;

   SingleMapping._(this.targetUrl, this.urls, this.names, this.lines)
       : _mapUrl = null;

   factory SingleMapping.fromEntries(Iterable<builder.Entry> entries,
       [String fileUrl]) {
     // The entries needs to be sorted by the target offsets.
     var sourceEntries = new List.from(entries)..sort();
     var lines = <TargetLineEntry>[];

     // Indices associated with file urls that will be part of the source map. We
     // use a linked hash-map so that `_urls.keys[_urls[u]] == u`
     var urls = new LinkedHashMap<String, int>();

     // Indices associated with identifiers that will be part of the source map.
     // We use a linked hash-map so that `_names.keys[_names[n]] == n`
     var names = new LinkedHashMap<String, int>();

     var lineNum;
     List<TargetEntry> targetEntries;
     for (var sourceEntry in sourceEntries) {
       if (lineNum == null || sourceEntry.target.line > lineNum) {
         lineNum = sourceEntry.target.line;
         targetEntries = <TargetEntry>[];
         lines.add(new TargetLineEntry(lineNum, targetEntries));
       }

       if (sourceEntry.source == null) {
         targetEntries.add(new TargetEntry(sourceEntry.target.column));
       } else {
         var sourceUrl = sourceEntry.source.sourceUrl;
         var urlId = urls.putIfAbsent(
             sourceUrl == null ? '' : sourceUrl.toString(), () => urls.length);
         var srcNameId = sourceEntry.identifierName == null
             ? null
             : names.putIfAbsent(sourceEntry.identifierName, () => names.length);
         targetEntries.add(new TargetEntry(sourceEntry.target.column, urlId,
             sourceEntry.source.line, sourceEntry.source.column, srcNameId));
       }
     }
     return new SingleMapping._(
         fileUrl, urls.keys.toList(), names.keys.toList(), lines);
   }

   SingleMapping.fromJson(Map map, {mapUrl})
       : targetUrl = map['file'],
         urls = new List<String>.from(map['sources']),
         names = new List<String>.from(map['names']),
         sourceRoot = map['sourceRoot'],
         lines = <TargetLineEntry>[],
         _mapUrl = mapUrl is String ? Uri.parse(mapUrl) : mapUrl {
     int line = 0;
     int column = 0;
     int srcUrlId = 0;
     int srcLine = 0;
     int srcColumn = 0;
     int srcNameId = 0;
     var tokenizer = new _MappingTokenizer(map['mappings']);
     var entries = <TargetEntry>[];

     while (tokenizer.hasTokens) {
       if (tokenizer.nextKind.isNewLine) {
         if (!entries.isEmpty) {
           lines.add(new TargetLineEntry(line, entries));
           entries = <TargetEntry>[];
         }
         line++;
         column = 0;
         tokenizer._consumeNewLine();
         continue;
       }

       // Decode the next entry, using the previous encountered values to
       // decode the relative values.
       //
       // We expect 1, 4, or 5 values. If present, values are expected in the
       // following order:
       //   0: the starting column in the current line of the generated file
       //   1: the id of the original source file
       //   2: the starting line in the original source
       //   3: the starting column in the original source
       //   4: the id of the original symbol name
       // The values are relative to the previous encountered values.
       if (tokenizer.nextKind.isNewSegment) throw _segmentError(0, line);
       column += tokenizer._consumeValue();
       if (!tokenizer.nextKind.isValue) {
         entries.add(new TargetEntry(column));
       } else {
         srcUrlId += tokenizer._consumeValue();
         if (srcUrlId >= urls.length) {
           throw new StateError(
               'Invalid source url id. $targetUrl, $line, $srcUrlId');
         }
         if (!tokenizer.nextKind.isValue) throw _segmentError(2, line);
         srcLine += tokenizer._consumeValue();
         if (!tokenizer.nextKind.isValue) throw _segmentError(3, line);
         srcColumn += tokenizer._consumeValue();
         if (!tokenizer.nextKind.isValue) {
           entries.add(new TargetEntry(column, srcUrlId, srcLine, srcColumn));
         } else {
           srcNameId += tokenizer._consumeValue();
           if (srcNameId >= names.length) {
             throw new StateError(
                 'Invalid name id: $targetUrl, $line, $srcNameId');
           }
           entries.add(
               new TargetEntry(column, srcUrlId, srcLine, srcColumn, srcNameId));
         }
       }
       if (tokenizer.nextKind.isNewSegment) tokenizer._consumeNewSegment();
     }
     if (!entries.isEmpty) {
       lines.add(new TargetLineEntry(line, entries));
     }
   }

   /// Encodes the Mapping mappings as a json map.
   Map toJson() {
     var buff = new StringBuffer();
     var line = 0;
     var column = 0;
     var srcLine = 0;
     var srcColumn = 0;
     var srcUrlId = 0;
     var srcNameId = 0;
     var first = true;

     for (var entry in lines) {
       int nextLine = entry.line;
       if (nextLine > line) {
         for (int i = line; i < nextLine; ++i) {
           buff.write(';');
         }
         line = nextLine;
         column = 0;
         first = true;
       }

       for (var segment in entry.entries) {
         if (!first) buff.write(',');
         first = false;
         column = _append(buff, column, segment.column);

         // Encoding can be just the column offset if there is no source
         // information.
         var newUrlId = segment.sourceUrlId;
         if (newUrlId == null) continue;
         srcUrlId = _append(buff, srcUrlId, newUrlId);
         srcLine = _append(buff, srcLine, segment.sourceLine);
         srcColumn = _append(buff, srcColumn, segment.sourceColumn);

         if (segment.sourceNameId == null) continue;
         srcNameId = _append(buff, srcNameId, segment.sourceNameId);
       }
     }

     var result = {
       'version': 3,
       'sourceRoot': sourceRoot == null ? '' : sourceRoot,
       'sources': urls,
       'names': names,
       'mappings': buff.toString()
     };
     if (targetUrl != null) {
       result['file'] = targetUrl;
     }
     return result;
   }

   /// Appends to [buff] a VLQ encoding of [newValue] using the difference
   /// between [oldValue] and [newValue]
   static int _append(StringBuffer buff, int oldValue, int newValue) {
     buff.writeAll(encodeVlq(newValue - oldValue));
     return newValue;
   }

   _segmentError(int seen, int line) =>
       new StateError('Invalid entry in sourcemap, expected 1, 4, or 5'
           ' values, but got $seen.\ntargeturl: $targetUrl, line: $line');

   /// Returns [TargetLineEntry] which includes the location in the target [line]
   /// number. In particular, the resulting entry is the last entry whose line
   /// number is lower or equal to [line].
   TargetLineEntry _findLine(int line) {
     int index = binarySearch(lines, (e) => e.line > line);
     return (index <= 0) ? null : lines[index - 1];
   }

   /// Returns [TargetEntry] which includes the location denoted by
   /// [line], [column]. If [lineEntry] corresponds to [line], then this will be
   /// the last entry whose column is lower or equal than [column]. If
   /// [lineEntry] corresponds to a line prior to [line], then the result will be
   /// the very last entry on that line.
   TargetEntry _findColumn(int line, int column, TargetLineEntry lineEntry) {
     if (lineEntry == null || lineEntry.entries.length == 0) return null;
     if (lineEntry.line != line) return lineEntry.entries.last;
     var entries = lineEntry.entries;
     int index = binarySearch(entries, (e) => e.column > column);
     return (index <= 0) ? null : entries[index - 1];
   }

   SourceMapSpan spanFor(int line, int column,
       {Map<String, SourceFile> files, String uri}) {
     var entry = _findColumn(line, column, _findLine(line));
     if (entry == null || entry.sourceUrlId == null) return null;
     var url = urls[entry.sourceUrlId];
     if (sourceRoot != null) {
       url = '${sourceRoot}${url}';
     }
     if (files != null && files[url] != null) {
       var file = files[url];
       var start = file.getOffset(entry.sourceLine, entry.sourceColumn);
       if (entry.sourceNameId != null) {
         var text = names[entry.sourceNameId];
         return new SourceMapFileSpan(
             files[url].span(start, start + text.length),
             isIdentifier: true);
       } else {
         return new SourceMapFileSpan(files[url].location(start).pointSpan());
       }
     } else {
       var start = new SourceLocation(0,
           sourceUrl: _mapUrl == null ? url : _mapUrl.resolve(url),
           line: entry.sourceLine,
           column: entry.sourceColumn);

       // Offset and other context is not available.
       if (entry.sourceNameId != null) {
         return new SourceMapSpan.identifier(start, names[entry.sourceNameId]);
       } else {
         return new SourceMapSpan(start, start, '');
       }
     }
   }

   String toString() {
     return (new StringBuffer("$runtimeType : [")
           ..write('targetUrl: ')
           ..write(targetUrl)
           ..write(', sourceRoot: ')
           ..write(sourceRoot)
           ..write(', urls: ')
           ..write(urls)
           ..write(', names: ')
           ..write(names)
           ..write(', lines: ')
           ..write(lines)
           ..write(']'))
         .toString();
   }

   String get debugString {
     var buff = new StringBuffer();
     for (var lineEntry in lines) {
       var line = lineEntry.line;
       for (var entry in lineEntry.entries) {
         buff
           ..write(targetUrl)
           ..write(': ')
           ..write(line)
           ..write(':')
           ..write(entry.column);
         if (entry.sourceUrlId != null) {
           buff
             ..write('   -->   ')
             ..write(sourceRoot)
             ..write(urls[entry.sourceUrlId])
             ..write(': ')
             ..write(entry.sourceLine)
             ..write(':')
             ..write(entry.sourceColumn);
         }
         if (entry.sourceNameId != null) {
           buff..write(' (')..write(names[entry.sourceNameId])..write(')');
         }
         buff.write('\n');
       }
     }
     return buff.toString();
   }
 }

 /// A line entry read from a source map.
 class TargetLineEntry {
   final int line;
   List<TargetEntry> entries;
   TargetLineEntry(this.line, this.entries);

   String toString() => '$runtimeType: $line $entries';
 }

 /// A target segment entry read from a source map
 class TargetEntry {
   final int column;
   final int sourceUrlId;
   final int sourceLine;
   final int sourceColumn;
   final int sourceNameId;

   TargetEntry(this.column,
       [this.sourceUrlId,
       this.sourceLine,
       this.sourceColumn,
       this.sourceNameId]);

   String toString() => '$runtimeType: '
       '($column, $sourceUrlId, $sourceLine, $sourceColumn, $sourceNameId)';
 }

 /** A character iterator over a string that can peek one character ahead. */
 class _MappingTokenizer implements Iterator<String> {
   final String _internal;
   final int _length;
   int index = -1;
   _MappingTokenizer(String internal)
       : _internal = internal,
         _length = internal.length;

   // Iterator API is used by decodeVlq to consume VLQ entries.
   bool moveNext() => ++index < _length;
   String get current =>
       (index >= 0 && index < _length) ? _internal[index] : null;

   bool get hasTokens => index < _length - 1 && _length > 0;

   _TokenKind get nextKind {
     if (!hasTokens) return _TokenKind.EOF;
     var next = _internal[index + 1];
     if (next == ';') return _TokenKind.LINE;
     if (next == ',') return _TokenKind.SEGMENT;
     return _TokenKind.VALUE;
   }

   int _consumeValue() => decodeVlq(this);
   void _consumeNewLine() {
     ++index;
   }

   void _consumeNewSegment() {
     ++index;
   }

   // Print the state of the iterator, with colors indicating the current
   // position.
   String toString() {
     var buff = new StringBuffer();
     for (int i = 0; i < index; i++) {
       buff.write(_internal[i]);
     }
     buff.write('[31m');
     buff.write(current == null ? '' : current);
     buff.write('[0m');
     for (int i = index + 1; i < _internal.length; i++) {
       buff.write(_internal[i]);
     }
     buff.write(' ($index)');
     return buff.toString();
   }
 }

 class _TokenKind {
   static const _TokenKind LINE = const _TokenKind(isNewLine: true);
   static const _TokenKind SEGMENT = const _TokenKind(isNewSegment: true);
   static const _TokenKind EOF = const _TokenKind(isEof: true);
   static const _TokenKind VALUE = const _TokenKind();
   final bool isNewLine;
   final bool isNewSegment;
   final bool isEof;
   bool get isValue => !isNewLine && !isNewSegment && !isEof;

   const _TokenKind(
       {this.isNewLine: false, this.isNewSegment: false, this.isEof: false});
 }
	// Copyright (c) 2013, the Dart project authors. Please see the AUTHORS file
	// for details. All rights reserved. Use of this source code is governed by a
	// BSD-style license that can be found in the LICENSE file.

	/// Contains the top-level function to parse source maps version 3.
	library source_maps.parser;

	import 'dart:collection';
	import 'dart:convert';

	import 'package:path/path.dart' as path;
	import 'package:source_span/source_span.dart';

	import 'builder.dart' as builder;
	import 'src/source_map_span.dart';
	import 'src/utils.dart';
	import 'src/vlq.dart';

	/// Parses a source map directly from a json string.
	///
	/// [mapUrl], which may be either a [String] or a [Uri], indicates the URL of
	/// the source map file itself. If it's passed, any URLs in the source
	/// map will be interpreted as relative to this URL when generating spans.
	// TODO(sigmund): evaluate whether other maps should have the json parsed, or
	// the string represenation.
	// TODO(tjblasi): Ignore the first line of [jsonMap] if the JSON safety string
	// `)]}'` begins the string representation of the map.
	Mapping parse(String jsonMap, {Map<String, Map> otherMaps, mapUrl}) =>
	parseJson(JSON.decode(jsonMap), otherMaps: otherMaps, mapUrl: mapUrl);

	/// Parses a source map or source map bundle directly from a json string.
	///
	/// [mapUrl], which may be either a [String] or a [Uri], indicates the URL of
	/// the source map file itself. If it's passed, any URLs in the source
	/// map will be interpreted as relative to this URL when generating spans.
	Mapping parseExtended(String jsonMap, {Map<String, Map> otherMaps, mapUrl}) =>
	parseJsonExtended(JSON.decode(jsonMap),
	otherMaps: otherMaps, mapUrl: mapUrl);

	/// Parses a source map or source map bundle.
	///
	/// [mapUrl], which may be either a [String] or a [Uri], indicates the URL of
	/// the source map file itself. If it's passed, any URLs in the source
	/// map will be interpreted as relative to this URL when generating spans.
	Mapping parseJsonExtended(/List\|Map/ json,
	{Map<String, Map> otherMaps, mapUrl}) {
	if (json is List) {
	return new MappingBundle.fromJson(json, mapUrl: mapUrl);
	}
	return parseJson(json as Map);
	}

	/// Parses a source map
	///
	/// [mapUrl], which may be either a [String] or a [Uri], indicates the URL of
	/// the source map file itself. If it's passed, any URLs in the source
	/// map will be interpreted as relative to this URL when generating spans.
	Mapping parseJson(Map map, {Map<String, Map> otherMaps, mapUrl}) {
	if (map['version'] != 3) {
	throw new ArgumentError('unexpected source map version: ${map["version"]}. '
	'Only version 3 is supported.');
	}

	if (map.containsKey('sections')) {
	if (map.containsKey('mappings') \|\|
	map.containsKey('sources') \|\|
	map.containsKey('names')) {
	throw new FormatException('map containing "sections" '
	'cannot contain "mappings", "sources", or "names".');
	}
	return new MultiSectionMapping.fromJson(map['sections'], otherMaps,
	mapUrl: mapUrl);
	}
	return new SingleMapping.fromJson(map, mapUrl: mapUrl);
	}

	/// A mapping parsed out of a source map.
	abstract class Mapping {
	/// Returns the span associated with [line] and [column].
	///
	/// [uri] is the optional location of the output file to find the span for
	/// to disambiguate cases where a mapping may have different mappings for
	/// different output files.
	SourceMapSpan spanFor(int line, int column,
	{Map<String, SourceFile> files, String uri});

	/// Returns the span associated with [location].
	SourceMapSpan spanForLocation(SourceLocation location,
	{Map<String, SourceFile> files}) {
	return spanFor(location.line, location.column,
	uri: location.sourceUrl?.toString(), files: files);
	}
	}

	/// A meta-level map containing sections.
	class MultiSectionMapping extends Mapping {
	/// For each section, the start line offset.
	final List<int> _lineStart = <int>[];

	/// For each section, the start column offset.
	final List<int> _columnStart = <int>[];

	/// For each section, the actual source map information, which is not adjusted
	/// for offsets.
	final List<Mapping> _maps = <Mapping>[];

	/// Creates a section mapping from json.
	MultiSectionMapping.fromJson(List sections, Map<String, Map> otherMaps,
	{mapUrl}) {
	for (var section in sections) {
	var offset = section['offset'];
	if (offset == null) throw new FormatException('section missing offset');

	var line = section['offset']['line'];
	if (line == null) throw new FormatException('offset missing line');

	var column = section['offset']['column'];
	if (column == null) throw new FormatException('offset missing column');

	_lineStart.add(line);
	_columnStart.add(column);

	var url = section['url'];
	var map = section['map'];

	if (url != null && map != null) {
	throw new FormatException("section can't use both url and map entries");
	} else if (url != null) {
	if (otherMaps == null \|\| otherMaps[url] == null) {
	throw new FormatException(
	'section contains refers to $url, but no map was '
	'given for it. Make sure a map is passed in "otherMaps"');
	}
	_maps.add(parseJson(otherMaps[url], otherMaps: otherMaps, mapUrl: url));
	} else if (map != null) {
	_maps.add(parseJson(map, otherMaps: otherMaps, mapUrl: mapUrl));
	} else {
	throw new FormatException('section missing url or map');
	}
	}
	if (_lineStart.length == 0) {
	throw new FormatException('expected at least one section');
	}
	}

	int _indexFor(line, column) {
	for (int i = 0; i < _lineStart.length; i++) {
	if (line < _lineStart[i]) return i - 1;
	if (line == _lineStart[i] && column < _columnStart[i]) return i - 1;
	}
	return _lineStart.length - 1;
	}

	SourceMapSpan spanFor(int line, int column,
	{Map<String, SourceFile> files, String uri}) {
	// TODO(jacobr): perhaps verify that targetUrl matches the actual uri
	// or at least ends in the same file name.
	int index = _indexFor(line, column);
	return _maps[index].spanFor(
	line - _lineStart[index], column - _columnStart[index],
	files: files);
	}

	String toString() {
	var buff = new StringBuffer("$runtimeType : [");
	for (int i = 0; i < _lineStart.length; i++) {
	buff
	..write('(')
	..write(_lineStart[i])
	..write(',')
	..write(_columnStart[i])
	..write(':')
	..write(_maps[i])
	..write(')');
	}
	buff.write(']');
	return buff.toString();
	}
	}

	class MappingBundle extends Mapping {
	Map<String, SingleMapping> _mappings = {};

	MappingBundle.fromJson(List json, {String mapUrl}) {
	for (var map in json) {
	var mapping = parseJson(map, mapUrl: mapUrl) as SingleMapping;
	var targetUrl = mapping.targetUrl;
	_mappings[targetUrl] = mapping;
	}
	}

	/// Encodes the Mapping mappings as a json map.
	List toJson() => _mappings.values.map((v) => v.toJson()).toList();

	String toString() {
	var buff = new StringBuffer();
	for (var map in _mappings.values) {
	buff.write(map.toString());
	}
	return buff.toString();
	}

	SourceMapSpan spanFor(int line, int column,
	{Map<String, SourceFile> files, String uri}) {
	if (uri == null) {
	throw new ArgumentError.notNull('uri');
	}
	if (_mappings.containsKey(uri)) {
	return _mappings[uri].spanFor(line, column, files: files, uri: uri);
	}
	// Fall back to looking up the source map on just the basename.
	var name = path.basename(uri.toString());
	if (_mappings.containsKey(name)) {
	return _mappings[name].spanFor(line, column, files: files, uri: name);
	}

	// Note: when there is no source map for an uri, this behaves like an
	// identity function, returning the requested location as the result.

	// Create a mock offset for the output location. We compute it in terms
	// of the input line and column to minimize the chances that two different
	// line and column locations are mapped to the same offset.
	var offset = line * 1000000 + column;
	var location = new SourceLocation(offset,
	line: line, column: column, sourceUrl: Uri.parse(uri));
	return new SourceMapSpan(location, location, "");
	}
	}

	/// A map containing direct source mappings.
	class SingleMapping extends Mapping {
	/// Source urls used in the mapping, indexed by id.
	final List<String> urls;

	/// Source names used in the mapping, indexed by id.
	final List<String> names;

	/// Entries indicating the beginning of each span.
	final List<TargetLineEntry> lines;

	/// Url of the target file.
	String targetUrl;

	/// Source root prepended to all entries in [urls].
	String sourceRoot;

	final Uri _mapUrl;

	SingleMapping._(this.targetUrl, this.urls, this.names, this.lines)
	: _mapUrl = null;

	factory SingleMapping.fromEntries(Iterable<builder.Entry> entries,
	[String fileUrl]) {
	// The entries needs to be sorted by the target offsets.
	var sourceEntries = new List.from(entries)..sort();
	var lines = <TargetLineEntry>[];

	// Indices associated with file urls that will be part of the source map. We
	// use a linked hash-map so that `_urls.keys[_urls[u]] == u`
	var urls = new LinkedHashMap<String, int>();

	// Indices associated with identifiers that will be part of the source map.
	// We use a linked hash-map so that `_names.keys[_names[n]] == n`
	var names = new LinkedHashMap<String, int>();

	var lineNum;
	List<TargetEntry> targetEntries;
	for (var sourceEntry in sourceEntries) {
	if (lineNum == null \|\| sourceEntry.target.line > lineNum) {
	lineNum = sourceEntry.target.line;
	targetEntries = <TargetEntry>[];
	lines.add(new TargetLineEntry(lineNum, targetEntries));
	}

	if (sourceEntry.source == null) {
	targetEntries.add(new TargetEntry(sourceEntry.target.column));
	} else {
	var sourceUrl = sourceEntry.source.sourceUrl;
	var urlId = urls.putIfAbsent(
	sourceUrl == null ? '' : sourceUrl.toString(), () => urls.length);
	var srcNameId = sourceEntry.identifierName == null
	? null
	: names.putIfAbsent(sourceEntry.identifierName, () => names.length);
	targetEntries.add(new TargetEntry(sourceEntry.target.column, urlId,
	sourceEntry.source.line, sourceEntry.source.column, srcNameId));
	}
	}
	return new SingleMapping._(
	fileUrl, urls.keys.toList(), names.keys.toList(), lines);
	}

	SingleMapping.fromJson(Map map, {mapUrl})
	: targetUrl = map['file'],
	urls = new List<String>.from(map['sources']),
	names = new List<String>.from(map['names']),
	sourceRoot = map['sourceRoot'],
	lines = <TargetLineEntry>[],
	_mapUrl = mapUrl is String ? Uri.parse(mapUrl) : mapUrl {
	int line = 0;
	int column = 0;
	int srcUrlId = 0;
	int srcLine = 0;
	int srcColumn = 0;
	int srcNameId = 0;
	var tokenizer = new _MappingTokenizer(map['mappings']);
	var entries = <TargetEntry>[];

	while (tokenizer.hasTokens) {
	if (tokenizer.nextKind.isNewLine) {
	if (!entries.isEmpty) {
	lines.add(new TargetLineEntry(line, entries));
	entries = <TargetEntry>[];
	}
	line++;
	column = 0;
	tokenizer._consumeNewLine();
	continue;
	}

	// Decode the next entry, using the previous encountered values to
	// decode the relative values.
	//
	// We expect 1, 4, or 5 values. If present, values are expected in the
	// following order:
	// 0: the starting column in the current line of the generated file
	// 1: the id of the original source file
	// 2: the starting line in the original source
	// 3: the starting column in the original source
	// 4: the id of the original symbol name
	// The values are relative to the previous encountered values.
	if (tokenizer.nextKind.isNewSegment) throw _segmentError(0, line);
	column += tokenizer._consumeValue();
	if (!tokenizer.nextKind.isValue) {
	entries.add(new TargetEntry(column));
	} else {
	srcUrlId += tokenizer._consumeValue();
	if (srcUrlId >= urls.length) {
	throw new StateError(
	'Invalid source url id. $targetUrl, $line, $srcUrlId');
	}
	if (!tokenizer.nextKind.isValue) throw _segmentError(2, line);
	srcLine += tokenizer._consumeValue();
	if (!tokenizer.nextKind.isValue) throw _segmentError(3, line);
	srcColumn += tokenizer._consumeValue();
	if (!tokenizer.nextKind.isValue) {
	entries.add(new TargetEntry(column, srcUrlId, srcLine, srcColumn));
	} else {
	srcNameId += tokenizer._consumeValue();
	if (srcNameId >= names.length) {
	throw new StateError(
	'Invalid name id: $targetUrl, $line, $srcNameId');
	}
	entries.add(
	new TargetEntry(column, srcUrlId, srcLine, srcColumn, srcNameId));
	}
	}
	if (tokenizer.nextKind.isNewSegment) tokenizer._consumeNewSegment();
	}
	if (!entries.isEmpty) {
	lines.add(new TargetLineEntry(line, entries));
	}
	}

	/// Encodes the Mapping mappings as a json map.
	Map toJson() {
	var buff = new StringBuffer();
	var line = 0;
	var column = 0;
	var srcLine = 0;
	var srcColumn = 0;
	var srcUrlId = 0;
	var srcNameId = 0;
	var first = true;

	for (var entry in lines) {
	int nextLine = entry.line;
	if (nextLine > line) {
	for (int i = line; i < nextLine; ++i) {
	buff.write(';');
	}
	line = nextLine;
	column = 0;
	first = true;
	}

	for (var segment in entry.entries) {
	if (!first) buff.write(',');
	first = false;
	column = _append(buff, column, segment.column);

	// Encoding can be just the column offset if there is no source
	// information.
	var newUrlId = segment.sourceUrlId;
	if (newUrlId == null) continue;
	srcUrlId = _append(buff, srcUrlId, newUrlId);
	srcLine = _append(buff, srcLine, segment.sourceLine);
	srcColumn = _append(buff, srcColumn, segment.sourceColumn);

	if (segment.sourceNameId == null) continue;
	srcNameId = _append(buff, srcNameId, segment.sourceNameId);
	}
	}

	var result = {
	'version': 3,
	'sourceRoot': sourceRoot == null ? '' : sourceRoot,
	'sources': urls,
	'names': names,
	'mappings': buff.toString()
	};
	if (targetUrl != null) {
	result['file'] = targetUrl;
	}
	return result;
	}

	/// Appends to [buff] a VLQ encoding of [newValue] using the difference
	/// between [oldValue] and [newValue]
	static int _append(StringBuffer buff, int oldValue, int newValue) {
	buff.writeAll(encodeVlq(newValue - oldValue));
	return newValue;
	}

	_segmentError(int seen, int line) =>
	new StateError('Invalid entry in sourcemap, expected 1, 4, or 5'
	' values, but got $seen.\ntargeturl: $targetUrl, line: $line');

	/// Returns [TargetLineEntry] which includes the location in the target [line]
	/// number. In particular, the resulting entry is the last entry whose line
	/// number is lower or equal to [line].
	TargetLineEntry _findLine(int line) {
	int index = binarySearch(lines, (e) => e.line > line);
	return (index <= 0) ? null : lines[index - 1];
	}

	/// Returns [TargetEntry] which includes the location denoted by
	/// [line], [column]. If [lineEntry] corresponds to [line], then this will be
	/// the last entry whose column is lower or equal than [column]. If
	/// [lineEntry] corresponds to a line prior to [line], then the result will be
	/// the very last entry on that line.
	TargetEntry _findColumn(int line, int column, TargetLineEntry lineEntry) {
	if (lineEntry == null \|\| lineEntry.entries.length == 0) return null;
	if (lineEntry.line != line) return lineEntry.entries.last;
	var entries = lineEntry.entries;
	int index = binarySearch(entries, (e) => e.column > column);
	return (index <= 0) ? null : entries[index - 1];
	}

	SourceMapSpan spanFor(int line, int column,
	{Map<String, SourceFile> files, String uri}) {
	var entry = _findColumn(line, column, _findLine(line));
	if (entry == null \|\| entry.sourceUrlId == null) return null;
	var url = urls[entry.sourceUrlId];
	if (sourceRoot != null) {
	url = '${sourceRoot}${url}';
	}
	if (files != null && files[url] != null) {
	var file = files[url];
	var start = file.getOffset(entry.sourceLine, entry.sourceColumn);
	if (entry.sourceNameId != null) {
	var text = names[entry.sourceNameId];
	return new SourceMapFileSpan(
	files[url].span(start, start + text.length),
	isIdentifier: true);
	} else {
	return new SourceMapFileSpan(files[url].location(start).pointSpan());
	}
	} else {
	var start = new SourceLocation(0,
	sourceUrl: _mapUrl == null ? url : _mapUrl.resolve(url),
	line: entry.sourceLine,
	column: entry.sourceColumn);

	// Offset and other context is not available.
	if (entry.sourceNameId != null) {
	return new SourceMapSpan.identifier(start, names[entry.sourceNameId]);
	} else {
	return new SourceMapSpan(start, start, '');
	}
	}
	}

	String toString() {
	return (new StringBuffer("$runtimeType : [")
	..write('targetUrl: ')
	..write(targetUrl)
	..write(', sourceRoot: ')
	..write(sourceRoot)
	..write(', urls: ')
	..write(urls)
	..write(', names: ')
	..write(names)
	..write(', lines: ')
	..write(lines)
	..write(']'))
	.toString();
	}

	String get debugString {
	var buff = new StringBuffer();
	for (var lineEntry in lines) {
	var line = lineEntry.line;
	for (var entry in lineEntry.entries) {
	buff
	..write(targetUrl)
	..write(': ')
	..write(line)
	..write(':')
	..write(entry.column);
	if (entry.sourceUrlId != null) {
	buff
	..write(' --> ')
	..write(sourceRoot)
	..write(urls[entry.sourceUrlId])
	..write(': ')
	..write(entry.sourceLine)
	..write(':')
	..write(entry.sourceColumn);
	}
	if (entry.sourceNameId != null) {
	buff..write(' (')..write(names[entry.sourceNameId])..write(')');
	}
	buff.write('\n');
	}
	}
	return buff.toString();
	}
	}

	/// A line entry read from a source map.
	class TargetLineEntry {
	final int line;
	List<TargetEntry> entries;
	TargetLineEntry(this.line, this.entries);

	String toString() => '$runtimeType: $line $entries';
	}

	/// A target segment entry read from a source map
	class TargetEntry {
	final int column;
	final int sourceUrlId;
	final int sourceLine;
	final int sourceColumn;
	final int sourceNameId;

	TargetEntry(this.column,
	[this.sourceUrlId,
	this.sourceLine,
	this.sourceColumn,
	this.sourceNameId]);

	String toString() => '$runtimeType: '
	'($column, $sourceUrlId, $sourceLine, $sourceColumn, $sourceNameId)';
	}

	/** A character iterator over a string that can peek one character ahead. */
	class _MappingTokenizer implements Iterator<String> {
	final String _internal;
	final int _length;
	int index = -1;
	_MappingTokenizer(String internal)
	: _internal = internal,
	_length = internal.length;

	// Iterator API is used by decodeVlq to consume VLQ entries.
	bool moveNext() => ++index < _length;
	String get current =>
	(index >= 0 && index < _length) ? _internal[index] : null;

	bool get hasTokens => index < _length - 1 && _length > 0;

	_TokenKind get nextKind {
	if (!hasTokens) return _TokenKind.EOF;
	var next = _internal[index + 1];
	if (next == ';') return _TokenKind.LINE;
	if (next == ',') return _TokenKind.SEGMENT;
	return _TokenKind.VALUE;
	}

	int _consumeValue() => decodeVlq(this);
	void _consumeNewLine() {
	++index;
	}

	void _consumeNewSegment() {
	++index;
	}

	// Print the state of the iterator, with colors indicating the current
	// position.
	String toString() {
	var buff = new StringBuffer();
	for (int i = 0; i < index; i++) {
	buff.write(_internal[i]);
	}
	buff.write('[31m');
	buff.write(current == null ? '' : current);
	buff.write('[0m');
	for (int i = index + 1; i < _internal.length; i++) {
	buff.write(_internal[i]);
	}
	buff.write(' ($index)');
	return buff.toString();
	}
	}

	class _TokenKind {
	static const _TokenKind LINE = const _TokenKind(isNewLine: true);
	static const _TokenKind SEGMENT = const _TokenKind(isNewSegment: true);
	static const _TokenKind EOF = const _TokenKind(isEof: true);
	static const _TokenKind VALUE = const _TokenKind();
	final bool isNewLine;
	final bool isNewSegment;
	final bool isEof;
	bool get isValue => !isNewLine && !isNewSegment && !isEof;

	const _TokenKind(
	{this.isNewLine: false, this.isNewSegment: false, this.isEof: false});
	}