Something went wrong. Try again.
My version of https://github.com/vercel-labs/fx
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251const std = @import("std");
const Allocator = std.mem.Allocator;
/// Maximum accepted glob pattern length in bytes.pub const max_pattern_bytes: usize = 4096;
const max_pattern_segments: usize = max_pattern_bytes + 1;
/// Error set for compiling a borrowed glob pattern.pub const CompileError = error{ OutOfMemory, PatternTooLong,};
/// Borrowed, pre-split glob pattern for matching workspace paths.pub const Pattern = struct { raw: []const u8, segments: []const []const u8, has_path_separator: bool,
/// Compiles a borrowed pattern. Caller owns the segment slice and releases it with deinit. pub fn compile(alloc: Allocator, raw: []const u8) CompileError!Pattern { if (raw.len > max_pattern_bytes) return error.PatternTooLong;
const has_path_separator = std.mem.findScalar(u8, raw, '/') != null; if (!has_path_separator) { return .{ .raw = raw, .segments = &.{}, .has_path_separator = false, }; }
var segments: std.ArrayList([]const u8) = .empty; errdefer segments.deinit(alloc); try appendSegments(alloc, raw, &segments); return .{ .raw = raw, .segments = try segments.toOwnedSlice(alloc), .has_path_separator = true, }; }
/// Frees the owned segment slice. The raw pattern bytes are borrowed. pub fn deinit(self: *Pattern, alloc: Allocator) void { if (self.has_path_separator) alloc.free(self.segments); self.* = .{ .raw = "", .segments = &.{}, .has_path_separator = false, }; }
/// Returns true when the pattern matches a path. Patterns without slash match the basename. pub fn matchesPath(self: Pattern, candidate_path: []const u8) bool { if (!self.has_path_separator) { return matchSegment(self.raw, std.fs.path.basename(candidate_path)); } return matchSegmented(self.segments, candidate_path); }
/// Returns true when a slash-free pattern matches a single basename. pub fn matchesBasename(self: Pattern, basename: []const u8) bool { if (self.has_path_separator) return false; return matchSegment(self.raw, basename); }};
fn appendSegments(alloc: Allocator, path: []const u8, segments: *std.ArrayList([]const u8)) Allocator.Error!void { var rest = path; while (rest.len > 0) { const slash = std.mem.findScalar(u8, rest, '/') orelse { try segments.append(alloc, rest); return; }; try segments.append(alloc, rest[0..slash]); rest = rest[slash + 1 ..]; }}
fn matchSegmented(pattern_segments: []const []const u8, candidate_path: []const u8) bool { const segment_count = pattern_segments.len; std.debug.assert(segment_count <= max_pattern_segments);
var previous: [max_pattern_segments + 1]bool = [_]bool{false} ** (max_pattern_segments + 1); var current: [max_pattern_segments + 1]bool = [_]bool{false} ** (max_pattern_segments + 1);
previous[0] = true; for (pattern_segments, 0..) |segment, index| { previous[index + 1] = previous[index] and isDoubleStar(segment); }
var candidate_it = SegmentIterator.init(candidate_path); while (candidate_it.next()) |candidate_segment| { @memset(current[0 .. segment_count + 1], false); for (pattern_segments, 0..) |pattern_segment, index| { current[index + 1] = if (isDoubleStar(pattern_segment)) current[index] or previous[index + 1] else previous[index] and matchSegment(pattern_segment, candidate_segment); } @memcpy(previous[0 .. segment_count + 1], current[0 .. segment_count + 1]); }
return previous[segment_count];}
const SegmentIterator = struct { rest: []const u8,
fn init(path: []const u8) SegmentIterator { return .{ .rest = path }; }
fn next(self: *SegmentIterator) ?[]const u8 { if (self.rest.len == 0) return null; const slash = std.mem.findScalar(u8, self.rest, '/') orelse { const segment = self.rest; self.rest = ""; return segment; }; const segment = self.rest[0..slash]; self.rest = self.rest[slash + 1 ..]; return segment; }};
fn isDoubleStar(segment: []const u8) bool { return std.mem.eql(u8, segment, "**");}
fn matchSegment(pattern: []const u8, candidate: []const u8) bool { var pattern_index: usize = 0; var candidate_index: usize = 0; var star_pattern_index: ?usize = null; var star_candidate_index: usize = 0;
while (candidate_index < candidate.len) { if (pattern_index < pattern.len) { const token = pattern[pattern_index]; if (token == '*') { while (pattern_index < pattern.len and pattern[pattern_index] == '*') { pattern_index += 1; } if (pattern_index == pattern.len) return true; star_pattern_index = pattern_index; star_candidate_index = candidate_index; continue; } if (token == '?' or token == candidate[candidate_index]) { if (candidate[candidate_index] == '/') return false; pattern_index += 1; candidate_index += 1; continue; } }
const retry_pattern_index = star_pattern_index orelse return false; star_candidate_index += 1; candidate_index = star_candidate_index; pattern_index = retry_pattern_index; }
while (pattern_index < pattern.len and pattern[pattern_index] == '*') { pattern_index += 1; } return pattern_index == pattern.len;}
fn expectCompiledMatch(pattern: []const u8, candidate_path: []const u8, expected: bool) !void { var compiled = try Pattern.compile(std.testing.allocator, pattern); defer compiled.deinit(std.testing.allocator); try std.testing.expectEqual(expected, compiled.matchesPath(candidate_path));}
test "glob pattern matches recursive and segment wildcards" { try expectCompiledMatch("**/*.zig", "main.zig", true); try expectCompiledMatch("**/*.zig", "src/core/main.zig", true); try expectCompiledMatch("*.zig", "src/main.zig", true); try expectCompiledMatch("file?.zig", "dir/file1.zig", true); try expectCompiledMatch("file?.zig", "dir/file12.zig", false); try expectCompiledMatch("foo\\bar.txt", "src/foo\\bar.txt", true); try expectCompiledMatch("src/*.zig", "src/main.zig", true); try expectCompiledMatch("src/*.zig", "src/core/main.zig", false); try expectCompiledMatch("src/*.zig", "lib/src/main.zig", false);}
test "glob pattern preserves globstar zero-or-more segment semantics" { try expectCompiledMatch("**", "", true); try expectCompiledMatch("src/", "src", true); try expectCompiledMatch("src/**", "src", true); try expectCompiledMatch("src/**", "src/core/main.zig", true); try expectCompiledMatch("src/**/main.zig", "src/main.zig", true); try expectCompiledMatch("src/**/main.zig", "src/core/nested/main.zig", true); try expectCompiledMatch("src/**/main.zig", "lib/src/core/main.zig", false);}
test "glob pattern treats backslashes literally" { try expectCompiledMatch("dir\\*.zig", "dir\\main.zig", true); try expectCompiledMatch("dir\\*.zig", "dir/main.zig", false);}
test "glob pattern handles adversarial repeated-star nonmatches without recursion" { const alloc = std.testing.allocator; const star_count = 1024;
var consecutive = try alloc.alloc(u8, star_count + 1); defer alloc.free(consecutive); @memset(consecutive[0..star_count], '*'); consecutive[star_count] = 'z';
const candidate = try alloc.alloc(u8, star_count); defer alloc.free(candidate); @memset(candidate, 'a');
var compiled_consecutive = try Pattern.compile(alloc, consecutive); defer compiled_consecutive.deinit(alloc); try std.testing.expect(!compiled_consecutive.matchesPath(candidate));
var separated: std.Io.Writer.Allocating = .init(alloc); defer separated.deinit(); var i: usize = 0; while (i < 512) : (i += 1) { try separated.writer.writeAll("*a"); } try separated.writer.writeByte('z'); const separated_pattern = try separated.toOwnedSlice(); defer alloc.free(separated_pattern);
var compiled_separated = try Pattern.compile(alloc, separated_pattern); defer compiled_separated.deinit(alloc); try std.testing.expect(!compiled_separated.matchesPath(candidate));}
test "glob pattern rejects patterns beyond the maximum accepted length" { const alloc = std.testing.allocator;
const accepted = try alloc.alloc(u8, max_pattern_bytes); defer alloc.free(accepted); @memset(accepted, 'a'); var accepted_pattern = try Pattern.compile(alloc, accepted); defer accepted_pattern.deinit(alloc); try std.testing.expect(accepted_pattern.matchesPath(accepted));
const rejected = try alloc.alloc(u8, max_pattern_bytes + 1); defer alloc.free(rejected); @memset(rejected, 'a'); try std.testing.expectError(error.PatternTooLong, Pattern.compile(alloc, rejected));}