File: tree.go

package info (click to toggle)
golang-pathtree 0.0~git20140121-3
  • links: PTS, VCS
  • area: main
  • in suites: bullseye, buster, sid
  • size: 60 kB
  • sloc: makefile: 2
file content (228 lines) | stat: -rw-r--r-- 6,555 bytes parent folder | download | duplicates (2)
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
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
// pathtree implements a tree for fast path lookup.
//
// Restrictions
//
//   - Paths must be a '/'-separated list of strings, like a URL or Unix filesystem.
//   - All paths must begin with a '/'.
//   - Path elements may not contain a '/'.
//   - Path elements beginning with a ':' or '*' will be interpreted as wildcards.
//   - Trailing slashes are inconsequential.
//
// Wildcards
//
// Wildcards are named path elements that may match any strings in that
// location.  Two different kinds of wildcards are permitted:
//   - :var - names beginning with ':' will match any single path element.
//   - *var - names beginning with '*' will match one or more path elements.
//            (however, no path elements may come after a star wildcard)
//
// Extensions
//
// Single element wildcards in the last path element can optionally end with an
// extension. This allows for routes like '/users/:id.json', which will not
// conflict with '/users/:id'.
//
// Algorithm
//
// Paths are mapped to the tree in the following way:
//   - Each '/' is a Node in the tree. The root node is the leading '/'.
//   - Each Node has edges to other nodes. The edges are named according to the
//     possible path elements at that depth in the path.
//   - Any Node may have an associated Leaf.  Leafs are terminals containing the
//     data associated with the path as traversed from the root to that Node.
//
// Edges are implemented as a map from the path element name to the next node in
// the path.
package pathtree

import (
	"errors"
	"strings"
)

type Node struct {
	edges      map[string]*Node // the various path elements leading out of this node.
	wildcard   *Node            // if set, this node had a wildcard as its path element.
	leaf       *Leaf            // if set, this is a terminal node for this leaf.
	extensions map[string]*Leaf // if set, this is a terminal node with a leaf that ends in a specific extension.
	star       *Leaf            // if set, this path ends in a star.
	leafs      int              // counter for # leafs in the tree
}

type Leaf struct {
	Value     interface{} // the value associated with this node
	Wildcards []string    // the wildcard names, in order they appear in the path
	order     int         // the order this leaf was added
}

// New returns a new path tree.
func New() *Node {
	return &Node{edges: make(map[string]*Node)}
}

// Add a path and its associated value to the tree.
//   - key must begin with "/"
//   - key must not duplicate any existing key.
// Returns an error if those conditions do not hold.
func (n *Node) Add(key string, val interface{}) error {
	if key == "" || key[0] != '/' {
		return errors.New("Path must begin with /")
	}
	n.leafs++
	return n.add(n.leafs, splitPath(key), nil, val)
}

// Adds a leaf to a terminal node.
// If the last wildcard contains an extension, add it to the 'extensions' map.
func (n *Node) addLeaf(leaf *Leaf) error {
	extension := stripExtensionFromLastSegment(leaf.Wildcards)
	if extension != "" {
		if n.extensions == nil {
			n.extensions = make(map[string]*Leaf)
		}
		if n.extensions[extension] != nil {
			return errors.New("duplicate path")
		}
		n.extensions[extension] = leaf
		return nil
	}

	if n.leaf != nil {
		return errors.New("duplicate path")
	}
	n.leaf = leaf
	return nil
}

func (n *Node) add(order int, elements, wildcards []string, val interface{}) error {
	if len(elements) == 0 {
		leaf := &Leaf{
			order:     order,
			Value:     val,
			Wildcards: wildcards,
		}
		return n.addLeaf(leaf)
	}

	var el string
	el, elements = elements[0], elements[1:]
	if el == "" {
		return errors.New("empty path elements are not allowed")
	}

	// Handle wildcards.
	switch el[0] {
	case ':':
		if n.wildcard == nil {
			n.wildcard = New()
		}
		return n.wildcard.add(order, elements, append(wildcards, el[1:]), val)
	case '*':
		if n.star != nil {
			return errors.New("duplicate path")
		}
		n.star = &Leaf{
			order:     order,
			Value:     val,
			Wildcards: append(wildcards, el[1:]),
		}
		return nil
	}

	// It's a normal path element.
	e, ok := n.edges[el]
	if !ok {
		e = New()
		n.edges[el] = e
	}

	return e.add(order, elements, wildcards, val)
}

// Find a given path. Any wildcards traversed along the way are expanded and
// returned, along with the value.
func (n *Node) Find(key string) (leaf *Leaf, expansions []string) {
	if len(key) == 0 || key[0] != '/' {
		return nil, nil
	}

	return n.find(splitPath(key), nil)
}

func (n *Node) find(elements, exp []string) (leaf *Leaf, expansions []string) {
	if len(elements) == 0 {
		// If this node has explicit extensions, check if the path matches one.
		if len(exp) > 0 && n.extensions != nil {
			lastExp := exp[len(exp)-1]
			prefix, extension := extensionForPath(lastExp)
			if leaf := n.extensions[extension]; leaf != nil {
				exp[len(exp)-1] = prefix
				return leaf, exp
			}
		}
		return n.leaf, exp
	}

	// If this node has a star, calculate the star expansions in advance.
	var starExpansion string
	if n.star != nil {
		starExpansion = strings.Join(elements, "/")
	}

	// Peel off the next element and look up the associated edge.
	var el string
	el, elements = elements[0], elements[1:]
	if nextNode, ok := n.edges[el]; ok {
		leaf, expansions = nextNode.find(elements, exp)
	}

	// Handle colon
	if n.wildcard != nil {
		wildcardLeaf, wildcardExpansions := n.wildcard.find(elements, append(exp, el))
		if wildcardLeaf != nil && (leaf == nil || leaf.order > wildcardLeaf.order) {
			leaf = wildcardLeaf
			expansions = wildcardExpansions
		}
	}

	// Handle star
	if n.star != nil && (leaf == nil || leaf.order > n.star.order) {
		leaf = n.star
		expansions = append(exp, starExpansion)
	}

	return
}

func extensionForPath(path string) (string, string) {
	dotPosition := strings.LastIndex(path, ".")
	if dotPosition != -1 {
		return path[:dotPosition], path[dotPosition:]
	}
	return "", ""
}

func splitPath(key string) []string {
	elements := strings.Split(key, "/")
	if elements[0] == "" {
		elements = elements[1:]
	}
	if elements[len(elements)-1] == "" {
		elements = elements[:len(elements)-1]
	}
	return elements
}

// stripExtensionFromLastSegment determines if a string slice representing a path
// ends with a file extension, removes the extension from the input, and returns it.
func stripExtensionFromLastSegment(segments []string) string {
	if len(segments) == 0 {
		return ""
	}
	lastSegment := segments[len(segments)-1]
	prefix, extension := extensionForPath(lastSegment)
	if extension != "" {
		segments[len(segments)-1] = prefix
	}
	return extension
}