tree.go 16 KB

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