canonical_tables.h

// 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.

#ifndef RUNTIME_VM_CANONICAL_TABLES_H_
#define RUNTIME_VM_CANONICAL_TABLES_H_

#include "platform/assert.h"
#include "vm/hash_table.h"
#include "vm/object.h"

namespace dart {

template <typename CharType>
class CharArray {
 public:
  CharArray(const CharType* data, intptr_t len) : data_(data), len_(len) {
    hash_ = String::Hash(data, len);
  }
  StringPtr ToSymbol() const {
    String& result = String::Handle(StringFrom(data_, len_, Heap::kOld));
    result.SetCanonical();
    result.SetHash(hash_);
    return result.ptr();
  }
  bool Equals(const String& other) const {
    ASSERT(other.HasHash());
    if (other.Hash() != hash_) {
      return false;
    }
    return other.Equals(data_, len_);
  }
  uword Hash() const { return hash_; }

 private:
  const CharType* data_;
  intptr_t len_;
  uword hash_;
};
typedef CharArray<uint8_t> Latin1Array;
typedef CharArray<uint16_t> UTF16Array;
typedef CharArray<int32_t> UTF32Array;

class StringSlice {
 public:
  StringSlice(const String& str, intptr_t begin_index, intptr_t length)
      : str_(str), begin_index_(begin_index), len_(length) {
    hash_ = is_all() ? str.Hash() : String::Hash(str, begin_index, length);
  }
  StringPtr ToSymbol() const;
  bool Equals(const String& other) const {
    ASSERT(other.HasHash());
    if (other.Hash() != hash_) {
      return false;
    }
    return other.Equals(str_, begin_index_, len_);
  }
  uword Hash() const { return hash_; }

 private:
  bool is_all() const { return begin_index_ == 0 && len_ == str_.Length(); }
  const String& str_;
  intptr_t begin_index_;
  intptr_t len_;
  uword hash_;
};

class ConcatString {
 public:
  ConcatString(const String& str1, const String& str2)
      : str1_(str1), str2_(str2), hash_(String::HashConcat(str1, str2)) {}
  StringPtr ToSymbol() const;
  bool Equals(const String& other) const {
    ASSERT(other.HasHash());
    if (other.Hash() != hash_) {
      return false;
    }
    return other.EqualsConcat(str1_, str2_);
  }
  uword Hash() const { return hash_; }

 private:
  const String& str1_;
  const String& str2_;
  uword hash_;
};

class SymbolTraits {
 public:
  static const char* Name() { return "SymbolTraits"; }
  static bool ReportStats() { return false; }

  static bool IsMatch(const Object& a, const Object& b) {
    const String& a_str = String::Cast(a);
    const String& b_str = String::Cast(b);
    ASSERT(a_str.HasHash());
    ASSERT(b_str.HasHash());
    if (a_str.Hash() != b_str.Hash()) {
      return false;
    }
    intptr_t a_len = a_str.Length();
    if (a_len != b_str.Length()) {
      return false;
    }
    // Use a comparison which does not consider the state of the canonical bit.
    return a_str.Equals(b_str, 0, a_len);
  }
  template <typename CharType>
  static bool IsMatch(const CharArray<CharType>& array, const Object& obj) {
    return array.Equals(String::Cast(obj));
  }
  static bool IsMatch(const StringSlice& slice, const Object& obj) {
    return slice.Equals(String::Cast(obj));
  }
  static bool IsMatch(const ConcatString& concat, const Object& obj) {
    return concat.Equals(String::Cast(obj));
  }
  static uword Hash(const Object& key) { return String::Cast(key).Hash(); }
  template <typename CharType>
  static uword Hash(const CharArray<CharType>& array) {
    return array.Hash();
  }
  static uword Hash(const StringSlice& slice) { return slice.Hash(); }
  static uword Hash(const ConcatString& concat) { return concat.Hash(); }
  template <typename CharType>
  static ObjectPtr NewKey(const CharArray<CharType>& array) {
    return array.ToSymbol();
  }
  static ObjectPtr NewKey(const StringSlice& slice) { return slice.ToSymbol(); }
  static ObjectPtr NewKey(const ConcatString& concat) {
    return concat.ToSymbol();
  }
};

typedef UnorderedHashSet<SymbolTraits, WeakAcqRelStorageTraits>
    CanonicalStringSet;

class CanonicalTypeKey {
 public:
  explicit CanonicalTypeKey(const Type& key) : key_(key) {}
  bool Matches(const Type& arg) const { return key_.Equals(arg); }
  uword Hash() const { return key_.Hash(); }
  const Type& key_;

 private:
  DISALLOW_ALLOCATION();
};

// Traits for looking up Canonical Type based on its hash.
class CanonicalTypeTraits {
 public:
  static const char* Name() { return "CanonicalTypeTraits"; }
  static bool ReportStats() { return false; }

  // Called when growing the table.
  static bool IsMatch(const Object& a, const Object& b) {
    ASSERT(a.IsType() && b.IsType());
    const Type& arg1 = Type::Cast(a);
    const Type& arg2 = Type::Cast(b);
    return arg1.Equals(arg2) && (arg1.Hash() == arg2.Hash());
  }
  static bool IsMatch(const CanonicalTypeKey& a, const Object& b) {
    ASSERT(b.IsType());
    return a.Matches(Type::Cast(b));
  }
  static uword Hash(const Object& key) {
    ASSERT(key.IsType());
    return Type::Cast(key).Hash();
  }
  static uword Hash(const CanonicalTypeKey& key) { return key.Hash(); }
  static ObjectPtr NewKey(const CanonicalTypeKey& obj) {
    return obj.key_.ptr();
  }
};
typedef UnorderedHashSet<CanonicalTypeTraits> CanonicalTypeSet;

class CanonicalFunctionTypeKey {
 public:
  explicit CanonicalFunctionTypeKey(const FunctionType& key) : key_(key) {}
  bool Matches(const FunctionType& arg) const { return key_.Equals(arg); }
  uword Hash() const { return key_.Hash(); }
  const FunctionType& key_;

 private:
  DISALLOW_ALLOCATION();
};

// Traits for looking up Canonical FunctionType based on its hash.
class CanonicalFunctionTypeTraits {
 public:
  static const char* Name() { return "CanonicalFunctionTypeTraits"; }
  static bool ReportStats() { return false; }

  // Called when growing the table.
  static bool IsMatch(const Object& a, const Object& b) {
    ASSERT(a.IsFunctionType() && b.IsFunctionType());
    const FunctionType& arg1 = FunctionType::Cast(a);
    const FunctionType& arg2 = FunctionType::Cast(b);
    return arg1.Equals(arg2) && (arg1.Hash() == arg2.Hash());
  }
  static bool IsMatch(const CanonicalFunctionTypeKey& a, const Object& b) {
    ASSERT(b.IsFunctionType());
    return a.Matches(FunctionType::Cast(b));
  }
  static uword Hash(const Object& key) {
    ASSERT(key.IsFunctionType());
    return FunctionType::Cast(key).Hash();
  }
  static uword Hash(const CanonicalFunctionTypeKey& key) { return key.Hash(); }
  static ObjectPtr NewKey(const CanonicalFunctionTypeKey& obj) {
    return obj.key_.ptr();
  }
};
typedef UnorderedHashSet<CanonicalFunctionTypeTraits> CanonicalFunctionTypeSet;

class CanonicalRecordTypeKey {
 public:
  explicit CanonicalRecordTypeKey(const RecordType& key) : key_(key) {}
  bool Matches(const RecordType& arg) const { return key_.Equals(arg); }
  uword Hash() const { return key_.Hash(); }
  const RecordType& key_;

 private:
  DISALLOW_ALLOCATION();
};

// Traits for looking up Canonical RecordType based on its hash.
class CanonicalRecordTypeTraits {
 public:
  static const char* Name() { return "CanonicalRecordTypeTraits"; }
  static bool ReportStats() { return false; }

  // Called when growing the table.
  static bool IsMatch(const Object& a, const Object& b) {
    ASSERT(a.IsRecordType() && b.IsRecordType());
    const RecordType& arg1 = RecordType::Cast(a);
    const RecordType& arg2 = RecordType::Cast(b);
    return arg1.Equals(arg2) && (arg1.Hash() == arg2.Hash());
  }
  static bool IsMatch(const CanonicalRecordTypeKey& a, const Object& b) {
    ASSERT(b.IsRecordType());
    return a.Matches(RecordType::Cast(b));
  }
  static uword Hash(const Object& key) {
    ASSERT(key.IsRecordType());
    return RecordType::Cast(key).Hash();
  }
  static uword Hash(const CanonicalRecordTypeKey& key) { return key.Hash(); }
  static ObjectPtr NewKey(const CanonicalRecordTypeKey& obj) {
    return obj.key_.ptr();
  }
};
typedef UnorderedHashSet<CanonicalRecordTypeTraits> CanonicalRecordTypeSet;

class CanonicalTypeParameterKey {
 public:
  explicit CanonicalTypeParameterKey(const TypeParameter& key) : key_(key) {}
  bool Matches(const TypeParameter& arg) const { return key_.Equals(arg); }
  uword Hash() const { return key_.Hash(); }
  const TypeParameter& key_;

 private:
  DISALLOW_ALLOCATION();
};

// Traits for looking up Canonical TypeParameter based on its hash.
class CanonicalTypeParameterTraits {
 public:
  static const char* Name() { return "CanonicalTypeParameterTraits"; }
  static bool ReportStats() { return false; }

  // Called when growing the table.
  static bool IsMatch(const Object& a, const Object& b) {
    ASSERT(a.IsTypeParameter() && b.IsTypeParameter());
    const TypeParameter& arg1 = TypeParameter::Cast(a);
    const TypeParameter& arg2 = TypeParameter::Cast(b);
    return arg1.Equals(arg2) && (arg1.Hash() == arg2.Hash());
  }
  static bool IsMatch(const CanonicalTypeParameterKey& a, const Object& b) {
    ASSERT(b.IsTypeParameter());
    return a.Matches(TypeParameter::Cast(b));
  }
  static uword Hash(const Object& key) {
    ASSERT(key.IsTypeParameter());
    return TypeParameter::Cast(key).Hash();
  }
  static uword Hash(const CanonicalTypeParameterKey& key) { return key.Hash(); }
  static ObjectPtr NewKey(const CanonicalTypeParameterKey& obj) {
    return obj.key_.ptr();
  }
};
typedef UnorderedHashSet<CanonicalTypeParameterTraits>
    CanonicalTypeParameterSet;

class CanonicalTypeArgumentsKey {
 public:
  explicit CanonicalTypeArgumentsKey(const TypeArguments& key) : key_(key) {}
  bool Matches(const TypeArguments& arg) const {
    return key_.Equals(arg) && (key_.Hash() == arg.Hash());
  }
  uword Hash() const { return key_.Hash(); }
  const TypeArguments& key_;

 private:
  DISALLOW_ALLOCATION();
};

// Traits for looking up Canonical TypeArguments based on its hash.
class CanonicalTypeArgumentsTraits {
 public:
  static const char* Name() { return "CanonicalTypeArgumentsTraits"; }
  static bool ReportStats() { return false; }

  // Called when growing the table.
  static bool IsMatch(const Object& a, const Object& b) {
    ASSERT(a.IsTypeArguments() && b.IsTypeArguments());
    const TypeArguments& arg1 = TypeArguments::Cast(a);
    const TypeArguments& arg2 = TypeArguments::Cast(b);
    return arg1.Equals(arg2) && (arg1.Hash() == arg2.Hash());
  }
  static bool IsMatch(const CanonicalTypeArgumentsKey& a, const Object& b) {
    ASSERT(b.IsTypeArguments());
    return a.Matches(TypeArguments::Cast(b));
  }
  static uword Hash(const Object& key) {
    ASSERT(key.IsTypeArguments());
    return TypeArguments::Cast(key).Hash();
  }
  static uword Hash(const CanonicalTypeArgumentsKey& key) { return key.Hash(); }
  static ObjectPtr NewKey(const CanonicalTypeArgumentsKey& obj) {
    return obj.key_.ptr();
  }
};
typedef UnorderedHashSet<CanonicalTypeArgumentsTraits>
    CanonicalTypeArgumentsSet;

class MetadataMapTraits {
 public:
  static const char* Name() { return "MetadataMapTraits"; }
  static bool ReportStats() { return false; }
  static bool IsMatch(const Object& a, const Object& b);
  static uword Hash(const Object& key);
};
typedef UnorderedHashMap<MetadataMapTraits> MetadataMap;

class DispatcherKey {
 public:
  DispatcherKey(const String& name,
                const Array& args_desc,
                UntaggedFunction::Kind kind)
      : name_(name), args_desc_(args_desc), kind_(kind) {}
  bool Equals(const Function& other) const {
    return (name_.ptr() == other.name()) &&
           (args_desc_.ptr() == other.saved_args_desc()) &&
           (kind_ == other.kind());
  }
  uword Hash() const { return CombineHashes(name_.Hash(), kind_); }

 private:
  const String& name_;
  const Array& args_desc_;
  UntaggedFunction::Kind kind_;
};

class DispatcherTraits {
 public:
  static const char* Name() { return "DispatcherTraits"; }
  static bool ReportStats() { return false; }

  // Called when growing the table.
  static bool IsMatch(const Object& a, const Object& b) {
    const Function& a_func = Function::Cast(a);
    const Function& b_func = Function::Cast(b);
    return (a_func.name() == b_func.name()) &&
           (a_func.kind() == b_func.kind()) &&
           (a_func.saved_args_desc() == b_func.saved_args_desc());
  }
  static bool IsMatch(const DispatcherKey& key, const Object& obj) {
    return key.Equals(Function::Cast(obj));
  }
  static uword Hash(const Object& key) {
    const Function& func = Function::Cast(key);
    return CombineHashes(String::Hash(func.name()), func.kind());
  }
  static uword Hash(const DispatcherKey& key) { return key.Hash(); }
  static ObjectPtr NewKey(const DispatcherKey& key) { UNREACHABLE(); }
};

typedef UnorderedHashSet<DispatcherTraits, AcqRelStorageTraits> DispatcherSet;

class CanonicalInstanceKey {
 public:
  explicit CanonicalInstanceKey(const Instance& key);
  bool Matches(const Instance& obj) const;
  uword Hash() const;
  const Instance& key_;

 private:
  DISALLOW_ALLOCATION();
};

// Traits for looking up Canonical Instances based on a hash of the fields.
class CanonicalInstanceTraits {
 public:
  static const char* Name() { return "CanonicalInstanceTraits"; }
  static bool ReportStats() { return false; }

  // Called when growing the table.
  static bool IsMatch(const Object& a, const Object& b);
  static bool IsMatch(const CanonicalInstanceKey& a, const Object& b);
  static uword Hash(const Object& key);
  static uword Hash(const CanonicalInstanceKey& key);
  static ObjectPtr NewKey(const CanonicalInstanceKey& obj);
};

typedef UnorderedHashSet<CanonicalInstanceTraits> CanonicalInstancesSet;

struct CanonicalFfiCallbackFunctionTraits {
  static uint32_t Hash(const Object& key) { return Function::Cast(key).Hash(); }
  static const char* Name() { return "CanonicalFfiCallbackFunctionTraits"; }
  static bool IsMatch(const Object& x, const Object& y) {
    const auto& f1 = Function::Cast(x);
    const auto& f2 = Function::Cast(y);
    return (f1.FfiCallbackTarget() == f2.FfiCallbackTarget() &&
            f1.FfiCSignature() == f2.FfiCSignature() &&
            f1.FfiCallbackExceptionalReturn() ==
                f2.FfiCallbackExceptionalReturn() &&
            f1.GetFfiCallbackKind() == f2.GetFfiCallbackKind());
  }
  static bool ReportStats() { return false; }
};

using FfiCallbackFunctionSet =
    UnorderedHashSet<CanonicalFfiCallbackFunctionTraits>;

class RegExpKey {
 public:
  RegExpKey(const String& pattern, RegExpFlags flags)
      : pattern_(pattern), flags_(flags) {}

  bool Equals(const RegExp& other) const {
    return pattern_.Equals(String::Handle(other.pattern())) &&
           (flags_ == other.flags());
  }
  uword Hash() const {
    // Must agree with RegExp::CanonicalizeHash.
    return CombineHashes(pattern_.Hash(), flags_.value());
  }

  const String& pattern_;
  RegExpFlags flags_;

 private:
  DISALLOW_ALLOCATION();
};

class CanonicalRegExpTraits {
 public:
  static const char* Name() { return "CanonicalRegExpTraits"; }
  static bool ReportStats() { return false; }
  static bool IsMatch(const Object& a, const Object& b) {
    return RegExp::Cast(a).CanonicalizeEquals(RegExp::Cast(b));
  }
  static bool IsMatch(const RegExpKey& a, const Object& b) {
    return a.Equals(RegExp::Cast(b));
  }
  static uword Hash(const Object& key) {
    return RegExp::Cast(key).CanonicalizeHash();
  }
  static uword Hash(const RegExpKey& key) { return key.Hash(); }
  static ObjectPtr NewKey(const RegExpKey& key);
};

typedef UnorderedHashSet<CanonicalRegExpTraits, WeakAcqRelStorageTraits>
    CanonicalRegExpSet;

}  // namespace dart

#endif  // RUNTIME_VM_CANONICAL_TABLES_H_