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// in the LICENSE file. 4 5package httprouter 6 7import ( 8 "strings" 9 "unicode" 10 "unicode/utf8" 11) 12 13func min(a, b int) int { 14 if a <= b { 15 return a 16 } 17 return b 18} 19 20const maxParamCount uint8 = ^uint8(0) 21 22func countParams(path string) uint8 { 23 var n uint 24 for i := 0; i < len(path); i++ { 25 if path[i] != ':' && path[i] != '*' { 26 continue 27 } 28 n++ 29 } 30 if n >= uint(maxParamCount) { 31 return maxParamCount 32 } 33 34 return uint8(n) 35} 36 37type nodeType uint8 38 39const ( 40 static nodeType = iota // default 41 root 42 param 43 catchAll 44) 45 46type node struct { 47 path string 48 wildChild bool 49 nType nodeType 50 maxParams uint8 51 priority uint32 52 indices string 53 children []*node 54 handle Handle 55} 56 57// increments priority of the given child and reorders if necessary 58func (n *node) incrementChildPrio(pos int) int { 59 n.children[pos].priority++ 60 prio := n.children[pos].priority 61 62 // adjust position (move to front) 63 newPos := pos 64 for newPos > 0 && n.children[newPos-1].priority < prio { 65 // swap node positions 66 n.children[newPos-1], n.children[newPos] = n.children[newPos], n.children[newPos-1] 67 68 newPos-- 69 } 70 71 // build new index char string 72 if newPos != pos { 73 n.indices = n.indices[:newPos] + // unchanged prefix, might be empty 74 n.indices[pos:pos+1] + // the index char we move 75 n.indices[newPos:pos] + n.indices[pos+1:] // rest without char at 'pos' 76 } 77 78 return newPos 79} 80 81// addRoute adds a node with the given handle to the path. 82// Not concurrency-safe! 83func (n *node) addRoute(path string, handle Handle) { 84 fullPath := path 85 n.priority++ 86 numParams := countParams(path) 87 88 // non-empty tree 89 if len(n.path) > 0 || len(n.children) > 0 { 90 walk: 91 for { 92 // Update maxParams of the current node 93 if numParams > n.maxParams { 94 n.maxParams = numParams 95 } 96 97 // Find the longest common prefix. 98 // This also implies that the common prefix contains no ':' or '*' 99 // since the existing key can't contain those chars. 100 i := 0 101 max := min(len(path), len(n.path)) 102 for i < max && path[i] == n.path[i] { 103 i++ 104 } 105 106 // Split edge 107 if i < len(n.path) { 108 child := node{ 109 path: n.path[i:], 110 wildChild: n.wildChild, 111 nType: static, 112 indices: n.indices, 113 children: n.children, 114 handle: n.handle, 115 priority: n.priority - 1, 116 } 117 118 // Update maxParams (max of all children) 119 for i := range child.children { 120 if child.children[i].maxParams > child.maxParams { 121 child.maxParams = child.children[i].maxParams 122 } 123 } 124 125 n.children = []*node{&child} 126 // []byte for proper unicode char conversion, see #65 127 n.indices = string([]byte{n.path[i]}) 128 n.path = path[:i] 129 n.handle = nil 130 n.wildChild = false 131 } 132 133 // Make new node a child of this node 134 if i < len(path) { 135 path = path[i:] 136 137 if n.wildChild { 138 n = n.children[0] 139 n.priority++ 140 141 // Update maxParams of the child node 142 if numParams > n.maxParams { 143 n.maxParams = numParams 144 } 145 numParams-- 146 147 // Check if the wildcard matches 148 if len(path) >= len(n.path) && n.path == path[:len(n.path)] && 149 // Adding a child to a catchAll is not possible 150 n.nType != catchAll && 151 // Check for longer wildcard, e.g. :name and :names 152 (len(n.path) >= len(path) || path[len(n.path)] == '/') { 153 continue walk 154 } else { 155 // Wildcard conflict 156 var pathSeg string 157 if n.nType == catchAll { 158 pathSeg = path 159 } else { 160 pathSeg = strings.SplitN(path, "/", 2)[0] 161 } 162 prefix := fullPath[:strings.Index(fullPath, pathSeg)] + n.path 163 panic("'" + pathSeg + 164 "' in new path '" + fullPath + 165 "' conflicts with existing wildcard '" + n.path + 166 "' in existing prefix '" + prefix + 167 "'") 168 } 169 } 170 171 c := path[0] 172 173 // slash after param 174 if n.nType == param && c == '/' && len(n.children) == 1 { 175 n = n.children[0] 176 n.priority++ 177 continue walk 178 } 179 180 // Check if a child with the next path byte exists 181 for i := 0; i < len(n.indices); i++ { 182 if c == n.indices[i] { 183 i = n.incrementChildPrio(i) 184 n = n.children[i] 185 continue walk 186 } 187 } 188 189 // Otherwise insert it 190 if c != ':' && c != '*' { 191 // []byte for proper unicode char conversion, see #65 192 n.indices += string([]byte{c}) 193 child := &node{ 194 maxParams: numParams, 195 } 196 n.children = append(n.children, child) 197 n.incrementChildPrio(len(n.indices) - 1) 198 n = child 199 } 200 n.insertChild(numParams, path, fullPath, handle) 201 return 202 203 } else if i == len(path) { // Make node a (in-path) leaf 204 if n.handle != nil { 205 panic("a handle is already registered for path '" + fullPath + "'") 206 } 207 n.handle = handle 208 } 209 return 210 } 211 } else { // Empty tree 212 n.insertChild(numParams, path, fullPath, handle) 213 n.nType = root 214 } 215} 216 217func (n *node) insertChild(numParams uint8, path, fullPath string, handle Handle) { 218 var offset int // already handled bytes of the path 219 220 // find prefix until first wildcard (beginning with ':'' or '*'') 221 for i, max := 0, len(path); numParams > 0; i++ { 222 c := path[i] 223 if c != ':' && c != '*' { 224 continue 225 } 226 227 // find wildcard end (either '/' or path end) 228 end := i + 1 229 for end < max && path[end] != '/' { 230 switch path[end] { 231 // the wildcard name must not contain ':' and '*' 232 case ':', '*': 233 panic("only one wildcard per path segment is allowed, has: '" + 234 path[i:] + "' in path '" + fullPath + "'") 235 default: 236 end++ 237 } 238 } 239 240 // check if this Node existing children which would be 241 // unreachable if we insert the wildcard here 242 if len(n.children) > 0 { 243 panic("wildcard route '" + path[i:end] + 244 "' conflicts with existing children in path '" + fullPath + "'") 245 } 246 247 // check if the wildcard has a name 248 if end-i < 2 { 249 panic("wildcards must be named with a non-empty name in path '" + fullPath + "'") 250 } 251 252 if c == ':' { // param 253 // split path at the beginning of the wildcard 254 if i > 0 { 255 n.path = path[offset:i] 256 offset = i 257 } 258 259 child := &node{ 260 nType: param, 261 maxParams: numParams, 262 } 263 n.children = []*node{child} 264 n.wildChild = true 265 n = child 266 n.priority++ 267 numParams-- 268 269 // if the path doesn't end with the wildcard, then there 270 // will be another non-wildcard subpath starting with '/' 271 if end < max { 272 n.path = path[offset:end] 273 offset = end 274 275 child := &node{ 276 maxParams: numParams, 277 priority: 1, 278 } 279 n.children = []*node{child} 280 n = child 281 } 282 283 } else { // catchAll 284 if end != max || numParams > 1 { 285 panic("catch-all routes are only allowed at the end of the path in path '" + fullPath + "'") 286 } 287 288 if len(n.path) > 0 && n.path[len(n.path)-1] == '/' { 289 panic("catch-all conflicts with existing handle for the path segment root in path '" + fullPath + "'") 290 } 291 292 // currently fixed width 1 for '/' 293 i-- 294 if path[i] != '/' { 295 panic("no / before catch-all in path '" + fullPath + "'") 296 } 297 298 n.path = path[offset:i] 299 300 // first node: catchAll node with empty path 301 child := &node{ 302 wildChild: true, 303 nType: catchAll, 304 maxParams: 1, 305 } 306 // update maxParams of the parent node 307 if n.maxParams < 1 { 308 n.maxParams = 1 309 } 310 n.children = []*node{child} 311 n.indices = string(path[i]) 312 n = child 313 n.priority++ 314 315 // second node: node holding the variable 316 child = &node{ 317 path: path[i:], 318 nType: catchAll, 319 maxParams: 1, 320 handle: handle, 321 priority: 1, 322 } 323 n.children = []*node{child} 324 325 return 326 } 327 } 328 329 // insert remaining path part and handle to the leaf 330 n.path = path[offset:] 331 n.handle = handle 332} 333 334// Returns the handle registered with the given path (key). The values of 335// wildcards are saved to a map. 336// If no handle can be found, a TSR (trailing slash redirect) recommendation is 337// made if a handle exists with an extra (without the) trailing slash for the 338// given path. 339func (n *node) getValue(path string) (handle Handle, p Params, tsr bool) { 340walk: // outer loop for walking the tree 341 for { 342 if len(path) > len(n.path) { 343 if path[:len(n.path)] == n.path { 344 path = path[len(n.path):] 345 // If this node does not have a wildcard (param or catchAll) 346 // child, we can just look up the next child node and continue 347 // to walk down the tree 348 if !n.wildChild { 349 c := path[0] 350 for i := 0; i < len(n.indices); i++ { 351 if c == n.indices[i] { 352 n = n.children[i] 353 continue walk 354 } 355 } 356 357 // Nothing found. 358 // We can recommend to redirect to the same URL without a 359 // trailing slash if a leaf exists for that path. 360 tsr = (path == "/" && n.handle != nil) 361 return 362 363 } 364 365 // handle wildcard child 366 n = n.children[0] 367 switch n.nType { 368 case param: 369 // find param end (either '/' or path end) 370 end := 0 371 for end < len(path) && path[end] != '/' { 372 end++ 373 } 374 375 // save param value 376 if p == nil { 377 // lazy allocation 378 p = make(Params, 0, n.maxParams) 379 } 380 i := len(p) 381 p = p[:i+1] // expand slice within preallocated capacity 382 p[i].Key = n.path[1:] 383 p[i].Value = path[:end] 384 385 // we need to go deeper! 386 if end < len(path) { 387 if len(n.children) > 0 { 388 path = path[end:] 389 n = n.children[0] 390 continue walk 391 } 392 393 // ... but we can't 394 tsr = (len(path) == end+1) 395 return 396 } 397 398 if handle = n.handle; handle != nil { 399 return 400 } else if len(n.children) == 1 { 401 // No handle found. Check if a handle for this path + a 402 // trailing slash exists for TSR recommendation 403 n = n.children[0] 404 tsr = (n.path == "/" && n.handle != nil) 405 } 406 407 return 408 409 case catchAll: 410 // save param value 411 if p == nil { 412 // lazy allocation 413 p = make(Params, 0, n.maxParams) 414 } 415 i := len(p) 416 p = p[:i+1] // expand slice within preallocated capacity 417 p[i].Key = n.path[2:] 418 p[i].Value = path 419 420 handle = n.handle 421 return 422 423 default: 424 panic("invalid node type") 425 } 426 } 427 } else if path == n.path { 428 // We should have reached the node containing the handle. 429 // Check if this node has a handle registered. 430 if handle = n.handle; handle != nil { 431 return 432 } 433 434 if path == "/" && n.wildChild && n.nType != root { 435 tsr = true 436 return 437 } 438 439 // No handle found. Check if a handle for this path + a 440 // trailing slash exists for trailing slash recommendation 441 for i := 0; i < len(n.indices); i++ { 442 if n.indices[i] == '/' { 443 n = n.children[i] 444 tsr = (len(n.path) == 1 && n.handle != nil) || 445 (n.nType == catchAll && n.children[0].handle != nil) 446 return 447 } 448 } 449 450 return 451 } 452 453 // Nothing found. We can recommend to redirect to the same URL with an 454 // extra trailing slash if a leaf exists for that path 455 tsr = (path == "/") || 456 (len(n.path) == len(path)+1 && n.path[len(path)] == '/' && 457 path == n.path[:len(n.path)-1] && n.handle != nil) 458 return 459 } 460} 461 462// Makes a case-insensitive lookup of the given path and tries to find a handler. 463// It can optionally also fix trailing slashes. 464// It returns the case-corrected path and a bool indicating whether the lookup 465// was successful. 466func (n *node) findCaseInsensitivePath(path string, fixTrailingSlash bool) (ciPath []byte, found bool) { 467 return n.findCaseInsensitivePathRec( 468 path, 469 make([]byte, 0, len(path)+1), // preallocate enough memory for new path 470 [4]byte{}, // empty rune buffer 471 fixTrailingSlash, 472 ) 473} 474 475// shift bytes in array by n bytes left 476func shiftNRuneBytes(rb [4]byte, n int) [4]byte { 477 switch n { 478 case 0: 479 return rb 480 case 1: 481 return [4]byte{rb[1], rb[2], rb[3], 0} 482 case 2: 483 return [4]byte{rb[2], rb[3]} 484 case 3: 485 return [4]byte{rb[3]} 486 default: 487 return [4]byte{} 488 } 489} 490 491// recursive case-insensitive lookup function used by n.findCaseInsensitivePath 492func (n *node) findCaseInsensitivePathRec(path string, ciPath []byte, rb [4]byte, fixTrailingSlash bool) ([]byte, bool) { 493 npLen := len(n.path) 494 495walk: // outer loop for walking the tree 496 for len(path) >= npLen && (npLen == 0 || strings.EqualFold(path[1:npLen], n.path[1:])) { 497 // add common prefix to result 498 499 oldPath := path 500 path = path[npLen:] 501 ciPath = append(ciPath, n.path...) 502 503 if len(path) > 0 { 504 // If this node does not have a wildcard (param or catchAll) child, 505 // we can just look up the next child node and continue to walk down 506 // the tree 507 if !n.wildChild { 508 // skip rune bytes already processed 509 rb = shiftNRuneBytes(rb, npLen) 510 511 if rb[0] != 0 { 512 // old rune not finished 513 for i := 0; i < len(n.indices); i++ { 514 if n.indices[i] == rb[0] { 515 // continue with child node 516 n = n.children[i] 517 npLen = len(n.path) 518 continue walk 519 } 520 } 521 } else { 522 // process a new rune 523 var rv rune 524 525 // find rune start 526 // runes are up to 4 byte long, 527 // -4 would definitely be another rune 528 var off int 529 for max := min(npLen, 3); off < max; off++ { 530 if i := npLen - off; utf8.RuneStart(oldPath[i]) { 531 // read rune from cached path 532 rv, _ = utf8.DecodeRuneInString(oldPath[i:]) 533 break 534 } 535 } 536 537 // calculate lowercase bytes of current rune 538 lo := unicode.ToLower(rv) 539 utf8.EncodeRune(rb[:], lo) 540 541 // skip already processed bytes 542 rb = shiftNRuneBytes(rb, off) 543 544 for i := 0; i < len(n.indices); i++ { 545 // lowercase matches 546 if n.indices[i] == rb[0] { 547 // must use a recursive approach since both the 548 // uppercase byte and the lowercase byte might exist 549 // as an index 550 if out, found := n.children[i].findCaseInsensitivePathRec( 551 path, ciPath, rb, fixTrailingSlash, 552 ); found { 553 return out, true 554 } 555 break 556 } 557 } 558 559 // if we found no match, the same for the uppercase rune, 560 // if it differs 561 if up := unicode.ToUpper(rv); up != lo { 562 utf8.EncodeRune(rb[:], up) 563 rb = shiftNRuneBytes(rb, off) 564 565 for i, c := 0, rb[0]; i < len(n.indices); i++ { 566 // uppercase matches 567 if n.indices[i] == c { 568 // continue with child node 569 n = n.children[i] 570 npLen = len(n.path) 571 continue walk 572 } 573 } 574 } 575 } 576 577 // Nothing found. We can recommend to redirect to the same URL 578 // without a trailing slash if a leaf exists for that path 579 return ciPath, (fixTrailingSlash && path == "/" && n.handle != nil) 580 } 581 582 n = n.children[0] 583 switch n.nType { 584 case param: 585 // find param end (either '/' or path end) 586 k := 0 587 for k < len(path) && path[k] != '/' { 588 k++ 589 } 590 591 // add param value to case insensitive path 592 ciPath = append(ciPath, path[:k]...) 593 594 // we need to go deeper! 595 if k < len(path) { 596 if len(n.children) > 0 { 597 // continue with child node 598 n = n.children[0] 599 npLen = len(n.path) 600 path = path[k:] 601 continue 602 } 603 604 // ... but we can't 605 if fixTrailingSlash && len(path) == k+1 { 606 return ciPath, true 607 } 608 return ciPath, false 609 } 610 611 if n.handle != nil { 612 return ciPath, true 613 } else if fixTrailingSlash && len(n.children) == 1 { 614 // No handle found. Check if a handle for this path + a 615 // trailing slash exists 616 n = n.children[0] 617 if n.path == "/" && n.handle != nil { 618 return append(ciPath, '/'), true 619 } 620 } 621 return ciPath, false 622 623 case catchAll: 624 return append(ciPath, path...), true 625 626 default: 627 panic("invalid node type") 628 } 629 } else { 630 // We should have reached the node containing the handle. 631 // Check if this node has a handle registered. 632 if n.handle != nil { 633 return ciPath, true 634 } 635 636 // No handle found. 637 // Try to fix the path by adding a trailing slash 638 if fixTrailingSlash { 639 for i := 0; i < len(n.indices); i++ { 640 if n.indices[i] == '/' { 641 n = n.children[i] 642 if (len(n.path) == 1 && n.handle != nil) || 643 (n.nType == catchAll && n.children[0].handle != nil) { 644 return append(ciPath, '/'), true 645 } 646 return ciPath, false 647 } 648 } 649 } 650 return ciPath, false 651 } 652 } 653 654 // Nothing found. 655 // Try to fix the path by adding / removing a trailing slash 656 if fixTrailingSlash { 657 if path == "/" { 658 return ciPath, true 659 } 660 if len(path)+1 == npLen && n.path[len(path)] == '/' && 661 strings.EqualFold(path[1:], n.path[1:len(path)]) && n.handle != nil { 662 return append(ciPath, n.path...), true 663 } 664 } 665 return ciPath, false 666} 667