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

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

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

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

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

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

131 101
	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 101
	fullPath := path
138 101
	n.priority++
139

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

147 101
	parentFullPathIndex := 0
148

149 101
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 101
		i := longestCommonPrefix(path, n.path)
155

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

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

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

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

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

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

207 101
			c := path[0]
208

209
			// slash after param
210 101
			if n.nType == param && c == '/' && len(n.children) == 1 {
211 101
				parentFullPathIndex += len(n.path)
212 101
				n = n.children[0]
213 101
				n.priority++
214 101
				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 101
				if c == n.indices[i] {
220 101
					parentFullPathIndex += len(n.path)
221 101
					i = n.incrementChildPrio(i)
222 101
					n = n.children[i]
223 101
					continue walk
224
				}
225
			}
226

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

242
		// Otherwise and handle to current node
243 101
		if n.handlers != nil {
244 101
			panic("handlers are already registered for path '" + fullPath + "'")
245
		}
246 101
		n.handlers = handlers
247 101
		n.fullPath = fullPath
248 101
		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 101
		if c != ':' && c != '*' {
259 101
			continue
260
		}
261

262
		// Find end and check for invalid characters
263 101
		valid = true
264
		for end, c := range []byte(path[start+1:]) {
265 101
			switch c {
266 101
			case '/':
267 101
				return path[start : start+1+end], start, valid
268 101
			case ':', '*':
269 101
				valid = false
270
			}
271
		}
272 101
		return path[start:], start, valid
273
	}
274 101
	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 101
		wildcard, i, valid := findWildcard(path)
281 101
		if i < 0 { // No wildcard found
282 101
			break
283
		}
284

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

291
		// check if the wildcard has a name
292 101
		if len(wildcard) < 2 {
293 101
			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 101
		if len(n.children) > 0 {
299 101
			panic("wildcard segment '" + wildcard +
300 101
				"' conflicts with existing children in path '" + fullPath + "'")
301
		}
302

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

310 101
			n.wildChild = true
311
			child := &node{
312 101
				nType:    param,
313 101
				path:     wildcard,
314 101
				fullPath: fullPath,
315
			}
316 101
			n.children = []*node{child}
317 101
			n = child
318 101
			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 101
			if len(wildcard) < len(path) {
323 101
				path = path[len(wildcard):]
324

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

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

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

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

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

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

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

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

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

378 101
		return
379
	}
380

381
	// If no wildcard was found, simply insert the path and handle
382 101
	n.path = path
383 101
	n.handlers = handlers
384 101
	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 101
walk: // Outer loop for walking the tree
402
	for {
403 101
		prefix := n.path
404 101
		if len(path) > len(prefix) {
405 101
			if path[:len(prefix)] == prefix {
406 101
				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 101
				if !n.wildChild {
411 101
					idxc := path[0]
412
					for i, c := range []byte(n.indices) {
413 101
						if c == idxc {
414 101
							n = n.children[i]
415 101
							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 101
					value.tsr = (path == "/" && n.handlers != nil)
423 101
					return
424
				}
425

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

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

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

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

469 101
					if value.handlers = n.handlers; value.handlers != nil {
470 101
						value.fullPath = n.fullPath
471 101
						return
472
					}
473 101
					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 101
						n = n.children[0]
477 101
						value.tsr = (n.path == "/" && n.handlers != nil)
478
					}
479 101
					return
480

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

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

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

512 101
		if path == prefix {
513
			// We should have reached the node containing the handle.
514
			// Check if this node has a handle registered.
515 101
			if value.handlers = n.handlers; value.handlers != nil {
516 101
				value.fullPath = n.fullPath
517 101
				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 101
			if path == "/" && n.wildChild && n.nType != root {
524 101
				value.tsr = true
525 101
				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 101
				if c == '/' {
532 101
					n = n.children[i]
533 101
					value.tsr = (len(n.path) == 1 && n.handlers != nil) ||
534 101
						(n.nType == catchAll && n.children[0].handlers != nil)
535 101
					return
536
				}
537
			}
538

539 101
			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 101
		value.tsr = (path == "/") ||
545 101
			(len(prefix) == len(path)+1 && prefix[len(path)] == '/' &&
546 101
				path == prefix[:len(prefix)-1] && n.handlers != nil)
547 101
		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 101
	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 101
	buf := make([]byte, 0, stackBufSize)
561 101
	if length := len(path) + 1; length > stackBufSize {
562 101
		buf = make([]byte, 0, length)
563
	}
564

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

572 101
	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 101
	switch n {
578 101
	case 0:
579 101
		return rb
580 101
	case 1:
581 101
		return [4]byte{rb[1], rb[2], rb[3], 0}
582 101
	case 2:
583 101
		return [4]byte{rb[2], rb[3]}
584 101
	case 3:
585 101
		return [4]byte{rb[3]}
586 101
	default:
587 101
		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 101
	npLen := len(n.path)
594

595 101
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 101
		oldPath := path
599 101
		path = path[npLen:]
600 101
		ciPath = append(ciPath, n.path...)
601

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

609
			// No handle found.
610
			// Try to fix the path by adding a trailing slash
611 101
			if fixTrailingSlash {
612
				for i, c := range []byte(n.indices) {
613 101
					if c == '/' {
614 101
						n = n.children[i]
615 101
						if (len(n.path) == 1 && n.handlers != nil) ||
616 101
							(n.nType == catchAll && n.children[0].handlers != nil) {
617 101
							return append(ciPath, '/')
618
						}
619 101
						return nil
620
					}
621
				}
622
			}
623 101
			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 101
		if !n.wildChild {
630
			// Skip rune bytes already processed
631 101
			rb = shiftNRuneBytes(rb, npLen)
632

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

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

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

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

667 101
				idxc := rb[0]
668
				for i, c := range []byte(n.indices) {
669
					// Lowercase matches
670 101
					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 101
						if out := n.children[i].findCaseInsensitivePathRec(
675 101
							path, ciPath, rb, fixTrailingSlash,
676 101
						); out != nil {
677 101
							return out
678
						}
679 101
						break
680
					}
681
				}
682

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

689 101
					idxc := rb[0]
690
					for i, c := range []byte(n.indices) {
691
						// Uppercase matches
692 101
						if c == idxc {
693
							// Continue with child node
694 101
							n = n.children[i]
695 101
							npLen = len(n.path)
696 101
							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 101
			if fixTrailingSlash && path == "/" && n.handlers != nil {
705 101
				return ciPath
706
			}
707 101
			return nil
708
		}
709

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

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

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

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

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

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

752 101
			return nil
753

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

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

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

Read our documentation on viewing source code .

Loading