-
Notifications
You must be signed in to change notification settings - Fork 0
/
node.go
161 lines (146 loc) · 4.22 KB
/
node.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
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
package oakmux
import (
"fmt"
"log"
"strings"
)
// Node is the nesting routing tree component.
type Node struct {
Leaf *Route
TrailingSlashLeaf *Route
TerminalLeaf *Route
Branches Branches
DynamicBranch *Node
}
type WalkFunc func(*Node) (ok bool, err error)
func (n *Node) MatchPath(path string) (route *Route, matches []string) {
switch path {
case "":
return n.Leaf, nil
case "/":
return n.TrailingSlashLeaf, nil
}
segment, remainder, err := munchPath(path) // speed this up
if err != nil { // TODO: drop this check
log.Println("double slash error?", err)
return nil, nil // double slash error possible only
}
// log.Println(segment, remainder)
// spew.Dump(n)
if n.Branches != nil {
if branch := n.Branches.Get(segment); branch != nil {
route, matches = branch.MatchPath(remainder)
if route != nil {
return route, matches
}
}
}
if n.DynamicBranch != nil {
// TODO: pass in array with pre-initialized len instead?
route, matches = n.DynamicBranch.MatchPath(remainder)
if route != nil {
return route, append([]string{segment}, matches...)
}
}
if n.TerminalLeaf != nil {
// if n.TerminalLeaf.segments[len(n.TerminalLeaf.segments)-1].Name() == "" {
// return n.TerminalLeaf, nil // deal with the {...}
// }
return n.TerminalLeaf, []string{path[1:]}
}
return nil, nil
}
func (n *Node) Grow(route *Route, remaining []Segment) (err error) {
if len(remaining) == 0 { // leaf
if n.Leaf != nil {
return fmt.Errorf("routes %q and %q overlap: %s resolves to the same static tree node as %s", n.Leaf.Name(), route.Name(), n.Leaf.String(), route.String())
}
n.Leaf = route
return nil
}
current := remaining[0]
switch current.Type() {
case SegmentTypeTrailingSlash: // leaf
if n.TrailingSlashLeaf != nil {
return fmt.Errorf("routes %q and %q overlap: %s resolves to the same trailing slash tree node as %s", n.TrailingSlashLeaf.Name(), route.Name(), n.TrailingSlashLeaf.String(), route.String())
}
n.TrailingSlashLeaf = route
case SegmentTypeTerminal: // leaf
if n.TerminalLeaf != nil {
return fmt.Errorf("routes %q and %q overlap: %s resolves to the same terminal tree node as %s", n.TerminalLeaf.Name(), route.Name(), n.TerminalLeaf.String(), route.String())
}
n.TerminalLeaf = route
case SegmentTypeStatic: // branch
if n.Branches == nil {
n.Branches = make(branchList, 0, 1)
}
var node *Node
// spew.Dump(current.Name())
node, n.Branches = n.Branches.Grow(current.Name())
// name := current.Name()
// node := n.Branches.Get(name)
// if node == nil {
// node = &Node{}
// n.Branches = n.Branches.Append(name, node)
// }
return node.Grow(route, remaining[1:])
case SegmentTypeDynamic: // branch
if n.DynamicBranch == nil {
n.DynamicBranch = &Node{}
}
return n.DynamicBranch.Grow(route, remaining[1:])
default:
return fmt.Errorf("cannot grow tree using a segment %q of unknown type %q", current.Name(), current.Type())
}
return nil
}
func (n *Node) Walk(walkFn WalkFunc) (err error) {
ok, err := walkFn(n)
if err != nil || !ok {
return
}
if n.Branches != nil {
for _, key := range n.Branches.Keys() {
if err = n.Branches.Get(key).Walk(walkFn); err != nil {
return
}
}
}
if n.DynamicBranch != nil {
return n.DynamicBranch.Walk(walkFn)
}
return
}
func (n *Node) String() string {
b := &strings.Builder{}
// b.WriteString("╟ ")
if n.Leaf != nil {
fmt.Fprintf(b, "[route:%s] ", n.Leaf.Name())
}
if n.TrailingSlashLeaf != nil {
fmt.Fprintf(b, "[route/%s] ", n.TrailingSlashLeaf.Name())
}
if n.TerminalLeaf != nil {
fmt.Fprintf(b, "[...%s]", n.TerminalLeaf.Name())
}
if n.Branches != nil {
for _, branch := range n.Branches.Keys() {
sub := n.Branches.Get(branch)
b.WriteString("\n╚ ")
fmt.Fprintf(b, "<%s>", branch)
b.WriteString(strings.Replace(sub.String(), "\n", "\n ", -1))
}
}
if n.DynamicBranch != nil {
b.WriteString("\n╚ <...>")
b.WriteString(strings.Replace(n.DynamicBranch.String(), "\n", "\n ", -1))
}
// fmt.Fprintf(b, "\n╟\n")
// fmt.Fprintf(b, "╚ ╟\n")
// Leaf *Route
// TrailingSlashLeaf *Route
// TerminalLeaf *Route
// Branches Branches
// DynamicBranch *Node
return b.String()
}