← Back to branch summary

~nskaggs/+junk/xenial-test

« back to all changes in this revision

Viewing changes to src/github.com/julienschmidt/httprouter/tree.go

  • Committer: Nicholas Skaggs
  • Date: 2016-10-24 20:56:05 UTC
  • Revision ID: nicholas.skaggs@canonical.com-20161024205605-z8lta0uvuhtxwzwl
Initi with beta15

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/github.com/julienschmidt/httprouter/tree.go
 
1
// Copyright 2013 Julien Schmidt. All rights reserved.
 
2
// Use of this source code is governed by a BSD-style license that can be found
 
3
// in the LICENSE file.
 
4
 
 
5
package httprouter
 
6
 
 
7
import (
 
8
        "strings"
 
9
        "unicode"
 
10
)
 
11
 
 
12
func min(a, b int) int {
 
13
        if a <= b {
 
14
                return a
 
15
        }
 
16
        return b
 
17
}
 
18
 
 
19
func countParams(path string) uint8 {
 
20
        var n uint
 
21
        for i := 0; i < len(path); i++ {
 
22
                if path[i] != ':' && path[i] != '*' {
 
23
                        continue
 
24
                }
 
25
                n++
 
26
        }
 
27
        if n >= 255 {
 
28
                return 255
 
29
        }
 
30
        return uint8(n)
 
31
}
 
32
 
 
33
type nodeType uint8
 
34
 
 
35
const (
 
36
        static nodeType = iota // default
 
37
        root
 
38
        param
 
39
        catchAll
 
40
)
 
41
 
 
42
type node struct {
 
43
        path      string
 
44
        wildChild bool
 
45
        nType     nodeType
 
46
        maxParams uint8
 
47
        indices   string
 
48
        children  []*node
 
49
        handle    Handle
 
50
        priority  uint32
 
51
}
 
52
 
 
53
// increments priority of the given child and reorders if necessary
 
54
func (n *node) incrementChildPrio(pos int) int {
 
55
        n.children[pos].priority++
 
56
        prio := n.children[pos].priority
 
57
 
 
58
        // adjust position (move to front)
 
59
        newPos := pos
 
60
        for newPos > 0 && n.children[newPos-1].priority < prio {
 
61
                // swap node positions
 
62
                tmpN := n.children[newPos-1]
 
63
                n.children[newPos-1] = n.children[newPos]
 
64
                n.children[newPos] = tmpN
 
65
 
 
66
                newPos--
 
67
        }
 
68
 
 
69
        // build new index char string
 
70
        if newPos != pos {
 
71
                n.indices = n.indices[:newPos] + // unchanged prefix, might be empty
 
72
                        n.indices[pos:pos+1] + // the index char we move
 
73
                        n.indices[newPos:pos] + n.indices[pos+1:] // rest without char at 'pos'
 
74
        }
 
75
 
 
76
        return newPos
 
77
}
 
78
 
 
79
// addRoute adds a node with the given handle to the path.
 
80
// Not concurrency-safe!
 
81
func (n *node) addRoute(path string, handle Handle) {
 
82
        fullPath := path
 
83
        n.priority++
 
84
        numParams := countParams(path)
 
85
 
 
86
        // non-empty tree
 
87
        if len(n.path) > 0 || len(n.children) > 0 {
 
88
        walk:
 
89
                for {
 
90
                        // Update maxParams of the current node
 
91
                        if numParams > n.maxParams {
 
92
                                n.maxParams = numParams
 
93
                        }
 
94
 
 
95
                        // Find the longest common prefix.
 
96
                        // This also implies that the common prefix contains no ':' or '*'
 
97
                        // since the existing key can't contain those chars.
 
98
                        i := 0
 
99
                        max := min(len(path), len(n.path))
 
100
                        for i < max && path[i] == n.path[i] {
 
101
                                i++
 
102
                        }
 
103
 
 
104
                        // Split edge
 
105
                        if i < len(n.path) {
 
106
                                child := node{
 
107
                                        path:      n.path[i:],
 
108
                                        wildChild: n.wildChild,
 
109
                                        indices:   n.indices,
 
110
                                        children:  n.children,
 
111
                                        handle:    n.handle,
 
112
                                        priority:  n.priority - 1,
 
113
                                }
 
114
 
 
115
                                // Update maxParams (max of all children)
 
116
                                for i := range child.children {
 
117
                                        if child.children[i].maxParams > child.maxParams {
 
118
                                                child.maxParams = child.children[i].maxParams
 
119
                                        }
 
120
                                }
 
121
 
 
122
                                n.children = []*node{&child}
 
123
                                // []byte for proper unicode char conversion, see #65
 
124
                                n.indices = string([]byte{n.path[i]})
 
125
                                n.path = path[:i]
 
126
                                n.handle = nil
 
127
                                n.wildChild = false
 
128
                        }
 
129
 
 
130
                        // Make new node a child of this node
 
131
                        if i < len(path) {
 
132
                                path = path[i:]
 
133
 
 
134
                                if n.wildChild {
 
135
                                        n = n.children[0]
 
136
                                        n.priority++
 
137
 
 
138
                                        // Update maxParams of the child node
 
139
                                        if numParams > n.maxParams {
 
140
                                                n.maxParams = numParams
 
141
                                        }
 
142
                                        numParams--
 
143
 
 
144
                                        // Check if the wildcard matches
 
145
                                        if len(path) >= len(n.path) && n.path == path[:len(n.path)] {
 
146
                                                // check for longer wildcard, e.g. :name and :names
 
147
                                                if len(n.path) >= len(path) || path[len(n.path)] == '/' {
 
148
                                                        continue walk
 
149
                                                }
 
150
                                        }
 
151
 
 
152
                                        panic("path segment '" + path +
 
153
                                                "' conflicts with existing wildcard '" + n.path +
 
154
                                                "' in path '" + fullPath + "'")
 
155
                                }
 
156
 
 
157
                                c := path[0]
 
158
 
 
159
                                // slash after param
 
160
                                if n.nType == param && c == '/' && len(n.children) == 1 {
 
161
                                        n = n.children[0]
 
162
                                        n.priority++
 
163
                                        continue walk
 
164
                                }
 
165
 
 
166
                                // Check if a child with the next path byte exists
 
167
                                for i := 0; i < len(n.indices); i++ {
 
168
                                        if c == n.indices[i] {
 
169
                                                i = n.incrementChildPrio(i)
 
170
                                                n = n.children[i]
 
171
                                                continue walk
 
172
                                        }
 
173
                                }
 
174
 
 
175
                                // Otherwise insert it
 
176
                                if c != ':' && c != '*' {
 
177
                                        // []byte for proper unicode char conversion, see #65
 
178
                                        n.indices += string([]byte{c})
 
179
                                        child := &node{
 
180
                                                maxParams: numParams,
 
181
                                        }
 
182
                                        n.children = append(n.children, child)
 
183
                                        n.incrementChildPrio(len(n.indices) - 1)
 
184
                                        n = child
 
185
                                }
 
186
                                n.insertChild(numParams, path, fullPath, handle)
 
187
                                return
 
188
 
 
189
                        } else if i == len(path) { // Make node a (in-path) leaf
 
190
                                if n.handle != nil {
 
191
                                        panic("a handle is already registered for path '" + fullPath + "'")
 
192
                                }
 
193
                                n.handle = handle
 
194
                        }
 
195
                        return
 
196
                }
 
197
        } else { // Empty tree
 
198
                n.insertChild(numParams, path, fullPath, handle)
 
199
                n.nType = root
 
200
        }
 
201
}
 
202
 
 
203
func (n *node) insertChild(numParams uint8, path, fullPath string, handle Handle) {
 
204
        var offset int // already handled bytes of the path
 
205
 
 
206
        // find prefix until first wildcard (beginning with ':'' or '*'')
 
207
        for i, max := 0, len(path); numParams > 0; i++ {
 
208
                c := path[i]
 
209
                if c != ':' && c != '*' {
 
210
                        continue
 
211
                }
 
212
 
 
213
                // find wildcard end (either '/' or path end)
 
214
                end := i + 1
 
215
                for end < max && path[end] != '/' {
 
216
                        switch path[end] {
 
217
                        // the wildcard name must not contain ':' and '*'
 
218
                        case ':', '*':
 
219
                                panic("only one wildcard per path segment is allowed, has: '" +
 
220
                                        path[i:] + "' in path '" + fullPath + "'")
 
221
                        default:
 
222
                                end++
 
223
                        }
 
224
                }
 
225
 
 
226
                // check if this Node existing children which would be
 
227
                // unreachable if we insert the wildcard here
 
228
                if len(n.children) > 0 {
 
229
                        panic("wildcard route '" + path[i:end] +
 
230
                                "' conflicts with existing children in path '" + fullPath + "'")
 
231
                }
 
232
 
 
233
                // check if the wildcard has a name
 
234
                if end-i < 2 {
 
235
                        panic("wildcards must be named with a non-empty name in path '" + fullPath + "'")
 
236
                }
 
237
 
 
238
                if c == ':' { // param
 
239
                        // split path at the beginning of the wildcard
 
240
                        if i > 0 {
 
241
                                n.path = path[offset:i]
 
242
                                offset = i
 
243
                        }
 
244
 
 
245
                        child := &node{
 
246
                                nType:     param,
 
247
                                maxParams: numParams,
 
248
                        }
 
249
                        n.children = []*node{child}
 
250
                        n.wildChild = true
 
251
                        n = child
 
252
                        n.priority++
 
253
                        numParams--
 
254
 
 
255
                        // if the path doesn't end with the wildcard, then there
 
256
                        // will be another non-wildcard subpath starting with '/'
 
257
                        if end < max {
 
258
                                n.path = path[offset:end]
 
259
                                offset = end
 
260
 
 
261
                                child := &node{
 
262
                                        maxParams: numParams,
 
263
                                        priority:  1,
 
264
                                }
 
265
                                n.children = []*node{child}
 
266
                                n = child
 
267
                        }
 
268
 
 
269
                } else { // catchAll
 
270
                        if end != max || numParams > 1 {
 
271
                                panic("catch-all routes are only allowed at the end of the path in path '" + fullPath + "'")
 
272
                        }
 
273
 
 
274
                        if len(n.path) > 0 && n.path[len(n.path)-1] == '/' {
 
275
                                panic("catch-all conflicts with existing handle for the path segment root in path '" + fullPath + "'")
 
276
                        }
 
277
 
 
278
                        // currently fixed width 1 for '/'
 
279
                        i--
 
280
                        if path[i] != '/' {
 
281
                                panic("no / before catch-all in path '" + fullPath + "'")
 
282
                        }
 
283
 
 
284
                        n.path = path[offset:i]
 
285
 
 
286
                        // first node: catchAll node with empty path
 
287
                        child := &node{
 
288
                                wildChild: true,
 
289
                                nType:     catchAll,
 
290
                                maxParams: 1,
 
291
                        }
 
292
                        n.children = []*node{child}
 
293
                        n.indices = string(path[i])
 
294
                        n = child
 
295
                        n.priority++
 
296
 
 
297
                        // second node: node holding the variable
 
298
                        child = &node{
 
299
                                path:      path[i:],
 
300
                                nType:     catchAll,
 
301
                                maxParams: 1,
 
302
                                handle:    handle,
 
303
                                priority:  1,
 
304
                        }
 
305
                        n.children = []*node{child}
 
306
 
 
307
                        return
 
308
                }
 
309
        }
 
310
 
 
311
        // insert remaining path part and handle to the leaf
 
312
        n.path = path[offset:]
 
313
        n.handle = handle
 
314
}
 
315
 
 
316
// Returns the handle registered with the given path (key). The values of
 
317
// wildcards are saved to a map.
 
318
// If no handle can be found, a TSR (trailing slash redirect) recommendation is
 
319
// made if a handle exists with an extra (without the) trailing slash for the
 
320
// given path.
 
321
func (n *node) getValue(path string) (handle Handle, p Params, tsr bool) {
 
322
walk: // Outer loop for walking the tree
 
323
        for {
 
324
                if len(path) > len(n.path) {
 
325
                        if path[:len(n.path)] == n.path {
 
326
                                path = path[len(n.path):]
 
327
                                // If this node does not have a wildcard (param or catchAll)
 
328
                                // child,  we can just look up the next child node and continue
 
329
                                // to walk down the tree
 
330
                                if !n.wildChild {
 
331
                                        c := path[0]
 
332
                                        for i := 0; i < len(n.indices); i++ {
 
333
                                                if c == n.indices[i] {
 
334
                                                        n = n.children[i]
 
335
                                                        continue walk
 
336
                                                }
 
337
                                        }
 
338
 
 
339
                                        // Nothing found.
 
340
                                        // We can recommend to redirect to the same URL without a
 
341
                                        // trailing slash if a leaf exists for that path.
 
342
                                        tsr = (path == "/" && n.handle != nil)
 
343
                                        return
 
344
 
 
345
                                }
 
346
 
 
347
                                // handle wildcard child
 
348
                                n = n.children[0]
 
349
                                switch n.nType {
 
350
                                case param:
 
351
                                        // find param end (either '/' or path end)
 
352
                                        end := 0
 
353
                                        for end < len(path) && path[end] != '/' {
 
354
                                                end++
 
355
                                        }
 
356
 
 
357
                                        // save param value
 
358
                                        if p == nil {
 
359
                                                // lazy allocation
 
360
                                                p = make(Params, 0, n.maxParams)
 
361
                                        }
 
362
                                        i := len(p)
 
363
                                        p = p[:i+1] // expand slice within preallocated capacity
 
364
                                        p[i].Key = n.path[1:]
 
365
                                        p[i].Value = path[:end]
 
366
 
 
367
                                        // we need to go deeper!
 
368
                                        if end < len(path) {
 
369
                                                if len(n.children) > 0 {
 
370
                                                        path = path[end:]
 
371
                                                        n = n.children[0]
 
372
                                                        continue walk
 
373
                                                }
 
374
 
 
375
                                                // ... but we can't
 
376
                                                tsr = (len(path) == end+1)
 
377
                                                return
 
378
                                        }
 
379
 
 
380
                                        if handle = n.handle; handle != nil {
 
381
                                                return
 
382
                                        } else if len(n.children) == 1 {
 
383
                                                // No handle found. Check if a handle for this path + a
 
384
                                                // trailing slash exists for TSR recommendation
 
385
                                                n = n.children[0]
 
386
                                                tsr = (n.path == "/" && n.handle != nil)
 
387
                                        }
 
388
 
 
389
                                        return
 
390
 
 
391
                                case catchAll:
 
392
                                        // save param value
 
393
                                        if p == nil {
 
394
                                                // lazy allocation
 
395
                                                p = make(Params, 0, n.maxParams)
 
396
                                        }
 
397
                                        i := len(p)
 
398
                                        p = p[:i+1] // expand slice within preallocated capacity
 
399
                                        p[i].Key = n.path[2:]
 
400
                                        p[i].Value = path
 
401
 
 
402
                                        handle = n.handle
 
403
                                        return
 
404
 
 
405
                                default:
 
406
                                        panic("invalid node type")
 
407
                                }
 
408
                        }
 
409
                } else if path == n.path {
 
410
                        // We should have reached the node containing the handle.
 
411
                        // Check if this node has a handle registered.
 
412
                        if handle = n.handle; handle != nil {
 
413
                                return
 
414
                        }
 
415
 
 
416
                        if path == "/" && n.wildChild && n.nType != root {
 
417
                                tsr = true
 
418
                                return
 
419
                        }
 
420
 
 
421
                        // No handle found. Check if a handle for this path + a
 
422
                        // trailing slash exists for trailing slash recommendation
 
423
                        for i := 0; i < len(n.indices); i++ {
 
424
                                if n.indices[i] == '/' {
 
425
                                        n = n.children[i]
 
426
                                        tsr = (len(n.path) == 1 && n.handle != nil) ||
 
427
                                                (n.nType == catchAll && n.children[0].handle != nil)
 
428
                                        return
 
429
                                }
 
430
                        }
 
431
 
 
432
                        return
 
433
                }
 
434
 
 
435
                // Nothing found. We can recommend to redirect to the same URL with an
 
436
                // extra trailing slash if a leaf exists for that path
 
437
                tsr = (path == "/") ||
 
438
                        (len(n.path) == len(path)+1 && n.path[len(path)] == '/' &&
 
439
                                path == n.path[:len(n.path)-1] && n.handle != nil)
 
440
                return
 
441
        }
 
442
}
 
443
 
 
444
// Makes a case-insensitive lookup of the given path and tries to find a handler.
 
445
// It can optionally also fix trailing slashes.
 
446
// It returns the case-corrected path and a bool indicating whether the lookup
 
447
// was successful.
 
448
func (n *node) findCaseInsensitivePath(path string, fixTrailingSlash bool) (ciPath []byte, found bool) {
 
449
        ciPath = make([]byte, 0, len(path)+1) // preallocate enough memory
 
450
 
 
451
        // Outer loop for walking the tree
 
452
        for len(path) >= len(n.path) && strings.ToLower(path[:len(n.path)]) == strings.ToLower(n.path) {
 
453
                path = path[len(n.path):]
 
454
                ciPath = append(ciPath, n.path...)
 
455
 
 
456
                if len(path) > 0 {
 
457
                        // If this node does not have a wildcard (param or catchAll) child,
 
458
                        // we can just look up the next child node and continue to walk down
 
459
                        // the tree
 
460
                        if !n.wildChild {
 
461
                                r := unicode.ToLower(rune(path[0]))
 
462
                                for i, index := range n.indices {
 
463
                                        // must use recursive approach since both index and
 
464
                                        // ToLower(index) could exist. We must check both.
 
465
                                        if r == unicode.ToLower(index) {
 
466
                                                out, found := n.children[i].findCaseInsensitivePath(path, fixTrailingSlash)
 
467
                                                if found {
 
468
                                                        return append(ciPath, out...), true
 
469
                                                }
 
470
                                        }
 
471
                                }
 
472
 
 
473
                                // Nothing found. We can recommend to redirect to the same URL
 
474
                                // without a trailing slash if a leaf exists for that path
 
475
                                found = (fixTrailingSlash && path == "/" && n.handle != nil)
 
476
                                return
 
477
                        }
 
478
 
 
479
                        n = n.children[0]
 
480
                        switch n.nType {
 
481
                        case param:
 
482
                                // find param end (either '/' or path end)
 
483
                                k := 0
 
484
                                for k < len(path) && path[k] != '/' {
 
485
                                        k++
 
486
                                }
 
487
 
 
488
                                // add param value to case insensitive path
 
489
                                ciPath = append(ciPath, path[:k]...)
 
490
 
 
491
                                // we need to go deeper!
 
492
                                if k < len(path) {
 
493
                                        if len(n.children) > 0 {
 
494
                                                path = path[k:]
 
495
                                                n = n.children[0]
 
496
                                                continue
 
497
                                        }
 
498
 
 
499
                                        // ... but we can't
 
500
                                        if fixTrailingSlash && len(path) == k+1 {
 
501
                                                return ciPath, true
 
502
                                        }
 
503
                                        return
 
504
                                }
 
505
 
 
506
                                if n.handle != nil {
 
507
                                        return ciPath, true
 
508
                                } else if fixTrailingSlash && len(n.children) == 1 {
 
509
                                        // No handle found. Check if a handle for this path + a
 
510
                                        // trailing slash exists
 
511
                                        n = n.children[0]
 
512
                                        if n.path == "/" && n.handle != nil {
 
513
                                                return append(ciPath, '/'), true
 
514
                                        }
 
515
                                }
 
516
                                return
 
517
 
 
518
                        case catchAll:
 
519
                                return append(ciPath, path...), true
 
520
 
 
521
                        default:
 
522
                                panic("invalid node type")
 
523
                        }
 
524
                } else {
 
525
                        // We should have reached the node containing the handle.
 
526
                        // Check if this node has a handle registered.
 
527
                        if n.handle != nil {
 
528
                                return ciPath, true
 
529
                        }
 
530
 
 
531
                        // No handle found.
 
532
                        // Try to fix the path by adding a trailing slash
 
533
                        if fixTrailingSlash {
 
534
                                for i := 0; i < len(n.indices); i++ {
 
535
                                        if n.indices[i] == '/' {
 
536
                                                n = n.children[i]
 
537
                                                if (len(n.path) == 1 && n.handle != nil) ||
 
538
                                                        (n.nType == catchAll && n.children[0].handle != nil) {
 
539
                                                        return append(ciPath, '/'), true
 
540
                                                }
 
541
                                                return
 
542
                                        }
 
543
                                }
 
544
                        }
 
545
                        return
 
546
                }
 
547
        }
 
548
 
 
549
        // Nothing found.
 
550
        // Try to fix the path by adding / removing a trailing slash
 
551
        if fixTrailingSlash {
 
552
                if path == "/" {
 
553
                        return ciPath, true
 
554
                }
 
555
                if len(path)+1 == len(n.path) && n.path[len(path)] == '/' &&
 
556
                        strings.ToLower(path) == strings.ToLower(n.path[:len(path)]) &&
 
557
                        n.handle != nil {
 
558
                        return append(ciPath, n.path...), true
 
559
                }
 
560
        }
 
561
        return
 
562
}