Skip to content

Commit e5c04b4

Browse files
committed
correct 'partial' mode matching of multiple-** patterns
Fix: #329
1 parent cff11d8 commit e5c04b4

4 files changed

Lines changed: 94 additions & 8 deletions

File tree

‎changelog.md‎

Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -17,6 +17,15 @@
1717
- Remove the `debug` option and the `debug()` method.
1818
- Remove the `matchOne()`, `slashSplit()`, and
1919
`levelTwoFileOptimize()` methods. They are internal now.
20+
- Fix patterns with more than one `**` and sections of different
21+
lengths between them, such as `**/a/b/c/**/d/**`, which failed
22+
to match some paths since 10.2.3.
23+
- Fix `partial` matching of patterns with `**`, which since
24+
10.2.3 matched some paths under a dot portion that `**` can not
25+
walk, and did not match some paths that end in the pattern's
26+
last portion.
27+
- `partial` matching of patterns with many `**` no longer takes
28+
exponential time.
2029
- On Windows, compare the host and share of UNC paths like
2130
`//host/share/...` case-insensitively, the same as drive
2231
letters.

‎src/index.ts‎

Lines changed: 31 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -1482,6 +1482,7 @@ export class Minimatch {
14821482
partial,
14831483
0,
14841484
!!fileTailMatch,
1485+
new Set(),
14851486
)
14861487
}
14871488

@@ -1525,10 +1526,10 @@ export class Minimatch {
15251526
nonGsParts++
15261527
}
15271528
}
1528-
let i = segments.length - 1
1529-
for (const b of segments) {
1530-
b[1] = (nonGsPartsSums[i--] as number) + b[0].length
1531-
}
1529+
// the portions in this section and the ones after it
1530+
segments.forEach((b, i) => {
1531+
b[1] = nonGsParts - (nonGsPartsSums[i] as number)
1532+
})
15321533

15331534
const parts = { head, body, tail, segments }
15341535
byStart[key] = parts
@@ -1548,6 +1549,11 @@ export class Minimatch {
15481549
partial: boolean,
15491550
globStarDepth: number,
15501551
sawTail: boolean,
1552+
// the places that a walk has already tried, as
1553+
// bodyIndex * (file.length + 1) + fileIndex. A walk from a place
1554+
// does the same no matter how it got there, and it only comes back
1555+
// if it found no match, so a walk that gets to one stops.
1556+
tried: Set<number>,
15511557
): boolean | null {
15521558
// take the first body segment, and walk from fileIndex to its "after"
15531559
// value at the end
@@ -1560,8 +1566,18 @@ export class Minimatch {
15601566
// can't possibly be a valid matching condition.
15611567
const bs = bodySegments[bodyIndex]
15621568
if (!bs) {
1563-
// just make sure that there's no bad dots
1564-
for (let i = fileIndex; i < file.length; i++) {
1569+
// with partial, the body is the rest of the pattern, so it
1570+
// matches if no portions are left, or only the '' of a trailing
1571+
// / (as a/* matches a/b/). A ** at the end walks them as its own
1572+
// empty section.
1573+
if (partial) {
1574+
return (
1575+
fileIndex >= fileLength ||
1576+
(fileIndex === fileLength - 1 && file[fileIndex] === '')
1577+
)
1578+
}
1579+
// just make sure that there's no bad dots before the tail
1580+
for (let i = fileIndex; i < fileLength; i++) {
15651581
sawTail = true
15661582
const f = file[i]
15671583
if (
@@ -1578,8 +1594,12 @@ export class Minimatch {
15781594
// have a non-globstar body section to test, up to the last index
15791595
// where it can start
15801596
const [body, need] = bs
1581-
const after = fileLength - need
1597+
// with partial, the path can end before the body does
1598+
const after = partial ? fileLength : fileLength - need
15821599
while (fileIndex <= after) {
1600+
const key = bodyIndex * (file.length + 1) + fileIndex
1601+
if (tried.has(key)) return false
1602+
tried.add(key)
15831603
const m = this.#matchOne(
15841604
file,
15851605
body,
@@ -1601,12 +1621,15 @@ export class Minimatch {
16011621
partial,
16021622
globStarDepth + 1,
16031623
sawTail,
1624+
tried,
16041625
)
16051626
if (sub !== false) {
16061627
return sub
16071628
}
16081629
}
1609-
const f = file[fileIndex]
1630+
// the ** does not walk past the last place the body can start
1631+
if (fileIndex === after) break
1632+
const f = file[fileIndex]!
16101633
if (
16111634
f === '.' ||
16121635
f === '..' ||

‎test/multiple-non-adjacent-globstars.ts‎

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -74,3 +74,46 @@ t.test('tail handling 2', async t => {
7474
pattern,
7575
})
7676
})
77+
78+
// https://github.com/isaacs/minimatch/issues/329
79+
t.test('body sections that differ in length', async t => {
80+
const pattern = '**/a/b/c/**/d/**'
81+
for (const level of [0, 1, 2]) {
82+
const o = { optimizationLevel: level }
83+
t.equal(minimatch('a/b/c/d/e', pattern, o), true)
84+
t.equal(minimatch('x/a/b/c/d/e', pattern, o), true)
85+
t.equal(minimatch('a/b/c/x/d/e', pattern, o), true)
86+
t.equal(minimatch('a/b/c/e', pattern, o), false)
87+
t.equal(minimatch('a/b/c/d', pattern, o), false)
88+
t.equal(minimatch('a/b/c/d/e', '**/d/**/a/b/c/**', o), false)
89+
t.equal(minimatch('d/x/a/b/c/e', '**/d/**/a/b/c/**', o), true)
90+
}
91+
})
92+
93+
t.test('the tail is not walked by the last **', async t => {
94+
t.equal(minimatch('.x/.x', '**/.x/**/.x'), true)
95+
t.equal(minimatch('a/.x/b/.x', '**/.x/**/.x'), true)
96+
t.equal(minimatch('a/.x/.y/.x', '**/.x/**/.x'), false)
97+
})
98+
99+
t.test('partial does not try a place in the path twice', async t => {
100+
const pattern =
101+
Array.from({ length: 50 }, () => '**/a').join('/') + '/b/**'
102+
const path = Array(100).fill('a').join('/') + '/b/c/d/.e/a/b'
103+
const alphabet = 'abcdefghijklmnopqrstuvwxyz'.repeat(5)
104+
const p2 = '**/' + alphabet.split('').join('/**/') + '/**'
105+
const f2 = alphabet
106+
.split('')
107+
.flatMap(c => alphabet.split('').filter(x => x !== c))
108+
.join('/')
109+
for (const [f, p, dot, expect] of [
110+
[path, pattern, false, false],
111+
[path, pattern, true, true],
112+
[`${f2}/.x/y`, p2, false, false],
113+
] as const) {
114+
const start = performance.now()
115+
t.equal(minimatch(f, p, { partial: true, dot }), expect)
116+
const dur = performance.now() - start
117+
t.ok(dur < 1000, 'should take less than 1s', { found: dur })
118+
}
119+
})

‎test/partial.ts‎

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -14,3 +14,14 @@ t.equal(mm('a', '**', { partial: true }), true)
1414
t.equal(mm('b/a', 'a/**', { partial: true }), false)
1515
t.equal(mm('/b/c/d/a', '/**/a/**/b/c/**', { partial: true }), true)
1616
t.equal(mm('/b/c/d/a', '/**/a/**', { partial: true }), true)
17+
18+
// ** can not walk a dot portion, so nothing under it can match
19+
t.equal(mm('.x', '**/b', { partial: true }), false)
20+
t.equal(mm('.x', '**/.x', { partial: true }), true)
21+
t.equal(mm('.x/', '**/.x', { partial: true }), true)
22+
t.equal(mm('a/.x/', 'a/**/.x', { partial: true }), true)
23+
t.equal(mm('.x/b', '**/.x', { partial: true }), false)
24+
// an empty section at the end of the body
25+
t.equal(mm('a/a', '*/**/?/**', { partial: true }), true)
26+
t.equal(mm('a/a/.x', '*/**/?/**', { partial: true }), false)
27+
t.equal(mm('.x/a', '*/**/?/**', { partial: true }), false)

0 commit comments

Comments
 (0)