Runes, a bi-directional code-point iterator/iterable.

sdk/lib/core/string.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.
 
 part of dart.core;
 
 /**
  * The String class represents sequences of characters. Strings are
  * immutable. A string is represented by a sequence of Unicode UTF-16
  * code units accessible through the [codeUnitAt] or the
@@ skipping 262 matching lines @@
   // TODO(floitsch): make it a bidirectional iterator.
   Iterable<int> get codeUnits;
 
   /**
    * Returns an iterable of Unicode code-points of this string.
    *
    * If the string contains surrogate pairs, they will be combined and returned
    * as one integer by this iterator. Unmatched surrogate halves are treated
    * like valid 16-bit code-units.
    */
-  // TODO(floitsch): make it a Runes class.
-  Iterable<int> get runes;
+  Runes get runes;
 
   /**
    * If this string is not already all lower case, returns a new string
    * where all characters are made lower case. Returns [:this:] otherwise.
    */
   // TODO(floitsch): document better. (See EcmaScript for description).
   String toLowerCase();
 
   /**
    * If this string is not already all upper case, returns a new string
    * where all characters are made upper case. Returns [:this:] otherwise.
    */
   // TODO(floitsch): document better. (See EcmaScript for description).
   String toUpperCase();
 }
+
+/**
+ * The runes of a [String].
+ */
+class Runes extends Iterable<int> {
+  final String string;
+  Runes(this.string);
+
+  RuneIterator get iterator => new RuneIterator(string);
+
+  int get first {

[floitsch, 2013/02/12 14:23:10]

You think it's worth specializing "first" ?

[Lasse Reichstein Nielsen, 2013/02/12 15:13:23]

Probably not. Let's drop it.

+    if (string.length == 0) {
+      throw new StateError("No elements.");
+    }
+    int code = string.charCodeAt(0);
+    if (_isLeadSurrogate(code) && string.length > 1) {
+      int nextCode = string.charCodeAt(1);
+      if (_isTrailSurrogate(nextCode)) {
+        return _combineSurrogatePair(code, nextCode);
+      }
+    }
+    return code;
+  }
+
+  int get last {
+    if (string.length == 0) {
+      throw new StateError("No elements.");
+    }
+    int length = string.length;
+    int code = string.charCodeAt(length - 1);
+    if (_isTrailSurrogate(code) && string.length > 1) {
+      int previousCode = string.charCodeAt(length - 2);
+      if (_isLeadSurrogate(previousCode)) {
+        return _combineSurrogatePair(previousCode, code);
+      }
+    }
+    return code;
+  }
+
+}
+
+// Is then code (a 16-bit unsigned integer) a UTF-16 lead surrogate.
+bool _isLeadSurrogate(int code) => (code & 0xFC00) == 0xD800;
+
+// Is then code (a 16-bit unsigned integer) a UTF-16 trail surrogate.
+bool _isTrailSurrogate(int code) => (code & 0xFC00) == 0xDC00;
+
+// Combine a lead and a trail surrogate value into a single code point.
+int _combineSurrogatePair(int start, int end) {
+  return 0x10000 + ((start & 0x3FF) << 10) + (end & 0x3FF);
+}
+
+/** [Iterator] for reading Unicode code points out of a Dart string. */
+class RuneIterator implements BiDirectionalIterator<int> {
+  /** String being iterated. */
+  final String string;
+  /** Position before the current code point. */
+  int _position;
+  /** Position after the current code point. */
+  int _nextPosition;
+  /**
+   * Current code point.
+   *
+   * If the iterator has hit either end, the [_currentCodePoint] is null
+   * and [: _position == _nextPosition :].
+   */
+  int _currentCodePoint;
+
+  /** Create an iterator positioned at the beginning of the string. */
+  RuneIterator(String string)
+      : string = string, _position = 0, _nextPosition = 0;

[floitsch, 2013/02/12 14:23:10]

not necessary, but reads better with "this.string = string".

[Lasse Reichstein Nielsen, 2013/02/12 15:13:23]

Done.

+
+  /**
+   * Create an iterator positioned before the [index]th code unit of the string.
+   *
+   * A [moveNext] will make the following code point the current value, and a

[floitsch, 2013/02/12 14:23:10]

don't use "code point", but "rune".
Not perfect either, but maybe you can get something out of the following
proposed description:
A [moveNext] will make the rune that is positioned at the [index]th code unit
become the current value. A [movePrevious] will make the preceding rune, not
using the code unit at the [index]th position, the current value.

[Lasse Reichstein Nielsen, 2013/02/12 15:13:23]

Reworded.

+   * [movePrevious] will make the preceding code pount the current value.

[floitsch, 2013/02/12 14:23:10]

point.

[Lasse Reichstein Nielsen, 2013/02/12 15:13:23]

Done.

+   *
+   * It is an error if the [index] position is in the middle of a surrogate
+   * pair.
+   */
+  RuneIterator.at(String string, int index)
+      : string = string, _position = index, _nextPosition = index {
+    if (index < 0 || index > string.length) {
+      throw new RangeError.range(index, 0, string.length);
+    }
+    _checkSplitSurrogate(index);
+  }
+
+  /** Throw an error if the index is in the middle of a surrogate pair. */
+  void _checkSplitSurrogate(int index) {
+    if (index > 0 && index < string.length &&
+        _isLeadSurrogate(string.charCodeAt(index - 1)) &&
+        _isTrailSurrogate(string.charCodeAt(index))) {
+      throw new ArgumentError("Index inside surrogate pair: $index");
+    }
+  }
+
+  /**
+   * Returns the starting position of the current rune in the string.
+   *
+   * If the current rune is null, this is the index of the rune that

[floitsch, 2013/02/12 14:23:10]

I would prefer if rawIndex was null or -1 then.

[Lasse Reichstein Nielsen, 2013/02/12 15:13:23]

This way, someone can give you an uninitialized iterator, and you can check
where it will start, and restore it to that position later, without doing any
moves.

[Lasse Reichstein Nielsen, 2013/02/12 15:20:23]

I've changed it to return null anyway, if there is no current rune. It's an easy
change back if someone wants it.

+   * will become current after a call to [moveNext].
+   */
+  int get rawIndex => _position;
+
+  /**
+   * Resets the iterator to the rune at the specified index of the string.
+   *
+   * Setting a negative [rawIndex], or one greater than [:string.length:],

[floitsch, 2013/02/12 14:23:10]

If we allow "string.length" we should maybe allow "-1" too (which would be
equivalent to "reset").

[Lasse Reichstein Nielsen, 2013/02/12 15:13:23]

I'd disallow string.length then. 

Positions in strings (or any sequence) are not of the characters, but of the
fenceposts between characters.
That's why 0..length is allowed in arguments to String.substring.

In this case, because we expect to do a moveNext immediately, I'm all for
disallowing length.

And no, -1 is not the same as reset(0).

[floitsch, 2013/02/13 10:12:19]

*Nobody* except the implementors see it this way. I'm at a position and look at
the "current" character. Then you can move forward or backward. No user should
think of "between characters".
And there it makes more sense, although most users see it as "from (including),
to (excluding)".

+   * is an error. So is setting it in the middle of a surrogate pair.
+   *
+   * Setting the position to the end of then string will set [current] to null.
+   */
+  void set rawIndex(int rawIndex) {
+    reset(rawIndex);
+    moveNext();
+  }
+
+  /**
+   * Resets the iterator to the given index into the string.
+   *
+   * After this the [current] value is unset.
+   * You must call [moveNext] make the rune at the position current,
+   * or [movePrevious] for the last rune before the position.
+   *
+   * Setting a negative [rawIndex], or one greater than [:string.length:],

[floitsch, 2013/02/12 14:23:10]

ditto. Maybe we should allow "-1".

[Lasse Reichstein Nielsen, 2013/02/12 15:13:23]

For what?
reset(0) is a reset to the beginning of the string.
reset(string.length) positions you just after the last rune.
It works here, like <deity> intended indices to work!

[floitsch, 2013/02/13 10:12:19]

If I reset to (0) and then moveNext I don't expect to get a code-unit at
position 0. I just moved away from it!

Currently you allow to set length+1 positions. Basically to every code-unit, and
to the position after the last code-unit. What's missing is the position before
the first code-unit, so that a moveNext brings you to the first position.
And yes: I know you see it differently, but nobody else does.

[Lasse Reichstein Nielsen, 2013/02/13 17:20:42]

That's not how RuneIterator.reset works. 
Are you talking about assigning zero to rawIndex?

There are two ways to set a position:
- setting rawIndex of the character you want to be current.
Valid indices are 0 .. length - 1.
- resetting to a state with no current, but so that the character you want will
be current after a moveNext, or the previous one will be after a movePrevious.
Valid indices are 0 .. length.

This allows reset to position the iterator AT the end of the list (which can't
have a current value), but does not allow setting rawIndex there.

The reset functionality is essential if you need to do something to the
iterator, and then pass it to another function that expects to start with a
moveNext (which is likely to be the case). I like to have this functionality
generalized so that I can reset to any index without a current value - so reset
does that for me.
I changed that to only allowing 0..length - 1, i.e., only indices of actual code
units.
There is no "positions before the first". That is not a position. It has no
rawIndex (now that rawIndex returns null on a newly created iterator).

Setting the iterator so that moveNext hits the first rune, or movePrevious hits
the last rune, means that you can't use setting rawIndex for it, because that
always points to a rune.

I guess we can make special cases for that if you think it's worth it.
Ok, then. How do you want setting rawIndex to work?

For 0..length - 1 it currently set the iterator to a state where current is the
rune starting at the index.

What do you want to happen for length?

What do you want to happen for -1?

Are there any other cases it should cover?

Just say so, and the CL will be in the mail :)

[floitsch, 2013/02/13 17:34:50]

Ok for original behavior for reset (including allowing string.length).

+   * is an error. So is setting it in the middle of a surrogate pair.
+   */
+  void reset([int rawIndex = 0]) {
+    if (rawIndex < 0 || rawIndex > string.length) {
+      throw new RangeError.range(rawIndex, 0, string.length);
+    }
+    _checkSplitSurrogate(rawIndex);
+    _position = _nextPosition = rawIndex;
+    _currentCodePoint = null;
+  }
+
+  /** The rune starting at the current position in the string. */
+  int get current => _currentCodePoint;
+
+  /**
+   * The number of code units comprising the current rune.
+   *
+   * Returns zero if the current rune

[floitsch, 2013/02/12 14:23:10]

unfinished sentence.

[Lasse Reichstein Nielsen, 2013/02/12 15:13:23]

Done.

+   */
+  int get currentSize => _nextPosition - _position;
+
+  /**
+   * A string containing the current rune.
+   *
+   * For runes outside the basic multilingual plane, this will be
+   * a two-character String.
+   *
+   * Returns null if [current] is null.
+   */
+  String get currentAsString {
+    if (_position == _nextPosition) return null;
+    if (_position + 1 == _nextPosition) return string[_position];
+    return string.substring(_position, _nextPosition);
+  }
+
+
+  bool moveNext() {
+    _position = _nextPosition;
+    if (_nextPosition == string.length) {

[floitsch, 2013/02/12 14:23:10]

_position. No need for _nextPosition anymore.

[Lasse Reichstein Nielsen, 2013/02/12 15:13:23]

Done.

+      _currentCodePoint = null;
+      return false;
+    }
+    int codeUnit = string.charCodeAt(_position);
+    int nextPosition = _position + 1;
+    if (_isLeadSurrogate(codeUnit) && nextPosition < string.length) {
+      int nextCodeUnit = string.charCodeAt(nextPosition);
+      if (_isTrailSurrogate(nextCodeUnit)) {
+        _nextPosition = nextPosition + 1;
+        _currentCodePoint = _combineSurrogatePair(codeUnit, nextCodeUnit);
+        return true;
+      }
+    }
+    _nextPosition = nextPosition;
+    _currentCodePoint = codeUnit;
+    return true;
+  }
+
+  bool movePrevious() {
+    _nextPosition = _position;
+    if (_position == 0) {
+      _currentCodePoint = null;
+      return false;
+    }
+    int position = _position - 1;
+    int codeUnit = string.charCodeAt(position);
+    if (_isTrailSurrogate(codeUnit) && position > 0) {
+      int prevCodeUnit = string.charCodeAt(position - 1);
+      if (_isLeadSurrogate(prevCodeUnit)) {
+        _position = position - 1;
+        _currentCodePoint = _combineSurrogatePair(prevCodeUnit, codeUnit);
+        return true;
+      }
+    }
+    _position = position;
+    _currentCodePoint = codeUnit;
+    return true;
+  }
+}