Wip

pub const Wip = struct {
    gpa: Allocator,
    string_table: StringTable = .empty,
    /// De-duplicates an array inside `extra`.
    dedupe_table: DedupeTable = .empty,
    targets_table: TargetsTable = .empty,

    string_bytes: std.ArrayList(u8) = .empty,
    unlazy_deps: std.ArrayList(String) = .empty,
    system_integrations: std.ArrayList(SystemIntegration) = .empty,
    available_options: std.ArrayList(AvailableOption) = .empty,
    steps: std.ArrayList(Step) = .empty,
    path_deps: std.ArrayList(PathDep) = .empty,
    search_prefixes: std.ArrayList(String) = .empty,
    extra: std.ArrayList(u32) = .empty,
    next_generated_file_index: u32 = 0,
    cache_poison: bool = false,

    const DedupeTable = std.HashMapUnmanaged(ExtraSlice, void, ExtraSlice.Context, std.hash_map.default_max_load_percentage);
    const TargetsTable = std.HashMapUnmanaged(TargetQuery.Index, void, TargetsTableContext, std.hash_map.default_max_load_percentage);

    const ExtraSlice = struct {
        index: u32,
        len: u32,

        const Context = struct {
            extra: []const u32,

            pub fn eql(ctx: @This(), a: ExtraSlice, b: ExtraSlice) bool {
                const slice_a = ctx.extra[a.index..][0..a.len];
                const slice_b = ctx.extra[b.index..][0..b.len];
                return std.mem.eql(u32, slice_a, slice_b);
            }

            pub fn hash(ctx: @This(), key: ExtraSlice) u64 {
                const slice = ctx.extra[key.index..][0..key.len];
                return std.hash_map.hashString(@ptrCast(slice));
            }
        };
    };

    const TargetsTableContext = struct {
        extra: []const u32,

        pub fn eql(ctx: @This(), a: TargetQuery.Index, b: TargetQuery.Index) bool {
            const slice_a = a.extraSlice(ctx.extra);
            const slice_b = b.extraSlice(ctx.extra);
            return std.mem.eql(u32, slice_a, slice_b);
        }

        pub fn hash(ctx: @This(), key: TargetQuery.Index) u64 {
            const slice = key.extraSlice(ctx.extra);
            return std.hash_map.hashString(@ptrCast(slice));
        }
    };

    const StringTable = std.HashMapUnmanaged(String, void, StringTableContext, std.hash_map.default_max_load_percentage);
    const StringTableContext = struct {
        bytes: []const u8,

        pub fn eql(_: @This(), a: String, b: String) bool {
            return a == b;
        }

        pub fn hash(ctx: @This(), key: String) u64 {
            return std.hash_map.hashString(std.mem.sliceTo(ctx.bytes[@backingInt(key)..], 0));
        }
    };

    const StringTableIndexAdapter = struct {
        bytes: []const u8,

        pub fn eql(ctx: @This(), a: []const u8, b: String) bool {
            return std.mem.eql(u8, a, std.mem.sliceTo(ctx.bytes[@backingInt(b)..], 0));
        }

        pub fn hash(_: @This(), adapted_key: []const u8) u64 {
            assert(std.mem.findScalar(u8, adapted_key, 0) == null);
            return std.hash_map.hashString(adapted_key);
        }
    };

    pub fn init(gpa: Allocator) Wip {
        return .{ .gpa = gpa };
    }

    pub fn deinit(wip: *Wip) void {
        const gpa = wip.gpa;
        wip.string_bytes.deinit(gpa);
        wip.unlazy_deps.deinit(gpa);
        wip.system_integrations.deinit(gpa);
        wip.available_options.deinit(gpa);
        wip.steps.deinit(gpa);
        wip.path_deps.deinit(gpa);
        wip.search_prefixes.deinit(gpa);
        wip.extra.deinit(gpa);
        wip.* = undefined;
    }

    pub const Static = struct {
        default_step: Step.Index,
        generated_files_len: u32,
        poisoned: bool,
    };

    pub fn write(wip: *Wip, w: *Io.Writer, static: Static) Io.Writer.Error!void {
        const header: Header = .{
            .string_bytes_len = @intCast(wip.string_bytes.items.len),
            .steps_len = @intCast(wip.steps.items.len),
            .path_deps_len = @intCast(wip.path_deps.items.len),
            .unlazy_deps_len = @intCast(wip.unlazy_deps.items.len),
            .system_integrations_len = @intCast(wip.system_integrations.items.len),
            .available_options_len = @intCast(wip.available_options.items.len),
            .search_prefixes_len = @intCast(wip.search_prefixes.items.len),
            .extra_len = @intCast(wip.extra.items.len),

            .default_step = static.default_step,
            .generated_files_len = static.generated_files_len,
            .flags = .{
                .poisoned = static.poisoned,
            },
        };
        var buffers = [_][]const u8{
            @ptrCast(&header),
            wip.string_bytes.items,
            @ptrCast(wip.steps.items),
            @ptrCast(wip.path_deps.items),
            @ptrCast(wip.unlazy_deps.items),
            @ptrCast(wip.system_integrations.items),
            @ptrCast(wip.available_options.items),
            @ptrCast(wip.search_prefixes.items),
            @ptrCast(wip.extra.items),
        };
        try w.writeVecAll(&buffers);
    }

    pub fn addString(wip: *Wip, bytes: []const u8) Allocator.Error!String {
        const gpa = wip.gpa;
        assert(std.mem.findScalar(u8, bytes, 0) == null);
        const gop = try wip.string_table.getOrPutContextAdapted(
            gpa,
            @as([]const u8, bytes),
            @as(StringTableIndexAdapter, .{ .bytes = wip.string_bytes.items }),
            @as(StringTableContext, .{ .bytes = wip.string_bytes.items }),
        );
        if (gop.found_existing) return gop.key_ptr.*;

        try wip.string_bytes.ensureUnusedCapacity(gpa, bytes.len + 1);
        const new_off: String = @fromBackingInt(@intCast(wip.string_bytes.items.len));

        wip.string_bytes.appendSliceAssumeCapacity(bytes);
        wip.string_bytes.appendAssumeCapacity(0);

        gop.key_ptr.* = new_off;

        return new_off;
    }

    pub fn addOptionalString(wip: *Wip, bytes: ?[]const u8) Allocator.Error!OptionalString {
        return .init(try addString(wip, bytes orelse return .none));
    }

    pub fn addStringList(wip: *Wip, list: []const []const u8) Allocator.Error!StringList {
        // Increase size of extra to support the list. Add the string list
        // there. Then check for duplicate, reverting list if already found.
        const gpa = wip.gpa;
        const revert_index: u32 = @intCast(wip.extra.items.len);
        const added = try wip.extra.addManyAsSlice(gpa, list.len + 1);
        added[0] = @intCast(list.len);
        for (added[1..], list) |*d, s| d.* = @backingInt(try addString(wip, s));
        const gop = try wip.dedupe_table.getOrPutContext(gpa, .{
            .index = revert_index,
            .len = @intCast(added.len),
        }, @as(ExtraSlice.Context, .{ .extra = wip.extra.items }));

        if (gop.found_existing) {
            wip.extra.items.len = revert_index;
            return @fromBackingInt(@intCast(gop.key_ptr.index));
        }

        return @fromBackingInt(@intCast(revert_index));
    }

    pub fn addBytes(wip: *Wip, bytes: []const u8) Allocator.Error!Bytes {
        try wip.string_bytes.appendSlice(wip.gpa, bytes);
        return .{
            .index = @intCast(wip.string_bytes.items.len - bytes.len),
            .len = @intCast(bytes.len),
        };
    }

    pub fn addSemVer(wip: *Wip, sv: std.SemanticVersion) Allocator.Error!String {
        var buffer: [256]u8 = undefined;
        var writer: std.Io.Writer = .fixed(&buffer);
        sv.format(&writer) catch return error.OutOfMemory;
        return addString(wip, writer.buffered());
    }

    pub fn addTargetQuery(wip: *Wip, q: *const std.Target.Query) !TargetQuery.OptionalIndex {
        if (q.isNative()) return .none;
        const gpa = wip.gpa;
        const cpu_name: ?String = switch (q.cpu_model) {
            .native, .baseline, .determined_by_arch_os => null,
            .explicit => |model| try wip.addString(model.name),
        };
        const os_version_min: TargetQuery.OsVersion = if (q.os_version_min) |ver| switch (ver) {
            .none => .none,
            .semver => |sem_ver| .{ .semver = try wip.addSemVer(sem_ver) },
            .windows => |win_ver| .{ .windows = win_ver },
        } else .default;
        const os_version_max: TargetQuery.OsVersion = if (q.os_version_max) |ver| switch (ver) {
            .none => .none,
            .semver => |sem_ver| .{ .semver = try wip.addSemVer(sem_ver) },
            .windows => |win_ver| .{ .windows = win_ver },
        } else .default;
        const glibc_version: ?String = if (q.glibc_version) |sem_ver| try wip.addSemVer(sem_ver) else null;
        const dynamic_linker: ?String = if (q.dynamic_linker) |*dl|
            if (dl.get()) |s| try wip.addString(s) else .empty
        else
            null;
        const cpu_features_add_empty = q.cpu_features_add.isEmpty();
        const cpu_features_sub_empty = q.cpu_features_sub.isEmpty();
        const result_index: TargetQuery.Index = try wip.addExtra(TargetQuery, .{
            .flags = .{
                .cpu_arch = .init(q.cpu_arch),
                .cpu_model = .init(q.cpu_model),
                .cpu_features_add = !cpu_features_add_empty,
                .cpu_features_sub = !cpu_features_sub_empty,
                .os_tag = .init(q.os_tag),
                .abi = .init(q.abi),
                .object_format = .init(q.ofmt),
                .os_version_min = os_version_min,
                .os_version_max = os_version_max,
                .glibc_version = glibc_version != null,
                .android_api_level = q.android_api_level != null,
                .dynamic_linker = dynamic_linker != null,
            },
            .cpu_features_add = .{ .value = if (cpu_features_add_empty) null else q.cpu_features_add },
            .cpu_features_sub = .{ .value = if (cpu_features_sub_empty) null else q.cpu_features_sub },
            .glibc_version = .{ .value = glibc_version },
            .android_api_level = .{ .value = q.android_api_level },
            .dynamic_linker = .{ .value = dynamic_linker },
            .cpu_name = .{ .value = cpu_name },
            .os_version_min = .{ .u = os_version_min },
            .os_version_max = .{ .u = os_version_max },
        });

        // Deduplicate.
        const gop = try wip.targets_table.getOrPutContext(gpa, result_index, @as(TargetsTableContext, .{
            .extra = wip.extra.items,
        }));
        if (gop.found_existing) {
            wip.extra.items.len = @backingInt(result_index);
            return .init(gop.key_ptr.*);
        } else {
            return .init(result_index);
        }
    }

    pub fn addTarget(wip: *Wip, t: std.Target) !TargetQuery.Index {
        const gpa = wip.gpa;
        const cpu_name: String = try wip.addString(t.cpu.model.name);

        const os_version_min: TargetQuery.OsVersion, const os_version_max: TargetQuery.OsVersion, const glibc_version: ?String, const android_api_level: ?u32 = switch (t.os.versionRange()) {
            .none => .{
                .none,
                .none,
                null,
                null,
            },
            .semver => |range| .{
                .{ .semver = try wip.addSemVer(range.min) },
                .{ .semver = try wip.addSemVer(range.max) },
                null,
                null,
            },
            .hurd => |hurd| .{
                .{ .semver = try wip.addSemVer(hurd.range.min) },
                .{ .semver = try wip.addSemVer(hurd.range.max) },
                try wip.addSemVer(hurd.glibc),
                null,
            },
            .linux => |linux| .{
                .{ .semver = try wip.addSemVer(linux.range.min) },
                .{ .semver = try wip.addSemVer(linux.range.max) },
                try wip.addSemVer(linux.glibc),
                linux.android,
            },
            .windows => |range| .{
                .{ .windows = range.min },
                .{ .windows = range.max },
                null,
                null,
            },
        };
        const dynamic_linker: ?String = if (t.dynamic_linker.get()) |dl| try wip.addString(dl) else null;
        const cpu_features_add_empty = t.cpu.features.isEmpty();
        const result_index = try wip.addExtra(TargetQuery, .{
            .flags = .{
                .cpu_arch = .init(t.cpu.arch),
                .cpu_model = .explicit,
                .cpu_features_add = !cpu_features_add_empty,
                .cpu_features_sub = false,
                .os_tag = .init(t.os.tag),
                .abi = .init(t.abi),
                .object_format = .init(t.ofmt),
                .os_version_min = os_version_min,
                .os_version_max = os_version_max,
                .glibc_version = glibc_version != null,
                .android_api_level = android_api_level != null,
                .dynamic_linker = dynamic_linker != null,
            },
            .cpu_features_add = .{ .value = if (cpu_features_add_empty) null else t.cpu.features },
            .cpu_features_sub = .{ .value = null },
            .glibc_version = .{ .value = glibc_version },
            .android_api_level = .{ .value = android_api_level },
            .dynamic_linker = .{ .value = dynamic_linker },
            .cpu_name = .{ .value = cpu_name },
            .os_version_min = .{ .u = os_version_min },
            .os_version_max = .{ .u = os_version_max },
        });

        // Deduplicate.
        const gop = try wip.targets_table.getOrPutContext(gpa, result_index, @as(TargetsTableContext, .{
            .extra = wip.extra.items,
        }));
        if (gop.found_existing) {
            wip.extra.items.len = @backingInt(result_index);
            return gop.key_ptr.*;
        } else {
            return result_index;
        }
    }

    pub fn addExtra(wip: *Wip, comptime T: type, v: T) Allocator.Error!T.Index {
        const extra_len = Storage.extraLen(v);
        try wip.extra.ensureUnusedCapacity(wip.gpa, extra_len);
        return addExtraReserved(wip, T, v);
    }

    pub fn addExtraErased(wip: *Wip, comptime T: type, v: T) Allocator.Error!u32 {
        const extra_len = Storage.extraLen(v);
        try wip.extra.ensureUnusedCapacity(wip.gpa, extra_len);
        return addExtraReservedErased(wip, T, v);
    }

    /// Same as `addExtra` but uses a hash map to possibly return an already
    /// existing index instead of appending to `extra`.
    pub fn addDeduped(wip: *Wip, comptime T: type, v: T) Allocator.Error!T.Index {
        const gpa = wip.gpa;
        const revert_index = wip.extra.items.len;
        const upper_bound_len = Storage.extraLen(v);
        try wip.extra.ensureUnusedCapacity(gpa, upper_bound_len);
        try wip.dedupe_table.ensureUnusedCapacityContext(gpa, 1, @as(ExtraSlice.Context, .{
            .extra = wip.extra.items,
        }));
        const new_index = addExtraReservedErased(wip, T, v);
        const len: u32 = @intCast(wip.extra.items.len - new_index);
        assert(len != 0);
        const gop = wip.dedupe_table.getOrPutAssumeCapacityContext(.{
            .index = new_index,
            .len = len,
        }, @as(ExtraSlice.Context, .{ .extra = wip.extra.items }));

        if (gop.found_existing) {
            wip.extra.items.len = revert_index;
            return @fromBackingInt(@intCast(gop.key_ptr.index));
        }

        return @fromBackingInt(@intCast(new_index));
    }

    pub fn addExtraReserved(wip: *Wip, comptime T: type, v: T) T.Index {
        return @fromBackingInt(@intCast(addExtraReservedErased(wip, T, v)));
    }

    pub fn addExtraReservedErased(wip: *Wip, comptime T: type, v: T) u32 {
        const result: u32 = @intCast(wip.extra.items.len);
        wip.extra.items.len = Storage.setExtra(wip.extra.allocatedSlice(), result, v);
        return result;
    }

    fn addExtraOptionalStringAssumeCapacity(wip: *Wip, optional_string: ?String) void {
        const string = optional_string orelse return;
        wip.extra.appendAssumeCapacity(@backingInt(string));
    }

    pub fn addGeneratedFile(wip: *Wip) GeneratedFileIndex {
        defer wip.next_generated_file_index += 1;
        return @fromBackingInt(@intCast(wip.next_generated_file_index));
    }

    /// Returned slice expires upon next append to the configuration.
    pub fn stringSlice(wip: *const Wip, s: String) [:0]const u8 {
        const start_slice = wip.string_bytes.items[@backingInt(s)..];
        return start_slice[0..std.mem.findScalar(u8, start_slice, 0).? :0];
    }
}