1 /**
2 	Pattern based URL router for HTTP request.
3 
4 	See `URLRouter` for more details.
5 
6 	Copyright: © 2012-2015 Sönke Ludwig
7 	License: Subject to the terms of the MIT license, as written in the included LICENSE.txt file.
8 	Authors: Sönke Ludwig
9 */
10 module vibe.http.router;
11 
12 public import vibe.http.server;
13 
14 import vibe.core.log;
15 
16 import std.functional;
17 
18 
19 /**
20 	Routes HTTP requests based on the request method and URL.
21 
22 	Routes are matched using a special URL match string that supports two forms
23 	of placeholders. See the sections below for more details.
24 
25 	Registered routes are matched according to the same sequence as initially
26 	specified using `match`, `get`, `post` etc. Matching ends as soon as a route
27 	handler writes a response using `res.writeBody()` or similar means. If no
28 	route matches or if no route handler writes a response, the router will
29 	simply not handle the request and the HTTP server will automatically
30 	generate a 404 error.
31 
32 	Match_patterns:
33 		Match patterns are character sequences that can optionally contain
34 		placeholders or raw wildcards ("*"). Raw wild cards match any character
35 		sequence, while placeholders match only sequences containing no slash
36 		("/") characters.
37 
38 		Placeholders are started using a colon (":") and are directly followed
39 		by their name. The first "/" character (or the end of the match string)
40 		denotes the end of the placeholder name. The part of the string that
41 		matches a placeholder will be stored in the `HTTPServerRequest.params`
42 		map using the placeholder name as the key.
43 
44 		Match strings are subject to the following rules:
45 		$(UL
46 			$(LI A raw wildcard ("*") may only occur at the end of the match string)
47 			$(LI At least one character must be placed between any two placeholders or wildcards)
48 			$(LI The maximum allowed number of placeholders in a single match string is 64)
49 		)
50 
51 	Match_String_Examples:
52 		$(UL
53 			$(LI `"/foo/bar"` matches only `"/foo/bar"` itself)
54 			$(LI `"/foo/*"` matches `"/foo/"`, `"/foo/bar"`, `"/foo/bar/baz"` or _any other string beginning with `"/foo/"`)
55 			$(LI `"/:x/"` matches `"/foo/"`, `"/bar/"` and similar strings (and stores `"foo"`/`"bar"` in `req.params["x"]`), but not `"/foo/bar/"`)
56 			$(LI Matching partial path entries with wildcards is possible: `"/foo:x"` matches `"/foo"`, `"/foobar"`, but not `"/foo/bar"`)
57 			$(LI Multiple placeholders and raw wildcards can be combined: `"/:x/:y/*"`)
58 		)
59 */
60 final class URLRouter : HTTPServerRequestHandler {
61 	@safe:
62 
63 	private {
64 		MatchTree!Route m_routes;
65 		string m_prefix;
66 		bool m_computeBasePath;
67 	}
68 
69 	this(string prefix = null)
70 	{
71 		m_prefix = prefix;
72 	}
73 
74 	/** Sets a common prefix for all registered routes.
75 
76 		All routes will implicitly have this prefix prepended before being
77 		matched against incoming requests.
78 	*/
79 	@property string prefix() const { return m_prefix; }
80 
81 	/** Controls the computation of the "routerRootDir" parameter.
82 
83 		This parameter is available as `req.params["routerRootDir"]` and
84 		contains the relative path to the base path of the router. The base
85 		path is determined by the `prefix` property.
86 
87 		Note that this feature currently is requires dynamic memory allocations
88 		and is opt-in for this reason.
89 	*/
90 	@property void enableRootDir(bool enable) { m_computeBasePath = enable; }
91 
92 	/// Returns a single route handle to conveniently register multiple methods.
93 	URLRoute route(string path)
94 	in { assert(path.length, "Cannot register null or empty path!"); }
95 	do { return URLRoute(this, path); }
96 
97 	///
98 	unittest {
99 		void getFoo(scope HTTPServerRequest req, scope HTTPServerResponse res) { /* ... */ }
100 		void postFoo(scope HTTPServerRequest req, scope HTTPServerResponse res) { /* ... */ }
101 		void deleteFoo(scope HTTPServerRequest req, scope HTTPServerResponse res) { /* ... */ }
102 
103 		auto r = new URLRouter;
104 
105 		// using 'with' statement
106 		with (r.route("/foo")) {
107 			get(&getFoo);
108 			post(&postFoo);
109 			delete_(&deleteFoo);
110 		}
111 
112 		// using method chaining
113 		r.route("/foo")
114 			.get(&getFoo)
115 			.post(&postFoo)
116 			.delete_(&deleteFoo);
117 
118 		// without using route()
119 		r.get("/foo", &getFoo);
120 		r.post("/foo", &postFoo);
121 		r.delete_("/foo", &deleteFoo);
122 	}
123 
124 	/// Adds a new route for requests matching the specified HTTP method and pattern.
125 	URLRouter match(Handler)(HTTPMethod method, string path, Handler handler)
126 		if (isValidHandler!Handler)
127 	{
128 		import std.algorithm;
129 		assert(path.length, "Cannot register null or empty path!");
130 		assert(count(path, ':') <= maxRouteParameters, "Too many route parameters");
131 		logDebug("add route %s %s", method, path);
132 		m_routes.addTerminal(path, Route(method, path, handlerDelegate(handler)));
133 		return this;
134 	}
135 
136 	/// ditto
137 	URLRouter match(HTTPMethod method, string path, HTTPServerRequestDelegate handler)
138 	{
139 		return match!HTTPServerRequestDelegate(method, path, handler);
140 	}
141 
142 	/// Adds a new route for GET requests matching the specified pattern.
143 	URLRouter get(Handler)(string url_match, Handler handler) if (isValidHandler!Handler) { return match(HTTPMethod.GET, url_match, handler); }
144 	/// ditto
145 	URLRouter get(string url_match, HTTPServerRequestDelegate handler) { return match(HTTPMethod.GET, url_match, handler); }
146 
147 	/// Adds a new route for POST requests matching the specified pattern.
148 	URLRouter post(Handler)(string url_match, Handler handler) if (isValidHandler!Handler) { return match(HTTPMethod.POST, url_match, handler); }
149 	/// ditto
150 	URLRouter post(string url_match, HTTPServerRequestDelegate handler) { return match(HTTPMethod.POST, url_match, handler); }
151 
152 	/// Adds a new route for PUT requests matching the specified pattern.
153 	URLRouter put(Handler)(string url_match, Handler handler) if (isValidHandler!Handler) { return match(HTTPMethod.PUT, url_match, handler); }
154 	/// ditto
155 	URLRouter put(string url_match, HTTPServerRequestDelegate handler) { return match(HTTPMethod.PUT, url_match, handler); }
156 
157 	/// Adds a new route for DELETE requests matching the specified pattern.
158 	URLRouter delete_(Handler)(string url_match, Handler handler) if (isValidHandler!Handler) { return match(HTTPMethod.DELETE, url_match, handler); }
159 	/// ditto
160 	URLRouter delete_(string url_match, HTTPServerRequestDelegate handler) { return match(HTTPMethod.DELETE, url_match, handler); }
161 
162 	/// Adds a new route for PATCH requests matching the specified pattern.
163 	URLRouter patch(Handler)(string url_match, Handler handler) if (isValidHandler!Handler) { return match(HTTPMethod.PATCH, url_match, handler); }
164 	/// ditto
165 	URLRouter patch(string url_match, HTTPServerRequestDelegate handler) { return match(HTTPMethod.PATCH, url_match, handler); }
166 
167 	/// Adds a new route for requests matching the specified pattern, regardless of their HTTP verb.
168 	URLRouter any(Handler)(string url_match, Handler handler)
169 	{
170 		import std.traits;
171 		static HTTPMethod[] all_methods = [EnumMembers!HTTPMethod];
172 		foreach(immutable method; all_methods)
173 			match(method, url_match, handler);
174 
175 		return this;
176 	}
177 	/// ditto
178 	URLRouter any(string url_match, HTTPServerRequestDelegate handler) { return any!HTTPServerRequestDelegate(url_match, handler); }
179 
180 
181 	/** Rebuilds the internal matching structures to account for newly added routes.
182 
183 		This should be used after a lot of routes have been added to the router, to
184 		force eager computation of the match structures. The alternative is to
185 		let the router lazily compute the structures when the first request happens,
186 		which can delay this request.
187 	*/
188 	void rebuild()
189 	{
190 		m_routes.rebuildGraph();
191 	}
192 
193 	/// Handles a HTTP request by dispatching it to the registered route handlers.
194 	void handleRequest(HTTPServerRequest req, HTTPServerResponse res)
195 	{
196 		auto method = req.method;
197 
198 		string calcBasePath()
199 		@safe {
200 			import vibe.core.path : InetPath, relativeToWeb;
201 			auto p = InetPath(prefix.length ? prefix : "/");
202 			p.endsWithSlash = true;
203 			return p.relativeToWeb(InetPath(req.path)).toString();
204 		}
205 
206 		auto path = req.path;
207 		if (path.length < m_prefix.length || path[0 .. m_prefix.length] != m_prefix) return;
208 		path = path[m_prefix.length .. $];
209 
210 		while (true) {
211 			bool done = m_routes.match(path, (ridx, scope values) @safe {
212 				auto r = () @trusted { return &m_routes.getTerminalData(ridx); } ();
213 				if (r.method != method) return false;
214 
215 				logDebugV("route match: %s -> %s %s %s", req.path, r.method, r.pattern, values);
216 				foreach (i, v; values) req.params[m_routes.getTerminalVarNames(ridx)[i]] = v;
217 				if (m_computeBasePath) req.params["routerRootDir"] = calcBasePath();
218 				r.cb(req, res);
219 				return res.headerWritten;
220 			});
221 			if (done) return;
222 
223 			if (method == HTTPMethod.HEAD) method = HTTPMethod.GET;
224 			else break;
225 		}
226 
227 		logDebug("no route match: %s %s", req.method, req.requestURL);
228 	}
229 
230 	/// Returns all registered routes as const AA
231 	const(Route)[] getAllRoutes()
232 	{
233 		auto routes = new Route[m_routes.terminalCount];
234 		foreach (i, ref r; routes)
235 			r = m_routes.getTerminalData(i);
236 		return routes;
237 	}
238 
239 	template isValidHandler(Handler) {
240 		@system {
241 			alias USDel = void delegate(HTTPServerRequest, HTTPServerResponse) @system;
242 			alias USFun = void function(HTTPServerRequest, HTTPServerResponse) @system;
243 			alias USDelS = void delegate(scope HTTPServerRequest, scope HTTPServerResponse) @system;
244 			alias USFunS = void function(scope HTTPServerRequest, scope HTTPServerResponse) @system;
245 		}
246 
247 		static if (
248 				is(Handler : HTTPServerRequestDelegate) ||
249 				is(Handler : HTTPServerRequestFunction) ||
250 				is(Handler : HTTPServerRequestHandler) ||
251 				is(Handler : HTTPServerRequestDelegateS) ||
252 				is(Handler : HTTPServerRequestFunctionS) ||
253 				is(Handler : HTTPServerRequestHandlerS)
254 			)
255 		{
256 			enum isValidHandler = true;
257 		} else static if (
258 				is(Handler : USDel) || is(Handler : USFun) ||
259 				is(Handler : USDelS) || is(Handler : USFunS)
260 			)
261 		{
262 			enum isValidHandler = true;
263 		} else {
264 			enum isValidHandler = false;
265 		}
266 	}
267 
268 	static void delegate(HTTPServerRequest, HTTPServerResponse) @safe handlerDelegate(Handler)(Handler handler)
269 	{
270 		import std.traits : isFunctionPointer;
271 		static if (isFunctionPointer!Handler) return handlerDelegate(() @trusted { return toDelegate(handler); } ());
272 		else static if (is(Handler == class) || is(Handler == interface)) return &handler.handleRequest;
273 		else static if (__traits(compiles, () @safe { handler(HTTPServerRequest.init, HTTPServerResponse.init); } ())) return handler;
274 		else return (req, res) @trusted { handler(req, res); };
275 	}
276 
277 	unittest {
278 		static assert(isValidHandler!HTTPServerRequestFunction);
279 		static assert(isValidHandler!HTTPServerRequestDelegate);
280 		static assert(isValidHandler!HTTPServerRequestHandler);
281 		static assert(isValidHandler!HTTPServerRequestFunctionS);
282 		static assert(isValidHandler!HTTPServerRequestDelegateS);
283 		static assert(isValidHandler!HTTPServerRequestHandlerS);
284 		static assert(isValidHandler!(void delegate(HTTPServerRequest req, HTTPServerResponse res) @system));
285 		static assert(isValidHandler!(void function(HTTPServerRequest req, HTTPServerResponse res) @system));
286 		static assert(isValidHandler!(void delegate(scope HTTPServerRequest req, scope HTTPServerResponse res) @system));
287 		static assert(isValidHandler!(void function(scope HTTPServerRequest req, scope HTTPServerResponse res) @system));
288 		static assert(!isValidHandler!(int delegate(HTTPServerRequest req, HTTPServerResponse res) @system));
289 		static assert(!isValidHandler!(int delegate(HTTPServerRequest req, HTTPServerResponse res) @safe));
290 		void test(H)(H h)
291 		{
292 			static assert(isValidHandler!H);
293 		}
294 		test((HTTPServerRequest req, HTTPServerResponse res) {});
295 	}
296 }
297 
298 ///
299 @safe unittest {
300 	import vibe.http.fileserver;
301 
302 	void addGroup(HTTPServerRequest req, HTTPServerResponse res)
303 	{
304 		// Route variables are accessible via the params map
305 		logInfo("Getting group %s for user %s.", req.params["groupname"], req.params["username"]);
306 	}
307 
308 	void deleteUser(HTTPServerRequest req, HTTPServerResponse res)
309 	{
310 		// ...
311 	}
312 
313 	void auth(HTTPServerRequest req, HTTPServerResponse res)
314 	{
315 		// TODO: check req.session to see if a user is logged in and
316 		//       write an error page or throw an exception instead.
317 	}
318 
319 	void setup()
320 	{
321 		auto router = new URLRouter;
322 		// Matches all GET requests for /users/*/groups/* and places
323 		// the place holders in req.params as 'username' and 'groupname'.
324 		router.get("/users/:username/groups/:groupname", &addGroup);
325 
326 		// Matches all requests. This can be useful for authorization and
327 		// similar tasks. The auth method will only write a response if the
328 		// user is _not_ authorized. Otherwise, the router will fall through
329 		// and continue with the following routes.
330 		router.any("*", &auth);
331 
332 		// Matches a POST request
333 		router.post("/users/:username/delete", &deleteUser);
334 
335 		// Matches all GET requests in /static/ such as /static/img.png or
336 		// /static/styles/sty.css
337 		router.get("/static/*", serveStaticFiles("public/"));
338 
339 		// Setup a HTTP server...
340 		auto settings = new HTTPServerSettings;
341 		// ...
342 
343 		// The router can be directly passed to the listenHTTP function as
344 		// the main request handler.
345 		listenHTTP(settings, router);
346 	}
347 }
348 
349 /** Using nested routers to map components to different sub paths. A component
350 	could for example be an embedded blog engine.
351 */
352 @safe unittest {
353 	// some embedded component:
354 
355 	void showComponentHome(HTTPServerRequest req, HTTPServerResponse res)
356 	{
357 		// ...
358 	}
359 
360 	void showComponentUser(HTTPServerRequest req, HTTPServerResponse res)
361 	{
362 		// ...
363 	}
364 
365 	void registerComponent(URLRouter router)
366 	{
367 		router.get("/", &showComponentHome);
368 		router.get("/users/:user", &showComponentUser);
369 	}
370 
371 	// main application:
372 
373 	void showHome(HTTPServerRequest req, HTTPServerResponse res)
374 	{
375 		// ...
376 	}
377 
378 	void setup()
379 	{
380 		auto c1router = new URLRouter("/component1");
381 		registerComponent(c1router);
382 
383 		auto mainrouter = new URLRouter;
384 		mainrouter.get("/", &showHome);
385 		// forward all unprocessed requests to the component router
386 		mainrouter.any("*", c1router);
387 
388 		// now the following routes will be matched:
389 		// / -> showHome
390 		// /component1/ -> showComponentHome
391 		// /component1/users/:user -> showComponentUser
392 
393 		// Start the HTTP server
394 		auto settings = new HTTPServerSettings;
395 		// ...
396 		listenHTTP(settings, mainrouter);
397 	}
398 }
399 
400 @safe unittest { // issue #1668
401 	auto r = new URLRouter;
402 	r.get("/", (req, res) {
403 		if ("foo" in req.headers)
404 			res.writeBody("bar");
405 	});
406 
407 	r.get("/", (scope req, scope res) {
408 		if ("foo" in req.headers)
409 			res.writeBody("bar");
410 	});
411 	r.get("/", (req, res) {});
412 	r.post("/", (req, res) {});
413 	r.put("/", (req, res) {});
414 	r.delete_("/", (req, res) {});
415 	r.patch("/", (req, res) {});
416 	r.any("/", (req, res) {});
417 }
418 
419 @safe unittest { // issue #1866
420 	auto r = new URLRouter;
421 	r.match(HTTPMethod.HEAD, "/foo", (scope req, scope res) { res.writeVoidBody; });
422 	r.match(HTTPMethod.HEAD, "/foo", (req, res) { res.writeVoidBody; });
423 	r.match(HTTPMethod.HEAD, "/foo", (scope HTTPServerRequest req, scope HTTPServerResponse res) { res.writeVoidBody; });
424 	r.match(HTTPMethod.HEAD, "/foo", (HTTPServerRequest req, HTTPServerResponse res) { res.writeVoidBody; });
425 
426 	auto r2 = new URLRouter;
427 	r.match(HTTPMethod.HEAD, "/foo", r2);
428 }
429 
430 @safe unittest {
431 	import vibe.inet.url;
432 
433 	auto router = new URLRouter;
434 	string result;
435 	void a(HTTPServerRequest req, HTTPServerResponse) { result ~= "A"; }
436 	void b(HTTPServerRequest req, HTTPServerResponse) { result ~= "B"; }
437 	void c(HTTPServerRequest req, HTTPServerResponse) { assert(req.params["test"] == "x", "Wrong variable contents: "~req.params["test"]); result ~= "C"; }
438 	void d(HTTPServerRequest req, HTTPServerResponse) { assert(req.params["test"] == "y", "Wrong variable contents: "~req.params["test"]); result ~= "D"; }
439 	router.get("/test", &a);
440 	router.post("/test", &b);
441 	router.get("/a/:test", &c);
442 	router.get("/a/:test/", &d);
443 
444 	auto res = createTestHTTPServerResponse();
445 	router.handleRequest(createTestHTTPServerRequest(URL("http://localhost/")), res);
446 	assert(result == "", "Matched for non-existent / path");
447 	router.handleRequest(createTestHTTPServerRequest(URL("http://localhost/test")), res);
448 	assert(result == "A", "Didn't match a simple GET request");
449 	router.handleRequest(createTestHTTPServerRequest(URL("http://localhost/test"), HTTPMethod.POST), res);
450 	assert(result == "AB", "Didn't match a simple POST request");
451 	router.handleRequest(createTestHTTPServerRequest(URL("http://localhost/a/"), HTTPMethod.GET), res);
452 	assert(result == "AB", "Matched empty variable. "~result);
453 	router.handleRequest(createTestHTTPServerRequest(URL("http://localhost/a/x"), HTTPMethod.GET), res);
454 	assert(result == "ABC", "Didn't match a trailing 1-character var.");
455 	// currently fails due to Path not accepting "//"
456 	//router.handleRequest(createTestHTTPServerRequest(URL("http://localhost/a//"), HTTPMethod.GET), res);
457 	//assert(result == "ABC", "Matched empty string or slash as var. "~result);
458 	router.handleRequest(createTestHTTPServerRequest(URL("http://localhost/a/y/"), HTTPMethod.GET), res);
459 	assert(result == "ABCD", "Didn't match 1-character infix variable.");
460 }
461 
462 @safe unittest {
463 	import vibe.inet.url;
464 
465 	auto router = new URLRouter("/test");
466 
467 	string result;
468 	void a(HTTPServerRequest req, HTTPServerResponse) { result ~= "A"; }
469 	void b(HTTPServerRequest req, HTTPServerResponse) { result ~= "B"; }
470 	router.get("/x", &a);
471 	router.get("/y", &b);
472 
473 	auto res = createTestHTTPServerResponse();
474 	router.handleRequest(createTestHTTPServerRequest(URL("http://localhost/test")), res);
475 	assert(result == "");
476 	router.handleRequest(createTestHTTPServerRequest(URL("http://localhost/test/x")), res);
477 	assert(result == "A");
478 	router.handleRequest(createTestHTTPServerRequest(URL("http://localhost/test/y")), res);
479 	assert(result == "AB");
480 }
481 
482 @safe unittest {
483 	string ensureMatch(string pattern, string local_uri, string[string] expected_params = null)
484 	{
485 		import vibe.inet.url : URL;
486 		string ret = local_uri ~ " did not match " ~ pattern;
487 		auto r = new URLRouter;
488 		r.get(pattern, (req, res) {
489 			ret = null;
490 			foreach (k, v; expected_params) {
491 				if (k !in req.params) { ret = "Parameter "~k~" was not matched."; return; }
492 				if (req.params[k] != v) { ret = "Parameter "~k~" is '"~req.params[k]~"' instead of '"~v~"'."; return; }
493 			}
494 		});
495 		auto req = createTestHTTPServerRequest(URL("http://localhost"~local_uri));
496 		auto res = createTestHTTPServerResponse();
497 		r.handleRequest(req, res);
498 		return ret;
499 	}
500 
501 	assert(ensureMatch("/foo bar/", "/foo%20bar/") is null);   // normalized pattern: "/foo%20bar/"
502 	//assert(ensureMatch("/foo%20bar/", "/foo%20bar/") is null); // normalized pattern: "/foo%20bar/"
503 	assert(ensureMatch("/foo/bar/", "/foo/bar/") is null);     // normalized pattern: "/foo/bar/"
504 	//assert(ensureMatch("/foo/bar/", "/foo%2fbar/") !is null);
505 	//assert(ensureMatch("/foo%2fbar/", "/foo%2fbar/") is null); // normalized pattern: "/foo%2Fbar/"
506 	//assert(ensureMatch("/foo%2Fbar/", "/foo%2fbar/") is null); // normalized pattern: "/foo%2Fbar/"
507 	//assert(ensureMatch("/foo%2fbar/", "/foo%2Fbar/") is null);
508 	//assert(ensureMatch("/foo%2fbar/", "/foo/bar/") !is null);
509 	//assert(ensureMatch("/:foo/", "/foo%2Fbar/", ["foo": "foo/bar"]) is null);
510 	assert(ensureMatch("/:foo/", "/foo/bar/") !is null);
511 }
512 
513 unittest { // issue #2561
514 	import vibe.http.server : createTestHTTPServerRequest, createTestHTTPServerResponse;
515 	import vibe.inet.url : URL;
516 	import vibe.stream.memory : createMemoryOutputStream;
517 
518 	Route[] routes = [
519 		Route(HTTPMethod.PUT, "/public/devices/commandList"),
520 		Route(HTTPMethod.PUT, "/public/devices/logicStateList"),
521 		Route(HTTPMethod.OPTIONS, "/public/devices/commandList"),
522 		Route(HTTPMethod.OPTIONS, "/public/devices/logicStateList"),
523 		Route(HTTPMethod.PUT, "/public/mnemoschema"),
524 		Route(HTTPMethod.PUT, "/public/static"),
525 		Route(HTTPMethod.PUT, "/public/dynamic"),
526 		Route(HTTPMethod.PUT, "/public/info"),
527 		Route(HTTPMethod.PUT, "/public/info-network"),
528 		Route(HTTPMethod.PUT, "/public/events"),
529 		Route(HTTPMethod.PUT, "/public/eventList"),
530 		Route(HTTPMethod.PUT, "/public/availBatteryModels"),
531 		Route(HTTPMethod.OPTIONS, "/public/availBatteryModels"),
532 		Route(HTTPMethod.OPTIONS, "/public/dynamic"),
533 		Route(HTTPMethod.OPTIONS, "/public/eventList"),
534 		Route(HTTPMethod.OPTIONS, "/public/events"),
535 		Route(HTTPMethod.OPTIONS, "/public/info"),
536 		Route(HTTPMethod.OPTIONS, "/public/info-network"),
537 		Route(HTTPMethod.OPTIONS, "/public/mnemoschema"),
538 		Route(HTTPMethod.OPTIONS, "/public/static"),
539 		Route(HTTPMethod.PUT, "/settings/admin/getinfo"),
540 		Route(HTTPMethod.PUT, "/settings/admin/setconf"),
541 		Route(HTTPMethod.PUT, "/settings/admin/checksetaccess"),
542 		Route(HTTPMethod.OPTIONS, "/settings/admin/checksetaccess"),
543 		Route(HTTPMethod.OPTIONS, "/settings/admin/getinfo"),
544 		Route(HTTPMethod.OPTIONS, "/settings/admin/setconf"),
545 	];
546 
547 	auto router = new URLRouter;
548 
549 	foreach (r; routes)
550 		router.match(r.method, r.pattern, (req, res) {
551 			res.writeBody("OK");
552 		});
553 
554 	{ // make sure unmatched routes are not handled by the router
555 		auto req = createTestHTTPServerRequest(URL("http://localhost/foobar"), HTTPMethod.PUT);
556 		auto res = createTestHTTPServerResponse();
557 		router.handleRequest(req, res);
558 		assert(!res.headerWritten);
559 	}
560 
561 	// ensure all routes are matched
562 	foreach (r; routes) {
563 		auto url = URL("http://localhost"~r.pattern);
564 		auto output = createMemoryOutputStream();
565 		auto req = createTestHTTPServerRequest(url, r.method);
566 		auto res = createTestHTTPServerResponse(output, null, TestHTTPResponseMode.bodyOnly);
567 		router.handleRequest(req, res);
568 		//assert(res.headerWritten);
569 		assert(output.data == "OK");
570 	}
571 }
572 
573 
574 /**
575 	Convenience abstraction for a single `URLRouter` route.
576 
577 	See `URLRouter.route` for a usage example.
578 */
579 struct URLRoute {
580 @safe:
581 
582 	URLRouter router;
583 	string path;
584 
585 	ref URLRoute get(Handler)(Handler h) { router.get(path, h); return this; }
586 	ref URLRoute post(Handler)(Handler h) { router.post(path, h); return this; }
587 	ref URLRoute put(Handler)(Handler h) { router.put(path, h); return this; }
588 	ref URLRoute delete_(Handler)(Handler h) { router.delete_(path, h); return this; }
589 	ref URLRoute patch(Handler)(Handler h) { router.patch(path, h); return this; }
590 	ref URLRoute any(Handler)(Handler h) { router.any(path, h); return this; }
591 	ref URLRoute match(Handler)(HTTPMethod method, Handler h) { router.match(method, path, h); return this; }
592 }
593 
594 
595 private enum maxRouteParameters = 64;
596 
597 private struct Route {
598 	HTTPMethod method;
599 	string pattern;
600 	HTTPServerRequestDelegate cb;
601 }
602 
603 private string skipPathNode(string str, ref size_t idx)
604 @safe {
605 	size_t start = idx;
606 	while( idx < str.length && str[idx] != '/' ) idx++;
607 	return str[start .. idx];
608 }
609 
610 private string skipPathNode(ref string str)
611 @safe {
612 	size_t idx = 0;
613 	auto ret = skipPathNode(str, idx);
614 	str = str[idx .. $];
615 	return ret;
616 }
617 
618 private struct MatchTree(T) {
619 @safe:
620 
621 	import std.algorithm : countUntil;
622 	import std.array : array;
623 
624 	private {
625 		alias NodeIndex = uint;
626 		alias TerminalTagIndex = uint;
627 		alias TerminalIndex = ushort;
628 		alias VarIndex = ushort;
629 
630 		struct Node {
631 			TerminalTagIndex terminalsStart; // slice into m_terminalTags
632 			TerminalTagIndex terminalsEnd;
633 			NodeIndex[ubyte.max+1] edges = NodeIndex.max; // character -> index into m_nodes
634 		}
635 		struct TerminalTag {
636 			TerminalIndex index; // index into m_terminals array
637 			VarIndex var = VarIndex.max; // index into Terminal.varNames/varValues or VarIndex.max
638 		}
639 		struct Terminal {
640 			string pattern;
641 			T data;
642 			string[] varNames;
643 			VarIndex[NodeIndex] varMap;
644 		}
645 		Node[] m_nodes; // all nodes as a single array
646 		TerminalTag[] m_terminalTags;
647 		Terminal[] m_terminals;
648 
649 		enum TerminalChar = 0;
650 		bool m_upToDate = false;
651 	}
652 
653 	@property size_t terminalCount() const { return m_terminals.length; }
654 
655 	void addTerminal(string pattern, T data)
656 	{
657 		assert(m_terminals.length < TerminalIndex.max, "Attempt to register too many routes.");
658 		m_terminals ~= Terminal(pattern, data, null, null);
659 		m_upToDate = false;
660 	}
661 
662 	bool match(string text, scope bool delegate(size_t terminal, scope string[] vars) @safe del)
663 	{
664 		// lazily update the match graph
665 		if (!m_upToDate) rebuildGraph();
666 
667 		return doMatch(text, del);
668 	}
669 
670 	const(string)[] getTerminalVarNames(size_t terminal) const { return m_terminals[terminal].varNames; }
671 	ref inout(T) getTerminalData(size_t terminal) inout { return m_terminals[terminal].data; }
672 
673 	void print()
674 	const {
675 		import std.algorithm : map;
676 		import std.array : join;
677 		import std.conv : to;
678 		import std.range : iota;
679 		import std.string : format;
680 
681 		logInfo("Nodes:");
682 		foreach (i, n; m_nodes) {
683 			logInfo("  %s %s", i, m_terminalTags[n.terminalsStart .. n.terminalsEnd]
684 				.map!(t => format("T%s%s", t.index, t.var != VarIndex.max ? "("~m_terminals[t.index].varNames[t.var]~")" : "")).join(" "));
685 			//logInfo("  %s %s-%s", i, n.terminalsStart, n.terminalsEnd);
686 
687 
688 			static string mapChar(ubyte ch) {
689 				if (ch == TerminalChar) return "$";
690 				if (ch >= '0' && ch <= '9') return to!string(cast(dchar)ch);
691 				if (ch >= 'a' && ch <= 'z') return to!string(cast(dchar)ch);
692 				if (ch >= 'A' && ch <= 'Z') return to!string(cast(dchar)ch);
693 				if (ch == '/') return "/";
694 				if (ch == '^') return "^";
695 				return ch.to!string;
696 			}
697 
698 			void printRange(uint node, ubyte from, ubyte to)
699 			{
700 				if (to - from <= 10) logInfo("    %s -> %s", iota(from, cast(uint)to+1).map!(ch => mapChar(cast(ubyte)ch)).join("|"), node);
701 				else logInfo("    %s-%s -> %s", mapChar(from), mapChar(to), node);
702 			}
703 
704 			auto last_to = NodeIndex.max;
705 			ubyte last_ch = 0;
706 			foreach (ch, e; n.edges)
707 				if (e != last_to) {
708 					if (last_to != NodeIndex.max)
709 						printRange(last_to, last_ch, cast(ubyte)(ch-1));
710 					last_ch = cast(ubyte)ch;
711 					last_to = e;
712 				}
713 			if (last_to != NodeIndex.max)
714 				printRange(last_to, last_ch, ubyte.max);
715 		}
716 	}
717 
718 	private bool doMatch(string text, scope bool delegate(size_t terminal, scope string[] vars) @safe del)
719 	const {
720 		string[maxRouteParameters] vars_buf;// = void;
721 
722 		import std.algorithm : canFind;
723 
724 		// first, determine the end node, if any
725 		auto n = matchTerminals(text);
726 		if (!n) return false;
727 
728 		// then, go through the terminals and match their variables
729 		foreach (ref t; m_terminalTags[n.terminalsStart .. n.terminalsEnd]) {
730 			auto term = &m_terminals[t.index];
731 			auto vars = vars_buf[0 .. term.varNames.length];
732 			matchVars(vars, term, text);
733 			if (vars.canFind!(v => v.length == 0)) continue; // all variables must be non-empty to match
734 			if (del(t.index, vars)) return true;
735 		}
736 		return false;
737 	}
738 
739 	private inout(Node)* matchTerminals(string text)
740 	inout {
741 		if (!m_nodes.length) return null;
742 
743 		auto n = &m_nodes[0];
744 
745 		// follow the path through the match graph
746 		foreach (i, char ch; text) {
747 			auto nidx = n.edges[cast(size_t)ch];
748 			if (nidx == NodeIndex.max) return null;
749 			n = &m_nodes[nidx];
750 		}
751 
752 		// finally, find a matching terminal node
753 		auto nidx = n.edges[TerminalChar];
754 		if (nidx == NodeIndex.max) return null;
755 		n = &m_nodes[nidx];
756 		return n;
757 	}
758 
759 	private void matchVars(string[] dst, in Terminal* term, string text)
760 	const {
761 		NodeIndex nidx = 0;
762 		VarIndex activevar = VarIndex.max;
763 		size_t activevarstart;
764 
765 		dst[] = null;
766 
767 		// folow the path throgh the match graph
768 		foreach (i, char ch; text) {
769 			auto var = term.varMap.get(nidx, VarIndex.max);
770 
771 			// detect end of variable
772 			if (var != activevar && activevar != VarIndex.max) {
773 				dst[activevar] = text[activevarstart .. i-1];
774 				activevar = VarIndex.max;
775 			}
776 
777 			// detect beginning of variable
778 			if (var != VarIndex.max && activevar == VarIndex.max) {
779 				activevar = var;
780 				activevarstart = i;
781 			}
782 
783 			nidx = m_nodes[nidx].edges[cast(ubyte)ch];
784 			assert(nidx != NodeIndex.max);
785 		}
786 
787 		// terminate any active varible with the end of the input string or with the last character
788 		auto var = term.varMap.get(nidx, VarIndex.max);
789 		if (activevar != VarIndex.max) dst[activevar] = text[activevarstart .. (var == activevar ? $ : $-1)];
790 	}
791 
792 	private void rebuildGraph()
793 	@trusted {
794 		import std.array : appender;
795 		import std.conv : to;
796 
797 		if (m_upToDate) return;
798 		m_upToDate = true;
799 
800 		m_nodes = null;
801 		m_terminalTags = null;
802 
803 		if (!m_terminals.length) return;
804 
805 		MatchGraphBuilder builder;
806 		foreach (i, ref t; m_terminals) {
807 			t.varNames = builder.insert(t.pattern, i.to!TerminalIndex);
808 			assert(t.varNames.length <= VarIndex.max, "Too many variables in route.");
809 		}
810 		//builder.print();
811 		builder.disambiguate();
812 
813 		auto nodemap = new NodeIndex[builder.m_nodes.length];
814 		nodemap[] = NodeIndex.max;
815 
816 		auto nodes = appender!(Node[]);
817 		nodes.reserve(1024);
818 		auto termtags = appender!(TerminalTag[]);
819 		termtags.reserve(1024);
820 
821 		NodeIndex process(NodeIndex n)
822 		{
823 			import std.algorithm : canFind;
824 
825 			if (nodemap[n] != NodeIndex.max) return nodemap[n];
826 			auto nmidx = cast(NodeIndex)nodes.data.length;
827 			nodemap[n] = nmidx;
828 			nodes.put(Node.init);
829 
830 			Node nn;
831 			nn.terminalsStart = termtags.data.length.to!TerminalTagIndex;
832 			foreach (t; builder.m_nodes[n].terminals) {
833 				auto var = cast(VarIndex)t.var;
834 				assert(!termtags.data[nn.terminalsStart .. $].canFind!(u => u.index == t.index && u.var == var));
835 				termtags ~= TerminalTag(cast(TerminalIndex)t.index, var);
836 				if (var != VarIndex.max)
837 					m_terminals[t.index].varMap[nmidx] = var;
838 			}
839 			nn.terminalsEnd = termtags.data.length.to!TerminalTagIndex;
840 			foreach (ch, targets; builder.m_nodes[n].edges)
841 				foreach (to; builder.m_edgeEntries.getItems(targets))
842 					nn.edges[ch] = process(to);
843 
844 			nodes.data[nmidx] = nn;
845 
846 			return nmidx;
847 		}
848 		assert(builder.m_edgeEntries.hasLength(builder.m_nodes[0].edges['^'], 1),
849 			"Graph must be disambiguated before purging.");
850 		process(builder.m_edgeEntries.getItems(builder.m_nodes[0].edges['^']).front);
851 
852 		m_nodes = nodes.data;
853 		m_terminalTags = termtags.data;
854 
855 		logDebug("Match tree has %s (of %s in the builder) nodes, %s terminals", m_nodes.length, builder.m_nodes.length, m_terminals.length);
856 	}
857 }
858 
859 unittest {
860 	import std.string : format;
861 	MatchTree!int m;
862 
863 	void testMatch(string str, size_t[] terms, string[] vars)
864 	{
865 		size_t[] mterms;
866 		string[] mvars;
867 		m.match(str, (t, scope vals) {
868 			mterms ~= t;
869 			mvars ~= vals;
870 			return false;
871 		});
872 		assert(mterms == terms, format("Mismatched terminals: %s (expected %s)", mterms, terms));
873 		assert(mvars == vars, format("Mismatched variables; %s (expected %s)", mvars, vars));
874 	}
875 
876 	m.addTerminal("a", 0);
877 	m.addTerminal("b", 0);
878 	m.addTerminal("ab", 0);
879 	m.rebuildGraph();
880 	assert(m.getTerminalVarNames(0) == []);
881 	assert(m.getTerminalVarNames(1) == []);
882 	assert(m.getTerminalVarNames(2) == []);
883 	testMatch("a", [0], []);
884 	testMatch("ab", [2], []);
885 	testMatch("abc", [], []);
886 	testMatch("b", [1], []);
887 
888 	m = MatchTree!int.init;
889 	m.addTerminal("ab", 0);
890 	m.addTerminal("a*", 0);
891 	m.rebuildGraph();
892 	assert(m.getTerminalVarNames(0) == []);
893 	assert(m.getTerminalVarNames(1) == []);
894 	testMatch("a", [1], []);
895 	testMatch("ab", [0, 1], []);
896 	testMatch("abc", [1], []);
897 
898 	m = MatchTree!int.init;
899 	m.addTerminal("ab", 0);
900 	m.addTerminal("a:var", 0);
901 	m.rebuildGraph();
902 	assert(m.getTerminalVarNames(0) == []);
903 	assert(m.getTerminalVarNames(1) == ["var"], format("%s", m.getTerminalVarNames(1)));
904 	testMatch("a", [], []); // vars may not be empty
905 	testMatch("ab", [0, 1], ["b"]);
906 	testMatch("abc", [1], ["bc"]);
907 
908 	m = MatchTree!int.init;
909 	m.addTerminal(":var1/:var2", 0);
910 	m.addTerminal("a/:var3", 0);
911 	m.addTerminal(":var4/b", 0);
912 	m.rebuildGraph();
913 	assert(m.getTerminalVarNames(0) == ["var1", "var2"]);
914 	assert(m.getTerminalVarNames(1) == ["var3"]);
915 	assert(m.getTerminalVarNames(2) == ["var4"]);
916 	testMatch("a", [], []);
917 	testMatch("a/a", [0, 1], ["a", "a", "a"]);
918 	testMatch("a/b", [0, 1, 2], ["a", "b", "b", "a"]);
919 	testMatch("a/bc", [0, 1], ["a", "bc", "bc"]);
920 	testMatch("ab/b", [0, 2], ["ab", "b", "ab"]);
921 	testMatch("ab/bc", [0], ["ab", "bc"]);
922 
923 	m = MatchTree!int.init;
924 	m.addTerminal(":var1/", 0);
925 	m.rebuildGraph();
926 	assert(m.getTerminalVarNames(0) == ["var1"]);
927 	testMatch("ab/", [0], ["ab"]);
928 	testMatch("ab", [], []);
929 	testMatch("/ab", [], []);
930 	testMatch("a/b", [], []);
931 	testMatch("ab//", [], []);
932 }
933 
934 
935 private struct MatchGraphBuilder {
936 @safe:
937 	import std.container.array : Array;
938 	import std.array : array;
939 	import std.algorithm : filter;
940 	import std.string : format;
941 
942 	alias NodeIndex = uint;
943 	alias TerminalIndex = ushort;
944 	alias VarIndex = ushort;
945 	alias NodeSet = LinkedSetBacking!NodeIndex.Handle;
946 
947 	private {
948 		enum TerminalChar = 0;
949 		struct TerminalTag {
950 			TerminalIndex index;
951 			VarIndex var = VarIndex.max;
952 		}
953 		struct Node {
954 			Array!TerminalTag terminals;
955 			NodeSet[ubyte.max+1] edges;
956 		}
957 		Array!Node m_nodes;
958 		LinkedSetBacking!NodeIndex m_edgeEntries;
959 	}
960 
961 	@disable this(this);
962 
963 	string[] insert(string pattern, TerminalIndex terminal)
964 	{
965 		import std.algorithm : canFind;
966 
967 		auto full_pattern = pattern;
968 		string[] vars;
969 		if (!m_nodes.length) addNode();
970 
971 		// create start node and connect to zero node
972 		auto nidx = addNode();
973 		addEdge(0, nidx, '^', terminal);
974 
975 		while (pattern.length) {
976 			auto ch = pattern[0];
977 			if (ch == '*') {
978 				assert(pattern.length == 1, "Asterisk is only allowed at the end of a pattern: "~full_pattern);
979 				pattern = null;
980 
981 				foreach (v; ubyte.min .. ubyte.max+1) {
982 					if (v == TerminalChar) continue;
983 					addEdge(nidx, nidx, cast(ubyte)v, terminal);
984 				}
985 			} else if (ch == ':') {
986 				pattern = pattern[1 .. $];
987 				auto name = skipPathNode(pattern);
988 				assert(name.length > 0, "Missing placeholder name: "~full_pattern);
989 				assert(!vars.canFind(name), "Duplicate placeholder name ':"~name~"': '"~full_pattern~"'");
990 				auto varidx = cast(VarIndex)vars.length;
991 				vars ~= name;
992 				assert(!pattern.length || (pattern[0] != '*' && pattern[0] != ':'),
993 					"Cannot have two placeholders directly follow each other.");
994 
995 				foreach (v; ubyte.min .. ubyte.max+1) {
996 					if (v == TerminalChar || v == '/') continue;
997 					addEdge(nidx, nidx, cast(ubyte)v, terminal, varidx);
998 				}
999 			} else {
1000 				nidx = addEdge(nidx, ch, terminal);
1001 				pattern = pattern[1 .. $];
1002 			}
1003 		}
1004 
1005 		addEdge(nidx, TerminalChar, terminal);
1006 		return vars;
1007 	}
1008 
1009 	void disambiguate()
1010 	@trusted {
1011 		import std.algorithm : map, sum;
1012 		import std.array : appender, join;
1013 
1014 		//logInfo("Disambiguate with %s initial nodes", m_nodes.length);
1015 		if (!m_nodes.length) return;
1016 
1017 		import vibe.utils.hashmap;
1018 		HashMap!(LinkedSetHash, NodeIndex) combined_nodes;
1019 		Array!bool visited;
1020 		visited.length = m_nodes.length * 2;
1021 		Stack!NodeIndex node_stack;
1022 		node_stack.reserve(m_nodes.length);
1023 		node_stack.push(0);
1024 		while (!node_stack.empty) {
1025 			auto n = node_stack.pop();
1026 
1027 			while (n >= visited.length) visited.length = visited.length * 2;
1028 			if (visited[n]) continue;
1029 			//logInfo("Disambiguate %s (stack=%s)", n, node_stack.fill);
1030 			visited[n] = true;
1031 
1032 			foreach (ch; ubyte.min .. ubyte.max+1) {
1033 				auto chnodes = m_nodes[n].edges[ch];
1034 				LinkedSetHash chhash = m_edgeEntries.getHash(chnodes);
1035 
1036 				// handle trivial cases
1037 				if (m_edgeEntries.hasMaxLength(chnodes, 1))
1038 					continue;
1039 
1040 				// generate combined state for ambiguous edges
1041 				if (auto pn = () @trusted { return chhash in combined_nodes; } ()) {
1042 					m_nodes[n].edges[ch] = m_edgeEntries.create(*pn);
1043 					assert(m_edgeEntries.hasLength(m_nodes[n].edges[ch], 1));
1044 					continue;
1045 				}
1046 
1047 				// for new combinations, create a new node
1048 				NodeIndex ncomb = addNode();
1049 				combined_nodes[chhash] = ncomb;
1050 
1051 				// write all edges
1052 				size_t idx = 0;
1053 				foreach (to_ch; ubyte.min .. ubyte.max+1) {
1054 					auto e = &m_nodes[ncomb].edges[to_ch];
1055 					foreach (chn; m_edgeEntries.getItems(chnodes))
1056 						m_edgeEntries.insert(e, m_edgeEntries.getItems(m_nodes[chn].edges[to_ch]));
1057 				}
1058 
1059 				// add terminal indices
1060 				foreach (chn; m_edgeEntries.getItems(chnodes))
1061 					foreach (t; m_nodes[chn].terminals)
1062 						addTerminal(ncomb, t.index, t.var);
1063 				foreach (i; 1 .. m_nodes[ncomb].terminals.length)
1064 					assert(m_nodes[ncomb].terminals[0] != m_nodes[ncomb].terminals[i]);
1065 
1066 				m_nodes[n].edges[ch] = m_edgeEntries.create(ncomb);
1067 				assert(m_edgeEntries.hasLength(m_nodes[n].edges[ch], 1));
1068 			}
1069 
1070 			// process nodes recursively
1071 			foreach (ch; ubyte.min .. ubyte.max+1) {
1072 				// should only have single out-edges now
1073 				assert(m_edgeEntries.hasMaxLength(m_nodes[n].edges[ch], 1));
1074 				foreach (e; m_edgeEntries.getItems(m_nodes[n].edges[ch]))
1075 					node_stack.push(e);
1076 			}
1077 		}
1078 
1079 		import std.algorithm.sorting : sort;
1080 		foreach (ref n; m_nodes)
1081 			n.terminals[].sort!((a, b) => a.index < b.index)();
1082 
1083 		debug logDebug("Disambiguate done: %s nodes, %s max stack size", m_nodes.length, node_stack.maxSize);
1084 	}
1085 
1086 	void print()
1087 	const @trusted {
1088 		import std.algorithm : map;
1089 		import std.array : join;
1090 		import std.conv : to;
1091 		import std.string : format;
1092 
1093 		logInfo("Nodes:");
1094 		size_t i = 0;
1095 		foreach (n; m_nodes) {
1096 			string mapChar(ubyte ch) {
1097 				if (ch == TerminalChar) return "$";
1098 				if (ch >= '0' && ch <= '9') return to!string(cast(dchar)ch);
1099 				if (ch >= 'a' && ch <= 'z') return to!string(cast(dchar)ch);
1100 				if (ch >= 'A' && ch <= 'Z') return to!string(cast(dchar)ch);
1101 				if (ch == '^') return "^";
1102 				if (ch == '/') return "/";
1103 				return format("$%s", ch);
1104 			}
1105 			logInfo("  %s: %s", i, n.terminals[].map!(t => t.var != VarIndex.max ? format("T%s(%s)", t.index, t.var) : format("T%s", t.index)).join(" "));
1106 			ubyte first_char;
1107 			LinkedSetHash list_hash;
1108 			NodeSet list;
1109 
1110 			void printEdges(ubyte last_char) {
1111 				if (!list.empty) {
1112 					string targets;
1113 					foreach (tn; m_edgeEntries.getItems(list))
1114 						targets ~= format(" %s", tn);
1115 					if (targets.length > 0)
1116 						logInfo("    [%s ... %s] -> %s", mapChar(first_char), mapChar(last_char), targets);
1117 				}
1118 			}
1119 			foreach (ch, tnodes; n.edges) {
1120 				auto h = m_edgeEntries.getHash(tnodes);
1121 				if (h != list_hash) {
1122 					printEdges(cast(ubyte)(ch-1));
1123 					list_hash = h;
1124 					list = tnodes;
1125 					first_char = cast(ubyte)ch;
1126 				}
1127 			}
1128 			printEdges(ubyte.max);
1129 			i++;
1130 		}
1131 	}
1132 
1133 	private void addEdge(NodeIndex from, NodeIndex to, ubyte ch, TerminalIndex terminal, VarIndex var = VarIndex.max)
1134 	@trusted {
1135 		m_edgeEntries.insert(&m_nodes[from].edges[ch], to);
1136 		addTerminal(to, terminal, var);
1137 	}
1138 
1139 	private NodeIndex addEdge(NodeIndex from, ubyte ch, TerminalIndex terminal, VarIndex var = VarIndex.max)
1140 	@trusted {
1141 		import std.algorithm : canFind;
1142 		import std.string : format;
1143 		if (!m_nodes[from].edges[ch].empty)
1144 			assert(false, format("%s is in %s", ch, m_nodes[from].edges[]));
1145 		auto nidx = addNode();
1146 		addEdge(from, nidx, ch, terminal, var);
1147 		return nidx;
1148 	}
1149 
1150 	private void addTerminal(NodeIndex node, TerminalIndex terminal, VarIndex var)
1151 	@trusted {
1152 		foreach (ref t; m_nodes[node].terminals) {
1153 			if (t.index == terminal) {
1154 				if (t.var != VarIndex.max && t.var != var)
1155 					assert(false, format("Ambiguous route var match!? %s vs %s", t.var, var));
1156 				t.var = var;
1157 				return;
1158 			}
1159 		}
1160 		m_nodes[node].terminals ~= TerminalTag(terminal, var);
1161 	}
1162 
1163 	private NodeIndex addNode()
1164 	@trusted {
1165 		assert(m_nodes.length <= 1_000_000_000, "More than 1B nodes in tree!?");
1166 		auto idx = cast(NodeIndex)m_nodes.length;
1167 		m_nodes ~= Node.init;
1168 		return idx;
1169 	}
1170 }
1171 
1172 
1173 /** Used to store and manipulate multiple linked lists within a single array
1174 	based storage.
1175 */
1176 struct LinkedSetBacking(T) {
1177 	import std.container.array : Array;
1178 	import std.range : isInputRange;
1179 
1180 	static struct Handle {
1181 		uint index = uint.max;
1182 		@property bool empty() const { return index == uint.max; }
1183 	}
1184 
1185 	private {
1186 		static struct Entry {
1187 			uint next;
1188 			T value;
1189 		}
1190 
1191 		Array!Entry m_storage;
1192 
1193 		static struct Range {
1194 			private {
1195 				Array!Entry* backing;
1196 				uint index;
1197 			}
1198 
1199 			@property bool empty() const { return index == uint.max; }
1200 			@property ref const(T) front() const { return (*backing)[index].value; }
1201 
1202 			void popFront()
1203 			{
1204 				index = (*backing)[index].next;
1205 			}
1206 		}
1207 	}
1208 
1209 	@property Handle emptySet() { return Handle.init; }
1210 
1211 	Handle create(scope T[] items...)
1212 	{
1213 		Handle ret;
1214 		foreach (i; items)
1215 			ret.index = createNode(i, ret.index);
1216 		return ret;
1217 	}
1218 
1219 	void insert(Handle* h, T value)
1220 	{
1221 		/*foreach (c; getItems(*h))
1222 			if (value == c)
1223 				return;*/
1224 		h.index = createNode(value, h.index);
1225 	}
1226 
1227 	void insert(R)(Handle* h, R items)
1228 		if (isInputRange!R)
1229 	{
1230 		foreach (itm; items)
1231 			insert(h, itm);
1232 	}
1233 
1234 	LinkedSetHash getHash(Handle sh)
1235 	const {
1236 		import std.digest.md : md5Of;
1237 
1238 		// NOTE: the returned hash is order independent, to avoid bogus
1239 		//       mismatches when comparing lists of different order
1240 		LinkedSetHash ret = cast(LinkedSetHash)md5Of([]);
1241 		while (sh != Handle.init) {
1242 			auto h = cast(LinkedSetHash)md5Of(cast(const(ubyte)[])(&m_storage[sh.index].value)[0 .. 1]);
1243 			foreach (i; 0 .. ret.length) ret[i] ^= h[i];
1244 			sh.index = m_storage[sh.index].next;
1245 		}
1246 		return ret;
1247 	}
1248 
1249 	auto getItems(Handle sh) { return Range(&m_storage, sh.index); }
1250 	auto getItems(Handle sh) const { return Range(&(cast()this).m_storage, sh.index); }
1251 
1252 	bool hasMaxLength(Handle sh, size_t l)
1253 	const {
1254 		uint idx = sh.index;
1255 		do {
1256 			if (idx == uint.max) return true;
1257 			idx = m_storage[idx].next;
1258 		} while (l-- > 0);
1259 		return false;
1260 	}
1261 
1262 	bool hasLength(Handle sh, size_t l)
1263 	const {
1264 		uint idx = sh.index;
1265 		while (l-- > 0) {
1266 			if (idx == uint.max) return false;
1267 			idx = m_storage[idx].next;
1268 		}
1269 		return idx == uint.max;
1270 	}
1271 
1272 	private uint createNode(ref T val, uint next)
1273 	{
1274 		auto id = cast(uint)m_storage.length;
1275 		m_storage ~= Entry(next, val);
1276 		return id;
1277 	}
1278 }
1279 
1280 unittest {
1281 	import std.algorithm.comparison : equal;
1282 
1283 	LinkedSetBacking!int b;
1284 	auto s = b.emptySet;
1285 	assert(s.empty);
1286 	assert(b.getItems(s).empty);
1287 	s = b.create(3, 5, 7);
1288 	assert(b.getItems(s).equal([7, 5, 3]));
1289 	assert(!b.hasLength(s, 2));
1290 	assert(b.hasLength(s, 3));
1291 	assert(!b.hasLength(s, 4));
1292 	assert(!b.hasMaxLength(s, 2));
1293 	assert(b.hasMaxLength(s, 3));
1294 	assert(b.hasMaxLength(s, 4));
1295 
1296 	auto h = b.getHash(s);
1297 	assert(h != b.getHash(b.emptySet));
1298 	s = b.create(5, 3, 7);
1299 	assert(b.getHash(s) == h);
1300 	assert(b.getItems(s).equal([7, 3, 5]));
1301 
1302 	b.insert(&s, 11);
1303 	assert(b.hasLength(s, 4));
1304 	assert(b.getHash(s) != h);
1305 	assert(b.getItems(s).equal([11, 7, 3, 5]));
1306 }
1307 
1308 alias LinkedSetHash = ulong[16/ulong.sizeof];
1309 
1310 private struct Stack(E)
1311 {
1312 	import std.range : isInputRange;
1313 
1314 	private {
1315 		E[] m_storage;
1316 		size_t m_fill;
1317 		debug size_t m_maxFill;
1318 	}
1319 
1320 	@property bool empty() const { return m_fill == 0; }
1321 
1322 	@property size_t fill() const { return m_fill; }
1323 
1324 	debug @property size_t maxSize() const { return m_maxFill; }
1325 
1326 	void reserve(size_t amt)
1327 	{
1328 		auto minsz = m_fill + amt;
1329 		if (m_storage.length < minsz) {
1330 			auto newlength = 64;
1331 			while (newlength < minsz) newlength *= 2;
1332 			m_storage.length = newlength;
1333 		}
1334 	}
1335 
1336 	void push(E el)
1337 	{
1338 		reserve(1);
1339 		m_storage[m_fill++] = el;
1340 		debug if (m_fill > m_maxFill) m_maxFill = m_fill;
1341 	}
1342 
1343 	void push(R)(R els)
1344 		if (isInputRange!R)
1345 	{
1346 		reserve(els.length);
1347 		foreach (el; els)
1348 			m_storage[m_fill++] = el;
1349 		debug if (m_fill > m_maxFill) m_maxFill = m_fill;
1350 	}
1351 
1352 	E pop()
1353 	{
1354 		assert(!empty, "Stack underflow.");
1355 		return m_storage[--m_fill];
1356 	}
1357 }