-
Notifications
You must be signed in to change notification settings - Fork 3
/
cyclic.go
96 lines (77 loc) · 2.21 KB
/
cyclic.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
package velty
import (
"github.com/viant/velty/est/op"
"reflect"
)
type (
CycleDetector struct {
rType reflect.Type
allTypes map[reflect.Type]*MultiCycleDetector
parent *CycleDetector
parentSelector *op.Selector
name string
}
MultiCycleDetector struct {
index map[reflect.Type]int
children []*CycleDetector
}
)
func NewCycleDetector(rType reflect.Type) *CycleDetector {
return newCycleDetector(nil, nil, rType, nil)
}
func newCycleDetector(parent *CycleDetector, state map[reflect.Type]*MultiCycleDetector, rType reflect.Type, parentSelector *op.Selector) *CycleDetector {
if state == nil {
state = map[reflect.Type]*MultiCycleDetector{}
}
rType, _ = elemIfNeeded(rType)
return &CycleDetector{
allTypes: state,
parent: parent,
rType: rType,
parentSelector: parentSelector,
name: rType.String(),
}
}
func (c *CycleDetector) Child(rType reflect.Type, parentSelector *op.Selector) (next *CycleDetector, hasCycle bool) {
cycle := c.getChildrenCycleHolder(rType)
return cycle.Get(c, rType, parentSelector)
}
func (d *MultiCycleDetector) Get(c *CycleDetector, rType reflect.Type, parentSelector *op.Selector) (*CycleDetector, bool) {
detector, parent := d.getOrCreate(c, rType, parentSelector)
return detector, parent != nil
}
func (d *MultiCycleDetector) getOrCreate(c *CycleDetector, rType reflect.Type, parentSelector *op.Selector) (current *CycleDetector, parent *CycleDetector) {
i, ok := d.index[rType]
if ok {
next := d.children[i]
if next.Has(next) {
return c, next
}
return next, nil
}
detector := newCycleDetector(c, c.allTypes, rType, parentSelector)
d.index[rType] = len(d.children)
d.children = append(d.children, detector)
return detector, nil
}
func (c *CycleDetector) getChildrenCycleHolder(rType reflect.Type) *MultiCycleDetector {
cycle, ok := c.allTypes[rType]
if ok {
return cycle
}
cycle = &MultiCycleDetector{
index: map[reflect.Type]int{},
}
c.allTypes[rType] = cycle
return cycle
}
func (c *CycleDetector) Has(parent *CycleDetector) bool {
curr := c
for curr != nil {
if curr.rType == parent.rType && curr.rType != nil {
return true
}
curr = curr.parent
}
return false
}