forked from cilium/ebpf
-
Notifications
You must be signed in to change notification settings - Fork 0
/
traversal.go
141 lines (123 loc) · 3.31 KB
/
traversal.go
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
package btf
import (
"fmt"
"github.com/mscastanho/ebpf/internal"
)
// 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
type postorderIterator struct {
// Iteration skips types for which this function returns true.
skip func(Type) bool
// The root type. May be nil if skip(root) is true.
root Type
// Contains types which need to be either walked or yielded.
types typeDeque
// Contains a boolean whether the type has been walked or not.
walked internal.Deque[bool]
// The set of types which has been pushed onto types.
pushed map[Type]struct{}
// The current type. Only valid after a call to Next().
Type Type
}
// postorderTraversal iterates all types reachable from root by visiting the
// leaves of the graph first.
//
// Types for which skip returns true are ignored. skip may be nil.
func postorderTraversal(root Type, skip func(Type) (skip bool)) postorderIterator {
// Avoid allocations for the common case of a skipped root.
if skip != nil && skip(root) {
return postorderIterator{}
}
po := postorderIterator{root: root, skip: skip}
walkType(root, po.push)
return po
}
func (po *postorderIterator) push(t *Type) {
if _, ok := po.pushed[*t]; ok || *t == po.root {
return
}
if po.skip != nil && po.skip(*t) {
return
}
if po.pushed == nil {
// Lazily allocate pushed to avoid an allocation for Types without children.
po.pushed = make(map[Type]struct{})
}
po.pushed[*t] = struct{}{}
po.types.Push(t)
po.walked.Push(false)
}
// Next returns true if there is another Type to traverse.
func (po *postorderIterator) Next() bool {
for !po.types.Empty() {
t := po.types.Pop()
if !po.walked.Pop() {
// Push the type again, so that we re-evaluate it in done state
// after all children have been handled.
po.types.Push(t)
po.walked.Push(true)
// Add all direct children to todo.
walkType(*t, po.push)
} else {
// We've walked this type previously, so we now know that all
// children have been handled.
po.Type = *t
return true
}
}
// Only return root once.
po.Type, po.root = po.root, nil
return po.Type != nil
}
// walkType calls fn on each child of typ.
func walkType(typ Type, fn func(*Type)) {
// 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.
switch v := typ.(type) {
case *Void, *Int, *Enum, *Fwd, *Float:
// No children to traverse.
case *Pointer:
fn(&v.Target)
case *Array:
fn(&v.Index)
fn(&v.Type)
case *Struct:
for i := range v.Members {
fn(&v.Members[i].Type)
}
case *Union:
for i := range v.Members {
fn(&v.Members[i].Type)
}
case *Typedef:
fn(&v.Type)
case *Volatile:
fn(&v.Type)
case *Const:
fn(&v.Type)
case *Restrict:
fn(&v.Type)
case *Func:
fn(&v.Type)
case *FuncProto:
fn(&v.Return)
for i := range v.Params {
fn(&v.Params[i].Type)
}
case *Var:
fn(&v.Type)
case *Datasec:
for i := range v.Vars {
fn(&v.Vars[i].Type)
}
case *declTag:
fn(&v.Type)
case *typeTag:
fn(&v.Type)
case *cycle:
// cycle has children, but we ignore them deliberately.
default:
panic(fmt.Sprintf("don't know how to walk Type %T", v))
}
}