zephyrtronium · January 24, 2020 21:10
diff --git a/slots.go b/slots.go
 package iolang

 /*
 This file contains the implementation of slots. Executing Io code amounts to
 looking up a slot and then calling a function pointer, and it turns out that
 the latter is cheap. Slots are the expensive part of the hot path, so they are
 the primary target for optimization.

 If you are here to read how this works, good luck and have fun; I tried hard to
 document everything thoroughly. If you're trying to make changes, have some
 results from my debugging experiences:

 panic: iolang: error executing initialization code from io/98_Debugger.io: Coroutine does not respond to setRunTarget (exception)
 	This happens when getSlot("self") returns nil, which probably means that
 Locals slots aren't set up correctly, which probably means that the underlying
 implementation of foreachSlot is broken.
 	This failure might be intermittent (but still happening much more often
 than not), depending on the exact nature of the problem with foreachSlot,
 because the order in which slots are created for Core protos is generally
 random. If getSlot is among the first few slots created, it is much more likely
 for a broken foreachSlot to still copy it to Locals, so the getSlot message
 doesn't need to be forwarded and thus will look on the locals instead of on
 self.
 	The reason this happens in 98_Debugger.io is because that is the first
 place where initialization code ends up using a setter created by newSlot.

 panic: iolang: no Core proto named CFunction
 	The first call to vm.NewCFunction involves the first slot lookup during VM
 initialization, via vm.CoreProto, which panics with this message if
 GetLocalSlot fails to find the slot. This means that at least one of
 vm.localSyncSlot and vm.SetSlot is broken.
 */

 import (
 	"math/bits"
 	"sync"
 	"sync/atomic"
 	"unsafe"
 )

 // syncSlot is a synchronized slot. Once a particular VM accesses this slot,
 // it becomes the slot's owner for the duration of the access, and other coros
 // must wait until the owner releases it before they can access the slot.
 type syncSlot struct {
 	mu    sync.Mutex
 	cond  sync.Cond // cond.L is &mu
 	owner *VM
 	holds int
 	value *Object
 }

 // newSy creates a new syncSlot with the given value and one hold by vm, or
 // with zero holds if vm is nil.
 func newSy(vm *VM, value *Object) *syncSlot {
 	sy := &syncSlot{
 		value: value,
 	}
 	sy.cond.L = &sy.mu
 	if vm != nil {
 		sy.owner = vm
 		sy.holds = 1
 	}
 	return sy
 }

 // claim causes vm to claim s, blocking until this becomes possible. Calling
 // this with a nil VM puts the slot in an erroneous state.
 func (s *syncSlot) claim(vm *VM) {
 	s.mu.Lock()
 	for s.owner != nil && s.owner != vm {
 		// This uses s.cond.L, an interface, instead of s.mu directly, which
 		// means it is much slower (not inlined). That's alright because this
 		// is already the slow path.
 		s.cond.Wait()
 	}
 	s.owner = vm
 	s.holds++
 	s.mu.Unlock()
 }

 // release releases one hold on the slot. If the number of holds reaches zero
 // as a result, then the slot awakens one of its waiters. Calling this from a
 // coroutine that is not the owner puts the slot in an erroneous state.
 func (s *syncSlot) release() {
 	s.mu.Lock()
 	s.holds--
 	if s.holds == 0 {
 		s.owner = nil
 		s.cond.Signal()
 	}
 	s.mu.Unlock()
 }

 // snap returns a snapshot of the value in s.
 func (s *syncSlot) snap(vm *VM) *Object {
 	s.claim(vm)
 	r := s.value
 	s.release()
 	return r
 }

 // actualSlots is a synchronized trie structure that implements slots.
 //
 // The trie is grow-only. A leaf value of nil indicates an empty slot that has
 // not been created; a slot value of nil indicates an unset or deleted slot.
 type actualSlots struct {
 	root *slotBranch // atomic
 }

 // slotBranch holds a level of the slots trie.
 type slotBranch struct {
 	// leaf is the value associated with the string ending at the current node.
 	// Once this branch is connected into the trie, leaf must be accessed
 	// atomically.
 	leaf *syncSlot

 	// scut is a read-only shortcut to the leaf that justified creating this
 	// branch, if there is one.
 	scut *syncSlot
 	// scutName is the name of the shortcut slot beginning at this node's
 	// parent edge value.
 	scutName string

 	// rec2 is the first slotRecord2. It is included as a value rather than as
 	// a pointer to save an indirection on each lookup.
 	rec2 slotRecord2
 	// rec1 is the first slotRecord1, if there is one.
 	rec1 *slotRecord1

 	// hasZero is an atomic flag indicating whether this branch has an edge
 	// corresponding to the zero byte. If this is nonzero, then readers should
 	// spin until zero is not nil.
 	//
 	// This is typed as a uintptr instead of a smaller type; no other type
 	// would save space due to alignment requirements anyway.
 	hasZero uintptr
 	// zero is the zero edge.
 	zero *slotBranch
 }

 // slotRecord2 manages two-byte edges of the slots trie. Its fields must be
 // manipulated atomically.
 type slotRecord2 struct {
 	// mask is the list of the names of this record's child nodes. A zero word
 	// indicates no edge.
 	mask uintptr
 	// children is this record's child nodes.
 	children [recordChildren / 2]*slotBranch
 	// sibling is the next record at the same level in the trie.
 	sibling *slotRecord2
 }

 // slotRecord1 manages one-byte edges of the slots trie. Its fields must be
 // manipulated atomically.
 type slotRecord1 struct {
 	// mask is the list of the names of this record's child nodes. A zero byte
 	// indicates no edge.
 	mask uintptr
 	// children is this record's child nodes.
 	children [recordChildren]*slotBranch
 	// sibling is the next record at the same level in the trie.
 	sibling *slotRecord1
 }

 // recordChildren is the number of children in a single slotRecord, i.e. the
 // size of uintptr in bytes.
 const recordChildren = 4 << (^uintptr(0) >> 32 & 1)

 // recordPop has the first bit in each byte set and all others clear.
 const recordPop = ^uintptr(0) / 0xff

 // recordPop2 has the first bit in each 2-byte word set and all others clear.
 const recordPop2 = ^uintptr(0) / 0xffff

 // load finds the given slot, or returns nil if there is no such slot.
 func (s *actualSlots) load(slot string) *syncSlot {
 	branch := (*slotBranch)(atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&s.root))))
 	if branch == nil {
 		return nil
 	}
 	// Iterate manually rather than by range; we want bytes, not runes.
 	for len(slot) > 0 {
 		switch {
 		case branch.scut != nil && branch.scutName == slot:
 			// Take the shortcut.
 			return branch.scut
 		case slot[0] == 0:
 			// The nul edge is special and lives on the branch itself. It is
 			// always a one-byte edge.
 			if atomic.LoadUintptr(&branch.hasZero) == 0 {
 				return nil
 			}
 			next := (*slotBranch)(atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&branch.zero))))
 			for next == nil {
 				next = (*slotBranch)(atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&branch.zero))))
 			}
 			branch = next
 			slot = slot[1:]
 		case len(slot) == 1:
 			// Check the one-byte edges.
 			cur := (*slotRecord1)(atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&branch.rec1))))
 			if cur == nil {
 				return nil
 			}
 			m := uintptr(slot[0]) * recordPop
 			for {
 				// From https://graphics.stanford.edu/~seander/bithacks.html
 				// v has a zero byte iff that byte in mask is equal to the byte
 				// we're looking for.
 				v := atomic.LoadUintptr(&cur.mask) ^ m
 				// After subtracting recordPop, the high bit of each byte in v
 				// is set iff the byte either was 0 or was greater than 0x80.
 				// After clearing the bits that were set in v, the latter case
 				// is eliminated. Then, masking the high bit in each byte leaves
 				// the bits whose bytes contained c as the only ones still set.
 				v = (v - recordPop) &^ v & (recordPop << 7)
 				if v == 0 {
 					// No match in this record.
 					cur = (*slotRecord1)(atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&cur.sibling))))
 					if cur == nil {
 						return nil
 					}
 					continue
 				}
 				// The lowest set bit is in the byte that matched c.
 				// There isn't currently any platform where uint is smaller
 				// than uintptr, but this check happens at compile-time anyway.
 				var k int
 				if uint64(^uint(0)) >= uint64(^uintptr(0)) {
 					k = bits.TrailingZeros(uint(v)) / 8
 				} else {
 					k = bits.TrailingZeros64(uint64(v)) / 8
 				}
 				next := (*slotBranch)(atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&cur.children[k]))))
 				for next == nil {
 					// The edge to this child exists, but the node hasn't been set.
 					// Another goroutine must be in the process of setting it. Spin
 					// until it's available.
 					next = (*slotBranch)(atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&cur.children[k]))))
 				}
 				branch = next
 				break
 			}
 			slot = slot[1:]
 			// This is the last iteration for this slot.
 		default:
 			// Check two-byte edges.
 			// rec2 isn't a pointer, so we don't need to get its reference
 			// atomically.
 			cur := &branch.rec2
 			m := (uintptr(slot[0]) | uintptr(slot[1])<<8) * recordPop2
 			for {
 				// This is basically the same as above, except replace "byte"
 				// with "two-byte word."
 				v := atomic.LoadUintptr(&cur.mask) ^ m
 				v = (v - recordPop2) &^ v & (recordPop2 << 15)
 				if v == 0 {
 					cur = (*slotRecord2)(atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&cur.sibling))))
 					if cur == nil {
 						return nil
 					}
 					continue
 				}
 				var k int
 				if uint64(^uint(0)) >= uint64(^uintptr(0)) {
 					k = bits.TrailingZeros(uint(v)) / 16
 				} else {
 					k = bits.TrailingZeros64(uint64(v)) / 16
 				}
 				next := (*slotBranch)(atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&cur.children[k]))))
 				for next == nil {
 					next = (*slotBranch)(atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&cur.children[k]))))
 				}
 				branch = next
 				break
 			}
 			slot = slot[2:]
 		}
 	}
 	return (*syncSlot)(atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&branch.leaf))))
 }

 // open loads the current value of the given slot if it exists or creates a new
 // slot there if it does not. The slot is claimed by vm.
 func (s *actualSlots) open(vm *VM, slot string) *syncSlot {
 	branch := (*slotBranch)(atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&s.root))))
 	if branch == nil {
 		// Slots are empty. Try to create them, but it's possible we're not the
 		// only ones doing so; whoever gets there first wins.
 		branch = &slotBranch{}
 		if !atomic.CompareAndSwapPointer((*unsafe.Pointer)(unsafe.Pointer(&s.root)), nil, unsafe.Pointer(branch)) {
 			branch = (*slotBranch)(atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&s.root))))
 		}
 	}
 	// Iterate manually rather than by range; we want bytes, not runes.
 	for len(slot) > 0 {
 		switch {
 		case slot[0] == 0:
 			// The zero edge is special and lives on the branch itself. It is
 			// always a one-byte edge.
 			if !atomic.CompareAndSwapUintptr(&branch.hasZero, 0, 1) {
 				next := (*slotBranch)(atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&branch.zero))))
 				for next == nil {
 					next = (*slotBranch)(atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&branch.zero))))
 				}
 				branch = next
 				slot = slot[1:]
 				continue
 			}
 			node, leaf := recordBranch(vm, slot[1:])
 			atomic.StorePointer((*unsafe.Pointer)(unsafe.Pointer(&branch.zero)), unsafe.Pointer(node))
 			return leaf
 		case len(slot) == 1:
 			// Check the one-byte edges.
 			cur := (*slotRecord1)(atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&branch.rec1))))
 			if cur == nil {
 				cur = &slotRecord1{}
 				if !atomic.CompareAndSwapPointer((*unsafe.Pointer)(unsafe.Pointer(&branch.rec1)), nil, unsafe.Pointer(cur)) {
 					cur = (*slotRecord1)(atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&branch.rec1))))
 				}
 			}
 			m := uintptr(slot[0]) * recordPop
 			for {
 				cm := atomic.LoadUintptr(&cur.mask)
 				// From https://graphics.stanford.edu/~seander/bithacks.html
 				// v has a zero byte iff that byte in mask is equal to the byte
 				// we're looking for.
 				v := cm ^ m
 				// After subtracting recordPop, the high bit of each byte in v
 				// is set iff the byte either was 0 or was greater than 0x80.
 				// After clearing the bits that were set in v, the latter case
 				// is eliminated. Then, masking the high bit in each byte leaves
 				// the bits whose bytes contained c as the only ones still set.
 				v = (v - recordPop) &^ v & (recordPop << 7)
 				if v == 0 {
 					// No match in this record.
 					if cm < 1<<(32<<(^uintptr(0)>>32&1)-7) {
 						// This record had at least one open spot at the time
 						// we loaded its mask. Locate it, create a new mask,
 						// and try to commit it to reserve the edge. The
 						// technique here is essentially the same as above, but
 						// the byte we're looking for is 0, so we don't xor.
 						v = (cm - recordPop) &^ cm & (recordPop << 7)
 						var k int
 						if uint64(^uint(0)) >= uint64(^uintptr(0)) {
 							k = bits.TrailingZeros(uint(v)) / 8
 						} else {
 							k = bits.TrailingZeros(uint(v)) / 8
 						}
 						n := cm | uintptr(slot[0])<<(k*8)
 						if atomic.CompareAndSwapUintptr(&cur.mask, cm, n) {
 							// We got the edge. Now we can allocate the node.
 							// This is the last node in the branch, as well.
 							node, leaf := recordBranch(vm, slot[1:])
 							atomic.StorePointer((*unsafe.Pointer)(unsafe.Pointer(&cur.children[k])), unsafe.Pointer(node))
 							return leaf
 						}
 						// Someone else added an edge, and it might have been the
 						// same edge we're looking for. Try again from the start.
 						continue
 					}
 					next := (*slotRecord1)(atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&cur.sibling))))
 					if next == nil {
 						// This was the last record in this level. Try to add a new
 						// sibling. Another goroutine might create a new sibling
 						// while we're allocating ours, though, so we don't want to
 						// try to make the whole branch.
 						next = &slotRecord1{}
 						if !atomic.CompareAndSwapPointer((*unsafe.Pointer)(unsafe.Pointer(&cur.sibling)), nil, unsafe.Pointer(next)) {
 							// Someone else added the sibling. Use theirs.
 							next = (*slotRecord1)(atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&cur.sibling))))
 						}
 					}
 					cur = next
 					continue
 				}
 				// The lowest set bit is in the byte that matched c.
 				// There isn't currently any platform where uint is smaller
 				// than uintptr, but this check happens at compile-time anyway.
 				var k int
 				if uint64(^uint(0)) >= uint64(^uintptr(0)) {
 					k = bits.TrailingZeros(uint(v)) / 8
 				} else {
 					k = bits.TrailingZeros64(uint64(v)) / 8
 				}
 				next := (*slotBranch)(atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&cur.children[k]))))
 				for next == nil {
 					// The edge to this child exists, but the node hasn't been set.
 					// Another goroutine must be in the process of setting it. Spin
 					// until it's available.
 					next = (*slotBranch)(atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&cur.children[k]))))
 				}
 				branch = next
 				break
 			}
 			slot = slot[1:]
 			// This is the last iteration for this slot.
 		default:
 			// Check two-byte edges.
 			// rec2 isn't a pointer, so we don't need to get its reference
 			// atomically.
 			cur := &branch.rec2
 			c := uintptr(slot[0]) | uintptr(slot[1])<<8
 			m := c * recordPop2
 			for {
 				// This is basically the same as above, except replace "byte"
 				// with "two-byte word."
 				cm := atomic.LoadUintptr(&cur.mask)
 				v := cm ^ m
 				v = (v - recordPop2) &^ v & (recordPop2 << 15)
 				if v == 0 {
 					if cm < 1<<(32<<(^uintptr(0)>>32&1)-7) {
 						v = (cm - recordPop2) &^ cm & (recordPop2 << 15)
 						var k int
 						if uint64(^uint(0)) >= uint64(^uintptr(0)) {
 							k = bits.TrailingZeros(uint(v)) / 16
 						} else {
 							k = bits.TrailingZeros(uint(v)) / 16
 						}
 						n := cm | uintptr(c)<<(k*16)
 						if atomic.CompareAndSwapUintptr(&cur.mask, cm, n) {
 							node, leaf := recordBranch(vm, slot[2:])
 							atomic.StorePointer((*unsafe.Pointer)(unsafe.Pointer(&cur.children[k])), unsafe.Pointer(node))
 							return leaf
 						}
 						continue
 					}
 					next := (*slotRecord2)(atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&cur.sibling))))
 					if next == nil {
 						next = &slotRecord2{}
 						if !atomic.CompareAndSwapPointer((*unsafe.Pointer)(unsafe.Pointer(&cur.sibling)), nil, unsafe.Pointer(next)) {
 							next = (*slotRecord2)(atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&cur.sibling))))
 						}
 					}
 					cur = next
 					continue
 				}
 				var k int
 				if uint64(^uint(0)) >= uint64(^uintptr(0)) {
 					k = bits.TrailingZeros(uint(v)) / 16
 				} else {
 					k = bits.TrailingZeros64(uint64(v)) / 16
 				}
 				next := (*slotBranch)(atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&cur.children[k]))))
 				for next == nil {
 					next = (*slotBranch)(atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&cur.children[k]))))
 				}
 				branch = next
 				break
 			}
 			slot = slot[2:]
 		}
 	}
 	sy := (*syncSlot)(atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&branch.leaf))))
 	if sy == nil {
 		// The node existed, but its value was unset. This happens if the slot
 		// we're creating is a prefix of a slot that was added earlier.
 		sy = newSy(vm, nil)
 		if atomic.CompareAndSwapPointer((*unsafe.Pointer)(unsafe.Pointer(&branch.leaf)), nil, unsafe.Pointer(sy)) {
 			return sy
 		}
 		// Someone else created the slot before us. Use theirs.
 		sy = (*syncSlot)(atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&branch.leaf))))
 	}
 	sy.claim(vm)
 	return sy
 }

 // foreach executes a function for each slot. If exec returns false, then the
 // iteration ceases. The slots passed to exec are claimed by VM and will be
 // released afterward.
 func (s *actualSlots) foreach(vm *VM, exec func(name string, sy *syncSlot) bool) {
 	cur := (*slotBranch)(atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&s.root))))
 	if cur == nil {
 		return
 	}
 	cur.foreachIter(vm, exec, nil)
 }

 // foreachIter executes actualSlots.foreach for a single depth of the trie.
 func (r *slotBranch) foreachIter(vm *VM, exec func(name string, sy *syncSlot) bool, b []byte) []byte {
 	sy := (*syncSlot)(atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&r.leaf))))
 	if sy != nil {
 		res := true
 		sy.claim(vm)
 		if sy.value != nil {
 			res = exec(string(b), sy)
 		}
 		sy.release()
 		if !res {
 			return nil
 		}
 	}
 	// Handle the zero edge specially.
 	zero := (*slotBranch)(atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&r.zero))))
 	if zero != nil {
 		b = append(b, 0)
 		b = zero.foreachIter(vm, exec, b)
 		if b == nil {
 			return nil
 		}
 		b = b[:len(b)-1]
 	}
 	// Iterate over one-byte edges.
 	rec1 := (*slotRecord1)(atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&r.rec1))))
 	if rec1 != nil {
 		if b = rec1.foreachIter1(vm, exec, b); b == nil {
 			return nil
 		}
 	}
 	// Now two-byte edges. We can just return its result directly.
 	return r.rec2.foreachIter2(vm, exec, b)
 }

 // foreachIter1 executes slotBranch.foreachIter for the branch's 1-byte edges.
 func (cur *slotRecord1) foreachIter1(vm *VM, exec func(name string, sy *syncSlot) bool, b []byte) []byte {
 	var branch *slotBranch
 	for cur != nil {
 		for k := 0; k < recordChildren; k++ {
 			cm := atomic.LoadUintptr(&cur.mask)
 			c := byte(cm >> (k * 8))
 			if c == 0 {
 				return b
 			}
 			branch = (*slotBranch)(atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&cur.children[k]))))
 			if branch == nil {
 				continue
 			}
 			b = append(b, c)
 			b = branch.foreachIter(vm, exec, b)
 			if b == nil {
 				return nil
 			}
 			b = b[:len(b)-1]
 		}
 		cur = (*slotRecord1)(atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&cur.sibling))))
 	}
 	return b
 }

 // foreachIter2 executes slotBranch.foreachIter for the branch's 2-byte edges.
 func (cur *slotRecord2) foreachIter2(vm *VM, exec func(name string, sy *syncSlot) bool, b []byte) []byte {
 	var branch *slotBranch
 	for cur != nil {
 		for k := 0; k < recordChildren/2; k++ {
 			cm := atomic.LoadUintptr(&cur.mask)
 			c := uint16(cm >> (k * 16))
 			if c == 0 {
 				return b
 			}
 			branch = (*slotBranch)(atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&cur.children[k]))))
 			if branch == nil {
 				continue
 			}
 			b = append(b, byte(c), byte(c>>8))
 			b = branch.foreachIter(vm, exec, b)
 			if b == nil {
 				return nil
 			}
 			b = b[:len(b)-2]
 		}
 		cur = (*slotRecord2)(atomic.LoadPointer((*unsafe.Pointer)(unsafe.Pointer(&cur.sibling))))
 	}
 	return b
 }

 // recordBranch allocates an entire new branch of a slots trie.
 func recordBranch(vm *VM, branch string) (trunk *slotBranch, slot *syncSlot) {
 	trunk = &slotBranch{}
 	leaf := newSy(vm, nil)
 	if len(branch) > 4 {
 		// Only create shortcuts that actually skip nodes.
 		trunk.scut = leaf
 		trunk.scutName = branch
 	}
 	cur := trunk
 	for len(branch) > 1 {
 		if branch[0] == 0 {
 			// Create zero edge.
 			cur.hasZero = 1
 			cur.zero = &slotBranch{}
 			cur = cur.zero
 			branch = branch[1:]
 			continue
 		}
 		// Create two-byte edge.
 		cur.rec2 = slotRecord2{
 			mask:     uintptr(branch[0]) | uintptr(branch[1])<<8,
 			children: [recordChildren / 2]*slotBranch{0: &slotBranch{}},
 		}
 		cur = cur.rec2.children[0]
 		branch = branch[2:]
 	}
 	if len(branch) > 0 {
 		// Create one-byte edge.
 		cur.rec1 = &slotRecord1{
 			mask:     uintptr(branch[0]),
 			children: [recordChildren]*slotBranch{0: &slotBranch{}},
 		}
 		cur = cur.rec1.children[0]
 	}
 	cur.leaf = leaf
 	return trunk, cur.leaf
 }

 // Slots represents the set of messages to which an object responds.
 type Slots = map[string]*Object

 // GetSlot checks obj and its ancestors in depth-first order without
 // cycles for a slot, returning the slot value and the proto which had it.
 // proto is nil if and only if the slot was not found. This method may acquire
 // the object's lock, as well as the lock of each ancestor in turn.
 func (vm *VM) GetSlot(obj *Object, slot string) (value, proto *Object) {
 	if obj == nil {
 		return nil, nil
 	}
 	// Check obj itself before using the graph traversal mechanisms.
 	if sy := vm.localSyncSlot(obj, slot); sy != nil {
 		value = sy.value
 		sy.release()
 		return value, obj
 	}
 	sy, proto := vm.getSlotAncestor(obj, slot)
 	if proto != nil {
 		value = sy.value
 		sy.release()
 	}
 	return
 }

 // GetSlotSync is like GetSlot, but it returns an extra function to synchronize
 // accesses to the slot. Other VMs will block on attempts to read or write the
 // same slot, whether it is on obj or an ancestor, until release is called.
 // If it is not nil, release must be called exactly once. Both proto and
 // release are nil if and only if the slot is not found.
 func (vm *VM) GetSlotSync(obj *Object, slot string) (value, proto *Object, release func()) {
 	if obj == nil {
 		return nil, nil, nil
 	}
 	if sy := vm.localSyncSlot(obj, slot); sy != nil {
 		// It'd be trivial to wrap sy.release in a *sync.Once so we don't have
 		// to worry about multiple calls, but that would be slow and would mean
 		// every call to this allocates.
 		return sy.value, obj, sy.release
 	}
 	sy, proto := vm.getSlotAncestor(obj, slot)
 	if proto != nil {
 		value = sy.value
 		release = sy.release
 	}
 	return
 }

 // getSlotAncestor finds a slot on obj's ancestors.
 func (vm *VM) getSlotAncestor(obj *Object, slot string) (sy *syncSlot, proto *Object) {
 	vm.protoSet.Reset()
 	vm.protoSet.Add(obj.UniqueID())
 	for {
 		obj.Lock()
 		switch {
 		case obj.proto == nil:
 			// The slot does not exist.
 			obj.Unlock()
 			return nil, nil
 		case len(obj.plusproto) == 0:
 			// One proto. We don't need to use vm.protoStack.
 			rp := obj.proto
 			obj.Unlock()
 			obj = rp
 			if !vm.protoSet.Add(obj.UniqueID()) {
 				return nil, nil
 			}
 			if sy := vm.localSyncSlot(obj, slot); sy != nil {
 				return sy, obj
 			}
 			// Try again with the proto.
 		default:
 			// Several protos. Using vm.protoStack is more efficient than using
 			// the goroutine stack for explicit recursion.
 			for i := len(obj.plusproto) - 1; i >= 0; i-- {
 				if p := obj.plusproto[i]; vm.protoSet.Add(p.UniqueID()) {
 					vm.protoStack = append(vm.protoStack, p)
 				}
 			}
 			if vm.protoSet.Add(obj.proto.UniqueID()) {
 				vm.protoStack = append(vm.protoStack, obj.proto)
 			}
 			obj.Unlock()
 			if len(vm.protoStack) == 0 {
 				// If all this object's protos have been checked already, stop.
 				return nil, nil
 			}
 			for len(vm.protoStack) > 1 {
 				obj = vm.protoStack[len(vm.protoStack)-1] // grab the top
 				if sy := vm.localSyncSlot(obj, slot); sy != nil {
 					vm.protoStack = vm.protoStack[:0]
 					return sy, obj
 				}
 				vm.protoStack = vm.protoStack[:len(vm.protoStack)-1] // actually pop
 				obj.Lock()
 				if obj.proto != nil {
 					for i := len(obj.plusproto) - 1; i >= 0; i-- {
 						if p := obj.plusproto[i]; vm.protoSet.Add(p.UniqueID()) {
 							vm.protoStack = append(vm.protoStack, p)
 						}
 					}
 					if vm.protoSet.Add(obj.proto.UniqueID()) {
 						vm.protoStack = append(vm.protoStack, obj.proto)
 					}
 				}
 				obj.Unlock()
 			}
 			// The stack is down to one object. Check it, then try to return to
 			// faster cases.
 			obj = vm.protoStack[0]
 			vm.protoStack = vm.protoStack[:0]
 			if sy := vm.localSyncSlot(obj, slot); sy != nil {
 				return sy, obj
 			}
 		}
 	}
 }

 // GetLocalSlot checks only obj's own slots for a slot.
 func (vm *VM) GetLocalSlot(obj *Object, slot string) (value *Object, ok bool) {
 	if obj == nil {
 		return nil, false
 	}
 	if sy := vm.localSyncSlot(obj, slot); sy != nil {
 		value = sy.value
 		sy.release()
 		return value, true
 	}
 	return nil, false
 }

 // GetLocalSlotSync is like GetLocalSlot, but it returns a function to
 // synchronize accesses to the slot. Other VMs will block on attempts to read
 // or write the same slot until release is called. If it is not nil, release
 // must be called exactly once. release is nil if and only if the slot does not
 // exist on obj.
 func (vm *VM) GetLocalSlotSync(obj *Object, slot string) (value *Object, release func()) {
 	if obj == nil {
 		return nil, nil
 	}
 	sy := vm.localSyncSlot(obj, slot)
 	if sy != nil {
 		return sy.value, sy.release
 	}
 	return nil, nil
 }

 // localSyncSlot claims a slot if it exists on obj.
 func (vm *VM) localSyncSlot(obj *Object, slot string) *syncSlot {
 	sy := obj.slots.load(slot)
 	if sy == nil {
 		return nil
 	}
 	sy.claim(vm)
 	if sy.value == nil {
 		// The slot value can be nil if the value is currently being created,
 		// like in x := x, or if the slot was created but then an exception
 		// occurred while evaluating its result, or if the slot was removed. In
 		// any case, the slot doesn't actually exist.
 		sy.release()
 		return nil
 	}
 	return sy
 }

 // GetAllSlots returns a copy of all slots on obj. This may block if another
 // coroutine is accessing any slot on the object.
 func (vm *VM) GetAllSlots(obj *Object) Slots {
 	slots := Slots{}
 	obj.slots.foreach(vm, func(key string, value *syncSlot) bool {
 		if value.value != nil {
 			slots[key] = value.value
 		}
 		return true
 	})
 	return slots
 }

 // SetSlot sets the value of a slot on obj.
 func (vm *VM) SetSlot(obj *Object, slot string, value *Object) {
 	sy := obj.slots.open(vm, slot)
 	sy.value = value
 	sy.release()
 }

 // SetSlotSync creates a synchronized setter for a slot on obj. set must be
 // called exactly once with the new slot value. Users should call SetSlotSync
 // before evaluating the Io code that will determine the value, e.g.:
 //
 // 	set := vm.SetSlotSync(obj, slot)
 // 	value, stop := msg.Eval(vm, locals)
 // 	if stop != NoStop {
 // 		set(nil)
 // 		return vm.Stop(value, stop)
 // 	}
 // 	set(value)
 //
 // set must be called exactly once.
 func (vm *VM) SetSlotSync(obj *Object, slot string) (set func(*Object)) {
 	sy := obj.slots.open(vm, slot)
 	return func(value *Object) {
 		sy.value = value
 		sy.release()
 	}
 }

 // SetSlots sets the values of multiple slots on obj.
 func (vm *VM) SetSlots(obj *Object, slots Slots) {
 	for slot, value := range slots {
 		vm.SetSlot(obj, slot, value)
 	}
 }

 // definitelyNewSlots creates the given new slots on obj. This is intended for
 // creating new objects; it is erroneous to use this if any slot in slots
 // already exists on obj.
 func (vm *VM) definitelyNewSlots(obj *Object, slots Slots) {
 	// TODO: create the trie directly instead of just setting each slot
 	for slot, value := range slots {
 		vm.SetSlot(obj, slot, value)
 	}
 }

 // RemoveSlot removes slots from obj's local slots, if they are present.
 func (vm *VM) RemoveSlot(obj *Object, slots ...string) {
 	for _, slot := range slots {
 		// TODO: only remove slots that exist
 		vm.SetSlot(obj, slot, nil)
 	}
 }
No results found