const Watch = @This();
const builtin = @import("builtin");

const std = @import("std");
const Io = std.Io;
const Allocator = std.mem.Allocator;
const assert = std.debug.assert;
const fatal = std.process.fatal;
const Configuration = std.Build.Configuration;

const FsEvents = @import("Watch/FsEvents.zig");
const Step = @import("Step.zig");
const Maker = @import("../Maker.zig");

os: Os,
/// The number to show as the number of directories being watched.
dir_count: usize,
// These fields are common to most implementations so are kept here for simplicity.
// They are `undefined` on implementations which do not utilize then.
dir_table: DirTable,
generation: Generation,
maker: *Maker,

pub const have_impl = Os != void;

/// Key is the directory to watch which contains one or more files we are
/// interested in noticing changes to.
///
/// Value is generation.
const DirTable = std.array_hash_map.Custom(Cache.Path, void, Cache.Path.TableAdapter, false);

/// Special key of "." means any changes in this directory trigger the steps.
const ReactionSet = std.array_hash_map.String(StepSet);
const StepSet = std.array_hash_map.Auto(Configuration.Step.Index, Generation);

const Generation = u8;

const Hash = std.hash.Wyhash;
const Cache = std.Build.Cache;

const Os = switch (builtin.os.tag) {
    .linux => struct {
        const posix = std.posix;

        /// Keyed differently but indexes correspond 1:1 with `dir_table`.
        handle_table: HandleTable,
        /// fanotify file descriptors are keyed by mount id since marks
        /// are limited to a single filesystem.
        poll_fds: std.array_hash_map.Auto(MountId, posix.pollfd),

        const MountId = i32;
        const HandleTable = std.array_hash_map.Custom(FileHandle, struct {
            mount_id: MountId,
            reaction_set: ReactionSet,
        }, FileHandle.Adapter, false);

        const fan_mask: std.os.linux.fanotify.MarkMask = .{
            .CLOSE_WRITE = true,
            .CREATE = true,
            .DELETE = true,
            .DELETE_SELF = true,
            .EVENT_ON_CHILD = true,
            .MOVED_FROM = true,
            .MOVED_TO = true,
            .MOVE_SELF = true,
            .ONDIR = true,
        };

        const FileHandle = struct {
            handle: *align(1) std.os.linux.file_handle,

            fn clone(lfh: FileHandle, gpa: Allocator) Allocator.Error!FileHandle {
                const bytes = lfh.slice();
                const new_ptr = try gpa.alignedAlloc(
                    u8,
                    .of(std.os.linux.file_handle),
                    @sizeOf(std.os.linux.file_handle) + bytes.len,
                );
                const new_header: *std.os.linux.file_handle = @ptrCast(new_ptr);
                new_header.* = lfh.handle.*;
                const new: FileHandle = .{ .handle = new_header };
                @memcpy(new.slice(), lfh.slice());
                return new;
            }

            fn destroy(lfh: FileHandle, gpa: Allocator) void {
                const ptr: [*]align(@alignOf(std.os.linux.file_handle)) u8 = @ptrCast(@alignCast(lfh.handle));
                const allocated_slice = ptr[0 .. @sizeOf(std.os.linux.file_handle) + lfh.handle.handle_bytes];
                return gpa.free(allocated_slice);
            }

            fn slice(lfh: FileHandle) []u8 {
                const ptr: [*]u8 = &lfh.handle.f_handle;
                return ptr[0..lfh.handle.handle_bytes];
            }

            const Adapter = struct {
                pub fn hash(self: Adapter, a: FileHandle) u32 {
                    _ = self;
                    const unsigned_type: u32 = @bitCast(a.handle.handle_type);
                    return @truncate(Hash.hash(unsigned_type, a.slice()));
                }
                pub fn eql(self: Adapter, a: FileHandle, b: FileHandle, b_index: usize) bool {
                    _ = self;
                    _ = b_index;
                    return a.handle.handle_type == b.handle.handle_type and std.mem.eql(u8, a.slice(), b.slice());
                }
            };
        };

        fn init(maker: *Maker) !Watch {
            return .{
                .dir_table = .{},
                .dir_count = 0,
                .os = switch (builtin.os.tag) {
                    .linux => .{
                        .handle_table = .{},
                        .poll_fds = .{},
                    },
                    else => {},
                },
                .generation = 0,
                .maker = maker,
            };
        }

        fn deinit(w: *Watch) void {
            const gpa = w.maker.gpa;

            for (w.os.handle_table.keys(), w.os.handle_table.values()) |fh, *reaction| {
                fh.destroy(gpa);
                reaction.reaction_set.deinit(gpa);
            }
            w.os.handle_table.deinit(gpa);

            for (w.os.poll_fds.values()) |pollfd| {
                Io.Threaded.closeFd(pollfd.fd);
            }
            w.os.poll_fds.deinit(gpa);

            w.dir_table.deinit(gpa);
            w.* = undefined;
        }

        fn getDirHandle(gpa: Allocator, path: std.Build.Cache.Path, mount_id: *MountId) !FileHandle {
            var file_handle_buffer: [@sizeOf(std.os.linux.file_handle) + 128]u8 align(@alignOf(std.os.linux.file_handle)) = undefined;
            var buf: [std.fs.max_path_bytes]u8 = undefined;
            const adjusted_path = if (path.sub_path.len == 0) "./" else std.mem.print(&buf, "{s}/", .{
                path.sub_path,
            }) catch return error.NameTooLong;
            const stack_ptr: *std.os.linux.file_handle = @ptrCast(&file_handle_buffer);
            stack_ptr.handle_bytes = file_handle_buffer.len - @sizeOf(std.os.linux.file_handle);
            try posix.name_to_handle_at(path.root_dir.handle.handle, adjusted_path, stack_ptr, mount_id, std.os.linux.AT.HANDLE_FID);
            const stack_lfh: FileHandle = .{ .handle = stack_ptr };
            return stack_lfh.clone(gpa);
        }

        fn markDirtySteps(w: *Watch, fan_fd: posix.fd_t) !bool {
            const maker = w.maker;
            const fanotify = std.os.linux.fanotify;
            const M = fanotify.event_metadata;
            var events_buf: [256 + 4096]u8 = undefined;
            var any_dirty = false;
            while (true) {
                var len = posix.read(fan_fd, &events_buf) catch |err| switch (err) {
                    error.WouldBlock => return any_dirty,
                    else => |e| return e,
                };
                var meta: [*]align(1) M = @ptrCast(&events_buf);
                while (len >= @sizeOf(M) and meta[0].event_len >= @sizeOf(M) and meta[0].event_len <= len) : ({
                    len -= meta[0].event_len;
                    meta = @ptrCast(@as([*]u8, @ptrCast(meta)) + meta[0].event_len);
                }) {
                    assert(meta[0].vers == M.VERSION);
                    if (meta[0].mask.Q_OVERFLOW) {
                        std.log.warn("file system watch queue overflowed; reconfiguring", .{});
                        return error.MustReconfigure;
                    }
                    const fid: *align(1) fanotify.event_info_fid = @ptrCast(meta + 1);
                    switch (fid.hdr.info_type) {
                        .DFID_NAME => {
                            const file_handle: *align(1) std.os.linux.file_handle = @ptrCast(&fid.handle);
                            const file_name_z: [*:0]u8 = @ptrCast((&file_handle.f_handle).ptr + file_handle.handle_bytes);
                            const file_name = std.mem.span(file_name_z);
                            const lfh: FileHandle = .{ .handle = file_handle };
                            if (w.os.handle_table.getPtr(lfh)) |value| {
                                if (value.reaction_set.getPtr(".")) |glob_set|
                                    any_dirty = try markStepSetDirty(maker, glob_set, any_dirty);
                                if (value.reaction_set.getPtr(file_name)) |step_set|
                                    any_dirty = try markStepSetDirty(maker, step_set, any_dirty);
                            }
                        },
                        else => |t| std.log.warn("unexpected fanotify event '{t}'", .{t}),
                    }
                }
            }
        }

        fn update(w: *Watch, steps: []const Configuration.Step.Index) !void {
            const maker = w.maker;
            const gpa = maker.gpa;

            // Add missing marks and note persisted ones.
            for (steps) |step_index| {
                const step = maker.stepByIndex(step_index);
                for (step.inputs.table.keys(), step.inputs.table.values()) |path, *files| {
                    const reaction_set = rs: {
                        const gop = try w.dir_table.getOrPut(gpa, path);
                        if (!gop.found_existing) {
                            var mount_id: MountId = undefined;
                            const dir_handle = getDirHandle(gpa, path, &mount_id) catch |err| switch (err) {
                                error.FileNotFound => {
                                    std.debug.assert(w.dir_table.swapRemove(path));
                                    continue;
                                },
                                else => return err,
                            };
                            const fan_fd = blk: {
                                const fd_gop = try w.os.poll_fds.getOrPut(gpa, mount_id);
                                if (!fd_gop.found_existing) {
                                    const fan_fd = std.posix.fanotify_init(.{
                                        .CLASS = .NOTIF,
                                        .CLOEXEC = true,
                                        .NONBLOCK = true,
                                        .REPORT_NAME = true,
                                        .REPORT_DIR_FID = true,
                                        .REPORT_FID = true,
                                        .REPORT_TARGET_FID = true,
                                    }, 0) catch |err| switch (err) {
                                        error.UnsupportedFlags => fatal("fanotify_init failed due to old kernel; requires 5.17+", .{}),
                                        else => |e| return e,
                                    };
                                    fd_gop.value_ptr.* = .{
                                        .fd = fan_fd,
                                        .events = std.posix.POLL.IN,
                                    };
                                }
                                break :blk fd_gop.value_ptr.*.fd;
                            };
                            // `dir_handle` may already be present in the table in
                            // the case that we have multiple Cache.Path instances
                            // that compare inequal but ultimately point to the same
                            // directory on the file system.
                            // In such case, we must revert adding this directory, but keep
                            // the additions to the step set.
                            const dh_gop = try w.os.handle_table.getOrPut(gpa, dir_handle);
                            if (dh_gop.found_existing) {
                                _ = w.dir_table.pop();
                            } else {
                                assert(dh_gop.index == gop.index);
                                dh_gop.value_ptr.* = .{ .mount_id = mount_id, .reaction_set = .{} };
                                posix.fanotify_mark(fan_fd, .{
                                    .ADD = true,
                                    .ONLYDIR = true,
                                }, fan_mask, path.root_dir.handle.handle, path.subPathOrDot()) catch |err|
                                    fatal("unable to watch {f}: {t}", .{ path, err });
                            }
                            break :rs &dh_gop.value_ptr.reaction_set;
                        }
                        break :rs &w.os.handle_table.values()[gop.index].reaction_set;
                    };
                    for (files.items) |basename| {
                        const gop = try reaction_set.getOrPut(gpa, basename);
                        if (!gop.found_existing) gop.value_ptr.* = .{};
                        try gop.value_ptr.put(gpa, step_index, w.generation);
                    }
                }
            }

            {
                // Remove marks for files that are no longer inputs.
                var i: usize = 0;
                while (i < w.os.handle_table.entries.len) {
                    {
                        const reaction_set = &w.os.handle_table.values()[i].reaction_set;
                        var step_set_i: usize = 0;
                        while (step_set_i < reaction_set.entries.len) {
                            const step_set = &reaction_set.values()[step_set_i];
                            var dirent_i: usize = 0;
                            while (dirent_i < step_set.entries.len) {
                                const generations = step_set.values();
                                if (generations[dirent_i] == w.generation) {
                                    dirent_i += 1;
                                    continue;
                                }
                                step_set.swapRemoveAt(dirent_i);
                            }
                            if (step_set.entries.len > 0) {
                                step_set_i += 1;
                                continue;
                            }
                            reaction_set.swapRemoveAt(step_set_i);
                        }
                        if (reaction_set.entries.len > 0) {
                            i += 1;
                            continue;
                        }
                    }

                    const path = w.dir_table.keys()[i];

                    const mount_id = w.os.handle_table.values()[i].mount_id;
                    const fan_fd = w.os.poll_fds.getEntry(mount_id).?.value_ptr.fd;
                    posix.fanotify_mark(fan_fd, .{
                        .REMOVE = true,
                        .ONLYDIR = true,
                    }, fan_mask, path.root_dir.handle.handle, path.subPathOrDot()) catch |err| switch (err) {
                        error.FileNotFound => {}, // Expected, harmless.
                        else => |e| std.log.warn("unable to unwatch {f}: {t}", .{ path, e }),
                    };

                    w.dir_table.swapRemoveAt(i);
                    w.os.handle_table.swapRemoveAt(i);
                }
                w.generation +%= 1;
            }
            w.dir_count = w.dir_table.count();
        }

        fn wait(w: *Watch, timeout: Timeout) !WaitResult {
            const events_len = try std.posix.poll(w.os.poll_fds.values(), timeout.to_i32_ms());
            if (events_len == 0)
                return .timeout;
            for (w.os.poll_fds.values()) |poll_fd| {
                if (poll_fd.revents & std.posix.POLL.IN == std.posix.POLL.IN and
                    try markDirtySteps(w, poll_fd.fd))
                {
                    return .dirty;
                }
            }
            return .clean;
        }
    },
    .windows => struct {
        const windows = std.os.windows;

        /// Keyed differently but indexes correspond 1:1 with `dir_table`.
        handle_table: std.array_hash_map.Custom(*Directory, void, Directory.TableAdapter, false),
        ready_dirs: std.DoublyLinkedList,

        const FileId = struct {
            volumeSerialNumber: windows.ULONG,
            indexNumber: windows.LARGE_INTEGER,
        };

        const Directory = struct {
            reaction_set: ReactionSet,
            id: FileId,
            file: Io.File,
            state: enum { idle, listening, ready },
            iosb: windows.IO_STATUS_BLOCK,
            // 64 KB is the packet size limit when monitoring over a network.
            // https://learn.microsoft.com/en-us/windows/win32/api/winbase/nf-winbase-readdirectorychangesw#remarks
            buffer: [64 * 1024]u8 align(@alignOf(windows.FILE.NOTIFY.INFORMATION)),
            ready_node: std.DoublyLinkedList.Node,

            /// Start listening for events, buffer field will be overwritten eventually.
            fn startListening(dir: *Directory, w: *Watch) !void {
                assert(dir.file.flags.nonblocking);
                assert(dir.state == .idle);
                switch (windows.ntdll.NtNotifyChangeDirectoryFileEx(
                    dir.file.handle,
                    null,
                    &notifyApc,
                    w,
                    &dir.iosb,
                    &dir.buffer,
                    dir.buffer.len,
                    .{
                        .FILE_NAME = true,
                        .DIR_NAME = true,
                        .SIZE = true,
                        .LAST_WRITE = true,
                        .CREATION = true,
                    },
                    .FALSE,
                    .Notify,
                )) {
                    .SUCCESS, .PENDING => dir.state = .listening,
                    .ILLEGAL_FUNCTION => return error.ReadDirectoryChangesUnsupported,
                    else => |status| return windows.unexpectedStatus(status),
                }
            }

            fn notifyApc(apc_context: ?*anyopaque, iosb: *windows.IO_STATUS_BLOCK, _: windows.ULONG) align(Io.Threaded.apc_align) callconv(.winapi) void {
                const w: *Watch = @ptrCast(@alignCast(apc_context));
                const dir: *Directory = @fieldParentPtr("iosb", iosb);
                assert(iosb.u.Status != .PENDING);
                assert(dir.state == .listening);
                w.os.ready_dirs.append(&dir.ready_node);
                dir.state = .ready;
            }

            fn init(gpa: Allocator, path: Cache.Path) !*Directory {
                // The following code is a drawn out NtCreateFile call. (mostly adapted from Io.Dir.makeOpenDirAccessMaskW)
                // It's necessary in order to get the specific flags that are required when calling ReadDirectoryChangesW.
                var dir_handle: windows.HANDLE = undefined;
                const root_fd = path.root_dir.handle.handle;
                const sub_path = path.subPathOrDot();
                const sub_path_w = try Io.Threaded.sliceToPrefixedFileW(root_fd, sub_path, .{}); // TODO eliminate this call
                var iosb: windows.IO_STATUS_BLOCK = undefined;
                switch (windows.ntdll.NtCreateFile(
                    &dir_handle,
                    .{
                        .SPECIFIC = .{ .FILE_DIRECTORY = .{
                            .LIST = true,
                        } },
                        .STANDARD = .{ .SYNCHRONIZE = true },
                        .GENERIC = .{ .READ = true },
                    },
                    &.{
                        .RootDirectory = if (std.fs.path.isAbsoluteWindowsW(sub_path_w.span())) null else root_fd,
                        .ObjectName = @constCast(&sub_path_w.string()),
                    },
                    &iosb,
                    null,
                    .{},
                    .VALID_FLAGS,
                    .OPEN,
                    .{
                        .DIRECTORY_FILE = true,
                        .IO = .ASYNCHRONOUS,
                        .OPEN_FOR_BACKUP_INTENT = true,
                    },
                    null,
                    0,
                )) {
                    .SUCCESS => {},
                    .OBJECT_NAME_INVALID => return error.BadPathName,
                    .OBJECT_NAME_NOT_FOUND => return error.FileNotFound,
                    .OBJECT_NAME_COLLISION => return error.PathAlreadyExists,
                    .OBJECT_PATH_NOT_FOUND => return error.FileNotFound,
                    .NOT_A_DIRECTORY => return error.NotDir,
                    // This can happen if the directory has 'List folder contents' permission set to 'Deny'
                    .ACCESS_DENIED => return error.AccessDenied,
                    .INVALID_PARAMETER => unreachable,
                    else => |rc| return windows.unexpectedStatus(rc),
                }
                assert(dir_handle != windows.INVALID_HANDLE_VALUE);
                errdefer windows.CloseHandle(dir_handle);

                const dir_id = try getFileId(dir_handle);

                const dir = try gpa.create(Directory);
                dir.* = .{
                    .reaction_set = .empty,
                    .id = dir_id,
                    .file = .{ .handle = dir_handle, .flags = .{ .nonblocking = true } },
                    .state = .idle,
                    .iosb = undefined,
                    .buffer = undefined,
                    .ready_node = undefined,
                };
                return dir;
            }

            fn deinit(dir: *Directory, gpa: Allocator, w: *Watch) void {
                state: switch (dir.state) {
                    .idle => {},
                    .listening => {
                        var cancel_iosb: windows.IO_STATUS_BLOCK = undefined;
                        _ = windows.ntdll.NtCancelIoFileEx(dir.file.handle, &dir.iosb, &cancel_iosb);
                        while (switch (dir.state) {
                            .idle => unreachable,
                            .listening => true,
                            .ready => false,
                        }) Io.Threaded.waitForApcOrAlert();
                        continue :state .ready;
                    },
                    .ready => w.os.ready_dirs.remove(&dir.ready_node),
                }
                windows.CloseHandle(dir.file.handle);
                gpa.destroy(dir);
            }

            /// Useful to make `*Directory` a key in `std.ArrayHashMap`.
            const TableAdapter = struct {
                pub fn hash(_: TableAdapter, lhs_dir: *Directory) u32 {
                    return @truncate(Hash.hash(lhs_dir.id.volumeSerialNumber, @ptrCast(&lhs_dir.id.indexNumber)));
                }
                pub fn eql(_: TableAdapter, lhs_dir: *Directory, rhs_dir: *Directory, rhs_index: usize) bool {
                    _ = rhs_index;
                    return lhs_dir.id.volumeSerialNumber == rhs_dir.id.volumeSerialNumber and
                        lhs_dir.id.indexNumber == rhs_dir.id.indexNumber;
                }
            };
        };

        fn init(maker: *Maker) !Watch {
            return .{
                .dir_table = .{},
                .dir_count = 0,
                .os = switch (builtin.os.tag) {
                    .windows => .{
                        .handle_table = .empty,
                        .ready_dirs = .{},
                    },
                    else => {},
                },
                .generation = 0,
                .maker = maker,
            };
        }

        fn deinit(w: *Watch) void {
            const gpa = w.maker.gpa;

            for (w.os.handle_table.keys()) |dir| {
                dir.deinit(gpa, w);
            }
            w.os.handle_table.deinit(gpa);

            w.dir_table.deinit(gpa);
            w.* = undefined;
        }

        fn getFileId(handle: windows.HANDLE) !FileId {
            var file_id: FileId = undefined;
            var io_status: windows.IO_STATUS_BLOCK = undefined;
            var volume_info: windows.FILE.FS_VOLUME_INFORMATION = undefined;
            switch (windows.ntdll.NtQueryVolumeInformationFile(
                handle,
                &io_status,
                &volume_info,
                @sizeOf(windows.FILE.FS_VOLUME_INFORMATION),
                .Volume,
            )) {
                .SUCCESS => {},
                // Buffer overflow here indicates that there is more information available than was able to be stored in the buffer
                // size provided. This is treated as success because the type of variable-length information that this would be relevant for
                // (name, volume name, etc) we don't care about.
                .BUFFER_OVERFLOW => {},
                else => |rc| return windows.unexpectedStatus(rc),
            }
            file_id.volumeSerialNumber = volume_info.VolumeSerialNumber;
            var internal_info: windows.FILE.INTERNAL_INFORMATION = undefined;
            switch (windows.ntdll.NtQueryInformationFile(
                handle,
                &io_status,
                &internal_info,
                @sizeOf(windows.FILE.INTERNAL_INFORMATION),
                .Internal,
            )) {
                .SUCCESS => {},
                else => |rc| return windows.unexpectedStatus(rc),
            }
            file_id.indexNumber = internal_info.IndexNumber;
            return file_id;
        }

        fn markDirtySteps(w: *Watch, dir: *Directory) !bool {
            const maker = w.maker;

            var any_dirty = false;
            const bytes_returned = dir.iosb.Information;
            if (bytes_returned == 0) {
                std.log.warn("file system watch queue overflowed; reconfiguring", .{});
                return error.MustReconfigure;
            }
            var file_name_buf: [std.fs.max_path_bytes]u8 = undefined;
            var offset: usize = 0;
            while (true) {
                const notify: *windows.FILE.NOTIFY.INFORMATION = @ptrCast(@alignCast(&dir.buffer[offset]));
                const file_name = file_name_buf[0..std.unicode.wtf16LeToWtf8(&file_name_buf, notify.fileName())];
                if (dir.reaction_set.getPtr(".")) |glob_set|
                    any_dirty = try markStepSetDirty(maker, glob_set, any_dirty);
                if (dir.reaction_set.getPtr(file_name)) |step_set|
                    any_dirty = try markStepSetDirty(maker, step_set, any_dirty);
                if (notify.NextEntryOffset == 0)
                    break;

                offset += notify.NextEntryOffset;
            }

            // We call this now since at this point we have finished reading dir.buffer.
            try dir.startListening(w);
            return any_dirty;
        }

        fn update(w: *Watch, steps: []const Configuration.Step.Index) !void {
            const maker = w.maker;
            const gpa = maker.gpa;
            // Add missing marks and note persisted ones.
            for (steps) |step_index| {
                const step = maker.stepByIndex(step_index);
                for (step.inputs.table.keys(), step.inputs.table.values()) |path, *files| {
                    const dir = dir: {
                        const gop = try w.dir_table.getOrPut(gpa, path);
                        if (!gop.found_existing) {
                            const dir: *Directory = try .init(gpa, path);
                            errdefer dir.deinit(gpa, w);
                            // `dir.id` may already be present in the table in
                            // the case that we have multiple Cache.Path instances
                            // that compare inequal but ultimately point to the same
                            // directory on the file system.
                            // In such case, we must revert adding this directory, but keep
                            // the additions to the step set.
                            const dh_gop = try w.os.handle_table.getOrPut(gpa, dir);
                            if (dh_gop.found_existing) {
                                dir.deinit(gpa, w);
                                _ = w.dir_table.pop();
                                break :dir w.os.handle_table.keys()[dh_gop.index];
                            } else {
                                assert(dh_gop.index == gop.index);
                                try dir.startListening(w);
                                break :dir dir;
                            }
                        }
                        break :dir w.os.handle_table.keys()[gop.index];
                    };
                    for (files.items) |basename| {
                        const gop = try dir.reaction_set.getOrPut(gpa, basename);
                        if (!gop.found_existing) gop.value_ptr.* = .{};
                        try gop.value_ptr.put(gpa, step_index, w.generation);
                    }
                }
            }

            {
                // Remove marks for files that are no longer inputs.
                var i: usize = 0;
                while (i < w.os.handle_table.entries.len) {
                    const dir = w.os.handle_table.keys()[i];
                    {
                        var step_set_i: usize = 0;
                        while (step_set_i < dir.reaction_set.entries.len) {
                            const step_set = &dir.reaction_set.values()[step_set_i];
                            var dirent_i: usize = 0;
                            while (dirent_i < step_set.entries.len) {
                                const generations = step_set.values();
                                if (generations[dirent_i] == w.generation) {
                                    dirent_i += 1;
                                    continue;
                                }
                                step_set.swapRemoveAt(dirent_i);
                            }
                            if (step_set.entries.len > 0) {
                                step_set_i += 1;
                                continue;
                            }
                            dir.reaction_set.swapRemoveAt(step_set_i);
                        }
                        if (dir.reaction_set.entries.len > 0) {
                            i += 1;
                            continue;
                        }
                    }

                    w.dir_table.swapRemoveAt(i);
                    w.os.handle_table.swapRemoveAt(i);
                    dir.deinit(gpa, w);
                }
                w.generation +%= 1;
            }
            w.dir_count = w.dir_table.count();
        }

        fn wait(w: *Watch, timeout: Timeout) !WaitResult {
            const maker = w.maker;
            const io = maker.graph.io;

            for (0..2) |attempt| {
                while (w.os.ready_dirs.popFirst()) |ready_node| {
                    const dir: *Directory = @fieldParentPtr("ready_node", ready_node);
                    assert(dir.state == .ready);
                    dir.state = .idle;
                    switch (dir.iosb.u.Status) {
                        .SUCCESS => return if (try markDirtySteps(w, dir)) .dirty else .clean,
                        .PENDING => unreachable,
                        .CANCELLED => {},
                        else => |status| return windows.unexpectedStatus(status),
                    }
                    try dir.startListening(w);
                }
                try io.checkCancel();
                if (attempt == 1) return .timeout;
                const delay_interval: windows.LARGE_INTEGER = switch (timeout) {
                    .none => std.math.minInt(windows.LARGE_INTEGER),
                    .ms => |ms| -@as(windows.LARGE_INTEGER, ms) * (std.time.ns_per_ms / 100),
                };
                _ = windows.ntdll.NtDelayExecution(.TRUE, &delay_interval);
            } else unreachable;
        }
    },
    .dragonfly, .freebsd, .netbsd, .openbsd, .ios, .tvos, .visionos, .watchos => struct {
        const posix = std.posix;

        kq_fd: i32,
        /// Indexes correspond 1:1 with `dir_table`.
        handles: std.MultiArrayList(struct {
            rs: ReactionSet,
            /// If the corresponding dir_table Path has sub_path == "", then it
            /// suffices as the open directory handle, and this value will be
            /// -1. Otherwise, it needs to be opened in update(), and will be
            /// stored here.
            dir_fd: i32,
        }),

        const dir_open_flags: posix.O = f: {
            var f: posix.O = .{
                .ACCMODE = .RDONLY,
                .NOFOLLOW = false,
                .DIRECTORY = true,
                .CLOEXEC = true,
            };
            if (@hasField(posix.O, "EVTONLY")) f.EVTONLY = true;
            if (@hasField(posix.O, "PATH")) f.PATH = true;
            break :f f;
        };

        const EV = std.c.EV;
        const NOTE = std.c.NOTE;

        fn init(maker: *Maker) !Watch {
            return .{
                .dir_table = .{},
                .dir_count = 0,
                .os = .{
                    .kq_fd = try Io.Kqueue.createFileDescriptor(),
                    .handles = .empty,
                },
                .generation = 0,
                .maker = maker,
            };
        }

        fn deinit(w: *Watch) void {
            const gpa = w.maker.gpa;

            for (w.os.handles.items(.rs), w.os.handles.items(.dir_fd)) |*rs, dir_fd| {
                rs.deinit(gpa);
                Io.Threaded.closeFd(dir_fd);
            }
            w.os.handles.deinit(gpa);

            Io.Threaded.closeFd(w.os.kq_fd);

            w.dir_table.deinit(gpa);
            w.* = undefined;
        }

        fn update(w: *Watch, steps: []const Configuration.Step.Index) !void {
            const maker = w.maker;
            const gpa = maker.gpa;
            const handles = &w.os.handles;
            for (steps) |step_index| {
                const step = maker.stepByIndex(step_index);
                for (step.inputs.table.keys(), step.inputs.table.values()) |path, *files| {
                    const reaction_set = rs: {
                        const gop = try w.dir_table.getOrPut(gpa, path);
                        if (!gop.found_existing) {
                            const skip_open_dir = path.sub_path.len == 0;
                            const dir_fd = if (skip_open_dir)
                                path.root_dir.handle.handle
                            else
                                posix.openat(path.root_dir.handle.handle, path.sub_path, dir_open_flags, 0) catch |err| {
                                    fatal("failed to open directory {f}: {t}", .{ path, err });
                                };
                            // Empirically the dir has to stay open or else no events are triggered.
                            errdefer if (!skip_open_dir) Io.Threaded.closeFd(dir_fd);
                            const changes = [1]posix.Kevent{.{
                                .ident = @bitCast(@as(isize, dir_fd)),
                                .filter = std.c.EVFILT.VNODE,
                                .flags = EV.ADD | EV.ENABLE | EV.CLEAR,
                                .fflags = NOTE.DELETE | NOTE.WRITE | NOTE.RENAME | NOTE.REVOKE,
                                .data = 0,
                                .udata = gop.index,
                            }};
                            _ = try Io.Kqueue.kevent(w.os.kq_fd, &changes, &.{}, null);
                            assert(handles.len == gop.index);
                            try handles.append(gpa, .{
                                .rs = .{},
                                .dir_fd = if (skip_open_dir) -1 else dir_fd,
                            });
                        }

                        break :rs &handles.items(.rs)[gop.index];
                    };
                    for (files.items) |basename| {
                        const gop = try reaction_set.getOrPut(gpa, basename);
                        if (!gop.found_existing) gop.value_ptr.* = .{};
                        try gop.value_ptr.put(gpa, step_index, w.generation);
                    }
                }
            }

            {
                // Remove marks for files that are no longer inputs.
                var i: usize = 0;
                while (i < handles.len) {
                    {
                        const reaction_set = &handles.items(.rs)[i];
                        var step_set_i: usize = 0;
                        while (step_set_i < reaction_set.entries.len) {
                            const step_set = &reaction_set.values()[step_set_i];
                            var dirent_i: usize = 0;
                            while (dirent_i < step_set.entries.len) {
                                const generations = step_set.values();
                                if (generations[dirent_i] == w.generation) {
                                    dirent_i += 1;
                                    continue;
                                }
                                step_set.swapRemoveAt(dirent_i);
                            }
                            if (step_set.entries.len > 0) {
                                step_set_i += 1;
                                continue;
                            }
                            reaction_set.swapRemoveAt(step_set_i);
                        }
                        if (reaction_set.entries.len > 0) {
                            i += 1;
                            continue;
                        }
                    }

                    // If the sub_path == "" then this patch has already the
                    // dir fd that we need to use as the ident to remove the
                    // event. If it was opened above with openat() then we need
                    // to access that data via the dir_fd field.
                    const path = w.dir_table.keys()[i];
                    const dir_fd = if (path.sub_path.len == 0)
                        path.root_dir.handle.handle
                    else
                        handles.items(.dir_fd)[i];
                    assert(dir_fd != -1);

                    // The changelist also needs to update the udata field of the last
                    // event, since we are doing a swap remove, and we store the dir_table
                    // index in the udata field.
                    const last_dir_fd = fd: {
                        const last_path = w.dir_table.keys()[handles.len - 1];
                        const last_dir_fd = if (last_path.sub_path.len == 0)
                            last_path.root_dir.handle.handle
                        else
                            handles.items(.dir_fd)[handles.len - 1];
                        assert(last_dir_fd != -1);
                        break :fd last_dir_fd;
                    };
                    const changes = [_]posix.Kevent{
                        .{
                            .ident = @bitCast(@as(isize, dir_fd)),
                            .filter = std.c.EVFILT.VNODE,
                            .flags = EV.DELETE,
                            .fflags = 0,
                            .data = 0,
                            .udata = i,
                        },
                        .{
                            .ident = @bitCast(@as(isize, last_dir_fd)),
                            .filter = std.c.EVFILT.VNODE,
                            .flags = EV.ADD,
                            .fflags = NOTE.DELETE | NOTE.WRITE | NOTE.RENAME | NOTE.REVOKE,
                            .data = 0,
                            .udata = i,
                        },
                    };
                    const filtered_changes = if (i == handles.len - 1) changes[0..1] else &changes;
                    _ = try Io.Kqueue.kevent(w.os.kq_fd, filtered_changes, &.{}, null);
                    if (path.sub_path.len != 0) Io.Threaded.closeFd(dir_fd);

                    w.dir_table.swapRemoveAt(i);
                    handles.swapRemove(i);
                }
                w.generation +%= 1;
            }
            w.dir_count = w.dir_table.count();
        }

        fn wait(w: *Watch, timeout: Timeout) !WaitResult {
            const maker = w.maker;
            var timespec_buffer: posix.timespec = undefined;
            var event_buffer: [100]posix.Kevent = undefined;
            var n = try Io.Kqueue.kevent(w.os.kq_fd, &.{}, &event_buffer, timeout.toTimespec(&timespec_buffer));
            if (n == 0) return .timeout;
            const reaction_sets = w.os.handles.items(.rs);
            var any_dirty = try markDirtySteps(maker, reaction_sets, event_buffer[0..n], false);
            timespec_buffer = .{ .sec = 0, .nsec = 0 };
            while (n == event_buffer.len) {
                n = try Io.Kqueue.kevent(w.os.kq_fd, &.{}, &event_buffer, &timespec_buffer);
                if (n == 0) break;
                any_dirty = try markDirtySteps(maker, reaction_sets, event_buffer[0..n], any_dirty);
            }
            return if (any_dirty) .dirty else .clean;
        }

        fn markDirtySteps(
            maker: *Maker,
            reaction_sets: []ReactionSet,
            events: []const std.c.Kevent,
            start_any_dirty: bool,
        ) !bool {
            var any_dirty = start_any_dirty;
            for (events) |event| {
                const index: usize = @intCast(event.udata);
                const reaction_set = &reaction_sets[index];
                // If we knew the basename of the changed file, here we would
                // mark only the step set dirty, and possibly the glob set:
                //if (reaction_set.getPtr(".")) |glob_set|
                //    any_dirty = try markStepSetDirty(maker, glob_set, any_dirty);
                //if (reaction_set.getPtr(file_name)) |step_set|
                //    any_dirty = try markStepSetDirty(maker, step_set, any_dirty);
                // However we don't know the file name so just mark all the
                // sets dirty for this directory.
                for (reaction_set.values()) |*step_set| {
                    any_dirty = try markStepSetDirty(maker, step_set, any_dirty);
                }
            }
            return any_dirty;
        }
    },
    .macos => struct {
        fse: FsEvents,

        fn init(maker: *Maker) !Watch {
            return .{
                .os = .{ .fse = try .init(maker.graph.cache.cwd) },
                .dir_count = 0,
                .dir_table = undefined,
                .generation = undefined,
                .maker = maker,
            };
        }
        fn deinit(w: *Watch) void {
            const gpa = w.maker.gpa;
            const io = w.maker.graph.io;
            w.os.fse.deinit(gpa, io);
            w.* = undefined;
        }
        fn update(w: *Watch, steps: []const Configuration.Step.Index) !void {
            try w.os.fse.setPaths(w.maker, steps);
            w.dir_count = w.os.fse.watch_roots.len;
        }
        fn wait(w: *Watch, timeout: Timeout) !WaitResult {
            return w.os.fse.wait(w.maker, switch (timeout) {
                .none => null,
                .ms => |ms| @as(u64, ms) * std.time.ns_per_ms,
            });
        }
    },
    else => void,
};

pub fn init(maker: *Maker) !Watch {
    return Os.init(maker);
}

pub const Match = struct {
    /// Relative to the watched directory, the file path that triggers this
    /// match.
    basename: []const u8,
    /// The step to re-run when file corresponding to `basename` is changed.
    step_index: Configuration.Step.Index,

    pub const Context = struct {
        pub fn hash(self: Context, a: Match) u32 {
            _ = self;
            var hasher = Hash.init(@backingInt(a.step_index));
            hasher.update(a.basename);
            return @truncate(hasher.final());
        }
        pub fn eql(self: Context, a: Match, b: Match, b_index: usize) bool {
            _ = self;
            _ = b_index;
            return a.step_index == b.step_index and std.mem.eql(u8, a.basename, b.basename);
        }
    };
};

fn markStepSetDirty(maker: *Maker, step_set: *StepSet, any_dirty: bool) error{MustReconfigure}!bool {
    var this_any_dirty = false;
    for (step_set.keys()) |step_index| {
        const step = maker.stepByIndex(step_index);
        if (try maker.invalidateResult(step)) this_any_dirty = true;
    }
    return any_dirty or this_any_dirty;
}

pub fn update(w: *Watch, steps: []const Configuration.Step.Index) !void {
    return Os.update(w, steps);
}

pub const Timeout = union(enum) {
    none,
    ms: u16,

    pub fn to_i32_ms(t: Timeout) i32 {
        return switch (t) {
            .none => -1,
            .ms => |ms| ms,
        };
    }

    pub fn toTimespec(t: Timeout, buf: *std.posix.timespec) ?*std.posix.timespec {
        return switch (t) {
            .none => null,
            .ms => |ms_u16| {
                const ms: isize = ms_u16;
                buf.* = .{
                    .sec = @divTrunc(ms, std.time.ms_per_s),
                    .nsec = @rem(ms, std.time.ms_per_s) * std.time.ns_per_ms,
                };
                return buf;
            },
        };
    }
};

pub const WaitResult = enum {
    timeout,
    /// File system watching triggered on files that were marked as inputs to at least one Step.
    /// Relevant steps have been marked dirty.
    dirty,
    /// File system watching triggered but none of the events were relevant to
    /// what we are listening to. There is nothing to do.
    clean,
};

/// May return `error.MustReconfigure`.
pub fn wait(w: *Watch, timeout: Timeout) !WaitResult {
    return Os.wait(w, timeout);
}

pub fn deinit(w: *Watch) void {
    Os.deinit(w);
}
