"Fossies" - the Fresh Open Source Software Archive

Member "gin-1.7.7/tree.go" (24 Nov 2021, 21952 Bytes) of package /linux/www/gin-1.7.7.tar.gz:


As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) Go source code syntax highlighting (style: standard) with prefixed line numbers and code folding option. Alternatively you can here view or download the uninterpreted source code file. See also the latest Fossies "Diffs" side-by-side code changes report for "tree.go": 1.7.6_vs_1.7.7.

    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     strSlash = []byte("/")
   21 )
   22 
   23 // Param is a single URL parameter, consisting of a key and a value.
   24 type Param struct {
   25     Key   string
   26     Value string
   27 }
   28 
   29 // Params is a Param-slice, as returned by the router.
   30 // The slice is ordered, the first URL parameter is also the first slice value.
   31 // It is therefore safe to read values by the index.
   32 type Params []Param
   33 
   34 // Get returns the value of the first Param which key matches the given name.
   35 // If no matching Param is found, an empty string is returned.
   36 func (ps Params) Get(name string) (string, bool) {
   37     for _, entry := range ps {
   38         if entry.Key == name {
   39             return entry.Value, true
   40         }
   41     }
   42     return "", false
   43 }
   44 
   45 // ByName returns the value of the first Param which key matches the given name.
   46 // If no matching Param is found, an empty string is returned.
   47 func (ps Params) ByName(name string) (va string) {
   48     va, _ = ps.Get(name)
   49     return
   50 }
   51 
   52 type methodTree struct {
   53     method string
   54     root   *node
   55 }
   56 
   57 type methodTrees []methodTree
   58 
   59 func (trees methodTrees) get(method string) *node {
   60     for _, tree := range trees {
   61         if tree.method == method {
   62             return tree.root
   63         }
   64     }
   65     return nil
   66 }
   67 
   68 func min(a, b int) int {
   69     if a <= b {
   70         return a
   71     }
   72     return b
   73 }
   74 
   75 func longestCommonPrefix(a, b string) int {
   76     i := 0
   77     max := min(len(a), len(b))
   78     for i < max && a[i] == b[i] {
   79         i++
   80     }
   81     return i
   82 }
   83 
   84 // addChild will add a child node, keeping wildcards at the end
   85 func (n *node) addChild(child *node) {
   86     if n.wildChild && len(n.children) > 0 {
   87         wildcardChild := n.children[len(n.children)-1]
   88         n.children = append(n.children[:len(n.children)-1], child, wildcardChild)
   89     } else {
   90         n.children = append(n.children, child)
   91     }
   92 }
   93 
   94 func countParams(path string) uint16 {
   95     var n uint16
   96     s := bytesconv.StringToBytes(path)
   97     n += uint16(bytes.Count(s, strColon))
   98     n += uint16(bytes.Count(s, strStar))
   99     return n
  100 }
  101 
  102 func countSections(path string) uint16 {
  103     s := bytesconv.StringToBytes(path)
  104     return uint16(bytes.Count(s, strSlash))
  105 }
  106 
  107 type nodeType uint8
  108 
  109 const (
  110     static nodeType = iota // default
  111     root
  112     param
  113     catchAll
  114 )
  115 
  116 type node struct {
  117     path      string
  118     indices   string
  119     wildChild bool
  120     nType     nodeType
  121     priority  uint32
  122     children  []*node // child nodes, at most 1 :param style node at the end of the array
  123     handlers  HandlersChain
  124     fullPath  string
  125 }
  126 
  127 // Increments priority of the given child and reorders if necessary
  128 func (n *node) incrementChildPrio(pos int) int {
  129     cs := n.children
  130     cs[pos].priority++
  131     prio := cs[pos].priority
  132 
  133     // Adjust position (move to front)
  134     newPos := pos
  135     for ; newPos > 0 && cs[newPos-1].priority < prio; newPos-- {
  136         // Swap node positions
  137         cs[newPos-1], cs[newPos] = cs[newPos], cs[newPos-1]
  138     }
  139 
  140     // Build new index char string
  141     if newPos != pos {
  142         n.indices = n.indices[:newPos] + // Unchanged prefix, might be empty
  143             n.indices[pos:pos+1] + // The index char we move
  144             n.indices[newPos:pos] + n.indices[pos+1:] // Rest without char at 'pos'
  145     }
  146 
  147     return newPos
  148 }
  149 
  150 // addRoute adds a node with the given handle to the path.
  151 // Not concurrency-safe!
  152 func (n *node) addRoute(path string, handlers HandlersChain) {
  153     fullPath := path
  154     n.priority++
  155 
  156     // Empty tree
  157     if len(n.path) == 0 && len(n.children) == 0 {
  158         n.insertChild(path, fullPath, handlers)
  159         n.nType = root
  160         return
  161     }
  162 
  163     parentFullPathIndex := 0
  164 
  165 walk:
  166     for {
  167         // Find the longest common prefix.
  168         // This also implies that the common prefix contains no ':' or '*'
  169         // since the existing key can't contain those chars.
  170         i := longestCommonPrefix(path, n.path)
  171 
  172         // Split edge
  173         if i < len(n.path) {
  174             child := node{
  175                 path:      n.path[i:],
  176                 wildChild: n.wildChild,
  177                 indices:   n.indices,
  178                 children:  n.children,
  179                 handlers:  n.handlers,
  180                 priority:  n.priority - 1,
  181                 fullPath:  n.fullPath,
  182             }
  183 
  184             n.children = []*node{&child}
  185             // []byte for proper unicode char conversion, see #65
  186             n.indices = bytesconv.BytesToString([]byte{n.path[i]})
  187             n.path = path[:i]
  188             n.handlers = nil
  189             n.wildChild = false
  190             n.fullPath = fullPath[:parentFullPathIndex+i]
  191         }
  192 
  193         // Make new node a child of this node
  194         if i < len(path) {
  195             path = path[i:]
  196             c := path[0]
  197 
  198             // '/' after param
  199             if n.nType == param && c == '/' && len(n.children) == 1 {
  200                 parentFullPathIndex += len(n.path)
  201                 n = n.children[0]
  202                 n.priority++
  203                 continue walk
  204             }
  205 
  206             // Check if a child with the next path byte exists
  207             for i, max := 0, len(n.indices); i < max; i++ {
  208                 if c == n.indices[i] {
  209                     parentFullPathIndex += len(n.path)
  210                     i = n.incrementChildPrio(i)
  211                     n = n.children[i]
  212                     continue walk
  213                 }
  214             }
  215 
  216             // Otherwise insert it
  217             if c != ':' && c != '*' && n.nType != catchAll {
  218                 // []byte for proper unicode char conversion, see #65
  219                 n.indices += bytesconv.BytesToString([]byte{c})
  220                 child := &node{
  221                     fullPath: fullPath,
  222                 }
  223                 n.addChild(child)
  224                 n.incrementChildPrio(len(n.indices) - 1)
  225                 n = child
  226             } else if n.wildChild {
  227                 // inserting a wildcard node, need to check if it conflicts with the existing wildcard
  228                 n = n.children[len(n.children)-1]
  229                 n.priority++
  230 
  231                 // Check if the wildcard matches
  232                 if len(path) >= len(n.path) && n.path == path[:len(n.path)] &&
  233                     // Adding a child to a catchAll is not possible
  234                     n.nType != catchAll &&
  235                     // Check for longer wildcard, e.g. :name and :names
  236                     (len(n.path) >= len(path) || path[len(n.path)] == '/') {
  237                     continue walk
  238                 }
  239 
  240                 // Wildcard conflict
  241                 pathSeg := path
  242                 if n.nType != catchAll {
  243                     pathSeg = strings.SplitN(pathSeg, "/", 2)[0]
  244                 }
  245                 prefix := fullPath[:strings.Index(fullPath, pathSeg)] + n.path
  246                 panic("'" + pathSeg +
  247                     "' in new path '" + fullPath +
  248                     "' conflicts with existing wildcard '" + n.path +
  249                     "' in existing prefix '" + prefix +
  250                     "'")
  251             }
  252 
  253             n.insertChild(path, fullPath, handlers)
  254             return
  255         }
  256 
  257         // Otherwise add handle to current node
  258         if n.handlers != nil {
  259             panic("handlers are already registered for path '" + fullPath + "'")
  260         }
  261         n.handlers = handlers
  262         n.fullPath = fullPath
  263         return
  264     }
  265 }
  266 
  267 // Search for a wildcard segment and check the name for invalid characters.
  268 // Returns -1 as index, if no wildcard was found.
  269 func findWildcard(path string) (wildcard string, i int, valid bool) {
  270     // Find start
  271     for start, c := range []byte(path) {
  272         // A wildcard starts with ':' (param) or '*' (catch-all)
  273         if c != ':' && c != '*' {
  274             continue
  275         }
  276 
  277         // Find end and check for invalid characters
  278         valid = true
  279         for end, c := range []byte(path[start+1:]) {
  280             switch c {
  281             case '/':
  282                 return path[start : start+1+end], start, valid
  283             case ':', '*':
  284                 valid = false
  285             }
  286         }
  287         return path[start:], start, valid
  288     }
  289     return "", -1, false
  290 }
  291 
  292 func (n *node) insertChild(path string, fullPath string, handlers HandlersChain) {
  293     for {
  294         // Find prefix until first wildcard
  295         wildcard, i, valid := findWildcard(path)
  296         if i < 0 { // No wildcard found
  297             break
  298         }
  299 
  300         // The wildcard name must not contain ':' and '*'
  301         if !valid {
  302             panic("only one wildcard per path segment is allowed, has: '" +
  303                 wildcard + "' in path '" + fullPath + "'")
  304         }
  305 
  306         // check if the wildcard has a name
  307         if len(wildcard) < 2 {
  308             panic("wildcards must be named with a non-empty name in path '" + fullPath + "'")
  309         }
  310 
  311         if wildcard[0] == ':' { // param
  312             if i > 0 {
  313                 // Insert prefix before the current wildcard
  314                 n.path = path[:i]
  315                 path = path[i:]
  316             }
  317 
  318             child := &node{
  319                 nType:    param,
  320                 path:     wildcard,
  321                 fullPath: fullPath,
  322             }
  323             n.addChild(child)
  324             n.wildChild = true
  325             n = child
  326             n.priority++
  327 
  328             // if the path doesn't end with the wildcard, then there
  329             // will be another non-wildcard subpath starting with '/'
  330             if len(wildcard) < len(path) {
  331                 path = path[len(wildcard):]
  332 
  333                 child := &node{
  334                     priority: 1,
  335                     fullPath: fullPath,
  336                 }
  337                 n.addChild(child)
  338                 n = child
  339                 continue
  340             }
  341 
  342             // Otherwise we're done. Insert the handle in the new leaf
  343             n.handlers = handlers
  344             return
  345         }
  346 
  347         // catchAll
  348         if i+len(wildcard) != len(path) {
  349             panic("catch-all routes are only allowed at the end of the path in path '" + fullPath + "'")
  350         }
  351 
  352         if len(n.path) > 0 && n.path[len(n.path)-1] == '/' {
  353             panic("catch-all conflicts with existing handle for the path segment root in path '" + fullPath + "'")
  354         }
  355 
  356         // currently fixed width 1 for '/'
  357         i--
  358         if path[i] != '/' {
  359             panic("no / before catch-all in path '" + fullPath + "'")
  360         }
  361 
  362         n.path = path[:i]
  363 
  364         // First node: catchAll node with empty path
  365         child := &node{
  366             wildChild: true,
  367             nType:     catchAll,
  368             fullPath:  fullPath,
  369         }
  370 
  371         n.addChild(child)
  372         n.indices = string('/')
  373         n = child
  374         n.priority++
  375 
  376         // second node: node holding the variable
  377         child = &node{
  378             path:     path[i:],
  379             nType:    catchAll,
  380             handlers: handlers,
  381             priority: 1,
  382             fullPath: fullPath,
  383         }
  384         n.children = []*node{child}
  385 
  386         return
  387     }
  388 
  389     // If no wildcard was found, simply insert the path and handle
  390     n.path = path
  391     n.handlers = handlers
  392     n.fullPath = fullPath
  393 }
  394 
  395 // nodeValue holds return values of (*Node).getValue method
  396 type nodeValue struct {
  397     handlers HandlersChain
  398     params   *Params
  399     tsr      bool
  400     fullPath string
  401 }
  402 
  403 type skippedNode struct {
  404     path        string
  405     node        *node
  406     paramsCount int16
  407 }
  408 
  409 // Returns the handle registered with the given path (key). The values of
  410 // wildcards are saved to a map.
  411 // If no handle can be found, a TSR (trailing slash redirect) recommendation is
  412 // made if a handle exists with an extra (without the) trailing slash for the
  413 // given path.
  414 func (n *node) getValue(path string, params *Params, skippedNodes *[]skippedNode, unescape bool) (value nodeValue) {
  415     var globalParamsCount int16
  416 
  417 walk: // Outer loop for walking the tree
  418     for {
  419         prefix := n.path
  420         if len(path) > len(prefix) {
  421             if path[:len(prefix)] == prefix {
  422                 path = path[len(prefix):]
  423 
  424                 // Try all the non-wildcard children first by matching the indices
  425                 idxc := path[0]
  426                 for i, c := range []byte(n.indices) {
  427                     if c == idxc {
  428                         //  strings.HasPrefix(n.children[len(n.children)-1].path, ":") == n.wildChild
  429                         if n.wildChild {
  430                             index := len(*skippedNodes)
  431                             *skippedNodes = (*skippedNodes)[:index+1]
  432                             (*skippedNodes)[index] = skippedNode{
  433                                 path: prefix + path,
  434                                 node: &node{
  435                                     path:      n.path,
  436                                     wildChild: n.wildChild,
  437                                     nType:     n.nType,
  438                                     priority:  n.priority,
  439                                     children:  n.children,
  440                                     handlers:  n.handlers,
  441                                     fullPath:  n.fullPath,
  442                                 },
  443                                 paramsCount: globalParamsCount,
  444                             }
  445                         }
  446 
  447                         n = n.children[i]
  448                         continue walk
  449                     }
  450                 }
  451 
  452                 if !n.wildChild {
  453                     // If the path at the end of the loop is not equal to '/' and the current node has no child nodes
  454                     // the current node needs to roll back to last vaild skippedNode
  455                     if path != "/" {
  456                         for l := len(*skippedNodes); l > 0; {
  457                             skippedNode := (*skippedNodes)[l-1]
  458                             *skippedNodes = (*skippedNodes)[:l-1]
  459                             if strings.HasSuffix(skippedNode.path, path) {
  460                                 path = skippedNode.path
  461                                 n = skippedNode.node
  462                                 if value.params != nil {
  463                                     *value.params = (*value.params)[:skippedNode.paramsCount]
  464                                 }
  465                                 globalParamsCount = skippedNode.paramsCount
  466                                 continue walk
  467                             }
  468                         }
  469                     }
  470 
  471                     // Nothing found.
  472                     // We can recommend to redirect to the same URL without a
  473                     // trailing slash if a leaf exists for that path.
  474                     value.tsr = path == "/" && n.handlers != nil
  475                     return
  476                 }
  477 
  478                 // Handle wildcard child, which is always at the end of the array
  479                 n = n.children[len(n.children)-1]
  480                 globalParamsCount++
  481 
  482                 switch n.nType {
  483                 case param:
  484                     // fix truncate the parameter
  485                     // tree_test.go  line: 204
  486 
  487                     // Find param end (either '/' or path end)
  488                     end := 0
  489                     for end < len(path) && path[end] != '/' {
  490                         end++
  491                     }
  492 
  493                     // Save param value
  494                     if params != nil && cap(*params) > 0 {
  495                         if value.params == nil {
  496                             value.params = params
  497                         }
  498                         // Expand slice within preallocated capacity
  499                         i := len(*value.params)
  500                         *value.params = (*value.params)[:i+1]
  501                         val := path[:end]
  502                         if unescape {
  503                             if v, err := url.QueryUnescape(val); err == nil {
  504                                 val = v
  505                             }
  506                         }
  507                         (*value.params)[i] = Param{
  508                             Key:   n.path[1:],
  509                             Value: val,
  510                         }
  511                     }
  512 
  513                     // we need to go deeper!
  514                     if end < len(path) {
  515                         if len(n.children) > 0 {
  516                             path = path[end:]
  517                             n = n.children[0]
  518                             continue walk
  519                         }
  520 
  521                         // ... but we can't
  522                         value.tsr = len(path) == end+1
  523                         return
  524                     }
  525 
  526                     if value.handlers = n.handlers; value.handlers != nil {
  527                         value.fullPath = n.fullPath
  528                         return
  529                     }
  530                     if len(n.children) == 1 {
  531                         // No handle found. Check if a handle for this path + a
  532                         // trailing slash exists for TSR recommendation
  533                         n = n.children[0]
  534                         value.tsr = n.path == "/" && n.handlers != nil
  535                     }
  536                     return
  537 
  538                 case catchAll:
  539                     // Save param value
  540                     if params != nil {
  541                         if value.params == nil {
  542                             value.params = params
  543                         }
  544                         // Expand slice within preallocated capacity
  545                         i := len(*value.params)
  546                         *value.params = (*value.params)[:i+1]
  547                         val := path
  548                         if unescape {
  549                             if v, err := url.QueryUnescape(path); err == nil {
  550                                 val = v
  551                             }
  552                         }
  553                         (*value.params)[i] = Param{
  554                             Key:   n.path[2:],
  555                             Value: val,
  556                         }
  557                     }
  558 
  559                     value.handlers = n.handlers
  560                     value.fullPath = n.fullPath
  561                     return
  562 
  563                 default:
  564                     panic("invalid node type")
  565                 }
  566             }
  567         }
  568 
  569         if path == prefix {
  570             // If the current path does not equal '/' and the node does not have a registered handle and the most recently matched node has a child node
  571             // the current node needs to roll back to last vaild skippedNode
  572             if n.handlers == nil && path != "/" {
  573                 for l := len(*skippedNodes); l > 0; {
  574                     skippedNode := (*skippedNodes)[l-1]
  575                     *skippedNodes = (*skippedNodes)[:l-1]
  576                     if strings.HasSuffix(skippedNode.path, path) {
  577                         path = skippedNode.path
  578                         n = skippedNode.node
  579                         if value.params != nil {
  580                             *value.params = (*value.params)[:skippedNode.paramsCount]
  581                         }
  582                         globalParamsCount = skippedNode.paramsCount
  583                         continue walk
  584                     }
  585                 }
  586                 //  n = latestNode.children[len(latestNode.children)-1]
  587             }
  588             // We should have reached the node containing the handle.
  589             // Check if this node has a handle registered.
  590             if value.handlers = n.handlers; value.handlers != nil {
  591                 value.fullPath = n.fullPath
  592                 return
  593             }
  594 
  595             // If there is no handle for this route, but this route has a
  596             // wildcard child, there must be a handle for this path with an
  597             // additional trailing slash
  598             if path == "/" && n.wildChild && n.nType != root {
  599                 value.tsr = true
  600                 return
  601             }
  602 
  603             // No handle found. Check if a handle for this path + a
  604             // trailing slash exists for trailing slash recommendation
  605             for i, c := range []byte(n.indices) {
  606                 if c == '/' {
  607                     n = n.children[i]
  608                     value.tsr = (len(n.path) == 1 && n.handlers != nil) ||
  609                         (n.nType == catchAll && n.children[0].handlers != nil)
  610                     return
  611                 }
  612             }
  613 
  614             return
  615         }
  616 
  617         // Nothing found. We can recommend to redirect to the same URL with an
  618         // extra trailing slash if a leaf exists for that path
  619         value.tsr = path == "/" ||
  620             (len(prefix) == len(path)+1 && prefix[len(path)] == '/' &&
  621                 path == prefix[:len(prefix)-1] && n.handlers != nil)
  622 
  623         // roll back to last valid skippedNode
  624         if !value.tsr && path != "/" {
  625             for l := len(*skippedNodes); l > 0; {
  626                 skippedNode := (*skippedNodes)[l-1]
  627                 *skippedNodes = (*skippedNodes)[:l-1]
  628                 if strings.HasSuffix(skippedNode.path, path) {
  629                     path = skippedNode.path
  630                     n = skippedNode.node
  631                     if value.params != nil {
  632                         *value.params = (*value.params)[:skippedNode.paramsCount]
  633                     }
  634                     globalParamsCount = skippedNode.paramsCount
  635                     continue walk
  636                 }
  637             }
  638         }
  639 
  640         return
  641     }
  642 }
  643 
  644 // Makes a case-insensitive lookup of the given path and tries to find a handler.
  645 // It can optionally also fix trailing slashes.
  646 // It returns the case-corrected path and a bool indicating whether the lookup
  647 // was successful.
  648 func (n *node) findCaseInsensitivePath(path string, fixTrailingSlash bool) ([]byte, bool) {
  649     const stackBufSize = 128
  650 
  651     // Use a static sized buffer on the stack in the common case.
  652     // If the path is too long, allocate a buffer on the heap instead.
  653     buf := make([]byte, 0, stackBufSize)
  654     if length := len(path) + 1; length > stackBufSize {
  655         buf = make([]byte, 0, length)
  656     }
  657 
  658     ciPath := n.findCaseInsensitivePathRec(
  659         path,
  660         buf,       // Preallocate enough memory for new path
  661         [4]byte{}, // Empty rune buffer
  662         fixTrailingSlash,
  663     )
  664 
  665     return ciPath, ciPath != nil
  666 }
  667 
  668 // Shift bytes in array by n bytes left
  669 func shiftNRuneBytes(rb [4]byte, n int) [4]byte {
  670     switch n {
  671     case 0:
  672         return rb
  673     case 1:
  674         return [4]byte{rb[1], rb[2], rb[3], 0}
  675     case 2:
  676         return [4]byte{rb[2], rb[3]}
  677     case 3:
  678         return [4]byte{rb[3]}
  679     default:
  680         return [4]byte{}
  681     }
  682 }
  683 
  684 // Recursive case-insensitive lookup function used by n.findCaseInsensitivePath
  685 func (n *node) findCaseInsensitivePathRec(path string, ciPath []byte, rb [4]byte, fixTrailingSlash bool) []byte {
  686     npLen := len(n.path)
  687 
  688 walk: // Outer loop for walking the tree
  689     for len(path) >= npLen && (npLen == 0 || strings.EqualFold(path[1:npLen], n.path[1:])) {
  690         // Add common prefix to result
  691         oldPath := path
  692         path = path[npLen:]
  693         ciPath = append(ciPath, n.path...)
  694 
  695         if len(path) == 0 {
  696             // We should have reached the node containing the handle.
  697             // Check if this node has a handle registered.
  698             if n.handlers != nil {
  699                 return ciPath
  700             }
  701 
  702             // No handle found.
  703             // Try to fix the path by adding a trailing slash
  704             if fixTrailingSlash {
  705                 for i, c := range []byte(n.indices) {
  706                     if c == '/' {
  707                         n = n.children[i]
  708                         if (len(n.path) == 1 && n.handlers != nil) ||
  709                             (n.nType == catchAll && n.children[0].handlers != nil) {
  710                             return append(ciPath, '/')
  711                         }
  712                         return nil
  713                     }
  714                 }
  715             }
  716             return nil
  717         }
  718 
  719         // If this node does not have a wildcard (param or catchAll) child,
  720         // we can just look up the next child node and continue to walk down
  721         // the tree
  722         if !n.wildChild {
  723             // Skip rune bytes already processed
  724             rb = shiftNRuneBytes(rb, npLen)
  725 
  726             if rb[0] != 0 {
  727                 // Old rune not finished
  728                 idxc := rb[0]
  729                 for i, c := range []byte(n.indices) {
  730                     if c == idxc {
  731                         // continue with child node
  732                         n = n.children[i]
  733                         npLen = len(n.path)
  734                         continue walk
  735                     }
  736                 }
  737             } else {
  738                 // Process a new rune
  739                 var rv rune
  740 
  741                 // Find rune start.
  742                 // Runes are up to 4 byte long,
  743                 // -4 would definitely be another rune.
  744                 var off int
  745                 for max := min(npLen, 3); off < max; off++ {
  746                     if i := npLen - off; utf8.RuneStart(oldPath[i]) {
  747                         // read rune from cached path
  748                         rv, _ = utf8.DecodeRuneInString(oldPath[i:])
  749                         break
  750                     }
  751                 }
  752 
  753                 // Calculate lowercase bytes of current rune
  754                 lo := unicode.ToLower(rv)
  755                 utf8.EncodeRune(rb[:], lo)
  756 
  757                 // Skip already processed bytes
  758                 rb = shiftNRuneBytes(rb, off)
  759 
  760                 idxc := rb[0]
  761                 for i, c := range []byte(n.indices) {
  762                     // Lowercase matches
  763                     if c == idxc {
  764                         // must use a recursive approach since both the
  765                         // uppercase byte and the lowercase byte might exist
  766                         // as an index
  767                         if out := n.children[i].findCaseInsensitivePathRec(
  768                             path, ciPath, rb, fixTrailingSlash,
  769                         ); out != nil {
  770                             return out
  771                         }
  772                         break
  773                     }
  774                 }
  775 
  776                 // If we found no match, the same for the uppercase rune,
  777                 // if it differs
  778                 if up := unicode.ToUpper(rv); up != lo {
  779                     utf8.EncodeRune(rb[:], up)
  780                     rb = shiftNRuneBytes(rb, off)
  781 
  782                     idxc := rb[0]
  783                     for i, c := range []byte(n.indices) {
  784                         // Uppercase matches
  785                         if c == idxc {
  786                             // Continue with child node
  787                             n = n.children[i]
  788                             npLen = len(n.path)
  789                             continue walk
  790                         }
  791                     }
  792                 }
  793             }
  794 
  795             // Nothing found. We can recommend to redirect to the same URL
  796             // without a trailing slash if a leaf exists for that path
  797             if fixTrailingSlash && path == "/" && n.handlers != nil {
  798                 return ciPath
  799             }
  800             return nil
  801         }
  802 
  803         n = n.children[0]
  804         switch n.nType {
  805         case param:
  806             // Find param end (either '/' or path end)
  807             end := 0
  808             for end < len(path) && path[end] != '/' {
  809                 end++
  810             }
  811 
  812             // Add param value to case insensitive path
  813             ciPath = append(ciPath, path[:end]...)
  814 
  815             // We need to go deeper!
  816             if end < len(path) {
  817                 if len(n.children) > 0 {
  818                     // Continue with child node
  819                     n = n.children[0]
  820                     npLen = len(n.path)
  821                     path = path[end:]
  822                     continue
  823                 }
  824 
  825                 // ... but we can't
  826                 if fixTrailingSlash && len(path) == end+1 {
  827                     return ciPath
  828                 }
  829                 return nil
  830             }
  831 
  832             if n.handlers != nil {
  833                 return ciPath
  834             }
  835 
  836             if fixTrailingSlash && len(n.children) == 1 {
  837                 // No handle found. Check if a handle for this path + a
  838                 // trailing slash exists
  839                 n = n.children[0]
  840                 if n.path == "/" && n.handlers != nil {
  841                     return append(ciPath, '/')
  842                 }
  843             }
  844 
  845             return nil
  846 
  847         case catchAll:
  848             return append(ciPath, path...)
  849 
  850         default:
  851             panic("invalid node type")
  852         }
  853     }
  854 
  855     // Nothing found.
  856     // Try to fix the path by adding / removing a trailing slash
  857     if fixTrailingSlash {
  858         if path == "/" {
  859             return ciPath
  860         }
  861         if len(path)+1 == npLen && n.path[len(path)] == '/' &&
  862             strings.EqualFold(path[1:], n.path[1:len(path)]) && n.handlers != nil {
  863             return append(ciPath, n.path...)
  864         }
  865     }
  866     return nil
  867 }