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