gin-gonic / gin
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 8
		if entry.Key == name {
38 8
			return entry.Value, true
39
		}
40
	}
41 8
	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 8
	va, _ = ps.Get(name)
48 8
	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 8
		if tree.method == method {
61 8
			return tree.root
62
		}
63
	}
64 8
	return nil
65
}
66

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

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

83
func countParams(path string) uint16 {
84 8
	var n uint16
85 8
	s := bytesconv.StringToBytes(path)
86 8
	n += uint16(bytes.Count(s, strColon))
87 8
	n += uint16(bytes.Count(s, strStar))
88 8
	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 8
	cs := n.children
114 8
	cs[pos].priority++
115 8
	prio := cs[pos].priority
116

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

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

131 8
	return newPos
132
}
133

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

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

147 8
	parentFullPathIndex := 0
148

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

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

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

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

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

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

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

207 8
			c := path[0]
208

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

354 8
		n.path = path[:i]
355

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

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

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

378 8
		return
379
	}
380

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

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

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

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

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

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

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

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

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

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

502 8
					value.handlers = n.handlers
503 8
					value.fullPath = n.fullPath
504 8
					return
505

506 8
				default:
507 8
					panic("invalid node type")
508
				}
509
			}
510
		}
511

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

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

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

539 8
			return
540
		}
541

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

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

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

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

572 8
	return ciPath, ciPath != nil
573
}
574

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

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

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

602 8
		if len(path) == 0 {
603
			// We should have reached the node containing the handle.
604
			// Check if this node has a handle registered.
605 8
			if n.handlers != nil {
606 8
				return ciPath
607
			}
608

609
			// No handle found.
610
			// Try to fix the path by adding a trailing slash
611 8
			if fixTrailingSlash {
612
				for i, c := range []byte(n.indices) {
613 8
					if c == '/' {
614 8
						n = n.children[i]
615 8
						if (len(n.path) == 1 && n.handlers != nil) ||
616 8
							(n.nType == catchAll && n.children[0].handlers != nil) {
617 8
							return append(ciPath, '/')
618
						}
619 8
						return nil
620
					}
621
				}
622
			}
623 8
			return nil
624
		}
625

626
		// If this node does not have a wildcard (param or catchAll) child,
627
		// we can just look up the next child node and continue to walk down
628
		// the tree
629 8
		if !n.wildChild {
630
			// Skip rune bytes already processed
631 8
			rb = shiftNRuneBytes(rb, npLen)
632

633 8
			if rb[0] != 0 {
634
				// Old rune not finished
635 8
				idxc := rb[0]
636
				for i, c := range []byte(n.indices) {
637 8
					if c == idxc {
638
						// continue with child node
639 8
						n = n.children[i]
640 8
						npLen = len(n.path)
641 8
						continue walk
642
					}
643
				}
644 8
			} else {
645
				// Process a new rune
646 8
				var rv rune
647

648
				// Find rune start.
649
				// Runes are up to 4 byte long,
650
				// -4 would definitely be another rune.
651 8
				var off int
652
				for max := min(npLen, 3); off < max; off++ {
653 8
					if i := npLen - off; utf8.RuneStart(oldPath[i]) {
654
						// read rune from cached path
655 8
						rv, _ = utf8.DecodeRuneInString(oldPath[i:])
656 8
						break
657
					}
658
				}
659

660
				// Calculate lowercase bytes of current rune
661 8
				lo := unicode.ToLower(rv)
662 8
				utf8.EncodeRune(rb[:], lo)
663

664
				// Skip already processed bytes
665 8
				rb = shiftNRuneBytes(rb, off)
666

667 8
				idxc := rb[0]
668
				for i, c := range []byte(n.indices) {
669
					// Lowercase matches
670 8
					if c == idxc {
671
						// must use a recursive approach since both the
672
						// uppercase byte and the lowercase byte might exist
673
						// as an index
674 8
						if out := n.children[i].findCaseInsensitivePathRec(
675 8
							path, ciPath, rb, fixTrailingSlash,
676 8
						); out != nil {
677 8
							return out
678
						}
679 8
						break
680
					}
681
				}
682

683
				// If we found no match, the same for the uppercase rune,
684
				// if it differs
685 8
				if up := unicode.ToUpper(rv); up != lo {
686 8
					utf8.EncodeRune(rb[:], up)
687 8
					rb = shiftNRuneBytes(rb, off)
688

689 8
					idxc := rb[0]
690
					for i, c := range []byte(n.indices) {
691
						// Uppercase matches
692 8
						if c == idxc {
693
							// Continue with child node
694 8
							n = n.children[i]
695 8
							npLen = len(n.path)
696 8
							continue walk
697
						}
698
					}
699
				}
700
			}
701

702
			// Nothing found. We can recommend to redirect to the same URL
703
			// without a trailing slash if a leaf exists for that path
704 8
			if fixTrailingSlash && path == "/" && n.handlers != nil {
705 8
				return ciPath
706
			}
707 8
			return nil
708
		}
709

710 8
		n = n.children[0]
711 8
		switch n.nType {
712 8
		case param:
713
			// Find param end (either '/' or path end)
714 8
			end := 0
715
			for end < len(path) && path[end] != '/' {
716 8
				end++
717
			}
718

719
			// Add param value to case insensitive path
720 8
			ciPath = append(ciPath, path[:end]...)
721

722
			// We need to go deeper!
723 8
			if end < len(path) {
724 8
				if len(n.children) > 0 {
725
					// Continue with child node
726 8
					n = n.children[0]
727 8
					npLen = len(n.path)
728 8
					path = path[end:]
729 8
					continue
730
				}
731

732
				// ... but we can't
733 8
				if fixTrailingSlash && len(path) == end+1 {
734 8
					return ciPath
735
				}
736 8
				return nil
737
			}
738

739 8
			if n.handlers != nil {
740 8
				return ciPath
741
			}
742

743 8
			if fixTrailingSlash && len(n.children) == 1 {
744
				// No handle found. Check if a handle for this path + a
745
				// trailing slash exists
746 8
				n = n.children[0]
747 8
				if n.path == "/" && n.handlers != nil {
748 8
					return append(ciPath, '/')
749
				}
750
			}
751

752 8
			return nil
753

754 8
		case catchAll:
755 8
			return append(ciPath, path...)
756

757 8
		default:
758 8
			panic("invalid node type")
759
		}
760
	}
761

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

Read our documentation on viewing source code .

Loading