Source file src/runtime/map_test.go

     1  // Copyright 2013 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 runtime_test
     6  
     7  import (
     8  	"fmt"
     9  	"internal/abi"
    10  	"internal/goarch"
    11  	"internal/runtime/maps"
    12  	"internal/testenv"
    13  	"math"
    14  	"os"
    15  	"reflect"
    16  	"runtime"
    17  	"slices"
    18  	"strconv"
    19  	"strings"
    20  	"sync"
    21  	"testing"
    22  	"unsafe"
    23  )
    24  
    25  // negative zero is a good test because:
    26  //  1. 0 and -0 are equal, yet have distinct representations.
    27  //  2. 0 is represented as all zeros, -0 isn't.
    28  //
    29  // I'm not sure the language spec actually requires this behavior,
    30  // but it's what the current map implementation does.
    31  func TestNegativeZero(t *testing.T) {
    32  	m := make(map[float64]bool, 0)
    33  
    34  	m[+0.0] = true
    35  	m[math.Copysign(0.0, -1.0)] = true // should overwrite +0 entry
    36  
    37  	if len(m) != 1 {
    38  		t.Error("length wrong")
    39  	}
    40  
    41  	for k := range m {
    42  		if math.Copysign(1.0, k) > 0 {
    43  			t.Error("wrong sign")
    44  		}
    45  	}
    46  
    47  	m = make(map[float64]bool, 0)
    48  	m[math.Copysign(0.0, -1.0)] = true
    49  	m[+0.0] = true // should overwrite -0.0 entry
    50  
    51  	if len(m) != 1 {
    52  		t.Error("length wrong")
    53  	}
    54  
    55  	for k := range m {
    56  		if math.Copysign(1.0, k) < 0 {
    57  			t.Error("wrong sign")
    58  		}
    59  	}
    60  }
    61  
    62  func testMapNan(t *testing.T, m map[float64]int) {
    63  	if len(m) != 3 {
    64  		t.Error("length wrong")
    65  	}
    66  	s := 0
    67  	for k, v := range m {
    68  		if k == k {
    69  			t.Error("nan disappeared")
    70  		}
    71  		if (v & (v - 1)) != 0 {
    72  			t.Error("value wrong")
    73  		}
    74  		s |= v
    75  	}
    76  	if s != 7 {
    77  		t.Error("values wrong")
    78  	}
    79  }
    80  
    81  // nan is a good test because nan != nan, and nan has
    82  // a randomized hash value.
    83  func TestMapAssignmentNan(t *testing.T) {
    84  	m := make(map[float64]int, 0)
    85  	nan := math.NaN()
    86  
    87  	// Test assignment.
    88  	m[nan] = 1
    89  	m[nan] = 2
    90  	m[nan] = 4
    91  	testMapNan(t, m)
    92  }
    93  
    94  // nan is a good test because nan != nan, and nan has
    95  // a randomized hash value.
    96  func TestMapOperatorAssignmentNan(t *testing.T) {
    97  	m := make(map[float64]int, 0)
    98  	nan := math.NaN()
    99  
   100  	// Test assignment operations.
   101  	m[nan] += 1
   102  	m[nan] += 2
   103  	m[nan] += 4
   104  	testMapNan(t, m)
   105  }
   106  
   107  func TestMapOperatorAssignment(t *testing.T) {
   108  	m := make(map[int]int, 0)
   109  
   110  	// "m[k] op= x" is rewritten into "m[k] = m[k] op x"
   111  	// differently when op is / or % than when it isn't.
   112  	// Simple test to make sure they all work as expected.
   113  	m[0] = 12345
   114  	m[0] += 67890
   115  	m[0] /= 123
   116  	m[0] %= 456
   117  
   118  	const want = (12345 + 67890) / 123 % 456
   119  	if got := m[0]; got != want {
   120  		t.Errorf("got %d, want %d", got, want)
   121  	}
   122  }
   123  
   124  var sinkAppend bool
   125  
   126  func TestMapAppendAssignment(t *testing.T) {
   127  	m := make(map[int][]int, 0)
   128  
   129  	m[0] = nil
   130  	m[0] = append(m[0], 12345)
   131  	m[0] = append(m[0], 67890)
   132  	sinkAppend, m[0] = !sinkAppend, append(m[0], 123, 456)
   133  	a := []int{7, 8, 9, 0}
   134  	m[0] = append(m[0], a...)
   135  
   136  	want := []int{12345, 67890, 123, 456, 7, 8, 9, 0}
   137  	if got := m[0]; !slices.Equal(got, want) {
   138  		t.Errorf("got %v, want %v", got, want)
   139  	}
   140  }
   141  
   142  // Maps aren't actually copied on assignment.
   143  func TestAlias(t *testing.T) {
   144  	m := make(map[int]int, 0)
   145  	m[0] = 5
   146  	n := m
   147  	n[0] = 6
   148  	if m[0] != 6 {
   149  		t.Error("alias didn't work")
   150  	}
   151  }
   152  
   153  func TestGrowWithNaN(t *testing.T) {
   154  	m := make(map[float64]int, 4)
   155  	nan := math.NaN()
   156  
   157  	// Use both assignment and assignment operations as they may
   158  	// behave differently.
   159  	m[nan] = 1
   160  	m[nan] = 2
   161  	m[nan] += 4
   162  
   163  	cnt := 0
   164  	s := 0
   165  	growflag := true
   166  	for k, v := range m {
   167  		if growflag {
   168  			// force a hashtable resize
   169  			for i := 0; i < 50; i++ {
   170  				m[float64(i)] = i
   171  			}
   172  			for i := 50; i < 100; i++ {
   173  				m[float64(i)] += i
   174  			}
   175  			growflag = false
   176  		}
   177  		if k != k {
   178  			cnt++
   179  			s |= v
   180  		}
   181  	}
   182  	if cnt != 3 {
   183  		t.Error("NaN keys lost during grow")
   184  	}
   185  	if s != 7 {
   186  		t.Error("NaN values lost during grow")
   187  	}
   188  }
   189  
   190  type FloatInt struct {
   191  	x float64
   192  	y int
   193  }
   194  
   195  func TestGrowWithNegativeZero(t *testing.T) {
   196  	negzero := math.Copysign(0.0, -1.0)
   197  	m := make(map[FloatInt]int, 4)
   198  	m[FloatInt{0.0, 0}] = 1
   199  	m[FloatInt{0.0, 1}] += 2
   200  	m[FloatInt{0.0, 2}] += 4
   201  	m[FloatInt{0.0, 3}] = 8
   202  	growflag := true
   203  	s := 0
   204  	cnt := 0
   205  	negcnt := 0
   206  	// The first iteration should return the +0 key.
   207  	// The subsequent iterations should return the -0 key.
   208  	// I'm not really sure this is required by the spec,
   209  	// but it makes sense.
   210  	// TODO: are we allowed to get the first entry returned again???
   211  	for k, v := range m {
   212  		if v == 0 {
   213  			continue
   214  		} // ignore entries added to grow table
   215  		cnt++
   216  		if math.Copysign(1.0, k.x) < 0 {
   217  			if v&16 == 0 {
   218  				t.Error("key/value not updated together 1")
   219  			}
   220  			negcnt++
   221  			s |= v & 15
   222  		} else {
   223  			if v&16 == 16 {
   224  				t.Error("key/value not updated together 2", k, v)
   225  			}
   226  			s |= v
   227  		}
   228  		if growflag {
   229  			// force a hashtable resize
   230  			for i := 0; i < 100; i++ {
   231  				m[FloatInt{3.0, i}] = 0
   232  			}
   233  			// then change all the entries
   234  			// to negative zero
   235  			m[FloatInt{negzero, 0}] = 1 | 16
   236  			m[FloatInt{negzero, 1}] = 2 | 16
   237  			m[FloatInt{negzero, 2}] = 4 | 16
   238  			m[FloatInt{negzero, 3}] = 8 | 16
   239  			growflag = false
   240  		}
   241  	}
   242  	if s != 15 {
   243  		t.Error("entry missing", s)
   244  	}
   245  	if cnt != 4 {
   246  		t.Error("wrong number of entries returned by iterator", cnt)
   247  	}
   248  	if negcnt != 3 {
   249  		t.Error("update to negzero missed by iteration", negcnt)
   250  	}
   251  }
   252  
   253  func TestIterGrowAndDelete(t *testing.T) {
   254  	m := make(map[int]int, 4)
   255  	for i := 0; i < 100; i++ {
   256  		m[i] = i
   257  	}
   258  	growflag := true
   259  	for k := range m {
   260  		if growflag {
   261  			// grow the table
   262  			for i := 100; i < 1000; i++ {
   263  				m[i] = i
   264  			}
   265  			// delete all odd keys
   266  			for i := 1; i < 1000; i += 2 {
   267  				delete(m, i)
   268  			}
   269  			growflag = false
   270  		} else {
   271  			if k&1 == 1 {
   272  				t.Error("odd value returned")
   273  			}
   274  		}
   275  	}
   276  }
   277  
   278  // make sure old bucket arrays don't get GCd while
   279  // an iterator is still using them.
   280  func TestIterGrowWithGC(t *testing.T) {
   281  	m := make(map[int]int, 4)
   282  	for i := 0; i < 8; i++ {
   283  		m[i] = i
   284  	}
   285  	for i := 8; i < 16; i++ {
   286  		m[i] += i
   287  	}
   288  	growflag := true
   289  	bitmask := 0
   290  	for k := range m {
   291  		if k < 16 {
   292  			bitmask |= 1 << uint(k)
   293  		}
   294  		if growflag {
   295  			// grow the table
   296  			for i := 100; i < 1000; i++ {
   297  				m[i] = i
   298  			}
   299  			// trigger a gc
   300  			runtime.GC()
   301  			growflag = false
   302  		}
   303  	}
   304  	if bitmask != 1<<16-1 {
   305  		t.Error("missing key", bitmask)
   306  	}
   307  }
   308  
   309  func testConcurrentReadsAfterGrowth(t *testing.T, useReflect bool) {
   310  	t.Parallel()
   311  	if runtime.GOMAXPROCS(-1) == 1 {
   312  		defer runtime.GOMAXPROCS(runtime.GOMAXPROCS(16))
   313  	}
   314  	numLoop := 10
   315  	numGrowStep := 250
   316  	numReader := 16
   317  	if testing.Short() {
   318  		numLoop, numGrowStep = 2, 100
   319  	}
   320  	for i := 0; i < numLoop; i++ {
   321  		m := make(map[int]int, 0)
   322  		for gs := 0; gs < numGrowStep; gs++ {
   323  			m[gs] = gs
   324  			var wg sync.WaitGroup
   325  			wg.Add(numReader * 2)
   326  			for nr := 0; nr < numReader; nr++ {
   327  				go func() {
   328  					defer wg.Done()
   329  					for range m {
   330  					}
   331  				}()
   332  				go func() {
   333  					defer wg.Done()
   334  					for key := 0; key < gs; key++ {
   335  						_ = m[key]
   336  					}
   337  				}()
   338  				if useReflect {
   339  					wg.Add(1)
   340  					go func() {
   341  						defer wg.Done()
   342  						mv := reflect.ValueOf(m)
   343  						keys := mv.MapKeys()
   344  						for _, k := range keys {
   345  							mv.MapIndex(k)
   346  						}
   347  					}()
   348  				}
   349  			}
   350  			wg.Wait()
   351  		}
   352  	}
   353  }
   354  
   355  func TestConcurrentReadsAfterGrowth(t *testing.T) {
   356  	testConcurrentReadsAfterGrowth(t, false)
   357  }
   358  
   359  func TestConcurrentReadsAfterGrowthReflect(t *testing.T) {
   360  	testConcurrentReadsAfterGrowth(t, true)
   361  }
   362  
   363  func TestBigItems(t *testing.T) {
   364  	var key [256]string
   365  	for i := 0; i < 256; i++ {
   366  		key[i] = "foo"
   367  	}
   368  	m := make(map[[256]string][256]string, 4)
   369  	for i := 0; i < 100; i++ {
   370  		key[37] = fmt.Sprintf("string%02d", i)
   371  		m[key] = key
   372  	}
   373  	var keys [100]string
   374  	var values [100]string
   375  	i := 0
   376  	for k, v := range m {
   377  		keys[i] = k[37]
   378  		values[i] = v[37]
   379  		i++
   380  	}
   381  	slices.Sort(keys[:])
   382  	slices.Sort(values[:])
   383  	for i := 0; i < 100; i++ {
   384  		if keys[i] != fmt.Sprintf("string%02d", i) {
   385  			t.Errorf("#%d: missing key: %v", i, keys[i])
   386  		}
   387  		if values[i] != fmt.Sprintf("string%02d", i) {
   388  			t.Errorf("#%d: missing value: %v", i, values[i])
   389  		}
   390  	}
   391  }
   392  
   393  func TestMapHugeZero(t *testing.T) {
   394  	type T [4000]byte
   395  	m := map[int]T{}
   396  	x := m[0]
   397  	if x != (T{}) {
   398  		t.Errorf("map value not zero")
   399  	}
   400  	y, ok := m[0]
   401  	if ok {
   402  		t.Errorf("map value should be missing")
   403  	}
   404  	if y != (T{}) {
   405  		t.Errorf("map value not zero")
   406  	}
   407  }
   408  
   409  type empty struct {
   410  }
   411  
   412  func TestEmptyKeyAndValue(t *testing.T) {
   413  	a := make(map[int]empty, 4)
   414  	b := make(map[empty]int, 4)
   415  	c := make(map[empty]empty, 4)
   416  	a[0] = empty{}
   417  	b[empty{}] = 0
   418  	b[empty{}] = 1
   419  	c[empty{}] = empty{}
   420  
   421  	if len(a) != 1 {
   422  		t.Errorf("empty value insert problem")
   423  	}
   424  	if len(b) != 1 {
   425  		t.Errorf("empty key insert problem")
   426  	}
   427  	if len(c) != 1 {
   428  		t.Errorf("empty key+value insert problem")
   429  	}
   430  	if b[empty{}] != 1 {
   431  		t.Errorf("empty key returned wrong value")
   432  	}
   433  }
   434  
   435  // Tests a map with a single bucket, with same-lengthed short keys
   436  // ("quick keys") as well as long keys.
   437  func TestSingleBucketMapStringKeys_DupLen(t *testing.T) {
   438  	testMapLookups(t, map[string]string{
   439  		"x":                      "x1val",
   440  		"xx":                     "x2val",
   441  		"foo":                    "fooval",
   442  		"bar":                    "barval", // same key length as "foo"
   443  		"xxxx":                   "x4val",
   444  		strings.Repeat("x", 128): "longval1",
   445  		strings.Repeat("y", 128): "longval2",
   446  	})
   447  }
   448  
   449  // Tests a map with a single bucket, with all keys having different lengths.
   450  func TestSingleBucketMapStringKeys_NoDupLen(t *testing.T) {
   451  	testMapLookups(t, map[string]string{
   452  		"x":                      "x1val",
   453  		"xx":                     "x2val",
   454  		"foo":                    "fooval",
   455  		"xxxx":                   "x4val",
   456  		"xxxxx":                  "x5val",
   457  		"xxxxxx":                 "x6val",
   458  		strings.Repeat("x", 128): "longval",
   459  	})
   460  }
   461  
   462  func testMapLookups(t *testing.T, m map[string]string) {
   463  	for k, v := range m {
   464  		if m[k] != v {
   465  			t.Fatalf("m[%q] = %q; want %q", k, m[k], v)
   466  		}
   467  	}
   468  }
   469  
   470  // Tests whether the iterator returns the right elements when
   471  // started in the middle of a grow, when the keys are NaNs.
   472  func TestMapNanGrowIterator(t *testing.T) {
   473  	m := make(map[float64]int)
   474  	nan := math.NaN()
   475  	const nBuckets = 16
   476  	// To fill nBuckets buckets takes LOAD * nBuckets keys.
   477  	nKeys := int(nBuckets * runtime.HashLoad)
   478  
   479  	// Get map to full point with nan keys.
   480  	for i := 0; i < nKeys; i++ {
   481  		m[nan] = i
   482  	}
   483  	// Trigger grow
   484  	m[1.0] = 1
   485  	delete(m, 1.0)
   486  
   487  	// Run iterator
   488  	found := make(map[int]struct{})
   489  	for _, v := range m {
   490  		if v != -1 {
   491  			if _, repeat := found[v]; repeat {
   492  				t.Fatalf("repeat of value %d", v)
   493  			}
   494  			found[v] = struct{}{}
   495  		}
   496  		if len(found) == nKeys/2 {
   497  			// Halfway through iteration, finish grow.
   498  			for i := 0; i < nBuckets; i++ {
   499  				delete(m, 1.0)
   500  			}
   501  		}
   502  	}
   503  	if len(found) != nKeys {
   504  		t.Fatalf("missing value")
   505  	}
   506  }
   507  
   508  // Issue 8410
   509  func TestMapSparseIterOrder(t *testing.T) {
   510  	// Run several rounds to increase the probability
   511  	// of failure. One is not enough.
   512  NextRound:
   513  	for round := 0; round < 10; round++ {
   514  		m := make(map[int]bool)
   515  		// Add 1000 items, remove 980.
   516  		for i := 0; i < 1000; i++ {
   517  			m[i] = true
   518  		}
   519  		for i := 20; i < 1000; i++ {
   520  			delete(m, i)
   521  		}
   522  
   523  		var first []int
   524  		for i := range m {
   525  			first = append(first, i)
   526  		}
   527  
   528  		// 800 chances to get a different iteration order.
   529  		// See bug 8736 for why we need so many tries.
   530  		for n := 0; n < 800; n++ {
   531  			idx := 0
   532  			for i := range m {
   533  				if i != first[idx] {
   534  					// iteration order changed.
   535  					continue NextRound
   536  				}
   537  				idx++
   538  			}
   539  		}
   540  		t.Fatalf("constant iteration order on round %d: %v", round, first)
   541  	}
   542  }
   543  
   544  // Map iteration must not return duplicate entries.
   545  func TestMapIterDuplicate(t *testing.T) {
   546  	// Run several rounds to increase the probability
   547  	// of failure. One is not enough.
   548  	for range 1000 {
   549  		m := make(map[int]bool)
   550  		// Add 1000 items, remove 980.
   551  		for i := 0; i < 1000; i++ {
   552  			m[i] = true
   553  		}
   554  		for i := 20; i < 1000; i++ {
   555  			delete(m, i)
   556  		}
   557  
   558  		var want []int
   559  		for i := 0; i < 20; i++ {
   560  			want = append(want, i)
   561  		}
   562  
   563  		var got []int
   564  		for i := range m {
   565  			got = append(got, i)
   566  		}
   567  
   568  		slices.Sort(got)
   569  
   570  		if !reflect.DeepEqual(got, want) {
   571  			t.Errorf("iteration got %v want %v\n", got, want)
   572  		}
   573  	}
   574  }
   575  
   576  func TestMapStringBytesLookup(t *testing.T) {
   577  	// Use large string keys to avoid small-allocation coalescing,
   578  	// which can cause AllocsPerRun to report lower counts than it should.
   579  	m := map[string]int{
   580  		"1000000000000000000000000000000000000000000000000": 1,
   581  		"2000000000000000000000000000000000000000000000000": 2,
   582  	}
   583  	buf := []byte("1000000000000000000000000000000000000000000000000")
   584  	if x := m[string(buf)]; x != 1 {
   585  		t.Errorf(`m[string([]byte("1"))] = %d, want 1`, x)
   586  	}
   587  	buf[0] = '2'
   588  	if x := m[string(buf)]; x != 2 {
   589  		t.Errorf(`m[string([]byte("2"))] = %d, want 2`, x)
   590  	}
   591  
   592  	var x int
   593  	n := testing.AllocsPerRun(100, func() {
   594  		x += m[string(buf)]
   595  	})
   596  	if n != 0 {
   597  		t.Errorf("AllocsPerRun for m[string(buf)] = %v, want 0", n)
   598  	}
   599  
   600  	x = 0
   601  	n = testing.AllocsPerRun(100, func() {
   602  		y, ok := m[string(buf)]
   603  		if !ok {
   604  			panic("!ok")
   605  		}
   606  		x += y
   607  	})
   608  	if n != 0 {
   609  		t.Errorf("AllocsPerRun for x,ok = m[string(buf)] = %v, want 0", n)
   610  	}
   611  }
   612  
   613  func TestMapLargeKeyNoPointer(t *testing.T) {
   614  	const (
   615  		I = 1000
   616  		N = 64
   617  	)
   618  	type T [N]int
   619  	m := make(map[T]int)
   620  	for i := 0; i < I; i++ {
   621  		var v T
   622  		for j := 0; j < N; j++ {
   623  			v[j] = i + j
   624  		}
   625  		m[v] = i
   626  	}
   627  	runtime.GC()
   628  	for i := 0; i < I; i++ {
   629  		var v T
   630  		for j := 0; j < N; j++ {
   631  			v[j] = i + j
   632  		}
   633  		if m[v] != i {
   634  			t.Fatalf("corrupted map: want %+v, got %+v", i, m[v])
   635  		}
   636  	}
   637  }
   638  
   639  func TestMapLargeValNoPointer(t *testing.T) {
   640  	const (
   641  		I = 1000
   642  		N = 64
   643  	)
   644  	type T [N]int
   645  	m := make(map[int]T)
   646  	for i := 0; i < I; i++ {
   647  		var v T
   648  		for j := 0; j < N; j++ {
   649  			v[j] = i + j
   650  		}
   651  		m[i] = v
   652  	}
   653  	runtime.GC()
   654  	for i := 0; i < I; i++ {
   655  		var v T
   656  		for j := 0; j < N; j++ {
   657  			v[j] = i + j
   658  		}
   659  		v1 := m[i]
   660  		for j := 0; j < N; j++ {
   661  			if v1[j] != v[j] {
   662  				t.Fatalf("corrupted map: want %+v, got %+v", v, v1)
   663  			}
   664  		}
   665  	}
   666  }
   667  
   668  // Test that making a map with a large or invalid hint
   669  // doesn't panic. (Issue 19926).
   670  func TestIgnoreBogusMapHint(t *testing.T) {
   671  	for _, hint := range []int64{-1, 1 << 62} {
   672  		_ = make(map[int]int, hint)
   673  	}
   674  }
   675  
   676  var testNonEscapingMapVariable int = 8
   677  
   678  func TestNonEscapingMap(t *testing.T) {
   679  	n := testing.AllocsPerRun(1000, func() {
   680  		m := map[int]int{}
   681  		m[0] = 0
   682  	})
   683  	if n != 0 {
   684  		t.Errorf("mapliteral: want 0 allocs, got %v", n)
   685  	}
   686  	n = testing.AllocsPerRun(1000, func() {
   687  		m := make(map[int]int)
   688  		m[0] = 0
   689  	})
   690  	if n != 0 {
   691  		t.Errorf("no hint: want 0 allocs, got %v", n)
   692  	}
   693  	n = testing.AllocsPerRun(1000, func() {
   694  		m := make(map[int]int, 8)
   695  		m[0] = 0
   696  	})
   697  	if n != 0 {
   698  		t.Errorf("with small hint: want 0 allocs, got %v", n)
   699  	}
   700  	n = testing.AllocsPerRun(1000, func() {
   701  		m := make(map[int]int, testNonEscapingMapVariable)
   702  		m[0] = 0
   703  	})
   704  	if n != 0 {
   705  		t.Errorf("with variable hint: want 0 allocs, got %v", n)
   706  	}
   707  
   708  }
   709  
   710  func TestDeferDeleteSlow(t *testing.T) {
   711  	ks := []complex128{0, 1, 2, 3}
   712  
   713  	m := make(map[any]int)
   714  	for i, k := range ks {
   715  		m[k] = i
   716  	}
   717  	if len(m) != len(ks) {
   718  		t.Errorf("want %d elements, got %d", len(ks), len(m))
   719  	}
   720  
   721  	func() {
   722  		for _, k := range ks {
   723  			defer delete(m, k)
   724  		}
   725  	}()
   726  	if len(m) != 0 {
   727  		t.Errorf("want 0 elements, got %d", len(m))
   728  	}
   729  }
   730  
   731  // TestIncrementAfterDeleteValueInt and other test Issue 25936.
   732  // Value types int, int32, int64 are affected. Value type string
   733  // works as expected.
   734  func TestIncrementAfterDeleteValueInt(t *testing.T) {
   735  	const key1 = 12
   736  	const key2 = 13
   737  
   738  	m := make(map[int]int)
   739  	m[key1] = 99
   740  	delete(m, key1)
   741  	m[key2]++
   742  	if n2 := m[key2]; n2 != 1 {
   743  		t.Errorf("incremented 0 to %d", n2)
   744  	}
   745  }
   746  
   747  func TestIncrementAfterDeleteValueInt32(t *testing.T) {
   748  	const key1 = 12
   749  	const key2 = 13
   750  
   751  	m := make(map[int]int32)
   752  	m[key1] = 99
   753  	delete(m, key1)
   754  	m[key2]++
   755  	if n2 := m[key2]; n2 != 1 {
   756  		t.Errorf("incremented 0 to %d", n2)
   757  	}
   758  }
   759  
   760  func TestIncrementAfterDeleteValueInt64(t *testing.T) {
   761  	const key1 = 12
   762  	const key2 = 13
   763  
   764  	m := make(map[int]int64)
   765  	m[key1] = 99
   766  	delete(m, key1)
   767  	m[key2]++
   768  	if n2 := m[key2]; n2 != 1 {
   769  		t.Errorf("incremented 0 to %d", n2)
   770  	}
   771  }
   772  
   773  func TestIncrementAfterDeleteKeyStringValueInt(t *testing.T) {
   774  	const key1 = ""
   775  	const key2 = "x"
   776  
   777  	m := make(map[string]int)
   778  	m[key1] = 99
   779  	delete(m, key1)
   780  	m[key2] += 1
   781  	if n2 := m[key2]; n2 != 1 {
   782  		t.Errorf("incremented 0 to %d", n2)
   783  	}
   784  }
   785  
   786  func TestIncrementAfterDeleteKeyValueString(t *testing.T) {
   787  	const key1 = ""
   788  	const key2 = "x"
   789  
   790  	m := make(map[string]string)
   791  	m[key1] = "99"
   792  	delete(m, key1)
   793  	m[key2] += "1"
   794  	if n2 := m[key2]; n2 != "1" {
   795  		t.Errorf("appended '1' to empty (nil) string, got %s", n2)
   796  	}
   797  }
   798  
   799  // TestIncrementAfterBulkClearKeyStringValueInt tests that map bulk
   800  // deletion (mapclear) still works as expected. Note that it was not
   801  // affected by Issue 25936.
   802  func TestIncrementAfterBulkClearKeyStringValueInt(t *testing.T) {
   803  	const key1 = ""
   804  	const key2 = "x"
   805  
   806  	m := make(map[string]int)
   807  	m[key1] = 99
   808  	for k := range m {
   809  		delete(m, k)
   810  	}
   811  	m[key2]++
   812  	if n2 := m[key2]; n2 != 1 {
   813  		t.Errorf("incremented 0 to %d", n2)
   814  	}
   815  }
   816  
   817  type canString int
   818  
   819  func (c canString) String() string {
   820  	return fmt.Sprintf("%d", int(c))
   821  }
   822  
   823  func TestMapInterfaceKey(t *testing.T) {
   824  	// Test all the special cases in runtime.typehash.
   825  	type GrabBag struct {
   826  		f32  float32
   827  		f64  float64
   828  		c64  complex64
   829  		c128 complex128
   830  		s    string
   831  		i0   any
   832  		i1   interface {
   833  			String() string
   834  		}
   835  		a [4]string
   836  	}
   837  
   838  	m := map[any]bool{}
   839  	// Put a bunch of data in m, so that a bad hash is likely to
   840  	// lead to a bad bucket, which will lead to a missed lookup.
   841  	for i := 0; i < 1000; i++ {
   842  		m[i] = true
   843  	}
   844  	m[GrabBag{f32: 1.0}] = true
   845  	if !m[GrabBag{f32: 1.0}] {
   846  		panic("f32 not found")
   847  	}
   848  	m[GrabBag{f64: 1.0}] = true
   849  	if !m[GrabBag{f64: 1.0}] {
   850  		panic("f64 not found")
   851  	}
   852  	m[GrabBag{c64: 1.0i}] = true
   853  	if !m[GrabBag{c64: 1.0i}] {
   854  		panic("c64 not found")
   855  	}
   856  	m[GrabBag{c128: 1.0i}] = true
   857  	if !m[GrabBag{c128: 1.0i}] {
   858  		panic("c128 not found")
   859  	}
   860  	m[GrabBag{s: "foo"}] = true
   861  	if !m[GrabBag{s: "foo"}] {
   862  		panic("string not found")
   863  	}
   864  	m[GrabBag{i0: "foo"}] = true
   865  	if !m[GrabBag{i0: "foo"}] {
   866  		panic("interface{} not found")
   867  	}
   868  	m[GrabBag{i1: canString(5)}] = true
   869  	if !m[GrabBag{i1: canString(5)}] {
   870  		panic("interface{String() string} not found")
   871  	}
   872  	m[GrabBag{a: [4]string{"foo", "bar", "baz", "bop"}}] = true
   873  	if !m[GrabBag{a: [4]string{"foo", "bar", "baz", "bop"}}] {
   874  		panic("array not found")
   875  	}
   876  }
   877  
   878  type panicStructKey struct {
   879  	sli []int
   880  }
   881  
   882  func (p panicStructKey) String() string {
   883  	return "panic"
   884  }
   885  
   886  type structKey struct {
   887  }
   888  
   889  func (structKey) String() string {
   890  	return "structKey"
   891  }
   892  
   893  func TestEmptyMapWithInterfaceKey(t *testing.T) {
   894  	var (
   895  		b    bool
   896  		i    int
   897  		i8   int8
   898  		i16  int16
   899  		i32  int32
   900  		i64  int64
   901  		ui   uint
   902  		ui8  uint8
   903  		ui16 uint16
   904  		ui32 uint32
   905  		ui64 uint64
   906  		uipt uintptr
   907  		f32  float32
   908  		f64  float64
   909  		c64  complex64
   910  		c128 complex128
   911  		a    [4]string
   912  		s    string
   913  		p    *int
   914  		up   unsafe.Pointer
   915  		ch   chan int
   916  		i0   any
   917  		i1   interface {
   918  			String() string
   919  		}
   920  		structKey structKey
   921  		i0Panic   any = []int{}
   922  		i1Panic   interface {
   923  			String() string
   924  		} = panicStructKey{}
   925  		panicStructKey = panicStructKey{}
   926  		sli            []int
   927  		me             = map[any]struct{}{}
   928  		mi             = map[interface {
   929  			String() string
   930  		}]struct{}{}
   931  	)
   932  	mustNotPanic := func(f func()) {
   933  		f()
   934  	}
   935  	mustPanic := func(f func()) {
   936  		defer func() {
   937  			r := recover()
   938  			if r == nil {
   939  				t.Errorf("didn't panic")
   940  			}
   941  		}()
   942  		f()
   943  	}
   944  	mustNotPanic(func() {
   945  		_ = me[b]
   946  	})
   947  	mustNotPanic(func() {
   948  		_ = me[i]
   949  	})
   950  	mustNotPanic(func() {
   951  		_ = me[i8]
   952  	})
   953  	mustNotPanic(func() {
   954  		_ = me[i16]
   955  	})
   956  	mustNotPanic(func() {
   957  		_ = me[i32]
   958  	})
   959  	mustNotPanic(func() {
   960  		_ = me[i64]
   961  	})
   962  	mustNotPanic(func() {
   963  		_ = me[ui]
   964  	})
   965  	mustNotPanic(func() {
   966  		_ = me[ui8]
   967  	})
   968  	mustNotPanic(func() {
   969  		_ = me[ui16]
   970  	})
   971  	mustNotPanic(func() {
   972  		_ = me[ui32]
   973  	})
   974  	mustNotPanic(func() {
   975  		_ = me[ui64]
   976  	})
   977  	mustNotPanic(func() {
   978  		_ = me[uipt]
   979  	})
   980  	mustNotPanic(func() {
   981  		_ = me[f32]
   982  	})
   983  	mustNotPanic(func() {
   984  		_ = me[f64]
   985  	})
   986  	mustNotPanic(func() {
   987  		_ = me[c64]
   988  	})
   989  	mustNotPanic(func() {
   990  		_ = me[c128]
   991  	})
   992  	mustNotPanic(func() {
   993  		_ = me[a]
   994  	})
   995  	mustNotPanic(func() {
   996  		_ = me[s]
   997  	})
   998  	mustNotPanic(func() {
   999  		_ = me[p]
  1000  	})
  1001  	mustNotPanic(func() {
  1002  		_ = me[up]
  1003  	})
  1004  	mustNotPanic(func() {
  1005  		_ = me[ch]
  1006  	})
  1007  	mustNotPanic(func() {
  1008  		_ = me[i0]
  1009  	})
  1010  	mustNotPanic(func() {
  1011  		_ = me[i1]
  1012  	})
  1013  	mustNotPanic(func() {
  1014  		_ = me[structKey]
  1015  	})
  1016  	mustPanic(func() {
  1017  		_ = me[i0Panic]
  1018  	})
  1019  	mustPanic(func() {
  1020  		_ = me[i1Panic]
  1021  	})
  1022  	mustPanic(func() {
  1023  		_ = me[panicStructKey]
  1024  	})
  1025  	mustPanic(func() {
  1026  		_ = me[sli]
  1027  	})
  1028  	mustPanic(func() {
  1029  		_ = me[me]
  1030  	})
  1031  
  1032  	mustNotPanic(func() {
  1033  		_ = mi[structKey]
  1034  	})
  1035  	mustPanic(func() {
  1036  		_ = mi[panicStructKey]
  1037  	})
  1038  }
  1039  
  1040  func computeHash() uintptr {
  1041  	var v struct{}
  1042  	return runtime.MemHash(unsafe.Pointer(&v), 0, unsafe.Sizeof(v))
  1043  }
  1044  
  1045  func subprocessHash(t *testing.T, env string) uintptr {
  1046  	t.Helper()
  1047  
  1048  	cmd := testenv.CleanCmdEnv(testenv.Command(t, testenv.Executable(t), "-test.run=^TestMemHashGlobalSeed$"))
  1049  	cmd.Env = append(cmd.Env, "GO_TEST_SUBPROCESS_HASH=1")
  1050  	if env != "" {
  1051  		cmd.Env = append(cmd.Env, env)
  1052  	}
  1053  
  1054  	out, err := cmd.Output()
  1055  	if err != nil {
  1056  		t.Fatalf("cmd.Output got err %v want nil", err)
  1057  	}
  1058  
  1059  	s := strings.TrimSpace(string(out))
  1060  	h, err := strconv.ParseUint(s, 10, 64)
  1061  	if err != nil {
  1062  		t.Fatalf("Parse output %q got err %v want nil", s, err)
  1063  	}
  1064  	return uintptr(h)
  1065  }
  1066  
  1067  // memhash has unique per-process seeds, so hashes should differ across
  1068  // processes.
  1069  //
  1070  // Regression test for https://go.dev/issue/66885.
  1071  func TestMemHashGlobalSeed(t *testing.T) {
  1072  	if os.Getenv("GO_TEST_SUBPROCESS_HASH") != "" {
  1073  		fmt.Println(computeHash())
  1074  		os.Exit(0)
  1075  		return
  1076  	}
  1077  
  1078  	testenv.MustHaveExec(t)
  1079  
  1080  	// aeshash and memhashFallback use separate per-process seeds, so test
  1081  	// both.
  1082  	t.Run("aes", func(t *testing.T) {
  1083  		if !*runtime.UseAeshash {
  1084  			t.Skip("No AES")
  1085  		}
  1086  
  1087  		h1 := subprocessHash(t, "")
  1088  		t.Logf("%d", h1)
  1089  		h2 := subprocessHash(t, "")
  1090  		t.Logf("%d", h2)
  1091  		h3 := subprocessHash(t, "")
  1092  		t.Logf("%d", h3)
  1093  
  1094  		if h1 == h2 && h2 == h3 {
  1095  			t.Errorf("got duplicate hash %d want unique", h1)
  1096  		}
  1097  	})
  1098  
  1099  	t.Run("noaes", func(t *testing.T) {
  1100  		env := ""
  1101  		if *runtime.UseAeshash {
  1102  			env = "GODEBUG=cpu.aes=off"
  1103  		}
  1104  
  1105  		h1 := subprocessHash(t, env)
  1106  		t.Logf("%d", h1)
  1107  		h2 := subprocessHash(t, env)
  1108  		t.Logf("%d", h2)
  1109  		h3 := subprocessHash(t, env)
  1110  		t.Logf("%d", h3)
  1111  
  1112  		if h1 == h2 && h2 == h3 {
  1113  			t.Errorf("got duplicate hash %d want unique", h1)
  1114  		}
  1115  	})
  1116  }
  1117  
  1118  func TestMapIterDeleteReplace(t *testing.T) {
  1119  	inc := 1
  1120  	if testing.Short() {
  1121  		inc = 100
  1122  	}
  1123  	for i := 0; i < 10000; i += inc {
  1124  		t.Run(fmt.Sprint(i), func(t *testing.T) {
  1125  			m := make(map[int]bool)
  1126  			for j := range i {
  1127  				m[j] = false
  1128  			}
  1129  
  1130  			// Delete and replace all entries.
  1131  			for k := range m {
  1132  				delete(m, k)
  1133  				m[k] = true
  1134  			}
  1135  
  1136  			for k, v := range m {
  1137  				if !v {
  1138  					t.Errorf("m[%d] got false want true", k)
  1139  				}
  1140  			}
  1141  		})
  1142  	}
  1143  }
  1144  
  1145  func TestHmapSize(t *testing.T) {
  1146  	// The structure of Map is defined in internal/runtime/maps/map.go
  1147  	// and in cmd/compile/internal/reflectdata/map.go and must be in sync.
  1148  	// The size of Map should be 48 bytes on 64 bit and 32 bytes on 32 bit platforms.
  1149  	wantSize := uintptr(2*8 + 4*goarch.PtrSize)
  1150  	gotSize := unsafe.Sizeof(maps.Map{})
  1151  	if gotSize != wantSize {
  1152  		t.Errorf("sizeof(maps.Map{})==%d, want %d", gotSize, wantSize)
  1153  	}
  1154  }
  1155  
  1156  // See also reflect_test.TestGroupSizeZero.
  1157  func TestGroupSizeZero(t *testing.T) {
  1158  	var m map[struct{}]struct{}
  1159  	mTyp := abi.TypeOf(m)
  1160  	mt := (*abi.MapType)(unsafe.Pointer(mTyp))
  1161  
  1162  	// internal/runtime/maps when create pointers to slots, even if slots
  1163  	// are size 0. The compiler should have reserved an extra word to
  1164  	// ensure that pointers to the zero-size type at the end of group are
  1165  	// valid.
  1166  	if mt.Group.Size() <= 8 {
  1167  		t.Errorf("Group size got %d want >8", mt.Group.Size())
  1168  	}
  1169  }
  1170  
  1171  func TestMapIterOrder(t *testing.T) {
  1172  	sizes := []int{3, 7, 9, 15}
  1173  	for _, n := range sizes {
  1174  		for i := 0; i < 1000; i++ {
  1175  			// Make m be {0: true, 1: true, ..., n-1: true}.
  1176  			m := make(map[int]bool)
  1177  			for i := 0; i < n; i++ {
  1178  				m[i] = true
  1179  			}
  1180  			// Check that iterating over the map produces at least two different orderings.
  1181  			ord := func() []int {
  1182  				var s []int
  1183  				for key := range m {
  1184  					s = append(s, key)
  1185  				}
  1186  				return s
  1187  			}
  1188  			first := ord()
  1189  			ok := false
  1190  			for try := 0; try < 100; try++ {
  1191  				if !slices.Equal(first, ord()) {
  1192  					ok = true
  1193  					break
  1194  				}
  1195  			}
  1196  			if !ok {
  1197  				t.Errorf("Map with n=%d elements had consistent iteration order: %v", n, first)
  1198  				break
  1199  			}
  1200  		}
  1201  	}
  1202  }
  1203  

View as plain text