const std = @import("std");
const ignore = @import("ignore.zig");

/// Thread-safe work queue for parallel directory walking
const WorkQueue = struct {
    items: std.ArrayList(WorkItem),
    mutex: std.Thread.Mutex,
    condition: std.Thread.Condition,
    done: bool,

    const WorkItem = struct {
        path: []const u8,
        depth: usize,
    };

    fn init() WorkQueue {
        return .{
            .items = .empty,
            .mutex = .{},
            .condition = .{},
            .done = false,
        };
    }

    fn deinit(self: *WorkQueue, allocator: std.mem.Allocator) void {
        for (self.items.items) |item| {
            allocator.free(item.path);
        }
        self.items.deinit();
    }

    fn push(self: *WorkQueue, path: []const u8, depth: usize, allocator: std.mem.Allocator) !void {
        self.mutex.lock();
        defer self.mutex.unlock();

        try self.items.append(.{
            .path = try allocator.dupe(u8, path),
            .depth = depth,
        });
        self.condition.signal();
    }

    fn pop(self: *WorkQueue) ?WorkItem {
        self.mutex.lock();
        defer self.mutex.unlock();

        while (self.items.items.len == 0 and !self.done) {
            self.condition.wait(&self.mutex);
        }

        if (self.items.items.len == 0) return null;
        return self.items.pop();
    }

    fn setDone(self: *WorkQueue) void {
        self.mutex.lock();
        defer self.mutex.unlock();
        self.done = true;
        self.condition.broadcast();
    }
};

/// Result from parallel directory walk
const WalkResult = struct {
    files: std.ArrayList([]const u8),
    mutex: std.Thread.Mutex,

    fn init(allocator: std.mem.Allocator) WalkResult {
        return .{
            .files = std.ArrayList([]const u8).init(allocator),
            .mutex = .{},
        };
    }

    fn deinit(self: *WalkResult, allocator: std.mem.Allocator) void {
        for (self.files.items) |file| {
            allocator.free(file);
        }
        self.files.deinit();
    }

    fn add(self: *WalkResult, path: []const u8, allocator: std.mem.Allocator) !void {
        self.mutex.lock();
        defer self.mutex.unlock();
        try self.files.append(try allocator.dupe(u8, path));
    }
};

/// Thread context for parallel walking
const ThreadContext = struct {
    queue: *WorkQueue,
    result: *WalkResult,
    gitignore: *ignore.GitIgnore,
    base_path: []const u8,
    allocator: std.mem.Allocator,
    max_depth: usize,
};

/// Worker thread function for parallel directory walking
fn walkWorker(ctx: *ThreadContext) void {
    while (true) {
        const item = ctx.queue.pop() orelse break;
        defer ctx.allocator.free(item.path);

        if (item.depth >= ctx.max_depth) continue;

        walkDirectoryParallel(ctx, item.path, item.depth) catch |err| {
            std.log.warn("Error walking {s}: {any}", .{ item.path, err });
        };
    }
}

/// Walk a single directory and add subdirectories to queue
fn walkDirectoryParallel(ctx: *ThreadContext, dir_path: []const u8, depth: usize) !void {
    const full_path = if (std.mem.eql(u8, dir_path, "."))
        ctx.base_path
    else
        try std.fs.path.join(ctx.allocator, &[_][]const u8{ ctx.base_path, dir_path });
    defer if (!std.mem.eql(u8, dir_path, ".")) ctx.allocator.free(full_path);

    var dir = std.fs.cwd().openDir(full_path, .{ .iterate = true }) catch |err| switch (err) {
        error.AccessDenied => return,
        error.FileNotFound => return,
        else => return err,
    };
    defer dir.close();

    var it = dir.iterate();
    while (true) {
        const entry = it.next() catch |err| switch (err) {
            error.AccessDenied => continue,
            else => return err,
        } orelse break;

        const entry_path = if (std.mem.eql(u8, dir_path, "."))
            try std.fmt.allocPrint(ctx.allocator, "{s}", .{entry.name})
        else
            try std.fs.path.join(ctx.allocator, &[_][]const u8{ dir_path, entry.name });
        defer ctx.allocator.free(entry_path);

        // Check default ignores
        if (ignore.matchesDefaultIgnore(entry_path)) continue;

        // Check gitignore patterns
        const is_dir = entry.kind == .directory;
        if (ctx.gitignore.isIgnored(entry_path, is_dir)) continue;

        if (is_dir) {
            // Add subdirectory to work queue
            ctx.queue.push(entry_path, depth + 1, ctx.allocator) catch |err| {
                std.log.warn("Failed to queue {s}: {any}", .{ entry_path, err });
            };
        } else if (entry.kind == .file) {
            // Add file to results
            ctx.result.add(entry_path, ctx.allocator) catch |err| {
                std.log.warn("Failed to add file {s}: {any}", .{ entry_path, err });
            };
        }
    }
}

/// Parallel directory walker that uses multiple threads
pub fn parallelWalk(
    allocator: std.mem.Allocator,
    base_path: []const u8,
    gitignore: *ignore.GitIgnore,
    num_threads: usize,
) ![][]const u8 {
    var queue = WorkQueue.init(allocator);
    defer queue.deinit(allocator);

    var result = WalkResult.init(allocator);
    defer result.deinit(allocator);

    // Start with base directory
    try queue.push(".", 0, allocator);

    // Create thread context
    var ctx = ThreadContext{
        .queue = &queue,
        .result = &result,
        .gitignore = gitignore,
        .base_path = base_path,
        .allocator = allocator,
        .max_depth = 100, // Prevent infinite recursion
    };

    // Spawn worker threads
    var threads = try allocator.alloc(std.Thread, num_threads);
    defer allocator.free(threads);

    for (0..num_threads) |i| {
        threads[i] = try std.Thread.spawn(.{}, walkWorker, .{&ctx});
    }

    // Wait for all workers to complete
    for (threads) |thread| {
        thread.join();
    }

    // Sort results for deterministic ordering
    std.sort.block([]const u8, result.files.items, {}, struct {
        fn lessThan(_: void, a: []const u8, b: []const u8) bool {
            return std.mem.order(u8, a, b) == .lt;
        }
    }.lessThan);

    // Transfer ownership to caller
    const files = try allocator.alloc([]const u8, result.files.items.len);
    @memcpy(files, result.files.items);
    result.files.items.len = 0; // Prevent deinit from freeing

    return files;
}

test "parallelWalk basic" {
    const allocator = std.testing.allocator;

    var gitignore = ignore.GitIgnore.init(allocator);
    defer gitignore.deinit();

    // Walk the current directory with 4 threads
    const files = try parallelWalk(allocator, ".", &gitignore, 4);
    defer {
        for (files) |f| allocator.free(f);
        allocator.free(files);
    }

    // Should find at least some files
    try std.testing.expect(files.len > 0);
}
