map_noswiss.go

     1  // Copyright 2024 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  //go:build !goexperiment.swissmap
     6  
     7  package reflect
     8  
     9  import (
    10  	"internal/abi"
    11  	"internal/goarch"
    12  	"unsafe"
    13  )
    14  
    15  // mapType represents a map type.
    16  type mapType struct {
    17  	abi.OldMapType
    18  }
    19  
    20  // Pushed from runtime.
    21  
    22  //go:noescape
    23  func mapiterinit(t *abi.Type, m unsafe.Pointer, it *hiter)
    24  
    25  //go:noescape
    26  func mapiternext(it *hiter)
    27  
    28  func (t *rtype) Key() Type {
    29  	if t.Kind() != Map {
    30  		panic("reflect: Key of non-map type " + t.String())
    31  	}
    32  	tt := (*mapType)(unsafe.Pointer(t))
    33  	return toType(tt.Key)
    34  }
    35  
    36  // MapOf returns the map type with the given key and element types.
    37  // For example, if k represents int and e represents string,
    38  // MapOf(k, e) represents map[int]string.
    39  //
    40  // If the key type is not a valid map key type (that is, if it does
    41  // not implement Go's == operator), MapOf panics.
    42  func MapOf(key, elem Type) Type {
    43  	ktyp := key.common()
    44  	etyp := elem.common()
    45  
    46  	if ktyp.Equal == nil {
    47  		panic("reflect.MapOf: invalid key type " + stringFor(ktyp))
    48  	}
    49  
    50  	// Look in cache.
    51  	ckey := cacheKey{Map, ktyp, etyp, 0}
    52  	if mt, ok := lookupCache.Load(ckey); ok {
    53  		return mt.(Type)
    54  	}
    55  
    56  	// Look in known types.
    57  	s := "map[" + stringFor(ktyp) + "]" + stringFor(etyp)
    58  	for _, tt := range typesByString(s) {
    59  		mt := (*mapType)(unsafe.Pointer(tt))
    60  		if mt.Key == ktyp && mt.Elem == etyp {
    61  			ti, _ := lookupCache.LoadOrStore(ckey, toRType(tt))
    62  			return ti.(Type)
    63  		}
    64  	}
    65  
    66  	// Make a map type.
    67  	// Note: flag values must match those used in the TMAP case
    68  	// in ../cmd/compile/internal/reflectdata/reflect.go:writeType.
    69  	var imap any = (map[unsafe.Pointer]unsafe.Pointer)(nil)
    70  	mt := **(**mapType)(unsafe.Pointer(&imap))
    71  	mt.Str = resolveReflectName(newName(s, "", false, false))
    72  	mt.TFlag = 0
    73  	mt.Hash = fnv1(etyp.Hash, 'm', byte(ktyp.Hash>>24), byte(ktyp.Hash>>16), byte(ktyp.Hash>>8), byte(ktyp.Hash))
    74  	mt.Key = ktyp
    75  	mt.Elem = etyp
    76  	mt.Bucket = bucketOf(ktyp, etyp)
    77  	mt.Hasher = func(p unsafe.Pointer, seed uintptr) uintptr {
    78  		return typehash(ktyp, p, seed)
    79  	}
    80  	mt.Flags = 0
    81  	if ktyp.Size_ > abi.OldMapMaxKeyBytes {
    82  		mt.KeySize = uint8(goarch.PtrSize)
    83  		mt.Flags |= 1 // indirect key
    84  	} else {
    85  		mt.KeySize = uint8(ktyp.Size_)
    86  	}
    87  	if etyp.Size_ > abi.OldMapMaxElemBytes {
    88  		mt.ValueSize = uint8(goarch.PtrSize)
    89  		mt.Flags |= 2 // indirect value
    90  	} else {
    91  		mt.ValueSize = uint8(etyp.Size_)
    92  	}
    93  	mt.BucketSize = uint16(mt.Bucket.Size_)
    94  	if isReflexive(ktyp) {
    95  		mt.Flags |= 4
    96  	}
    97  	if needKeyUpdate(ktyp) {
    98  		mt.Flags |= 8
    99  	}
   100  	if hashMightPanic(ktyp) {
   101  		mt.Flags |= 16
   102  	}
   103  	mt.PtrToThis = 0
   104  
   105  	ti, _ := lookupCache.LoadOrStore(ckey, toRType(&mt.Type))
   106  	return ti.(Type)
   107  }
   108  
   109  func bucketOf(ktyp, etyp *abi.Type) *abi.Type {
   110  	if ktyp.Size_ > abi.OldMapMaxKeyBytes {
   111  		ktyp = ptrTo(ktyp)
   112  	}
   113  	if etyp.Size_ > abi.OldMapMaxElemBytes {
   114  		etyp = ptrTo(etyp)
   115  	}
   116  
   117  	// Prepare GC data if any.
   118  	// A bucket is at most bucketSize*(1+maxKeySize+maxValSize)+ptrSize bytes,
   119  	// or 2064 bytes, or 258 pointer-size words, or 33 bytes of pointer bitmap.
   120  	// Note that since the key and value are known to be <= 128 bytes,
   121  	// they're guaranteed to have bitmaps instead of GC programs.
   122  	var gcdata *byte
   123  	var ptrdata uintptr
   124  
   125  	size := abi.OldMapBucketCount*(1+ktyp.Size_+etyp.Size_) + goarch.PtrSize
   126  	if size&uintptr(ktyp.Align_-1) != 0 || size&uintptr(etyp.Align_-1) != 0 {
   127  		panic("reflect: bad size computation in MapOf")
   128  	}
   129  
   130  	if ktyp.Pointers() || etyp.Pointers() {
   131  		nptr := (abi.OldMapBucketCount*(1+ktyp.Size_+etyp.Size_) + goarch.PtrSize) / goarch.PtrSize
   132  		n := (nptr + 7) / 8
   133  
   134  		// Runtime needs pointer masks to be a multiple of uintptr in size.
   135  		n = (n + goarch.PtrSize - 1) &^ (goarch.PtrSize - 1)
   136  		mask := make([]byte, n)
   137  		base := uintptr(abi.OldMapBucketCount / goarch.PtrSize)
   138  
   139  		if ktyp.Pointers() {
   140  			emitGCMask(mask, base, ktyp, abi.OldMapBucketCount)
   141  		}
   142  		base += abi.OldMapBucketCount * ktyp.Size_ / goarch.PtrSize
   143  
   144  		if etyp.Pointers() {
   145  			emitGCMask(mask, base, etyp, abi.OldMapBucketCount)
   146  		}
   147  		base += abi.OldMapBucketCount * etyp.Size_ / goarch.PtrSize
   148  
   149  		word := base
   150  		mask[word/8] |= 1 << (word % 8)
   151  		gcdata = &mask[0]
   152  		ptrdata = (word + 1) * goarch.PtrSize
   153  
   154  		// overflow word must be last
   155  		if ptrdata != size {
   156  			panic("reflect: bad layout computation in MapOf")
   157  		}
   158  	}
   159  
   160  	b := &abi.Type{
   161  		Align_:   goarch.PtrSize,
   162  		Size_:    size,
   163  		Kind_:    abi.Struct,
   164  		PtrBytes: ptrdata,
   165  		GCData:   gcdata,
   166  	}
   167  	s := "bucket(" + stringFor(ktyp) + "," + stringFor(etyp) + ")"
   168  	b.Str = resolveReflectName(newName(s, "", false, false))
   169  	return b
   170  }
   171  
   172  var stringType = rtypeOf("")
   173  
   174  // MapIndex returns the value associated with key in the map v.
   175  // It panics if v's Kind is not [Map].
   176  // It returns the zero Value if key is not found in the map or if v represents a nil map.
   177  // As in Go, the key's value must be assignable to the map's key type.
   178  func (v Value) MapIndex(key Value) Value {
   179  	v.mustBe(Map)
   180  	tt := (*mapType)(unsafe.Pointer(v.typ()))
   181  
   182  	// Do not require key to be exported, so that DeepEqual
   183  	// and other programs can use all the keys returned by
   184  	// MapKeys as arguments to MapIndex. If either the map
   185  	// or the key is unexported, though, the result will be
   186  	// considered unexported. This is consistent with the
   187  	// behavior for structs, which allow read but not write
   188  	// of unexported fields.
   189  
   190  	var e unsafe.Pointer
   191  	if (tt.Key == stringType || key.kind() == String) && tt.Key == key.typ() && tt.Elem.Size() <= abi.OldMapMaxElemBytes {
   192  		k := *(*string)(key.ptr)
   193  		e = mapaccess_faststr(v.typ(), v.pointer(), k)
   194  	} else {
   195  		key = key.assignTo("reflect.Value.MapIndex", tt.Key, nil)
   196  		var k unsafe.Pointer
   197  		if key.flag&flagIndir != 0 {
   198  			k = key.ptr
   199  		} else {
   200  			k = unsafe.Pointer(&key.ptr)
   201  		}
   202  		e = mapaccess(v.typ(), v.pointer(), k)
   203  	}
   204  	if e == nil {
   205  		return Value{}
   206  	}
   207  	typ := tt.Elem
   208  	fl := (v.flag | key.flag).ro()
   209  	fl |= flag(typ.Kind())
   210  	return copyVal(typ, fl, e)
   211  }
   212  
   213  // MapKeys returns a slice containing all the keys present in the map,
   214  // in unspecified order.
   215  // It panics if v's Kind is not [Map].
   216  // It returns an empty slice if v represents a nil map.
   217  func (v Value) MapKeys() []Value {
   218  	v.mustBe(Map)
   219  	tt := (*mapType)(unsafe.Pointer(v.typ()))
   220  	keyType := tt.Key
   221  
   222  	fl := v.flag.ro() | flag(keyType.Kind())
   223  
   224  	m := v.pointer()
   225  	mlen := int(0)
   226  	if m != nil {
   227  		mlen = maplen(m)
   228  	}
   229  	var it hiter
   230  	mapiterinit(v.typ(), m, &it)
   231  	a := make([]Value, mlen)
   232  	var i int
   233  	for i = 0; i < len(a); i++ {
   234  		key := it.key
   235  		if key == nil {
   236  			// Someone deleted an entry from the map since we
   237  			// called maplen above. It's a data race, but nothing
   238  			// we can do about it.
   239  			break
   240  		}
   241  		a[i] = copyVal(keyType, fl, key)
   242  		mapiternext(&it)
   243  	}
   244  	return a[:i]
   245  }
   246  
   247  // hiter's structure matches runtime.hiter's structure.
   248  // Having a clone here allows us to embed a map iterator
   249  // inside type MapIter so that MapIters can be re-used
   250  // without doing any allocations.
   251  type hiter struct {
   252  	key         unsafe.Pointer
   253  	elem        unsafe.Pointer
   254  	t           unsafe.Pointer
   255  	h           unsafe.Pointer
   256  	buckets     unsafe.Pointer
   257  	bptr        unsafe.Pointer
   258  	overflow    *[]unsafe.Pointer
   259  	oldoverflow *[]unsafe.Pointer
   260  	startBucket uintptr
   261  	offset      uint8
   262  	wrapped     bool
   263  	B           uint8
   264  	i           uint8
   265  	bucket      uintptr
   266  	checkBucket uintptr
   267  	clearSeq    uint64
   268  }
   269  
   270  func (h *hiter) initialized() bool {
   271  	return h.t != nil
   272  }
   273  
   274  // A MapIter is an iterator for ranging over a map.
   275  // See [Value.MapRange].
   276  type MapIter struct {
   277  	m     Value
   278  	hiter hiter
   279  }
   280  
   281  // Key returns the key of iter's current map entry.
   282  func (iter *MapIter) Key() Value {
   283  	if !iter.hiter.initialized() {
   284  		panic("MapIter.Key called before Next")
   285  	}
   286  	iterkey := iter.hiter.key
   287  	if iterkey == nil {
   288  		panic("MapIter.Key called on exhausted iterator")
   289  	}
   290  
   291  	t := (*mapType)(unsafe.Pointer(iter.m.typ()))
   292  	ktype := t.Key
   293  	return copyVal(ktype, iter.m.flag.ro()|flag(ktype.Kind()), iterkey)
   294  }
   295  
   296  // SetIterKey assigns to v the key of iter's current map entry.
   297  // It is equivalent to v.Set(iter.Key()), but it avoids allocating a new Value.
   298  // As in Go, the key must be assignable to v's type and
   299  // must not be derived from an unexported field.
   300  // It panics if [Value.CanSet] returns false.
   301  func (v Value) SetIterKey(iter *MapIter) {
   302  	if !iter.hiter.initialized() {
   303  		panic("reflect: Value.SetIterKey called before Next")
   304  	}
   305  	iterkey := iter.hiter.key
   306  	if iterkey == nil {
   307  		panic("reflect: Value.SetIterKey called on exhausted iterator")
   308  	}
   309  
   310  	v.mustBeAssignable()
   311  	var target unsafe.Pointer
   312  	if v.kind() == Interface {
   313  		target = v.ptr
   314  	}
   315  
   316  	t := (*mapType)(unsafe.Pointer(iter.m.typ()))
   317  	ktype := t.Key
   318  
   319  	iter.m.mustBeExported() // do not let unexported m leak
   320  	key := Value{ktype, iterkey, iter.m.flag | flag(ktype.Kind()) | flagIndir}
   321  	key = key.assignTo("reflect.MapIter.SetKey", v.typ(), target)
   322  	typedmemmove(v.typ(), v.ptr, key.ptr)
   323  }
   324  
   325  // Value returns the value of iter's current map entry.
   326  func (iter *MapIter) Value() Value {
   327  	if !iter.hiter.initialized() {
   328  		panic("MapIter.Value called before Next")
   329  	}
   330  	iterelem := iter.hiter.elem
   331  	if iterelem == nil {
   332  		panic("MapIter.Value called on exhausted iterator")
   333  	}
   334  
   335  	t := (*mapType)(unsafe.Pointer(iter.m.typ()))
   336  	vtype := t.Elem
   337  	return copyVal(vtype, iter.m.flag.ro()|flag(vtype.Kind()), iterelem)
   338  }
   339  
   340  // SetIterValue assigns to v the value of iter's current map entry.
   341  // It is equivalent to v.Set(iter.Value()), but it avoids allocating a new Value.
   342  // As in Go, the value must be assignable to v's type and
   343  // must not be derived from an unexported field.
   344  // It panics if [Value.CanSet] returns false.
   345  func (v Value) SetIterValue(iter *MapIter) {
   346  	if !iter.hiter.initialized() {
   347  		panic("reflect: Value.SetIterValue called before Next")
   348  	}
   349  	iterelem := iter.hiter.elem
   350  	if iterelem == nil {
   351  		panic("reflect: Value.SetIterValue called on exhausted iterator")
   352  	}
   353  
   354  	v.mustBeAssignable()
   355  	var target unsafe.Pointer
   356  	if v.kind() == Interface {
   357  		target = v.ptr
   358  	}
   359  
   360  	t := (*mapType)(unsafe.Pointer(iter.m.typ()))
   361  	vtype := t.Elem
   362  
   363  	iter.m.mustBeExported() // do not let unexported m leak
   364  	elem := Value{vtype, iterelem, iter.m.flag | flag(vtype.Kind()) | flagIndir}
   365  	elem = elem.assignTo("reflect.MapIter.SetValue", v.typ(), target)
   366  	typedmemmove(v.typ(), v.ptr, elem.ptr)
   367  }
   368  
   369  // Next advances the map iterator and reports whether there is another
   370  // entry. It returns false when iter is exhausted; subsequent
   371  // calls to [MapIter.Key], [MapIter.Value], or [MapIter.Next] will panic.
   372  func (iter *MapIter) Next() bool {
   373  	if !iter.m.IsValid() {
   374  		panic("MapIter.Next called on an iterator that does not have an associated map Value")
   375  	}
   376  	if !iter.hiter.initialized() {
   377  		mapiterinit(iter.m.typ(), iter.m.pointer(), &iter.hiter)
   378  	} else {
   379  		if iter.hiter.key == nil {
   380  			panic("MapIter.Next called on exhausted iterator")
   381  		}
   382  		mapiternext(&iter.hiter)
   383  	}
   384  	return iter.hiter.key != nil
   385  }
   386  
   387  // Reset modifies iter to iterate over v.
   388  // It panics if v's Kind is not [Map] and v is not the zero Value.
   389  // Reset(Value{}) causes iter to not to refer to any map,
   390  // which may allow the previously iterated-over map to be garbage collected.
   391  func (iter *MapIter) Reset(v Value) {
   392  	if v.IsValid() {
   393  		v.mustBe(Map)
   394  	}
   395  	iter.m = v
   396  	iter.hiter = hiter{}
   397  }
   398  
   399  // MapRange returns a range iterator for a map.
   400  // It panics if v's Kind is not [Map].
   401  //
   402  // Call [MapIter.Next] to advance the iterator, and [MapIter.Key]/[MapIter.Value] to access each entry.
   403  // [MapIter.Next] returns false when the iterator is exhausted.
   404  // MapRange follows the same iteration semantics as a range statement.
   405  //
   406  // Example:
   407  //
   408  //	iter := reflect.ValueOf(m).MapRange()
   409  //	for iter.Next() {
   410  //		k := iter.Key()
   411  //		v := iter.Value()
   412  //		...
   413  //	}
   414  func (v Value) MapRange() *MapIter {
   415  	// This is inlinable to take advantage of "function outlining".
   416  	// The allocation of MapIter can be stack allocated if the caller
   417  	// does not allow it to escape.
   418  	// See https://blog.filippo.io/efficient-go-apis-with-the-inliner/
   419  	if v.kind() != Map {
   420  		v.panicNotMap()
   421  	}
   422  	return &MapIter{m: v}
   423  }
   424  
   425  // SetMapIndex sets the element associated with key in the map v to elem.
   426  // It panics if v's Kind is not [Map].
   427  // If elem is the zero Value, SetMapIndex deletes the key from the map.
   428  // Otherwise if v holds a nil map, SetMapIndex will panic.
   429  // As in Go, key's elem must be assignable to the map's key type,
   430  // and elem's value must be assignable to the map's elem type.
   431  func (v Value) SetMapIndex(key, elem Value) {
   432  	v.mustBe(Map)
   433  	v.mustBeExported()
   434  	key.mustBeExported()
   435  	tt := (*mapType)(unsafe.Pointer(v.typ()))
   436  
   437  	if (tt.Key == stringType || key.kind() == String) && tt.Key == key.typ() && tt.Elem.Size() <= abi.OldMapMaxElemBytes {
   438  		k := *(*string)(key.ptr)
   439  		if elem.typ() == nil {
   440  			mapdelete_faststr(v.typ(), v.pointer(), k)
   441  			return
   442  		}
   443  		elem.mustBeExported()
   444  		elem = elem.assignTo("reflect.Value.SetMapIndex", tt.Elem, nil)
   445  		var e unsafe.Pointer
   446  		if elem.flag&flagIndir != 0 {
   447  			e = elem.ptr
   448  		} else {
   449  			e = unsafe.Pointer(&elem.ptr)
   450  		}
   451  		mapassign_faststr(v.typ(), v.pointer(), k, e)
   452  		return
   453  	}
   454  
   455  	key = key.assignTo("reflect.Value.SetMapIndex", tt.Key, nil)
   456  	var k unsafe.Pointer
   457  	if key.flag&flagIndir != 0 {
   458  		k = key.ptr
   459  	} else {
   460  		k = unsafe.Pointer(&key.ptr)
   461  	}
   462  	if elem.typ() == nil {
   463  		mapdelete(v.typ(), v.pointer(), k)
   464  		return
   465  	}
   466  	elem.mustBeExported()
   467  	elem = elem.assignTo("reflect.Value.SetMapIndex", tt.Elem, nil)
   468  	var e unsafe.Pointer
   469  	if elem.flag&flagIndir != 0 {
   470  		e = elem.ptr
   471  	} else {
   472  		e = unsafe.Pointer(&elem.ptr)
   473  	}
   474  	mapassign(v.typ(), v.pointer(), k, e)
   475  }
   476  
   477  // Force slow panicking path not inlined, so it won't add to the
   478  // inlining budget of the caller.
   479  // TODO: undo when the inliner is no longer bottom-up only.
   480  //
   481  //go:noinline
   482  func (f flag) panicNotMap() {
   483  	f.mustBe(Map)
   484  }
   485
View as plain text