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