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