Skip to content

Commit 04fbd5b

Browse files
fiskerfisker
authored
Improve performance with mutiple patterns (#222)
1 parent f816156 commit 04fbd5b

6 files changed

Lines changed: 159 additions & 19 deletions

File tree

‎bench.js‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -4,7 +4,7 @@ import path from 'node:path';
44
import {fileURLToPath} from 'node:url';
55
import Benchmark from 'benchmark';
66
import rimraf from 'rimraf';
7-
import * as globbyMainBranch from 'globby';
7+
import * as globbyMainBranch from '@globby/main-branch';
88
import gs from 'glob-stream';
99
import fastGlob from 'fast-glob';
1010
import {globby, globbySync, globbyStream} from './index.js';

‎index.js‎

Lines changed: 30 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -55,9 +55,11 @@ const normalizeArgumentsSync = fn => (patterns, options) => fn(toPatternsArray(p
5555
const getFilter = async options => createFilterFunction(
5656
options.gitignore && await isGitIgnored({cwd: options.cwd}),
5757
);
58+
5859
const getFilterSync = options => createFilterFunction(
5960
options.gitignore && isGitIgnoredSync({cwd: options.cwd}),
6061
);
62+
6163
const createFilterFunction = isIgnored => {
6264
const seen = new Set();
6365

@@ -72,27 +74,40 @@ const createFilterFunction = isIgnored => {
7274
const unionFastGlobResults = (results, filter) => results.flat().filter(fastGlobResult => filter(fastGlobResult));
7375
const unionFastGlobStreams = (streams, filter) => merge2(streams).pipe(new FilterStream(fastGlobResult => filter(fastGlobResult)));
7476

75-
const convertNegativePatterns = (patterns, taskOptions) => {
76-
const globTasks = [];
77-
for (const [index, pattern] of patterns.entries()) {
78-
if (isNegative(pattern)) {
79-
continue;
77+
const convertNegativePatterns = (patterns, options) => {
78+
const tasks = [];
79+
80+
while (patterns.length > 0) {
81+
const index = patterns.findIndex(pattern => isNegative(pattern));
82+
83+
if (index === -1) {
84+
tasks.push({patterns, options});
85+
break;
8086
}
8187

82-
const ignore = patterns
83-
.slice(index)
84-
.filter(pattern => isNegative(pattern))
85-
.map(pattern => pattern.slice(1));
88+
const ignorePattern = patterns[index].slice(1);
8689

87-
const options = {
88-
...taskOptions,
89-
ignore: [...taskOptions.ignore, ...ignore],
90-
};
90+
for (const task of tasks) {
91+
task.options.ignore.push(ignorePattern);
92+
}
93+
94+
if (index !== 0) {
95+
tasks.push({
96+
patterns: patterns.slice(0, index),
97+
options: {
98+
...options,
99+
ignore: [
100+
...options.ignore,
101+
ignorePattern,
102+
],
103+
},
104+
});
105+
}
91106

92-
globTasks.push({patterns: [pattern], options});
107+
patterns = patterns.slice(index + 1);
93108
}
94109

95-
return globTasks;
110+
return tasks;
96111
};
97112

98113
const getDirGlobOptions = (options, cwd) => ({

‎package.json‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -16,7 +16,7 @@
1616
"node": "^12.20.0 || ^14.13.1 || >=16.0.0"
1717
},
1818
"scripts": {
19-
"bench": "npm update globby glob-stream fast-glob && node bench.js",
19+
"bench": "npm update @globby/main-branch glob-stream fast-glob && node bench.js",
2020
"test": "xo && ava && tsd"
2121
},
2222
"files": [
@@ -66,12 +66,12 @@
6666
"slash": "^4.0.0"
6767
},
6868
"devDependencies": {
69+
"@globby/main-branch": "sindresorhus/globby#main",
6970
"@types/node": "^16.11.11",
7071
"ava": "^3.15.0",
7172
"benchmark": "2.1.4",
7273
"get-stream": "^6.0.1",
7374
"glob-stream": "^7.0.0",
74-
"globby": "sindresorhus/globby#main",
7575
"rimraf": "^3.0.2",
7676
"tsd": "^0.19.0",
7777
"typescript": "^4.5.2",

‎tests/generate-glob-tasks.js‎

Lines changed: 121 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -9,6 +9,7 @@ import {
99
import {
1010
invalidPatterns,
1111
getPathValues,
12+
isUnique,
1213
} from './utilities.js';
1314

1415
const runGenerateGlobTasks = async (t, patterns, options) => {
@@ -24,6 +25,11 @@ const runGenerateGlobTasks = async (t, patterns, options) => {
2425
return promiseResult;
2526
};
2627

28+
const getTasks = async (t, patterns, options) => {
29+
const tasks = await runGenerateGlobTasks(t, patterns, options);
30+
return tasks.map(({patterns, options: {ignore}}) => ({patterns, ignore}));
31+
};
32+
2733
test('generateGlobTasks', async t => {
2834
const tasks = await runGenerateGlobTasks(t, ['*.tmp', '!b.tmp'], {ignore: ['c.tmp']});
2935

@@ -99,3 +105,118 @@ test('expandDirectories option', async t => {
99105
t.deepEqual(tasks[0].options.ignore, ['**/b.tmp']);
100106
}
101107
});
108+
109+
test('combine tasks', async t => {
110+
t.deepEqual(
111+
await getTasks(t, ['a', 'b']),
112+
[{patterns: ['a', 'b'], ignore: []}],
113+
);
114+
115+
t.deepEqual(
116+
await getTasks(t, ['!a', 'b']),
117+
[{patterns: ['b'], ignore: []}],
118+
);
119+
120+
t.deepEqual(
121+
await getTasks(t, ['!a']),
122+
[],
123+
);
124+
125+
t.deepEqual(
126+
await getTasks(t, ['a', 'b', '!c', '!d']),
127+
[{patterns: ['a', 'b'], ignore: ['c', 'd']}],
128+
);
129+
130+
t.deepEqual(
131+
await getTasks(t, ['a', 'b', '!c', '!d', 'e']),
132+
[
133+
{patterns: ['a', 'b'], ignore: ['c', 'd']},
134+
{patterns: ['e'], ignore: []},
135+
],
136+
);
137+
138+
t.deepEqual(
139+
await getTasks(t, ['a', 'b', '!c', 'd', 'e', '!f', '!g', 'h']),
140+
[
141+
{patterns: ['a', 'b'], ignore: ['c', 'f', 'g']},
142+
{patterns: ['d', 'e'], ignore: ['f', 'g']},
143+
{patterns: ['h'], ignore: []},
144+
],
145+
);
146+
});
147+
148+
test('random patterns', async t => {
149+
for (let index = 0; index < 500; index++) {
150+
const positivePatterns = [];
151+
const negativePatterns = [];
152+
const negativePatternsAtStart = [];
153+
154+
const patterns = Array.from({length: 1 + Math.floor(Math.random() * 20)}, (_, index) => {
155+
const negative = Math.random() > 0.5;
156+
let pattern = String(index + 1);
157+
if (negative) {
158+
negativePatterns.push(pattern);
159+
160+
if (positivePatterns.length === 0) {
161+
negativePatternsAtStart.push(pattern);
162+
}
163+
164+
pattern = `!${pattern}`;
165+
} else {
166+
positivePatterns.push(pattern);
167+
}
168+
169+
return pattern;
170+
});
171+
172+
// eslint-disable-next-line no-await-in-loop
173+
const tasks = await getTasks(t, patterns);
174+
const patternsToDebug = JSON.stringify(patterns);
175+
176+
t.true(
177+
tasks.length <= negativePatterns.length - negativePatternsAtStart.length + 1,
178+
`Unexpected tasks: ${patternsToDebug}`,
179+
);
180+
181+
for (const [index, {patterns, ignore}] of tasks.entries()) {
182+
t.not(
183+
patterns.length,
184+
0,
185+
`Unexpected empty patterns: ${patternsToDebug}`,
186+
);
187+
188+
t.true(
189+
isUnique(patterns),
190+
`patterns should be unique: ${patternsToDebug}`,
191+
);
192+
193+
t.true(
194+
isUnique(ignore),
195+
`ignore should be unique: ${patternsToDebug}`,
196+
);
197+
198+
if (index !== 0 && ignore.length > 0) {
199+
t.deepEqual(
200+
tasks[index - 1].ignore.slice(-ignore.length),
201+
ignore,
202+
`Unexpected ignore: ${patternsToDebug}`,
203+
);
204+
}
205+
}
206+
207+
const allPatterns = tasks.flatMap(({patterns}) => patterns);
208+
const allIgnore = tasks.flatMap(({ignore}) => ignore);
209+
210+
t.is(
211+
new Set(allPatterns).size,
212+
positivePatterns.length,
213+
`positive patterns should be in patterns: ${patternsToDebug}`,
214+
);
215+
216+
t.is(
217+
new Set(allIgnore).size,
218+
negativePatterns.length - negativePatternsAtStart.length,
219+
`negative patterns should be in ignore: ${patternsToDebug}`,
220+
);
221+
}
222+
});

‎tests/globby.js‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -14,6 +14,7 @@ import {
1414
PROJECT_ROOT,
1515
getPathValues,
1616
invalidPatterns,
17+
isUnique,
1718
} from './utilities.js';
1819

1920
const cwd = process.cwd();
@@ -298,6 +299,5 @@ test('don\'t throw when specifying a non-existing cwd directory', async t => {
298299

299300
test('unique when using objectMode option', async t => {
300301
const result = await runGlobby(t, ['a.tmp', '*.tmp'], {cwd, objectMode: true});
301-
const isUnique = array => [...new Set(array)].length === array.length;
302302
t.true(isUnique(result.map(({path}) => path)));
303303
});

‎tests/utilities.js‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,7 +1,9 @@
11
import {fileURLToPath, pathToFileURL} from 'node:url';
22

33
export const PROJECT_ROOT = fileURLToPath(new URL('../', import.meta.url));
4+
45
export const getPathValues = path => [path, pathToFileURL(path)];
6+
57
export const invalidPatterns = [
68
{},
79
[{}],
@@ -20,3 +22,5 @@ export const invalidPatterns = [
2022
function () {},
2123
[function () {}],
2224
];
25+
26+
export const isUnique = array => new Set(array).size === array.length;

0 commit comments

Comments
 (0)