tree.go

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