1
// Copyright (c) 2026 Cloudflare, Inc.
2
// Licensed under the Apache 2.0 license found in the LICENSE file or at:
3
//     https://opensource.org/licenses/Apache-2.0
4
 
5
import { default as cffs } from 'cloudflare-internal:filesystem';
6
import type { DirEntryHandle } from 'cloudflare-internal:filesystem';
7
import { normalizePath } from 'node-internal:internal_fs_utils';
8
 
9
// UV_DIRENT_DIR constant from internal_fs_constants
10
const UV_DIRENT_DIR = 2;
11
 
12
// Maximum recursion depth to prevent stack overflow on deeply nested VFS
13
const MAX_WALK_DEPTH = 256;
14
 
15
// ============================================================================
16
// Brace Expansion
17
// ============================================================================
18
 
19
// Splits a string by top-level occurrences of a separator character,
20
// respecting nested braces/parens and backslash escapes.
21
function splitTopLevel(str: string, sep: string): string[] {
22
  const parts: string[] = [];
23
  let depth = 0;
24
  let current = '';
25
 
26
  for (let i = 0; i < str.length; i++) {
27
    const c = str.charAt(i);
28
    if (c === '\\' && i + 1 < str.length) {
29
      current += c + str.charAt(i + 1);
30
      i++;
31
    } else if (c === '{' || c === '(') {
32
      depth++;
33
      current += c;
34
    } else if (c === '}' || c === ')') {
35
      depth--;
36
      current += c;
37
    } else if (c === sep && depth === 0) {
38
      parts.push(current);
39
      current = '';
40
    } else {
41
      current += c;
42
    }
43
  }
44
 
45
  parts.push(current);
46
  return parts;
47
}
48
 
49
// Expands brace expressions in a glob pattern into multiple patterns.
50
export function expandBraces(pattern: string): string[] {
51
  let depth = 0;
52
  let braceStart = -1;
53
 
54
  for (let i = 0; i < pattern.length; i++) {
55
    const c = pattern[i];
56
    if (c === '\\' && i + 1 < pattern.length) {
57
      i++;
58
      continue;
59
    }
60
    if (c === '{') {
61
      if (depth === 0) braceStart = i;
62
      depth++;
63
    } else if (c === '}') {
64
      depth--;
65
      if (depth === 0 && braceStart !== -1) {
66
        const prefix = pattern.slice(0, braceStart);
67
        const body = pattern.slice(braceStart + 1, i);
68
        const suffix = pattern.slice(i + 1);
69
 
70
        const alternatives = splitTopLevel(body, ',');
71
 
72
        if (alternatives.length === 1) {
73
          return [pattern];
74
        }
75
 
76
        const results: string[] = [];
77
        for (const alt of alternatives) {
78
          for (const expanded of expandBraces(prefix + alt + suffix)) {
79
            results.push(expanded);
80
          }
81
        }
82
        return results;
83
      }
84
    }
85
  }
86
 
87
  return [pattern];
88
}
89
 
90
// ============================================================================
91
// Pattern Normalization
92
// ============================================================================
93
 
94
export function normalizePattern(pattern: string): string {
95
  // Strip leading ./
96
  if (pattern.startsWith('./')) {
97
    pattern = pattern.slice(2);
98
  }
99
  // Collapse multiple slashes to single
100
  pattern = pattern.replace(/\/\/+/g, '/');
101
  // Strip trailing slash
102
  if (pattern.endsWith('/') && pattern.length > 1) {
103
    pattern = pattern.slice(0, -1);
104
  }
105
  return pattern;
106
}
107
 
108
// ============================================================================
109
// Segment-Level Regex (with extglob support)
110
// ============================================================================
111
 
112
// Converts a single path segment pattern to a RegExp.
113
// Supports: *, ?, [...], [!...], @(...), *(...), +(...), ?(...), !(...)
114
export function segmentToRegex(segment: string): RegExp {
115
  const regex = segmentToRegexStr(segment);
116
  return new RegExp('^' + regex + '$');
117
}
118
 
119
function segmentToRegexStr(segment: string): string {
120
  let regex = '';
121
  let i = 0;
122
  let inCharClass = false;
123
 
124
  while (i < segment.length) {
125
    const c = segment[i] ?? '';
126
 
127
    // Handle escape sequences
128
    if (c === '\\' && i + 1 < segment.length) {
129
      regex += '\\' + escapeRegexChar(segment[i + 1] ?? '');
130
      i += 2;
131
      continue;
132
    }
133
 
134
    // Inside character classes, most chars are literal
135
    if (inCharClass) {
136
      if (c === ']') {
137
        regex += ']';
138
        inCharClass = false;
139
      } else {
140
        regex += c;
141
      }
142
      i++;
143
      continue;
144
    }
145
 
146
    // Check for extglob: @(...), *(...), +(...), ?(...), !(...)
147
    if (
148
      (c === '@' || c === '*' || c === '+' || c === '?' || c === '!') &&
149
      i + 1 < segment.length &&
150
      segment[i + 1] === '('
151
    ) {
152
      const closeIdx = findMatchingParen(segment, i + 1);
153
      if (closeIdx !== -1) {
154
        const inner = segment.slice(i + 2, closeIdx);
155
        // Convert pipe-separated alternatives, each may contain glob chars
156
        const alts = splitTopLevel(inner, '|');
157
        const altRegexes = alts.map((a) => segmentToRegexStr(a));
158
        const group = altRegexes.join('|');
159
 
160
        switch (c) {
161
          case '@': // exactly one
162
            regex += '(?:' + group + ')';
163
            break;
164
          case '*': // zero or more
165
            regex += '(?:' + group + ')*';
166
            break;
167
          case '+': // one or more
168
            regex += '(?:' + group + ')+';
169
            break;
170
          case '?': // zero or one
171
            regex += '(?:' + group + ')?';
172
            break;
173
          case '!': // none of (negative lookahead)
174
            regex += '(?!(?:' + group + ')$)[^/]*';
175
            break;
176
        }
177
 
178
        i = closeIdx + 1;
179
        continue;
180
      }
181
    }
182
 
183
    switch (c) {
184
      case '[':
185
        inCharClass = true;
186
        regex += '[';
187
        if (i + 1 < segment.length && segment[i + 1] === '!') {
188
          regex += '^';
189
          i++;
190
        }
191
        break;
192
 
193
      case '*':
194
        regex += '[^/]*';
195
        break;
196
 
197
      case '?':
198
        regex += '[^/]';
199
        break;
200
 
201
      case '.':
202
      case '+':
203
      case '^':
204
      case '$':
205
      case '|':
206
      case '(':
207
      case ')':
208
      case '{':
209
      case '}':
210
        regex += '\\' + c;
211
        break;
212
 
213
      default:
214
        regex += c;
215
        break;
216
    }
217
    i++;
218
  }
219
 
220
  return regex;
221
}
222
 
223
function findMatchingParen(str: string, openIdx: number): number {
224
  let depth = 0;
225
  for (let i = openIdx; i < str.length; i++) {
226
    if (str[i] === '\\' && i + 1 < str.length) {
227
      i++;
228
      continue;
229
    }
230
    if (str[i] === '(') depth++;
231
    else if (str[i] === ')') {
232
      depth--;
233
      if (depth === 0) return i;
234
    }
235
  }
236
  return -1;
237
}
238
 
239
function escapeRegexChar(c: string): string {
240
  if ('.+*?^$|()[]{}\\'.includes(c)) {
241
    return '\\' + c;
242
  }
243
  return c;
244
}
245
 
246
// ============================================================================
247
// Full-Path Regex (used for exclude pattern matching)
248
// ============================================================================
249
 
250
// Converts a full glob pattern (with /) to a single RegExp for exclude matching.
251
export function globToRegex(pattern: string): RegExp {
252
  const normalized = normalizePattern(pattern);
253
  const segments = normalized.split('/').filter((s) => s !== '');
254
  const parts: string[] = [];
255
 
256
  for (const seg of segments) {
257
    if (seg === '**') {
258
      // ** matches zero or more path segments
259
      // We handle this by inserting a special marker
260
      parts.push('**');
261
    } else if (seg === '.') {
262
      // skip
263
    } else if (seg === '..') {
264
      parts.pop();
265
    } else {
266
      parts.push(segmentToRegexStr(seg));
267
    }
268
  }
269
 
270
  // Now build regex from parts, handling ** markers
271
  let regex = '';
272
  for (let i = 0; i < parts.length; i++) {
273
    const part = parts[i] ?? '';
274
    const prevPart = i > 0 ? (parts[i - 1] ?? '') : '';
275
    if (part === '**') {
276
      if (parts.length === 1) {
277
        // ** alone: match everything
278
        regex = '.*';
279
      } else if (i === 0) {
280
        // ** at start: match zero or more leading segments
281
        regex += '(?:.*\\/)?';
282
      } else if (i === parts.length - 1) {
283
        // ** at end: match zero or more trailing segments
284
        regex += '(?:\\/.*)?';
285
      } else {
286
        // ** in middle: match zero or more middle segments
287
        regex += '(?:\\/[^/]+)*(?:\\/)?';
288
      }
289
    } else {
290
      if (i > 0 && prevPart !== '**') {
291
        regex += '\\/';
292
      }
293
      regex += part;
294
    }
295
  }
296
 
297
  return new RegExp('^' + regex + '$');
298
}
299
 
300
// ============================================================================
301
// Exclude Compiler
302
// ============================================================================
303
 
304
// Compiles an array of glob patterns into an exclude function.
305
// Only accepts string arrays — user-provided functions are handled
306
// separately in globSync to preserve their (string | Dirent) signature.
307
export function compileExcludePatterns(
308
  exclude: readonly string[]
309
): (path: string) => boolean {
310
  const regexes: RegExp[] = [];
311
  for (const pat of exclude) {
312
    for (const expanded of expandBraces(pat)) {
313
      regexes.push(globToRegex(expanded));
314
    }
315
  }
316
 
317
  return (path: string): boolean => {
318
    for (const re of regexes) {
319
      if (re.test(path)) return true;
320
    }
321
    return false;
322
  };
323
}
324
 
325
// ============================================================================
326
// Directory Entry Cache
327
// ============================================================================
328
 
329
type EntryCache = Map<string, DirEntryHandle[]>;
330
 
331
function getDirectoryEntries(
332
  absPath: string,
333
  cache: EntryCache
334
): DirEntryHandle[] {
335
  const cached = cache.get(absPath);
336
  if (cached !== undefined) return cached;
337
 
338
  try {
339
    const entries = cffs.readdir(normalizePath(absPath), { recursive: false });
340
    cache.set(absPath, entries);
341
    return entries;
342
  } catch {
343
    const empty: DirEntryHandle[] = [];
344
    cache.set(absPath, empty);
345
    return empty;
346
  }
347
}
348
 
349
function isDirectory(entry: DirEntryHandle): boolean {
350
  return entry.type === UV_DIRENT_DIR;
351
}
352
 
353
// ============================================================================
354
// Pattern-Driven Directory Walk
355
// ============================================================================
356
 
357
export interface GlobResult {
358
  relativePath: string;
359
  handle: DirEntryHandle | null;
360
}
361
 
362
// Collapses consecutive '**' segments to prevent exponential blowup.
363
export function collapseGlobstars(segments: string[]): string[] {
364
  const result: string[] = [];
365
  for (const seg of segments) {
366
    if (seg === '**' && result[result.length - 1] === '**') continue;
367
    result.push(seg);
368
  }
369
  return result;
370
}
371
 
372
// Precompiles segment regexes for all non-special segments.
373
export function precompileSegmentRegexes(
374
  segments: string[]
375
): (RegExp | null)[] {
376
  return segments.map((seg) => {
377
    if (seg === '**' || seg === '.' || seg === '..') return null;
378
    return segmentToRegex(seg);
379
  });
380
}
381
 
382
export function walkGlob(
383
  cwd: string,
384
  segments: string[],
385
  segIdx: number,
386
  currentAbsPath: string,
387
  relativePath: string,
388
  results: Map<string, GlobResult>,
389
  cache: EntryCache,
390
  segmentRegexes: (RegExp | null)[],
391
  visitedGlobstar?: Set<string>,
392
  depth: number = 0
393
): void {
394
  // Guard against excessive recursion depth
395
  if (depth >= MAX_WALK_DEPTH) return;
396
 
397
  // All segments consumed: this path is a match
398
  if (segIdx >= segments.length) {
399
    if (!results.has(relativePath)) {
400
      // Resolve handle for the matched path by reading the parent directory
401
      const lastSlash = currentAbsPath.lastIndexOf('/');
402
      const parentDir =
403
        lastSlash > 0 ? currentAbsPath.slice(0, lastSlash) : currentAbsPath;
404
      const basename = relativePath.split('/').pop() ?? '';
405
      const entries = getDirectoryEntries(parentDir, cache);
406
      const handle = entries.find((e) => e.name === basename) ?? null;
407
      results.set(relativePath, { relativePath, handle });
408
    }
409
    return;
410
  }
411
 
412
  const seg = segments[segIdx] ?? '';
413
 
414
  // Handle '.' — stay in current directory
415
  if (seg === '.') {
416
    walkGlob(
417
      cwd,
418
      segments,
419
      segIdx + 1,
420
      currentAbsPath,
421
      relativePath,
422
      results,
423
      cache,
424
      segmentRegexes,
425
      visitedGlobstar,
426
      depth
427
    );
428
    return;
429
  }
430
 
431
  // Handle '..' — go up one directory (but don't escape cwd)
432
  if (seg === '..') {
433
    if (currentAbsPath === cwd || !currentAbsPath.startsWith(cwd + '/')) {
434
      return;
435
    }
436
 
437
    const lastSlash = currentAbsPath.lastIndexOf('/');
438
    const newAbs = lastSlash > 0 ? currentAbsPath.slice(0, lastSlash) : '/';
439
 
440
    const relParts = relativePath.split('/').filter(Boolean);
441
    relParts.pop();
442
    const newRel = relParts.join('/');
443
 
444
    walkGlob(
445
      cwd,
446
      segments,
447
      segIdx + 1,
448
      newAbs,
449
      newRel,
450
      results,
451
      cache,
452
      segmentRegexes,
453
      visitedGlobstar,
454
      depth
455
    );
456
    return;
457
  }
458
 
459
  // Handle '**' — match zero or more directory levels
460
  if (seg === '**') {
461
    const gsKey = `${currentAbsPath}:${String(segIdx)}`;
462
    if (visitedGlobstar === undefined) {
463
      visitedGlobstar = new Set();
464
    }
465
    if (visitedGlobstar.has(gsKey)) return;
466
    visitedGlobstar.add(gsKey);
467
 
468
    // Zero levels: advance to next segment at current path
469
    walkGlob(
470
      cwd,
471
      segments,
472
      segIdx + 1,
473
      currentAbsPath,
474
      relativePath,
475
      results,
476
      cache,
477
      segmentRegexes,
478
      visitedGlobstar,
479
      depth
480
    );
481
 
482
    // One or more levels: enumerate children
483
    const entries = getDirectoryEntries(currentAbsPath, cache);
484
    for (const entry of entries) {
485
      const childAbs = currentAbsPath + '/' + entry.name;
486
      const childRel = relativePath
487
        ? relativePath + '/' + entry.name
488
        : entry.name;
489
 
490
      // Try matching next segment against this child
491
      walkGlob(
492
        cwd,
493
        segments,
494
        segIdx + 1,
495
        childAbs,
496
        childRel,
497
        results,
498
        cache,
499
        segmentRegexes,
500
        visitedGlobstar,
501
        depth + 1
502
      );
503
 
504
      // If directory, recurse ** deeper
505
      if (isDirectory(entry)) {
506
        walkGlob(
507
          cwd,
508
          segments,
509
          segIdx,
510
          childAbs,
511
          childRel,
512
          results,
513
          cache,
514
          segmentRegexes,
515
          visitedGlobstar,
516
          depth + 1
517
        );
518
      }
519
    }
520
    return;
521
  }
522
 
523
  // Regular segment: match against precompiled regex
524
  const segRegex = segmentRegexes[segIdx] ?? segmentToRegex(seg);
525
  const entries = getDirectoryEntries(currentAbsPath, cache);
526
 
527
  for (const entry of entries) {
528
    if (segRegex.test(entry.name)) {
529
      const childAbs = currentAbsPath + '/' + entry.name;
530
      const childRel = relativePath
531
        ? relativePath + '/' + entry.name
532
        : entry.name;
533
 
534
      if (segIdx + 1 >= segments.length) {
535
        // This is the last segment — record match
536
        if (!results.has(childRel)) {
537
          results.set(childRel, { relativePath: childRel, handle: entry });
538
        }
539
      } else {
540
        // More segments to match — recurse
541
        walkGlob(
542
          cwd,
543
          segments,
544
          segIdx + 1,
545
          childAbs,
546
          childRel,
547
          results,
548
          cache,
549
          segmentRegexes,
550
          visitedGlobstar,
551
          depth + 1
552
        );
553
      }
554
    }
555
  }
556
}