Skip to content

Commit c2ff434

Browse files
geekgeek
committed
Merge pull request hapijs#425 from walmartlabs/user/eran
Route sorting rewrite
2 parents 8b054e4 + 40ef54a commit c2ff434

File tree

8 files changed

+267
-168
lines changed

8 files changed

+267
-168
lines changed

‎README.md

Lines changed: 32 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -46,6 +46,7 @@ Current version: **0.11.3**
4646
- [Configuration options](#configuration-options)
4747
- [Override Route Defaults](#override-route-defaults)
4848
- [Path Processing](#path-processing)
49+
- [Route Matching Order](#route-matching-order)
4950
- [Parameters](#parameters)
5051
- [Route Handler](#route-handler)
5152
- [Response](#response)
@@ -172,7 +173,6 @@ var server = new Hapi.Server(options);
172173
### Router
173174

174175
The `router` option controls how incoming request URIs are matched against the routing table. The router only uses the first match found. Router options:
175-
- `isTrailingSlashSensitive` - determines whether the paths '/example' and '/example/' are considered different resources. Defaults to _false_.
176176
- `isCaseSensitive` - determines whether the paths '/example' and '/EXAMPLE' are considered different resources. Defaults to _true_.
177177
- `normalizeRequestPath` - determines whether a path should have certain reserved and unreserved percent encoded characters decoded. Also, all percent encodings will be capitalized that cannot be decoded. Defaults to _false_.
178178

@@ -685,14 +685,43 @@ Route matching is done on the request path only (excluding the query and other c
685685
- Static - the route path is a static string which begin with _'/'_ and will only match incoming requests containing the exact string match (as defined by the server `router` option).
686686
- Parameterized - same as _static_ with the additional support of named parameters (enclosed in _'{}'_).
687687

688+
#### Route Matching Order
689+
690+
**hapi** matches incoming requests in a deterministic order. This means the order in which routes are added does not
691+
matter. To achieve this, **hapi** uses a set of rules to sort the routes from the most specific to the most generic. For example, the following
692+
path array shows the order in which an incoming request path will be matched against the routes, regardless of the order they are added:
693+
694+
```javascript
695+
var paths = [
696+
'/',
697+
'/a',
698+
'/b',
699+
'/ab',
700+
'/{p}',
701+
'/a/b',
702+
'/a/{p}',
703+
'/b/',
704+
'/a/b/c',
705+
'/a/b/{p}',
706+
'/a/{p}/b',
707+
'/a/{p}/c',
708+
'/a/{p*2}',
709+
'/a/b/c/d',
710+
'/a/b/{p*2}',
711+
'/a/{p}/b/{x}',
712+
'/{p*5}',
713+
'/a/b/{p*}',
714+
'/{p*}'
715+
];
716+
```
717+
688718

689719
#### Parameters
690720

691721
Parameterized paths are processed by matching the named parameters to the content of the incoming request path at that level. For example, the route:
692722
'/book/{id}/cover' will match: '/book/123/cover' and 'request.params.id' will be set to '123'. Each path level (everything between the opening _'/'_ and
693723
the closing _'/'_ unless it is the end of the path) can only include one named parameter. The _'?'_ suffix following the parameter name indicates
694-
an optional parameter (only allowed if the parameter is at the ends of the path). For example: the route: '/book/{id?}' will match: '/book/' (and may
695-
match '/book' based on the server `router` option).
724+
an optional parameter (only allowed if the parameter is at the ends of the path). For example: the route: '/book/{id?}' will match: '/book/'.
696725

697726
```javascript
698727
server.addRoute({

‎lib/defaults.js

Lines changed: 0 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -23,7 +23,6 @@ exports.server = {
2323
// Router
2424

2525
router: {
26-
isTrailingSlashSensitive: false, // Treat trailing '/' in path as different resources
2726
isCaseSensitive: true, // Case-seinsitive paths
2827
normalizeRequestPath: false // Normalize incoming request path (Uppercase % encoding and decode non-reserved encoded characters)
2928
},

‎lib/route.js

Lines changed: 79 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -174,14 +174,12 @@ internals.Route.validatePathEncodedRegex = /%(?:2[146-9A-E]|3[\dABD]|4[\dA-F]|5[
174174

175175
internals.Route.prototype._generateRegex = function () {
176176

177-
var trailingSlashOptional = !this.server.settings.router.isTrailingSlashSensitive;
178-
179177
// Split on /
180178

181179
var segments = this.path.split('/');
182180
var params = {};
183181
var pathRX = '';
184-
var fingerprint = '';
182+
var fingers = [];
185183

186184
var paramRegex = /^\{(\w+)(?:(\*)(\d+)?)?(\?)?\}$/; // $1: name, $2: *, $3: segments, $4: optional
187185

@@ -216,12 +214,7 @@ internals.Route.prototype._generateRegex = function () {
216214
if (isOptional ||
217215
(isMulti && !multiCount)) {
218216

219-
if (trailingSlashOptional) {
220-
pathRX += '(?:(?:\\/)|(?:' + segmentRX + '))?';
221-
}
222-
else {
223-
pathRX += '(?:(?:\\/)|(?:' + segmentRX + '))';
224-
}
217+
pathRX += '(?:(?:\\/)|(?:' + segmentRX + '))';
225218
}
226219
else {
227220
pathRX += segmentRX;
@@ -230,15 +223,15 @@ internals.Route.prototype._generateRegex = function () {
230223
if (isMulti) {
231224
if (multiCount) {
232225
for (var m = 0; m < multiCount; ++m) {
233-
fingerprint += '/?';
226+
fingers.push('/?');
234227
}
235228
}
236229
else {
237-
fingerprint += '/?*';
230+
fingers.push('/*');
238231
}
239232
}
240233
else {
241-
fingerprint += '/?';
234+
fingers.push('/?');
242235
}
243236
}
244237
else {
@@ -247,28 +240,29 @@ internals.Route.prototype._generateRegex = function () {
247240

248241
if (segment) {
249242
pathRX += '\\/' + Utils.escapeRegex(segment);
250-
fingerprint += '/' + segment;
243+
if (this.server.settings.router.isCaseSensitive) {
244+
fingers.push('/' + segment);
245+
}
246+
else {
247+
fingers.push('/' + segment.toLowerCase());
248+
}
251249
}
252250
else {
253251
pathRX += '\\/';
254-
if (trailingSlashOptional) {
255-
pathRX += '?';
256-
}
257-
258-
fingerprint += '/';
252+
fingers.push('/');
259253
}
260254
}
261255
}
262256

263257
if (this.server.settings.router.isCaseSensitive) {
264258
this.regexp = new RegExp('^' + pathRX + '$');
265-
this.fingerprint = fingerprint;
266259
}
267260
else {
268261
this.regexp = new RegExp('^' + pathRX + '$', 'i');
269-
this.fingerprint = fingerprint.toLowerCase();
270262
}
271263

264+
this.fingerprint = fingers.join('');
265+
this._fingerprintParts = fingers;
272266
this.params = Object.keys(params);
273267
};
274268

@@ -308,4 +302,68 @@ internals.Route.prototype.test = function (path) {
308302

309303
var match = this.regexp.exec(path);
310304
return !!match;
311-
};
305+
};
306+
307+
308+
exports.sort = function (a, b) {
309+
310+
// Biased for less and shorter segments which are faster to compare
311+
312+
var aFirst = -1;
313+
var bFirst = 1;
314+
315+
// Prepare fingerprints
316+
317+
var aFingers = a._fingerprintParts;
318+
var bFingers = b._fingerprintParts;
319+
320+
var al = aFingers.length;
321+
var bl = bFingers.length;
322+
323+
// Comare fingerprints
324+
325+
if ((aFingers[al - 1] === '/*') ^ (bFingers[bl - 1] === '/*')) {
326+
return (aFingers[al - 1] === '/*' ? bFirst : aFirst);
327+
}
328+
329+
var size = Math.min(al, bl);
330+
for (var i = 0; i < size; ++i) {
331+
332+
var aSegment = aFingers[i];
333+
var bSegment = bFingers[i];
334+
335+
if (aSegment === bSegment) {
336+
continue;
337+
}
338+
339+
if (aSegment === '/*' ||
340+
bSegment === '/*') {
341+
342+
return (aSegment === '/*' ? bFirst : aFirst);
343+
}
344+
345+
if (aSegment === '/?' ||
346+
bSegment === '/?') {
347+
348+
if (aSegment === '/?') {
349+
return (al >= bl ? bFirst : aFirst);
350+
}
351+
else {
352+
return (bl < al ? bFirst : aFirst);
353+
}
354+
}
355+
356+
if (al === bl) {
357+
if (aSegment.length === bSegment.length) {
358+
return (aSegment > bSegment ? bFirst : aFirst);
359+
}
360+
361+
return (aSegment.length > bSegment.length ? bFirst : aFirst);
362+
}
363+
364+
return (al > bl ? bFirst : aFirst);
365+
}
366+
367+
return (al > bl ? bFirst : aFirst);
368+
};
369+

‎lib/server.js

Lines changed: 1 addition & 35 deletions
Original file line numberDiff line numberDiff line change
@@ -329,41 +329,7 @@ internals.Server.prototype.addRoute = function (options) {
329329
}
330330

331331
routes.push(route);
332-
333-
routes.sort(function (a, b) {
334-
335-
var aSegments = a.fingerprint.split('/');
336-
var bSegments = b.fingerprint.split('/');
337-
338-
aSegments.shift();
339-
bSegments.shift();
340-
341-
if (aSegments[0] === '?*') {
342-
return 1;
343-
}
344-
else if (bSegments[0] === '?*') {
345-
return -1;
346-
}
347-
348-
for (var si = 0, sl = aSegments.length, bsl = bSegments.length; si < sl; ++si) {
349-
if (si === bsl) { // a has more segments than b and should appear after b
350-
return 1;
351-
}
352-
353-
var aSegment = aSegments[si];
354-
var bSegment = bSegments[si];
355-
356-
if (aSegment !== bSegment && aSegment === '?') { // a is less specific than b
357-
return 1;
358-
}
359-
else if (aSegment !== bSegment && bSegment === '?') { // b is less specific than a
360-
return -1;
361-
}
362-
}
363-
364-
return 0;
365-
});
366-
332+
routes.sort(Route.sort);
367333

368334
// Setup CORS 'OPTIONS' handler
369335

‎package.json

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -36,7 +36,7 @@
3636
"mime": "1.2.x",
3737
"catbox": "0.1.x",
3838
"cryptiles": "0.0.x",
39-
"iron": "0.0.x"
39+
"iron": "0.1.x"
4040
},
4141
"devDependencies": {
4242
"mocha": "1.x.x",

‎test/integration/response.js

Lines changed: 8 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -566,7 +566,7 @@ describe('Response', function () {
566566

567567
server.start(function () {
568568

569-
Request.get(server.settings.uri + '/directory', function (err, res, body) {
569+
Request.get(server.settings.uri + '/directory/', function (err, res, body) {
570570

571571
expect(err).to.not.exist;
572572
expect(res.statusCode).to.equal(403);
@@ -635,7 +635,7 @@ describe('Response', function () {
635635

636636
server.start(function () {
637637

638-
Request.get(server.settings.uri + '/directoryx', function (err, res, body) {
638+
Request.get(server.settings.uri + '/directoryx/', function (err, res, body) {
639639

640640
expect(err).to.not.exist;
641641
expect(res.statusCode).to.equal(403);
@@ -650,7 +650,7 @@ describe('Response', function () {
650650

651651
server.start(function () {
652652

653-
Request.get(server.settings.uri + '/directorylist', function (err, res, body) {
653+
Request.get(server.settings.uri + '/directorylist/', function (err, res, body) {
654654

655655
expect(err).to.not.exist;
656656
expect(res.statusCode).to.equal(200);
@@ -680,7 +680,7 @@ describe('Response', function () {
680680

681681
server.start(function () {
682682

683-
Request.get(server.settings.uri + '/directorylistx', function (err, res, body) {
683+
Request.get(server.settings.uri + '/directorylistx/', function (err, res, body) {
684684

685685
expect(err).to.not.exist;
686686
expect(res.statusCode).to.equal(200);
@@ -696,7 +696,7 @@ describe('Response', function () {
696696

697697
server.start(function () {
698698

699-
Request.get(server.settings.uri + '/directoryIndex', function (err, res, body) {
699+
Request.get(server.settings.uri + '/directoryIndex/', function (err, res, body) {
700700

701701
expect(err).to.not.exist;
702702
expect(res.statusCode).to.equal(200);
@@ -744,7 +744,7 @@ describe('Response', function () {
744744

745745
server.start(function () {
746746

747-
Request.get(server.settings.uri + '/showhidden', function (err, res, body) {
747+
Request.get(server.settings.uri + '/showhidden/', function (err, res, body) {
748748

749749
expect(err).to.not.exist;
750750
expect(body).to.contain('.hidden');
@@ -757,7 +757,7 @@ describe('Response', function () {
757757

758758
server.start(function () {
759759

760-
Request.get(server.settings.uri + '/noshowhidden', function (err, res, body) {
760+
Request.get(server.settings.uri + '/noshowhidden/', function (err, res, body) {
761761

762762
expect(err).to.not.exist;
763763
expect(body).to.not.contain('.hidden');
@@ -902,7 +902,7 @@ describe('Response', function () {
902902

903903
it('returns a stream reply', function (done) {
904904

905-
server.inject({ method: 'GET', url: '/stream' }, function (res) {
905+
server.inject({ method: 'GET', url: '/stream/' }, function (res) {
906906

907907
expect(res.readPayload()).to.equal('x');
908908
expect(res.statusCode).to.equal(200);

0 commit comments

Comments
 (0)