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

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

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

83
// addChild will add a child node, keeping wildcards at the end
84
func (n *node) addChild(child *node) {
85 18
	if n.wildChild && len(n.children) > 0 {
86 18
		wildcardChild := n.children[len(n.children)-1]
87 18
		n.children = append(n.children[:len(n.children)-1], child, wildcardChild)
88 18
	} else {
89 18
		n.children = append(n.children, child)
90
	}
91
}
92

93
func countParams(path string) uint16 {
94 18
	var n uint16
95 18
	s := bytesconv.StringToBytes(path)
96 18
	n += uint16(bytes.Count(s, strColon))
97 18
	n += uint16(bytes.Count(s, strStar))
98 18
	return n
99
}
100

101
type nodeType uint8
102

103
const (
104
	static nodeType = iota // default
105
	root
106
	param
107
	catchAll
108
)
109

110
type node struct {
111
	path      string
112
	indices   string
113
	wildChild bool
114
	nType     nodeType
115
	priority  uint32
116
	children  []*node // child nodes, at most 1 :param style node at the end of the array
117
	handlers  HandlersChain
118
	fullPath  string
119
}
120

121
// Increments priority of the given child and reorders if necessary
122
func (n *node) incrementChildPrio(pos int) int {
123 18
	cs := n.children
124 18
	cs[pos].priority++
125 18
	prio := cs[pos].priority
126

127
	// Adjust position (move to front)
128 18
	newPos := pos
129
	for ; newPos > 0 && cs[newPos-1].priority < prio; newPos-- {
130
		// Swap node positions
131 18
		cs[newPos-1], cs[newPos] = cs[newPos], cs[newPos-1]
132
	}
133

134
	// Build new index char string
135 18
	if newPos != pos {
136 18
		n.indices = n.indices[:newPos] + // Unchanged prefix, might be empty
137 18
			n.indices[pos:pos+1] + // The index char we move
138 18
			n.indices[newPos:pos] + n.indices[pos+1:] // Rest without char at 'pos'
139
	}
140

141 18
	return newPos
142
}
143

144
// addRoute adds a node with the given handle to the path.
145
// Not concurrency-safe!
146
func (n *node) addRoute(path string, handlers HandlersChain) {
147 18
	fullPath := path
148 18
	n.priority++
149

150
	// Empty tree
151 18
	if len(n.path) == 0 && len(n.children) == 0 {
152 18
		n.insertChild(path, fullPath, handlers)
153 18
		n.nType = root
154 18
		return
155
	}
156

157 18
	parentFullPathIndex := 0
158

159 18
walk:
160
	for {
161
		// Find the longest common prefix.
162
		// This also implies that the common prefix contains no ':' or '*'
163
		// since the existing key can't contain those chars.
164 18
		i := longestCommonPrefix(path, n.path)
165

166
		// Split edge
167 18
		if i < len(n.path) {
168
			child := node{
169 18
				path:      n.path[i:],
170 18
				wildChild: n.wildChild,
171 18
				indices:   n.indices,
172 18
				children:  n.children,
173 18
				handlers:  n.handlers,
174 18
				priority:  n.priority - 1,
175 18
				fullPath:  n.fullPath,
176
			}
177

178 18
			n.children = []*node{&child}
179
			// []byte for proper unicode char conversion, see #65
180 18
			n.indices = bytesconv.BytesToString([]byte{n.path[i]})
181 18
			n.path = path[:i]
182 18
			n.handlers = nil
183 18
			n.wildChild = false
184 18
			n.fullPath = fullPath[:parentFullPathIndex+i]
185
		}
186

187
		// Make new node a child of this node
188 18
		if i < len(path) {
189 18
			path = path[i:]
190 18
			c := path[0]
191

192
			// '/' after param
193 18
			if n.nType == param && c == '/' && len(n.children) == 1 {
194 18
				parentFullPathIndex += len(n.path)
195 18
				n = n.children[0]
196 18
				n.priority++
197 18
				continue walk
198
			}
199

200
			// Check if a child with the next path byte exists
201
			for i, max := 0, len(n.indices); i < max; i++ {
202 18
				if c == n.indices[i] {
203 18
					parentFullPathIndex += len(n.path)
204 18
					i = n.incrementChildPrio(i)
205 18
					n = n.children[i]
206 18
					continue walk
207
				}
208
			}
209

210
			// Otherwise insert it
211 18
			if c != ':' && c != '*' && n.nType != catchAll {
212
				// []byte for proper unicode char conversion, see #65
213 18
				n.indices += bytesconv.BytesToString([]byte{c})
214
				child := &node{
215 18
					fullPath: fullPath,
216
				}
217 18
				n.addChild(child)
218 18
				n.incrementChildPrio(len(n.indices) - 1)
219 18
				n = child
220 18
			} else if n.wildChild {
221
				// inserting a wildcard node, need to check if it conflicts with the existing wildcard
222 18
				n = n.children[len(n.children)-1]
223 18
				n.priority++
224

225
				// Check if the wildcard matches
226 18
				if len(path) >= len(n.path) && n.path == path[:len(n.path)] &&
227
					// Adding a child to a catchAll is not possible
228 18
					n.nType != catchAll &&
229
					// Check for longer wildcard, e.g. :name and :names
230 18
					(len(n.path) >= len(path) || path[len(n.path)] == '/') {
231 18
					continue walk
232
				}
233

234
				// Wildcard conflict
235 18
				pathSeg := path
236 18
				if n.nType != catchAll {
237 18
					pathSeg = strings.SplitN(pathSeg, "/", 2)[0]
238
				}
239 18
				prefix := fullPath[:strings.Index(fullPath, pathSeg)] + n.path
240 18
				panic("'" + pathSeg +
241 18
					"' in new path '" + fullPath +
242 18
					"' conflicts with existing wildcard '" + n.path +
243 18
					"' in existing prefix '" + prefix +
244 18
					"'")
245
			}
246

247 18
			n.insertChild(path, fullPath, handlers)
248 18
			return
249
		}
250

251
		// Otherwise add handle to current node
252 18
		if n.handlers != nil {
253 18
			panic("handlers are already registered for path '" + fullPath + "'")
254
		}
255 18
		n.handlers = handlers
256 18
		n.fullPath = fullPath
257 18
		return
258
	}
259
}
260

261
// Search for a wildcard segment and check the name for invalid characters.
262
// Returns -1 as index, if no wildcard was found.
263
func findWildcard(path string) (wildcard string, i int, valid bool) {
264
	// Find start
265
	for start, c := range []byte(path) {
266
		// A wildcard starts with ':' (param) or '*' (catch-all)
267 18
		if c != ':' && c != '*' {
268 18
			continue
269
		}
270

271
		// Find end and check for invalid characters
272 18
		valid = true
273
		for end, c := range []byte(path[start+1:]) {
274 18
			switch c {
275 18
			case '/':
276 18
				return path[start : start+1+end], start, valid
277 18
			case ':', '*':
278 18
				valid = false
279
			}
280
		}
281 18
		return path[start:], start, valid
282
	}
283 18
	return "", -1, false
284
}
285

286
func (n *node) insertChild(path string, fullPath string, handlers HandlersChain) {
287
	for {
288
		// Find prefix until first wildcard
289 18
		wildcard, i, valid := findWildcard(path)
290 18
		if i < 0 { // No wildcard found
291 18
			break
292
		}
293

294
		// The wildcard name must not contain ':' and '*'
295 18
		if !valid {
296 18
			panic("only one wildcard per path segment is allowed, has: '" +
297 18
				wildcard + "' in path '" + fullPath + "'")
298
		}
299

300
		// check if the wildcard has a name
301 18
		if len(wildcard) < 2 {
302 18
			panic("wildcards must be named with a non-empty name in path '" + fullPath + "'")
303
		}
304

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

312
			child := &node{
313 18
				nType:    param,
314 18
				path:     wildcard,
315 18
				fullPath: fullPath,
316
			}
317 18
			n.addChild(child)
318 18
			n.wildChild = true
319 18
			n = child
320 18
			n.priority++
321

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

327
				child := &node{
328 18
					priority: 1,
329 18
					fullPath: fullPath,
330
				}
331 18
				n.addChild(child)
332 18
				n = child
333 18
				continue
334
			}
335

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

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

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

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

356 18
		n.path = path[:i]
357

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

365 18
		n.addChild(child)
366 18
		n.indices = string('/')
367 18
		n = child
368 18
		n.priority++
369

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

380 18
		return
381
	}
382

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

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

397
// Returns the handle registered with the given path (key). The values of
398
// wildcards are saved to a map.
399
// If no handle can be found, a TSR (trailing slash redirect) recommendation is
400
// made if a handle exists with an extra (without the) trailing slash for the
401
// given path.
402
func (n *node) getValue(path string, params *Params, unescape bool) (value nodeValue) {
403 18
walk: // Outer loop for walking the tree
404
	for {
405 18
		prefix := n.path
406 18
		if len(path) > len(prefix) {
407 18
			if path[:len(prefix)] == prefix {
408 18
				path = path[len(prefix):]
409

410
				// Try all the non-wildcard children first by matching the indices
411 18
				idxc := path[0]
412
				for i, c := range []byte(n.indices) {
413 18
					if c == idxc {
414 18
						n = n.children[i]
415 18
						continue walk
416
					}
417
				}
418

419
				// If there is no wildcard pattern, recommend a redirection
420 18
				if !n.wildChild {
421
					// Nothing found.
422
					// We can recommend to redirect to the same URL without a
423
					// trailing slash if a leaf exists for that path.
424 18
					value.tsr = (path == "/" && n.handlers != nil)
425 18
					return
426
				}
427

428
				// Handle wildcard child, which is always at the end of the array
429 18
				n = n.children[len(n.children)-1]
430

431 18
				switch n.nType {
432 18
				case param:
433
					// Find param end (either '/' or path end)
434 18
					end := 0
435
					for end < len(path) && path[end] != '/' {
436 18
						end++
437
					}
438

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

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

467
						// ... but we can't
468 18
						value.tsr = (len(path) == end+1)
469 18
						return
470
					}
471

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

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

505 18
					value.handlers = n.handlers
506 18
					value.fullPath = n.fullPath
507 18
					return
508

509 18
				default:
510 18
					panic("invalid node type")
511
				}
512
			}
513
		}
514

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

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

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

542 18
			return
543
		}
544

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

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

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

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

575 18
	return ciPath, ciPath != nil
576
}
577

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

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

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

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

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

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

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

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

663
				// Calculate lowercase bytes of current rune
664 18
				lo := unicode.ToLower(rv)
665 18
				utf8.EncodeRune(rb[:], lo)
666

667
				// Skip already processed bytes
668 18
				rb = shiftNRuneBytes(rb, off)
669

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

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

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

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

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

722
			// Add param value to case insensitive path
723 18
			ciPath = append(ciPath, path[:end]...)
724

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

735
				// ... but we can't
736 18
				if fixTrailingSlash && len(path) == end+1 {
737 18
					return ciPath
738
				}
739 18
				return nil
740
			}
741

742 18
			if n.handlers != nil {
743 18
				return ciPath
744
			}
745

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

755 18
			return nil
756

757 18
		case catchAll:
758 18
			return append(ciPath, path...)
759

760 18
		default:
761 18
			panic("invalid node type")
762
		}
763
	}
764

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

Read our documentation on viewing source code .

Loading