vipunen/patched_sdk/lib/core/core.dart

// Copyright (c) 2012, 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.

/**
 *
 * Built-in types, collections,
 * and other core functionality for every Dart program.
 *
 * This library is automatically imported.
 *
 * Some classes in this library,
 * such as [String] and [num],
 * support Dart's built-in data types.
 * Other classes, such as [List] and [Map], provide data structures
 * for managing collections of objects.
 * And still other classes represent commonly used types of data
 * such as URIs, dates and times, and errors.
 *
 * ## Numbers and booleans
 *
 * [int] and [double] provide support for Dart's built-in numerical data types:
 * integers and double-precision floating point numbers, respectively.
 * An object of type [bool] is either true or false.
 * Variables of these types can be constructed from literals:
 *
 *     int meaningOfLife = 42;
 *     double valueOfPi  = 3.141592;
 *     bool visible      = true;
 *
 * ## Strings and regular expressions
 *
 * A [String] is immutable and represents a sequence of characters.
 *
 *     String shakespeareQuote = "All the world's a stage, ...";
 *
 * [StringBuffer] provides a way to construct strings efficiently.
 *
 *     StringBuffer moreShakespeare = new StringBuffer();
 *     moreShakespeare.write('And all the men and women ');
 *     moreShakespeare.write('merely players; ...');
 *
 * The String and StringBuffer classes implement string concatenation,
 * interpolation, and other string manipulation features.
 *
 *     String philosophy = 'Live on ';
 *     String get palindrome => philosophy + philosophy.split('').reversed.join();
 *
 * [RegExp] implements Dart regular expressions,
 * which provide a grammar for matching patterns within text.
 * For example, here's a regular expression that matches
 * a string of one or more digits:
 *
 *     var numbers = new RegExp(r'\d+');
 *
 * Dart regular expressions have the same syntax and semantics as
 * JavaScript regular expressions. See
 * <http://ecma-international.org/ecma-262/5.1/#sec-15.10>
 * for the specification of JavaScript regular expressions.
 *
 * ## Collections
 *
 * The dart:core library provides basic collections,
 * such as [List], [Map], and [Set].
 *
 * A List is an ordered collection of objects, with a length.
 * Lists are sometimes called arrays.
 * Use a List when you need to access objects by index.
 *
 *     List superheroes = [ 'Batman', 'Superman', 'Harry Potter' ];
 *
 * A Set is an unordered collection of unique objects.
 * You cannot get an item by index (position).
 * Adding a duplicate item has no effect.
 *
 *     Set villains = new Set();
 *     villains.add('Joker');
 *     villains.addAll( ['Lex Luther', 'Voldemort'] );
 *
 * A Map is an unordered collection of key-value pairs.
 * Maps are sometimes called associative arrays because
 * maps associate a key to some value for easy retrieval.
 * Keys are unique.
 * Use a Map when you need to access objects
 * by a unique identifier.
 *
 *     Map sidekicks = { 'Batman': 'Robin',
 *                       'Superman': 'Lois Lane',
 *                       'Harry Potter': 'Ron and Hermione' };
 *
 * In addition to these classes,
 * dart:core contains [Iterable],
 * an interface that defines functionality
 * common in collections of objects.
 * Examples include the ability
 * to run a function on each element in the collection,
 * to apply a test to each element,
 * to retrieve an object, and to determine length.
 *
 * Iterable is implemented by List and Set,
 * and used by Map for its keys and values.
 *
 * For other kinds of collections, check out the
 * [dart:collection](#dart-collection) library.
 *
 * ## Date and time
 *
 * Use [DateTime] to represent a point in time
 * and [Duration] to represent a span of time.
 *
 * You can create DateTime objects with constructors
 * or by parsing a correctly formatted string.
 *
 *     DateTime now = new DateTime.now();
 *     DateTime berlinWallFell = new DateTime(1989, 11, 9);
 *     DateTime moonLanding = DateTime.parse("1969-07-20");
 *
 * Create a Duration object specifying the individual time units.
 *
 *     Duration timeRemaining = new Duration(hours:56, minutes:14);
 *
 * In addition to DateTime and Duration,
 * dart:core contains the [Stopwatch] class for measuring elapsed time.
 *
 * ## Uri
 *
 * A [Uri] object represents a uniform resource identifier,
 * which identifies a resource on the web.
 *
 *     Uri dartlang = Uri.parse('http://dartlang.org/');
 *
 * ## Errors
 *
 * The [Error] class represents the occurrence of an error
 * during runtime.
 * Subclasses of this class represent specific kinds of errors.
 *
 * ## Other documentation
 *
 * For more information about how to use the built-in types, refer to [Built-in
 * Types](http://www.dartlang.org/docs/dart-up-and-running/contents/ch02.html#built-in-types)
 * in Chapter 2 of
 * [Dart: Up and Running](http://www.dartlang.org/docs/dart-up-and-running/).
 *
 * Also, see [dart:core - Numbers, Collections, Strings, and
 * More](https://www.dartlang.org/docs/dart-up-and-running/ch03.html#dartcore---numbers-collections-strings-and-more)
 * for more coverage of classes in this package.
 *
 * The
 * [Dart Language Specification](http://www.dartlang.org/docs/spec/)
 * provides technical details.
 */
library dart.core;

import "dart:collection";
import "dart:_internal" hide Symbol;
import "dart:_internal" as internal show Symbol;
import "dart:convert"
    show Encoding, ASCII, LATIN1, UTF8, BASE64, StringConversionSink;
import "dart:math" show Random; // Used by List.shuffle.
import "dart:typed_data" show Uint8List;
import "dart:async";
import "dart:collection" show LinkedList, LinkedListEntry;
import 'dart:convert' show ASCII, JSON;
import "dart:isolate";
import "dart:math";
import "dart:typed_data";
import 'dart:_internal' as internal;

part "annotations.dart";
part "bool.dart";
part "comparable.dart";
part "date_time.dart";
part "double.dart";
part "duration.dart";
part "errors.dart";
part "exceptions.dart";
part "expando.dart";
part "function.dart";
part "identical.dart";
part "int.dart";
part "invocation.dart";
part "iterable.dart";
part "iterator.dart";
part "list.dart";
part "map.dart";
part "null.dart";
part "num.dart";
part "object.dart";
part "pattern.dart";
part "print.dart";
part "regexp.dart";
part "set.dart";
part "sink.dart";
part "stacktrace.dart";
part "stopwatch.dart";
part "string.dart";
part "string_buffer.dart";
part "string_sink.dart";
part "symbol.dart";
part "type.dart";
part "uri.dart";

class _CastError extends Error implements CastError {
  _CastError._create(this._url, this._line, this._column, this._errorMsg);

  // A CastError is allocated by TypeError._throwNew() when dst_name equals
  // Symbols::InTypeCast().

  String toString() => _errorMsg;

  // Fields _url, _line, and _column are only used for debugging purposes.
  final String _url;
  final int _line;
  final int _column;
  final String _errorMsg;
}
typedef bool _SyncGeneratorCallback(Iterator iterator);
class _SyncIterable extends IterableBase {
  // _moveNextFn is the closurized body of the generator function.
  final _SyncGeneratorCallback _moveNextFn;

  const _SyncIterable(this._moveNextFn);

  get iterator {
    return new _SyncIterator(_moveNextFn._clone());
  }
}
class _SyncIterator implements Iterator {
  bool isYieldEach; // Set by generated code for the yield* statement.
  Iterator yieldEachIterator;
  var _current; // Set by generated code for the yield and yield* statement.
  _SyncGeneratorCallback _moveNextFn;

  get current =>
      yieldEachIterator != null ? yieldEachIterator.current : _current;

  _SyncIterator(this._moveNextFn);

  bool moveNext() {
    if (_moveNextFn == null) {
      return false;
    }
    while (true) {
      if (yieldEachIterator != null) {
        if (yieldEachIterator.moveNext()) {
          return true;
        }
        yieldEachIterator = null;
      }
      isYieldEach = false;
      // _moveNextFn() will update the values of isYieldEach and _current.
      if (!_moveNextFn(this)) {
        _moveNextFn = null;
        _current = null;
        return false;
      }
      if (isYieldEach) {
        // Spec mandates: it is a dynamic error if the class of [the object
        // returned by yield*] does not implement Iterable.
        yieldEachIterator = (_current as Iterable).iterator;
        _current = null;
        continue;
      }
      return true;
    }
  }
}
class _List<E> extends FixedLengthListBase<E> {
  factory _List(int length) native "List_allocate";

  E operator [](int index) native "List_getIndexed";

  void operator []=(int index, E value) native "List_setIndexed";

  int get length native "List_getLength";

  List _slice(int start, int count, bool needsTypeArgument) {
    if (count <= 64) {
      final result = needsTypeArgument ? new _List<E>(count) : new _List(count);
      for (int i = 0; i < result.length; i++) {
        result[i] = this[start + i];
      }
      return result;
    } else {
      return _sliceInternal(start, count, needsTypeArgument);
    }
  }

  List _sliceInternal(int start, int count, bool needsTypeArgument)
      native "List_slice";

  // List interface.
  void setRange(int start, int end, Iterable<E> iterable, [int skipCount = 0]) {
    if (start < 0 || start > this.length) {
      throw new RangeError.range(start, 0, this.length);
    }
    if (end < start || end > this.length) {
      throw new RangeError.range(end, start, this.length);
    }
    int length = end - start;
    if (length == 0) return;
    if (identical(this, iterable)) {
      Lists.copy(iterable, skipCount, this, start, length);
    } else if (ClassID.getID(iterable) == ClassID.cidArray) {
      Lists.copy(iterable, skipCount, this, start, length);
    } else if (iterable is List) {
      Lists.copy(iterable, skipCount, this, start, length);
    } else {
      Iterator it = iterable.iterator;
      while (skipCount > 0) {
        if (!it.moveNext()) return;
        skipCount--;
      }
      for (int i = start; i < end; i++) {
        if (!it.moveNext()) return;
        this[i] = it.current;
      }
    }
  }

  List<E> sublist(int start, [int end]) {
    end = RangeError.checkValidRange(start, end, this.length);
    int length = end - start;
    if (length == 0) return <E>[];
    var result = new _GrowableList<E>.withData(_slice(start, length, false));
    result._setLength(length);
    return result;
  }

  // Iterable interface.

  void forEach(f(E element)) {
    final length = this.length;
    for (int i = 0; i < length; i++) {
      f(this[i]);
    }
  }

  Iterator<E> get iterator {
    return new _FixedSizeArrayIterator<E>(this);
  }

  E get first {
    if (length > 0) return this[0];
    throw IterableElementError.noElement();
  }

  E get last {
    if (length > 0) return this[length - 1];
    throw IterableElementError.noElement();
  }

  E get single {
    if (length == 1) return this[0];
    if (length == 0) throw IterableElementError.noElement();
    throw IterableElementError.tooMany();
  }

  List<E> toList({bool growable: true}) {
    var length = this.length;
    if (length > 0) {
      var result = _slice(0, length, !growable);
      if (growable) {
        result = new _GrowableList<E>.withData(result);
        result._setLength(length);
      }
      return result;
    }
    // _GrowableList.withData must not be called with empty list.
    return growable ? <E>[] : new List<E>(0);
  }
}
class _ImmutableList<E> extends UnmodifiableListBase<E> {
  factory _ImmutableList._uninstantiable() {
    throw new UnsupportedError(
        "ImmutableArray can only be allocated by the VM");
  }

  factory _ImmutableList._from(List from, int offset, int length)
      native "ImmutableList_from";

  E operator [](int index) native "List_getIndexed";

  int get length native "List_getLength";

  List<E> sublist(int start, [int end]) {
    end = RangeError.checkValidRange(start, end, this.length);
    int length = end - start;
    if (length == 0) return <E>[];
    List list = new _List(length);
    for (int i = 0; i < length; i++) {
      list[i] = this[start + i];
    }
    var result = new _GrowableList<E>.withData(list);
    result._setLength(length);
    return result;
  }

  // Collection interface.

  void forEach(f(E element)) {
    final length = this.length;
    for (int i = 0; i < length; i++) {
      f(this[i]);
    }
  }

  Iterator<E> get iterator {
    return new _FixedSizeArrayIterator<E>(this);
  }

  E get first {
    if (length > 0) return this[0];
    throw IterableElementError.noElement();
  }

  E get last {
    if (length > 0) return this[length - 1];
    throw IterableElementError.noElement();
  }

  E get single {
    if (length == 1) return this[0];
    if (length == 0) throw IterableElementError.noElement();
    throw IterableElementError.tooMany();
  }

  List<E> toList({bool growable: true}) {
    var length = this.length;
    if (length > 0) {
      List<E> list = new _List<E>(length);
      for (int i = 0; i < length; i++) {
        list[i] = this[i];
      }
      if (!growable) return list;
      list = new _GrowableList<E>.withData(list);
      list._setLength(length);
      return list;
    }
    return growable ? <E>[] : new _List<E>(0);
  }
}
class _FixedSizeArrayIterator<E> implements Iterator<E> {
  final List<E> _array;
  final int _length; // Cache array length for faster access.
  int _index;
  E _current;

  _FixedSizeArrayIterator(List array)
      : _array = array,
        _length = array.length,
        _index = 0 {
    assert(array is _List || array is _ImmutableList);
  }

  E get current => _current;

  bool moveNext() {
    if (_index >= _length) {
      _current = null;
      return false;
    }
    _current = _array[_index];
    _index++;
    return true;
  }
}
const int _GROWABLE_ARRAY_MARKER = -42;
class _Double implements double {
  factory _Double.fromInteger(int value) native "Double_doubleFromInteger";

  // TODO: Make a stared static method for hashCode and _identityHashCode
  //       when semantics are corrected as described in:
  //       https://github.com/dart-lang/sdk/issues/2884
  int get hashCode => (isNaN || isInfinite) ? 0 : toInt();
  int get _identityHashCode => (isNaN || isInfinite) ? 0 : toInt();

  double operator +(double other) {
    return _add(other.toDouble());
  }

  double _add(double other) native "Double_add";

  double operator -(double other) {
    return _sub(other.toDouble());
  }

  double _sub(double other) native "Double_sub";

  double operator *(double other) {
    return _mul(other.toDouble());
  }

  double _mul(double other) native "Double_mul";

  int operator ~/(double other) {
    return _trunc_div(other.toDouble());
  }

  int _trunc_div(double other) native "Double_trunc_div";

  double operator /(double other) {
    return _div(other.toDouble());
  }

  double _div(double other) native "Double_div";

  double operator %(double other) {
    return _modulo(other.toDouble());
  }

  double _modulo(double other) native "Double_modulo";

  double remainder(double other) {
    return _remainder(other.toDouble());
  }

  double _remainder(double other) native "Double_remainder";

  double operator -() native "Double_flipSignBit";

  bool operator ==(double other) {
    return _equal(other.toDouble());
  }

  bool _equal(double other) native "Double_equal";
  bool _equalToInteger(int other) native "Double_equalToInteger";
  bool operator <(double other) {
    return other > this;
  }

  bool operator >(double other) {
    return _greaterThan(other.toDouble());
  }

  bool _greaterThan(double other) native "Double_greaterThan";
  bool operator >=(double other) {
    return (this == other) || (this > other);
  }

  bool operator <=(double other) {
    return (this == other) || (this < other);
  }

  double _addFromInteger(int other) {
    return new _Double.fromInteger(other)._add(this);
  }

  double _subFromInteger(int other) {
    return new _Double.fromInteger(other)._sub(this);
  }

  double _mulFromInteger(int other) {
    return new _Double.fromInteger(other)._mul(this);
  }

  int _truncDivFromInteger(int other) {
    return new _Double.fromInteger(other)._trunc_div(this);
  }

  double _moduloFromInteger(int other) {
    return new _Double.fromInteger(other)._modulo(this);
  }

  double _remainderFromInteger(int other) {
    return new _Double.fromInteger(other)._remainder(this);
  }

  bool _greaterThanFromInteger(int other)
      native "Double_greaterThanFromInteger";

  bool get isNegative native "Double_getIsNegative";
  bool get isInfinite native "Double_getIsInfinite";
  bool get isNaN native "Double_getIsNaN";
  bool get isFinite => !isInfinite && !isNaN; // Can be optimized.

  double abs() {
    // Handle negative 0.0.
    if (this == 0.0) return 0.0;
    return this < 0.0 ? -this : this;
  }

  double get sign {
    if (this > 0.0) return 1.0;
    if (this < 0.0) return -1.0;
    return this; // +/-0.0 or NaN.
  }

  int round() => roundToDouble().toInt();
  int floor() => floorToDouble().toInt();
  int ceil() => ceilToDouble().toInt();
  int truncate() => truncateToDouble().toInt();

  double roundToDouble() native "Double_round";
  double floorToDouble() native "Double_floor";
  double ceilToDouble() native "Double_ceil";
  double truncateToDouble() native "Double_truncate";

  double clamp(double lowerLimit, double upperLimit) {
    if (lowerLimit.compareTo(upperLimit) > 0) {
      throw new ArgumentError(lowerLimit as Object);
    }
    if (lowerLimit.isNaN) return lowerLimit;
    if (this.compareTo(lowerLimit) < 0) return lowerLimit;
    if (this.compareTo(upperLimit) > 0) return upperLimit;
    return this;
  }

  int toInt() native "Double_toInt";
  num _toBigintOrDouble() {
    return this;
  }

  double toDouble() {
    return this;
  }

  static const int CACHE_SIZE_LOG2 = 3;
  static const int CACHE_LENGTH = 1 << (CACHE_SIZE_LOG2 + 1);
  static const int CACHE_MASK = CACHE_LENGTH - 1;
  // Each key (double) followed by its toString result.
  static final List _cache = new List(CACHE_LENGTH);
  static int _cacheEvictIndex = 0;

  String _toString() native "Double_toString";

  String toString() {
    if (0.0 == this) {
      return "0.0";
    }
    return _toString();
  }

  String toStringAsFixed(int fractionDigits) {
    // See ECMAScript-262, 15.7.4.5 for details.

   // Step 2.
    if (fractionDigits < 0 || fractionDigits > 20) {
      throw new RangeError.range(fractionDigits, 0, 20, "fractionDigits");
    }

    // Step 3.
    double x = this;

    // Step 4.
    if (isNaN) return "NaN";

    // Step 5 and 6 skipped. Will be dealt with by native function.

    // Step 7.
    if (x >= 1e21 || x <= -1e21) {
      return x.toString();
    }

    return _toStringAsFixed(fractionDigits);
  }

  String _toStringAsFixed(int fractionDigits) native "Double_toStringAsFixed";

  String toStringAsExponential([int fractionDigits = -1]) {
    // See ECMAScript-262, 15.7.4.6 for details.

    // The EcmaScript specification checks for NaN and Infinity before looking
    // at the fractionDigits. In Dart we are consistent with toStringAsFixed and
    // look at the fractionDigits first.

    // Step 7.
      if (fractionDigits < -1  || fractionDigits > 20) {
        throw new RangeError.range(fractionDigits, 0, 20, "fractionDigits");
      }

    if (isNaN) return "NaN";
    if (this == double.INFINITY) return "Infinity";
    if (this == -double.INFINITY) return "-Infinity";

    return _toStringAsExponential(fractionDigits);
  }

  String _toStringAsExponential(int fractionDigits)
      native "Double_toStringAsExponential";

  String toStringAsPrecision(int precision) {
    // See ECMAScript-262, 15.7.4.7 for details.

    // The EcmaScript specification checks for NaN and Infinity before looking
    // at the fractionDigits. In Dart we are consistent with toStringAsFixed and
    // look at the fractionDigits first.

    // Step 8.
    if (precision < 1 || precision > 21) {
      throw new RangeError.range(precision, 1, 21, "precision");
    }

    if (isNaN) return "NaN";
    if (this == double.INFINITY) return "Infinity";
    if (this == -double.INFINITY) return "-Infinity";

    return _toStringAsPrecision(precision);
  }

  String _toStringAsPrecision(int fractionDigits)
      native "Double_toStringAsPrecision";

  // Order is: NaN > Infinity > ... > 0.0 > -0.0 > ... > -Infinity.
  int compareTo(double other) {
    const int EQUAL = 0, LESS = -1, GREATER = 1;
    if (this < other) {
      return LESS;
    } else if (this > other) {
      return GREATER;
    } else if (this == other) {
      if (this == 0.0) {
        bool thisIsNegative = isNegative;
        bool otherIsNegative = other.isNegative;
        if (thisIsNegative == otherIsNegative) {
          return EQUAL;
        }
        return thisIsNegative ? LESS : GREATER;
      } else {
        return EQUAL;
      }
    } else if (isNaN) {
      return other.isNaN ? EQUAL : GREATER;
    } else {
      // Other is NaN.
      return LESS;
    }
  }
}
class _AssertionError extends Error implements AssertionError {
  _AssertionError._create(
      this._failedAssertion, this._url, this._line, this._column, this.message);

  // AssertionError_throwNew in errors.cc fishes the assertion source code
  // out of the script. It expects a Dart stack frame from class
  // _AssertionError. Thus we need a Dart stub that calls the native code.
  static _throwNew(int assertionStart, int assertionEnd, Object message) {
    _doThrowNew(assertionStart, assertionEnd, message);
  }

  static _doThrowNew(int assertionStart, int assertionEnd, Object message)
      native "AssertionError_throwNew";

  static _evaluateAssertion(condition) {
    if (identical(condition, true) || identical(condition, false)) {
      return condition;
    }
    if (condition is _Closure) {
      return condition();
    }
    if (condition is Function) {
      condition = condition();
    }
    return condition;
  }

  String get _messageString {
    if (message == null) return "is not true.";
    if (message is String) return message;
    return Error.safeToString(message);
  }

  String toString() {
    if (_url == null) {
      if (message == null) return _failedAssertion;
      return "'$_failedAssertion': $_messageString";
    }
    var columnInfo = "";
    if (_column > 0) {
      // Only add column information if it is valid.
      columnInfo = " pos $_column";
    }
    return "'$_url': Failed assertion: line $_line$columnInfo: "
        "'$_failedAssertion': $_messageString";
  }

  final String _failedAssertion;
  final String _url;
  final int _line;
  final int _column;
  final Object message;
}
class _TypeError extends _AssertionError implements TypeError {
  _TypeError._create(String url, int line, int column, String errorMsg)
      : super._create("is assignable", url, line, column, errorMsg);

  static _throwNew(int location, Object src_value, _Type dst_type,
      String dst_name, String bound_error_msg) native "TypeError_throwNew";
/*
  static _throwNewIfNotLoaded(
      _LibraryPrefix prefix,
      int location,
      Object src_value,
      _Type dst_type,
      String dst_name,
      String bound_error_msg) {
    if (!prefix.isLoaded()) {
      _throwNew(location, src_value, dst_type, dst_name, bound_error_msg);
    }
  }
*/
  String toString() => super.message;
}
class _EnumHelper {
  String _name;
  String toString() => _name;
  int get hashCode => _name.hashCode;
}
class _InternalError {
  const _InternalError(this._msg);
  String toString() => "InternalError: '${_msg}'";
  final String _msg;
}
class _CompileTimeError extends Error {
  final String _errorMsg;
  _CompileTimeError(this._errorMsg);
  String toString() => _errorMsg;
}
class _Closure implements Function {
  bool operator ==(other) native "Closure_equals";

  int get hashCode native "Closure_hashCode";

  _Closure get call => this;

  _Closure _clone() native "Closure_clone";

  _invoke() native "Closure_invoke"; // Used as a marker.

  // No instance fields should be declared before the following 3 fields whose
  // offsets must be identical in Dart and C++.

  // The following 3 fields are declared both in raw_object.h (for direct access
  // from C++ code) and also here so that the offset-to-field map used by
  // deferred objects is properly initialized.
  // Caution: These fields are not Dart instances, but VM objects.
  // The fields had to be renamed here so that they would be private fields
  // in dart
  // instantiator_ ===> _instantiator
  // function_ ===> _function
  // context_ ===> _context
  var _instantiator;
  var _function;
  var _context;
}
class _GrowableList<T> extends ListBase<T> {
  void insert(int index, T element) {
    if ((index < 0) || (index > length)) {
      throw new RangeError.range(index, 0, length);
    }
    if (index == this.length) {
      add(element);
      return;
    }
    int oldLength = this.length;
    // We are modifying the length just below the is-check. Without the check
    // Array.copy could throw an exception, leaving the list in a bad state
    // (with a length that has been increased, but without a new element).
    if (index is! int) throw new ArgumentError(index);
    this.length++;
    Lists.copy(this, index, this, index + 1, oldLength - index);
    _data[index] = element;
  }

  T removeAt(int index) {
    var result = _data[index];
    int newLength = this.length - 1;
    if (index < newLength) {
      Lists.copy(this, index + 1, this, index, newLength - index);
    }
    this.length = newLength;
    return result;
  }

  bool remove(Object element) {
    for (int i = 0; i < this.length; i++) {
      if (_data[i] == element) {
        removeAt(i);
        return true;
      }
    }
    return false;
  }

  void insertAll(int index, Iterable<T> iterable) {
    if (index < 0 || index > length) {
      throw new RangeError.range(index, 0, length);
    }
    // TODO(floitsch): we can probably detect more cases.
    if (iterable is! List && iterable is! Set && iterable is! SubListIterable) {
      iterable = iterable.toList();
    }
    int insertionLength = iterable.length;
    // There might be errors after the length change, in which case the list
    // will end up being modified but the operation not complete. Unless we
    // always go through a "toList" we can't really avoid that.
    this.length += insertionLength;
    setRange(index + insertionLength, this.length, this, index);
    setAll(index, iterable);
  }

  void setAll(int index, Iterable<T> iterable) {
    if (iterable is List) {
      setRange(index, index + iterable.length, iterable);
    } else {
      for (T element in iterable) {
        _data[index++] = element;
      }
    }
  }

  void removeRange(int start, int end) {
    RangeError.checkValidRange(start, end, this.length);
    Lists.copy(this, end, this, start, this.length - end);
    this.length = this.length - (end - start);
  }

  List<T> sublist(int start, [int end]) {
    end = RangeError.checkValidRange(start, end, this.length);
    int length = end - start;
    if (length == 0) return <T>[];
    List list = new _List(length);
    for (int i = 0; i < length; i++) {
      list[i] = _data[start + i];
    }
    var result = new _GrowableList<T>.withData(list);
    result._setLength(length);
    return result;
  }

  static const int _kDefaultCapacity = 2;

  factory _GrowableList(int length) {
    var data = new _List((length == 0) ? _kDefaultCapacity : length);
    var result = new _GrowableList<T>.withData(data);
    if (length > 0) {
      result._setLength(length);
    }
    return result;
  }

  factory _GrowableList.withCapacity(int capacity) {
    var data = new _List((capacity == 0) ? _kDefaultCapacity : capacity);
    return new _GrowableList<T>.withData(data);
  }

  factory _GrowableList.withData(_List data) native "GrowableList_allocate";

  int get _capacity native "GrowableList_getCapacity";

  int get length native "GrowableList_getLength";

  void set length(int new_length) {
    int old_capacity = _capacity;
    int new_capacity = new_length;
    if (new_length == 0) {
      // Ensure that we use _kDefaultCapacity only when the old_capacity
      // is greater than _kDefaultCapacity otherwise we end up growing the
      // the array.
      if (old_capacity < _kDefaultCapacity) {
        new_capacity = old_capacity;
      } else {
        new_capacity = _kDefaultCapacity;
      }
    }
    if (new_capacity > old_capacity) {
      _grow(new_capacity);
      _setLength(new_length);
      return;
    }
    // We are shrinking. Pick the method which has fewer writes.
    // In the shrink-to-fit path, we write |new_capacity + new_length| words
    // (null init + copy).
    // In the non-shrink-to-fit path, we write |length - new_length| words
    // (null overwrite).
    final bool shouldShrinkToFit =
        (new_capacity + new_length) < (length - new_length);
    if (shouldShrinkToFit) {
      _shrink(new_capacity, new_length);
    } else {
      for (int i = new_length; i < length; i++) {
        _data[i] = null;
      }
    }
    _setLength(new_length);
  }

  void _setLength(int new_length) native "GrowableList_setLength";

  void _setData(_List array) native "GrowableList_setData";

  _List get _data native "GrowableList_getData";

  T operator [](int index) native "GrowableList_getIndexed";

  void operator []=(int index, T value) native "GrowableList_setIndexed";

  // The length of this growable array. It is always less than or equal to the
  // length of the object array, which itself is always greater than 0, so that
  // grow() does not have to check for a zero length object array before
  // doubling its size.
  void add(T value) {
    var len = length;
    if (len == _capacity) {
      _grow(len * 2);
    }
    _setLength(len + 1);
    _data[len] = value;
  }

  void addAll(Iterable<T> iterable) {
    var len = length;
    final cid = ClassID.getID(iterable);
    final isVMList = (cid == ClassID.cidArray) ||
        (cid == ClassID.cidGrowableObjectArray) ||
        (cid == ClassID.cidImmutableArray);
    if (isVMList || (iterable is EfficientLengthIterable)) {
      var cap = _capacity;
      // Pregrow if we know iterable.length.
      var iterLen = iterable.length;
      var newLen = len + iterLen;
      if (newLen > cap) {
        do {
          cap *= 2;
        } while (newLen > cap);
        _grow(cap);
      }
      if (isVMList) {
        if (identical(iterable, this)) {
          throw new ConcurrentModificationError(this);
        }
        this._setLength(newLen);
        for (int i = 0; i < iterLen; i++) {
          _data[len++] = iterable[i];
        }
        return;
      }
    }
    Iterator it = iterable.iterator;
    if (!it.moveNext()) return;
    do {
      while (len < _capacity) {
        int newLen = len + 1;
        this._setLength(newLen);
        _data[len] = it.current;
        if (!it.moveNext()) return;
        if (this.length != newLen) throw new ConcurrentModificationError(this);
        len = newLen;
      }
      _grow(_capacity * 2);
    } while (true);
  }

  T removeLast() {
    var len = length - 1;
    var elem = _data[len];
    this.length = len;
    return elem;
  }

  T get first {
    if (length > 0) return _data[0];
    throw IterableElementError.noElement();
  }

  T get last {
    if (length > 0) return _data[length - 1];
    throw IterableElementError.noElement();
  }

  T get single {
    if (length == 1) return _data[0];
    if (length == 0) throw IterableElementError.noElement();
    throw IterableElementError.tooMany();
    ;
  }

  void _grow(int new_capacity) {
    final _List new_data = new _List(new_capacity);
    for (int i = 0; i < length; i++) {
      new_data[i] = _data[i];
    }
    _setData(new_data);
  }

  void _shrink(int new_capacity, int new_length) {
    final _List new_data = new _List(new_capacity);
    for (int i = 0; i < new_length; i++) {
      new_data[i] = _data[i];
    }
    _setData(new_data);
  }

  // Iterable interface.

  void forEach(f(T element)) {
    int initialLength = length;
    for (int i = 0; i < length; i++) {
      f(_data[i]);
      if (length != initialLength) throw new ConcurrentModificationError(this);
    }
  }

  String join([String separator = ""]) {
    final int length = this.length;
    if (length == 0) return "";
    if (length == 1) return "${_data[0]}";
    if (separator.isNotEmpty) return _joinWithSeparator(separator);
    var i = 0;
    var codeUnitCount = 0;
    while (i < length) {
      final element = _data[i];
      final int cid = ClassID.getID(element);
      // While list contains one-byte strings.
      if (ClassID.cidOneByteString == cid) {
        codeUnitCount += element.length;
        i++;
        // Loop back while strings are one-byte strings.
        continue;
      }
      // Otherwise, never loop back to the outer loop, and
      // handle the remaining strings below.

      // Loop while elements are strings,
      final int firstNonOneByteStringLimit = i;
      var nextElement = element;
      while (nextElement is String) {
        i++;
        if (i == length) {
          return _StringBase._concatRangeNative(this, 0, length);
        }
        nextElement = _data[i];
      }

      // Not all elements are strings, so allocate a new backing array.
      final list = new _List(length);
      for (int copyIndex = 0; copyIndex < i; copyIndex++) {
        list[copyIndex] = _data[copyIndex];
      }
      // Is non-zero if list contains a non-onebyte string.
      var onebyteCanary = i - firstNonOneByteStringLimit;
      while (true) {
        final String elementString = "$nextElement";
        onebyteCanary |=
            (ClassID.getID(elementString) ^ ClassID.cidOneByteString);
        list[i] = elementString;
        codeUnitCount += elementString.length;
        i++;
        if (i == length) break;
        nextElement = _data[i];
      }
      if (onebyteCanary == 0) {
        // All elements returned a one-byte string from toString.
        return _OneByteString._concatAll(list, codeUnitCount);
      }
      return _StringBase._concatRangeNative(list, 0, length);
    }
    // All elements were one-byte strings.
    return _OneByteString._concatAll(this, codeUnitCount);
  }

  String _joinWithSeparator(String separator) {
    StringBuffer buffer = new StringBuffer();
    buffer.write(_data[0]);
    for (int i = 1; i < this.length; i++) {
      buffer.write(separator);
      buffer.write(_data[i]);
    }
    return buffer.toString();
  }

  T elementAt(int index) {
    return _data[index];
  }

  bool get isEmpty {
    return this.length == 0;
  }

  bool get isNotEmpty => !isEmpty;

  void clear() {
    this.length = 0;
  }

  String toString() => ListBase.listToString(this);

  Iterator<T> get iterator {
    return new ListIterator<T>(this);
  }

  List<T> toList({bool growable: true}) {
    var length = this.length;
    if (length > 0) {
      List list = growable ? new _List(length) : new _List<T>(length);
      for (int i = 0; i < length; i++) {
        list[i] = _data[i];
      }
      if (!growable) return list;
      var result = new _GrowableList<T>.withData(list);
      result._setLength(length);
      return result;
    }
    return growable ? <T>[] : new List<T>(0);
  }

  Set<T> toSet() {
    return new Set<T>.from(this);
  }
}
class _ImmutableMap<K, V> implements Map<K, V> {
  final _ImmutableList _kvPairs;

  const _ImmutableMap._create(_ImmutableList keyValuePairs)
      : _kvPairs = keyValuePairs;

  V operator [](Object key) {
    // To preserve the key-value order of the map literal, the keys are
    // not sorted. Need to do linear search or implement an additional
    // lookup table.
    for (int i = 0; i < _kvPairs.length - 1; i += 2) {
      if (key == _kvPairs[i]) {
        return _kvPairs[i + 1];
      }
    }
    return null;
  }

  bool get isEmpty {
    return _kvPairs.length == 0;
  }

  bool get isNotEmpty => !isEmpty;

  int get length {
    return _kvPairs.length ~/ 2;
  }

  void forEach(void f(K key, V value)) {
    for (int i = 0; i < _kvPairs.length; i += 2) {
      f(_kvPairs[i], _kvPairs[i + 1]);
    }
  }

  Iterable<K> get keys {
    return new _ImmutableMapKeyIterable<K>(this);
  }

  Iterable<V> get values {
    return new _ImmutableMapValueIterable<V>(this);
  }

  bool containsKey(Object key) {
    for (int i = 0; i < _kvPairs.length; i += 2) {
      if (key == _kvPairs[i]) {
        return true;
      }
    }
    return false;
  }

  bool containsValue(Object value) {
    for (int i = 1; i < _kvPairs.length; i += 2) {
      if (value == _kvPairs[i]) {
        return true;
      }
    }
    return false;
  }

  void operator []=(K key, V value) {
    throw new UnsupportedError("Cannot set value in unmodifiable Map");
  }

  V putIfAbsent(K key, V ifAbsent()) {
    throw new UnsupportedError("Cannot set value in unmodifiable Map");
  }

  void clear() {
    throw new UnsupportedError("Cannot clear unmodifiable Map");
  }

  V remove(Object key) {
    throw new UnsupportedError("Cannot remove from unmodifiable Map");
  }

  String toString() {
    return Maps.mapToString(this);
  }
}
class _ImmutableMapKeyIterable<E> extends EfficientLengthIterable<E> {
  final _ImmutableMap _map;
  _ImmutableMapKeyIterable(this._map);

  Iterator<E> get iterator {
    return new _ImmutableMapKeyIterator<E>(_map);
  }

  int get length => _map.length;
}
class _ImmutableMapValueIterable<E> extends EfficientLengthIterable<E> {
  final _ImmutableMap _map;
  _ImmutableMapValueIterable(this._map);

  Iterator<E> get iterator {
    return new _ImmutableMapValueIterator<E>(_map);
  }

  int get length => _map.length;
}
class _ImmutableMapKeyIterator<E> implements Iterator<E> {
  _ImmutableMap _map;
  int _index = -1;
  E _current;

  _ImmutableMapKeyIterator(this._map);

  bool moveNext() {
    int newIndex = _index + 1;
    if (newIndex < _map.length) {
      _index = newIndex;
      _current = _map._kvPairs[newIndex * 2];
      return true;
    }
    _current = null;
    _index = _map.length;
    return false;
  }

  E get current => _current;
}
class _ImmutableMapValueIterator<E> implements Iterator<E> {
  _ImmutableMap _map;
  int _index = -1;
  E _current;

  _ImmutableMapValueIterator(this._map);

  bool moveNext() {
    int newIndex = _index + 1;
    if (newIndex < _map.length) {
      _index = newIndex;
      _current = _map._kvPairs[newIndex * 2 + 1];
      return true;
    }
    _current = null;
    _index = _map.length;
    return false;
  }

  E get current => _current;
}
/*
abstract class _IntegerImplementation {
  // The Dart class _Bigint extending _IntegerImplementation requires a
  // default constructor.


  num operator +(num other) {
    var result = other._addFromInteger(this);
    if (result != null) return result;
    return other._toBigint()._addFromInteger(this);
  }

  num operator -(num other) {
    var result = other._subFromInteger(this);
    if (result != null) return result;
    return other._toBigint()._subFromInteger(this);
  }

  num operator *(num other) {
    var result = other._mulFromInteger(this);
    if (result != null) return result;
    return other._toBigint()._mulFromInteger(this);
  }

  num operator ~/(num other) {
    if ((other is int) && (other == 0)) {
      throw const IntegerDivisionByZeroException();
    }
    var result = other._truncDivFromInteger(this);
    if (result != null) return result;
    return other._toBigint()._truncDivFromInteger(this);
  }

  double operator /(int other) {
    return this.toDouble() / other.toDouble();
  }

  num operator %(num other) {
    if ((other is int) && (other == 0)) {
      throw const IntegerDivisionByZeroException();
    }
    var result = other._moduloFromInteger(this);
    if (result != null) return result;
    return other._toBigint()._moduloFromInteger(this);
  }

  int operator -() {
    return 0 - this;
  }

  int operator &(int other) {
    var result = other._bitAndFromInteger(this);
    if (result != null) return result;
    return other._toBigint()._bitAndFromInteger(this);
  }

  int operator |(int other) {
    var result = other._bitOrFromInteger(this);
    if (result != null) return result;
    return other._toBigint()._bitOrFromInteger(this);
  }

  int operator ^(int other) {
    var result = other._bitXorFromInteger(this);
    if (result != null) return result;
    return other._toBigint()._bitXorFromInteger(this);
  }

  num remainder(num other) {
    return other._remainderFromInteger(this);
  }

  int _bitAndFromSmi(int other) native "Integer_bitAndFromInteger";
  int _bitAndFromInteger(int other) native "Integer_bitAndFromInteger";
  int _bitOrFromInteger(int other) native "Integer_bitOrFromInteger";
  int _bitXorFromInteger(int other) native "Integer_bitXorFromInteger";
  int _addFromInteger(int other) native "Integer_addFromInteger";
  int _subFromInteger(int other) native "Integer_subFromInteger";
  int _mulFromInteger(int other) native "Integer_mulFromInteger";
  int _truncDivFromInteger(int other) native "Integer_truncDivFromInteger";
  int _moduloFromInteger(int other) native "Integer_moduloFromInteger";
  int _remainderFromInteger(int other) {
    return other - (other ~/ this) * this;
  }


  int operator >>(int other) {
    var result = other._shrFromInt(this);
    if (result != null) return result;
    return other._toBigint()._shrFromInt(this);
  }

  int operator <<(int other) {
    var result = other._shlFromInt(this);
    if (result != null) return result;
    return other._toBigint()._shlFromInt(this);
  }

  bool operator <(num other) {
    return other > this;
  }

  bool operator >(num other) {
    return other._greaterThanFromInteger(this);
  }

  bool operator >=(num other) {
    return (this == other) || (this > other);
  }

  bool operator <=(num other) {
    return (this == other) || (this < other);
  }

  bool _greaterThanFromInteger(int other)
      native "Integer_greaterThanFromInteger";
  bool operator ==(other) {
    if (other is num) {
      return other._equalToInteger(this);
    }
    return false;
  }

  bool _equalToInteger(int other) native "Integer_equalToInteger";

  int abs() {
    return this < 0 ? -this : this;
  }

  int get sign {
    return (this > 0) ? 1 : (this < 0) ? -1 : 0;
  }

  bool get isEven => ((this & 1) == 0);
  bool get isOdd => !isEven;
  bool get isNaN => false;
  bool get isNegative => this < 0;
  bool get isInfinite => false;
  bool get isFinite => true;

  int toUnsigned(int width) {
    return this & ((1 << width) - 1);
  }

  int toSigned(int width) {
    // The value of binary number weights each bit by a power of two.  The
    // twos-complement value weights the sign bit negatively.  We compute the
    // value of the negative weighting by isolating the sign bit with the
    // correct power of two weighting and subtracting it from the value of the
    // lower bits.
    int signMask = 1 << (width - 1);
    return (this & (signMask - 1)) - (this & signMask);
  }

  int compareTo(num other) {
    const int EQUAL = 0, LESS = -1, GREATER = 1;
    if (other is double) {
      const int MAX_EXACT_INT_TO_DOUBLE = 9007199254740992; // 2^53.
      const int MIN_EXACT_INT_TO_DOUBLE = -MAX_EXACT_INT_TO_DOUBLE;
      double d = other;
      if (d.isInfinite) {
        return d == double.NEGATIVE_INFINITY ? GREATER : LESS;
      }
      if (d.isNaN) {
        return LESS;
      }
      if (MIN_EXACT_INT_TO_DOUBLE <= this && this <= MAX_EXACT_INT_TO_DOUBLE) {
        // Let the double implementation deal with -0.0.
        return -(d.compareTo(this.toDouble()));
      } else {
        // If abs(other) > MAX_EXACT_INT_TO_DOUBLE, then other has an integer
        // value (no bits below the decimal point).
        other = d.toInt();
      }
    }
    if (this < other) {
      return LESS;
    } else if (this > other) {
      return GREATER;
    } else {
      return EQUAL;
    }
  }

  int round() {
    return this;
  }

  int floor() {
    return this;
  }

  int ceil() {
    return this;
  }

  int truncate() {
    return this;
  }

  double roundToDouble() {
    return this.toDouble();
  }

  double floorToDouble() {
    return this.toDouble();
  }

  double ceilToDouble() {
    return this.toDouble();
  }

  double truncateToDouble() {
    return this.toDouble();
  }

  num clamp(num lowerLimit, num upperLimit) {
    if (lowerLimit is! num) {
      throw new ArgumentError.value(lowerLimit, "lowerLimit", "not a number");
    }
    if (upperLimit is! num) {
      throw new ArgumentError.value(upperLimit, "upperLimit", "not a number");
    }

    // Special case for integers.
    if (lowerLimit is int && upperLimit is int && lowerLimit <= upperLimit) {
      if (this < lowerLimit) return lowerLimit;
      if (this > upperLimit) return upperLimit;
      return this;
    }
    // Generic case involving doubles, and invalid integer ranges.
    if (lowerLimit.compareTo(upperLimit) > 0) {
      throw new ArgumentError(lowerLimit);
    }
    if (lowerLimit.isNaN) return lowerLimit;
    // Note that we don't need to care for -0.0 for the lower limit.
    if (this < lowerLimit) return lowerLimit;
    if (this.compareTo(upperLimit) > 0) return upperLimit;
    return this;
  }

  int toInt() {
    return this;
  }

  double toDouble() {
    return new _Double.fromInteger(this);
  }

  int _toBigint() {
    return this;
  }

  num _toBigintOrDouble() {
    return _toBigint();
  }

  String toStringAsFixed(int fractionDigits) {
    return this.toDouble().toStringAsFixed(fractionDigits);
  }

  String toStringAsExponential([int fractionDigits]) {
    return this.toDouble().toStringAsExponential(fractionDigits);
  }

  String toStringAsPrecision(int precision) {
    return this.toDouble().toStringAsPrecision(precision);
  }

  static const _digits = "0123456789abcdefghijklmnopqrstuvwxyz";

  String toRadixString(int radix) {
    if (radix < 2 || 36 < radix) {
      throw new RangeError.range(radix, 2, 36, "radix");
    }
    if (radix & (radix - 1) == 0) {
      return _toPow2String(radix);
    }
    if (radix == 10) return this.toString();
    final bool isNegative = this < 0;
    int value = isNegative ? -this : this;
    List temp = new List();
    do {
      int digit = value % radix;
      value ~/= radix;
      temp.add(_digits.codeUnitAt(digit));
    } while (value > 0);
    if (isNegative) temp.add(0x2d); // '-'.

    _OneByteString string = _OneByteString._allocate(temp.length);
    for (int i = 0, j = temp.length; j > 0; i++) {
      string._setAt(i, temp[--j]);
    }
    return string;
  }

  String _toPow2String(int radix) {
    int value = this;
    if (value == 0) return "0";
    assert(radix & (radix - 1) == 0);
    var negative = value < 0;
    var bitsPerDigit = radix.bitLength - 1;
    var length = 0;
    if (negative) {
      value = -value;
      length = 1;
    }
    // Integer division, rounding up, to find number of _digits.
    length += (value.bitLength + bitsPerDigit - 1) ~/ bitsPerDigit;
    _OneByteString string = _OneByteString._allocate(length);
    string._setAt(0, 0x2d); // '-'. Is overwritten if not negative.
    var mask = radix - 1;
    do {
      string._setAt(--length, _digits.codeUnitAt(value & mask));
      value >>= bitsPerDigit;
    } while (value > 0);
    return string;
  }

  // Returns pow(this, e) % m.
  int modPow(int e, int m) {
    if (e is! int) {
      throw new ArgumentError.value(e, "exponent", "not an integer");
    }
    if (m is! int) {
      throw new ArgumentError.value(m, "modulus", "not an integer");
    }
    if (e < 0) throw new RangeError.range(e, 0, null, "exponent");
    if (m <= 0) throw new RangeError.range(m, 1, null, "modulus");
    if (e == 0) return 1;
    int b = this;
    if (b < 0 || b > m) {
      b %= m;
    }
    int r = 1;
    while (e > 0) {
      if (e.isOdd) {
        r = (r * b) % m;
      }
      e >>= 1;
      b = (b * b) % m;
    }
    return r;
  }

  // If inv is false, returns gcd(x, y).
  // If inv is true and gcd(x, y) = 1, returns d, so that c*x + d*y = 1.
  // If inv is true and gcd(x, y) != 1, throws Exception("Not coprime").
  static int _binaryGcd(int x, int y, bool inv) {
    int s = 0;
    if (!inv) {
      while (x.isEven && y.isEven) {
        x >>= 1;
        y >>= 1;
        s++;
      }
      if (y.isOdd) {
        var t = x;
        x = y;
        y = t;
      }
    }
    final bool ac = x.isEven;
    int u = x;
    int v = y;
    int a = 1, b = 0, c = 0, d = 1;
    do {
      while (u.isEven) {
        u >>= 1;
        if (ac) {
          if (!a.isEven || !b.isEven) {
            a += y;
            b -= x;
          }
          a >>= 1;
        } else if (!b.isEven) {
          b -= x;
        }
        b >>= 1;
      }
      while (v.isEven) {
        v >>= 1;
        if (ac) {
          if (!c.isEven || !d.isEven) {
            c += y;
            d -= x;
          }
          c >>= 1;
        } else if (!d.isEven) {
          d -= x;
        }
        d >>= 1;
      }
      if (u >= v) {
        u -= v;
        if (ac) a -= c;
        b -= d;
      } else {
        v -= u;
        if (ac) c -= a;
        d -= b;
      }
    } while (u != 0);
    if (!inv) return v << s;
    if (v != 1) {
      throw new Exception("Not coprime");
    }
    if (d < 0) {
      d += x;
      if (d < 0) d += x;
    } else if (d > x) {
      d -= x;
      if (d > x) d -= x;
    }
    return d;
  }

  // Returns 1/this % m, with m > 0.
  int modInverse(int m) {
    if (m is! int) {
      throw new ArgumentError.value(m, "modulus", "not an integer");
    }
    if (m <= 0) throw new RangeError.range(m, 1, null, "modulus");
    if (m == 1) return 0;
    int t = this;
    if ((t < 0) || (t >= m)) t %= m;
    if (t == 1) return 1;
    if ((t == 0) || (t.isEven && m.isEven)) {
      throw new Exception("Not coprime");
    }
    return _binaryGcd(m, t, true);
  }

  // Returns gcd of abs(this) and abs(other).
  int gcd(int other) {
    if (other is! int) {
      throw new ArgumentError.value(other, "other", "not an integer");
    }
    int x = this.abs();
    int y = other.abs();
    if (x == 0) return y;
    if (y == 0) return x;
    if ((x == 1) || (y == 1)) return 1;
    return _binaryGcd(x, y, false);
  }
}*/
class _Integer implements int {
  factory _Integer._uninstantiable() {
    throw new UnsupportedError("_Smi can only be allocated by the VM");
  }
  int get hashCode => this;
  int get _identityHashCode => this;
  int operator ~() native "Smi_bitNegate";
  int get bitLength native "Smi_bitLength";

  //int operator &(int other) => other._bitAndFromSmi(this);

  //int _bitAndFromSmi(int other) native "Smi_bitAndFromSmi";
  //int _shrFromInt(int other) native "Smi_shrFromInt";
  //int _shlFromInt(int other) native "Smi_shlFromInt";

  /**
   * The digits of '00', '01', ... '99' as a single array.
   *
   * Get the digits of `n`, with `0 <= n < 100`, as
   * `_digitTable[n * 2]` and `_digitTable[n * 2 + 1]`.
   */
  static final Uint8List _digitTable = buildTable();

  static Uint8List buildTable() {
    final Uint8List table = new Uint8List(200);
    int i = 0;
    table[i++] = 0x30;
    table[i++] = 0x30;
    table[i++] = 0x30;
    table[i++] = 0x31;
    table[i++] = 0x30;
    table[i++] = 0x32;
    table[i++] = 0x30;
    table[i++] = 0x33;
    table[i++] = 0x30;
    table[i++] = 0x34;
    table[i++] = 0x30;
    table[i++] = 0x35;
    table[i++] = 0x30;
    table[i++] = 0x36;
    table[i++] = 0x30;
    table[i++] = 0x37;
    table[i++] = 0x30;
    table[i++] = 0x38;
    table[i++] = 0x30;
    table[i++] = 0x39;
    table[i++] = 0x31;
    table[i++] = 0x30;
    table[i++] = 0x31;
    table[i++] = 0x31;
    table[i++] = 0x31;
    table[i++] = 0x32;
    table[i++] = 0x31;
    table[i++] = 0x33;
    table[i++] = 0x31;
    table[i++] = 0x34;
    table[i++] = 0x31;
    table[i++] = 0x35;
    table[i++] = 0x31;
    table[i++] = 0x36;
    table[i++] = 0x31;
    table[i++] = 0x37;
    table[i++] = 0x31;
    table[i++] = 0x38;
    table[i++] = 0x31;
    table[i++] = 0x39;
    table[i++] = 0x32;
    table[i++] = 0x30;
    table[i++] = 0x32;
    table[i++] = 0x31;
    table[i++] = 0x32;
    table[i++] = 0x32;
    table[i++] = 0x32;
    table[i++] = 0x33;
    table[i++] = 0x32;
    table[i++] = 0x34;
    table[i++] = 0x32;
    table[i++] = 0x35;
    table[i++] = 0x32;
    table[i++] = 0x36;
    table[i++] = 0x32;
    table[i++] = 0x37;
    table[i++] = 0x32;
    table[i++] = 0x38;
    table[i++] = 0x32;
    table[i++] = 0x39;
    table[i++] = 0x33;
    table[i++] = 0x30;
    table[i++] = 0x33;
    table[i++] = 0x31;
    table[i++] = 0x33;
    table[i++] = 0x32;
    table[i++] = 0x33;
    table[i++] = 0x33;
    table[i++] = 0x33;
    table[i++] = 0x34;
    table[i++] = 0x33;
    table[i++] = 0x35;
    table[i++] = 0x33;
    table[i++] = 0x36;
    table[i++] = 0x33;
    table[i++] = 0x37;
    table[i++] = 0x33;
    table[i++] = 0x38;
    table[i++] = 0x33;
    table[i++] = 0x39;
    table[i++] = 0x34;
    table[i++] = 0x30;
    table[i++] = 0x34;
    table[i++] = 0x31;
    table[i++] = 0x34;
    table[i++] = 0x32;
    table[i++] = 0x34;
    table[i++] = 0x33;
    table[i++] = 0x34;
    table[i++] = 0x34;
    table[i++] = 0x34;
    table[i++] = 0x35;
    table[i++] = 0x34;
    table[i++] = 0x36;
    table[i++] = 0x34;
    table[i++] = 0x37;
    table[i++] = 0x34;
    table[i++] = 0x38;
    table[i++] = 0x34;
    table[i++] = 0x39;
    table[i++] = 0x35;
    table[i++] = 0x30;
    table[i++] = 0x35;
    table[i++] = 0x31;
    table[i++] = 0x35;
    table[i++] = 0x32;
    table[i++] = 0x35;
    table[i++] = 0x33;
    table[i++] = 0x35;
    table[i++] = 0x34;
    table[i++] = 0x35;
    table[i++] = 0x35;
    table[i++] = 0x35;
    table[i++] = 0x36;
    table[i++] = 0x35;
    table[i++] = 0x37;
    table[i++] = 0x35;
    table[i++] = 0x38;
    table[i++] = 0x35;
    table[i++] = 0x39;
    table[i++] = 0x36;
    table[i++] = 0x30;
    table[i++] = 0x36;
    table[i++] = 0x31;
    table[i++] = 0x36;
    table[i++] = 0x32;
    table[i++] = 0x36;
    table[i++] = 0x33;
    table[i++] = 0x36;
    table[i++] = 0x34;
    table[i++] = 0x36;
    table[i++] = 0x35;
    table[i++] = 0x36;
    table[i++] = 0x36;
    table[i++] = 0x36;
    table[i++] = 0x37;
    table[i++] = 0x36;
    table[i++] = 0x38;
    table[i++] = 0x36;
    table[i++] = 0x39;
    table[i++] = 0x37;
    table[i++] = 0x30;
    table[i++] = 0x37;
    table[i++] = 0x31;
    table[i++] = 0x37;
    table[i++] = 0x32;
    table[i++] = 0x37;
    table[i++] = 0x33;
    table[i++] = 0x37;
    table[i++] = 0x34;
    table[i++] = 0x37;
    table[i++] = 0x35;
    table[i++] = 0x37;
    table[i++] = 0x36;
    table[i++] = 0x37;
    table[i++] = 0x37;
    table[i++] = 0x37;
    table[i++] = 0x38;
    table[i++] = 0x37;
    table[i++] = 0x39;
    table[i++] = 0x38;
    table[i++] = 0x30;
    table[i++] = 0x38;
    table[i++] = 0x31;
    table[i++] = 0x38;
    table[i++] = 0x32;
    table[i++] = 0x38;
    table[i++] = 0x33;
    table[i++] = 0x38;
    table[i++] = 0x34;
    table[i++] = 0x38;
    table[i++] = 0x35;
    table[i++] = 0x38;
    table[i++] = 0x36;
    table[i++] = 0x38;
    table[i++] = 0x37;
    table[i++] = 0x38;
    table[i++] = 0x38;
    table[i++] = 0x38;
    table[i++] = 0x39;
    table[i++] = 0x39;
    table[i++] = 0x30;
    table[i++] = 0x39;
    table[i++] = 0x31;
    table[i++] = 0x39;
    table[i++] = 0x32;
    table[i++] = 0x39;
    table[i++] = 0x33;
    table[i++] = 0x39;
    table[i++] = 0x34;
    table[i++] = 0x39;
    table[i++] = 0x35;
    table[i++] = 0x39;
    table[i++] = 0x36;
    table[i++] = 0x39;
    table[i++] = 0x37;
    table[i++] = 0x39;
    table[i++] = 0x38;
    table[i++] = 0x39;
    table[i++] = 0x39;
    return table;
  }

  /**
   * Result of int.toString for -99, -98, ..., 98, 99.
   */
  static const List<String> _smallLookupTable = const <String>[
    "-99", "-98", "-97", "-96", "-95", "-94", "-93", "-92", "-91", "-90", //
    "-89", "-88", "-87", "-86", "-85", "-84", "-83", "-82", "-81", "-80", //
    "-79", "-78", "-77", "-76", "-75", "-74", "-73", "-72", "-71", "-70", //
    "-69", "-68", "-67", "-66", "-65", "-64", "-63", "-62", "-61", "-60", //
    "-59", "-58", "-57", "-56", "-55", "-54", "-53", "-52", "-51", "-50", //
    "-49", "-48", "-47", "-46", "-45", "-44", "-43", "-42", "-41", "-40", //
    "-39", "-38", "-37", "-36", "-35", "-34", "-33", "-32", "-31", "-30", //
    "-29", "-28", "-27", "-26", "-25", "-24", "-23", "-22", "-21", "-20", //
    "-19", "-18", "-17", "-16", "-15", "-14", "-13", "-12", "-11", "-10", //
    "-9", "-8", "-7", "-6", "-5", "-4", "-3", "-2", "-1", "0", //
    "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" //
  ];

  // Powers of 10 above 1000000 are indistinguishable by eye.
  static const int _POW_10_7 = 10000000;
  static const int _POW_10_8 = 100000000;
  static const int _POW_10_9 = 1000000000;

  // Find the number of decimal digits in a positive smi.
  // Never called with numbers < 100. These are handled before calling.
  static int _positiveBase10Length(int smi) {
    // A positive smi has length <= 19 if 63-bit,  <=10 if 31-bit.
    // Avoid comparing a 31-bit smi to a non-smi.
    if (smi < 1000) return 3;
    if (smi < 10000) return 4;
    if (smi < _POW_10_7) {
      if (smi < 100000) return 5;
      if (smi < 1000000) return 6;
      return 7;
    }
    if (smi < _POW_10_8) return 8;
    if (smi < _POW_10_9) return 9;
    smi = smi ~/ _POW_10_9;
    // Handle numbers < 100 before calling recursively.
    if (smi < 10) return 10;
    if (smi < 100) return 11;
    return 9 + _positiveBase10Length(smi);
  }

  String toString() {
    if (this < 100 && this > -100) return _smallLookupTable[this + 99];
    if (this < 0) return _negativeToString(this);
    // Inspired by Andrei Alexandrescu: "Three Optimization Tips for C++"
    // Avoid expensive remainder operation by doing it on more than
    // one digit at a time.
    const int DIGIT_ZERO = 0x30;
    int length = _positiveBase10Length(this);
    _OneByteString result = _OneByteString._allocate(length);
    int index = length - 1;
    int smi = this;
    do {
      // Two digits at a time.
      var twoDigits = smi.remainder(100);
      smi = smi ~/ 100;
      int digitIndex = twoDigits * 2;
      result._setAt(index, _digitTable[digitIndex + 1]);
      result._setAt(index - 1, _digitTable[digitIndex]);
      index -= 2;
    } while (smi >= 100);
    if (smi < 10) {
      // Character code for '0'.
      result._setAt(index, DIGIT_ZERO + smi);
    } else {
      // No remainder for this case.
      int digitIndex = smi * 2;
      result._setAt(index, _digitTable[digitIndex + 1]);
      result._setAt(index - 1, _digitTable[digitIndex]);
    }
    return result;
  }

  // Find the number of decimal digits in a negative smi.
  // Never called with numbers > -100. These are handled before calling.
  static int _negativeBase10Length(int negSmi) {
    // A negative smi has length <= 19 if 63-bit, <=10 if 31-bit.
    // Avoid comparing a 31-bit smi to a non-smi.
    if (negSmi > -1000) return 3;
    if (negSmi > -10000) return 4;
    if (negSmi > -_POW_10_7) {
      if (negSmi > -100000) return 5;
      if (negSmi > -1000000) return 6;
      return 7;
    }
    if (negSmi > -_POW_10_8) return 8;
    if (negSmi > -_POW_10_9) return 9;
    negSmi = negSmi ~/ _POW_10_9;
    // Handle numbers > -100 before calling recursively.
    if (negSmi > -10) return 10;
    if (negSmi > -100) return 11;
    return 9 + _negativeBase10Length(negSmi);
  }

  // Convert a negative smi to a string.
  // Doesn't negate the smi to avoid negating the most negative smi, which
  // would become a non-smi.
  static String _negativeToString(int negSmi) {
    // Character code for '-'
    const int MINUS_SIGN = 0x2d;
    // Character code for '0'.
    const int DIGIT_ZERO = 0x30;
    if (negSmi > -10) {
      return _OneByteString._allocate(2)
        .._setAt(0, MINUS_SIGN)
        .._setAt(1, DIGIT_ZERO - negSmi);
    }
    if (negSmi > -100) {
      int digitIndex = 2 * -negSmi;
      return _OneByteString._allocate(3)
        .._setAt(0, MINUS_SIGN)
        .._setAt(1, _digitTable[digitIndex])
        .._setAt(2, _digitTable[digitIndex + 1]);
    }
    // Number of digits, not including minus.
    int digitCount = _negativeBase10Length(negSmi);
    _OneByteString result = _OneByteString._allocate(digitCount + 1);
    result._setAt(0, MINUS_SIGN); // '-'.
    int index = digitCount;
    do {
      var twoDigits = negSmi.remainder(100);
      negSmi = negSmi ~/ 100;
      int digitIndex = -twoDigits * 2;
      result._setAt(index, _digitTable[digitIndex + 1]);
      result._setAt(index - 1, _digitTable[digitIndex]);
      index -= 2;
    } while (negSmi <= -100);
    if (negSmi > -10) {
      result._setAt(index, DIGIT_ZERO - negSmi);
    } else {
      // No remainder necessary for this case.
      int digitIndex = -negSmi * 2;
      result._setAt(index, _digitTable[digitIndex + 1]);
      result._setAt(index - 1, _digitTable[digitIndex]);
    }
    return result;
  }
}


class _InvocationMirror implements Invocation {
  // Constants describing the invocation type.
  // _FIELD cannot be generated by regular invocation mirrors.
  static const int _METHOD = 0;
  static const int _GETTER = 1;
  static const int _SETTER = 2;
  static const int _FIELD = 3;
  static const int _LOCAL_VAR = 4;
  static const int _TYPE_SHIFT = 0;
  static const int _TYPE_BITS = 3;
  static const int _TYPE_MASK = (1 << _TYPE_BITS) - 1;

  // These values, except _DYNAMIC and _SUPER, are only used when throwing
  // NoSuchMethodError for compile-time resolution failures.
  static const int _DYNAMIC = 0;
  static const int _SUPER = 1;
  static const int _STATIC = 2;
  static const int _CONSTRUCTOR = 3;
  static const int _TOP_LEVEL = 4;
  static const int _CALL_SHIFT = _TYPE_BITS;
  static const int _CALL_BITS = 3;
  static const int _CALL_MASK = (1 << _CALL_BITS) - 1;

  // Internal representation of the invocation mirror.
  final String _functionName;
  final List<Object> _argumentsDescriptor;
  final List<Object> _arguments;
  final bool _isSuperInvocation;

  // External representation of the invocation mirror; populated on demand.
  Symbol _memberName;
  int _type = -1;
  List<Object> _positionalArguments;
  Map<Symbol, Object> _namedArguments;

  void _setMemberNameAndType() {
    if (_functionName.startsWith("get:")) {
      _type = _GETTER;
      _memberName = new internal.Symbol.unvalidated(_functionName.substring(4));
    } else if (_functionName.startsWith("set:")) {
      _type = _SETTER;
      _memberName =
          new internal.Symbol.unvalidated(_functionName.substring(4) + "=");
    } else {
      _type = _isSuperInvocation ? (_SUPER << _CALL_SHIFT) | _METHOD : _METHOD;
      _memberName = new internal.Symbol.unvalidated(_functionName);
    }
  }

  Symbol get memberName {
    if (_memberName == null) {
      _setMemberNameAndType();
    }
    return _memberName;
  }

  List get positionalArguments {
    if (_positionalArguments == null) {
      int numPositionalArguments = _argumentsDescriptor[1] as int;
      // Don't count receiver.
      if (numPositionalArguments == 1) {
        return _positionalArguments = const <Object>[];
      }
      // Exclude receiver.
      _positionalArguments =
          new _ImmutableList<Object>._from(_arguments, 1, numPositionalArguments - 1);
    }
    return _positionalArguments;
  }

  Map<Symbol, Object> get namedArguments {
    if (_namedArguments == null) {
      int numArguments = (_argumentsDescriptor[0] as int) - 1; // Exclude receiver.
      int numPositionalArguments = (_argumentsDescriptor[1] as int) - 1;
      int numNamedArguments = numArguments - numPositionalArguments;
      if (numNamedArguments == 0) {
        return _namedArguments = const <Symbol, Object>{};
      }
      _namedArguments = new Map<Symbol, Object>();
      for (int i = 0; i < numNamedArguments; i++) {
        String arg_name = _argumentsDescriptor[2 + 2 * i];
        var arg_value = _arguments[_argumentsDescriptor[3 + 2 * i] as int];
        _namedArguments[new internal.Symbol.unvalidated(arg_name)] = arg_value;
      }
      _namedArguments = new Map<Symbol, Object>.unmodifiable(_namedArguments);
    }
    return _namedArguments;
  }

  bool get isMethod {
    if (_type == -1) {
      _setMemberNameAndType();
    }
    return (_type & _TYPE_MASK) == _METHOD;
  }

  bool get isAccessor {
    if (_type == -1) {
      _setMemberNameAndType();
    }
    return (_type & _TYPE_MASK) != _METHOD;
  }

  bool get isGetter {
    if (_type == -1) {
      _setMemberNameAndType();
    }
    return (_type & _TYPE_MASK) == _GETTER;
  }

  bool get isSetter {
    if (_type == -1) {
      _setMemberNameAndType();
    }
    return (_type & _TYPE_MASK) == _SETTER;
  }

  _InvocationMirror(this._functionName, this._argumentsDescriptor,
      this._arguments, this._isSuperInvocation);

  static _allocateInvocationMirror(String functionName,
      List argumentsDescriptor, List arguments, bool isSuperInvocation) {
    return new _InvocationMirror(
        functionName, argumentsDescriptor, arguments, isSuperInvocation);
  }
}
/*
class _LibraryPrefix {
  bool _load() native "LibraryPrefix_load";
  Object _loadError() native "LibraryPrefix_loadError";
  bool isLoaded() native "LibraryPrefix_isLoaded";
  bool _invalidateDependentCode()
      native "LibraryPrefix_invalidateDependentCode";

  loadLibrary() {
    for (int i = 0; i < _outstandingLoadRequests.length; i++) {
      if (_outstandingLoadRequests[i][0] == this) {
        return _outstandingLoadRequests[i][1].future;
      }
    }

    var completer = new Completer<bool>();
    var pair = new List();
    pair.add(this);
    pair.add(completer);
    _outstandingLoadRequests.add(pair);
    Timer.run(() {
      var hasCompleted = this._load();
      // Loading can complete immediately, for example when the same
      // library has been loaded eagerly or through another deferred
      // prefix. If that is the case, we must invalidate the dependent
      // code and complete the future now since there will be no callback
      // from the VM.
      if (hasCompleted && !completer.isCompleted) {
        _invalidateDependentCode();
        completer.complete(true);
        _outstandingLoadRequests.remove(pair);
      }
    });
    return completer.future;
  }
}
var _outstandingLoadRequests = new List<List>();
_completeDeferredLoads() {
  // Determine which outstanding load requests have completed and complete
  // their completer (with an error or true). For outstanding load requests
  // which have not completed, remember them for next time in
  // stillOutstandingLoadRequests.
  var stillOutstandingLoadRequests = new List<List>();
  var completedLoadRequests = new List<List>();

  // Make a copy of the outstandingRequests because the call to _load below
  // may recursively trigger another call to |_completeDeferredLoads|, which
  // can cause |_outstandingLoadRequests| to be modified.
  var outstandingRequests = _outstandingLoadRequests.toList();
  for (int i = 0; i < outstandingRequests.length; i++) {
    var prefix = outstandingRequests[i][0];
    var completer = outstandingRequests[i][1];
    var error = prefix._loadError();
    if (completer.isCompleted) {
      // Already completed. Skip.
      continue;
    }
    if (error != null) {
      completer.completeError(error);
    } else if (prefix._load()) {
      prefix._invalidateDependentCode();
      completer.complete(true);
    } else {
      stillOutstandingLoadRequests.add(outstandingRequests[i]);
    }
  }
  _outstandingLoadRequests = stillOutstandingLoadRequests;
}*/
class _RegExpHashKey extends LinkedListEntry<_RegExpHashKey> {
  final String pattern;
  final bool multiLine;
  final bool caseSensitive;

  _RegExpHashKey(this.pattern, this.multiLine, this.caseSensitive);

  int get hashCode => pattern.hashCode;
  bool operator ==(_RegExpHashKey that) {
    return (this.pattern == that.pattern) &&
        (this.multiLine == that.multiLine) &&
        (this.caseSensitive == that.caseSensitive);
  }
}
class _RegExpHashValue {
  final _RegExp regexp;
  final _RegExpHashKey key;

  _RegExpHashValue(this.regexp, this.key);
}
class _RegExpMatch implements Match {
  _RegExpMatch(this._regexp, this.input, this._match);

  int get start => _start(0);
  int get end => _end(0);

  int _start(int groupIdx) {
    return _match[(groupIdx * _MATCH_PAIR)];
  }

  int _end(int groupIdx) {
    return _match[(groupIdx * _MATCH_PAIR) + 1];
  }

  String group(int groupIdx) {
    if (groupIdx < 0 || groupIdx > _regexp._groupCount) {
      throw new RangeError.value(groupIdx);
    }
    int startIndex = _start(groupIdx);
    int endIndex = _end(groupIdx);
    if (startIndex == -1) {
      assert(endIndex == -1);
      return null;
    }
    return (input as _StringBase)._substringUnchecked(startIndex, endIndex);
  }

  String operator [](int groupIdx) {
    return this.group(groupIdx);
  }

  List<String> groups(List<int> groupsSpec) {
    var groupsList = new List<String>(groupsSpec.length);
    for (int i = 0; i < groupsSpec.length; i++) {
      groupsList[i] = group(groupsSpec[i]);
    }
    return groupsList;
  }

  int get groupCount => _regexp._groupCount;

  Pattern get pattern => _regexp;

  final _RegExp _regexp;
  final String input;
  final List<int> _match;
  static const int _MATCH_PAIR = 2;
}
class _RegExp implements RegExp {
  factory _RegExp(String pattern,
      {bool multiLine: false,
      bool caseSensitive: true}) native "RegExp_factory";

  Match firstMatch(String str) {
    if (str is! String) throw new ArgumentError(str);
    List match = _ExecuteMatch(str, 0);
    if (match == null) {
      return null;
    }
    return new _RegExpMatch(this, str, match);
  }

  Iterable<Match> allMatches(String string, [int start = 0]) {
    if (string is! String) throw new ArgumentError(string);
    if (0 > start || start > string.length) {
      throw new RangeError.range(start, 0, string.length);
    }
    return new _AllMatchesIterable(this, string, start);
  }

  Match matchAsPrefix(String string, [int start = 0]) {
    if (string is! String) throw new ArgumentError(string);
    if (start < 0 || start > string.length) {
      throw new RangeError.range(start, 0, string.length);
    }
    List<int> list = _ExecuteMatchSticky(string, start);
    if (list == null) return null;
    return new _RegExpMatch(this, string, list);
  }

  bool hasMatch(String str) {
    if (str is! String) throw new ArgumentError(str);
    List match = _ExecuteMatch(str, 0);
    return (match == null) ? false : true;
  }

  String stringMatch(String str) {
    if (str is! String) throw new ArgumentError(str);
    List match = _ExecuteMatch(str, 0);
    if (match == null) {
      return null;
    }
    return str._substringUnchecked(match[0], match[1]);
  }

  String get pattern native "RegExp_getPattern";

  bool get isMultiLine native "RegExp_getIsMultiLine";

  bool get isCaseSensitive native "RegExp_getIsCaseSensitive";

  int get _groupCount native "RegExp_getGroupCount";

  // Byte map of one byte characters with a 0xff if the character is a word
  // character (digit, letter or underscore) and 0x00 otherwise.
  // Used by generated RegExp code.
  static const List<int> _wordCharacterMap = const <int>[
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,

    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, // '0' - '7'
    0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, // '8' - '9'

    0x00, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, // 'A' - 'G'
    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, // 'H' - 'O'
    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, // 'P' - 'W'
    0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0xff, // 'X' - 'Z', '_'

    0x00, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, // 'a' - 'g'
    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, // 'h' - 'o'
    0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, 0xff, // 'p' - 'w'
    0xff, 0xff, 0xff, 0x00, 0x00, 0x00, 0x00, 0x00, // 'x' - 'z'
    // Latin-1 range
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,

    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,

    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,

    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
    0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,
  ];

  List _ExecuteMatch(String str, int start_index) native "RegExp_ExecuteMatch";

  List _ExecuteMatchSticky(String str, int start_index)
      native "RegExp_ExecuteMatchSticky";
}
class _WeakProperty {
  factory _WeakProperty(key, value) => _new(key, value);

  get key => _getKey();
  get value => _getValue();
  set value(value) => _setValue(value);

  static _WeakProperty _new(key, value) native "WeakProperty_new";

  _getKey() native "WeakProperty_getKey";
  _getValue() native "WeakProperty_getValue";
  _setValue(value) native "WeakProperty_setValue";
}
class _AllMatchesIterator implements Iterator<Match> {
  final String _str;
  int _nextIndex;
  _RegExp _re;
  Match _current;

  _AllMatchesIterator(this._re, this._str, this._nextIndex);

  Match get current => _current;

  bool moveNext() {
    if (_re == null) return false; // Cleared after a failed match.
    if (_nextIndex <= _str.length) {
      var match = _re._ExecuteMatch(_str, _nextIndex);
      if (match != null) {
        _current = new _RegExpMatch(_re, _str, match);
        _nextIndex = _current.end;
        if (_nextIndex == _current.start) {
          // Zero-width match. Advance by one more.
          _nextIndex++;
        }
        return true;
      }
    }
    _current = null;
    _re = null;
    return false;
  }
}
class _StackTrace implements StackTrace {
  // toString() is overridden on the C++ side.
}
const int _maxAscii = 0x7f;
const int _maxLatin1 = 0xff;
const int _maxUtf16 = 0xffff;
const int _maxUnicode = 0x10ffff;
/**
 * [_StringBase] contains common methods used by concrete String
 * implementations, e.g., _OneByteString.
 */
abstract class _StringBase implements String {
  // Constants used by replaceAll encoding of string slices between matches.
  // A string slice (start+length) is encoded in a single Smi to save memory
  // overhead in the common case.
  // We use fewer bits for length (11 bits) than for the start index (19+ bits).
  // For long strings, it's possible to have many large indices,
  // but it's unlikely to have many long lengths since slices don't overlap.
  // If there are few matches in a long string, then there are few long slices,
  // and if there are many matches, there'll likely be many short slices.
  //
  // Encoding is: 0((start << _lengthBits) | length)

  // Number of bits used by length.
  // This is the shift used to encode and decode the start index.
  static const int _lengthBits = 11;
  // The maximal allowed length value in an encoded slice.
  static const int _maxLengthValue = (1 << _lengthBits) - 1;
  // Mask of length in encoded smi value.
  static const int _lengthMask = _maxLengthValue;
  static const int _startBits = _maxUnsignedSmiBits - _lengthBits;
  // Maximal allowed start index value in an encoded slice.
  static const int _maxStartValue = (1 << _startBits) - 1;
  // We pick 30 as a safe lower bound on available bits in a negative smi.
  // TODO(lrn): Consider allowing more bits for start on 64-bit systems.
  static const int _maxUnsignedSmiBits = 30;

  // For longer strings, calling into C++ to create the result of a
  // [replaceAll] is faster than [_joinReplaceAllOneByteResult].
  // TODO(lrn): See if this limit can be tweaked.
  static const int _maxJoinReplaceOneByteStringLength = 500;

  factory _StringBase._uninstantiable() {
    throw new UnsupportedError("_StringBase can't be instaniated");
  }

  int get hashCode native "String_getHashCode";

  bool get _isOneByte {
    // Alternatively return false and override it on one-byte string classes.
    int id = ClassID.getID(this);