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

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

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

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

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

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

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

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

147 151
	parentFullPathIndex := 0
148

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

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

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

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

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

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

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

207 151
			c := path[0]
208

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

378 151
		return
379
	}
380

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

609
			// No handle found.
610
			// Try to fix the path by adding a trailing slash
611 151
			if fixTrailingSlash {
612
				for i, c := range []byte(n.indices) {
</