Source file src/hash/maphash/maphash_test.go

     1  // Copyright 2019 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package maphash
     6  
     7  import (
     8  	"bytes"
     9  	"fmt"
    10  	"hash"
    11  	"internal/asan"
    12  	"math"
    13  	"reflect"
    14  	"strings"
    15  	"testing"
    16  	"unsafe"
    17  )
    18  
    19  func TestUnseededHash(t *testing.T) {
    20  	m := map[uint64]struct{}{}
    21  	for i := 0; i < 1000; i++ {
    22  		h := new(Hash)
    23  		m[h.Sum64()] = struct{}{}
    24  	}
    25  	if len(m) < 900 {
    26  		t.Errorf("empty hash not sufficiently random: got %d, want 1000", len(m))
    27  	}
    28  }
    29  
    30  func TestSeededHash(t *testing.T) {
    31  	s := MakeSeed()
    32  	m := map[uint64]struct{}{}
    33  	for i := 0; i < 1000; i++ {
    34  		h := new(Hash)
    35  		h.SetSeed(s)
    36  		m[h.Sum64()] = struct{}{}
    37  	}
    38  	if len(m) != 1 {
    39  		t.Errorf("seeded hash is random: got %d, want 1", len(m))
    40  	}
    41  }
    42  
    43  func TestHashGrouping(t *testing.T) {
    44  	b := bytes.Repeat([]byte("foo"), 100)
    45  	hh := make([]*Hash, 7)
    46  	for i := range hh {
    47  		hh[i] = new(Hash)
    48  	}
    49  	for _, h := range hh[1:] {
    50  		h.SetSeed(hh[0].Seed())
    51  	}
    52  	hh[0].Write(b)
    53  	hh[1].WriteString(string(b))
    54  
    55  	writeByte := func(h *Hash, b byte) {
    56  		err := h.WriteByte(b)
    57  		if err != nil {
    58  			t.Fatalf("WriteByte: %v", err)
    59  		}
    60  	}
    61  	writeSingleByte := func(h *Hash, b byte) {
    62  		_, err := h.Write([]byte{b})
    63  		if err != nil {
    64  			t.Fatalf("Write single byte: %v", err)
    65  		}
    66  	}
    67  	writeStringSingleByte := func(h *Hash, b byte) {
    68  		_, err := h.WriteString(string([]byte{b}))
    69  		if err != nil {
    70  			t.Fatalf("WriteString single byte: %v", err)
    71  		}
    72  	}
    73  
    74  	for i, x := range b {
    75  		writeByte(hh[2], x)
    76  		writeSingleByte(hh[3], x)
    77  		if i == 0 {
    78  			writeByte(hh[4], x)
    79  		} else {
    80  			writeSingleByte(hh[4], x)
    81  		}
    82  		writeStringSingleByte(hh[5], x)
    83  		if i == 0 {
    84  			writeByte(hh[6], x)
    85  		} else {
    86  			writeStringSingleByte(hh[6], x)
    87  		}
    88  	}
    89  
    90  	sum := hh[0].Sum64()
    91  	for i, h := range hh {
    92  		if sum != h.Sum64() {
    93  			t.Errorf("hash %d not identical to a single Write", i)
    94  		}
    95  	}
    96  
    97  	if sum1 := Bytes(hh[0].Seed(), b); sum1 != hh[0].Sum64() {
    98  		t.Errorf("hash using Bytes not identical to a single Write")
    99  	}
   100  
   101  	if sum1 := String(hh[0].Seed(), string(b)); sum1 != hh[0].Sum64() {
   102  		t.Errorf("hash using String not identical to a single Write")
   103  	}
   104  }
   105  
   106  func TestHashBytesVsString(t *testing.T) {
   107  	s := "foo"
   108  	b := []byte(s)
   109  	h1 := new(Hash)
   110  	h2 := new(Hash)
   111  	h2.SetSeed(h1.Seed())
   112  	n1, err1 := h1.WriteString(s)
   113  	if n1 != len(s) || err1 != nil {
   114  		t.Fatalf("WriteString(s) = %d, %v, want %d, nil", n1, err1, len(s))
   115  	}
   116  	n2, err2 := h2.Write(b)
   117  	if n2 != len(b) || err2 != nil {
   118  		t.Fatalf("Write(b) = %d, %v, want %d, nil", n2, err2, len(b))
   119  	}
   120  	if h1.Sum64() != h2.Sum64() {
   121  		t.Errorf("hash of string and bytes not identical")
   122  	}
   123  }
   124  
   125  func TestHashHighBytes(t *testing.T) {
   126  	// See issue 34925.
   127  	const N = 10
   128  	m := map[uint64]struct{}{}
   129  	for i := 0; i < N; i++ {
   130  		h := new(Hash)
   131  		h.WriteString("foo")
   132  		m[h.Sum64()>>32] = struct{}{}
   133  	}
   134  	if len(m) < N/2 {
   135  		t.Errorf("from %d seeds, wanted at least %d different hashes; got %d", N, N/2, len(m))
   136  	}
   137  }
   138  
   139  func TestRepeat(t *testing.T) {
   140  	h1 := new(Hash)
   141  	h1.WriteString("testing")
   142  	sum1 := h1.Sum64()
   143  
   144  	h1.Reset()
   145  	h1.WriteString("testing")
   146  	sum2 := h1.Sum64()
   147  
   148  	if sum1 != sum2 {
   149  		t.Errorf("different sum after resetting: %#x != %#x", sum1, sum2)
   150  	}
   151  
   152  	h2 := new(Hash)
   153  	h2.SetSeed(h1.Seed())
   154  	h2.WriteString("testing")
   155  	sum3 := h2.Sum64()
   156  
   157  	if sum1 != sum3 {
   158  		t.Errorf("different sum on the same seed: %#x != %#x", sum1, sum3)
   159  	}
   160  }
   161  
   162  func TestSeedFromSum64(t *testing.T) {
   163  	h1 := new(Hash)
   164  	h1.WriteString("foo")
   165  	x := h1.Sum64() // seed generated here
   166  	h2 := new(Hash)
   167  	h2.SetSeed(h1.Seed())
   168  	h2.WriteString("foo")
   169  	y := h2.Sum64()
   170  	if x != y {
   171  		t.Errorf("hashes don't match: want %x, got %x", x, y)
   172  	}
   173  }
   174  
   175  func TestSeedFromSeed(t *testing.T) {
   176  	h1 := new(Hash)
   177  	h1.WriteString("foo")
   178  	_ = h1.Seed() // seed generated here
   179  	x := h1.Sum64()
   180  	h2 := new(Hash)
   181  	h2.SetSeed(h1.Seed())
   182  	h2.WriteString("foo")
   183  	y := h2.Sum64()
   184  	if x != y {
   185  		t.Errorf("hashes don't match: want %x, got %x", x, y)
   186  	}
   187  }
   188  
   189  func TestSeedFromFlush(t *testing.T) {
   190  	b := make([]byte, 65)
   191  	h1 := new(Hash)
   192  	h1.Write(b) // seed generated here
   193  	x := h1.Sum64()
   194  	h2 := new(Hash)
   195  	h2.SetSeed(h1.Seed())
   196  	h2.Write(b)
   197  	y := h2.Sum64()
   198  	if x != y {
   199  		t.Errorf("hashes don't match: want %x, got %x", x, y)
   200  	}
   201  }
   202  
   203  func TestSeedFromReset(t *testing.T) {
   204  	h1 := new(Hash)
   205  	h1.WriteString("foo")
   206  	h1.Reset() // seed generated here
   207  	h1.WriteString("foo")
   208  	x := h1.Sum64()
   209  	h2 := new(Hash)
   210  	h2.SetSeed(h1.Seed())
   211  	h2.WriteString("foo")
   212  	y := h2.Sum64()
   213  	if x != y {
   214  		t.Errorf("hashes don't match: want %x, got %x", x, y)
   215  	}
   216  }
   217  
   218  func negativeZero[T float32 | float64]() T {
   219  	var f T
   220  	f = -f
   221  	return f
   222  }
   223  
   224  func TestComparable(t *testing.T) {
   225  	testComparable(t, int64(2))
   226  	testComparable(t, uint64(8))
   227  	testComparable(t, uintptr(12))
   228  	testComparable(t, any("s"))
   229  	testComparable(t, "s")
   230  	testComparable(t, true)
   231  	testComparable(t, new(float64))
   232  	testComparable(t, float64(9))
   233  	testComparable(t, complex128(9i+1))
   234  	testComparable(t, struct{}{})
   235  	testComparable(t, struct {
   236  		i int
   237  		u uint
   238  		b bool
   239  		f float64
   240  		p *int
   241  		a any
   242  	}{i: 9, u: 1, b: true, f: 9.9, p: new(int), a: 1})
   243  	type S struct {
   244  		s string
   245  	}
   246  	s1 := S{s: heapStr(t)}
   247  	s2 := S{s: heapStr(t)}
   248  	if unsafe.StringData(s1.s) == unsafe.StringData(s2.s) {
   249  		t.Fatalf("unexpected two heapStr ptr equal")
   250  	}
   251  	if s1.s != s2.s {
   252  		t.Fatalf("unexpected two heapStr value not equal")
   253  	}
   254  	testComparable(t, s1, s2)
   255  	testComparable(t, s1.s, s2.s)
   256  	testComparable(t, float32(0), negativeZero[float32]())
   257  	testComparable(t, float64(0), negativeZero[float64]())
   258  	testComparableNoEqual(t, math.NaN(), math.NaN())
   259  	testComparableNoEqual(t, [2]string{"a", ""}, [2]string{"", "a"})
   260  	testComparableNoEqual(t, struct{ a, b string }{"foo", ""}, struct{ a, b string }{"", "foo"})
   261  	testComparableNoEqual(t, struct{ a, b any }{int(0), struct{}{}}, struct{ a, b any }{struct{}{}, int(0)})
   262  }
   263  
   264  func testComparableNoEqual[T comparable](t *testing.T, v1, v2 T) {
   265  	seed := MakeSeed()
   266  	if Comparable(seed, v1) == Comparable(seed, v2) {
   267  		t.Fatalf("Comparable(seed, %v) == Comparable(seed, %v)", v1, v2)
   268  	}
   269  }
   270  
   271  var heapStrValue = []byte("aTestString")
   272  
   273  func heapStr(t *testing.T) string {
   274  	return string(heapStrValue)
   275  }
   276  
   277  func testComparable[T comparable](t *testing.T, v T, v2 ...T) {
   278  	t.Run(reflect.TypeFor[T]().String(), func(t *testing.T) {
   279  		var a, b T = v, v
   280  		if len(v2) != 0 {
   281  			b = v2[0]
   282  		}
   283  		var pa *T = &a
   284  		seed := MakeSeed()
   285  		if Comparable(seed, a) != Comparable(seed, b) {
   286  			t.Fatalf("Comparable(seed, %v) != Comparable(seed, %v)", a, b)
   287  		}
   288  		old := Comparable(seed, pa)
   289  		stackGrow(8192)
   290  		new := Comparable(seed, pa)
   291  		if old != new {
   292  			t.Fatal("Comparable(seed, ptr) != Comparable(seed, ptr)")
   293  		}
   294  	})
   295  }
   296  
   297  var use byte
   298  
   299  //go:noinline
   300  func stackGrow(dep int) {
   301  	if dep == 0 {
   302  		return
   303  	}
   304  	var local [1024]byte
   305  	// make sure local is allocated on the stack.
   306  	local[randUint64()%1024] = byte(randUint64())
   307  	use = local[randUint64()%1024]
   308  	stackGrow(dep - 1)
   309  }
   310  
   311  func TestWriteComparable(t *testing.T) {
   312  	testWriteComparable(t, int64(2))
   313  	testWriteComparable(t, uint64(8))
   314  	testWriteComparable(t, uintptr(12))
   315  	testWriteComparable(t, any("s"))
   316  	testWriteComparable(t, "s")
   317  	testComparable(t, true)
   318  	testWriteComparable(t, new(float64))
   319  	testWriteComparable(t, float64(9))
   320  	testWriteComparable(t, complex128(9i+1))
   321  	testWriteComparable(t, struct{}{})
   322  	testWriteComparable(t, struct {
   323  		i int
   324  		u uint
   325  		b bool
   326  		f float64
   327  		p *int
   328  		a any
   329  	}{i: 9, u: 1, b: true, f: 9.9, p: new(int), a: 1})
   330  	type S struct {
   331  		s string
   332  	}
   333  	s1 := S{s: heapStr(t)}
   334  	s2 := S{s: heapStr(t)}
   335  	if unsafe.StringData(s1.s) == unsafe.StringData(s2.s) {
   336  		t.Fatalf("unexpected two heapStr ptr equal")
   337  	}
   338  	if s1.s != s2.s {
   339  		t.Fatalf("unexpected two heapStr value not equal")
   340  	}
   341  	testWriteComparable(t, s1, s2)
   342  	testWriteComparable(t, s1.s, s2.s)
   343  	testWriteComparable(t, float32(0), negativeZero[float32]())
   344  	testWriteComparable(t, float64(0), negativeZero[float64]())
   345  	testWriteComparableNoEqual(t, math.NaN(), math.NaN())
   346  	testWriteComparableNoEqual(t, [2]string{"a", ""}, [2]string{"", "a"})
   347  	testWriteComparableNoEqual(t, struct{ a, b string }{"foo", ""}, struct{ a, b string }{"", "foo"})
   348  	testWriteComparableNoEqual(t, struct{ a, b any }{int(0), struct{}{}}, struct{ a, b any }{struct{}{}, int(0)})
   349  }
   350  
   351  func testWriteComparableNoEqual[T comparable](t *testing.T, v1, v2 T) {
   352  	seed := MakeSeed()
   353  	h1 := Hash{}
   354  	h2 := Hash{}
   355  	h1.seed, h2.seed = seed, seed
   356  	WriteComparable(&h1, v1)
   357  	WriteComparable(&h2, v2)
   358  	if h1.Sum64() == h2.Sum64() {
   359  		t.Fatalf("WriteComparable(seed, %v) == WriteComparable(seed, %v)", v1, v2)
   360  	}
   361  
   362  }
   363  
   364  func testWriteComparable[T comparable](t *testing.T, v T, v2 ...T) {
   365  	t.Run(reflect.TypeFor[T]().String(), func(t *testing.T) {
   366  		var a, b T = v, v
   367  		if len(v2) != 0 {
   368  			b = v2[0]
   369  		}
   370  		var pa *T = &a
   371  		h1 := Hash{}
   372  		h2 := Hash{}
   373  		h1.seed = MakeSeed()
   374  		h2.seed = h1.seed
   375  		WriteComparable(&h1, a)
   376  		WriteComparable(&h2, b)
   377  		if h1.Sum64() != h2.Sum64() {
   378  			t.Fatalf("WriteComparable(h, %v) != WriteComparable(h, %v)", a, b)
   379  		}
   380  		WriteComparable(&h1, pa)
   381  		old := h1.Sum64()
   382  		stackGrow(8192)
   383  		WriteComparable(&h2, pa)
   384  		new := h2.Sum64()
   385  		if old != new {
   386  			t.Fatal("WriteComparable(seed, ptr) != WriteComparable(seed, ptr)")
   387  		}
   388  	})
   389  }
   390  
   391  func TestComparableShouldPanic(t *testing.T) {
   392  	s := []byte("s")
   393  	a := any(s)
   394  	defer func() {
   395  		e := recover()
   396  		err, ok := e.(error)
   397  		if !ok {
   398  			t.Fatalf("Comaparable(any([]byte)) should panic")
   399  		}
   400  		want := "hash of unhashable type []uint8"
   401  		if s := err.Error(); !strings.Contains(s, want) {
   402  			t.Fatalf("want %s, got %s", want, s)
   403  		}
   404  	}()
   405  	Comparable(MakeSeed(), a)
   406  }
   407  
   408  func TestWriteComparableNoncommute(t *testing.T) {
   409  	seed := MakeSeed()
   410  	var h1, h2 Hash
   411  	h1.SetSeed(seed)
   412  	h2.SetSeed(seed)
   413  
   414  	h1.WriteString("abc")
   415  	WriteComparable(&h1, 123)
   416  	WriteComparable(&h2, 123)
   417  	h2.WriteString("abc")
   418  
   419  	if h1.Sum64() == h2.Sum64() {
   420  		t.Errorf("WriteComparable and WriteString unexpectedly commute")
   421  	}
   422  }
   423  
   424  func TestComparableAllocations(t *testing.T) {
   425  	if purego {
   426  		t.Skip("skip allocation test in purego mode - reflect-based implementation allocates more")
   427  	}
   428  	if asan.Enabled {
   429  		t.Skip("skip allocation test under -asan")
   430  	}
   431  	seed := MakeSeed()
   432  	x := heapStr(t)
   433  	allocs := testing.AllocsPerRun(10, func() {
   434  		s := "s" + x
   435  		Comparable(seed, s)
   436  	})
   437  	if allocs > 0 {
   438  		t.Errorf("got %v allocs, want 0", allocs)
   439  	}
   440  
   441  	type S struct {
   442  		a int
   443  		b string
   444  	}
   445  	allocs = testing.AllocsPerRun(10, func() {
   446  		s := S{123, "s" + x}
   447  		Comparable(seed, s)
   448  	})
   449  	if allocs > 0 {
   450  		t.Errorf("got %v allocs, want 0", allocs)
   451  	}
   452  }
   453  
   454  // Make sure a Hash implements the hash.Hash and hash.Hash64 interfaces.
   455  var _ hash.Hash = &Hash{}
   456  var _ hash.Hash64 = &Hash{}
   457  
   458  func benchmarkSize(b *testing.B, size int) {
   459  	h := &Hash{}
   460  	buf := make([]byte, size)
   461  	s := string(buf)
   462  
   463  	b.Run("Write", func(b *testing.B) {
   464  		b.SetBytes(int64(size))
   465  		for i := 0; i < b.N; i++ {
   466  			h.Reset()
   467  			h.Write(buf)
   468  			h.Sum64()
   469  		}
   470  	})
   471  
   472  	b.Run("Bytes", func(b *testing.B) {
   473  		b.SetBytes(int64(size))
   474  		seed := h.Seed()
   475  		for i := 0; i < b.N; i++ {
   476  			Bytes(seed, buf)
   477  		}
   478  	})
   479  
   480  	b.Run("String", func(b *testing.B) {
   481  		b.SetBytes(int64(size))
   482  		seed := h.Seed()
   483  		for i := 0; i < b.N; i++ {
   484  			String(seed, s)
   485  		}
   486  	})
   487  }
   488  
   489  func BenchmarkHash(b *testing.B) {
   490  	sizes := []int{4, 8, 16, 32, 64, 256, 320, 1024, 4096, 16384}
   491  	for _, size := range sizes {
   492  		b.Run(fmt.Sprint("n=", size), func(b *testing.B) {
   493  			benchmarkSize(b, size)
   494  		})
   495  	}
   496  }
   497  
   498  func benchmarkComparable[T comparable](b *testing.B, v T) {
   499  	b.Run(reflect.TypeFor[T]().String(), func(b *testing.B) {
   500  		seed := MakeSeed()
   501  		for i := 0; i < b.N; i++ {
   502  			Comparable(seed, v)
   503  		}
   504  	})
   505  }
   506  
   507  func BenchmarkComparable(b *testing.B) {
   508  	type testStruct struct {
   509  		i int
   510  		u uint
   511  		b bool
   512  		f float64
   513  		p *int
   514  		a any
   515  	}
   516  	benchmarkComparable(b, int64(2))
   517  	benchmarkComparable(b, uint64(8))
   518  	benchmarkComparable(b, uintptr(12))
   519  	benchmarkComparable(b, any("s"))
   520  	benchmarkComparable(b, "s")
   521  	benchmarkComparable(b, true)
   522  	benchmarkComparable(b, new(float64))
   523  	benchmarkComparable(b, float64(9))
   524  	benchmarkComparable(b, complex128(9i+1))
   525  	benchmarkComparable(b, struct{}{})
   526  	benchmarkComparable(b, testStruct{i: 9, u: 1, b: true, f: 9.9, p: new(int), a: 1})
   527  }
   528  

View as plain text