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
|
package btf
import (
"fmt"
)
// Functions to traverse a cyclic graph of types. The below was very useful:
// https://eli.thegreenplace.net/2015/directed-graph-traversal-orderings-and-applications-to-data-flow-analysis/#post-order-and-reverse-post-order
// Visit all types reachable from root in postorder.
//
// Traversal stops if yield returns false.
//
// Returns false if traversal was aborted.
func visitInPostorder(root Type, visited map[Type]struct{}, yield func(typ Type) bool) bool {
if _, ok := visited[root]; ok {
return true
}
if visited == nil {
visited = make(map[Type]struct{})
}
visited[root] = struct{}{}
cont := children(root, func(child *Type) bool {
return visitInPostorder(*child, visited, yield)
})
if !cont {
return false
}
return yield(root)
}
// children calls yield on each child of typ.
//
// Traversal stops if yield returns false.
//
// Returns false if traversal was aborted.
func children(typ Type, yield func(child *Type) bool) bool {
// Explicitly type switch on the most common types to allow the inliner to
// do its work. This avoids allocating intermediate slices from walk() on
// the heap.
var tags []string
switch v := typ.(type) {
case *Void, *Int, *Enum, *Fwd, *Float, *declTag:
// No children to traverse.
// declTags is declared as a leaf type since it's parsed into .Tags fields of other types
// during unmarshaling.
case *Pointer:
if !yield(&v.Target) {
return false
}
case *Array:
if !yield(&v.Index) {
return false
}
if !yield(&v.Type) {
return false
}
case *Struct:
for i := range v.Members {
if !yield(&v.Members[i].Type) {
return false
}
for _, t := range v.Members[i].Tags {
var tag Type = &declTag{v, t, i}
if !yield(&tag) {
return false
}
}
}
tags = v.Tags
case *Union:
for i := range v.Members {
if !yield(&v.Members[i].Type) {
return false
}
for _, t := range v.Members[i].Tags {
var tag Type = &declTag{v, t, i}
if !yield(&tag) {
return false
}
}
}
tags = v.Tags
case *Typedef:
if !yield(&v.Type) {
return false
}
tags = v.Tags
case *Volatile:
if !yield(&v.Type) {
return false
}
case *Const:
if !yield(&v.Type) {
return false
}
case *Restrict:
if !yield(&v.Type) {
return false
}
case *Func:
if !yield(&v.Type) {
return false
}
if fp, ok := v.Type.(*FuncProto); ok {
for i := range fp.Params {
if len(v.ParamTags) <= i {
continue
}
for _, t := range v.ParamTags[i] {
var tag Type = &declTag{v, t, i}
if !yield(&tag) {
return false
}
}
}
}
tags = v.Tags
case *FuncProto:
if !yield(&v.Return) {
return false
}
for i := range v.Params {
if !yield(&v.Params[i].Type) {
return false
}
}
case *Var:
if !yield(&v.Type) {
return false
}
tags = v.Tags
case *Datasec:
for i := range v.Vars {
if !yield(&v.Vars[i].Type) {
return false
}
}
case *TypeTag:
if !yield(&v.Type) {
return false
}
case *cycle:
// cycle has children, but we ignore them deliberately.
default:
panic(fmt.Sprintf("don't know how to walk Type %T", v))
}
for _, t := range tags {
var tag Type = &declTag{typ, t, -1}
if !yield(&tag) {
return false
}
}
return true
}
|
