4584930191

Committed 01 Apr 2023 07:55PM UTC coverage: 92.375% (+2.9%) from 89.483%

Build Type

github

Committed by Huan Du

Commit Message

refactory AllocatorMethods to support parent allocator

Pull Request Pull Request #14: Let Allocator hold all customization data

Run Details

197 of 197 new or added lines in 5 files covered. (100.0%)

1163 of 1259 relevant lines covered (92.37%)

1.03 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

93.92

/allocator.go

// Copyright 2023 Huan Du. All rights reserved.
// Licensed under the MIT license that can be found in the LICENSE file.

package clone

import (
        "reflect"
        "runtime"
        "sync"
        "unsafe"
)

var typeOfAllocator = reflect.TypeOf(Allocator{})

// defaultAllocator is the default allocator and allocates memory from heap.
var defaultAllocator = &Allocator{
        new:       heapNew,
        makeSlice: heapMakeSlice,
        makeMap:   heapMakeMap,
        makeChan:  heapMakeChan,
        isScalar:  IsScalar,
}

// Allocator is a utility type for memory allocation.
type Allocator struct {
        parent *Allocator

        pool      unsafe.Pointer
        new       func(pool unsafe.Pointer, t reflect.Type) reflect.Value
        makeSlice func(pool unsafe.Pointer, t reflect.Type, len, cap int) reflect.Value
        makeMap   func(pool unsafe.Pointer, t reflect.Type, n int) reflect.Value
        makeChan  func(pool unsafe.Pointer, t reflect.Type, buffer int) reflect.Value
        isScalar  func(t reflect.Kind) bool

        cachedStructTypes     sync.Map
        cachedPointerTypes    sync.Map
        cachedCustomFuncTypes sync.Map
}

// FromHeap creates an allocator which allocate memory from heap.
func FromHeap() *Allocator {
        return NewAllocator(nil, nil)
}

// NewAllocator creates an allocator which allocate memory from the pool.
// Both pool and methods are optional.
//
// If methods.New is not nil, the allocator itself is created by calling methods.New.
//
// The pool is a pointer to the memory pool which is opaque to the allocator.
// It's methods's responsibility to allocate memory from the pool properly.
func NewAllocator(pool unsafe.Pointer, methods *AllocatorMethods) (allocator *Allocator) {
        parent := methods.parent()
        new := methods.new(parent, pool)

        // Allocate the allocator from the pool.
        val := new(pool, typeOfAllocator)
        allocator = (*Allocator)(unsafe.Pointer(val.Pointer()))
        runtime.KeepAlive(val)

        allocator.pool = pool
        allocator.new = new
        allocator.makeSlice = methods.makeSlice(parent, pool)
        allocator.makeMap = methods.makeMap(parent, pool)
        allocator.makeChan = methods.makeChan(parent, pool)
        allocator.isScalar = methods.isScalar(parent)

        if parent == nil {
                parent = defaultAllocator
        }

        allocator.parent = parent
        return
}

// New returns a new zero value of t.
func (a *Allocator) New(t reflect.Type) reflect.Value {
        return a.new(a.pool, t)
}

// MakeSlice creates a new zero-initialized slice value of t with len and cap.
func (a *Allocator) MakeSlice(t reflect.Type, len, cap int) reflect.Value {
        return a.makeSlice(a.pool, t, len, cap)
}

// MakeMap creates a new map with minimum size n.
func (a *Allocator) MakeMap(t reflect.Type, n int) reflect.Value {
        return a.makeMap(a.pool, t, n)
}

// MakeChan creates a new chan with buffer.
func (a *Allocator) MakeChan(t reflect.Type, buffer int) reflect.Value {
        return a.makeChan(a.pool, t, buffer)
}

// Clone recursively deep clone val to a new value with memory allocated from a.
func (a *Allocator) Clone(val reflect.Value) reflect.Value {
        return a.clone(val, true)
}

func (a *Allocator) clone(val reflect.Value, inCustomFunc bool) reflect.Value {
        if !val.IsValid() {
                return val
        }

        state := &cloneState{
                allocator: a,
        }

        if inCustomFunc {
                state.skipCustomFuncValue = val
        }

        return state.clone(val)
}

// CloneSlowly recursively deep clone val to a new value with memory allocated from a.
// It marks all cloned values internally, thus it can clone v with cycle pointer.
func (a *Allocator) CloneSlowly(val reflect.Value) reflect.Value {
        return a.cloneSlowly(val, true)
}

func (a *Allocator) cloneSlowly(val reflect.Value, inCustomFunc bool) reflect.Value {
        if !val.IsValid() {
                return val
        }

        state := &cloneState{
                allocator: a,
                visited:   visitMap{},
                invalid:   invalidPointers{},
        }

        if inCustomFunc {
                state.skipCustomFuncValue = val
        }

        cloned := state.clone(val)
        state.fix(cloned)
        return cloned
}

func (a *Allocator) loadStructType(t reflect.Type) (st structType) {
        st, ok := a.lookupStructType(t)

        if ok {
                return
        }

        num := t.NumField()
        pointerFields := make([]structFieldType, 0, num)

        // Find pointer fields in depth-first order.
        for i := 0; i < num; i++ {
                field := t.Field(i)
                ft := field.Type
                k := ft.Kind()

                if a.isScalar(k) {
                        continue
                }

                switch k {
                case reflect.Array:
                        if ft.Len() == 0 {
                                continue
                        }

                        elem := ft.Elem()

                        if a.isScalar(elem.Kind()) {
                                continue
                        }

                        if elem.Kind() == reflect.Struct {
                                if fst := a.loadStructType(elem); fst.CanShadowCopy() {
                                        continue
                                }
                        }
                case reflect.Struct:
                        if fst := a.loadStructType(ft); fst.CanShadowCopy() {
                                continue
                        }
                }

                pointerFields = append(pointerFields, structFieldType{
                        Offset: field.Offset,
                        Index:  i,
                })
        }

        if len(pointerFields) == 0 {
                pointerFields = nil // Release memory ASAP.
        }

        st = structType{
                PointerFields: pointerFields,
        }

        // Load custom function.
        current := a

        for current != nil {
                if fn, ok := current.cachedCustomFuncTypes.Load(t); ok {
                        st.fn = fn.(Func)
                        break
                }

                current = current.parent
        }

        a.cachedStructTypes.LoadOrStore(t, st)
        return
}

func (a *Allocator) lookupStructType(t reflect.Type) (st structType, ok bool) {
        var v interface{}
        current := a

        for current != nil {
                v, ok = current.cachedStructTypes.Load(t)

                if ok {
                        st = v.(structType)
                        return
                }

                current = current.parent
        }

        return
}

func (a *Allocator) isOpaquePointer(t reflect.Type) (ok bool) {
        current := a

        for current != nil {
                if _, ok = current.cachedPointerTypes.Load(t); ok {
                        return
                }

                current = current.parent
        }

        return
}

// MarkAsScalar marks t as a scalar type so that all clone methods will copy t by value.
// If t is not struct or pointer to struct, MarkAsScalar ignores t.
//
// In the most cases, it's not necessary to call it explicitly.
// If a struct type contains scalar type fields only, the struct will be marked as scalar automatically.
//
// Here is a list of types marked as scalar by default:
//   - time.Time
//   - reflect.Value
func (a *Allocator) MarkAsScalar(t reflect.Type) {
        for t.Kind() == reflect.Ptr {
                t = t.Elem()
        }

        if t.Kind() != reflect.Struct {
                return
        }

        a.cachedStructTypes.Store(t, zeroStructType)
}

// MarkAsOpaquePointer marks t as an opaque pointer so that all clone methods will copy t by value.
// If t is not a pointer, MarkAsOpaquePointer ignores t.
//
// Here is a list of types marked as opaque pointers by default:
//   - `elliptic.Curve`, which is `*elliptic.CurveParam` or `elliptic.p256Curve`;
//   - `reflect.Type`, which is `*reflect.rtype` defined in `runtime`.
func (a *Allocator) MarkAsOpaquePointer(t reflect.Type) {
        if t.Kind() != reflect.Ptr {
                return
        }

        a.cachedPointerTypes.Store(t, struct{}{})
}

// SetCustomFunc sets a custom clone function for type t.
// If t is not struct or pointer to struct, SetCustomFunc ignores t.
//
// If fn is nil, remove the custom clone function for type t.
func (a *Allocator) SetCustomFunc(t reflect.Type, fn Func) {
        if fn == nil {
                a.cachedCustomFuncTypes.Delete(t)
                return
        }

        for t.Kind() == reflect.Ptr {
                t = t.Elem()
        }

        if t.Kind() != reflect.Struct {
                return
        }

        a.cachedCustomFuncTypes.Store(t, fn)
}

func heapNew(pool unsafe.Pointer, t reflect.Type) reflect.Value {
        return reflect.New(t)
}

func heapMakeSlice(pool unsafe.Pointer, t reflect.Type, len, cap int) reflect.Value {
        return reflect.MakeSlice(t, len, cap)
}

func heapMakeMap(pool unsafe.Pointer, t reflect.Type, n int) reflect.Value {
        return reflect.MakeMapWithSize(t, n)
}

func heapMakeChan(pool unsafe.Pointer, t reflect.Type, buffer int) reflect.Value {
        return reflect.MakeChan(t, buffer)
}

1	// Copyright 2023 Huan Du. All rights reserved.
2	// Licensed under the MIT license that can be found in the LICENSE file.
3
4	package clone
5
6	import (
7	"reflect"
8	"runtime"
9	"sync"
10	"unsafe"
11	)
12
13	var typeOfAllocator = reflect.TypeOf(Allocator{})
14
15	// defaultAllocator is the default allocator and allocates memory from heap.
16	var defaultAllocator = &Allocator{
17	new: heapNew,
18	makeSlice: heapMakeSlice,
19	makeMap: heapMakeMap,
20	makeChan: heapMakeChan,
21	isScalar: IsScalar,
22	}
23
24	// Allocator is a utility type for memory allocation.
25	type Allocator struct {
26	parent *Allocator
27
28	pool unsafe.Pointer
29	new func(pool unsafe.Pointer, t reflect.Type) reflect.Value
30	makeSlice func(pool unsafe.Pointer, t reflect.Type, len, cap int) reflect.Value
31	makeMap func(pool unsafe.Pointer, t reflect.Type, n int) reflect.Value
32	makeChan func(pool unsafe.Pointer, t reflect.Type, buffer int) reflect.Value
33	isScalar func(t reflect.Kind) bool
34
35	cachedStructTypes sync.Map
36	cachedPointerTypes sync.Map
37	cachedCustomFuncTypes sync.Map
38	}
39
40	// FromHeap creates an allocator which allocate memory from heap.
41	func FromHeap() *Allocator {	1✔
42	return NewAllocator(nil, nil)	1✔
43	}	1✔
44
45	// NewAllocator creates an allocator which allocate memory from the pool.
46	// Both pool and methods are optional.
47	//
48	// If methods.New is not nil, the allocator itself is created by calling methods.New.
49	//
50	// The pool is a pointer to the memory pool which is opaque to the allocator.
51	// It's methods's responsibility to allocate memory from the pool properly.
52	func NewAllocator(pool unsafe.Pointer, methods AllocatorMethods) (allocator Allocator) {	1✔
53	parent := methods.parent()	1✔
54	new := methods.new(parent, pool)	1✔
55		1✔
56	// Allocate the allocator from the pool.	1✔
57	val := new(pool, typeOfAllocator)	1✔
58	allocator = (*Allocator)(unsafe.Pointer(val.Pointer()))	1✔
59	runtime.KeepAlive(val)	1✔
60		1✔
61	allocator.pool = pool	1✔
62	allocator.new = new	1✔
63	allocator.makeSlice = methods.makeSlice(parent, pool)	1✔
64	allocator.makeMap = methods.makeMap(parent, pool)	1✔
65	allocator.makeChan = methods.makeChan(parent, pool)	1✔
66	allocator.isScalar = methods.isScalar(parent)	1✔
67		1✔
68	if parent == nil {	2✔
69	parent = defaultAllocator	1✔
70	}	1✔
71
72	allocator.parent = parent	1✔
73	return	1✔
74	}
75
76	// New returns a new zero value of t.
77	func (a *Allocator) New(t reflect.Type) reflect.Value {	1✔
78	return a.new(a.pool, t)	1✔
79	}	1✔
80
81	// MakeSlice creates a new zero-initialized slice value of t with len and cap.
82	func (a *Allocator) MakeSlice(t reflect.Type, len, cap int) reflect.Value {	1✔
83	return a.makeSlice(a.pool, t, len, cap)	1✔
84	}	1✔
85
86	// MakeMap creates a new map with minimum size n.
87	func (a *Allocator) MakeMap(t reflect.Type, n int) reflect.Value {	1✔
88	return a.makeMap(a.pool, t, n)	1✔
89	}	1✔
90
91	// MakeChan creates a new chan with buffer.
92	func (a *Allocator) MakeChan(t reflect.Type, buffer int) reflect.Value {	1✔
93	return a.makeChan(a.pool, t, buffer)	1✔
94	}	1✔
95
96	// Clone recursively deep clone val to a new value with memory allocated from a.
97	func (a *Allocator) Clone(val reflect.Value) reflect.Value {	1✔
98	return a.clone(val, true)	1✔
99	}	1✔
100
101	func (a *Allocator) clone(val reflect.Value, inCustomFunc bool) reflect.Value {	1✔
102	if !val.IsValid() {	1✔
103	return val	×
104	}	×
105
106	state := &cloneState{	1✔
107	allocator: a,	1✔
108	}	1✔
109		1✔
110	if inCustomFunc {	2✔
111	state.skipCustomFuncValue = val	1✔
112	}	1✔
113
114	return state.clone(val)	1✔
115	}
116
117	// CloneSlowly recursively deep clone val to a new value with memory allocated from a.
118	// It marks all cloned values internally, thus it can clone v with cycle pointer.
119	func (a *Allocator) CloneSlowly(val reflect.Value) reflect.Value {	1✔
120	return a.cloneSlowly(val, true)	1✔
121	}	1✔
122
123	func (a *Allocator) cloneSlowly(val reflect.Value, inCustomFunc bool) reflect.Value {	1✔
124	if !val.IsValid() {	1✔
125	return val	×
126	}	×
127
128	state := &cloneState{	1✔
129	allocator: a,	1✔
130	visited: visitMap{},	1✔
131	invalid: invalidPointers{},	1✔
132	}	1✔
133		1✔
134	if inCustomFunc {	2✔
135	state.skipCustomFuncValue = val	1✔
136	}	1✔
137
138	cloned := state.clone(val)	1✔
139	state.fix(cloned)	1✔
140	return cloned	1✔
141	}
142
143	func (a *Allocator) loadStructType(t reflect.Type) (st structType) {	1✔
144	st, ok := a.lookupStructType(t)	1✔
145		1✔
146	if ok {	2✔
147	return	1✔
148	}	1✔
149
150	num := t.NumField()	1✔
151	pointerFields := make([]structFieldType, 0, num)	1✔
152		1✔
153	// Find pointer fields in depth-first order.	1✔
154	for i := 0; i < num; i++ {	2✔
155	field := t.Field(i)	1✔
156	ft := field.Type	1✔
157	k := ft.Kind()	1✔
158		1✔
159	if a.isScalar(k) {	2✔
160	continue	1✔
161	}
162
163	switch k {	1✔
164	case reflect.Array:	1✔
165	if ft.Len() == 0 {	2✔
166	continue	1✔
167	}
168
169	elem := ft.Elem()	1✔
170		1✔
171	if a.isScalar(elem.Kind()) {	2✔
172	continue	1✔
173	}
174
175	if elem.Kind() == reflect.Struct {	1✔
176	if fst := a.loadStructType(elem); fst.CanShadowCopy() {	×
177	continue	×
178	}
179	}
180	case reflect.Struct:	1✔
181	if fst := a.loadStructType(ft); fst.CanShadowCopy() {	2✔
182	continue	1✔
183	}
184	}
185
186	pointerFields = append(pointerFields, structFieldType{	1✔
187	Offset: field.Offset,	1✔
188	Index: i,	1✔
189	})	1✔
190	}
191
192	if len(pointerFields) == 0 {	2✔
193	pointerFields = nil // Release memory ASAP.	1✔
194	}	1✔
195
196	st = structType{	1✔
197	PointerFields: pointerFields,	1✔
198	}	1✔
199		1✔
200	// Load custom function.	1✔
201	current := a	1✔
202		1✔
203	for current != nil {	2✔
204	if fn, ok := current.cachedCustomFuncTypes.Load(t); ok {	2✔
205	st.fn = fn.(Func)	1✔
206	break	1✔
207	}
208
209	current = current.parent	1✔
210	}
211
212	a.cachedStructTypes.LoadOrStore(t, st)	1✔
213	return	1✔
214	}
215
216	func (a *Allocator) lookupStructType(t reflect.Type) (st structType, ok bool) {	1✔
217	var v interface{}	1✔
218	current := a	1✔
219		1✔
220	for current != nil {	2✔
221	v, ok = current.cachedStructTypes.Load(t)	1✔
222		1✔
223	if ok {	2✔
224	st = v.(structType)	1✔
225	return	1✔
226	}	1✔
227
228	current = current.parent	1✔
229	}
230
231	return	1✔
232	}
233
234	func (a *Allocator) isOpaquePointer(t reflect.Type) (ok bool) {	1✔
235	current := a	1✔
236		1✔
237	for current != nil {	2✔
238	if _, ok = current.cachedPointerTypes.Load(t); ok {	2✔
239	return	1✔
240	}	1✔
241
242	current = current.parent	1✔
243	}
244
245	return	1✔
246	}
247
248	// MarkAsScalar marks t as a scalar type so that all clone methods will copy t by value.
249	// If t is not struct or pointer to struct, MarkAsScalar ignores t.
250	//
251	// In the most cases, it's not necessary to call it explicitly.
252	// If a struct type contains scalar type fields only, the struct will be marked as scalar automatically.
253	//
254	// Here is a list of types marked as scalar by default:
255	// - time.Time
256	// - reflect.Value
257	func (a *Allocator) MarkAsScalar(t reflect.Type) {	1✔
258	for t.Kind() == reflect.Ptr {	2✔
259	t = t.Elem()	1✔
260	}	1✔
261
262	if t.Kind() != reflect.Struct {	2✔
263	return	1✔
264	}	1✔
265
266	a.cachedStructTypes.Store(t, zeroStructType)	1✔
267	}
268
269	// MarkAsOpaquePointer marks t as an opaque pointer so that all clone methods will copy t by value.
270	// If t is not a pointer, MarkAsOpaquePointer ignores t.
271	//
272	// Here is a list of types marked as opaque pointers by default:
273	// - `elliptic.Curve`, which is `*elliptic.CurveParam` or `elliptic.p256Curve`;
274	// - `reflect.Type`, which is `*reflect.rtype` defined in `runtime`.
275	func (a *Allocator) MarkAsOpaquePointer(t reflect.Type) {	1✔
276	if t.Kind() != reflect.Ptr {	2✔
277	return	1✔
278	}	1✔
279
280	a.cachedPointerTypes.Store(t, struct{}{})	1✔
281	}
282
283	// SetCustomFunc sets a custom clone function for type t.
284	// If t is not struct or pointer to struct, SetCustomFunc ignores t.
285	//
286	// If fn is nil, remove the custom clone function for type t.
287	func (a *Allocator) SetCustomFunc(t reflect.Type, fn Func) {	1✔
288	if fn == nil {	1✔
289	a.cachedCustomFuncTypes.Delete(t)	×
290	return	×
291	}	×
292
293	for t.Kind() == reflect.Ptr {	2✔
294	t = t.Elem()	1✔
295	}	1✔
296
297	if t.Kind() != reflect.Struct {	1✔
298	return	×
299	}	×
300
301	a.cachedCustomFuncTypes.Store(t, fn)	1✔
302	}
303
304	func heapNew(pool unsafe.Pointer, t reflect.Type) reflect.Value {	1✔
305	return reflect.New(t)	1✔
306	}	1✔
307
308	func heapMakeSlice(pool unsafe.Pointer, t reflect.Type, len, cap int) reflect.Value {	1✔
309	return reflect.MakeSlice(t, len, cap)	1✔
310	}	1✔
311
312	func heapMakeMap(pool unsafe.Pointer, t reflect.Type, n int) reflect.Value {	1✔
313	return reflect.MakeMapWithSize(t, n)	1✔
314	}	1✔
315
316	func heapMakeChan(pool unsafe.Pointer, t reflect.Type, buffer int) reflect.Value {	1✔
317	return reflect.MakeChan(t, buffer)	1✔
318	}	1✔

huandu / go-clone / 4584930191

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous