Introduce Crystal::Hasher for computing a hash value

crystal-lang · Sep 11, 2017 · f9237fd · f9237fd
1 parent 177028e
commit f9237fd
Show file tree

Hide file tree

Showing 39 changed files with 204 additions and 162 deletions.
diff --git a/spec/std/big/big_int_spec.cr b/spec/std/big/big_int_spec.cr
@@ -324,9 +324,12 @@ describe "BigInt" do
   end
 
   it "#hash" do
-    hash = 5.to_big_i.hash
-    hash.should eq(5)
-    typeof(hash).should eq(UInt64)
+    b1 = 5.to_big_i
+    b2 = 5.to_big_i
+    b3 = 6.to_big_i
+
+    b1.hash.should eq(b2.hash)
+    b1.hash.should_not eq(b3.hash)
   end
 
   it "clones" do

diff --git a/spec/std/bool_spec.cr b/spec/std/bool_spec.cr
@@ -28,8 +28,7 @@ describe "Bool" do
   end
 
   describe "hash" do
-    it { true.hash.should eq(1) }
-    it { false.hash.should eq(0) }
+    it { true.hash.should_not eq(false.hash) }
   end
 
   describe "to_s" do

diff --git a/spec/std/enum_spec.cr b/spec/std/enum_spec.cr
@@ -142,7 +142,7 @@ describe Enum do
   end
 
   it "has hash" do
-    SpecEnum::Two.hash.should eq(1.hash)
+    SpecEnum::Two.hash.should_not eq(SpecEnum::Three.hash)
   end
 
   it "parses" do

diff --git a/spec/std/float_spec.cr b/spec/std/float_spec.cr
@@ -206,11 +206,11 @@ describe "Float" do
 
   describe "hash" do
     it "does for Float32" do
-      1.2_f32.hash.should_not eq(0)
+      1.2_f32.hash.should eq(1.2_f32.hash)
     end
 
     it "does for Float64" do
-      1.2.hash.should_not eq(0)
+      1.2.hash.should eq(1.2.hash)
     end
   end
 

diff --git a/spec/std/hash_spec.cr b/spec/std/hash_spec.cr
@@ -146,7 +146,7 @@ describe "Hash" do
     end
 
     it "works with mixed types" do
-      {1 => :a, "a" => 1, 1.0 => "a", :a => 1.0}.values_at(1, "a", 1.0, :a).should eq({:a, 1, "a", 1.0})
+      {1 => :a, "a" => 1, 2.0 => "a", :a => 1.0}.values_at(1, "a", 2.0, :a).should eq({:a, 1, "a", 1.0})
     end
   end
 
@@ -542,14 +542,13 @@ describe "Hash" do
   end
 
   it "computes hash" do
-    h = { {1 => 2} => {3 => 4} }
-    h.hash.should_not eq(h.object_id)
-
+    h1 = { {1 => 2} => {3 => 4} }
     h2 = { {1 => 2} => {3 => 4} }
-    h.hash.should eq(h2.hash)
+    h1.hash.should eq(h2.hash)
 
     h3 = {1 => 2, 3 => 4}
     h4 = {3 => 4, 1 => 2}
+
     h3.hash.should eq(h4.hash)
   end
 

diff --git a/spec/std/named_tuple_spec.cr b/spec/std/named_tuple_spec.cr
@@ -135,7 +135,7 @@ describe "NamedTuple" do
 
   it "computes a hash value" do
     tup1 = {a: 1, b: 'a'}
-    tup1.hash.should_not eq(0)
+    tup1.hash.should eq(tup1.dup.hash)
 
     tup2 = {b: 'a', a: 1}
     tup2.hash.should eq(tup1.hash)

diff --git a/spec/std/proc_spec.cr b/spec/std/proc_spec.cr
@@ -91,7 +91,5 @@ describe "Proc" do
     f2.call('r').should eq(2)
   end
 
-  it "#hash" do
-    ->{ 1 }.hash.should_not eq(0)
-  end
+  typeof(->{ 1 }.hash)
 end
diff --git a/spec/std/struct_spec.cr b/spec/std/struct_spec.cr
@@ -42,11 +42,12 @@ describe "Struct" do
 
   it "does hash" do
     s = StructSpec::TestClass.new(1, "hello")
-    s.hash.should eq(31 + "hello".hash)
+    s.hash.should eq(s.dup.hash)
   end
 
   it "does hash for struct wrapper (#1940)" do
-    StructSpec::BigIntWrapper.new(BigInt.new(0)).hash.should eq(0)
+    s = StructSpec::BigIntWrapper.new(BigInt.new(0))
+    s.hash.should eq(s.dup.hash)
   end
 
   it "does dup" do

diff --git a/spec/std/time/span_spec.cr b/spec/std/time/span_spec.cr
@@ -176,7 +176,9 @@ describe Time::Span do
   end
 
   it "test hash code" do
-    Time::Span.new(77).hash.should eq(77)
+    t1 = Time::Span.new(77)
+    t2 = Time::Span.new(77)
+    t1.hash.should eq(t2.hash)
   end
 
   it "test subtract" do

diff --git a/src/big/big_float.cr b/src/big/big_float.cr
@@ -76,9 +76,8 @@ struct BigFloat < Float
     new(mpf)
   end
 
-  def hash
-    to_f64.hash
-  end
+  # TODO: improve this
+  def_hash to_f64
 
   def self.default_precision
     LibGMP.mpf_get_default_prec

diff --git a/src/big/big_int.cr b/src/big/big_int.cr
@@ -343,9 +343,8 @@ struct BigInt < Int
     io << "_big_i"
   end
 
-  def hash
-    to_u64
-  end
+  # TODO: improve this
+  def_hash to_u64
 
   # Returns a string representation of self.
   #

diff --git a/src/big/big_rational.cr b/src/big/big_rational.cr
@@ -161,9 +161,8 @@ struct BigRational < Number
     BigRational.new { |mpq| LibGMP.mpq_abs(mpq, self) }
   end
 
-  def hash
-    to_f64.hash
-  end
+  # TODO: improve this
+  def_hash to_f64
 
   # Returns the `Float64` representing this rational.
   def to_f

diff --git a/src/bool.cr b/src/bool.cr
@@ -41,9 +41,9 @@ struct Bool
     self != other
   end
 
-  # Returns a hash value for this boolean: 0 for `false`, 1 for `true`.
-  def hash
-    self ? 1 : 0
+  # See `Object#hash(hasher)`
+  def hash(hasher)
+    hasher.bool(self)
   end
 
   # Returns `"true"` for `true` and `"false"` for `false`.

diff --git a/src/char.cr b/src/char.cr
@@ -414,9 +414,9 @@ struct Char
     Unicode.upcase(self, options) { |char| yield char }
   end
 
-  # Returns this char's codepoint.
-  def hash
-    ord
+  # See `Object#hash(hasher)`
+  def hash(hasher)
+    hasher.char(self)
   end
 
   # Returns a Char that is one codepoint bigger than this char's codepoint.

diff --git a/src/class.cr b/src/class.cr
@@ -3,8 +3,9 @@ class Class
     to_s(io)
   end
 
-  def hash
-    crystal_type_id
+  # See `Object#hash(hasher)`
+  def hash(hasher)
+    hasher.class(self)
   end
 
   def ==(other : Class)

diff --git a/src/compiler/crystal/syntax/ast.cr b/src/compiler/crystal/syntax/ast.cr
@@ -1175,9 +1175,7 @@ module Crystal
       self
     end
 
-    def hash
-      0
-    end
+    def_hash
   end
 
   # A qualified identifier.
@@ -1545,9 +1543,7 @@ module Crystal
       Self.new
     end
 
-    def hash
-      0
-    end
+    def_hash
   end
 
   abstract class ControlExpression < ASTNode
@@ -2025,9 +2021,7 @@ module Crystal
       Underscore.new
     end
 
-    def hash
-      0
-    end
+    def_hash
   end
 
   class Splat < UnaryExpression

diff --git a/src/crystal/hasher.cr b/src/crystal/hasher.cr
@@ -0,0 +1,59 @@
+require "crystal/system/random"
+
+# :nodoc:
+struct Crystal::Hasher
+  # Implementation of a Hasher to compute a fast and safe hash
+  # value for primitive and basic Crystal objects. All other
+  # hashes are computed based on these.
+  #
+  # TODO: the implementation is naive and should probably use
+  # another algorithm like SipHash or FNV.
+
+  @@seed = uninitialized UInt64
+  Crystal::System::Random.random_bytes(Slice.new(pointerof(@@seed).as(UInt8*), 8))
+
+  property result : UInt64 = @@seed
+
+  def nil
+    self
+  end
+
+  def bool(value)
+    (value ? 1 : 0).hash(self)
+  end
+
+  def int(value)
+    @result = @result * 31 + value.to_u64
+    self
+  end
+
+  def float(value)
+    @result *= @result * 31 + value.to_f64.unsafe_as(UInt64)
+    self
+  end
+
+  def char(value)
+    value.ord.hash(self)
+  end
+
+  def enum(value)
+    value.value.hash(self)
+  end
+
+  def symbol(value)
+    value.to_i.hash(self)
+  end
+
+  def reference(value)
+    @result = @result * 31 + value.object_id.to_u64
+    self
+  end
+
+  def string(value)
+    value.to_slice.hash(self)
+  end
+
+  def class(value)
+    value.crystal_type_id.hash(self)
+  end
+end
diff --git a/src/enum.cr b/src/enum.cr
@@ -274,9 +274,9 @@ struct Enum
     value == other.value
   end
 
-  # Returns a hash value. This is the hash of the underlying value.
-  def hash
-    value.hash
+  # See `Object#hash(hasher)`
+  def hash(hasher)
+    hasher.enum(self)
   end
 
   # Iterates each values in a Flags Enum.

diff --git a/src/float.cr b/src/float.cr
@@ -86,6 +86,11 @@ struct Float
     end
   end
 
+  # See `Object#hash(hasher)`
+  def hash(hasher)
+    hasher.float(self)
+  end
+
   # Writes this float to the given *io* in the given *format*.
   # See also: `IO#write_bytes`.
   def to_io(io : IO, format : IO::ByteFormat)
@@ -153,10 +158,6 @@ struct Float32
     io << "_f32"
   end
 
-  def hash
-    unsafe_as(Int32)
-  end
-
   def clone
     self
   end
@@ -211,10 +212,6 @@ struct Float64
     Printer.print(self, io)
   end
 
-  def hash
-    unsafe_as(Int64)
-  end
-
   def clone
     self
   end

diff --git a/src/hash.cr b/src/hash.cr
@@ -1,3 +1,5 @@
+require "crystal/hasher"
+
 # A `Hash` represents a mapping of keys to values.
 #
 # See the [official docs](http://crystal-lang.org/docs/syntax_and_semantics/literals/hash.html) for the basics.
@@ -706,18 +708,20 @@ class Hash(K, V)
     true
   end
 
-  # See also: `Object#hash`.
-  #
-  # ```
-  # foo = {"foo" => "bar"}
-  # foo.hash # => 3247054
-  # ```
-  def hash
-    hash = size
+  # See `Object#hash(hasher)`
+  def hash(hasher)
+    # The hash value must be the same regardless of the
+    # order of the keys.
+    result = hasher.result
+
     each do |key, value|
-      hash += key.hash ^ value.hash
+      copy = hasher
+      copy = key.hash(copy)
+      copy = value.hash(copy)
+      result += copy.result
     end
-    hash
+
+    result.hash(hasher)
   end
 
   # Duplicates a `Hash`.
@@ -864,7 +868,7 @@ class Hash(K, V)
   end
 
   private def bucket_index(key)
-    key.hash.to_u32.remainder(@buckets_size).to_i
+    key.hash.remainder(@buckets_size).to_i
   end
 
   private def calculate_new_size(size)

diff --git a/src/http/headers.cr b/src/http/headers.cr
@@ -9,13 +9,11 @@ struct HTTP::Headers
   record Key, name : String do
     forward_missing_to @name
 
-    def hash
-      h = 0
+    def hash(hasher)
       name.each_byte do |c|
-        c = normalize_byte(c)
-        h = 31 * h + c
+        hasher = normalize_byte(c).hash(hasher)
       end
-      h
+      hasher
     end
 
     def ==(key2)