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