Source file src/tawesoft.co.uk/go/router/private.go

Documentation: src/tawesoft.co.uk/go/router/private.go

     1  package router
     2  
     3  import (
     4      "fmt"
     5      "regexp"
     6      "sort"
     7  )
     8  
     9  // visit applies `f(route)` to a tree of routes (DFS)
    10  func visit(route *Route, f func(route *Route)) {
    11      f(route)
    12      
    13      for i := 0; i < len(route.Children); i++ {
    14          visit(&route.Children[i], f)
    15      }
    16  }
    17  
    18  // visiterr applies `f(route) => error` to a tree of routes (DFS), aborting on error
    19  func visiterr(route *Route, f func(route *Route) error) error {
    20      err := f(route)
    21      if err != nil { return err }
    22      
    23      for i := 0; i < len(route.Children); i++ {
    24          err = visiterr(&route.Children[i], f)
    25          if err != nil { return err }
    26      }
    27      
    28      return nil
    29  }
    30  
    31  // visitp applies `f(route, parent)` to a tree of routes (DFS)
    32  func visitp(route *Route, parent *Route, f func(route *Route, parent *Route)) {
    33      f(route, parent)
    34      
    35      for i := 0; i < len(route.Children); i++ {
    36          visitp(&route.Children[i], route, f)
    37      }
    38  }
    39  
    40  /*
    41  // sortedStringSetAdd inserts an item into a sorted list of strings if it does not exist already.
    42  func sortedStringSetAdd(list []string, item string) []string {
    43      var index = sort.SearchStrings(list, item)
    44      if (len(list) <= index) || (list[index] != item) {
    45          list = append(list, item)
    46          sort.Strings(list)
    47      }
    48      return list
    49  }
    50  */
    51  
    52  // acceptMethod parses [A-Z-]+ and returns a length plus a length including trailing spaces and commas.
    53  func acceptMethod(s string) (len int, offset int) {
    54      for _, c := range s {
    55          if (c >= 'A' && c <= 'Z') || (c == '-') {
    56              if offset != len { break } // next token appearing after commas/whitespace
    57              len++
    58              offset++
    59          } else if (c == ',') || (c == ' ') || (c == '\t') {
    60              offset++
    61          } else {
    62              break
    63          }
    64      }
    65      
    66      return len, offset
    67  }
    68  
    69  // nextMethod parses a comma-separated list of methods at a given offset and returns the offset of the
    70  // next method.
    71  func nextMethod(methods string, offset int) (string, int) {
    72      length, advance := acceptMethod(methods[offset:])
    73      if length > 0 {
    74          return methods[offset:offset+length], advance
    75      } else {
    76          return "", -1
    77      }
    78  }
    79  
    80  // acceptPathComponent parses up to the next '/' and returns a length excluding that '/'
    81  func acceptPathComponent(s string) (offset int) {
    82      for _, c := range s {
    83          if (c == '/') { break }
    84          offset++
    85      }
    86      
    87      return offset
    88  }
    89  
    90  /*
    91  // scanMethods visits each route in a tree, building a sorted list of methods.
    92  func scanMethods(root *Route) []string {
    93      methods := make([]string, 0)
    94      
    95      visit(root, func(route *Route) {
    96          offset := 0
    97          for {
    98              method, advance := nextMethod(route.Methods, offset)
    99              if advance < 0 { break }
   100              offset += advance
   101              methods = sortedStringSetAdd(methods, method)
   102          }
   103      })
   104      
   105      return methods
   106  }
   107   */
   108  
   109  // scanRouteNames builds a mapping of `name => Route`
   110  func scanRouteNames(root *Route) (map[string]*Route, error) {
   111      namedRoutes := make(map[string]*Route)
   112      
   113      err := visiterr(root, func(route *Route) error {
   114          name := route.Name
   115          if len(name) == 0 { return nil }
   116          
   117          if namedRoutes[name] == nil {
   118              namedRoutes[name] = route
   119          } else {
   120              return fmt.Errorf("route name %s is not unique", name)
   121          }
   122          
   123          return nil
   124      })
   125      
   126      return namedRoutes, err
   127  }
   128  
   129  // builds a mapping of `Route => parent Route`
   130  func scanParents(root *Route) map[*Route]*Route {
   131      parents := make(map[*Route]*Route)
   132      
   133      visitp(root, nil, func(route *Route, parent *Route) {
   134          parents[route] = parent
   135      })
   136      
   137      return parents
   138  }
   139  
   140  // reverseStringList reverses in place.
   141  func reverseStringList(a ... string) {
   142      // https://github.com/golang/go/wiki/SliceTricks
   143      for left, right := 0, len(a)-1; left < right; left, right = left+1, right-1 {
   144          a[left], a[right] = a[right], a[left]
   145      }
   146  }
   147  
   148  type sortableRoutes []Route
   149  
   150  func (a sortableRoutes) Len() int             { return len(a) }
   151  func (a sortableRoutes) Swap(i, j int)        { a[i], a[j] = a[j], a[i] }
   152  func (a sortableRoutes) Less(i, j int) bool   { return a[i].order() < a[j].order() }
   153  func (r Route) order() int {
   154      /*
   155      // ORDER:
   156      // 0 Empty path (Pattern is nil or empty string; Final has no effect)
   157      // 1 Final Exact matches (Pattern is string and Final is true)
   158      // 2 Exact matches (Pattern is string and Final is false)
   159      // 3 Final Regex matches (Pattern is Regexp and Final is true)
   160      // 4 Regex matches (Pattern is Regexp and Final is false)
   161      // 5 Wildcard (string "*" and Final is false)
   162      // 6 Final Wildcard (string "*" and Final is true)
   163       */
   164      
   165      switch v := r.Pattern.(type) {
   166          case nil:
   167                                        return 0
   168          case string:
   169              if v == ""              { return 0 }
   170              if v == "*" && !r.Final { return 5 }
   171              if v == "*" && r.Final  { return 6 }
   172              if r.Final              { return 1 }
   173              if !r.Final             { return 2 }
   174          case *regexp.Regexp:
   175              if r.Final              { return 3 }
   176              if !r.Final             { return 4 }
   177          default:
   178              panic(fmt.Errorf("invalid Route Pattern type %T", v))
   179      }
   180      
   181      return 0
   182  }
   183  
   184  // sortRoutes sorts a list of routes in place such that
   185  func sortRoutes(routes []Route) {
   186      if routes == nil { return }
   187      if len(routes) == 0 { return }
   188  
   189      sort.Stable(sortableRoutes(routes))
   190      for _, i := range routes {
   191          sortRoutes(i.Children)
   192      }
   193  }
   194  
   195  // match returns true if a route matches the given path component
   196  func (r *Route) match(component string) bool {
   197  
   198      switch v := r.Pattern.(type) {
   199          case nil:
   200              return component == ""
   201          case string:
   202              if v == "" { return component == ""  }
   203              if v == "*" { return true }
   204              return v == component
   205          case *regexp.Regexp:
   206              return v.MatchString(component)
   207          default:
   208              panic(fmt.Errorf("invalid Route Pattern type %T", v))
   209      }
   210  }
   211  
   212  // submatch returns a slice of submatches like `(*Regexp) FindStringSubmatch`
   213  // from https://golang.org/pkg/regexp/#Regexp.FindStringSubmatch
   214  //
   215  // e.g. pattern `a(b*)(c*)(d|D)f` and string "acccDf" returns
   216  // ["acccDf", "", "ccc", "D"].
   217  //
   218  // These can be nested e.g. pattern `(a+)(\.(b+))?c` and string "aaa.bbbbbbbc"
   219  // returns ["aaa.bbbbbbbc" "aaa" ".bbbbbbb" "bbbbbbb"]
   220  //
   221  // Returns nil if no matches/submatches
   222  //
   223  // IMPORTANT: assumes in the case of a string pattern (rather than a regex
   224  // pattern) that match(component) is already true
   225  func (r *Route) submatch(component string) []string {
   226  
   227      switch v := r.Pattern.(type) {
   228          case nil:
   229              return nil
   230          case string:
   231              return []string{component} // N.B. assumes match(component) is true!
   232          case *regexp.Regexp:
   233              return v.FindStringSubmatch(component)
   234          default:
   235              panic(fmt.Errorf("invalid Route Pattern type %T", v))
   236      }
   237  }
   238  
   239  func (router *Router) match(method string, path string, current *Route,
   240      params *map[string]string, subparams *map[string][]string) *Route {
   241      // NOTE: modifies params, subparams
   242      
   243      // NOTE: must only check the last match against the method argument so that
   244      // we can match routes with identical Pattern values but differing Method
   245      // values.
   246      
   247      var component string
   248      var advance int
   249      
   250      if current.Final {
   251          component = path
   252      } else {
   253          advance = acceptPathComponent(path)
   254          component = path[0:advance]
   255      }
   256      
   257      match := current.match(component)
   258      
   259      if match && current.Key != "" {
   260          if *params == nil { *params = make(map[string]string) }
   261          (*params)[current.Key] = component
   262          
   263          submatch := current.submatch(component)
   264          if submatch != nil {
   265              if *subparams == nil { *subparams = make(map[string][]string) }
   266              (*subparams)[current.Key] = submatch
   267          }
   268      }
   269      
   270      if !match { return nil }
   271      
   272      if current.Final {
   273          
   274          // its the last match because its a Final pattern
   275          if !current.matchMethod(method, router.DefaultMethods) { return nil }
   276          return current
   277          
   278      } else if (current.Children == nil) || (len(current.Children) == 0) {
   279          
   280          // its the last possible match because its a match with no children
   281          // so its a successful match if the full path has been parsed
   282          if advance == len(path) {
   283              if !current.matchMethod(method, router.DefaultMethods) { return nil }
   284              return current
   285          }
   286          
   287      } else if match {
   288          
   289          // its a match with children
   290          
   291          // if the full path has been matched, it has to be this route
   292          if advance == len(path) {
   293              if !current.matchMethod(method, router.DefaultMethods) { return nil }
   294              return current
   295          }
   296          
   297          // otherwise its a partial match, that the child routes have to try and
   298          // handle.
   299          remainder := path[advance+1:]
   300          for _, i := range(current.Children) {
   301              match := router.match(method, remainder, &i, params, subparams)
   302              if match != nil { return match }
   303          }
   304      }
   305      
   306      return nil
   307  }
   308  
   309  func (r *Route) matchMethod(method string, defaultMethods string) bool {
   310      offset := 0
   311      
   312      methods := r.Methods
   313      if methods == "" { methods = defaultMethods }
   314      
   315      for {
   316          routeMethod, advance := nextMethod(methods, offset)
   317          if advance < 0 { break }
   318          offset += advance
   319          if method == routeMethod { return true }
   320      }
   321      
   322      return false
   323  }
   324  

View as plain text