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
// at https://github.com/julienschmidt/httprouter/blob/master/LICENSE
4

5
package gin
6

7
import (
8
	"bytes"
9
	"net/url"
10
	"strings"
11
	"unicode"
12
	"unicode/utf8"
13

14
	"github.com/gin-gonic/gin/internal/bytesconv"
15
)
16

17
var (
18
	strColon = []byte(":")
19
	strStar  = []byte("*")
20
)
21

22
// Param is a single URL parameter, consisting of a key and a value.
23
type Param struct {
24
	Key   string
25
	Value string
26
}
27

28
// Params is a Param-slice, as returned by the router.
29
// The slice is ordered, the first URL parameter is also the first slice value.
30
// It is therefore safe to read values by the index.
31
type Params []Param
32

33
// Get returns the value of the first Param which key matches the given name.
34
// If no matching Param is found, an empty string is returned.
35
func (ps Params) Get(name string) (string, bool) {
36
	for _, entry := range ps {
37 14
		if entry.Key == name {
38 14
			return entry.Value, true
39
		}
40
	}
41 14
	return "", false
42
}
43

44
// ByName returns the value of the first Param which key matches the given name.
45
// If no matching Param is found, an empty string is returned.
46
func (ps Params) ByName(name string) (va string) {
47 14
	va, _ = ps.Get(name)
48 14
	return
49
}
50

51
type methodTree struct {
52
	method string
53
	root   *node
54
}
55

56
type methodTrees []methodTree
57

58
func (trees methodTrees) get(method string) *node {
59
	for _, tree := range trees {
60 14
		if tree.method == method {
61 14
			return tree.root
62
		}
63
	}
64 14
	return nil
65
}
66

67
func min(a, b int) int {
68 14
	if a <= b {
69 14
		return a
70
	}
71 14
	return b
72
}
73

74
func longestCommonPrefix(a, b string) int {
75 14
	i := 0
76 14
	max := min(len(a), len(b))
77
	for i < max && a[i] == b[i] {
78 14
		i++
79
	}
80 14
	return i
81
}
82

83
func countParams(path string) uint16 {
84 14
	var n uint16
85 14
	s := bytesconv.StringToBytes(path)
86 14
	n += uint16(bytes.Count(s, strColon))
87 14
	n += uint16(bytes.Count(s, strStar))
88 14
	return n
89
}
90

91
type nodeType uint8
92

93
const (
94
	static nodeType = iota // default
95
	root
96
	param
97
	catchAll
98
)
99

100
type node struct {
101
	path      string
102
	indices   string
103
	wildChild bool
104
	nType     nodeType
105
	priority  uint32
106
	children  []*node
107
	handlers  HandlersChain
108
	fullPath  string
109
}
110

111
// Increments priority of the given child and reorders if necessary
112
func (n *node) incrementChildPrio(pos int) int {
113 14
	cs := n.children
114 14
	cs[pos].priority++
115 14
	prio := cs[pos].priority
116

117
	// Adjust position (move to front)
118 14
	newPos := pos
119
	for ; newPos > 0 && cs[newPos-1].priority < prio; newPos-- {
120
		// Swap node positions
121 14
		cs[newPos-1], cs[newPos] = cs[newPos], cs[newPos-1]
122

123
	}
124

125
	// Build new index char string
126 14
	if newPos != pos {
127 14
		n.indices = n.indices[:newPos] + // Unchanged prefix, might be empty
128 14
			n.indices[pos:pos+1] + // The index char we move
129 14
			n.indices[newPos:pos] + n.indices[pos+1:] // Rest without char at 'pos'
130
	}
131

132 14
	return newPos
133
}
134

135
// addRoute adds a node with the given handle to the path.
136
// Not concurrency-safe!
137
func (n *node) addRoute(path string, handlers HandlersChain) {
138 14
	fullPath := path
139 14
	n.priority++
140

141
	// Empty tree
142 14
	if len(n.path) == 0 && len(n.children) == 0 {
143 14
		n.insertChild(path, fullPath, handlers)
144 14
		n.nType = root
145 14
		return
146
	}
147

148 14
	parentFullPathIndex := 0
149

150 14
walk:
151
	for {
152
		// Find the longest common prefix.
153
		// This also implies that the common prefix contains no ':' or '*'
154
		// since the existing key can't contain those chars.
155 14
		i := longestCommonPrefix(path, n.path)
156

157
		// Split edge
158 14
		if i < len(n.path) {
159
			child := node{
160 14
				path:      n.path[i:],
161 14
				wildChild: n.wildChild,
162 14
				indices:   n.indices,
163 14
				children:  n.children,
164 14
				handlers:  n.handlers,
165 14
				priority:  n.priority - 1,
166 14
				fullPath:  n.fullPath,
167
			}
168

169 14
			n.children = []*node{&child}
170
			// []byte for proper unicode char conversion, see #65
171 14
			n.indices = bytesconv.BytesToString([]byte{n.path[i]})
172 14
			n.path = path[:i]
173 14
			n.handlers = nil
174 14
			n.wildChild = false
175 14
			n.fullPath = fullPath[:parentFullPathIndex+i]
176
		}
177

178
		// Make new node a child of this node
179 14
		if i < len(path) {
180 14
			path = path[i:]
181

182 14
			if n.wildChild {
183 14
				parentFullPathIndex += len(n.path)
184 14
				n = n.children[0]
185 14
				n.priority++
186

187
				// Check if the wildcard matches
188 14
				if len(path) >= len(n.path) && n.path == path[:len(n.path)] &&
189
					// Adding a child to a catchAll is not possible
190 14
					n.nType != catchAll &&
191
					// Check for longer wildcard, e.g. :name and :names
192 14
					(len(n.path) >= len(path) || path[len(n.path)] == '/') {
193 14
					continue walk
194
				}
195

196 14
				pathSeg := path
197 14
				if n.nType != catchAll {
198 14
					pathSeg = strings.SplitN(path, "/", 2)[0]
199
				}
200 14
				prefix := fullPath[:strings.Index(fullPath, pathSeg)] + n.path
201 14
				panic("'" + pathSeg +
202 14
					"' in new path '" + fullPath +
203 14
					"' conflicts with existing wildcard '" + n.path +
204 14
					"' in existing prefix '" + prefix +
205 14
					"'")
206
			}
207

208 14
			c := path[0]
209

210
			// slash after param
211 14
			if n.nType == param && c == '/' && len(n.children) == 1 {
212 14
				parentFullPathIndex += len(n.path)
213 14
				n = n.children[0]
214 14
				n.priority++
215 14
				continue walk
216
			}
217

218
			// Check if a child with the next path byte exists
219
			for i, max := 0, len(n.indices); i < max; i++ {
220 14
				if c == n.indices[i] {
221 14
					parentFullPathIndex += len(n.path)
222 14
					i = n.incrementChildPrio(i)
223 14
					n = n.children[i]
224 14
					continue walk
225
				}
226
			}
227

228
			// Otherwise insert it
229 14
			if c != ':' && c != '*' {
230
				// []byte for proper unicode char conversion, see #65
231 14
				n.indices += bytesconv.BytesToString([]byte{c})
232
				child := &node{
233 14
					fullPath: fullPath,
234
				}
235 14
				n.children = append(n.children, child)
236 14
				n.incrementChildPrio(len(n.indices) - 1)
237 14
				n = child
238
			}
239 14
			n.insertChild(path, fullPath, handlers)
240 14
			return
241
		}
242

243
		// Otherwise and handle to current node
244 14
		if n.handlers != nil {
245 14
			panic("handlers are already registered for path '" + fullPath + "'")
246
		}
247 14
		n.handlers = handlers
248 14
		n.fullPath = fullPath
249 14
		return
250
	}
251
}
252

253
// Search for a wildcard segment and check the name for invalid characters.
254
// Returns -1 as index, if no wildcard was found.
255
func findWildcard(path string) (wildcard string, i int, valid bool) {
256
	// Find start
257
	for start, c := range []byte(path) {
258
		// A wildcard starts with ':' (param) or '*' (catch-all)
259 14
		if c != ':' && c != '*' {
260 14
			continue
261
		}
262

263
		// Find end and check for invalid characters
264 14
		valid = true
265
		for end, c := range []byte(path[start+1:]) {
266 14
			switch c {
267 14
			case '/':
268 14
				return path[start : start+1+end], start, valid
269 14
			case ':', '*':
270 14
				valid = false
271
			}
272
		}
273 14
		return path[start:], start, valid
274
	}
275 14
	return "", -1, false
276
}
277

278
func (n *node) insertChild(path string, fullPath string, handlers HandlersChain) {
279
	for {
280
		// Find prefix until first wildcard
281 14
		wildcard, i, valid := findWildcard(path)
282 14
		if i < 0 { // No wildcard found
283 14
			break
284
		}
285

286
		// The wildcard name must not contain ':' and '*'
287 14
		if !valid {
288 14
			panic("only one wildcard per path segment is allowed, has: '" +
289 14
				wildcard + "' in path '" + fullPath + "'")
290
		}
291

292
		// check if the wildcard has a name
293 14
		if len(wildcard) < 2 {
294 14
			panic("wildcards must be named with a non-empty name in path '" + fullPath + "'")
295
		}
296

297
		// Check if this node has existing children which would be
298
		// unreachable if we insert the wildcard here
299 14
		if len(n.children) > 0 {
300 14
			panic("wildcard segment '" + wildcard +
301 14
				"' conflicts with existing children in path '" + fullPath + "'")
302
		}
303

304 14
		if wildcard[0] == ':' { // param
305 14
			if i > 0 {
306
				// Insert prefix before the current wildcard
307 14
				n.path = path[:i]
308 14
				path = path[i:]
309
			}
310

311 14
			n.wildChild = true
312
			child := &node{
313 14
				nType:    param,
314 14
				path:     wildcard,
315 14
				fullPath: fullPath,
316
			}
317 14
			n.children = []*node{child}
318 14
			n = child
319 14
			n.priority++
320

321
			// if the path doesn't end with the wildcard, then there
322
			// will be another non-wildcard subpath starting with '/'
323 14
			if len(wildcard) < len(path) {
324 14
				path = path[len(wildcard):]
325

326
				child := &node{
327 14
					priority: 1,
328 14
					fullPath: fullPath,
329
				}
330 14
				n.children = []*node{child}
331 14
				n = child
332 14
				continue
333
			}
334

335
			// Otherwise we're done. Insert the handle in the new leaf
336 14
			n.handlers = handlers
337 14
			return
338
		}
339

340
		// catchAll
341 14
		if i+len(wildcard) != len(path) {
342 14
			panic("catch-all routes are only allowed at the end of the path in path '" + fullPath + "'")
343
		}
344

345 14
		if len(n.path) > 0 && n.path[len(n.path)-1] == '/' {
346 14
			panic("catch-all conflicts with existing handle for the path segment root in path '" + fullPath + "'")
347
		}
348

349
		// currently fixed width 1 for '/'
350 14
		i--
351 14
		if path[i] != '/' {
352 14
			panic("no / before catch-all in path '" + fullPath + "'")
353
		}
354

355 14
		n.path = path[:i]
356

357
		// First node: catchAll node with empty path
358
		child := &node{
359 14
			wildChild: true,
360 14
			nType:     catchAll,
361 14
			fullPath:  fullPath,
362
		}
363

364 14
		n.children = []*node{child}
365 14
		n.indices = string('/')
366 14
		n = child
367 14
		n.priority++
368

369
		// second node: node holding the variable
370
		child = &node{
371 14
			path:     path[i:],
372 14
			nType:    catchAll,
373 14
			handlers: handlers,
374 14
			priority: 1,
375 14
			fullPath: fullPath,
376
		}
377 14
		n.children = []*node{child}
378

379 14
		return
380
	}
381

382
	// If no wildcard was found, simply insert the path and handle
383 14
	n.path = path
384 14
	n.handlers = handlers
385 14
	n.fullPath = fullPath
386
}
387

388
// nodeValue holds return values of (*Node).getValue method
389
type nodeValue struct {
390
	handlers HandlersChain
391
	params   *Params
392
	tsr      bool
393
	fullPath string
394
}
395

396
// Returns the handle registered with the given path (key). The values of
397
// wildcards are saved to a map.
398
// If no handle can be found, a TSR (trailing slash redirect) recommendation is
399
// made if a handle exists with an extra (without the) trailing slash for the
400
// given path.
401
func (n *node) getValue(path string, params *Params, unescape bool) (value nodeValue) {
402 14
walk: // Outer loop for walking the tree
403
	for {
404 14
		prefix := n.path
405 14
		if len(path) > len(prefix) {
406 14
			if path[:len(prefix)] == prefix {
407 14
				path = path[len(prefix):]
408
				// If this node does not have a wildcard (param or catchAll)
409
				// child, we can just look up the next child node and continue
410
				// to walk down the tree
411 14
				if !n.wildChild {
412 14
					idxc := path[0]
413
					for i, c := range []byte(n.indices) {
414 14
						if c == idxc {
415 14
							n = n.children[i]
416 14
							continue walk
417
						}
418
					}
419

420
					// Nothing found.
421
					// We can recommend to redirect to the same URL without a
422
					// trailing slash if a leaf exists for that path.
423 14
					value.tsr = (path == "/" && n.handlers != nil)
424 14
					return
425
				}
426

427
				// Handle wildcard child
428 14
				n = n.children[0]
429 14
				switch n.nType {
430 14
				case param:
431
					// Find param end (either '/' or path end)
432 14
					end := 0
433
					for end < len(path) && path[end] != '/' {
434 14
						end++
435
					}
436

437
					// Save param value
438 14
					if params != nil {
439 14
						if value.params == nil {
440 14
							value.params = params
441
						}
442
						// Expand slice within preallocated capacity
443 14
						i := len(*value.params)
444 14
						*value.params = (*value.params)[:i+1]
445 14
						val := path[:end]
446 14
						if unescape {
447 14
							if v, err := url.QueryUnescape(val); err == nil {
448 14
								val = v
449
							}
450
						}
451 14
						(*value.params)[i] = Param{
452 14
							Key:   n.path[1:],
453 14
							Value: val,
454
						}
455
					}
456

457
					// we need to go deeper!
458 14
					if end < len(path) {
459 14
						if len(n.children) > 0 {
460 14
							path = path[end:]
461 14
							n = n.children[0]
462 14
							continue walk
463
						}
464

465
						// ... but we can't
466 14
						value.tsr = (len(path) == end+1)
467 14
						return
468
					}
469

470 14
					if value.handlers = n.handlers; value.handlers != nil {
471 14
						value.fullPath = n.fullPath
472 14
						return
473
					}
474 14
					if len(n.children) == 1 {
475
						// No handle found. Check if a handle for this path + a
476
						// trailing slash exists for TSR recommendation
477 14
						n = n.children[0]
478 14
						value.tsr = (n.path == "/" && n.handlers != nil)
479
					}
480 14
					return
481

482 14
				case catchAll:
483
					// Save param value
484 14
					if params != nil {
485 14
						if value.params == nil {
486 14
							value.params = params
487
						}
488
						// Expand slice within preallocated capacity
489 14
						i := len(*value.params)
490 14
						*value.params = (*value.params)[:i+1]
491 14
						val := path
492 14
						if unescape {
493 14
							if v, err := url.QueryUnescape(path); err == nil {
494 14
								val = v
495
							}
496
						}
497 14
						(*value.params)[i] = Param{
498 14
							Key:   n.path[2:],
499 14
							Value: val,
500
						}
501
					}
502

503 14
					value.handlers = n.handlers
504 14
					value.fullPath = n.fullPath
505 14
					return
506

507 14
				default:
508 14
					panic("invalid node type")
509
				}
510
			}
511
		}
512

513 14
		if path == prefix {
514
			// We should have reached the node containing the handle.
515
			// Check if this node has a handle registered.
516 14
			if value.handlers = n.handlers; value.handlers != nil {
517 14
				value.fullPath = n.fullPath
518 14
				return
519
			}
520

521
			// If there is no handle for this route, but this route has a
522
			// wildcard child, there must be a handle for this path with an
523
			// additional trailing slash
524 14
			if path == "/" && n.wildChild && n.nType != root {
525 14
				value.tsr = true
526 14
				return
527
			}
528

529
			// No handle found. Check if a handle for this path + a
530
			// trailing slash exists for trailing slash recommendation
531
			for i, c := range []byte(n.indices) {
532 14
				if c == '/' {
533 14
					n = n.children[i]
534 14
					value.tsr = (len(n.path) == 1 && n.handlers != nil) ||
535 14
						(n.nType == catchAll && n.children[0].handlers != nil)
536 14
					return
537
				}
538
			}
539

540 14
			return
541
		}
542

543
		// Nothing found. We can recommend to redirect to the same URL with an
544
		// extra trailing slash if a leaf exists for that path
545 14
		value.tsr = (path == "/") ||
546 14
			(len(prefix) == len(path)+1 && prefix[len(path)] == '/' &&
547 14
				path == prefix[:len(prefix)-1] && n.handlers != nil)
548 14
		return
549
	}
550
}
551

552
// Makes a case-insensitive lookup of the given path and tries to find a handler.
553
// It can optionally also fix trailing slashes.
554
// It returns the case-corrected path and a bool indicating whether the lookup
555
// was successful.
556
func (n *node) findCaseInsensitivePath(path string, fixTrailingSlash bool) ([]byte, bool) {
557 14
	const stackBufSize = 128
558

559
	// Use a static sized buffer on the stack in the common case.
560
	// If the path is too long, allocate a buffer on the heap instead.
561 14
	buf := make([]byte, 0, stackBufSize)
562 14
	if l := len(path) + 1; l > stackBufSize {
563 14
		buf = make([]byte, 0, l)
564
	}
565

566 14
	ciPath := n.findCaseInsensitivePathRec(
567 14
		path,
568 14
		buf,       // Preallocate enough memory for new path
569 14
		[4]byte{}, // Empty rune buffer
570 14
		fixTrailingSlash,
571 14
	)
572

573 14
	return ciPath, ciPath != nil
574
}
575

576
// Shift bytes in array by n bytes left
577
func shiftNRuneBytes(rb [4]byte, n int) [4]byte {
578 14
	switch n {
579 14
	case 0:
580 14
		return rb
581 14
	case 1:
582 14
		return [4]byte{rb[1], rb[2], rb[3], 0}
583 14
	case 2:
584 14
		return [4]byte{rb[2], rb[3]}
585 14
	case 3:
586 14
		return [4]byte{rb[3]}
587 14
	default:
588 14
		return [4]byte{}
589
	}
590
}
591

592
// Recursive case-insensitive lookup function used by n.findCaseInsensitivePath
593
func (n *node) findCaseInsensitivePathRec(path string, ciPath []byte, rb [4]byte, fixTrailingSlash bool) []byte {
594 14
	npLen := len(n.path)
595

596 14
walk: // Outer loop for walking the tree
597
	for len(path) >= npLen && (npLen == 0 || strings.EqualFold(path[1:npLen], n.path[1:])) {
598
		// Add common prefix to result
599 14
		oldPath := path
600 14
		path = path[npLen:]
601 14
		ciPath = append(ciPath, n.path...)
602

603 14
		if len(path) > 0 {
604
			// If this node does not have a wildcard (param or catchAll) child,
605
			// we can just look up the next child node and continue to walk down
606
			// the tree
607 14
			if !n.wildChild {
608
				// Skip rune bytes already processed
609 14
				rb = shiftNRuneBytes(rb, npLen)
610

611 14
				if rb[0] != 0 {
612
					// Old rune not finished
613 14
					idxc := rb[0]
614
					for i, c := range []byte(n.indices) {
615 14
						if c == idxc {
616
							// continue with child node
617 14
							n = n.children[i]
618 14
							npLen = len(n.path)
619 14
							continue walk
620
						}
621
					}
622 14
				} else {
623
					// Process a new rune
624 14
					var rv rune
625

626
					// Find rune start.
627
					// Runes are up to 4 byte long,
628
					// -4 would definitely be another rune.
629 14
					var off int
630
					for max := min(npLen, 3); off < max; off++ {
631 14
						if i := npLen - off; utf8.RuneStart(oldPath[i]) {
632
							// read rune from cached path
633 14
							rv, _ = utf8.DecodeRuneInString(oldPath[i:])
634 14
							break
635
						}
636
					}
637

638
					// Calculate lowercase bytes of current rune
639 14
					lo := unicode.ToLower(rv)
640 14
					utf8.EncodeRune(rb[:], lo)
641

642
					// Skip already processed bytes
643 14
					rb = shiftNRuneBytes(rb, off)
644

645 14
					idxc := rb[0]
646
					for i, c := range []byte(n.indices) {
647
						// Lowercase matches
648 14
						if c == idxc {
649
							// must use a recursive approach since both the
650
							// uppercase byte and the lowercase byte might exist
651
							// as an index
652 14
							if out := n.children[i].findCaseInsensitivePathRec(
653 14
								path, ciPath, rb, fixTrailingSlash,
654 14
							); out != nil {
655 14
								return out
656
							}
657 14
							break
658
						}
659
					}
660

661
					// If we found no match, the same for the uppercase rune,
662
					// if it differs
663 14
					if up := unicode.ToUpper(rv); up != lo {
664 14
						utf8.EncodeRune(rb[:], up)
665 14
						rb = shiftNRuneBytes(rb, off)
666

667 14
						idxc := rb[0]
668
						for i, c := range []byte(n.indices) {
669
							// Uppercase matches
670 14
							if c == idxc {
671
								// Continue with child node
672 14
								n = n.children[i]
673 14
								npLen = len(n.path)
674 14
								continue walk
675
							}
676
						}
677
					}
678
				}
679

680
				// Nothing found. We can recommend to redirect to the same URL
681
				// without a trailing slash if a leaf exists for that path
682 14
				if fixTrailingSlash && path == "/" && n.handlers != nil {
683 14
					return ciPath
684
				}
685 14
				return nil
686
			}
687

688 14
			n = n.children[0]
689 14
			switch n.nType {
690 14
			case param:
691
				// Find param end (either '/' or path end)
692 14
				end := 0
693
				for end < len(path) && path[end] != '/' {
694 14
					end++
695
				}
696

697
				// Add param value to case insensitive path
698 14
				ciPath = append(ciPath, path[:end]...)
699

700
				// We need to go deeper!
701 14
				if end < len(path) {
702 14
					if len(n.children) > 0 {
703
						// Continue with child node
704 14
						n = n.children[0]
705 14
						npLen = len(n.path)
706 14
						path = path[end:]
707 14
						continue
708
					}
709

710
					// ... but we can't
711 14
					if fixTrailingSlash && len(path) == end+1 {
712 14
						return ciPath
713
					}
714 14
					return nil
715
				}
716

717 14
				if n.handlers != nil {
718 14
					return ciPath
719
				}
720

721 14
				if fixTrailingSlash && len(n.children) == 1 {
722
					// No handle found. Check if a handle for this path + a
723
					// trailing slash exists
724 14
					n = n.children[0]
725 14
					if n.path == "/" && n.handlers != nil {
726 14
						return append(ciPath, '/')
727
					}
728
				}
729

730 14
				return nil
731

732 14
			case catchAll:
733 14
				return append(ciPath, path...)
734

735 14
			default:
736 14
				panic("invalid node type")
737
			}
738 14
		} else {
739
			// We should have reached the node containing the handle.
740
			// Check if this node has a handle registered.
741 14
			if n.handlers != nil {
742 14
				return ciPath
743
			}
744

745
			// No handle found.
746
			// Try to fix the path by adding a trailing slash
747 14
			if fixTrailingSlash {
748
				for i, c := range []byte(n.indices) {
749 14
					if c == '/' {
750 14
						n = n.children[i]
751 14
						if (len(n.path) == 1 && n.handlers != nil) ||
752 14
							(n.nType == catchAll && n.children[0].handlers != nil) {
753 14
							return append(ciPath, '/')
754
						}
755 14
						return nil
756
					}
757
				}
758
			}
759 14
			return nil
760
		}
761
	}
762

763
	// Nothing found.
764
	// Try to fix the path by adding / removing a trailing slash
765 14
	if fixTrailingSlash {
766 14
		if path == "/" {
767 14
			return ciPath
768
		}
769 14
		if len(path)+1 == npLen && n.path[len(path)] == '/' &&
770 14
			strings.EqualFold(path[1:], n.path[1:len(path)]) && n.handlers != nil {
771 14
			return append(ciPath, n.path...)
772
		}
773
	}
774 14
	return nil
775
}

Read our documentation on viewing source code .

Loading