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

View as plain text