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  	if goexperiment.SwissMap {
   678  		t.Skip("TODO(go.dev/issue/54766): implement stack allocated maps")
   679  	}
   680  
   681  	n := testing.AllocsPerRun(1000, func() {
   682  		m := map[int]int{}
   683  		m[0] = 0
   684  	})
   685  	if n != 0 {
   686  		t.Errorf("mapliteral: want 0 allocs, got %v", n)
   687  	}
   688  	n = testing.AllocsPerRun(1000, func() {
   689  		m := make(map[int]int)
   690  		m[0] = 0
   691  	})
   692  	if n != 0 {
   693  		t.Errorf("no hint: want 0 allocs, got %v", n)
   694  	}
   695  	n = testing.AllocsPerRun(1000, func() {
   696  		m := make(map[int]int, 8)
   697  		m[0] = 0
   698  	})
   699  	if n != 0 {
   700  		t.Errorf("with small hint: want 0 allocs, got %v", n)
   701  	}
   702  	n = testing.AllocsPerRun(1000, func() {
   703  		m := make(map[int]int, testNonEscapingMapVariable)
   704  		m[0] = 0
   705  	})
   706  	if n != 0 {
   707  		t.Errorf("with variable hint: want 0 allocs, got %v", n)
   708  	}
   709  
   710  }
   711  
   712  func TestDeferDeleteSlow(t *testing.T) {
   713  	ks := []complex128{0, 1, 2, 3}
   714  
   715  	m := make(map[any]int)
   716  	for i, k := range ks {
   717  		m[k] = i
   718  	}
   719  	if len(m) != len(ks) {
   720  		t.Errorf("want %d elements, got %d", len(ks), len(m))
   721  	}
   722  
   723  	func() {
   724  		for _, k := range ks {
   725  			defer delete(m, k)
   726  		}
   727  	}()
   728  	if len(m) != 0 {
   729  		t.Errorf("want 0 elements, got %d", len(m))
   730  	}
   731  }
   732  
   733  // TestIncrementAfterDeleteValueInt and other test Issue 25936.
   734  // Value types int, int32, int64 are affected. Value type string
   735  // works as expected.
   736  func TestIncrementAfterDeleteValueInt(t *testing.T) {
   737  	const key1 = 12
   738  	const key2 = 13
   739  
   740  	m := make(map[int]int)
   741  	m[key1] = 99
   742  	delete(m, key1)
   743  	m[key2]++
   744  	if n2 := m[key2]; n2 != 1 {
   745  		t.Errorf("incremented 0 to %d", n2)
   746  	}
   747  }
   748  
   749  func TestIncrementAfterDeleteValueInt32(t *testing.T) {
   750  	const key1 = 12
   751  	const key2 = 13
   752  
   753  	m := make(map[int]int32)
   754  	m[key1] = 99
   755  	delete(m, key1)
   756  	m[key2]++
   757  	if n2 := m[key2]; n2 != 1 {
   758  		t.Errorf("incremented 0 to %d", n2)
   759  	}
   760  }
   761  
   762  func TestIncrementAfterDeleteValueInt64(t *testing.T) {
   763  	const key1 = 12
   764  	const key2 = 13
   765  
   766  	m := make(map[int]int64)
   767  	m[key1] = 99
   768  	delete(m, key1)
   769  	m[key2]++
   770  	if n2 := m[key2]; n2 != 1 {
   771  		t.Errorf("incremented 0 to %d", n2)
   772  	}
   773  }
   774  
   775  func TestIncrementAfterDeleteKeyStringValueInt(t *testing.T) {
   776  	const key1 = ""
   777  	const key2 = "x"
   778  
   779  	m := make(map[string]int)
   780  	m[key1] = 99
   781  	delete(m, key1)
   782  	m[key2] += 1
   783  	if n2 := m[key2]; n2 != 1 {
   784  		t.Errorf("incremented 0 to %d", n2)
   785  	}
   786  }
   787  
   788  func TestIncrementAfterDeleteKeyValueString(t *testing.T) {
   789  	const key1 = ""
   790  	const key2 = "x"
   791  
   792  	m := make(map[string]string)
   793  	m[key1] = "99"
   794  	delete(m, key1)
   795  	m[key2] += "1"
   796  	if n2 := m[key2]; n2 != "1" {
   797  		t.Errorf("appended '1' to empty (nil) string, got %s", n2)
   798  	}
   799  }
   800  
   801  // TestIncrementAfterBulkClearKeyStringValueInt tests that map bulk
   802  // deletion (mapclear) still works as expected. Note that it was not
   803  // affected by Issue 25936.
   804  func TestIncrementAfterBulkClearKeyStringValueInt(t *testing.T) {
   805  	const key1 = ""
   806  	const key2 = "x"
   807  
   808  	m := make(map[string]int)
   809  	m[key1] = 99
   810  	for k := range m {
   811  		delete(m, k)
   812  	}
   813  	m[key2]++
   814  	if n2 := m[key2]; n2 != 1 {
   815  		t.Errorf("incremented 0 to %d", n2)
   816  	}
   817  }
   818  
   819  func TestMapTombstones(t *testing.T) {
   820  	m := map[int]int{}
   821  	const N = 10000
   822  	// Fill a map.
   823  	for i := 0; i < N; i++ {
   824  		m[i] = i
   825  	}
   826  	runtime.MapTombstoneCheck(m)
   827  	// Delete half of the entries.
   828  	for i := 0; i < N; i += 2 {
   829  		delete(m, i)
   830  	}
   831  	runtime.MapTombstoneCheck(m)
   832  	// Add new entries to fill in holes.
   833  	for i := N; i < 3*N/2; i++ {
   834  		m[i] = i
   835  	}
   836  	runtime.MapTombstoneCheck(m)
   837  	// Delete everything.
   838  	for i := 0; i < 3*N/2; i++ {
   839  		delete(m, i)
   840  	}
   841  	runtime.MapTombstoneCheck(m)
   842  }
   843  
   844  type canString int
   845  
   846  func (c canString) String() string {
   847  	return fmt.Sprintf("%d", int(c))
   848  }
   849  
   850  func TestMapInterfaceKey(t *testing.T) {
   851  	// Test all the special cases in runtime.typehash.
   852  	type GrabBag struct {
   853  		f32  float32
   854  		f64  float64
   855  		c64  complex64
   856  		c128 complex128
   857  		s    string
   858  		i0   any
   859  		i1   interface {
   860  			String() string
   861  		}
   862  		a [4]string
   863  	}
   864  
   865  	m := map[any]bool{}
   866  	// Put a bunch of data in m, so that a bad hash is likely to
   867  	// lead to a bad bucket, which will lead to a missed lookup.
   868  	for i := 0; i < 1000; i++ {
   869  		m[i] = true
   870  	}
   871  	m[GrabBag{f32: 1.0}] = true
   872  	if !m[GrabBag{f32: 1.0}] {
   873  		panic("f32 not found")
   874  	}
   875  	m[GrabBag{f64: 1.0}] = true
   876  	if !m[GrabBag{f64: 1.0}] {
   877  		panic("f64 not found")
   878  	}
   879  	m[GrabBag{c64: 1.0i}] = true
   880  	if !m[GrabBag{c64: 1.0i}] {
   881  		panic("c64 not found")
   882  	}
   883  	m[GrabBag{c128: 1.0i}] = true
   884  	if !m[GrabBag{c128: 1.0i}] {
   885  		panic("c128 not found")
   886  	}
   887  	m[GrabBag{s: "foo"}] = true
   888  	if !m[GrabBag{s: "foo"}] {
   889  		panic("string not found")
   890  	}
   891  	m[GrabBag{i0: "foo"}] = true
   892  	if !m[GrabBag{i0: "foo"}] {
   893  		panic("interface{} not found")
   894  	}
   895  	m[GrabBag{i1: canString(5)}] = true
   896  	if !m[GrabBag{i1: canString(5)}] {
   897  		panic("interface{String() string} not found")
   898  	}
   899  	m[GrabBag{a: [4]string{"foo", "bar", "baz", "bop"}}] = true
   900  	if !m[GrabBag{a: [4]string{"foo", "bar", "baz", "bop"}}] {
   901  		panic("array not found")
   902  	}
   903  }
   904  
   905  type panicStructKey struct {
   906  	sli []int
   907  }
   908  
   909  func (p panicStructKey) String() string {
   910  	return "panic"
   911  }
   912  
   913  type structKey struct {
   914  }
   915  
   916  func (structKey) String() string {
   917  	return "structKey"
   918  }
   919  
   920  func TestEmptyMapWithInterfaceKey(t *testing.T) {
   921  	var (
   922  		b    bool
   923  		i    int
   924  		i8   int8
   925  		i16  int16
   926  		i32  int32
   927  		i64  int64
   928  		ui   uint
   929  		ui8  uint8
   930  		ui16 uint16
   931  		ui32 uint32
   932  		ui64 uint64
   933  		uipt uintptr
   934  		f32  float32
   935  		f64  float64
   936  		c64  complex64
   937  		c128 complex128
   938  		a    [4]string
   939  		s    string
   940  		p    *int
   941  		up   unsafe.Pointer
   942  		ch   chan int
   943  		i0   any
   944  		i1   interface {
   945  			String() string
   946  		}
   947  		structKey structKey
   948  		i0Panic   any = []int{}
   949  		i1Panic   interface {
   950  			String() string
   951  		} = panicStructKey{}
   952  		panicStructKey = panicStructKey{}
   953  		sli            []int
   954  		me             = map[any]struct{}{}
   955  		mi             = map[interface {
   956  			String() string
   957  		}]struct{}{}
   958  	)
   959  	mustNotPanic := func(f func()) {
   960  		f()
   961  	}
   962  	mustPanic := func(f func()) {
   963  		defer func() {
   964  			r := recover()
   965  			if r == nil {
   966  				t.Errorf("didn't panic")
   967  			}
   968  		}()
   969  		f()
   970  	}
   971  	mustNotPanic(func() {
   972  		_ = me[b]
   973  	})
   974  	mustNotPanic(func() {
   975  		_ = me[i]
   976  	})
   977  	mustNotPanic(func() {
   978  		_ = me[i8]
   979  	})
   980  	mustNotPanic(func() {
   981  		_ = me[i16]
   982  	})
   983  	mustNotPanic(func() {
   984  		_ = me[i32]
   985  	})
   986  	mustNotPanic(func() {
   987  		_ = me[i64]
   988  	})
   989  	mustNotPanic(func() {
   990  		_ = me[ui]
   991  	})
   992  	mustNotPanic(func() {
   993  		_ = me[ui8]
   994  	})
   995  	mustNotPanic(func() {
   996  		_ = me[ui16]
   997  	})
   998  	mustNotPanic(func() {
   999  		_ = me[ui32]
  1000  	})
  1001  	mustNotPanic(func() {
  1002  		_ = me[ui64]
  1003  	})
  1004  	mustNotPanic(func() {
  1005  		_ = me[uipt]
  1006  	})
  1007  	mustNotPanic(func() {
  1008  		_ = me[f32]
  1009  	})
  1010  	mustNotPanic(func() {
  1011  		_ = me[f64]
  1012  	})
  1013  	mustNotPanic(func() {
  1014  		_ = me[c64]
  1015  	})
  1016  	mustNotPanic(func() {
  1017  		_ = me[c128]
  1018  	})
  1019  	mustNotPanic(func() {
  1020  		_ = me[a]
  1021  	})
  1022  	mustNotPanic(func() {
  1023  		_ = me[s]
  1024  	})
  1025  	mustNotPanic(func() {
  1026  		_ = me[p]
  1027  	})
  1028  	mustNotPanic(func() {
  1029  		_ = me[up]
  1030  	})
  1031  	mustNotPanic(func() {
  1032  		_ = me[ch]
  1033  	})
  1034  	mustNotPanic(func() {
  1035  		_ = me[i0]
  1036  	})
  1037  	mustNotPanic(func() {
  1038  		_ = me[i1]
  1039  	})
  1040  	mustNotPanic(func() {
  1041  		_ = me[structKey]
  1042  	})
  1043  	mustPanic(func() {
  1044  		_ = me[i0Panic]
  1045  	})
  1046  	mustPanic(func() {
  1047  		_ = me[i1Panic]
  1048  	})
  1049  	mustPanic(func() {
  1050  		_ = me[panicStructKey]
  1051  	})
  1052  	mustPanic(func() {
  1053  		_ = me[sli]
  1054  	})
  1055  	mustPanic(func() {
  1056  		_ = me[me]
  1057  	})
  1058  
  1059  	mustNotPanic(func() {
  1060  		_ = mi[structKey]
  1061  	})
  1062  	mustPanic(func() {
  1063  		_ = mi[panicStructKey]
  1064  	})
  1065  }
  1066  
  1067  func TestMapKeys(t *testing.T) {
  1068  	if goexperiment.SwissMap {
  1069  		t.Skip("mapkeys not implemented for swissmaps")
  1070  	}
  1071  
  1072  	type key struct {
  1073  		s   string
  1074  		pad [128]byte // sizeof(key) > abi.MapMaxKeyBytes
  1075  	}
  1076  	m := map[key]int{{s: "a"}: 1, {s: "b"}: 2}
  1077  	keys := make([]key, 0, len(m))
  1078  	runtime.MapKeys(m, unsafe.Pointer(&keys))
  1079  	for _, k := range keys {
  1080  		if len(k.s) != 1 {
  1081  			t.Errorf("len(k.s) == %d, want 1", len(k.s))
  1082  		}
  1083  	}
  1084  }
  1085  
  1086  func TestMapValues(t *testing.T) {
  1087  	if goexperiment.SwissMap {
  1088  		t.Skip("mapvalues not implemented for swissmaps")
  1089  	}
  1090  
  1091  	type val struct {
  1092  		s   string
  1093  		pad [128]byte // sizeof(val) > abi.MapMaxElemBytes
  1094  	}
  1095  	m := map[int]val{1: {s: "a"}, 2: {s: "b"}}
  1096  	vals := make([]val, 0, len(m))
  1097  	runtime.MapValues(m, unsafe.Pointer(&vals))
  1098  	for _, v := range vals {
  1099  		if len(v.s) != 1 {
  1100  			t.Errorf("len(v.s) == %d, want 1", len(v.s))
  1101  		}
  1102  	}
  1103  }
  1104  
  1105  func computeHash() uintptr {
  1106  	var v struct{}
  1107  	return runtime.MemHash(unsafe.Pointer(&v), 0, unsafe.Sizeof(v))
  1108  }
  1109  
  1110  func subprocessHash(t *testing.T, env string) uintptr {
  1111  	t.Helper()
  1112  
  1113  	cmd := testenv.CleanCmdEnv(testenv.Command(t, os.Args[0], "-test.run=^TestMemHashGlobalSeed$"))
  1114  	cmd.Env = append(cmd.Env, "GO_TEST_SUBPROCESS_HASH=1")
  1115  	if env != "" {
  1116  		cmd.Env = append(cmd.Env, env)
  1117  	}
  1118  
  1119  	out, err := cmd.Output()
  1120  	if err != nil {
  1121  		t.Fatalf("cmd.Output got err %v want nil", err)
  1122  	}
  1123  
  1124  	s := strings.TrimSpace(string(out))
  1125  	h, err := strconv.ParseUint(s, 10, 64)
  1126  	if err != nil {
  1127  		t.Fatalf("Parse output %q got err %v want nil", s, err)
  1128  	}
  1129  	return uintptr(h)
  1130  }
  1131  
  1132  // memhash has unique per-process seeds, so hashes should differ across
  1133  // processes.
  1134  //
  1135  // Regression test for https://go.dev/issue/66885.
  1136  func TestMemHashGlobalSeed(t *testing.T) {
  1137  	if os.Getenv("GO_TEST_SUBPROCESS_HASH") != "" {
  1138  		fmt.Println(computeHash())
  1139  		os.Exit(0)
  1140  		return
  1141  	}
  1142  
  1143  	testenv.MustHaveExec(t)
  1144  
  1145  	// aeshash and memhashFallback use separate per-process seeds, so test
  1146  	// both.
  1147  	t.Run("aes", func(t *testing.T) {
  1148  		if !*runtime.UseAeshash {
  1149  			t.Skip("No AES")
  1150  		}
  1151  
  1152  		h1 := subprocessHash(t, "")
  1153  		t.Logf("%d", h1)
  1154  		h2 := subprocessHash(t, "")
  1155  		t.Logf("%d", h2)
  1156  		h3 := subprocessHash(t, "")
  1157  		t.Logf("%d", h3)
  1158  
  1159  		if h1 == h2 && h2 == h3 {
  1160  			t.Errorf("got duplicate hash %d want unique", h1)
  1161  		}
  1162  	})
  1163  
  1164  	t.Run("noaes", func(t *testing.T) {
  1165  		env := ""
  1166  		if *runtime.UseAeshash {
  1167  			env = "GODEBUG=cpu.aes=off"
  1168  		}
  1169  
  1170  		h1 := subprocessHash(t, env)
  1171  		t.Logf("%d", h1)
  1172  		h2 := subprocessHash(t, env)
  1173  		t.Logf("%d", h2)
  1174  		h3 := subprocessHash(t, env)
  1175  		t.Logf("%d", h3)
  1176  
  1177  		if h1 == h2 && h2 == h3 {
  1178  			t.Errorf("got duplicate hash %d want unique", h1)
  1179  		}
  1180  	})
  1181  }
  1182  
  1183  func TestMapIterDeleteReplace(t *testing.T) {
  1184  	inc := 1
  1185  	if testing.Short() {
  1186  		inc = 100
  1187  	}
  1188  	for i := 0; i < 10000; i += inc {
  1189  		t.Run(fmt.Sprint(i), func(t *testing.T) {
  1190  			m := make(map[int]bool)
  1191  			for j := range i {
  1192  				m[j] = false
  1193  			}
  1194  
  1195  			// Delete and replace all entries.
  1196  			for k := range m {
  1197  				delete(m, k)
  1198  				m[k] = true
  1199  			}
  1200  
  1201  			for k, v := range m {
  1202  				if !v {
  1203  					t.Errorf("m[%d] got false want true", k)
  1204  				}
  1205  			}
  1206  		})
  1207  	}
  1208  }
  1209  

View as plain text