Create string efficiently from Uint16List/View.

runtime/lib/string_patch.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.
 
+const int _maxAscii = 0x7f;
+const int _maxLatin1 = 0xff;
+const int _maxUtf16 = 0xffff;
+const int _maxUnicode = 0x10ffff;
+
 patch class String {
   /* patch */ factory String.fromCharCodes(Iterable<int> charCodes,
                                            [int start = 0, int end]) {
-    return _StringBase.createFromCharCodes(charCodes, start, end);
+    if (charCodes is! Iterable) throw new ArgumentError.value(charCodes, "charCodes");
+    if (start is! int) throw new ArgumentError.value(start, "start");
+    if (end != null && end is! int) throw new ArgumentError.value(end, "end");
+    return _StringBase.createFromCharCodes(charCodes, start, end, null);
   }
 
   /* patch */ factory String.fromCharCode(int charCode) {
     if (charCode >= 0) {
       if (charCode <= 0xff) {
         return _OneByteString._allocate(1).._setAt(0, charCode);
       }
       if (charCode <= 0xffff) {
         return _StringBase._createFromCodePoints(new _List(1)..[0] = charCode,
                                                  0, 1);
@@ skipping 25 matching lines @@
   factory _StringBase._uninstantiable() {
     throw new UnsupportedError(
         "_StringBase can't be instaniated");
   }
 
   Type get runtimeType => String;
 
   int get hashCode native "String_getHashCode";
 
   /**
-   *  Create the most efficient string representation for specified
-   *  [codePoints].
+   * Create the most efficient string representation for specified
+   * [codePoints].

[siva, 2015/01/20 23:50:26]

The parameter name is not documented correctly, the function has charCodes and
here it is documented as [codePoints].

[Lasse Reichstein Nielsen, 2015/01/22 07:16:32]

Done.

+   *
+   * The [limit] is an upper limit on the character codes in the iterable.
+   * It's `null` if unknown.

[siva, 2015/01/20 23:50:26]

Since limit is documented maybe we should also document start and end.

[Lasse Reichstein Nielsen, 2015/01/22 07:16:33]

Done.

    */
   static String createFromCharCodes(Iterable<int> charCodes,
-                                    int start, int end) {
+                                    int start, int end,
+                                    int limit) {
+    if (start == null) throw new ArgumentError.notNull("start");
     if (charCodes == null) throw new ArgumentError(charCodes);
     // TODO(srdjan): Also skip copying of wide typed arrays.
     final ccid = ClassID.getID(charCodes);
     bool isOneByteString = false;
     if ((ccid != ClassID.cidArray) &&
         (ccid != ClassID.cidGrowableObjectArray) &&
         (ccid != ClassID.cidImmutableArray)) {
       if (charCodes is Uint8List) {
-        isOneByteString = true;
-      } else {
-        // Treat charCodes as Iterable.
-        if (start < 0) throw new RangeError.range(start, 0, charCodes.length);
-        if (end != null && end < start) {
-          throw new RangeError.range(end, start, charCodes.length);
-        }
-        var it = charCodes.iterator;
-        for (int i = 0; i < start; i++) {
-          if (!it.moveNext()) {
-            throw new RangeError.range(start, 0, i);
-          }
-        }
-        int bits = 0;  // Bitwise or of all char codes in list.
-        var list = [];
-        if (end == null) {
-          while (it.moveNext()) {
-            int code = it.current;
-            bits |= code;
-            list.add(code);
-          }
-        } else {
-          for (int i = start; i < end; i++) {
-            if (!it.moveNext()) {
-              throw new RangeError.range(end, start, i);
-            }
-            int code = it.current;
-            bits |= code;
-            list.add(code);
-          }
-        }
-        charCodes = list;
-        isOneByteString = (bits >= 0 && bits <= 0xff);
-        start = 0;
-        end = list.length;
+        end = RangeError.checkValidRange(start, end, charCodes.length);
+        return _createOneByteString(charCodes, start, end - start);
+      } else if (charCodes is! Uint16List) {
+        return _createStringFromIterable(charCodes, start, end);
       }
     }
     int codeCount = charCodes.length;
-    if (start < 0 || start > codeCount) {
-      throw new RangeError.range(start, 0, codeCount);
-    }
-    if (end == null) {
-      end = codeCount;
-    } else if (end < start || end > codeCount) {
-      throw new RangeError.range(end, start, codeCount);
-    }
+    end = RangeError.checkValidRange(start, end, codeCount);
     final len = end - start;
-    if (!isOneByteString) {
-      for (int i = start; i < end; i++) {
-        int e = charCodes[i];
-        if (e is! _Smi) throw new ArgumentError(e);
-        // Is e Latin1?
-        if ((e < 0) || (e > 0xFF)) {
-          return _createFromCodePoints(charCodes, start, end);
-        }
+    if (len == 0) return "";
+    if (limit == null) {
+      limit = _scanCodeUnits(charCodes, start, end);
+      if (limit < 0) {
+        throw new ArgumentError(charCodes);
       }

[siva, 2015/01/20 23:50:26]

the (limit < 0) should be pulled outside the if (limit == null) block to protect
against a negative limit value being passed in to this function.

[Lasse Reichstein Nielsen, 2015/01/22 07:16:32]

While that shouldn't happen (we check that elsewhere), I guess it's better to be
safe.

     }
-    // Allocate a one byte string. When the list is 128 entries or longer,
-    // it's faster to perform a runtime-call.
-    if (len >= 128) {
-      return _OneByteString._allocateFromOneByteList(charCodes, start, end);
+    if (limit <= _maxLatin1) {
+      return _createOneByteString(charCodes, start, len);
     }

[siva, 2015/01/20 23:50:26]

Since you are checking for 'limit' not being < 0 above the optimized path could
also potentially work if charCodes is a Int16List?

[Lasse Reichstein Nielsen, 2015/01/22 07:16:32]

True. I'll consider if it's worth it for another CL.

+    if (limit <= _maxUtf16) {
+      return _TwoByteString._allocateFromTwoByteList(charCodes, start, end);
+    }
+    return _createFromCodePoints(charCodes, start, end);

[siva, 2015/01/20 23:50:26]

The same TODO applies to this call of createFromCodePoints too as limit has
already been computed and can be passed in thus avoiding the need to scan again.

[Lasse Reichstein Nielsen, 2015/01/22 07:16:33]

If we get here, then limit > 0xffff, so there is at least one code point that
need to be converted to a surrogate pair. That means that the next code will
need to scan to count these to find the string length anyway (and see if any
value is not a valid code point, which the limit doesn't show), so the saving
isn't expected to be great - but still, it might be useful, so adding a TODO.

+  }
+
+  static int _scanCodeUnits(List<int> charCodes, int start, int end) {
+    int bits = 0;
+    for (int i = start; i < end; i++) {
+      int code = charCodes[i];
+      if (code is! _Smi) throw new ArgumentError(charCodes);
+      bits |= code;
+    }
+    return bits;
+  }
+
+  static String _createStringFromIterable(Iterable<int> charCodes,
+                                          int start, int end) {
+    // Treat charCodes as Iterable.
+    if (charCodes is EfficientLength) {
+      int length = charCodes.length;
+      end = RangeError.checkValidRange(start, end, length);
+      List charCodeList = new List.from(charCodes.take(end).skip(start),
+                                        growable: false);
+      return createFromCharCodes(charCodeList, 0, charCodeList.length, null);
+    }
+    // Don't know length of iterable, so iterate and see if all the values
+    // are there.
+    if (start < 0) throw new RangeError.range(start, 0, charCodes.length);
+    if (end != null && end < start) {
+      throw new RangeError.range(end, start, charCodes.length);
+    }
+    var it = charCodes.iterator;
+    for (int i = 0; i < start; i++) {
+      if (!it.moveNext()) {
+        throw new RangeError.range(start, 0, i);
+      }
+    }
+    List charCodeList;
+    int bits = 0;  // Bitwise-or of all char codes in list.
+    if (end == null) {
+      var list = [];
+      while (it.moveNext()) {
+        int code = it.current;
+        bits |= code;
+        list.add(code);
+      }
+      charCodeList = makeListFixedLength(list);
+    } else {

[siva, 2015/01/20 23:50:26]

why not move the end < start check here to avoid having to test if end is null
multiple times.

[Lasse Reichstein Nielsen, 2015/01/22 07:16:32]

Done.

+      int len = end - start;
+      var list = new List(len);
+      for (int i = 0; i < len; i++) {
+        if (!it.moveNext()) {
+          throw new RangeError.range(end, start, start + i);
+        }
+        int code = it.current;
+        bits |= code;
+        list[i] = code;
+      }
+      charCodeList = list;
+    }
+    int length = charCodeList.length;
+    if (bits < 0) throw new ArgumentError(charCodes);

[siva, 2015/01/20 23:50:26]

This style of not using a '{' ... '}' seems inconsistent with other parts of
code in this file.

[Lasse Reichstein Nielsen, 2015/01/22 07:16:32]

I use it when it fits on a line, but not consistently. Probably better to be
consistent (and not hide control flow late on a line).

+    bool isOneByteString = (bits <= _maxLatin1);
+    if (isOneByteString) {
+      return _createOneByteString(charCodeList, 0, length);
+    }
+    return createFromCharCodes(charCodeList, 0, length, bits);
+  }
+
+  static String _createOneByteString(List<int> charCodes, int start, int len) {
+    // It's always faster to do this in Dart than to call into the runtime.
     var s = _OneByteString._allocate(len);
     for (int i = 0; i < len; i++) {
       s._setAt(i, charCodes[start + i]);
     }
     return s;
   }
 
+  static String _createTwoByteString(List<int> charCodes, int start, int len) {
+    // TODO(lrn): Create string without scanning charCodes again - all values
+    // in the [start..end] range are uint16 values.
+    return _createFromCodePoints(charCodes, start, end);
+  }
+
   static String _createFromCodePoints(List<int> codePoints, int start, int end)
       native "StringBase_createFromCodePoints";
 
   String operator [](int index) native "String_charAt";
 
   int codeUnitAt(int index) native "String_codeUnitAt";
 
   int get length native "String_getLength";
 
   bool get isEmpty {
@@ skipping 843 matching lines @@
   void _setAt(int index, int codePoint) native "OneByteString_setAt";
 }
 
 
 class _TwoByteString extends _StringBase implements String {
   factory _TwoByteString._uninstantiable() {
     throw new UnsupportedError(
         "_TwoByteString can only be allocated by the VM");
   }
 
+  static String _allocateFromTwoByteList(List list, int start, int end)
+      native "TwoByteString_allocateFromTwoByteList";
+
   bool _isWhitespace(int codeUnit) {
     return _StringBase._isTwoByteWhitespace(codeUnit);
   }
 
   bool operator ==(Object other) {
     return super == other;
   }
 }
 
 
@@ skipping 66 matching lines @@
 class _CodeUnits extends Object with ListMixin<int>,
                                      UnmodifiableListMixin<int> {
   /** The string that this is the code units of. */
   String _string;
 
   _CodeUnits(this._string);
 
   int get length => _string.length;
   int operator[](int i) => _string.codeUnitAt(i);
 }