property/hashable.fz

# This file is part of the Fuzion language implementation.
#
# The Fuzion language implementation is free software: you can redistribute it
# and/or modify it under the terms of the GNU General Public License as published
# by the Free Software Foundation, version 3 of the License.
#
# The Fuzion language implementation is distributed in the hope that it will be
# useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public
# License for more details.
#
# You should have received a copy of the GNU General Public License along with The
# Fuzion language implementation.  If not, see <https://www.gnu.org/licenses/>.


# -----------------------------------------------------------------------
#
#  Tokiwa Software GmbH, Germany
#
#  Source code of Fuzion standard library feature hashable
#
# -----------------------------------------------------------------------

# hashable -- feature for immutable values that have a hash function
#
# NYI: the compiler should check that features inheriting from this are
# actually immutable.
#
public hashable : equatable is


  # create hash code for this instance
  #
  # This should satisfy the following condition:
  #
  #   (T.equality a b) : (T.hash_code a = T.hash_code b)
  #
  public type.hash_code(a hashable.this) u64 => abstract


  # helper for an xxh-style quick hash function.
  #
  # The algorithm used here is a variation of (XXXHash)[https://xxhash.com] as used in
  # (Python's tuple)[https://github.com/python/cpython/blob/849a80ec412c36bbca5d400a7db5645b8cf54f1f/Objects/tupleobject.c#L305]:
  #
  #   we start with a constant `hash_prime5`
  #   for each value:
  #     we take its hash code * `hash_prime2` and add it
  #     then we rotate by `hash_rotate`
  #     and multiply by `hash_prime3`
  #
  module type.xxh_next(# the existing hash code, start with `xxh_first`
                h0 u64,

                # the additional hash code to be incorporated
                h1 u64)
  =>
    h2 := h0 +? h1 *? xxh_prime_2
    h3 := (h2 << xxh_rotate) | (h2 >> (u64 64 - xxh_rotate))
    h3 *? xxh_prime_1


  # Preferred initial value f?r `h0` when calling `xxh_next`.
  #
  module type.xxh_first => xxh_prime_5


  # XXH constants from https://xxhash.com/doc/v0.8.3/group___x_x_h64__impl.html
  #
  type.xxh_prime_1 => u64 0x9E3779B185EBCA87  # factor after each value's hash code was added and result was rotated
  type.xxh_prime_2 => u64 0xC2B2AE3D27D4EB4F  # factor for adding hash code of values
  type.xxh_prime_3 => u64 0x165667B19E3779F9  # not needed here
  type.xxh_prime_4 => u64 0x85EBCA77C2B2AE63  # not needed here
  type.xxh_prime_5 => u64 0x27D4EB2F165667C5  # initial hash used for empty values list
  type.xxh_rotate  => u64 31                  # rotation after adding hash code of values