// JavaScript version
function test(s){
  console.time("substring(js)");
  while (s.length > 1) {
    s = s.substring(1);
  }
  console.timeEnd("substring(js)");
}

// Dart version
test(s) {
  final stopwatch = new Stopwatch()..start();
  while (s.length > 1) {
    s = s.substring(1);
  }
  print("substring(Dart): ${stopwatch.elapsedMilliseconds}ms");
}

$ dart substring.dart
benchmarking with string of length 25000
substring(Dart): 244ms
benchmarking with string of length 50000
substring(Dart): 949ms
benchmarking with string of length 100000
substring(Dart): 3709ms
$ node substring.js
benchmarking with string of length 25000
substring(js): 2.566ms
benchmarking with string of length 50000
substring(js): 2.308ms
benchmarking with string of length 100000
substring(js): 2.633ms

while (s.length > 1) {
  s = s.substring(1);
}

// The String abstract class captures JavaScript string values:
//
// Ecma-262:
//  4.3.16 String Value
//    A string value is a member of the type String and is a finite
//    ordered sequence of zero or more 16-bit unsigned integer values.
//
// All string values have a length field.
class String: public Name {
  // ...
};

// The SeqString abstract class captures sequential string values.
class SeqString: public String {
  // ...
};


// The OneByteString class captures sequential one-byte string objects.
// Each character in the OneByteString is an one-byte character.
class SeqOneByteString: public SeqString {
  // ...
};


// The TwoByteString class captures sequential unicode string objects.
// Each character in the TwoByteString is a two-byte uint16_t.
class SeqTwoByteString: public SeqString {
  // ...
};

// The ConsString class describes string values built by using the
// addition operator on strings.  A ConsString is a pair where the
// first and second components are pointers to other string values.
// One or both components of a ConsString can be pointers to other
// ConsStrings, creating a binary tree of ConsStrings where the leaves
// are non-ConsString string values.  The string value represented by
// a ConsString can be obtained by concatenating the leaf string
// values in a left-to-right depth-first traversal of the tree.
class ConsString: public String {
  // ...
};

// The Sliced String class describes strings that are substrings of another
// sequential string.  The motivation is to save time and memory when creating
// a substring.  A Sliced String is described as a pointer to the parent,
// the offset from the start of the parent string and the length.  Using
// a Sliced String therefore requires unpacking of the parent string and
// adding the offset to the start address.  A substring of a Sliced String
// are not nested since the double indirection is simplified when creating
// such a substring.
// Currently missing features are:
//  - handling externalized parent strings
//  - external strings as parent
//  - truncating sliced string to enable otherwise unneeded parent to be GC'ed.
class SlicedString: public String {
  // ...
};

// The ExternalString class describes string values that are backed by
// a string resource that lies outside the V8 heap.  ExternalStrings
// consist of the length field common to all strings, a pointer to the
// external resource.  It is important to ensure (externally) that the
// resource is not deallocated while the ExternalString is live in the
// V8 heap.
//
// The API expects that all ExternalStrings are created through the
// API.  Therefore, ExternalStrings should not be used internally.
class ExternalString: public String {
  // ...
};


// The ExternalOneByteString class is an external string backed by an
// one-byte string.
class ExternalOneByteString : public ExternalString {
  // ...
};


// The ExternalTwoByteString class is an external string backed by a UTF-16
// encoded string.
class ExternalTwoByteString: public ExternalString {
  // ...
};

function strange() {
  var s = "01234567891011121314";
  for (var i = 0; i < 100000; i++) {
    s += s[Math.floor(s.length / 2)];
  }
  return s;
}

// Note: this a cleaned up version of the original V8 code with some
// unimportant details removed for readablity.
Handle<String> Factory::NewProperSubString(Handle<String> str,
                                           int begin,
                                           int end) {
  // If string is a cons-string produced as a result of concatenations
  // flatten it to have a flat representation.
  str = String::Flatten(str);

  int length = end - begin;
  if (length < SlicedString::kMinLength /* 13 */) {
    // If resulting substring is small then simply allocate a new sequential
    // string and fill it with characters.
    if (str->IsOneByteRepresentation()) {
      Handle<SeqOneByteString> result =
          NewRawOneByteString(length).ToHandleChecked();
      uint8_t* dest = result->GetChars();
      String::WriteToFlat(*str, dest, begin, end);
      return result;
    } else {
      Handle<SeqTwoByteString> result =
          NewRawTwoByteString(length).ToHandleChecked();
      uc16* dest = result->GetChars();
      String::WriteToFlat(*str, dest, begin, end);
      return result;
    }
  }

  // Resulting substring is large enough to warrant sliced-string allocation.
  // Instead of allocating sequential string and copying substring characters
  // allocate a SlicedString object that contains a pointer to the
  // original string, substring start offset and substring length.

  int offset = begin;

  // If input string is a SlicedString itself unwrap it.
  if (str->IsSlicedString()) {
    Handle<SlicedString> slice = Handle<SlicedString>::cast(str);
    str = slice->parent();
    offset += slice->offset();
  }

  // Create a slice.
  Handle<SlicedString> slice = New<SlicedString>(...);
  slice->set_hash_field(String::kEmptyHashField);
  slice->set_length(length);
  slice->set_parent(*str);
  slice->set_offset(offset);
  return slice;
}

class StringSlice /* implements String */ {
  final String parent;
  final int offset;
  final int length;

  StringSlice(this.parent, this.offset, this.length);

  static substring(str, start, [end]) {
    if (end == null) {
      end = str.length;
    } else if (end > str.length) {
      throw "range error: end ${end} is greater than string length ${str.length}";
    }

    if (start < 0 || start >= end) {
      throw "range error: start ${start} is out of range [0, ${end})";
    }

    final length = end - start;
    if (str is StringSlice) {
      start += str.offset;
      str = str.parent;
    }

    return new StringSlice(str, start, length);
  }
}

test(s) {
  final stopwatch = new Stopwatch()..start();
  while (s.length > 1) {
    s = StringSlice.substring(s, 1);
  }
  print("substring(Dart): ${stopwatch.elapsedMilliseconds}ms");
}

$ dart substring.dart
benchmarking with string of length 25000
substring(Dart): 3ms
benchmarking with string of length 50000
substring(Dart): 3ms
benchmarking with string of length 100000
substring(Dart): 1ms

function process(str) {
  var small20CharToken = str.substring(0, 20);
  return {token: small20CharToken};
}

var obj = process(gigantic10GbString);

$re(RegExp reg, [int index]) {
  if (i > currentPos) {
    current = current.substring(i - currentPos);
    currentPos = i;
  }

  Match m = reg.firstMatch(current);
  if (m == null) return null;
  // ... skipped ...
}

function Lexer(str) {
  this.str = str;
  this.idx = 0;
}

Lexer.prototype.nextToken = function () {
  if (this.idx == this.str.length)
    return "eof";
  else if (this.match(/\d+(?!\w)/))
    return "number";
  else if (this.match(/[a-zA-Z_]\w*/)) {
    // note: names can't start with a digit
    return "name";
  } else if (this.match(/\s+/))
    return "space";
  else
    throw "unexpected token";
};

// Try to match the given regexp at the current
// position (this.index) in the string.
// If match succeeds then advance position in the
// string past it and return the match object.
// Otherwise return null.
Lexer.prototype.match = function (re) {
  // ???
};

Lexer.prototype.match = function (re) {
  re.lastIndex = this.idx;
  var m = re.exec(this.str);
  if (m != null) {
    this.idx = re.lastIndex;
  }
  return m;
};

// Note: all regular expressions now need to have
// sticky bit set.
Lexer.prototype.nextToken = function () {
  if (this.idx == this.str.length)
    return "eof";
  else if (this.match(/\d+(?!\w)/y))
    return "number";
  else if (this.match(/[a-zA-Z]\w*/y))
    return "name";
  else if (this.match(/\s+/y))
    return "space";
  else
    throw "unexpected token";
};

Lexer.prototype.match = function (re) {
  re.lastIndex = this.idx;
  var m = re.exec(this.str);

  // No match at all or match at a wrong
  // position
  if (m === null ||
      m.index !== this.idx) {
    return null;
  }

  this.idx = re.lastIndex;
  return m;
};

// Note: all regular expressions now need to have
// global bit set otherwise lastIndex will be
// ignored.
Lexer.prototype.nextToken = function () {
  if (this.idx == this.str.length)
    return "eof";
  else if (this.match(/\d+(?!\w)/g))
    return "number";
  else if (this.match(/[a-zA-Z]\w*/g))
    return "name";
  else if (this.match(/\s+/g))
    return "space";
  else
    throw "unexpected token";
};

// Note: all regexps have irrefutable pattern
// as an alternative "...|()" this guarantees
// that regexp engine won't attempt to match
// this expression at a different position because
// irrefutable pattern always matches.
Lexer.prototype.nextToken = function () {
  if (this.idx == this.str.length)
    return "eof";
  else if (this.match(/\d+(?!\w)|()/g))
    return "number";
  else if (this.match(/[a-zA-Z]\w*|()/g))
    return "name";
  else if (this.match(/\s+|()/g))
    return "space";
  else
    throw "unexpected token";
};

Lexer.prototype.match = function (re) {
  re.lastIndex = this.idx;
  var m = re.exec(this.str);

  // No match at all or an empty match.
  if (m === null || m[0] === "") {
    return null;
  }

  this.idx = re.lastIndex;
  return m;
};

Lexer.prototype.match = function (re) {
  var m = re.exec(this.str);
  if (m !== null) return null;

  // Slice away consumed part of the string.
  this.str = this.str.substring(m[0].length);
  return m;
};

// Note: all regular expressions now need to
// be anchored at the start.
Lexer.prototype.nextToken = function () {
  if (this.str.length === 0)
    return "eof";
  else if (this.match(/^\d+(?!\w)/))
    return "number";
  else if (this.match(/^[a-zA-Z]\w*/))
    return "name";
  else if (this.match(/^\s+/))
    return "space";
  else
    throw "unexpected token";
};

Match matchAsPrefix(String string, [int start = 0]) {
  // ...
  // Inefficient check that searches for a later match too.
  // Change this when possible.
  List<int> list = _ExecuteMatch(string, start);
  if (list == null) return null;
  if (list[0] != start) return null;
  return new _RegExpMatch(this, string, list);
}

# Naive tokenizer that just uses global regexps with lastIndex.
$ node tokenize-global.js
processed 2020001 tokens in 987ms

# Tokenizer that is using a global regexps with an irrefutable pattern
# to prevent searching for regexp match forward.
$ node tokenize-global-irrefutable.js
processed 2020001 tokens in 471ms

# Tokenizer that uses anchored regexps and substring to slice
# away the processed part of the string.
$ node tokenize-substring.js
processed 2020001 tokens in 393ms

# Tokenizer that uses sticky regexps.
$ node tokenize-sticky.js
processed 2020001 tokens in 295ms

function Lexer(str) {
  this.str = str;  // Input string
  this.idx = 0;    // Current position within the input.
  this.tok = null; // Last parsed token type (number, name, space)
  this._tokStart = this._tokEnd = 0;  // Last parsed token position.
}

// Lazy getter for the token value - to avoid allocating substrings
// when not needed.
Object.defineProperty(Lexer.prototype, "val", {
  get: function () {
    return this.str.substring(this._tokStart, this._tokEnd);
  }
});

function isDigit(ch) {
  return 48 /* 0 */ <= ch && ch <= 57 /* 9 */;
}

function isAlpha(ch) {
  ch &= ~32;
  return 65 /* A */ <= ch && ch <= 90 /* Z */;
}

function isIdent(ch) {
  return isAlpha(ch) ||
         isDigit(ch) ||
         ch === 95 /* _ */
}

function isSpace(ch) {
  return ch === 9  /* \t */  ||
         ch === 10 /* \n */  ||
         ch === 13 /* \r */  ||
         ch === 32 /* space */;
}

Lexer.prototype.nextToken = function () {
  if (this.idx >= this.str.length) {
    return "eof";
  }

  this._tokStart = this.idx;
  var ch = this.str.charCodeAt(this.idx++);
  if (isDigit(ch)) {
    while (this.idx < this.str.length &&
           isDigit(this.str.charCodeAt(this.idx))) {
      this.idx++;
    }
    if (this.idx < this.str.length && isIdent(this.str.charCodeAt(this.idx))) {
      throw "unexpected token";
    }
    this.tok = "number";
  } else if (isAlpha(ch) || ch === 95) {
    while (this.idx < this.str.length &&
           isIdent(this.str.charCodeAt(this.idx))) {
      this.idx++;
    }
    this.tok = "name";
  }
  else if (isSpace(ch)) {
    while (this.idx < this.str.length &&
           isSpace(this.str.charCodeAt(this.idx))) {
      this.idx++;
    }
    this.tok = "space";
  }
  else
    throw `unexpected token '${ch}'`;
  this._tokEnd = this.idx;

  return this.tok;
};

function benchmark() {
  var seq = ("aaaaa aaaa ".repeat(50) + "10 ").repeat(10000);
  var l = new Lexer(seq);

  var start = Date.now();
  var cnt = 0;
  do {
    var tok = l.nextToken();
    cnt++;
  } while (tok != "eof");
  var end = Date.now();
  console.log(`processed ${cnt} tokens in ${end - start}ms`);
}

$ node tokenize-manual.js
processed 2020001 tokens in 50ms

$ node tokenize-manual.js
processed 2020001 tokens in 98ms

class Lexer {
  final String str;  /// Input string.
  int idx = 0;  /// Current position within the str.

  Lexer(this.str);

  Token tok;  /// Last processed token type.

  /// Last processed token value.
  String get val => str.substring(_tokStart, _tokEnd);

  /// Beginning and end positions of the last processed token.
  var _tokStart = 0;
  var _tokEnd = 0;

  Token nextToken() {
    if (idx == str.length) return Token.End;

    _tokStart = idx;
    final ch = advance();
    if (isDigit(ch)) {
      while (isDigit(currentChar)) idx++;
      if (isIdent(currentChar)) {
        throw "unexpected token";
      }

      tok = Token.Number;
    } else if (isAlpha(ch) || ch == _) {
      while (isIdent(currentChar)) idx++;
      tok = Token.Name;
    } else if (isSpace(ch)) {
      while (isSpace(currentChar)) idx++;
      tok = Token.Space;
    } else {
      throw "unexpected token";
    }
    _tokEnd = idx;
    return tok;
  }

  int advance() => str.codeUnitAt(idx++);
  int get currentChar => idx < str.length ? str.codeUnitAt(idx) : 0;

  static final ZERO = '0'.codeUnitAt(0);
  static final NINE = '9'.codeUnitAt(0);
  static final A = 'A'.codeUnitAt(0);
  static final Z = 'Z'.codeUnitAt(0);
  static final _ = '_'.codeUnitAt(0);
  static final SPACE = ' '.codeUnitAt(0);
  static final LF = '\n'.codeUnitAt(0);
  static final CR = '\r'.codeUnitAt(0);
  static final TAB = '\t'.codeUnitAt(0);

  static isDigit(ch) => ZERO <= ch && ch <= NINE;

  static isAlpha(ch) {
    ch = ch & ~32;
    return (A <= ch && ch <= Z);
  }

  static isSpace(ch) => ch == SPACE || ch == LF || ch == CR || ch == TAB;

  static isIdent(ch) => isAlpha(ch) || isDigit(ch) || ch == _;
}

enum Token {
  Number, Name, Space, End
}

benchmark() {
  var seq = ("aaaaa aaaa " * 50 + "10 ") * 10000;
  var l = new Lexer(seq);

  final stopwatch = new Stopwatch()..start();
  var tok, val;
  var cnt = 0;
  do {
    tok = l.nextToken();
    val = l.val;  // Force substring allocation.
    cnt++;
  } while (tok != Token.End);
  print('processed ${cnt} tokens in ${stopwatch.elapsedMilliseconds}ms');
  return val;
}

$ dart tokenize.dart
processed 2020001 tokens in 67ms