tiny.tldr.incremental

1pub const ManifestFieldPatch = struct {2    offset: usize,3    len: usize,4    bytes: [manifest_field_patch_capacity]u8,56    pub fn slice(self: *const ManifestFieldPatch) []const u8 {7        return self.bytes[0..self.len];8    }9};

1pub const ArchiveMemberRecord = extern struct {2    hash: u64 align(1),3    link_hash: u64 align(1) = 0,4    input_index: u64 align(1),5    name_id: u32 align(1),6    selected: bool,7};

1pub const Builder = struct {2    allocator: Allocator,3    target: model.Target,4    output_kind: model.OutputKind,5    entry_symbol_id: u32,6    image_base: u64,7    page_size: u64,8    gc_sections: bool,9    icf: model.IcfMode,10    strip_debug: bool,11    build_id: model.BuildIdMode,12    input_hashes_recorded: bool,13    contribution_records_enabled: bool,14    inputs_read_at_ns: i64,15    strings: Strings = .{},16    inputs: std.ArrayListUnmanaged(InputRecord) = .empty,17    sections: std.ArrayListUnmanaged(SectionRecord) = .empty,18    contributions: std.ArrayListUnmanaged(ContributionRecord) = .empty,19    discarded_contributions: std.ArrayListUnmanaged(DiscardedContributionRecord) = .empty,20    external_targets: std.ArrayListUnmanaged(ExternalTargetRecord) = .empty,21    archive_members: std.ArrayListUnmanaged(ArchiveMemberRecord) = .empty,22    got_entries: std.ArrayListUnmanaged(GotEntryRecord) = .empty,23    merge_pieces: std.ArrayListUnmanaged(MergePieceRecord) = .empty,2425    pub fn init(allocator: Allocator, options: model.LinkOptions) Allocator.Error!Builder {26        const incremental_records_enabled = options.incremental_mode != .off;27        var builder = Builder{28            .allocator = allocator,29            .target = options.target,30            .output_kind = options.output_kind,31            .entry_symbol_id = 0,32            .image_base = options.image_base,33            .page_size = options.page_size,34            .gc_sections = options.gc_sections,35            .icf = options.icf,36            .strip_debug = options.strip_debug,37            .build_id = options.build_id,38            .input_hashes_recorded = incremental_records_enabled,39            .contribution_records_enabled = incremental_records_enabled,40            .inputs_read_at_ns = options.inputs_read_at_ns,41        };42        errdefer builder.deinit();43        builder.entry_symbol_id = try builder.strings.intern(allocator, options.entry_symbol);44        return builder;45    }4647    pub fn recordsContributions(self: Builder) bool {48        return self.contribution_records_enabled;49    }5051    pub fn deinit(self: *Builder) void {52        self.strings.deinit(self.allocator);53        self.inputs.deinit(self.allocator);54        self.sections.deinit(self.allocator);55        self.contributions.deinit(self.allocator);56        self.discarded_contributions.deinit(self.allocator);57        self.external_targets.deinit(self.allocator);58        self.archive_members.deinit(self.allocator);59        self.got_entries.deinit(self.allocator);60        self.merge_pieces.deinit(self.allocator);61        self.* = undefined;62    }6364    pub fn addInput(self: *Builder, input: model.Input) Allocator.Error!void {65        const hash = if (self.input_hashes_recorded) hashBytes(input.bytes) else 0;66        const identity = input.identity orelse model.InputIdentity{ .mtime_ns = 0, .inode = 0 };67        try self.inputs.append(self.allocator, .{68            .name_id = try self.strings.intern(self.allocator, input.name),69            .size = input.bytes.len,70            .hash = hash,71            .mtime_ns = identity.mtime_ns,72            .inode = identity.inode,73            .identity_recorded = input.identity != null,74            .link_hash = hash,75        });76    }7778    pub fn setInputLinkHash(self: *Builder, input_index: usize, link_hash: u64) void {79        if (!self.input_hashes_recorded) return;80        if (input_index >= self.inputs.items.len) return;81        self.inputs.items[input_index].link_hash = link_hash;82    }8384    pub fn setInputSelectionHash(self: *Builder, input_index: usize, selection_hash: u64) void {85        if (!self.input_hashes_recorded) return;86        if (input_index >= self.inputs.items.len) return;87        self.inputs.items[input_index].selection_hash = selection_hash;88    }8990    pub fn addArchiveMember(91        self: *Builder,92        input_index: usize,93        name: []const u8,94        hash: u64,95        link_hash: u64,96        selected: bool,97    ) Allocator.Error!void {98        if (!self.contribution_records_enabled) return;99100        try self.archive_members.append(self.allocator, .{101            .input_index = input_index,102            .name_id = try self.strings.intern(self.allocator, name),103            .hash = hash,104            .link_hash = link_hash,105            .selected = selected,106        });107    }108109    pub fn addSection(110        self: *Builder,111        name: []const u8,112        address: u64,113        file_offset: u64,114        size: u64,115        reserved_size: u64,116        alignment: u64,117    ) Allocator.Error!void {118        try self.sections.append(self.allocator, .{119            .name_id = try self.strings.intern(self.allocator, name),120            .address = address,121            .file_offset = file_offset,122            .size = size,123            .reserved_size = reserved_size,124            .alignment = alignment,125        });126    }127128    pub fn addContribution(129        self: *Builder,130        input_name: []const u8,131        input_index: usize,132        kind: ContributionKind,133        name: []const u8,134        ordinal: u32,135        output_section_name: []const u8,136        address: u64,137        file_offset: u64,138        size: u64,139        reserved_size: u64,140        alignment: u64,141    ) Allocator.Error!void {142        return try self.addContributionWithFileSize(143            input_name,144            input_index,145            kind,146            name,147            ordinal,148            output_section_name,149            address,150            file_offset,151            size,152            size,153            reserved_size,154            alignment,155        );156    }157158    pub fn addContributionWithFileSize(159        self: *Builder,160        input_name: []const u8,161        input_index: usize,162        kind: ContributionKind,163        name: []const u8,164        ordinal: u32,165        output_section_name: []const u8,166        address: u64,167        file_offset: u64,168        size: u64,169        file_size: u64,170        reserved_size: u64,171        alignment: u64,172    ) Allocator.Error!void {173        if (!self.contribution_records_enabled) return;174175        try self.contributions.append(self.allocator, .{176            .input_name_id = try self.strings.intern(self.allocator, input_name),177            .input_index = input_index,178            .kind = kind,179            .name_id = try self.strings.intern(self.allocator, name),180            .ordinal = ordinal,181            .output_section_name_id = try self.strings.intern(self.allocator, output_section_name),182            .address = address,183            .file_offset = file_offset,184            .size = size,185            .file_size = file_size,186            .reserved_size = reserved_size,187            .alignment = alignment,188        });189    }190191    pub fn addDiscardedContribution(192        self: *Builder,193        input_name: []const u8,194        input_index: usize,195        name: []const u8,196        ordinal: u32,197        reason: DiscardReason,198        size: u64,199        alignment: u64,200    ) Allocator.Error!void {201        if (!self.contribution_records_enabled) return;202203        try self.discarded_contributions.append(self.allocator, .{204            .input_name_id = try self.strings.intern(self.allocator, input_name),205            .input_index = input_index,206            .name_id = try self.strings.intern(self.allocator, name),207            .ordinal = ordinal,208            .reason = reason,209            .size = size,210            .alignment = alignment,211        });212    }213214    pub fn addExternalTarget(215        self: *Builder,216        name: []const u8,217        resolved_address: i128,218        size: u64,219    ) Allocator.Error!void {220        if (!self.contribution_records_enabled) return;221222        const name_id = try self.strings.intern(self.allocator, name);223        const record = ExternalTargetRecord.fromResolved(name_id, resolved_address, size) orelse return;224        try self.external_targets.append(self.allocator, record);225    }226227    pub fn addGotEntry(228        self: *Builder,229        input_index: usize,230        input_name: []const u8,231        ordinal: u32,232        name: []const u8,233        address: u64,234    ) Allocator.Error!void {235        if (!self.contribution_records_enabled) return;236237        try self.got_entries.append(self.allocator, .{238            .input_index = input_index,239            .input_name_id = try self.strings.intern(self.allocator, input_name),240            .ordinal = ordinal,241            .name_id = try self.strings.intern(self.allocator, name),242            .address = address,243        });244    }245246    pub fn addMergePiece(247        self: *Builder,248        input_index: usize,249        input_name: []const u8,250        ordinal: u32,251        input_offset: u64,252        size: u64,253        address: u64,254    ) Allocator.Error!void {255        if (!self.contribution_records_enabled) return;256257        try self.merge_pieces.append(self.allocator, .{258            .input_index = input_index,259            .input_name_id = try self.strings.intern(self.allocator, input_name),260            .ordinal = ordinal,261            .input_offset = input_offset,262            .size = size,263            .address = address,264        });265    }266267    pub fn finish(self: *Builder) Allocator.Error!Manifest {268        var strings = self.strings;269        self.strings = .{};270        errdefer strings.deinit(self.allocator);271        strings.ids.deinit(self.allocator);272        strings.ids = .empty;273        return .{274            .target = self.target,275            .output_kind = self.output_kind,276            .entry_symbol_id = self.entry_symbol_id,277            .image_base = self.image_base,278            .page_size = self.page_size,279            .gc_sections = self.gc_sections,280            .icf = self.icf,281            .strip_debug = self.strip_debug,282            .build_id = self.build_id,283            .input_hashes_recorded = self.input_hashes_recorded,284            .inputs_read_at_ns = self.inputs_read_at_ns,285            .strings = strings,286            .inputs = try self.inputs.toOwnedSlice(self.allocator),287            .sections = try self.sections.toOwnedSlice(self.allocator),288            .contributions = try self.contributions.toOwnedSlice(self.allocator),289            .discarded_contributions = try self.discarded_contributions.toOwnedSlice(self.allocator),290            .external_targets = try self.external_targets.toOwnedSlice(self.allocator),291            .archive_members = try self.archive_members.toOwnedSlice(self.allocator),292            .got_entries = try self.got_entries.toOwnedSlice(self.allocator),293            .merge_pieces = try self.merge_pieces.toOwnedSlice(self.allocator),294            .owned = .{295                .inputs = true,296                .sections = true,297                .contributions = true,298                .discarded_contributions = true,299                .external_targets = true,300                .archive_members = true,301                .got_entries = true,302                .merge_pieces = true,303            },304        };305    }306};

1pub const ContributionKind = enum(u8) {2    section,3    common_symbol,4};

1pub const ContributionRecord = extern struct {2    address: u64 align(1),3    file_offset: u64 align(1),4    size: u64 align(1),5    file_size: u64 align(1),6    reserved_size: u64 align(1),7    alignment: u64 align(1),8    input_index: u64 align(1),9    input_name_id: u32 align(1),10    name_id: u32 align(1),11    output_section_name_id: u32 align(1),12    ordinal: u32 align(1),13    kind: ContributionKind,14};

1pub const DiscardReason = enum(u8) {2    discarded,3    identical_code_folded,4};

1pub const DiscardedContributionRecord = extern struct {2    size: u64 align(1),3    alignment: u64 align(1),4    input_index: u64 align(1),5    input_name_id: u32 align(1),6    name_id: u32 align(1),7    ordinal: u32 align(1),8    reason: DiscardReason,9};

1pub const ExternalTargetRecord = extern struct {2    address_bits: u64 align(1),3    size: u64 align(1),4    name_id: u32 align(1),5    address_signed: bool = false,67    pub fn fromResolved(name_id: u32, resolved_address: i128, size: u64) ?ExternalTargetRecord {8        if (resolved_address < 0) {9            const signed = std.math.cast(i64, resolved_address) orelse return null;10            return .{11                .name_id = name_id,12                .address_bits = @bitCast(signed),13                .address_signed = true,14                .size = size,15            };16        }17        return .{18            .name_id = name_id,19            .address_bits = std.math.cast(u64, resolved_address) orelse return null,20            .size = size,21        };22    }2324    pub fn address(self: ExternalTargetRecord) i128 {25        if (self.address_signed) return @as(i64, @bitCast(self.address_bits));26        return self.address_bits;27    }28};

1pub const GotEntryRecord = extern struct {2    address: u64 align(1),3    input_index: u64 align(1),4    input_name_id: u32 align(1),5    name_id: u32 align(1),6    ordinal: u32 align(1),7};

1pub const InputChange = struct {2    kind: InputChangeKind,3    recorded_index: ?usize = null,4    current_index: ?usize = null,5};

1pub const InputChangeKind = enum {2    unchanged,3    changed,4    added,5    removed,6};

1pub const InputChangeStorage = struct {2    phase: alloc_phase.capacity.Phase,3    capacity: Capacity,4    limits: Limits,5    storage: Storage,6    changes: []InputChange,7    matched_current: []bool,8    current_links: []u32,9    current_by_name: []InputChangeNameEntry,1011    pub const storage_alignment: usize = @max(12        @alignOf(InputChange),13        @alignOf(InputChangeNameEntry),14    );15    pub const Storage = []align(storage_alignment) u8;16    pub const Limits: type = InputChangeLimits;17    pub const Capacity: type = InputChangeCapacity;1819    pub const Exhaustion = error{InputCountExceedsCapacity};20    pub const InitError = Capacity.DeriveError || error{StorageTooShort};21    pub const work_limits: alloc_phase.capacity.WorkLimits = .{22        .transition_steps_max = std.math.maxInt(usize),23        .cleanup_steps_per_call_max = 0,24        .cleanup_calls_at_capacity_max = 0,25    };2627    pub const claim: alloc_phase.capacity.Declaration = .{28        .source = .{29            .id = "tldr.input_change_storage",30            .kind = .phase_static,31            .limit_source = .caller,32            .storage = .{33                .covered = &.{34                    .{35                        .id = "classification_scratch_and_retained_name_index",36                        .lifetime = .steady,37                        .detail = "classification scratch and retained name index",38                    },39                },40                .excluded = &.{41                    "borrowed manifest records, strings, and current input bytes",42                    "downstream replacement, candidate-image, and output storage",43                },44            },45            .capacity = .{46                .inputs = &.{47                    alloc_phase.capacity.bindInput(Limits, "current_inputs", "current_inputs"),48                    alloc_phase.capacity.bindInput(Limits, "recorded_inputs", "recorded_inputs"),49                },50                .type_selectors = &.{51                    alloc_phase.capacity.bindType(InputChange, "change"),52                    alloc_phase.capacity.bindType(u32, "u32"),53                    alloc_phase.capacity.bindType(InputChangeNameEntry, "nameslot"),54                },55                .nodes = &.{56                    .{ .input = 0 },57                    .{ .scale = .{ .node = 0, .coefficient = .{ .literal = 2 } } },58                    .{ .next_power_of_two = 1 },59                    .{ .input = 1 },60                    .{ .scale = .{ .node = 3, .coefficient = .{ .size_of_concrete_type = 0 } } },61                    .{ .alignment = .{ .node = 4, .alignment = .{ .literal = 16 } } },62                    .{ .alignment = .{ .node = 3, .alignment = .{ .literal = 16 } } },63                    .{ .scale = .{ .node = 0, .coefficient = .{ .size_of_concrete_type = 1 } } },64                    .{ .alignment = .{ .node = 7, .alignment = .{ .literal = 16 } } },65                    .{ .scale = .{ .node = 2, .coefficient = .{ .size_of_concrete_type = 2 } } },66                    .{ .alignment = .{ .node = 9, .alignment = .{ .literal = 16 } } },67                    .{ .add = .{ .left = 5, .right = 6 } },68                    .{ .add = .{ .left = 11, .right = 8 } },69                    .{ .add = .{ .left = 12, .right = 10 } },70                },71                .assertions = &.{.{72                    .scope = .closure_total,73                    .measure = .retained,74                    .relation = .exact,75                    .expression = 13,76                }},77            },78            .overload = .{79                .kind = .reject_before_mutation,80                .detail = "over-capacity input counts preserve the prior result and workspace",81            },82            .risks = .{83                .transitive = .{84                    .status = .witnessed,85                    .detail = "classification calls only fixed slices, Wyhash, and allocator-free content hashing",86                },87                .foreign = .{88                    .status = .excluded,89                    .detail = "classification has no callback or operating-system boundary",90                },91            },92            .work = .{ .equation = "linear matching scans current inputs; indexed lookup probes at most name_slots" },93            .obligations = &.{94                .{ .key = "tldr_input_change_capacity_capacity_model", .role = .capacity_model },95                .{ .key = "tldr_input_change_capacity_overload", .role = .overload },96                .{ .key = "tldr_input_change_oom_retry", .role = .custom },97                .{ .key = "tldr_input_change_region", .role = .overload },98                .{ .key = "tldr_input_change_sealed_transitive_risk", .role = .transitive_risk },99                .{ .key = "tldr_input_change_sealed_foreign_risk", .role = .foreign_risk },100                .{ .key = "tldr_input_change_max_plus_one", .role = .overload },101                .{ .key = "tldr_input_change_differential", .role = .work_bound },102            },103        },104        .bindings = .{105            .owner = @This(),106            .seal = .{107                .family = alloc_phase.capacity.selector(@This().activate),108                .premise = .{109                    .class = .checked_semantic_fact,110                    .authority = .checker,111                },112            },113            .teardown = .{114                .family = alloc_phase.capacity.selector(@This().deinit),115                .premise = .{116                    .class = .checked_semantic_fact,117                    .authority = .checker,118                },119            },120        },121    };122123    pub fn init(storage: Storage, limits: Limits) InitError!InputChangeStorage {124        const capacity = try Capacity.derive(limits);125        if (storage.len < capacity.storage_bytes) return error.StorageTooShort;126        const owned = storage[0..capacity.storage_bytes];127        return .{128            .phase = .initialization,129            .capacity = capacity,130            .limits = limits,131            .storage = owned,132            .changes = inputChangeSlice(133                InputChange,134                owned,135                capacity.changes_offset,136                capacity.change_records,137            ),138            .matched_current = inputChangeSlice(139                bool,140                owned,141                capacity.matched_offset,142                capacity.matched_flags,143            ),144            .current_links = inputChangeSlice(145                u32,146                owned,147                capacity.links_offset,148                capacity.current_links,149            ),150            .current_by_name = inputChangeSlice(151                InputChangeNameEntry,152                owned,153                capacity.names_offset,154                capacity.name_slots,155            ),156        };157    }158159    pub fn activate(self: *InputChangeStorage) void {160        std.debug.assert(self.phase == .initialization);161        self.assertStorage();162        self.phase = .steady;163    }164165    /// The call matches `current_inputs` with the recorded inputs by name, in166    /// order, and marks each one unchanged, changed, added or removed. A relink167    /// (a later link that compares its inputs with recorded ones) calls this168    /// function first to learn which inputs changed since the manifest (the169    /// record a prepared link keeps beside its output) was written. An input170    /// counts as unchanged when its size matches and either its file identity171    /// matches or its content hash does. A file identity matches when the172    /// manifest recorded one, the current input carries one, the inode and173    /// modification time are equal, and that modification time is earlier than174    /// the time the recorded inputs were read. The returned view stays valid175    /// until the next successful classification or teardown. When either input176    /// count exceeds what the storage was sized for, the call returns177    /// `error.InputCountExceedsCapacity` and leaves the previous view and the178    /// workspace as they were.179    pub fn classify(180        self: *InputChangeStorage,181        recorded: RecordedInputs,182        current_inputs: []const model.Input,183    ) Exhaustion!InputChanges {184        std.debug.assert(self.phase == .steady);185        if (recorded.inputs.len > self.capacity.recorded_inputs or186            current_inputs.len > self.capacity.current_inputs)187        {188            return error.InputCountExceedsCapacity;189        }190        self.assertStorage();191        if (recorded.inputs.len <= linear_input_classification_limit or192            current_inputs.len <= linear_input_classification_limit)193        {194            return self.classifyLinear(recorded, current_inputs);195        }196        return self.classifyIndexed(recorded, current_inputs);197    }198199    pub fn deinit(self: *InputChangeStorage) Storage {200        std.debug.assert(self.phase != .teardown);201        self.assertStorage();202        const storage = self.storage;203        self.phase = .teardown;204        self.storage = &.{};205        self.changes = &.{};206        self.matched_current = &.{};207        self.current_links = &.{};208        self.current_by_name = &.{};209        return storage;210    }211212    fn classifyLinear(213        self: *InputChangeStorage,214        recorded_inputs: RecordedInputs,215        current_inputs: []const model.Input,216    ) InputChanges {217        const matched_current = self.matched_current[0..current_inputs.len];218        @memset(matched_current, false);219        var change_count: usize = 0;220        var summary: InputChangeSummary = .{};221        for (recorded_inputs.inputs, 0..) |recorded, recorded_index| {222            const current_index = findUnmatchedInput(223                current_inputs,224                matched_current,225                recorded_inputs.string(recorded.name_id),226            ) orelse {227                self.append(&change_count, &summary, .{228                    .kind = .removed,229                    .recorded_index = recorded_index,230                });231                continue;232            };233            matched_current[current_index] = true;234            const current = current_inputs[current_index];235            self.append(&change_count, &summary, .{236                .kind = if (inputContentUnchanged(237                    recorded,238                    current,239                    recorded_inputs.inputs_read_at_ns,240                )) .unchanged else .changed,241                .recorded_index = recorded_index,242                .current_index = current_index,243            });244        }245        for (matched_current, 0..) |matched, current_index| {246            if (matched) continue;247            self.append(&change_count, &summary, .{248                .kind = .added,249                .current_index = current_index,250            });251        }252        return .{ .changes = self.changes[0..change_count], .summary = summary };253    }254255    fn classifyIndexed(256        self: *InputChangeStorage,257        recorded_inputs: RecordedInputs,258        current_inputs: []const model.Input,259    ) InputChanges {260        const matched_current = self.matched_current[0..current_inputs.len];261        @memset(matched_current, false);262        const current_links = self.current_links[0..current_inputs.len];263        @memset(current_links, no_input_index);264        @memset(self.current_by_name, .{});265        var current_index = current_inputs.len;266        while (current_index != 0) {267            current_index -= 1;268            self.pushCurrent(current_inputs, current_links, current_index);269        }270271        var change_count: usize = 0;272        var summary: InputChangeSummary = .{};273        for (recorded_inputs.inputs, 0..) |recorded, recorded_index| {274            const matched_index = self.popCurrent(275                current_inputs,276                current_links,277                recorded_inputs.string(recorded.name_id),278            ) orelse {279                self.append(&change_count, &summary, .{280                    .kind = .removed,281                    .recorded_index = recorded_index,282                });283                continue;284            };285            matched_current[matched_index] = true;286            const current = current_inputs[matched_index];287            self.append(&change_count, &summary, .{288                .kind = if (inputContentUnchanged(289                    recorded,290                    current,291                    recorded_inputs.inputs_read_at_ns,292                )) .unchanged else .changed,293                .recorded_index = recorded_index,294                .current_index = matched_index,295            });296        }297        for (matched_current, 0..) |matched, unmatched_index| {298            if (matched) continue;299            self.append(&change_count, &summary, .{300                .kind = .added,301                .current_index = unmatched_index,302            });303        }304        return .{ .changes = self.changes[0..change_count], .summary = summary };305    }306307    fn append(308        self: *InputChangeStorage,309        count: *usize,310        summary: *InputChangeSummary,311        change: InputChange,312    ) void {313        std.debug.assert(count.* < self.changes.len);314        self.changes[count.*] = change;315        count.* += 1;316        switch (change.kind) {317            .unchanged => summary.unchanged += 1,318            .changed => summary.changed += 1,319            .added => summary.added += 1,320            .removed => summary.removed += 1,321        }322    }323324    fn popCurrent(325        self: *InputChangeStorage,326        current_inputs: []const model.Input,327        current_links: []const u32,328        name: []const u8,329    ) ?usize {330        const entry = self.findCurrent(current_inputs, name) orelse return null;331        const input_index = entry.head_index;332        if (input_index == no_input_index) return null;333        const current_index: usize = @intCast(input_index);334        const next_index = current_links[current_index];335        entry.head_index = next_index;336        return current_index;337    }338339    fn pushCurrent(340        self: *InputChangeStorage,341        current_inputs: []const model.Input,342        current_links: []u32,343        input_index: usize,344    ) void {345        const entry = self.findOrCreateCurrent(current_inputs, input_index);346        if (entry.head_index != no_input_index) {347            current_links[input_index] = entry.head_index;348        }349        entry.head_index = @intCast(input_index);350    }351352    fn findOrCreateCurrent(353        self: *InputChangeStorage,354        current_inputs: []const model.Input,355        input_index: usize,356    ) *InputChangeNameEntry {357        std.debug.assert(input_index < current_inputs.len);358        const name = current_inputs[input_index].name;359        const slots = self.current_by_name;360        std.debug.assert(slots.len != 0);361        const mask = slots.len - 1;362        const hash: usize = @truncate(std.hash.Wyhash.hash(0, name));363        var slot_index = hash & mask;364        var probes: usize = 0;365        while (probes < slots.len) : (probes += 1) {366            const entry = &slots[slot_index];367            if (entry.key_index == no_input_index) {368                entry.* = .{ .key_index = @intCast(input_index) };369                return entry;370            }371            const key_index: usize = @intCast(entry.key_index);372            if (std.mem.eql(u8, current_inputs[key_index].name, name)) {373                return entry;374            }375            slot_index = (slot_index + 1) & mask;376        }377        unreachable;378    }379380    fn findCurrent(381        self: *InputChangeStorage,382        current_inputs: []const model.Input,383        name: []const u8,384    ) ?*InputChangeNameEntry {385        const slots = self.current_by_name;386        if (slots.len == 0) return null;387        const mask = slots.len - 1;388        const hash: usize = @truncate(std.hash.Wyhash.hash(0, name));389        var slot_index = hash & mask;390        var probes: usize = 0;391        while (probes < slots.len) : (probes += 1) {392            const entry = &slots[slot_index];393            if (entry.key_index == no_input_index) return null;394            const key_index: usize = @intCast(entry.key_index);395            if (std.mem.eql(u8, current_inputs[key_index].name, name)) {396                return entry;397            }398            slot_index = (slot_index + 1) & mask;399        }400        return null;401    }402403    fn assertStorage(self: *const InputChangeStorage) void {404        const expected = Capacity.derive(self.limits) catch unreachable;405        std.debug.assert(std.meta.eql(expected, self.capacity));406        std.debug.assert(self.storage.len == self.capacity.storage_bytes);407        std.debug.assert(self.changes.len == self.capacity.change_records);408        std.debug.assert(self.matched_current.len == self.capacity.matched_flags);409        std.debug.assert(self.current_links.len == self.capacity.current_links);410        std.debug.assert(self.current_by_name.len == self.capacity.name_slots);411    }412};

1pub const InputChangeSummary = struct {2    unchanged: usize = 0,3    changed: usize = 0,4    added: usize = 0,5    removed: usize = 0,67    pub fn allUnchanged(self: InputChangeSummary) bool {8        return self.changed == 0 and self.added == 0 and self.removed == 0;9    }10};

1pub const InputChanges = struct {2    /// The slice carries one record per recorded or current input, each marked3    /// unchanged, changed, added or removed: the recorded inputs come first in4    /// their recorded order, and the added inputs follow in their current5    /// order. The relink planner reads these records to decide whether the6    /// output can be reused or patched during a relink (a later link that7    /// compares its inputs with recorded ones). This slice lives in the8    /// classification storage and stays valid until that storage completes9    /// another classification or is torn down.10    changes: []const InputChange = &.{},11    summary: InputChangeSummary = .{},1213    pub fn allUnchanged(self: InputChanges) bool {14        return self.summary.allUnchanged();15    }16};

1pub const InputContributionSummary = struct {2    retained: usize = 0,3    discarded: usize = 0,4    retained_size: u64 = 0,5    discarded_size: u64 = 0,67    pub fn isEmpty(self: InputContributionSummary) bool {8        return self.retained == 0 and self.discarded == 0;9    }10};

1pub const InputRecord = extern struct {2    size: u64 align(1),3    hash: u64 align(1),4    mtime_ns: i64 align(1) = 0,5    inode: u64 align(1) = 0,6    identity_recorded: bool = false,7    _pad: [3]u8 = @splat(0),8    name_id: u32 align(1),9    link_hash: u64 align(1),10    selection_hash: u64 align(1) = 0,11};

1pub const Manifest = struct {2    target: model.Target,3    output_kind: model.OutputKind,4    entry_symbol_id: u32 = 0,5    image_base: u64,6    page_size: u64,7    gc_sections: bool,8    icf: model.IcfMode,9    strip_debug: bool,10    build_id: model.BuildIdMode,11    input_hashes_recorded: bool,12    inputs_read_at_ns: i64 = 0,13    strings: Strings = .{},14    inputs: []InputRecord = &.{},15    sections: []SectionRecord = &.{},16    contributions: []ContributionRecord = &.{},17    discarded_contributions: []DiscardedContributionRecord = &.{},18    external_targets: []ExternalTargetRecord = &.{},19    archive_members: []ArchiveMemberRecord = &.{},20    got_entries: []GotEntryRecord = &.{},21    merge_pieces: []MergePieceRecord = &.{},22    owned: RecordOwnership = .{},2324    pub fn empty() Manifest {25        return .{26            .target = .{},27            .output_kind = .executable,28            .image_base = 0,29            .page_size = 0,30            .gc_sections = false,31            .icf = .off,32            .strip_debug = false,33            .build_id = .none,34            .input_hashes_recorded = false,35        };36    }3738    pub fn fromBinary(allocator: Allocator, bytes: []u8) !Manifest {39        return try format.manifestFromBinary(allocator, bytes);40    }4142    pub fn string(self: *const Manifest, id: u32) []const u8 {43        return self.strings.get(id);44    }4546    pub fn entrySymbol(self: *const Manifest) []const u8 {47        if (self.strings.count() == 0) return "";48        return self.strings.get(self.entry_symbol_id);49    }5051    pub fn deinit(self: *Manifest, allocator: Allocator) void {52        if (self.owned.inputs and self.inputs.len != 0) allocator.free(self.inputs);53        if (self.owned.sections and self.sections.len != 0) allocator.free(self.sections);54        if (self.owned.contributions and self.contributions.len != 0) allocator.free(self.contributions);55        if (self.owned.discarded_contributions and self.discarded_contributions.len != 0) allocator.free(self.discarded_contributions);56        if (self.owned.external_targets and self.external_targets.len != 0) allocator.free(self.external_targets);57        if (self.owned.archive_members and self.archive_members.len != 0) allocator.free(self.archive_members);58        if (self.owned.got_entries and self.got_entries.len != 0) allocator.free(self.got_entries);59        if (self.owned.merge_pieces and self.merge_pieces.len != 0) allocator.free(self.merge_pieces);60        self.strings.deinit(allocator);61        self.* = empty();62    }6364    pub fn take(self: *Manifest) Manifest {65        const manifest = self.*;66        self.* = empty();67        return manifest;68    }6970    pub fn canReuseFor(self: Manifest, options: model.LinkOptions, inputs: []const model.Input) bool {71        if (!self.input_hashes_recorded) return false;72        if (!self.canReuseOptions(options)) return false;73        if (self.inputs.len != inputs.len) return false;7475        for (inputs, 0..) |input, index| {76            const record = self.inputs[index];77            if (!std.mem.eql(u8, self.string(record.name_id), input.name)) return false;78            if (!inputContentUnchanged(record, input, self.inputs_read_at_ns)) return false;79        }80        return true;81    }8283    pub fn canReuseOptions(self: Manifest, options: model.LinkOptions) bool {84        if (options.incremental_mode == .off) return false;85        if (self.target.object_format != options.target.object_format) return false;86        if (self.target.architecture != options.target.architecture) return false;87        if (self.target.endianness != options.target.endianness) return false;88        if (self.target.pointer_width_bits != options.target.pointer_width_bits) return false;89        if (self.output_kind != options.output_kind) return false;90        if (self.image_base != options.image_base) return false;91        if (self.page_size != options.page_size) return false;92        if (self.gc_sections != options.gc_sections) return false;93        if (self.icf != options.icf) return false;94        if (self.strip_debug != options.strip_debug) return false;95        if (self.build_id != options.build_id) return false;96        if (!std.mem.eql(u8, self.entrySymbol(), options.entry_symbol)) return false;97        return true;98    }99100    pub fn planContributionReplacement(101        self: Manifest,102        replacements: []const ReplacementContribution,103    ) PatchPlan {104        return patch.planContributionReplacement(self, replacements);105    }106107    pub fn applyContributionReplacement(108        self: Manifest,109        image: []u8,110        replacements: []const ReplacementContribution,111    ) PatchApplyError!PatchApplication {112        return try patch.applyContributionReplacement(self, image, replacements);113    }114115    pub fn formatTextAlloc(self: Manifest, allocator: Allocator) ![]u8 {116        return try format.textAlloc(self, allocator);117    }118119    pub fn scalarPatchesAlloc(120        self: Manifest,121        allocator: Allocator,122        encoded: []const u8,123        input_indexes: []const usize,124        contribution_indexes: []const usize,125        archive_member_indexes: []const usize,126    ) ![]format.ManifestFieldPatch {127        return format.manifestScalarPatchesAlloc(allocator, encoded, self, input_indexes, contribution_indexes, archive_member_indexes);128    }129130    pub fn formatBinaryAlloc(self: Manifest, allocator: Allocator) ![]u8 {131        return try format.binaryAlloc(self, allocator);132    }133134    pub fn writeBinary(self: Manifest, writer: *std.Io.Writer) !void {135        try format.writeBinary(self, writer);136    }137138    pub fn writeText(self: Manifest, writer: *std.Io.Writer) std.Io.Writer.Error!void {139        try format.writeText(self, writer);140    }141};

1pub const MergePieceRecord = extern struct {2    input_offset: u64 align(1),3    size: u64 align(1),4    address: u64 align(1),5    input_index: u64 align(1),6    input_name_id: u32 align(1),7    ordinal: u32 align(1),8};

1pub const PreparedState = struct {2    manifest: Manifest,3    contribution_index: ?ContributionIndex = null,4    input_contributions: []InputContributionSummary = &.{},56    pub const RecordUpdates = struct {7        input_indexes: std.ArrayListUnmanaged(usize) = .empty,8        contribution_indexes: std.ArrayListUnmanaged(usize) = .empty,9        archive_member_indexes: std.ArrayListUnmanaged(usize) = .empty,1011        pub fn deinit(self: *RecordUpdates, allocator: Allocator) void {12            self.input_indexes.deinit(allocator);13            self.contribution_indexes.deinit(allocator);14            self.archive_member_indexes.deinit(allocator);15        }16    };1718    pub fn fromOwnedManifest(allocator: Allocator, manifest: Manifest) Allocator.Error!PreparedState {19        var owned_manifest = manifest;20        errdefer owned_manifest.deinit(allocator);2122        const input_contributions = try buildInputContributionSummaries(allocator, owned_manifest);23        errdefer if (input_contributions.len != 0) allocator.free(input_contributions);2425        return .{26            .manifest = owned_manifest,27            .input_contributions = input_contributions,28        };29    }3031    pub fn ensureReplacementIndex(32        self: *PreparedState,33        allocator: Allocator,34        replacements: []const ReplacementContribution,35    ) IndexError!void {36        if (replacements.len == 0) return;37        if (self.contribution_index) |*index| {38            index.deinit(allocator);39            self.contribution_index = null;40        }41        self.contribution_index = try ContributionIndex.initForReplacements(42            allocator,43            self.manifest,44            replacements,45        );46    }4748    pub fn deinit(self: *PreparedState, allocator: Allocator) void {49        if (self.contribution_index) |*index| index.deinit(allocator);50        if (self.input_contributions.len != 0) allocator.free(self.input_contributions);51        self.manifest.deinit(allocator);52        self.* = undefined;53    }5455    pub fn canReuseFor(self: *const PreparedState, options: model.LinkOptions, inputs: []const model.Input) bool {56        return self.manifest.canReuseFor(options, inputs);57    }5859    pub fn classifyInputs(60        self: *const PreparedState,61        storage: *InputChangeStorage,62        inputs: []const model.Input,63    ) InputChangeStorage.Exhaustion!InputChanges {64        return try storage.classify(RecordedInputs.fromManifest(&self.manifest), inputs);65    }6667    pub fn contributionSummaryForInput(self: *const PreparedState, recorded_index: usize) InputContributionSummary {68        if (recorded_index >= self.input_contributions.len) return .{};69        return self.input_contributions[recorded_index];70    }7172    pub fn contributionSummaryForChange(self: *const PreparedState, change: InputChange) InputContributionSummary {73        const recorded_index = change.recorded_index orelse return .{};74        return self.contributionSummaryForInput(recorded_index);75    }7677    fn relinkPreconditionPlan(self: *const PreparedState, options: model.LinkOptions) ?RelinkPlan {78        if (options.incremental_mode == .off) {79            return .{80                .decision = .full_link,81                .blocker = .incremental_disabled,82            };83        }84        if (!self.manifest.input_hashes_recorded) {85            return .{86                .decision = .full_link,87                .blocker = .input_hashes_unrecorded,88            };89        }90        if (!self.manifest.canReuseOptions(options)) {91            return .{92                .decision = .full_link,93                .blocker = .compatibility_mismatch,94            };95        }96        return null;97    }9899    pub fn planInputRelink(100        self: *const PreparedState,101        storage: *InputChangeStorage,102        options: model.LinkOptions,103        inputs: []const model.Input,104    ) InputChangeStorage.Exhaustion!RelinkPlan {105        if (self.relinkPreconditionPlan(options)) |plan| return plan;106107        const input_changes = try self.classifyInputs(storage, inputs);108        return planRelinkFromInputChangesWithContributions(input_changes, self.input_contributions);109    }110111    pub fn planChangedInputRelink(112        self: *const PreparedState,113        storage: *InputChangeStorage,114        options: model.LinkOptions,115        inputs: []const model.Input,116        replacements: []const ReplacementContribution,117    ) InputChangeStorage.Exhaustion!RelinkPlan {118        if (self.relinkPreconditionPlan(options)) |plan| return plan;119120        const input_changes = try self.classifyInputs(storage, inputs);121        return self.planChangedInputRelinkFromInputChanges(options, input_changes, replacements);122    }123124    pub fn planChangedInputRelinkFromInputChanges(125        self: *const PreparedState,126        options: model.LinkOptions,127        input_changes: InputChanges,128        replacements: []const ReplacementContribution,129    ) RelinkPlan {130        if (self.relinkPreconditionPlan(options)) |plan| return plan;131        return self.planChangedInputRelinkFromChanges(input_changes, replacements);132    }133134    fn planChangedInputRelinkFromChanges(135        self: *const PreparedState,136        input_changes: InputChanges,137        replacements: []const ReplacementContribution,138    ) RelinkPlan {139        if (input_changes.summary.added != 0 or input_changes.summary.removed != 0) {140            for (input_changes.changes, 0..) |change, change_index| switch (change.kind) {141                .unchanged, .changed => {},142                .added => return .{143                    .decision = .full_link,144                    .blocker = .input_added,145                    .blocking_change_index = change_index,146                    .input_summary = input_changes.summary,147                },148                .removed => return .{149                    .decision = .full_link,150                    .blocker = .input_removed,151                    .blocking_change_index = change_index,152                    .input_summary = input_changes.summary,153                    .affected_contributions = self.contributionSummaryForChange(change),154                },155            };156        }157158        if (inputOrderDriftChangeIndex(input_changes)) |change_index| {159            return .{160                .decision = .full_link,161                .blocker = .input_reordered,162                .blocking_change_index = change_index,163                .input_summary = input_changes.summary,164                .affected_contributions = self.contributionSummaryForChange(input_changes.changes[change_index]),165            };166        }167168        if (input_changes.allUnchanged()) {169            if (replacements.len == 0) {170                return .{171                    .decision = .reuse_output,172                    .input_summary = input_changes.summary,173                };174            }175            return self.replacementNotChangedPlan(input_changes, replacements, 0);176        }177178        if (input_changes.changes.len <= replacement_accounting_index_limit) {179            return self.planChangedInputRelinkFromIndexedChanges(input_changes, replacements);180        }181        return self.planChangedInputRelinkFromLinearChanges(input_changes, replacements);182    }183184    fn planChangedInputRelinkFromLinearChanges(185        self: *const PreparedState,186        input_changes: InputChanges,187        replacements: []const ReplacementContribution,188    ) RelinkPlan {189        var affected: InputContributionSummary = .{};190        for (input_changes.changes, 0..) |change, change_index| {191            switch (change.kind) {192                .unchanged => {},193                .added => return .{194                    .decision = .full_link,195                    .blocker = .input_added,196                    .blocking_change_index = change_index,197                    .input_summary = input_changes.summary,198                },199                .removed => return .{200                    .decision = .full_link,201                    .blocker = .input_removed,202                    .blocking_change_index = change_index,203                    .input_summary = input_changes.summary,204                    .affected_contributions = self.contributionSummaryForChange(change),205                },206                .changed => {207                    const contribution_summary = self.contributionSummaryForChange(change);208                    addInputContributionSummary(&affected, contribution_summary);209                    const recorded_index = change.recorded_index orelse {210                        return .{211                            .decision = .full_link,212                            .blocker = .replacement_missing,213                            .blocking_change_index = change_index,214                            .input_summary = input_changes.summary,215                            .affected_contributions = contribution_summary,216                        };217                    };218                    if (countRetainedReplacementsForInput(replacements, recorded_index) != contribution_summary.retained) {219                        return .{220                            .decision = .full_link,221                            .blocker = .replacement_missing,222                            .blocking_change_index = change_index,223                            .input_summary = input_changes.summary,224                            .affected_contributions = contribution_summary,225                        };226                    }227                },228            }229        }230231        if (replacementIndexOutsideChangedInputs(input_changes, replacements)) |replacement_index| {232            return self.replacementNotChangedPlan(input_changes, replacements, replacement_index);233        }234235        return self.planReplacementRelinkFromChanges(input_changes, replacements, affected);236    }237238    fn planChangedInputRelinkFromIndexedChanges(239        self: *const PreparedState,240        input_changes: InputChanges,241        replacements: []const ReplacementContribution,242    ) RelinkPlan {243        var recorded_change_indexes_storage = @as([replacement_accounting_index_limit]?usize, @splat(null));244        var replacement_counts_storage = @as([replacement_accounting_index_limit]usize, @splat(0));245        const recorded_change_indexes = recorded_change_indexes_storage[0..input_changes.changes.len];246        const replacement_counts = replacement_counts_storage[0..input_changes.changes.len];247        @memset(recorded_change_indexes, null);248        @memset(replacement_counts, 0);249250        var affected: InputContributionSummary = .{};251        for (input_changes.changes, 0..) |change, change_index| {252            switch (change.kind) {253                .unchanged => {},254                .added => return .{255                    .decision = .full_link,256                    .blocker = .input_added,257                    .blocking_change_index = change_index,258                    .input_summary = input_changes.summary,259                },260                .removed => return .{261                    .decision = .full_link,262                    .blocker = .input_removed,263                    .blocking_change_index = change_index,264                    .input_summary = input_changes.summary,265                    .affected_contributions = self.contributionSummaryForChange(change),266                },267                .changed => {268                    const contribution_summary = self.contributionSummaryForChange(change);269                    addInputContributionSummary(&affected, contribution_summary);270                    const recorded_index = change.recorded_index orelse {271                        return .{272                            .decision = .full_link,273                            .blocker = .replacement_missing,274                            .blocking_change_index = change_index,275                            .input_summary = input_changes.summary,276                            .affected_contributions = contribution_summary,277                        };278                    };279                    if (recorded_index >= recorded_change_indexes.len) {280                        return .{281                            .decision = .full_link,282                            .blocker = .replacement_missing,283                            .blocking_change_index = change_index,284                            .input_summary = input_changes.summary,285                            .affected_contributions = contribution_summary,286                        };287                    }288                    recorded_change_indexes[recorded_index] = change_index;289                },290            }291        }292293        var first_outside_replacement_index: ?usize = null;294        for (replacements, 0..) |replacement, replacement_index| {295            if (replacement.input_index >= recorded_change_indexes.len) {296                if (first_outside_replacement_index == null) first_outside_replacement_index = replacement_index;297                continue;298            }299            const change_index = recorded_change_indexes[replacement.input_index] orelse {300                if (first_outside_replacement_index == null) first_outside_replacement_index = replacement_index;301                continue;302            };303            if (input_changes.changes[change_index].kind != .changed) {304                if (first_outside_replacement_index == null) first_outside_replacement_index = replacement_index;305                continue;306            }307            replacement_counts[replacement.input_index] += 1;308        }309310        for (input_changes.changes, 0..) |change, change_index| {311            if (change.kind != .changed) continue;312            const recorded_index = change.recorded_index orelse continue;313            const contribution_summary = self.contributionSummaryForChange(change);314            if (recorded_index >= replacement_counts.len or replacement_counts[recorded_index] != contribution_summary.retained) {315                return .{316                    .decision = .full_link,317                    .blocker = .replacement_missing,318                    .blocking_change_index = change_index,319                    .input_summary = input_changes.summary,320                    .affected_contributions = contribution_summary,321                };322            }323        }324325        if (first_outside_replacement_index) |replacement_index| {326            return self.replacementNotChangedPlan(input_changes, replacements, replacement_index);327        }328329        return self.planReplacementRelinkFromChanges(input_changes, replacements, affected);330    }331332    fn replacementNotChangedPlan(333        self: *const PreparedState,334        input_changes: InputChanges,335        replacements: []const ReplacementContribution,336        replacement_index: usize,337    ) RelinkPlan {338        const blocking_change_index = if (replacement_index < replacements.len)339            changeIndexForRecordedInput(input_changes, replacements[replacement_index].input_index)340        else341            null;342        return .{343            .decision = .full_link,344            .blocker = .replacement_not_changed,345            .blocking_change_index = blocking_change_index,346            .blocking_replacement_index = replacement_index,347            .input_summary = input_changes.summary,348            .affected_contributions = if (blocking_change_index) |change_index|349                self.contributionSummaryForChange(input_changes.changes[change_index])350            else351                .{},352        };353    }354355    fn planReplacementRelinkFromChanges(356        self: *const PreparedState,357        input_changes: InputChanges,358        replacements: []const ReplacementContribution,359        affected: InputContributionSummary,360    ) RelinkPlan {361        const patch_plan = self.planContributionReplacement(replacements);362        if (patch_plan.decision == .in_place) {363            return .{364                .decision = .in_place,365                .input_summary = input_changes.summary,366                .affected_contributions = affected,367            };368        }369370        const blocking_replacement_index = patch_plan.blocking_index;371        const blocking_change_index = if (blocking_replacement_index) |replacement_index|372            if (replacement_index < replacements.len)373                changeIndexForRecordedInput(input_changes, replacements[replacement_index].input_index)374            else375                null376        else377            null;378379        return .{380            .decision = .full_link,381            .blocker = relinkBlockerForPatchBlocker(patch_plan.blocker),382            .blocking_change_index = blocking_change_index,383            .blocking_replacement_index = blocking_replacement_index,384            .input_summary = input_changes.summary,385            .affected_contributions = if (blocking_change_index) |change_index|386                self.contributionSummaryForChange(input_changes.changes[change_index])387            else388                affected,389        };390    }391392    pub fn planContributionReplacement(393        self: *const PreparedState,394        replacements: []const ReplacementContribution,395    ) PatchPlan {396        if (self.contribution_index) |index| {397            return index.planContributionReplacement(self.manifest, replacements);398        }399        return patch.planContributionReplacement(self.manifest, replacements);400    }401402    fn contributionIndexForReplacement(403        self: *const PreparedState,404        cursor: *patch.ContributionCursor,405        replacement: ReplacementContribution,406    ) ?usize {407        if (self.contribution_index) |index| return index.contributionIndexForReplacement(replacement);408        const match = cursor.find(self.manifest, replacement) orelse return null;409        return match.index;410    }411412    pub fn applyChangedInputRelink(413        self: *const PreparedState,414        storage: *InputChangeStorage,415        image: []u8,416        options: model.LinkOptions,417        inputs: []const model.Input,418        replacements: []const ReplacementContribution,419    ) RelinkApplyError!RelinkApplication {420        if (self.relinkPreconditionPlan(options)) |plan| return .{ .plan = plan };421422        const input_changes = try self.classifyInputs(storage, inputs);423        return try self.applyChangedInputRelinkFromInputChanges(options, input_changes, image, replacements);424    }425426    pub fn applyChangedInputRelinkFromCandidate(427        self: *const PreparedState,428        allocator: Allocator,429        storage: *InputChangeStorage,430        image: []u8,431        options: model.LinkOptions,432        inputs: []const model.Input,433        candidate_image: []const u8,434        candidate_manifest: Manifest,435    ) CandidateRelinkApplyError!RelinkApplication {436        if (self.relinkPreconditionPlan(options)) |plan| return .{ .plan = plan };437438        const input_changes = try self.classifyInputs(storage, inputs);439440        const replacements = try replacementContributionsFromImage(441            allocator,442            candidate_image,443            candidate_manifest,444            input_changes,445        );446        defer freeReplacementContributions(allocator, replacements);447448        return try self.applyChangedInputRelinkFromChanges(input_changes, image, replacements);449    }450451    pub fn applyChangedInputRelinkFromInputChanges(452        self: *const PreparedState,453        options: model.LinkOptions,454        input_changes: InputChanges,455        image: []u8,456        replacements: []const ReplacementContribution,457    ) PatchApplyError!RelinkApplication {458        if (self.relinkPreconditionPlan(options)) |plan| return .{ .plan = plan };459        return try self.applyChangedInputRelinkFromChanges(input_changes, image, replacements);460    }461462    fn applyChangedInputRelinkFromChanges(463        self: *const PreparedState,464        input_changes: InputChanges,465        image: []u8,466        replacements: []const ReplacementContribution,467    ) PatchApplyError!RelinkApplication {468        const plan = self.planChangedInputRelinkFromChanges(input_changes, replacements);469        return try self.applyAcceptedChangedInputRelink(image, replacements, plan);470    }471472    pub fn acceptedRelinkRecordUpdates(473        self: *const PreparedState,474        allocator: Allocator,475        inputs: []const model.Input,476        input_changes: InputChanges,477        replacements: []const ReplacementContribution,478        member_updates: []const MemberHashUpdate,479    ) !RecordUpdates {480        var updates = RecordUpdates{};481        errdefer updates.deinit(allocator);482        for (input_changes.changes) |change| {483            const recorded_index = change.recorded_index orelse continue;484            const current_index = change.current_index orelse continue;485            if (recorded_index >= self.manifest.inputs.len or current_index >= inputs.len) continue;486            try updates.input_indexes.append(allocator, recorded_index);487        }488        var cursor = patch.ContributionCursor{};489        for (replacements) |replacement| {490            const contribution_index = self.contributionIndexForReplacement(&cursor, replacement) orelse491                return error.ReplacementMissing;492            if (contribution_index >= self.manifest.contributions.len) return error.ReplacementMissing;493            try updates.contribution_indexes.append(allocator, contribution_index);494        }495        for (member_updates) |update| {496            if (update.member_index >= self.manifest.archive_members.len) return error.MemberMissing;497            try updates.archive_member_indexes.append(allocator, update.member_index);498        }499        return updates;500    }501502    pub fn replacementFileRange(503        self: *const PreparedState,504        replacement: ReplacementContribution,505    ) ?patch.FileRange {506        var cursor = patch.ContributionCursor{};507        const contribution_index = self.contributionIndexForReplacement(&cursor, replacement) orelse return null;508        if (contribution_index >= self.manifest.contributions.len) return null;509        return patch.replacementFileRange(self.manifest.contributions[contribution_index], replacement);510    }511512    pub fn applyAcceptedChangedInputRelink(513        self: *const PreparedState,514        image: []u8,515        replacements: []const ReplacementContribution,516        accepted_plan: RelinkPlan,517    ) PatchApplyError!RelinkApplication {518        var application = RelinkApplication{519            .plan = accepted_plan,520        };521        if (accepted_plan.decision != .in_place) return application;522        const patch_application = try self.applyContributionReplacementInPlace(image, replacements);523        if (patch_application.plan.decision == .full_link) {524            application.plan = .{525                .decision = .full_link,526                .blocker = relinkBlockerForPatchBlocker(patch_application.plan.blocker),527                .blocking_replacement_index = patch_application.plan.blocking_index,528                .input_summary = accepted_plan.input_summary,529                .affected_contributions = accepted_plan.affected_contributions,530            };531            return application;532        }533        application.contributions_written = patch_application.contributions_written;534        application.bytes_written = patch_application.bytes_written;535        application.zero_fill_bytes = patch_application.zero_fill_bytes;536        return application;537    }538539    pub fn applyContributionReplacement(540        self: *const PreparedState,541        image: []u8,542        replacements: []const ReplacementContribution,543    ) PatchApplyError!PatchApplication {544        if (self.contribution_index) |index| {545            return try index.applyContributionReplacement(image, self.manifest, replacements);546        }547        return try patch.applyContributionReplacement(self.manifest, image, replacements);548    }549550    fn applyContributionReplacementInPlace(551        self: *const PreparedState,552        image: []u8,553        replacements: []const ReplacementContribution,554    ) PatchApplyError!PatchApplication {555        if (self.contribution_index) |index| {556            return try index.applyContributionReplacementInPlace(image, self.manifest, replacements);557        }558        return try patch.applyContributionReplacementInPlace(self.manifest, image, replacements);559    }560561    pub fn updateManifestForChangedInputRelinkFromInputChanges(562        self: *PreparedState,563        inputs: []const model.Input,564        input_changes: InputChanges,565        replacements: []const ReplacementContribution,566        member_updates: []const MemberHashUpdate,567        inputs_read_at_ns: i64,568    ) RelinkManifestUpdateError!void {569        if (!self.manifest.input_hashes_recorded) return error.RelinkUpdateRequiresInPlacePlan;570571        const plan = self.planChangedInputRelinkFromChanges(input_changes, replacements);572        try self.updateManifestForAcceptedChangedInputRelinkFromInputChanges(573            inputs,574            input_changes,575            replacements,576            member_updates,577            inputs_read_at_ns,578            plan,579        );580    }581582    pub fn updateManifestForAcceptedChangedInputRelinkFromInputChanges(583        self: *PreparedState,584        inputs: []const model.Input,585        input_changes: InputChanges,586        replacements: []const ReplacementContribution,587        member_updates: []const MemberHashUpdate,588        inputs_read_at_ns: i64,589        accepted_plan: RelinkPlan,590    ) RelinkManifestUpdateError!void {591        if (!self.manifest.input_hashes_recorded) return error.RelinkUpdateRequiresInPlacePlan;592        if (accepted_plan.decision != .in_place) return error.RelinkUpdateRequiresInPlacePlan;593594        for (input_changes.changes) |change| {595            const recorded_index = change.recorded_index orelse continue;596            const current_index = change.current_index orelse continue;597            if (recorded_index >= self.manifest.inputs.len or current_index >= inputs.len) continue;598            const input = inputs[current_index];599            const identity = input.identity orelse model.InputIdentity{ .mtime_ns = 0, .inode = 0 };600            self.manifest.inputs[recorded_index].size = input.bytes.len;601            self.manifest.inputs[recorded_index].hash = hashBytes(input.bytes);602            self.manifest.inputs[recorded_index].mtime_ns = identity.mtime_ns;603            self.manifest.inputs[recorded_index].inode = identity.inode;604            self.manifest.inputs[recorded_index].identity_recorded = input.identity != null;605        }606        self.manifest.inputs_read_at_ns = inputs_read_at_ns;607608        var cursor = patch.ContributionCursor{};609        for (replacements) |replacement| {610            const contribution_index = self.contributionIndexForReplacement(&cursor, replacement) orelse611                return error.ReplacementMissing;612            if (contribution_index >= self.manifest.contributions.len) return error.ReplacementMissing;613            const previous_file_size = self.manifest.contributions[contribution_index].file_size;614            self.manifest.contributions[contribution_index].size = replacement.size;615            self.manifest.contributions[contribution_index].file_size = if (previous_file_size == 0 and replacement.payload.len == 0)616                0617            else618                replacement.size;619        }620621        for (member_updates) |update| {622            if (update.member_index >= self.manifest.archive_members.len) return error.MemberMissing;623            self.manifest.archive_members[update.member_index].hash = update.hash;624        }625    }626627    pub fn updateManifestForCandidateRelink(628        self: *PreparedState,629        allocator: Allocator,630        storage: *InputChangeStorage,631        inputs: []const model.Input,632        replacements: []const ReplacementContribution,633        candidate_manifest: Manifest,634    ) RelinkManifestClassifyError!void {635        const input_changes = try self.classifyInputs(storage, inputs);636        try self.updateManifestForCandidateRelinkFromInputChanges(allocator, inputs, input_changes, replacements, candidate_manifest);637    }638639    pub fn updateManifestForCandidateRelinkFromInputChanges(640        self: *PreparedState,641        allocator: Allocator,642        inputs: []const model.Input,643        input_changes: InputChanges,644        replacements: []const ReplacementContribution,645        candidate_manifest: Manifest,646    ) RelinkManifestUpdateError!void {647        const plan = self.planChangedInputRelinkFromChanges(input_changes, replacements);648        try self.updateManifestForAcceptedCandidateRelinkFromInputChanges(649            allocator,650            inputs,651            input_changes,652            replacements,653            candidate_manifest,654            plan,655        );656    }657658    pub fn updateManifestForAcceptedCandidateRelinkFromInputChanges(659        self: *PreparedState,660        allocator: Allocator,661        inputs: []const model.Input,662        input_changes: InputChanges,663        replacements: []const ReplacementContribution,664        candidate_manifest: Manifest,665        accepted_plan: RelinkPlan,666    ) RelinkManifestUpdateError!void {667        try self.validateCandidateSectionLayout(candidate_manifest);668        try self.updateManifestForAcceptedChangedInputRelinkFromInputChanges(669            inputs,670            input_changes,671            replacements,672            &.{},673            candidate_manifest.inputs_read_at_ns,674            accepted_plan,675        );676        for (self.manifest.sections, 0..) |*section, section_index| {677            section.size = candidate_manifest.sections[section_index].size;678        }679        try self.updateInputLinkHashesFromCandidate(input_changes, candidate_manifest);680        try self.replaceDiscardedContributionsFromCandidate(allocator, input_changes, candidate_manifest);681        try self.replaceExternalTargetsFromCandidate(allocator, candidate_manifest);682        try self.replaceArchiveMembersFromCandidate(allocator, input_changes, candidate_manifest);683        try self.replaceGotEntriesFromCandidate(allocator, input_changes, candidate_manifest);684        try self.replaceMergePiecesFromCandidate(allocator, input_changes, candidate_manifest);685        try self.rebuildInputContributionSummaries(allocator);686    }687688    fn updateInputLinkHashesFromCandidate(689        self: *PreparedState,690        input_changes: InputChanges,691        candidate_manifest: Manifest,692    ) RelinkManifestUpdateError!void {693        for (input_changes.changes) |change| {694            const recorded_index = change.recorded_index orelse continue;695            const current_index = change.current_index orelse continue;696            if (recorded_index >= self.manifest.inputs.len or current_index >= candidate_manifest.inputs.len) return error.SectionLayoutChanged;697            self.manifest.inputs[recorded_index].link_hash = candidate_manifest.inputs[current_index].link_hash;698            self.manifest.inputs[recorded_index].selection_hash = candidate_manifest.inputs[current_index].selection_hash;699        }700    }701702    fn validateCandidateSectionLayout(703        self: *const PreparedState,704        candidate_manifest: Manifest,705    ) error{SectionLayoutChanged}!void {706        if (self.manifest.sections.len != candidate_manifest.sections.len) return error.SectionLayoutChanged;707        for (self.manifest.sections, candidate_manifest.sections) |recorded, candidate| {708            if (!std.mem.eql(u8, self.manifest.string(recorded.name_id), candidate_manifest.string(candidate.name_id))) return error.SectionLayoutChanged;709            if (recorded.address != candidate.address) return error.SectionLayoutChanged;710            if (recorded.file_offset != candidate.file_offset) return error.SectionLayoutChanged;711            if (recorded.reserved_size != candidate.reserved_size) return error.SectionLayoutChanged;712            if (recorded.alignment != candidate.alignment) return error.SectionLayoutChanged;713        }714    }715716    fn replaceDiscardedContributionsFromCandidate(717        self: *PreparedState,718        allocator: Allocator,719        input_changes: InputChanges,720        candidate_manifest: Manifest,721    ) RelinkManifestUpdateError!void {722        const discarded_contributions = try cloneCandidateDiscardedContributions(723            allocator,724            &self.manifest.strings,725            input_changes,726            candidate_manifest,727        );728        errdefer if (discarded_contributions.len != 0) allocator.free(discarded_contributions);729730        if (self.manifest.owned.discarded_contributions and self.manifest.discarded_contributions.len != 0) {731            allocator.free(self.manifest.discarded_contributions);732        }733        self.manifest.discarded_contributions = discarded_contributions;734        self.manifest.owned.discarded_contributions = true;735    }736737    fn replaceArchiveMembersFromCandidate(738        self: *PreparedState,739        allocator: Allocator,740        input_changes: InputChanges,741        candidate_manifest: Manifest,742    ) RelinkManifestUpdateError!void {743        const archive_members = try cloneArchiveMemberRecords(allocator, &self.manifest.strings, input_changes, candidate_manifest);744        errdefer if (archive_members.len != 0) allocator.free(archive_members);745746        if (self.manifest.owned.archive_members and self.manifest.archive_members.len != 0) {747            allocator.free(self.manifest.archive_members);748        }749        self.manifest.archive_members = archive_members;750        self.manifest.owned.archive_members = true;751    }752753    fn replaceGotEntriesFromCandidate(754        self: *PreparedState,755        allocator: Allocator,756        input_changes: InputChanges,757        candidate_manifest: Manifest,758    ) RelinkManifestUpdateError!void {759        const got_entries = try cloneGotEntryRecords(allocator, &self.manifest.strings, input_changes, candidate_manifest);760        errdefer if (got_entries.len != 0) allocator.free(got_entries);761762        if (self.manifest.owned.got_entries and self.manifest.got_entries.len != 0) {763            allocator.free(self.manifest.got_entries);764        }765        self.manifest.got_entries = got_entries;766        self.manifest.owned.got_entries = true;767    }768769    fn replaceMergePiecesFromCandidate(770        self: *PreparedState,771        allocator: Allocator,772        input_changes: InputChanges,773        candidate_manifest: Manifest,774    ) RelinkManifestUpdateError!void {775        const merge_pieces = try cloneMergePieceRecords(allocator, &self.manifest.strings, input_changes, candidate_manifest);776        errdefer if (merge_pieces.len != 0) allocator.free(merge_pieces);777778        if (self.manifest.owned.merge_pieces and self.manifest.merge_pieces.len != 0) {779            allocator.free(self.manifest.merge_pieces);780        }781        self.manifest.merge_pieces = merge_pieces;782        self.manifest.owned.merge_pieces = true;783    }784785    fn replaceExternalTargetsFromCandidate(786        self: *PreparedState,787        allocator: Allocator,788        candidate_manifest: Manifest,789    ) Allocator.Error!void {790        const external_targets = try cloneExternalTargetRecords(allocator, &self.manifest.strings, candidate_manifest);791        errdefer if (external_targets.len != 0) allocator.free(external_targets);792793        if (self.manifest.owned.external_targets and self.manifest.external_targets.len != 0) {794            allocator.free(self.manifest.external_targets);795        }796        self.manifest.external_targets = external_targets;797        self.manifest.owned.external_targets = true;798    }799800    fn rebuildInputContributionSummaries(801        self: *PreparedState,802        allocator: Allocator,803    ) Allocator.Error!void {804        const input_contributions = try buildInputContributionSummaries(allocator, self.manifest);805        if (self.input_contributions.len != 0) allocator.free(self.input_contributions);806        self.input_contributions = input_contributions;807    }808};

1pub const RecordOwnership = packed struct {2    inputs: bool = false,3    sections: bool = false,4    contributions: bool = false,5    discarded_contributions: bool = false,6    external_targets: bool = false,7    archive_members: bool = false,8    got_entries: bool = false,9    merge_pieces: bool = false,10};