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
13 // Param is a single URL parameter, consisting of a key and a value.
19 // Params is a Param-slice, as returned by the router.
20 // The slice is ordered, the first URL parameter is also the first slice value.
21 // It is therefore safe to read values by the index.
24 // Get returns the value of the first Param which key matches the given name.
25 // If no matching Param is found, an empty string is returned.
26 func (ps Params) Get(name string) (string, bool) {
27 for _, entry := range ps {
28 if entry.Key == name {
29 return entry.Value, true
35 // ByName returns the value of the first Param which key matches the given name.
36 // If no matching Param is found, an empty string is returned.
37 func (ps Params) ByName(name string) (va string) {
42 type methodTree struct {
47 type methodTrees []methodTree
49 func (trees methodTrees) get(method string) *node {
50 for _, tree := range trees {
51 if tree.method == method {
58 func min(a, b int) int {
65 func countParams(path string) uint8 {
67 for i := 0; i < len(path); i++ {
68 if path[i] != ':' && path[i] != '*' {
82 static nodeType = iota // default
92 handlers HandlersChain
99 // increments priority of the given child and reorders if necessary.
100 func (n *node) incrementChildPrio(pos int) int {
101 n.children[pos].priority++
102 prio := n.children[pos].priority
104 // adjust position (move to front)
106 for newPos > 0 && n.children[newPos-1].priority < prio {
107 // swap node positions
108 n.children[newPos-1], n.children[newPos] = n.children[newPos], n.children[newPos-1]
113 // build new index char string
115 n.indices = n.indices[:newPos] + // unchanged prefix, might be empty
116 n.indices[pos:pos+1] + // the index char we move
117 n.indices[newPos:pos] + n.indices[pos+1:] // rest without char at 'pos'
123 // addRoute adds a node with the given handle to the path.
124 // Not concurrency-safe!
125 func (n *node) addRoute(path string, handlers HandlersChain) {
128 numParams := countParams(path)
131 if len(n.path) > 0 || len(n.children) > 0 {
134 // Update maxParams of the current node
135 if numParams > n.maxParams {
136 n.maxParams = numParams
139 // Find the longest common prefix.
140 // This also implies that the common prefix contains no ':' or '*'
141 // since the existing key can't contain those chars.
143 max := min(len(path), len(n.path))
144 for i < max && path[i] == n.path[i] {
152 wildChild: n.wildChild,
154 children: n.children,
155 handlers: n.handlers,
156 priority: n.priority - 1,
159 // Update maxParams (max of all children)
160 for i := range child.children {
161 if child.children[i].maxParams > child.maxParams {
162 child.maxParams = child.children[i].maxParams
166 n.children = []*node{&child}
167 // []byte for proper unicode char conversion, see #65
168 n.indices = string([]byte{n.path[i]})
174 // Make new node a child of this node
182 // Update maxParams of the child node
183 if numParams > n.maxParams {
184 n.maxParams = numParams
188 // Check if the wildcard matches
189 if len(path) >= len(n.path) && n.path == path[:len(n.path)] {
190 // check for longer wildcard, e.g. :name and :names
191 if len(n.path) >= len(path) || path[len(n.path)] == '/' {
196 panic("path segment '" + path +
197 "' conflicts with existing wildcard '" + n.path +
198 "' in path '" + fullPath + "'")
204 if n.nType == param && c == '/' && len(n.children) == 1 {
210 // Check if a child with the next path byte exists
211 for i := 0; i < len(n.indices); i++ {
212 if c == n.indices[i] {
213 i = n.incrementChildPrio(i)
219 // Otherwise insert it
220 if c != ':' && c != '*' {
221 // []byte for proper unicode char conversion, see #65
222 n.indices += string([]byte{c})
224 maxParams: numParams,
226 n.children = append(n.children, child)
227 n.incrementChildPrio(len(n.indices) - 1)
230 n.insertChild(numParams, path, fullPath, handlers)
233 } else if i == len(path) { // Make node a (in-path) leaf
234 if n.handlers != nil {
235 panic("handlers are already registered for path '" + fullPath + "'")
237 n.handlers = handlers
241 } else { // Empty tree
242 n.insertChild(numParams, path, fullPath, handlers)
247 func (n *node) insertChild(numParams uint8, path string, fullPath string, handlers HandlersChain) {
248 var offset int // already handled bytes of the path
250 // find prefix until first wildcard (beginning with ':' or '*')
251 for i, max := 0, len(path); numParams > 0; i++ {
253 if c != ':' && c != '*' {
257 // find wildcard end (either '/' or path end)
259 for end < max && path[end] != '/' {
261 // the wildcard name must not contain ':' and '*'
263 panic("only one wildcard per path segment is allowed, has: '" +
264 path[i:] + "' in path '" + fullPath + "'")
270 // check if this Node existing children which would be
271 // unreachable if we insert the wildcard here
272 if len(n.children) > 0 {
273 panic("wildcard route '" + path[i:end] +
274 "' conflicts with existing children in path '" + fullPath + "'")
277 // check if the wildcard has a name
279 panic("wildcards must be named with a non-empty name in path '" + fullPath + "'")
282 if c == ':' { // param
283 // split path at the beginning of the wildcard
285 n.path = path[offset:i]
291 maxParams: numParams,
293 n.children = []*node{child}
299 // if the path doesn't end with the wildcard, then there
300 // will be another non-wildcard subpath starting with '/'
302 n.path = path[offset:end]
306 maxParams: numParams,
309 n.children = []*node{child}
314 if end != max || numParams > 1 {
315 panic("catch-all routes are only allowed at the end of the path in path '" + fullPath + "'")
318 if len(n.path) > 0 && n.path[len(n.path)-1] == '/' {
319 panic("catch-all conflicts with existing handle for the path segment root in path '" + fullPath + "'")
322 // currently fixed width 1 for '/'
325 panic("no / before catch-all in path '" + fullPath + "'")
328 n.path = path[offset:i]
330 // first node: catchAll node with empty path
336 n.children = []*node{child}
337 n.indices = string(path[i])
341 // second node: node holding the variable
349 n.children = []*node{child}
355 // insert remaining path part and handle to the leaf
356 n.path = path[offset:]
357 n.handlers = handlers
360 // getValue returns the handle registered with the given path (key). The values of
361 // wildcards are saved to a map.
362 // If no handle can be found, a TSR (trailing slash redirect) recommendation is
363 // made if a handle exists with an extra (without the) trailing slash for the
365 func (n *node) getValue(path string, po Params, unescape bool) (handlers HandlersChain, p Params, tsr bool) {
367 walk: // Outer loop for walking the tree
369 if len(path) > len(n.path) {
370 if path[:len(n.path)] == n.path {
371 path = path[len(n.path):]
372 // If this node does not have a wildcard (param or catchAll)
373 // child, we can just look up the next child node and continue
374 // to walk down the tree
377 for i := 0; i < len(n.indices); i++ {
378 if c == n.indices[i] {
385 // We can recommend to redirect to the same URL without a
386 // trailing slash if a leaf exists for that path.
387 tsr = path == "/" && n.handlers != nil
391 // handle wildcard child
395 // find param end (either '/' or path end)
397 for end < len(path) && path[end] != '/' {
402 if cap(p) < int(n.maxParams) {
403 p = make(Params, 0, n.maxParams)
406 p = p[:i+1] // expand slice within preallocated capacity
407 p[i].Key = n.path[1:]
411 if p[i].Value, err = url.QueryUnescape(val); err != nil {
412 p[i].Value = val // fallback, in case of error
418 // we need to go deeper!
420 if len(n.children) > 0 {
427 tsr = len(path) == end+1
431 if handlers = n.handlers; handlers != nil {
434 if len(n.children) == 1 {
435 // No handle found. Check if a handle for this path + a
436 // trailing slash exists for TSR recommendation
438 tsr = n.path == "/" && n.handlers != nil
445 if cap(p) < int(n.maxParams) {
446 p = make(Params, 0, n.maxParams)
449 p = p[:i+1] // expand slice within preallocated capacity
450 p[i].Key = n.path[2:]
453 if p[i].Value, err = url.QueryUnescape(path); err != nil {
454 p[i].Value = path // fallback, in case of error
460 handlers = n.handlers
464 panic("invalid node type")
467 } else if path == n.path {
468 // We should have reached the node containing the handle.
469 // Check if this node has a handle registered.
470 if handlers = n.handlers; handlers != nil {
474 if path == "/" && n.wildChild && n.nType != root {
479 // No handle found. Check if a handle for this path + a
480 // trailing slash exists for trailing slash recommendation
481 for i := 0; i < len(n.indices); i++ {
482 if n.indices[i] == '/' {
484 tsr = (len(n.path) == 1 && n.handlers != nil) ||
485 (n.nType == catchAll && n.children[0].handlers != nil)
493 // Nothing found. We can recommend to redirect to the same URL with an
494 // extra trailing slash if a leaf exists for that path
495 tsr = (path == "/") ||
496 (len(n.path) == len(path)+1 && n.path[len(path)] == '/' &&
497 path == n.path[:len(n.path)-1] && n.handlers != nil)
502 // findCaseInsensitivePath makes a case-insensitive lookup of the given path and tries to find a handler.
503 // It can optionally also fix trailing slashes.
504 // It returns the case-corrected path and a bool indicating whether the lookup
506 func (n *node) findCaseInsensitivePath(path string, fixTrailingSlash bool) (ciPath []byte, found bool) {
507 ciPath = make([]byte, 0, len(path)+1) // preallocate enough memory
509 // Outer loop for walking the tree
510 for len(path) >= len(n.path) && strings.ToLower(path[:len(n.path)]) == strings.ToLower(n.path) {
511 path = path[len(n.path):]
512 ciPath = append(ciPath, n.path...)
515 // If this node does not have a wildcard (param or catchAll) child,
516 // we can just look up the next child node and continue to walk down
519 r := unicode.ToLower(rune(path[0]))
520 for i, index := range n.indices {
521 // must use recursive approach since both index and
522 // ToLower(index) could exist. We must check both.
523 if r == unicode.ToLower(index) {
524 out, found := n.children[i].findCaseInsensitivePath(path, fixTrailingSlash)
526 return append(ciPath, out...), true
531 // Nothing found. We can recommend to redirect to the same URL
532 // without a trailing slash if a leaf exists for that path
533 found = fixTrailingSlash && path == "/" && n.handlers != nil
540 // find param end (either '/' or path end)
542 for k < len(path) && path[k] != '/' {
546 // add param value to case insensitive path
547 ciPath = append(ciPath, path[:k]...)
549 // we need to go deeper!
551 if len(n.children) > 0 {
558 if fixTrailingSlash && len(path) == k+1 {
564 if n.handlers != nil {
566 } else if fixTrailingSlash && len(n.children) == 1 {
567 // No handle found. Check if a handle for this path + a
568 // trailing slash exists
570 if n.path == "/" && n.handlers != nil {
571 return append(ciPath, '/'), true
577 return append(ciPath, path...), true
580 panic("invalid node type")
583 // We should have reached the node containing the handle.
584 // Check if this node has a handle registered.
585 if n.handlers != nil {
590 // Try to fix the path by adding a trailing slash
591 if fixTrailingSlash {
592 for i := 0; i < len(n.indices); i++ {
593 if n.indices[i] == '/' {
595 if (len(n.path) == 1 && n.handlers != nil) ||
596 (n.nType == catchAll && n.children[0].handlers != nil) {
597 return append(ciPath, '/'), true
608 // Try to fix the path by adding / removing a trailing slash
609 if fixTrailingSlash {
613 if len(path)+1 == len(n.path) && n.path[len(path)] == '/' &&
614 strings.ToLower(path) == strings.ToLower(n.path[:len(path)]) &&
616 return append(ciPath, n.path...), true