1
0

tree.go 15 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580
  1. // Copyright 2014 beego Author. All Rights Reserved.
  2. //
  3. // Licensed under the Apache License, Version 2.0 (the "License");
  4. // you may not use this file except in compliance with the License.
  5. // You may obtain 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,
  11. // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  12. // See the License for the specific language governing permissions and
  13. // limitations under the License.
  14. package beego
  15. import (
  16. "path"
  17. "regexp"
  18. "strings"
  19. "github.com/astaxie/beego/context"
  20. "github.com/astaxie/beego/utils"
  21. )
  22. var (
  23. allowSuffixExt = []string{".json", ".xml", ".html"}
  24. )
  25. // Tree has three elements: FixRouter/wildcard/leaves
  26. // fixRouter sotres Fixed Router
  27. // wildcard stores params
  28. // leaves store the endpoint information
  29. type Tree struct {
  30. //prefix set for static router
  31. prefix string
  32. //search fix route first
  33. fixrouters []*Tree
  34. //if set, failure to match fixrouters search then search wildcard
  35. wildcard *Tree
  36. //if set, failure to match wildcard search
  37. leaves []*leafInfo
  38. }
  39. // NewTree return a new Tree
  40. func NewTree() *Tree {
  41. return &Tree{}
  42. }
  43. // AddTree will add tree to the exist Tree
  44. // prefix should has no params
  45. func (t *Tree) AddTree(prefix string, tree *Tree) {
  46. t.addtree(splitPath(prefix), tree, nil, "")
  47. }
  48. func (t *Tree) addtree(segments []string, tree *Tree, wildcards []string, reg string) {
  49. if len(segments) == 0 {
  50. panic("prefix should has path")
  51. }
  52. seg := segments[0]
  53. iswild, params, regexpStr := splitSegment(seg)
  54. // if it's ? meaning can igone this, so add one more rule for it
  55. if len(params) > 0 && params[0] == ":" {
  56. params = params[1:]
  57. if len(segments[1:]) > 0 {
  58. t.addtree(segments[1:], tree, append(wildcards, params...), reg)
  59. } else {
  60. filterTreeWithPrefix(tree, wildcards, reg)
  61. }
  62. }
  63. //Rule: /login/*/access match /login/2009/11/access
  64. //if already has *, and when loop the access, should as a regexpStr
  65. if !iswild && utils.InSlice(":splat", wildcards) {
  66. iswild = true
  67. regexpStr = seg
  68. }
  69. //Rule: /user/:id/*
  70. if seg == "*" && len(wildcards) > 0 && reg == "" {
  71. regexpStr = "(.+)"
  72. }
  73. if len(segments) == 1 {
  74. if iswild {
  75. if regexpStr != "" {
  76. if reg == "" {
  77. rr := ""
  78. for _, w := range wildcards {
  79. if w == ":splat" {
  80. rr = rr + "(.+)/"
  81. } else {
  82. rr = rr + "([^/]+)/"
  83. }
  84. }
  85. regexpStr = rr + regexpStr
  86. } else {
  87. regexpStr = "/" + regexpStr
  88. }
  89. } else if reg != "" {
  90. if seg == "*.*" {
  91. regexpStr = "([^.]+).(.+)"
  92. } else {
  93. for _, w := range params {
  94. if w == "." || w == ":" {
  95. continue
  96. }
  97. regexpStr = "([^/]+)/" + regexpStr
  98. }
  99. }
  100. }
  101. reg = strings.Trim(reg+"/"+regexpStr, "/")
  102. filterTreeWithPrefix(tree, append(wildcards, params...), reg)
  103. t.wildcard = tree
  104. } else {
  105. reg = strings.Trim(reg+"/"+regexpStr, "/")
  106. filterTreeWithPrefix(tree, append(wildcards, params...), reg)
  107. tree.prefix = seg
  108. t.fixrouters = append(t.fixrouters, tree)
  109. }
  110. return
  111. }
  112. if iswild {
  113. if t.wildcard == nil {
  114. t.wildcard = NewTree()
  115. }
  116. if regexpStr != "" {
  117. if reg == "" {
  118. rr := ""
  119. for _, w := range wildcards {
  120. if w == ":splat" {
  121. rr = rr + "(.+)/"
  122. } else {
  123. rr = rr + "([^/]+)/"
  124. }
  125. }
  126. regexpStr = rr + regexpStr
  127. } else {
  128. regexpStr = "/" + regexpStr
  129. }
  130. } else if reg != "" {
  131. if seg == "*.*" {
  132. regexpStr = "([^.]+).(.+)"
  133. params = params[1:]
  134. } else {
  135. for range params {
  136. regexpStr = "([^/]+)/" + regexpStr
  137. }
  138. }
  139. } else {
  140. if seg == "*.*" {
  141. params = params[1:]
  142. }
  143. }
  144. reg = strings.TrimRight(strings.TrimRight(reg, "/")+"/"+regexpStr, "/")
  145. t.wildcard.addtree(segments[1:], tree, append(wildcards, params...), reg)
  146. } else {
  147. subTree := NewTree()
  148. subTree.prefix = seg
  149. t.fixrouters = append(t.fixrouters, subTree)
  150. subTree.addtree(segments[1:], tree, append(wildcards, params...), reg)
  151. }
  152. }
  153. func filterTreeWithPrefix(t *Tree, wildcards []string, reg string) {
  154. for _, v := range t.fixrouters {
  155. filterTreeWithPrefix(v, wildcards, reg)
  156. }
  157. if t.wildcard != nil {
  158. filterTreeWithPrefix(t.wildcard, wildcards, reg)
  159. }
  160. for _, l := range t.leaves {
  161. if reg != "" {
  162. if l.regexps != nil {
  163. l.wildcards = append(wildcards, l.wildcards...)
  164. l.regexps = regexp.MustCompile("^" + reg + "/" + strings.Trim(l.regexps.String(), "^$") + "$")
  165. } else {
  166. for _, v := range l.wildcards {
  167. if v == ":splat" {
  168. reg = reg + "/(.+)"
  169. } else {
  170. reg = reg + "/([^/]+)"
  171. }
  172. }
  173. l.regexps = regexp.MustCompile("^" + reg + "$")
  174. l.wildcards = append(wildcards, l.wildcards...)
  175. }
  176. } else {
  177. l.wildcards = append(wildcards, l.wildcards...)
  178. if l.regexps != nil {
  179. for _, w := range wildcards {
  180. if w == ":splat" {
  181. reg = "(.+)/" + reg
  182. } else {
  183. reg = "([^/]+)/" + reg
  184. }
  185. }
  186. l.regexps = regexp.MustCompile("^" + reg + strings.Trim(l.regexps.String(), "^$") + "$")
  187. }
  188. }
  189. }
  190. }
  191. // AddRouter call addseg function
  192. func (t *Tree) AddRouter(pattern string, runObject interface{}) {
  193. t.addseg(splitPath(pattern), runObject, nil, "")
  194. }
  195. // "/"
  196. // "admin" ->
  197. func (t *Tree) addseg(segments []string, route interface{}, wildcards []string, reg string) {
  198. if len(segments) == 0 {
  199. if reg != "" {
  200. t.leaves = append(t.leaves, &leafInfo{runObject: route, wildcards: wildcards, regexps: regexp.MustCompile("^" + reg + "$")})
  201. } else {
  202. t.leaves = append(t.leaves, &leafInfo{runObject: route, wildcards: wildcards})
  203. }
  204. } else {
  205. seg := segments[0]
  206. iswild, params, regexpStr := splitSegment(seg)
  207. // if it's ? meaning can igone this, so add one more rule for it
  208. if len(params) > 0 && params[0] == ":" {
  209. t.addseg(segments[1:], route, wildcards, reg)
  210. params = params[1:]
  211. }
  212. //Rule: /login/*/access match /login/2009/11/access
  213. //if already has *, and when loop the access, should as a regexpStr
  214. if !iswild && utils.InSlice(":splat", wildcards) {
  215. iswild = true
  216. regexpStr = seg
  217. }
  218. //Rule: /user/:id/*
  219. if seg == "*" && len(wildcards) > 0 && reg == "" {
  220. regexpStr = "(.+)"
  221. }
  222. if iswild {
  223. if t.wildcard == nil {
  224. t.wildcard = NewTree()
  225. }
  226. if regexpStr != "" {
  227. if reg == "" {
  228. rr := ""
  229. for _, w := range wildcards {
  230. if w == ":splat" {
  231. rr = rr + "(.+)/"
  232. } else {
  233. rr = rr + "([^/]+)/"
  234. }
  235. }
  236. regexpStr = rr + regexpStr
  237. } else {
  238. regexpStr = "/" + regexpStr
  239. }
  240. } else if reg != "" {
  241. if seg == "*.*" {
  242. regexpStr = "/([^.]+).(.+)"
  243. params = params[1:]
  244. } else {
  245. for range params {
  246. regexpStr = "/([^/]+)" + regexpStr
  247. }
  248. }
  249. } else {
  250. if seg == "*.*" {
  251. params = params[1:]
  252. }
  253. }
  254. t.wildcard.addseg(segments[1:], route, append(wildcards, params...), reg+regexpStr)
  255. } else {
  256. var subTree *Tree
  257. for _, sub := range t.fixrouters {
  258. if sub.prefix == seg {
  259. subTree = sub
  260. break
  261. }
  262. }
  263. if subTree == nil {
  264. subTree = NewTree()
  265. subTree.prefix = seg
  266. t.fixrouters = append(t.fixrouters, subTree)
  267. }
  268. subTree.addseg(segments[1:], route, wildcards, reg)
  269. }
  270. }
  271. }
  272. // Match router to runObject & params
  273. func (t *Tree) Match(pattern string, ctx *context.Context) (runObject interface{}) {
  274. if len(pattern) == 0 || pattern[0] != '/' {
  275. return nil
  276. }
  277. w := make([]string, 0, 20)
  278. return t.match(pattern, w, ctx)
  279. }
  280. func (t *Tree) match(pattern string, wildcardValues []string, ctx *context.Context) (runObject interface{}) {
  281. if len(pattern) > 0 {
  282. i := 0
  283. for ; i < len(pattern) && pattern[i] == '/'; i++ {
  284. }
  285. pattern = pattern[i:]
  286. }
  287. // Handle leaf nodes:
  288. if len(pattern) == 0 {
  289. for _, l := range t.leaves {
  290. if ok := l.match(wildcardValues, ctx); ok {
  291. return l.runObject
  292. }
  293. }
  294. if t.wildcard != nil {
  295. for _, l := range t.wildcard.leaves {
  296. if ok := l.match(wildcardValues, ctx); ok {
  297. return l.runObject
  298. }
  299. }
  300. }
  301. return nil
  302. }
  303. var seg string
  304. i, l := 0, len(pattern)
  305. for ; i < l && pattern[i] != '/'; i++ {
  306. }
  307. if i == 0 {
  308. seg = pattern
  309. pattern = ""
  310. } else {
  311. seg = pattern[:i]
  312. pattern = pattern[i:]
  313. }
  314. for _, subTree := range t.fixrouters {
  315. if subTree.prefix == seg {
  316. runObject = subTree.match(pattern, wildcardValues, ctx)
  317. if runObject != nil {
  318. break
  319. }
  320. }
  321. }
  322. if runObject == nil && len(t.fixrouters) > 0 {
  323. // Filter the .json .xml .html extension
  324. for _, str := range allowSuffixExt {
  325. if strings.HasSuffix(seg, str) {
  326. for _, subTree := range t.fixrouters {
  327. if subTree.prefix == seg[:len(seg)-len(str)] {
  328. runObject = subTree.match(pattern, wildcardValues, ctx)
  329. if runObject != nil {
  330. ctx.Input.SetParam(":ext", str[1:])
  331. }
  332. }
  333. }
  334. }
  335. }
  336. }
  337. if runObject == nil && t.wildcard != nil {
  338. runObject = t.wildcard.match(pattern, append(wildcardValues, seg), ctx)
  339. }
  340. if runObject == nil && len(t.leaves) > 0 {
  341. wildcardValues = append(wildcardValues, seg)
  342. start, i := 0, 0
  343. for ; i < len(pattern); i++ {
  344. if pattern[i] == '/' {
  345. if i != 0 && start < len(pattern) {
  346. wildcardValues = append(wildcardValues, pattern[start:i])
  347. }
  348. start = i + 1
  349. continue
  350. }
  351. }
  352. if start > 0 {
  353. wildcardValues = append(wildcardValues, pattern[start:i])
  354. }
  355. for _, l := range t.leaves {
  356. if ok := l.match(wildcardValues, ctx); ok {
  357. return l.runObject
  358. }
  359. }
  360. }
  361. return runObject
  362. }
  363. type leafInfo struct {
  364. // names of wildcards that lead to this leaf. eg, ["id" "name"] for the wildcard ":id" and ":name"
  365. wildcards []string
  366. // if the leaf is regexp
  367. regexps *regexp.Regexp
  368. runObject interface{}
  369. }
  370. func (leaf *leafInfo) match(wildcardValues []string, ctx *context.Context) (ok bool) {
  371. //fmt.Println("Leaf:", wildcardValues, leaf.wildcards, leaf.regexps)
  372. if leaf.regexps == nil {
  373. if len(wildcardValues) == 0 && len(leaf.wildcards) == 0 { // static path
  374. return true
  375. }
  376. // match *
  377. if len(leaf.wildcards) == 1 && leaf.wildcards[0] == ":splat" {
  378. ctx.Input.SetParam(":splat", path.Join(wildcardValues...))
  379. return true
  380. }
  381. // match *.* or :id
  382. if len(leaf.wildcards) >= 2 && leaf.wildcards[len(leaf.wildcards)-2] == ":path" && leaf.wildcards[len(leaf.wildcards)-1] == ":ext" {
  383. if len(leaf.wildcards) == 2 {
  384. lastone := wildcardValues[len(wildcardValues)-1]
  385. strs := strings.SplitN(lastone, ".", 2)
  386. if len(strs) == 2 {
  387. ctx.Input.SetParam(":ext", strs[1])
  388. }
  389. ctx.Input.SetParam(":path", path.Join(path.Join(wildcardValues[:len(wildcardValues)-1]...), strs[0]))
  390. return true
  391. } else if len(wildcardValues) < 2 {
  392. return false
  393. }
  394. var index int
  395. for index = 0; index < len(leaf.wildcards)-2; index++ {
  396. ctx.Input.SetParam(leaf.wildcards[index], wildcardValues[index])
  397. }
  398. lastone := wildcardValues[len(wildcardValues)-1]
  399. strs := strings.SplitN(lastone, ".", 2)
  400. if len(strs) == 2 {
  401. ctx.Input.SetParam(":ext", strs[1])
  402. }
  403. if index > (len(wildcardValues) - 1) {
  404. ctx.Input.SetParam(":path", "")
  405. } else {
  406. ctx.Input.SetParam(":path", path.Join(path.Join(wildcardValues[index:len(wildcardValues)-1]...), strs[0]))
  407. }
  408. return true
  409. }
  410. // match :id
  411. if len(leaf.wildcards) != len(wildcardValues) {
  412. return false
  413. }
  414. for j, v := range leaf.wildcards {
  415. ctx.Input.SetParam(v, wildcardValues[j])
  416. }
  417. return true
  418. }
  419. if !leaf.regexps.MatchString(path.Join(wildcardValues...)) {
  420. return false
  421. }
  422. matches := leaf.regexps.FindStringSubmatch(path.Join(wildcardValues...))
  423. for i, match := range matches[1:] {
  424. if i < len(leaf.wildcards) {
  425. ctx.Input.SetParam(leaf.wildcards[i], match)
  426. }
  427. }
  428. return true
  429. }
  430. // "/" -> []
  431. // "/admin" -> ["admin"]
  432. // "/admin/" -> ["admin"]
  433. // "/admin/users" -> ["admin", "users"]
  434. func splitPath(key string) []string {
  435. key = strings.Trim(key, "/ ")
  436. if key == "" {
  437. return []string{}
  438. }
  439. return strings.Split(key, "/")
  440. }
  441. // "admin" -> false, nil, ""
  442. // ":id" -> true, [:id], ""
  443. // "?:id" -> true, [: :id], "" : meaning can empty
  444. // ":id:int" -> true, [:id], ([0-9]+)
  445. // ":name:string" -> true, [:name], ([\w]+)
  446. // ":id([0-9]+)" -> true, [:id], ([0-9]+)
  447. // ":id([0-9]+)_:name" -> true, [:id :name], ([0-9]+)_(.+)
  448. // "cms_:id_:page.html" -> true, [:id_ :page], cms_(.+)(.+).html
  449. // "cms_:id(.+)_:page.html" -> true, [:id :page], cms_(.+)_(.+).html
  450. // "*" -> true, [:splat], ""
  451. // "*.*" -> true,[. :path :ext], "" . meaning separator
  452. func splitSegment(key string) (bool, []string, string) {
  453. if strings.HasPrefix(key, "*") {
  454. if key == "*.*" {
  455. return true, []string{".", ":path", ":ext"}, ""
  456. }
  457. return true, []string{":splat"}, ""
  458. }
  459. if strings.ContainsAny(key, ":") {
  460. var paramsNum int
  461. var out []rune
  462. var start bool
  463. var startexp bool
  464. var param []rune
  465. var expt []rune
  466. var skipnum int
  467. params := []string{}
  468. reg := regexp.MustCompile(`[a-zA-Z0-9_]+`)
  469. for i, v := range key {
  470. if skipnum > 0 {
  471. skipnum--
  472. continue
  473. }
  474. if start {
  475. //:id:int and :name:string
  476. if v == ':' {
  477. if len(key) >= i+4 {
  478. if key[i+1:i+4] == "int" {
  479. out = append(out, []rune("([0-9]+)")...)
  480. params = append(params, ":"+string(param))
  481. start = false
  482. startexp = false
  483. skipnum = 3
  484. param = make([]rune, 0)
  485. paramsNum++
  486. continue
  487. }
  488. }
  489. if len(key) >= i+7 {
  490. if key[i+1:i+7] == "string" {
  491. out = append(out, []rune(`([\w]+)`)...)
  492. params = append(params, ":"+string(param))
  493. paramsNum++
  494. start = false
  495. startexp = false
  496. skipnum = 6
  497. param = make([]rune, 0)
  498. continue
  499. }
  500. }
  501. }
  502. // params only support a-zA-Z0-9
  503. if reg.MatchString(string(v)) {
  504. param = append(param, v)
  505. continue
  506. }
  507. if v != '(' {
  508. out = append(out, []rune(`(.+)`)...)
  509. params = append(params, ":"+string(param))
  510. param = make([]rune, 0)
  511. paramsNum++
  512. start = false
  513. startexp = false
  514. }
  515. }
  516. if startexp {
  517. if v != ')' {
  518. expt = append(expt, v)
  519. continue
  520. }
  521. }
  522. // Escape Sequence '\'
  523. if i > 0 && key[i-1] == '\\' {
  524. out = append(out, v)
  525. } else if v == ':' {
  526. param = make([]rune, 0)
  527. start = true
  528. } else if v == '(' {
  529. startexp = true
  530. start = false
  531. if len(param) > 0 {
  532. params = append(params, ":"+string(param))
  533. param = make([]rune, 0)
  534. }
  535. paramsNum++
  536. expt = make([]rune, 0)
  537. expt = append(expt, '(')
  538. } else if v == ')' {
  539. startexp = false
  540. expt = append(expt, ')')
  541. out = append(out, expt...)
  542. param = make([]rune, 0)
  543. } else if v == '?' {
  544. params = append(params, ":")
  545. } else {
  546. out = append(out, v)
  547. }
  548. }
  549. if len(param) > 0 {
  550. if paramsNum > 0 {
  551. out = append(out, []rune(`(.+)`)...)
  552. }
  553. params = append(params, ":"+string(param))
  554. }
  555. return true, params, string(out)
  556. }
  557. return false, nil, ""
  558. }