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