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