Skip to content

Commit 7396793

Browse files
committed
fix(router-core): wildcard nodes respect DFS priority like other nodes in route matching
1 parent 1248e44 commit 7396793

2 files changed

Lines changed: 79 additions & 31 deletions

File tree

‎packages/router-core/src/new-process-route-tree.ts‎

Lines changed: 43 additions & 31 deletions
Original file line numberDiff line numberDiff line change
@@ -1023,6 +1023,7 @@ type MatchStackFrame<T extends RouteLike> = {
10231023
* If we really really need to support more than 32 segments we can switch to using a `BigInt` here. It's about 2x slower in worst case scenarios.
10241024
*/
10251025
skipped: number
1026+
/** Positional bitmasks tracking which consumed URL segments matched each segment kind. */
10261027
statics: number
10271028
dynamics: number
10281029
optionals: number
@@ -1066,13 +1067,12 @@ function getNodeMatch<T extends RouteLike>(
10661067
index: 1,
10671068
skipped: 0,
10681069
depth: 1,
1069-
statics: 1,
1070+
statics: 0,
10701071
dynamics: 0,
10711072
optionals: 0,
10721073
},
10731074
]
10741075

1075-
let wildcardMatch: Frame | null = null
10761076
let bestFuzzy: Frame | null = null
10771077
let bestMatch: Frame | null = null
10781078

@@ -1101,7 +1101,13 @@ function getNodeMatch<T extends RouteLike>(
11011101

11021102
const isBeyondPath = index === partsLength
11031103
if (isBeyondPath) {
1104-
if (node.route && !pathIsIndex && isFrameMoreSpecific(bestMatch, frame)) {
1104+
if (
1105+
node.route &&
1106+
(!pathIsIndex ||
1107+
node.kind === SEGMENT_TYPE_INDEX ||
1108+
node.kind === SEGMENT_TYPE_WILDCARD) &&
1109+
isFrameMoreSpecific(bestMatch, frame)
1110+
) {
11051111
bestMatch = frame
11061112
}
11071113
// beyond the length of the path parts, only some segment types can match
@@ -1134,7 +1140,12 @@ function getNodeMatch<T extends RouteLike>(
11341140
if (indexValid) {
11351141
// perfect match, no need to continue
11361142
// this is an optimization, algorithm should work correctly without this block
1137-
if (statics === partsLength && !dynamics && !optionals && !skipped) {
1143+
if (
1144+
!dynamics &&
1145+
!optionals &&
1146+
!skipped &&
1147+
isPerfectStaticMatch(statics, partsLength)
1148+
) {
11381149
return indexFrame
11391150
}
11401151
if (isFrameMoreSpecific(bestMatch, indexFrame)) {
@@ -1145,7 +1156,7 @@ function getNodeMatch<T extends RouteLike>(
11451156
}
11461157

11471158
// 5. Try wildcard match
1148-
if (node.wildcard && isFrameMoreSpecific(wildcardMatch, frame)) {
1159+
if (node.wildcard) {
11491160
for (const segment of node.wildcard) {
11501161
const { prefix, suffix } = segment
11511162
if (prefix) {
@@ -1162,15 +1173,16 @@ function getNodeMatch<T extends RouteLike>(
11621173
if (casePart !== suffix) continue
11631174
}
11641175
// the first wildcard match is the highest priority one
1165-
// wildcard matches skip the stack because they cannot have children
1176+
// wildcard matches consume the rest of the URL and cannot have children
1177+
const consumed = partsLength - index
11661178
const frame = {
11671179
node: segment,
11681180
index: partsLength,
11691181
skipped,
1170-
depth,
1171-
statics,
1172-
dynamics,
1173-
optionals,
1182+
depth: depth + 1,
1183+
statics: shiftScore(statics, consumed),
1184+
dynamics: shiftScore(dynamics, consumed),
1185+
optionals: shiftScore(optionals, consumed),
11741186
extract,
11751187
rawParams,
11761188
parsedParams,
@@ -1179,7 +1191,7 @@ function getNodeMatch<T extends RouteLike>(
11791191
const result = validateMatchParams(path, parts, frame)
11801192
if (!result) continue
11811193
}
1182-
wildcardMatch = frame
1194+
stack.push(frame)
11831195
break
11841196
}
11851197
}
@@ -1220,9 +1232,9 @@ function getNodeMatch<T extends RouteLike>(
12201232
index: index + 1,
12211233
skipped,
12221234
depth: nextDepth,
1223-
statics,
1224-
dynamics,
1225-
optionals: optionals + 1,
1235+
statics: shiftScore(statics),
1236+
dynamics: shiftScore(dynamics),
1237+
optionals: shiftScore(optionals) + 1,
12261238
extract,
12271239
rawParams,
12281240
parsedParams,
@@ -1248,9 +1260,9 @@ function getNodeMatch<T extends RouteLike>(
12481260
index: index + 1,
12491261
skipped,
12501262
depth: depth + 1,
1251-
statics,
1252-
dynamics: dynamics + 1,
1253-
optionals,
1263+
statics: shiftScore(statics),
1264+
dynamics: shiftScore(dynamics) + 1,
1265+
optionals: shiftScore(optionals),
12541266
extract,
12551267
rawParams,
12561268
parsedParams,
@@ -1269,9 +1281,9 @@ function getNodeMatch<T extends RouteLike>(
12691281
index: index + 1,
12701282
skipped,
12711283
depth: depth + 1,
1272-
statics: statics + 1,
1273-
dynamics,
1274-
optionals,
1284+
statics: shiftScore(statics) + 1,
1285+
dynamics: shiftScore(dynamics),
1286+
optionals: shiftScore(optionals),
12751287
extract,
12761288
rawParams,
12771289
parsedParams,
@@ -1288,9 +1300,9 @@ function getNodeMatch<T extends RouteLike>(
12881300
index: index + 1,
12891301
skipped,
12901302
depth: depth + 1,
1291-
statics: statics + 1,
1292-
dynamics,
1293-
optionals,
1303+
statics: shiftScore(statics) + 1,
1304+
dynamics: shiftScore(dynamics),
1305+
optionals: shiftScore(optionals),
12941306
extract,
12951307
rawParams,
12961308
parsedParams,
@@ -1319,16 +1331,8 @@ function getNodeMatch<T extends RouteLike>(
13191331
}
13201332
}
13211333

1322-
if (bestMatch && wildcardMatch) {
1323-
return isFrameMoreSpecific(wildcardMatch, bestMatch)
1324-
? bestMatch
1325-
: wildcardMatch
1326-
}
1327-
13281334
if (bestMatch) return bestMatch
13291335

1330-
if (wildcardMatch) return wildcardMatch
1331-
13321336
if (fuzzy && bestFuzzy) {
13331337
let sliceIndex = bestFuzzy.index
13341338
for (let i = 0; i < bestFuzzy.index; i++) {
@@ -1343,6 +1347,14 @@ function getNodeMatch<T extends RouteLike>(
13431347
return null
13441348
}
13451349

1350+
function shiftScore(score: number, amount = 1): number {
1351+
return score * 2 ** amount
1352+
}
1353+
1354+
function isPerfectStaticMatch(statics: number, partsLength: number): boolean {
1355+
return statics === 2 ** (partsLength - 1) - 1
1356+
}
1357+
13461358
function validateMatchParams<T extends RouteLike>(
13471359
path: string,
13481360
parts: Array<string>,

‎packages/router-core/tests/new-process-route-tree.test.ts‎

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -233,6 +233,42 @@ describe('findRouteMatch', () => {
233233
const treeWithIndex = makeTree(['/a/', '/a/{-$b}'])
234234
expect(findRouteMatch('/a', treeWithIndex)?.route.id).toBe('/a/')
235235
})
236+
it('optional+static vs static+wildcard', () => {
237+
const tree = makeTree(['/{-$a}/b', '/a/$'])
238+
expect(findRouteMatch('/a/b', tree)?.route.id).toBe('/a/$')
239+
})
240+
it('dynamic+static vs static+wildcard', () => {
241+
const tree = makeTree(['/$a/b', '/a/$'])
242+
expect(findRouteMatch('/a/b', tree)?.route.id).toBe('/a/$')
243+
})
244+
it('dynamic+static+static vs static+wildcard', () => {
245+
const tree = makeTree(['/$a/b/c', '/a/$'])
246+
expect(findRouteMatch('/a/b/c', tree)?.route.id).toBe('/a/$')
247+
})
248+
it('static+optional+static vs static+static+wildcard', () => {
249+
const tree = makeTree(['/a/{-$b}/c', '/a/b/$'])
250+
expect(findRouteMatch('/a/b/c', tree)?.route.id).toBe('/a/b/$')
251+
})
252+
it('static+dynamic+wildcard vs static+optional+static', () => {
253+
const tree = makeTree(['/a/$b/$', '/a/{-$b}/c'])
254+
expect(findRouteMatch('/a/b/c', tree)?.route.id).toBe('/a/{-$b}/c')
255+
})
256+
it('static+dynamic+static vs static+dynamic+wildcard', () => {
257+
const tree = makeTree(['/a/$b/c', '/a/$b/$'])
258+
expect(findRouteMatch('/a/b/c', tree)?.route.id).toBe('/a/$b/c')
259+
})
260+
it('skipped optional keeps later static priority over wildcard', () => {
261+
const tree = makeTree(['/{-$a}/b/c', '/b/$'])
262+
expect(findRouteMatch('/b/c', tree)?.route.id).toBe('/{-$a}/b/c')
263+
})
264+
it('optional child wins over empty wildcard at the same node', () => {
265+
const tree = makeTree(['/a/{-$b}', '/a/$'])
266+
expect(findRouteMatch('/a', tree)?.route.id).toBe('/a/{-$b}')
267+
})
268+
it('optional+static vs static+optional', () => {
269+
const tree = makeTree(['/{-$a}/b', '/a/{-$b}'])
270+
expect(findRouteMatch('/a/b', tree)?.route.id).toBe('/a/{-$b}')
271+
})
236272
})
237273
})
238274

0 commit comments

Comments
 (0)