tree.go 10 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390
  1. // Copyright 2015 The Macaron Authors
  2. //
  3. // Licensed under the Apache License, Version 2.0 (the "License"): you may
  4. // not use this file except in compliance with the License. You may obtain
  5. // a copy of the License at
  6. //
  7. // http://www.apache.org/licenses/LICENSE-2.0
  8. //
  9. // Unless required by applicable law or agreed to in writing, software
  10. // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
  11. // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
  12. // License for the specific language governing permissions and limitations
  13. // under the License.
  14. package macaron
  15. import (
  16. "regexp"
  17. "strings"
  18. "github.com/Unknwon/com"
  19. )
  20. type patternType int8
  21. const (
  22. _PATTERN_STATIC patternType = iota // /home
  23. _PATTERN_REGEXP // /:id([0-9]+)
  24. _PATTERN_PATH_EXT // /*.*
  25. _PATTERN_HOLDER // /:user
  26. _PATTERN_MATCH_ALL // /*
  27. )
  28. // Leaf represents a leaf route information.
  29. type Leaf struct {
  30. parent *Tree
  31. typ patternType
  32. pattern string
  33. rawPattern string // Contains wildcard instead of regexp
  34. wildcards []string
  35. reg *regexp.Regexp
  36. optional bool
  37. handle Handle
  38. }
  39. var wildcardPattern = regexp.MustCompile(`:[a-zA-Z0-9]+`)
  40. func isSpecialRegexp(pattern, regStr string, pos []int) bool {
  41. return len(pattern) >= pos[1]+len(regStr) && pattern[pos[1]:pos[1]+len(regStr)] == regStr
  42. }
  43. // getNextWildcard tries to find next wildcard and update pattern with corresponding regexp.
  44. func getNextWildcard(pattern string) (wildcard, _ string) {
  45. pos := wildcardPattern.FindStringIndex(pattern)
  46. if pos == nil {
  47. return "", pattern
  48. }
  49. wildcard = pattern[pos[0]:pos[1]]
  50. // Reach last character or no regexp is given.
  51. if len(pattern) == pos[1] {
  52. return wildcard, strings.Replace(pattern, wildcard, `(.+)`, 1)
  53. } else if pattern[pos[1]] != '(' {
  54. switch {
  55. case isSpecialRegexp(pattern, ":int", pos):
  56. pattern = strings.Replace(pattern, ":int", "([0-9]+)", 1)
  57. case isSpecialRegexp(pattern, ":string", pos):
  58. pattern = strings.Replace(pattern, ":string", "([\\w]+)", 1)
  59. default:
  60. return wildcard, strings.Replace(pattern, wildcard, `(.+)`, 1)
  61. }
  62. }
  63. // Cut out placeholder directly.
  64. return wildcard, pattern[:pos[0]] + pattern[pos[1]:]
  65. }
  66. func getWildcards(pattern string) (string, []string) {
  67. wildcards := make([]string, 0, 2)
  68. // Keep getting next wildcard until nothing is left.
  69. var wildcard string
  70. for {
  71. wildcard, pattern = getNextWildcard(pattern)
  72. if len(wildcard) > 0 {
  73. wildcards = append(wildcards, wildcard)
  74. } else {
  75. break
  76. }
  77. }
  78. return pattern, wildcards
  79. }
  80. // getRawPattern removes all regexp but keeps wildcards for building URL path.
  81. func getRawPattern(rawPattern string) string {
  82. rawPattern = strings.Replace(rawPattern, ":int", "", -1)
  83. rawPattern = strings.Replace(rawPattern, ":string", "", -1)
  84. for {
  85. startIdx := strings.Index(rawPattern, "(")
  86. if startIdx == -1 {
  87. break
  88. }
  89. closeIdx := strings.Index(rawPattern, ")")
  90. if closeIdx > -1 {
  91. rawPattern = rawPattern[:startIdx] + rawPattern[closeIdx+1:]
  92. }
  93. }
  94. return rawPattern
  95. }
  96. func checkPattern(pattern string) (typ patternType, rawPattern string, wildcards []string, reg *regexp.Regexp) {
  97. pattern = strings.TrimLeft(pattern, "?")
  98. rawPattern = getRawPattern(pattern)
  99. if pattern == "*" {
  100. typ = _PATTERN_MATCH_ALL
  101. } else if pattern == "*.*" {
  102. typ = _PATTERN_PATH_EXT
  103. } else if strings.Contains(pattern, ":") {
  104. typ = _PATTERN_REGEXP
  105. pattern, wildcards = getWildcards(pattern)
  106. if pattern == "(.+)" {
  107. typ = _PATTERN_HOLDER
  108. } else {
  109. reg = regexp.MustCompile(pattern)
  110. }
  111. }
  112. return typ, rawPattern, wildcards, reg
  113. }
  114. func NewLeaf(parent *Tree, pattern string, handle Handle) *Leaf {
  115. typ, rawPattern, wildcards, reg := checkPattern(pattern)
  116. optional := false
  117. if len(pattern) > 0 && pattern[0] == '?' {
  118. optional = true
  119. }
  120. return &Leaf{parent, typ, pattern, rawPattern, wildcards, reg, optional, handle}
  121. }
  122. // URLPath build path part of URL by given pair values.
  123. func (l *Leaf) URLPath(pairs ...string) string {
  124. if len(pairs)%2 != 0 {
  125. panic("number of pairs does not match")
  126. }
  127. urlPath := l.rawPattern
  128. parent := l.parent
  129. for parent != nil {
  130. urlPath = parent.rawPattern + "/" + urlPath
  131. parent = parent.parent
  132. }
  133. for i := 0; i < len(pairs); i += 2 {
  134. if len(pairs[i]) == 0 {
  135. panic("pair value cannot be empty: " + com.ToStr(i))
  136. } else if pairs[i][0] != ':' && pairs[i] != "*" && pairs[i] != "*.*" {
  137. pairs[i] = ":" + pairs[i]
  138. }
  139. urlPath = strings.Replace(urlPath, pairs[i], pairs[i+1], 1)
  140. }
  141. return urlPath
  142. }
  143. // Tree represents a router tree in Macaron.
  144. type Tree struct {
  145. parent *Tree
  146. typ patternType
  147. pattern string
  148. rawPattern string
  149. wildcards []string
  150. reg *regexp.Regexp
  151. subtrees []*Tree
  152. leaves []*Leaf
  153. }
  154. func NewSubtree(parent *Tree, pattern string) *Tree {
  155. typ, rawPattern, wildcards, reg := checkPattern(pattern)
  156. return &Tree{parent, typ, pattern, rawPattern, wildcards, reg, make([]*Tree, 0, 5), make([]*Leaf, 0, 5)}
  157. }
  158. func NewTree() *Tree {
  159. return NewSubtree(nil, "")
  160. }
  161. func (t *Tree) addLeaf(pattern string, handle Handle) *Leaf {
  162. for i := 0; i < len(t.leaves); i++ {
  163. if t.leaves[i].pattern == pattern {
  164. return t.leaves[i]
  165. }
  166. }
  167. leaf := NewLeaf(t, pattern, handle)
  168. // Add exact same leaf to grandparent/parent level without optional.
  169. if leaf.optional {
  170. parent := leaf.parent
  171. if parent.parent != nil {
  172. parent.parent.addLeaf(parent.pattern, handle)
  173. } else {
  174. parent.addLeaf("", handle) // Root tree can add as empty pattern.
  175. }
  176. }
  177. i := 0
  178. for ; i < len(t.leaves); i++ {
  179. if leaf.typ < t.leaves[i].typ {
  180. break
  181. }
  182. }
  183. if i == len(t.leaves) {
  184. t.leaves = append(t.leaves, leaf)
  185. } else {
  186. t.leaves = append(t.leaves[:i], append([]*Leaf{leaf}, t.leaves[i:]...)...)
  187. }
  188. return leaf
  189. }
  190. func (t *Tree) addSubtree(segment, pattern string, handle Handle) *Leaf {
  191. for i := 0; i < len(t.subtrees); i++ {
  192. if t.subtrees[i].pattern == segment {
  193. return t.subtrees[i].addNextSegment(pattern, handle)
  194. }
  195. }
  196. subtree := NewSubtree(t, segment)
  197. i := 0
  198. for ; i < len(t.subtrees); i++ {
  199. if subtree.typ < t.subtrees[i].typ {
  200. break
  201. }
  202. }
  203. if i == len(t.subtrees) {
  204. t.subtrees = append(t.subtrees, subtree)
  205. } else {
  206. t.subtrees = append(t.subtrees[:i], append([]*Tree{subtree}, t.subtrees[i:]...)...)
  207. }
  208. return subtree.addNextSegment(pattern, handle)
  209. }
  210. func (t *Tree) addNextSegment(pattern string, handle Handle) *Leaf {
  211. pattern = strings.TrimPrefix(pattern, "/")
  212. i := strings.Index(pattern, "/")
  213. if i == -1 {
  214. return t.addLeaf(pattern, handle)
  215. }
  216. return t.addSubtree(pattern[:i], pattern[i+1:], handle)
  217. }
  218. func (t *Tree) Add(pattern string, handle Handle) *Leaf {
  219. pattern = strings.TrimSuffix(pattern, "/")
  220. return t.addNextSegment(pattern, handle)
  221. }
  222. func (t *Tree) matchLeaf(globLevel int, url string, params Params) (Handle, bool) {
  223. url, err := PathUnescape(url)
  224. if err != nil {
  225. return nil, false
  226. }
  227. for i := 0; i < len(t.leaves); i++ {
  228. switch t.leaves[i].typ {
  229. case _PATTERN_STATIC:
  230. if t.leaves[i].pattern == url {
  231. return t.leaves[i].handle, true
  232. }
  233. case _PATTERN_REGEXP:
  234. results := t.leaves[i].reg.FindStringSubmatch(url)
  235. // Number of results and wildcasrd should be exact same.
  236. if len(results)-1 != len(t.leaves[i].wildcards) {
  237. break
  238. }
  239. for j := 0; j < len(t.leaves[i].wildcards); j++ {
  240. params[t.leaves[i].wildcards[j]] = results[j+1]
  241. }
  242. return t.leaves[i].handle, true
  243. case _PATTERN_PATH_EXT:
  244. j := strings.LastIndex(url, ".")
  245. if j > -1 {
  246. params[":path"] = url[:j]
  247. params[":ext"] = url[j+1:]
  248. } else {
  249. params[":path"] = url
  250. }
  251. return t.leaves[i].handle, true
  252. case _PATTERN_HOLDER:
  253. params[t.leaves[i].wildcards[0]] = url
  254. return t.leaves[i].handle, true
  255. case _PATTERN_MATCH_ALL:
  256. params["*"] = url
  257. params["*"+com.ToStr(globLevel)] = url
  258. return t.leaves[i].handle, true
  259. }
  260. }
  261. return nil, false
  262. }
  263. func (t *Tree) matchSubtree(globLevel int, segment, url string, params Params) (Handle, bool) {
  264. unescapedSegment, err := PathUnescape(segment)
  265. if err != nil {
  266. return nil, false
  267. }
  268. for i := 0; i < len(t.subtrees); i++ {
  269. switch t.subtrees[i].typ {
  270. case _PATTERN_STATIC:
  271. if t.subtrees[i].pattern == unescapedSegment {
  272. if handle, ok := t.subtrees[i].matchNextSegment(globLevel, url, params); ok {
  273. return handle, true
  274. }
  275. }
  276. case _PATTERN_REGEXP:
  277. results := t.subtrees[i].reg.FindStringSubmatch(unescapedSegment)
  278. if len(results)-1 != len(t.subtrees[i].wildcards) {
  279. break
  280. }
  281. for j := 0; j < len(t.subtrees[i].wildcards); j++ {
  282. params[t.subtrees[i].wildcards[j]] = results[j+1]
  283. }
  284. if handle, ok := t.subtrees[i].matchNextSegment(globLevel, url, params); ok {
  285. return handle, true
  286. }
  287. case _PATTERN_HOLDER:
  288. if handle, ok := t.subtrees[i].matchNextSegment(globLevel+1, url, params); ok {
  289. params[t.subtrees[i].wildcards[0]] = unescapedSegment
  290. return handle, true
  291. }
  292. case _PATTERN_MATCH_ALL:
  293. if handle, ok := t.subtrees[i].matchNextSegment(globLevel+1, url, params); ok {
  294. params["*"+com.ToStr(globLevel)] = unescapedSegment
  295. return handle, true
  296. }
  297. }
  298. }
  299. if len(t.leaves) > 0 {
  300. leaf := t.leaves[len(t.leaves)-1]
  301. unescapedURL, err := PathUnescape(segment + "/" + url)
  302. if err != nil {
  303. return nil, false
  304. }
  305. if leaf.typ == _PATTERN_PATH_EXT {
  306. j := strings.LastIndex(unescapedURL, ".")
  307. if j > -1 {
  308. params[":path"] = unescapedURL[:j]
  309. params[":ext"] = unescapedURL[j+1:]
  310. } else {
  311. params[":path"] = unescapedURL
  312. }
  313. return leaf.handle, true
  314. } else if leaf.typ == _PATTERN_MATCH_ALL {
  315. params["*"] = unescapedURL
  316. params["*"+com.ToStr(globLevel)] = unescapedURL
  317. return leaf.handle, true
  318. }
  319. }
  320. return nil, false
  321. }
  322. func (t *Tree) matchNextSegment(globLevel int, url string, params Params) (Handle, bool) {
  323. i := strings.Index(url, "/")
  324. if i == -1 {
  325. return t.matchLeaf(globLevel, url, params)
  326. }
  327. return t.matchSubtree(globLevel, url[:i], url[i+1:], params)
  328. }
  329. func (t *Tree) Match(url string) (Handle, Params, bool) {
  330. url = strings.TrimPrefix(url, "/")
  331. url = strings.TrimSuffix(url, "/")
  332. params := make(Params)
  333. handle, ok := t.matchNextSegment(0, url, params)
  334. return handle, params, ok
  335. }
  336. // MatchTest returns true if given URL is matched by given pattern.
  337. func MatchTest(pattern, url string) bool {
  338. t := NewTree()
  339. t.Add(pattern, nil)
  340. _, _, ok := t.Match(url)
  341. return ok
  342. }