const 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));
}