Avoiding creating strings for canonicalization

pkg/front_end/lib/src/fasta/scanner/canonicalizer.dart

+// Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file

[ahe, 2017/02/14 13:52:46]

That comment is so last last last last last year ;-)

[Dmitry Olshansky, 2017/02/14 14:31:09]

Done.

+// 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 fasta.scanner.abstract_scanner;
+
+import 'dart:convert';
+
+class _Node {

[ahe, 2017/02/14 13:52:46]

No need for privacy on classes.

[Dmitry Olshansky, 2017/02/14 14:31:09]

Done.

+  var data; // String or List<int>

[ahe, 2017/02/14 13:52:46]

When I can't give a precise type, I usually do this:

var /* String or List<int> */ data;

[Dmitry Olshansky, 2017/02/14 14:31:09]

Done.

+  int start, end;

[ahe, 2017/02/14 13:52:45]

Could you split this declaration in two?

[Dmitry Olshansky, 2017/02/14 14:31:09]

Done.

+  String payload;
+  _Node next;
+  _Node(this.data, this.start, this.end, this.payload, this.next);
+}
+
+class HashCanonicalizer {

[ahe, 2017/02/14 13:52:45]

I suggest you rename this to StringCanonicalizer.

A small amount of documentation would be nice, for example, what you put in the
CL description.

[Dmitry Olshansky, 2017/02/14 14:31:09]

Done.

+  // Mask away top bits to keep hash calculation within 32-bit SMI range.

[ahe, 2017/02/14 13:52:46]

This is a documentation comment, it should have three slashes.

[Dmitry Olshansky, 2017/02/14 14:31:09]

Done.

+  static const int MASK = 16 * 1024 * 1024 - 1;
+
+  int _size; // Linear size of hash table.

[ahe, 2017/02/14 13:52:46]

No need for privacy.

[ahe, 2017/02/14 13:52:46]

This is also a documentation comment, so it should be formatted like this:

/// Linear size of hash table.
int _size;

Applies to two more below.

[Dmitry Olshansky, 2017/02/14 14:31:09]

On the contrary I believe that direct access to _size from the outside is
dangerous as it could easily destroy the fragile invariant that _nodes.length ==
size and size is power of 2. Also size is not informative to the outside, it
doesn't tell the actual count of items.

+  int _count; // Items in a hash table.
+  _Node _nodes; // The table itself.
+
+  HashCanonicalizer() {
+    _count = 0;

[ahe, 2017/02/14 13:52:46]

Move the field initializers to the field declarations and remove the
constructor.

[Dmitry Olshansky, 2017/02/14 14:31:09]

Done.

+    _size = 8 * 1024;
+    _nodes = new List<_Node>(_size);
+  }
+
+  static String decode(List<int> data, int start, int end, bool asciiOnly) {
+    var s;
+    if (asciiOnly) {
+      s = new String.fromCharCodes(data, start, end);
+    } else {
+      s = UTF8.decoder.convert(data, start, end);

[ahe, 2017/02/14 13:52:46]

You need to change this to:

new Utf8Decoder(allowMalformed: true).convert(data, start, end)

Otherwise this may cause compiler crashes on malformed input.

[Dmitry Olshansky, 2017/02/14 14:31:09]

Done.

+    }
+    return s;
+  }
+
+  static int hashBytes(List<int> data, int start, int end) {
+    int h = 5381;
+    for (int i = start; i < end; i++) {
+      h = ((h << 5) + h + data[i]) & MASK;
+    }
+    return h;
+  }
+
+  static int hashString(String data, int start, int end) {
+    int h = 5381;
+    for (int i = start; i < end; i++) {
+      h = ((h << 5) + h + data.codeUnitAt(i)) & MASK;
+    }
+    return h;
+  }
+
+  _rehash() {

[ahe, 2017/02/14 13:52:46]

No need for privacy.

[Dmitry Olshansky, 2017/02/14 14:31:09]

Done.

+    var newSize = _size * 2;
+    var newNodes = new List<_Node>(newSize);
+    for (int i = 0; i < _size; i++) {
+      _Node t = _nodes[i];
+      while (t != null) {
+        _Node n = t.next;
+        int newIndex = hashBytes(t.data, t.start, t.end) & (newSize - 1);
+        _Node s = newNodes[newIndex];
+        t.next = s;
+        newNodes[newIndex] = t;
+        t = n;
+      }
+    }
+    _size = newSize;
+    _nodes = newNodes;
+  }
+
+  String canonicalize(data, int start, int end, bool asciiOnly) {
+    if (_count > _size) _rehash();
+    int index = data is String
+        ? hashString(data, start, end)
+        : hashBytes(data, start, end);
+    index = index & (_size - 1);
+    _Node s = _nodes[index];
+    _Node t = s;
+    int len = end - start;
+    while (t != null) {
+      if (t.end - t.start == len) {
+        int i = start, j = t.start;
+        while (i < end && data[i] == t.data[j]) {
+          i++;
+          j++;
+        }
+        if (i == end) {
+          return t.payload;
+        }
+      }
+      t = t.next;
+    }
+    String payload;
+    if (data is String)
+      payload = data.substring(start, end);
+    else
+      payload = decode(data, start, end, asciiOnly);
+    _nodes[index] = new _Node(data, start, end, payload, s);
+    _count++;
+    return payload;
+  }
+
+  clear() {
+    _nodes = new List<_Node>(size);
+  }
+}