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