test.py: First step towards support of caching dart2js compilations across runtimes

tools/testing/dart/utils.dart

 // Copyright (c) 2013, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 library utils;
 
 import 'dart:io';
 import 'dart:async';
 import 'dart:utf' as utf;
 
@@ skipping 46 matching lines @@
     if (_sink != null) {
       _sink.writeln(msg);
     } else {
       print(msg);
     }
   }
 
   static String get _datetime => "${new DateTime.now()}";
 }
 
+
+/**
+ * [areByteArraysEqual] compares a range of bytes from [buffer1] with a
+ * range of bytes from [buffer2].
+ *
+ * Returns [true] if the [count] bytes in [buffer1] (starting at
+ * [offset1]) match the [count] bytes in [buffer2] (starting at
+ * [offset2]).
+ * Otherwise [false] is returned.
+ */
+bool areByteArraysEqual(List<int> buffer1, int offset1,
+                        List<int> buffer2, int offset2,
+                        int count) {
+  if ((offset1 + count) > buffer1.length ||
+      (offset2 + count) > buffer2.length) {
+    return false;
+  }
+
+  for (var i = 0; i < count; i++) {
+    if (buffer1[offset1 + i] != buffer2[offset2 + i]) {
+      return false;
+    }
+  }
+  return true;
+}
+
+/**
+ * [findBytes] searches for [pattern] in [data] beginning at [startPos].
+ *
+ * Returns [true] if [pattern] was found in [data].
+ * Otherwise [false] is returned.
+ */
+int findBytes(List<int> data, List<int> pattern, [int startPos=0]) {
+  // TODO(kustermann): Use one of the fast string-matching algorithms!
+  for (int i = startPos; i < (data.length - pattern.length); i++) {
+    bool found = true;
+    for (int j = 0; j < pattern.length; j++) {
+      if (data[i + j] != pattern[j]) {
+        found = false;
+        break;
+      }
+    }
+    if (found) {
+      return i;
+    }
+  }
+  return -1;
+}
+
 List<int> encodeUtf8(String string) {
   return utf.encodeUtf8(string);
 }
 
 // TODO(kustermann,ricow): As soon we have a debug log we should log
 // invalid utf8-encoded input to the log.
 // Currently invalid bytes will be replaced by a replacement character.
 String decodeUtf8(List<int> bytes) {
   return utf.decodeUtf8(bytes);
 }
 
 // This function is pretty stupid and only puts quotes around an argument if
 // it the argument contains a space.
 String escapeCommandLineArgument(String argument) {
   if (argument.contains(' ')) {
     return '"$argument"';
   }
   return argument;
 }
 
+class HashCodeBuilder {

[ahe, 2015/05/18 15:48:12]

This way of computing a hashCode creates a lot of polymorphism and other kinds
of code that is hard to optimize away. So it is probably rather slow.

I'd suggest a top-level function instead, for example:

int extendHashCode(int hashCode, int other) {
  return ((((hashCode & 0x3FFFFFFF) * 31) & 0x3FFFFFFF) ^ (other & 0x3FFFFFFF))
& 0x3FFFFFFF;
}

Then use this function to compute hash codes like this:

  int computeHashCode() {
    int hashCode = extendHashCode(0, commandLine.hashCode);
    hashCode = extendHashCode(hashCode, displayName.hashCode)
    return hashCode;
  }

Compared to using the builder:

  void _buildHashCode(HashCodeBuilder builder) {
    builder
        ..add(commandLine)
        ..add(displayName);
  }

The advantage of the former is:

* No object allocation in order to compute hashCodes.

* No field access.

* High probability that .hashCode invocations are mono-morphic.

In addition, extendHashCode guarantees that all intermediate computations are
within the 24-bit range (not just the result). This should also be faster.

[kustermann, 2015/05/18 18:31:58]

Agreed, this is sub-optimal and could be optimized.

+  int _value = 0;
+
+  void add(Object object) {
+    _value = ((_value * 31) ^ object.hashCode)  & 0x3FFFFFFF;
+  }
+
+  int get value => _value;
+}
+
+class UniqueObject {
+  static int _nextId = 1;
+  final int _hashCode;
+
+  int get hashCode => _hashCode;
+  operator==(other) => other is UniqueObject && _hashCode == other._hashCode;
+
+  UniqueObject() : _hashCode = ++_nextId;
+}