pkg/kernel/lib/type_propagation/canonicalizer.dart

// Copyright (c) 2016, 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 kernel.type_propagation.canonicalizer;

import 'dart:collection';

/// Generates unique consecutive integer IDs for tuples of variable length.
class TupleCanonicalizer {
  final HashMap<List<Object>, int> _table = new HashMap<List<Object>, int>(
      equals: _contentEquals, hashCode: _contentHashCode);
  final List<List<Object>> _canonicalList = <List<Object>>[];
  List<Object> _buffer = [];

  void _push(Object value) {
    _buffer.add(value);
  }

  int _finish() {
    int index = _table[_buffer];
    if (index == null) {
      index = _canonicalList.length;
      _canonicalList.add(_buffer);
      _table[_buffer] = index;
      _buffer = [];
    } else {
      // The item already existed.  Reuse the buffer object for the next query.
      _buffer.clear();
    }
    return index;
  }

  /// Generate or get the ID for a "unary tuple".
  int get1(Object first) {
    _push(first);
    return _finish();
  }

  /// Generate or get the ID for a pair.
  int get2(Object first, Object second) {
    _push(first);
    _push(second);
    return _finish();
  }

  /// Generate or get the ID for a triple.
  int get3(Object first, Object second, Object third) {
    _push(first);
    _push(second);
    _push(third);
    return _finish();
  }

  List<Object> getFromIndex(int index) {
    return _canonicalList[index];
  }

  int get length => _canonicalList.length;

  static bool _contentEquals(List<Object> first, List<Object> second) {
    if (first.length != second.length) return false;
    for (int i = 0; i < first.length; ++i) {
      if (first[i] != second[i]) return false;
    }
    return true;
  }

  static int _contentHashCode(List<Object> list) {
    int hash = 0;
    for (int i = 0; i < list.length; ++i) {
      hash = (hash * 31 + hash ^ list[i].hashCode) & 0x3fffffff;
    }
    return hash;
  }
}

/// Maps uint31 pairs to values of type [T].
class Uint31PairMap<T> {
  final HashMap<int, T> _table = new HashMap<int, T>(hashCode: _bigintHash);
  int _key;

  /// Returns the value associated with the given pair, or `null` if no value
  /// is associated with the pair.
  ///
  /// This association can be changed using a subsequent call to [put].
  T lookup(int x, int y) {
    assert(x >= 0 && x >> 31 == 0);
    assert(y >= 0 && y >> 31 == 0);
    int key = (x << 31) + y;
    _key = key;
    return _table[key];
  }

  /// Associates [value] with the pair previously queried using [lookup].
  void put(T value) {
    _table[_key] = value;
  }

  Iterable<T> get values => _table.values;

  static int _bigintHash(int bigint) {
  	int x = 0x3fffffff & (bigint >> 31);
  	int y = 0x3fffffff & bigint;
    int hash = 0x3fffffff & (x * 1367);
    hash = 0x3fffffff & (y * 31 + hash ^ y);
    hash = 0x3fffffff & ((x ^ y) * 31 + hash ^ y);
    return hash;
  }
}