trout
2015-03-16
Child:bf38b050b6c4
trout/route.go
First pass at a router library. First pass at a router library and, incidentally, implementing a trie. I could probably optimise the search for the right branch somehow, but I honestly just can't be bothered right now. I also haven't tested this at all or even tried to run it, so who knows if my code even works. But it compiles, go vet and golint have found nothing to complain about, it has documentation, and it's properly formatted. So it's already better than most software out there. </ba dump tiss>
1 package trout
3 import (
4 "net/http"
5 "strconv"
6 "strings"
7 "time"
8 )
10 var (
11 default404Handler = http.Handler(http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
12 w.WriteHeader(http.StatusNotFound)
13 w.Write([]byte("404 Not Found"))
14 return
15 }))
16 default405Handler = http.Handler(http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
17 w.WriteHeader(http.StatusMethodNotAllowed)
18 w.Write([]byte("405 Method Not Allowed"))
19 return
20 }))
21 )
23 // RequestVars returns easy-to-access mappings of parameters to values for URL templates. Any {parameter} in
24 // your URL template will be available in the returned Header as a slice of strings, one for each instance of
25 // the {parameter}. In the case of a parameter name being used more than once in the same URL template, the
26 // values will be in the slice in the order they appeared in the template.
27 //
28 // Values can easily be accessed by using the .Get() method of the returned Header, though to access multiple
29 // values, they must be accessed through the map. All parameters use http.CanonicalHeaderKey for their formatting.
30 // When using .Get(), the parameter name will be transformed automatically. When utilising the Header as a map,
31 // the parameter name needs to have http.CanonicalHeaderKey applied manually.
32 func RequestVars(r *http.Request) http.Header {
33 res := http.Header{}
34 for h, v := range r.Header {
35 stripped := strings.TrimPrefix(h, http.CanonicalHeaderKey("Trout-Param-"))
36 if stripped != h {
37 res[stripped] = v
38 }
39 }
40 return res
41 }
43 // Router defines a set of Endpoints that map requests to the http.Handlers. The http.Handler assigned to
44 // Handle404, if set, will be called when no Endpoint matches the current request. The http.Handler assigned
45 // to Handle405, if set, will be called when an Endpoint matches the current request, but has no http.Handler
46 // set for the HTTP method that the request used. Should either of these properties be unset, a default
47 // http.Handler will be used.
48 //
49 // The Router type is safe for use with empty values, but makes no attempt at concurrency-safety in adding
50 // Endpoints or in setting properties. It should also be noted that the adding Endpoints while simultaneously
51 // routing requests will lead to undefined and (almost certainly) undesirable behaviour. Routers are intended
52 // to be initialised with a set of Endpoints, and then start serving requests. Using them outside of this use
53 // case is unsupported.
54 type Router struct {
55 t *trie
56 Handle404 http.Handler
57 Handle405 http.Handler
58 }
60 func (router Router) serve404(w http.ResponseWriter, r *http.Request, t time.Time) {
61 h := default404Handler
62 if router.Handle404 != nil {
63 h = router.Handle404
64 }
65 r.Header.Set("Trout-Timer", strconv.FormatInt(time.Now().Sub(t).Nanoseconds(), 10))
66 h.ServeHTTP(w, r)
67 }
69 func (router Router) serve405(w http.ResponseWriter, r *http.Request, t time.Time) {
70 h := default405Handler
71 if router.Handle405 != nil {
72 h = router.Handle405
73 }
74 r.Header.Set("Trout-Timer", strconv.FormatInt(time.Now().Sub(t).Nanoseconds(), 10))
75 h.ServeHTTP(w, r)
76 }
78 func (router Router) ServeHTTP(w http.ResponseWriter, r *http.Request) {
79 start := time.Now()
80 if router.t == nil {
81 router.serve404(w, r, start)
82 }
83 pieces := strings.Split(strings.ToLower(strings.Trim(r.URL.Path, "/")), "/")
84 router.t.RLock()
85 defer router.t.RUnlock()
86 branches := make([]*branch, len(pieces))
87 path, ok := router.t.match(pieces)
88 if !ok {
89 router.serve404(w, r, start)
90 }
91 b := router.t.branch
92 for i, pos := range path {
93 b = b.children[pos]
94 branches[i] = b
95 }
96 v := vars(branches, pieces)
97 for key, vals := range v {
98 r.Header[http.CanonicalHeaderKey("Trout-Param-"+key)] = vals
99 }
100 ms := make([]string, len(b.methods))
101 i := 0
102 for m := range b.methods {
103 ms[i] = m
104 i = i + 1
105 }
106 r.Header[http.CanonicalHeaderKey("Trout-Methods")] = ms
107 h := b.methods[r.Method]
108 if h == nil {
109 router.serve405(w, r, start)
110 }
111 r.Header.Set("Trout-Timer", strconv.FormatInt(time.Now().Sub(start).Nanoseconds(), 10))
112 h.ServeHTTP(w, r)
113 }
115 // Endpoint defines a new Endpoint on the Router. The Endpoint should be a URL template, using curly braces
116 // to denote parameters that should be filled at runtime. For example, `{id}` denotes a parameter named `id`
117 // that should be filled with whatever the request has in that space.
118 //
119 // Parameters are always `/`-separated strings. There is no support for regular expressions or other limitations
120 // on what may be in those strings. A parameter is simply defined as "whatever is between these two / characters".
121 func (router Router) Endpoint(e string) *Endpoint {
122 e = strings.Trim(e, "/")
123 e = strings.ToLower(e)
124 pieces := strings.Split(e, "/")
125 router.t.Lock()
126 defer router.t.Unlock()
127 if router.t.branch == nil {
128 router.t.branch = &branch{
129 parent: nil,
130 children: []*branch{},
131 key: "",
132 isParam: false,
133 methods: map[string]http.Handler{},
134 }
135 }
136 closest := findClosestLeaf(pieces, router.t.branch)
137 b := router.t.branch
138 for _, pos := range closest {
139 b = b.children[pos]
140 }
141 if len(closest) == len(pieces) {
142 return (*Endpoint)(b)
143 }
144 offset := len(closest)
145 for i := offset; i < len(pieces); i++ {
146 piece := pieces[i]
147 var isParam bool
148 if piece[0:1] == "{" && piece[len(piece)-1:] == "}" {
149 isParam = true
150 piece = piece[1 : len(piece)-1]
151 }
152 b = b.addChild(piece, isParam)
153 }
154 return (*Endpoint)(b)
155 }
157 func vars(path []*branch, pieces []string) map[string][]string {
158 v := map[string][]string{}
159 for pos, p := range path {
160 if !p.isParam {
161 continue
162 }
163 _, ok := v[p.key]
164 if !ok {
165 v[p.key] = []string{pieces[pos]}
166 continue
167 }
168 v[p.key] = append(v[p.key], pieces[pos])
169 }
170 return v
171 }
173 func findClosestLeaf(pieces []string, b *branch) []int {
174 offset := 0
175 path := []int{}
176 longest := []int{}
177 num := len(pieces)
178 for i := 0; i < num; i++ {
179 piece := pieces[i]
180 var isParam bool
181 if piece[0:1] == "{" && piece[len(piece)-1:] == "}" {
182 isParam = true
183 piece = piece[1 : len(piece)-1]
184 }
185 offset = pickNextRoute(b, offset, piece, isParam)
186 if offset == -1 {
187 if len(path) == 0 {
188 // exhausted our options, bail
189 break
190 }
191 // no match, maybe save this and backup
192 if len(path) > len(longest) {
193 longest = append([]int{}, path...) // copy them over so they don't get modified
194 }
195 path, offset = backup(path)
196 offset = offset + 1
197 b = b.parent
198 i = i - 2
199 } else {
200 path = append(path, offset)
201 b = b.children[offset]
202 offset = 0
203 }
204 }
205 if len(longest) < len(path) {
206 longest = append([]int{}, path...)
207 }
208 return longest
209 }
211 func pickNextRoute(b *branch, offset int, input string, variable bool) int {
212 count := len(b.children)
213 for i := offset; i < count; i++ {
214 if b.children[i].key == input && b.isParam == variable {
215 return i
216 }
217 }
218 return -1
219 }
221 // Endpoint defines a single URL template that requests can be matched against. It uses
222 // URL parameters to accept variables in the URL structure and make them available to
223 // the Handlers associated with the Endpoint.
224 type Endpoint branch
226 // Handler associates the passed http.Handler with the Endpoint. This http.Handler will be
227 // used for all requests, regardless of the HTTP method they are using, unless overridden by
228 // the Methods method. Endpoints without a http.Handler associated with them will not be
229 // considered matches for requests, unless the request was made using an HTTP method that the
230 // Endpoint has an http.Handler mapped to.
231 func (e *Endpoint) Handler(h http.Handler) {
232 (*branch)(e).setHandler("", h)
233 }
235 // Methods simple returns a Methods object that will enable the mapping of the passed HTTP
236 // request methods to a Methods object. On its own, this function does not modify anything. It
237 // should, instead, be used as a friendly shorthand to get to the Methods.Handler method.
238 func (e *Endpoint) Methods(m ...string) Methods {
239 return Methods{
240 e: e,
241 m: m,
242 }
243 }
245 // Methods defines a pairing of an Endpoint to the HTTP request methods that should be mapped to
246 // specific http.Handlers. Its sole purpose is to enable the Methods.Handler method.
247 type Methods struct {
248 e *Endpoint
249 m []string
250 }
252 // Handler maps a Methods object to a specific http.Handler. This overrides the http.Handler
253 // associated with the Endpoint to only handle specific HTTP method(s).
254 func (m Methods) Handler(h http.Handler) {
255 b := (*branch)(m.e)
256 for _, method := range m.m {
257 b.setHandler(method, h)
258 }
259 }