map_swiss.go

Documentation: reflect

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