1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
|
package litter
import (
"fmt"
"reflect"
"sort"
)
// mapReusedPointers takes a structure, and recursively maps all pointers mentioned in the tree,
// detecting circular references, and providing a list of all pointers that was referenced at
// least twice by the provided structure.
func mapReusedPointers(v reflect.Value) ptrmap {
pm := &pointerVisitor{}
pm.consider(v)
return pm.reused
}
// A map of pointers.
type ptrinfo struct {
id int
parent *ptrmap
}
func (p *ptrinfo) label() string {
if p.id == -1 {
p.id = p.parent.count
p.parent.count++
}
return fmt.Sprintf("p%d", p.id)
}
type ptrkey struct {
p uintptr
t reflect.Type
}
func ptrkeyFor(v reflect.Value) (k ptrkey) {
k.p = v.Pointer()
for v.Kind() == reflect.Ptr {
v = v.Elem()
}
if v.IsValid() {
k.t = v.Type()
}
return
}
type ptrmap struct {
m map[ptrkey]*ptrinfo
count int
}
// Returns true if contains a pointer.
func (pm *ptrmap) contains(v reflect.Value) bool {
if pm.m != nil {
_, ok := pm.m[ptrkeyFor(v)]
return ok
}
return false
}
// Gets a pointer.
func (pm *ptrmap) get(v reflect.Value) (*ptrinfo, bool) {
if pm.m != nil {
p, ok := pm.m[ptrkeyFor(v)]
return p, ok
}
return nil, false
}
// Removes a pointer.
func (pm *ptrmap) remove(v reflect.Value) {
if pm.m != nil {
delete(pm.m, ptrkeyFor(v))
}
}
// Adds a pointer.
func (pm *ptrmap) add(p reflect.Value) bool {
if pm.contains(p) {
return false
}
pm.put(p)
return true
}
// Adds a pointer (slow path).
func (pm *ptrmap) put(v reflect.Value) {
if pm.m == nil {
pm.m = make(map[ptrkey]*ptrinfo, 31)
}
key := ptrkeyFor(v)
if _, ok := pm.m[key]; !ok {
pm.m[key] = &ptrinfo{id: -1, parent: pm}
}
}
type pointerVisitor struct {
pointers ptrmap
reused ptrmap
}
// Recursively consider v and each of its children, updating the map according to the
// semantics of MapReusedPointers
func (pv *pointerVisitor) consider(v reflect.Value) {
if v.Kind() == reflect.Invalid {
return
}
if isPointerValue(v) { // pointer is 0 for unexported fields
if pv.tryAddPointer(v) {
// No use descending inside this value, since it have been seen before and all its descendants
// have been considered
return
}
}
// Now descend into any children of this value
switch v.Kind() {
case reflect.Slice, reflect.Array:
for i := 0; i < v.Len(); i++ {
pv.consider(v.Index(i))
}
case reflect.Interface:
pv.consider(v.Elem())
case reflect.Ptr:
pv.consider(v.Elem())
case reflect.Map:
keys := v.MapKeys()
sort.Sort(mapKeySorter{
keys: keys,
options: &Config,
})
for _, key := range keys {
pv.consider(key)
pv.consider(v.MapIndex(key))
}
case reflect.Struct:
numFields := v.NumField()
for i := 0; i < numFields; i++ {
pv.consider(v.Field(i))
}
}
}
// addPointer to the pointerMap, update reusedPointers. Returns true if pointer was reused
func (pv *pointerVisitor) tryAddPointer(v reflect.Value) bool {
// Is this allready known to be reused?
if pv.reused.contains(v) {
return true
}
// Have we seen it once before?
if pv.pointers.contains(v) {
// Add it to the register of pointers we have seen more than once
pv.reused.add(v)
return true
}
// This pointer was new to us
pv.pointers.add(v)
return false
}
|
