lib/tldr/src/incremental/manifest.zig

daab053ee43316e1809a84551d573ddd1e5bf3d2

   1 const std = @import("std");
   2 const alloc_phase = @import("alloc_phase");
   3 const parent = @import("../root.zig");
   4 const format = @import("format.zig");
   5 const patch = @import("patch.zig");
   6 const model = parent.model;
   7 
   8 const Allocator = std.mem.Allocator;
   9 
  10 pub const StringSpan = extern struct {
  11     offset: u32 align(1),
  12     len: u32 align(1),
  13 };
  14 
  15 pub const Strings = struct {
  16     spans: []const StringSpan = &.{},
  17     blob: []const u8 = &.{},
  18     owned: bool = false,
  19     appendix_spans: std.ArrayListUnmanaged(StringSpan) = .empty,
  20     appendix: std.ArrayListUnmanaged(u8) = .empty,
  21     ids: IdMap = .empty,
  22 
  23     const IdMap: type = std.HashMapUnmanaged(u32, void, IdContext, 80);
  24 
  25     const IdContext = struct {
  26         strings: *const Strings,
  27 
  28         pub fn hash(context: IdContext, id: u32) u64 {
  29             return std.hash.Wyhash.hash(0, context.strings.get(id));
  30         }
  31 
  32         pub fn eql(context: IdContext, a: u32, b: u32) bool {
  33             if (a == b) return true;
  34             return std.mem.eql(u8, context.strings.get(a), context.strings.get(b));
  35         }
  36     };
  37 
  38     const BytesContext = struct {
  39         strings: *const Strings,
  40 
  41         pub fn hash(context: BytesContext, bytes: []const u8) u64 {
  42             _ = context;
  43             return std.hash.Wyhash.hash(0, bytes);
  44         }
  45 
  46         pub fn eql(context: BytesContext, bytes: []const u8, id: u32) bool {
  47             return std.mem.eql(u8, bytes, context.strings.get(id));
  48         }
  49     };
  50 
  51     pub fn deinit(self: *Strings, allocator: Allocator) void {
  52         if (self.owned) {
  53             if (self.spans.len != 0) allocator.free(self.spans);
  54             if (self.blob.len != 0) allocator.free(self.blob);
  55         }
  56         self.appendix_spans.deinit(allocator);
  57         self.appendix.deinit(allocator);
  58         self.ids.deinit(allocator);
  59         self.* = .{};
  60     }
  61 
  62     pub fn count(self: *const Strings) usize {
  63         return self.spans.len + self.appendix_spans.items.len;
  64     }
  65 
  66     pub fn get(self: *const Strings, id: u32) []const u8 {
  67         if (id < self.spans.len) {
  68             const span = self.spans[id];
  69             return self.blob[span.offset..][0..span.len];
  70         }
  71         const span = self.appendix_spans.items[id - self.spans.len];
  72         return self.appendix.items[span.offset..][0..span.len];
  73     }
  74 
  75     pub fn intern(self: *Strings, allocator: Allocator, bytes: []const u8) Allocator.Error!u32 {
  76         if (self.ids.size == 0 and self.count() != 0) try self.rebuildIds(allocator);
  77         const gop = try self.ids.getOrPutContextAdapted(
  78             allocator,
  79             bytes,
  80             BytesContext{ .strings = self },
  81             IdContext{ .strings = self },
  82         );
  83         if (gop.found_existing) return gop.key_ptr.*;
  84         errdefer self.ids.removeByPtr(gop.key_ptr);
  85 
  86         const id = std.math.cast(u32, self.count()) orelse return error.OutOfMemory;
  87         const offset = std.math.cast(u32, self.appendix.items.len) orelse return error.OutOfMemory;
  88         const len = std.math.cast(u32, bytes.len) orelse return error.OutOfMemory;
  89         try self.appendix.appendSlice(allocator, bytes);
  90         errdefer self.appendix.shrinkRetainingCapacity(offset);
  91         try self.appendix_spans.append(allocator, .{ .offset = offset, .len = len });
  92         gop.key_ptr.* = id;
  93         return id;
  94     }
  95 
  96     fn rebuildIds(self: *Strings, allocator: Allocator) Allocator.Error!void {
  97         const total = std.math.cast(u32, self.count()) orelse return error.OutOfMemory;
  98         try self.ids.ensureTotalCapacityContext(allocator, total, IdContext{ .strings = self });
  99         var id: u32 = 0;
 100         while (id < total) : (id += 1) {
 101             const gop = self.ids.getOrPutAssumeCapacityContext(id, IdContext{ .strings = self });
 102             if (!gop.found_existing) gop.key_ptr.* = id;
 103         }
 104     }
 105 };
 106 
 107 pub const InputRecord = extern struct {
 108     size: u64 align(1),
 109     hash: u64 align(1),
 110     mtime_ns: i64 align(1) = 0,
 111     inode: u64 align(1) = 0,
 112     identity_recorded: bool = false,
 113     _pad: [3]u8 = @splat(0),
 114     name_id: u32 align(1),
 115     link_hash: u64 align(1),
 116     selection_hash: u64 align(1) = 0,
 117 };
 118 
 119 pub const SectionRecord = extern struct {
 120     address: u64 align(1),
 121     file_offset: u64 align(1),
 122     size: u64 align(1),
 123     reserved_size: u64 align(1),
 124     alignment: u64 align(1),
 125     name_id: u32 align(1),
 126 };
 127 
 128 pub const ContributionKind = enum(u8) {
 129     section,
 130     common_symbol,
 131 };
 132 
 133 pub const ContributionRecord = extern struct {
 134     address: u64 align(1),
 135     file_offset: u64 align(1),
 136     size: u64 align(1),
 137     file_size: u64 align(1),
 138     reserved_size: u64 align(1),
 139     alignment: u64 align(1),
 140     input_index: u64 align(1),
 141     input_name_id: u32 align(1),
 142     name_id: u32 align(1),
 143     output_section_name_id: u32 align(1),
 144     ordinal: u32 align(1),
 145     kind: ContributionKind,
 146 };
 147 
 148 pub const DiscardReason = enum(u8) {
 149     discarded,
 150     identical_code_folded,
 151 };
 152 
 153 pub const DiscardedContributionRecord = extern struct {
 154     size: u64 align(1),
 155     alignment: u64 align(1),
 156     input_index: u64 align(1),
 157     input_name_id: u32 align(1),
 158     name_id: u32 align(1),
 159     ordinal: u32 align(1),
 160     reason: DiscardReason,
 161 };
 162 
 163 pub const ExternalTargetRecord = extern struct {
 164     address_bits: u64 align(1),
 165     size: u64 align(1),
 166     name_id: u32 align(1),
 167     address_signed: bool = false,
 168 
 169     pub fn fromResolved(name_id: u32, resolved_address: i128, size: u64) ?ExternalTargetRecord {
 170         if (resolved_address < 0) {
 171             const signed = std.math.cast(i64, resolved_address) orelse return null;
 172             return .{
 173                 .name_id = name_id,
 174                 .address_bits = @bitCast(signed),
 175                 .address_signed = true,
 176                 .size = size,
 177             };
 178         }
 179         return .{
 180             .name_id = name_id,
 181             .address_bits = std.math.cast(u64, resolved_address) orelse return null,
 182             .size = size,
 183         };
 184     }
 185 
 186     pub fn address(self: ExternalTargetRecord) i128 {
 187         if (self.address_signed) return @as(i64, @bitCast(self.address_bits));
 188         return self.address_bits;
 189     }
 190 };
 191 
 192 pub const ArchiveMemberRecord = extern struct {
 193     hash: u64 align(1),
 194     link_hash: u64 align(1) = 0,
 195     input_index: u64 align(1),
 196     name_id: u32 align(1),
 197     selected: bool,
 198 };
 199 
 200 pub const GotEntryRecord = extern struct {
 201     address: u64 align(1),
 202     input_index: u64 align(1),
 203     input_name_id: u32 align(1),
 204     name_id: u32 align(1),
 205     ordinal: u32 align(1),
 206 };
 207 
 208 pub const MergePieceRecord = extern struct {
 209     input_offset: u64 align(1),
 210     size: u64 align(1),
 211     address: u64 align(1),
 212     input_index: u64 align(1),
 213     input_name_id: u32 align(1),
 214     ordinal: u32 align(1),
 215 };
 216 
 217 pub const InputChangeKind = enum {
 218     unchanged,
 219     changed,
 220     added,
 221     removed,
 222 };
 223 
 224 pub const InputChange = struct {
 225     kind: InputChangeKind,
 226     recorded_index: ?usize = null,
 227     current_index: ?usize = null,
 228 };
 229 
 230 pub const InputChangeSummary = struct {
 231     unchanged: usize = 0,
 232     changed: usize = 0,
 233     added: usize = 0,
 234     removed: usize = 0,
 235 
 236     pub fn allUnchanged(self: InputChangeSummary) bool {
 237         return self.changed == 0 and self.added == 0 and self.removed == 0;
 238     }
 239 };
 240 
 241 pub const InputContributionSummary = struct {
 242     retained: usize = 0,
 243     discarded: usize = 0,
 244     retained_size: u64 = 0,
 245     discarded_size: u64 = 0,
 246 
 247     pub fn isEmpty(self: InputContributionSummary) bool {
 248         return self.retained == 0 and self.discarded == 0;
 249     }
 250 };
 251 
 252 pub const InputChanges = struct {
 253     /// The slice carries one record per recorded or current input, each marked
 254     /// unchanged, changed, added or removed: the recorded inputs come first in
 255     /// their recorded order, and the added inputs follow in their current
 256     /// order. The relink planner reads these records to decide whether the
 257     /// output can be reused or patched during a relink (a later link that
 258     /// compares its inputs with recorded ones). This slice lives in the
 259     /// classification storage and stays valid until that storage completes
 260     /// another classification or is torn down.
 261     changes: []const InputChange = &.{},
 262     summary: InputChangeSummary = .{},
 263 
 264     pub fn allUnchanged(self: InputChanges) bool {
 265         return self.summary.allUnchanged();
 266     }
 267 };
 268 
 269 /// This struct borrows the parts of a manifest (the record a prepared link
 270 /// keeps beside its output) that input classification (matching current inputs
 271 /// to recorded ones by name) reads: the input records, the time the inputs were
 272 /// read, and the string tables that hold input names. Callers build one with
 273 /// `fromManifest` and pass it to `classify`. Classification through this struct
 274 /// allocates nothing. The struct points into the arrays of the manifest, so the
 275 /// instance stays valid only while that manifest is alive and gains no new
 276 /// strings.
 277 pub const RecordedInputs = struct {
 278     inputs: []const InputRecord,
 279     inputs_read_at_ns: i64,
 280     spans: []const StringSpan,
 281     blob: []const u8,
 282     appendix_spans: []const StringSpan,
 283     appendix: []const u8,
 284 
 285     pub fn fromManifest(manifest: *const Manifest) RecordedInputs {
 286         return .{
 287             .inputs = manifest.inputs,
 288             .inputs_read_at_ns = manifest.inputs_read_at_ns,
 289             .spans = manifest.strings.spans,
 290             .blob = manifest.strings.blob,
 291             .appendix_spans = manifest.strings.appendix_spans.items,
 292             .appendix = manifest.strings.appendix.items,
 293         };
 294     }
 295 
 296     pub fn string(self: RecordedInputs, id: u32) []const u8 {
 297         const string_count = std.math.add(
 298             usize,
 299             self.spans.len,
 300             self.appendix_spans.len,
 301         ) catch unreachable;
 302         std.debug.assert(id < string_count);
 303         if (id < self.spans.len) {
 304             const span = self.spans[id];
 305             return self.blob[span.offset..][0..span.len];
 306         }
 307         const span = self.appendix_spans[id - self.spans.len];
 308         return self.appendix[span.offset..][0..span.len];
 309     }
 310 };
 311 
 312 const InputChangeLimits = struct {
 313     recorded_inputs: usize,
 314     current_inputs: usize,
 315 
 316     pub fn inspect(recorded: RecordedInputs, current_inputs: []const model.Input) InputChangeLimits {
 317         return .{
 318             .recorded_inputs = recorded.inputs.len,
 319             .current_inputs = current_inputs.len,
 320         };
 321     }
 322 };
 323 
 324 const InputChangeNameEntry = struct {
 325     key_index: u32 = no_input_index,
 326     head_index: u32 = no_input_index,
 327 };
 328 
 329 const InputChangeCapacity = struct {
 330     recorded_inputs: usize,
 331     current_inputs: usize,
 332     change_records: usize,
 333     matched_flags: usize,
 334     current_links: usize,
 335     name_slots: usize,
 336     changes_offset: usize,
 337     matched_offset: usize,
 338     links_offset: usize,
 339     names_offset: usize,
 340     storage_bytes: usize,
 341 
 342     pub const DeriveError = error{CapacityOverflow};
 343 
 344     pub fn derive(limits: InputChangeLimits) DeriveError!InputChangeCapacity {
 345         _ = std.math.cast(u32, limits.current_inputs) orelse
 346             return error.CapacityOverflow;
 347         const change_records = std.math.add(
 348             usize,
 349             limits.recorded_inputs,
 350             limits.current_inputs,
 351         ) catch return error.CapacityOverflow;
 352         const name_slots = try inputChangeNameSlots(limits.current_inputs);
 353         const changes = try placeInputChangeRegion(InputChange, 0, change_records);
 354         const matched = try placeInputChangeRegion(bool, changes.end, limits.current_inputs);
 355         const links = try placeInputChangeRegion(u32, matched.end, limits.current_inputs);
 356         const names = try placeInputChangeRegion(InputChangeNameEntry, links.end, name_slots);
 357         return .{
 358             .recorded_inputs = limits.recorded_inputs,
 359             .current_inputs = limits.current_inputs,
 360             .change_records = change_records,
 361             .matched_flags = limits.current_inputs,
 362             .current_links = limits.current_inputs,
 363             .name_slots = name_slots,
 364             .changes_offset = changes.start,
 365             .matched_offset = matched.start,
 366             .links_offset = links.start,
 367             .names_offset = names.start,
 368             .storage_bytes = names.end,
 369         };
 370     }
 371 };
 372 
 373 const InputChangeRegion = struct {
 374     start: usize,
 375     end: usize,
 376 };
 377 
 378 fn placeInputChangeRegion(
 379     comptime T: type,
 380     offset: usize,
 381     count: usize,
 382 ) InputChangeCapacity.DeriveError!InputChangeRegion {
 383     const mask: usize = @alignOf(T) - 1;
 384     const padded = std.math.add(usize, offset, mask) catch return error.CapacityOverflow;
 385     const start = padded & ~mask;
 386     const bytes = std.math.mul(usize, count, @sizeOf(T)) catch
 387         return error.CapacityOverflow;
 388     return .{
 389         .start = start,
 390         .end = std.math.add(usize, start, bytes) catch return error.CapacityOverflow,
 391     };
 392 }
 393 
 394 fn inputChangeNameSlots(current_inputs: usize) InputChangeCapacity.DeriveError!usize {
 395     if (current_inputs == 0) return 0;
 396     const doubled = std.math.mul(usize, current_inputs, 2) catch
 397         return error.CapacityOverflow;
 398     return std.math.ceilPowerOfTwo(usize, doubled) catch error.CapacityOverflow;
 399 }
 400 
 401 pub const InputChangeStorage = struct {
 402     phase: alloc_phase.capacity.Phase,
 403     capacity: Capacity,
 404     limits: Limits,
 405     storage: Storage,
 406     changes: []InputChange,
 407     matched_current: []bool,
 408     current_links: []u32,
 409     current_by_name: []InputChangeNameEntry,
 410 
 411     pub const storage_alignment: usize = @max(
 412         @alignOf(InputChange),
 413         @alignOf(InputChangeNameEntry),
 414     );
 415     pub const Storage = []align(storage_alignment) u8;
 416     pub const Limits: type = InputChangeLimits;
 417     pub const Capacity: type = InputChangeCapacity;
 418 
 419     pub const Exhaustion = error{InputCountExceedsCapacity};
 420     pub const InitError = Capacity.DeriveError || error{StorageTooShort};
 421     pub const work_limits: alloc_phase.capacity.WorkLimits = .{
 422         .transition_steps_max = std.math.maxInt(usize),
 423         .cleanup_steps_per_call_max = 0,
 424         .cleanup_calls_at_capacity_max = 0,
 425     };
 426 
 427     pub const claim: alloc_phase.capacity.Declaration = .{
 428         .source = .{
 429             .id = "tldr.input_change_storage",
 430             .kind = .phase_static,
 431             .limit_source = .caller,
 432             .storage = .{
 433                 .covered = &.{
 434                     .{
 435                         .id = "classification_scratch_and_retained_name_index",
 436                         .lifetime = .steady,
 437                         .detail = "classification scratch and retained name index",
 438                     },
 439                 },
 440                 .excluded = &.{
 441                     "borrowed manifest records, strings, and current input bytes",
 442                     "downstream replacement, candidate-image, and output storage",
 443                 },
 444             },
 445             .capacity = .{
 446                 .inputs = &.{
 447                     alloc_phase.capacity.bindInput(Limits, "current_inputs", "current_inputs"),
 448                     alloc_phase.capacity.bindInput(Limits, "recorded_inputs", "recorded_inputs"),
 449                 },
 450                 .type_selectors = &.{
 451                     alloc_phase.capacity.bindType(InputChange, "change"),
 452                     alloc_phase.capacity.bindType(u32, "u32"),
 453                     alloc_phase.capacity.bindType(InputChangeNameEntry, "nameslot"),
 454                 },
 455                 .nodes = &.{
 456                     .{ .input = 0 },
 457                     .{ .scale = .{ .node = 0, .coefficient = .{ .literal = 2 } } },
 458                     .{ .next_power_of_two = 1 },
 459                     .{ .input = 1 },
 460                     .{ .scale = .{ .node = 3, .coefficient = .{ .size_of_concrete_type = 0 } } },
 461                     .{ .alignment = .{ .node = 4, .alignment = .{ .literal = 16 } } },
 462                     .{ .alignment = .{ .node = 3, .alignment = .{ .literal = 16 } } },
 463                     .{ .scale = .{ .node = 0, .coefficient = .{ .size_of_concrete_type = 1 } } },
 464                     .{ .alignment = .{ .node = 7, .alignment = .{ .literal = 16 } } },
 465                     .{ .scale = .{ .node = 2, .coefficient = .{ .size_of_concrete_type = 2 } } },
 466                     .{ .alignment = .{ .node = 9, .alignment = .{ .literal = 16 } } },
 467                     .{ .add = .{ .left = 5, .right = 6 } },
 468                     .{ .add = .{ .left = 11, .right = 8 } },
 469                     .{ .add = .{ .left = 12, .right = 10 } },
 470                 },
 471                 .assertions = &.{.{
 472                     .scope = .closure_total,
 473                     .measure = .retained,
 474                     .relation = .exact,
 475                     .expression = 13,
 476                 }},
 477             },
 478             .overload = .{
 479                 .kind = .reject_before_mutation,
 480                 .detail = "over-capacity input counts preserve the prior result and workspace",
 481             },
 482             .risks = .{
 483                 .transitive = .{
 484                     .status = .witnessed,
 485                     .detail = "classification calls only fixed slices, Wyhash, and allocator-free content hashing",
 486                 },
 487                 .foreign = .{
 488                     .status = .excluded,
 489                     .detail = "classification has no callback or operating-system boundary",
 490                 },
 491             },
 492             .work = .{ .equation = "linear matching scans current inputs; indexed lookup probes at most name_slots" },
 493             .obligations = &.{
 494                 .{ .key = "tldr_input_change_capacity_capacity_model", .role = .capacity_model },
 495                 .{ .key = "tldr_input_change_capacity_overload", .role = .overload },
 496                 .{ .key = "tldr_input_change_oom_retry", .role = .custom },
 497                 .{ .key = "tldr_input_change_region", .role = .overload },
 498                 .{ .key = "tldr_input_change_sealed_transitive_risk", .role = .transitive_risk },
 499                 .{ .key = "tldr_input_change_sealed_foreign_risk", .role = .foreign_risk },
 500                 .{ .key = "tldr_input_change_max_plus_one", .role = .overload },
 501                 .{ .key = "tldr_input_change_differential", .role = .work_bound },
 502             },
 503         },
 504         .bindings = .{
 505             .owner = @This(),
 506             .seal = .{
 507                 .family = alloc_phase.capacity.selector(@This().activate),
 508                 .premise = .{
 509                     .class = .checked_semantic_fact,
 510                     .authority = .checker,
 511                 },
 512             },
 513             .teardown = .{
 514                 .family = alloc_phase.capacity.selector(@This().deinit),
 515                 .premise = .{
 516                     .class = .checked_semantic_fact,
 517                     .authority = .checker,
 518                 },
 519             },
 520         },
 521     };
 522 
 523     pub fn init(storage: Storage, limits: Limits) InitError!InputChangeStorage {
 524         const capacity = try Capacity.derive(limits);
 525         if (storage.len < capacity.storage_bytes) return error.StorageTooShort;
 526         const owned = storage[0..capacity.storage_bytes];
 527         return .{
 528             .phase = .initialization,
 529             .capacity = capacity,
 530             .limits = limits,
 531             .storage = owned,
 532             .changes = inputChangeSlice(
 533                 InputChange,
 534                 owned,
 535                 capacity.changes_offset,
 536                 capacity.change_records,
 537             ),
 538             .matched_current = inputChangeSlice(
 539                 bool,
 540                 owned,
 541                 capacity.matched_offset,
 542                 capacity.matched_flags,
 543             ),
 544             .current_links = inputChangeSlice(
 545                 u32,
 546                 owned,
 547                 capacity.links_offset,
 548                 capacity.current_links,
 549             ),
 550             .current_by_name = inputChangeSlice(
 551                 InputChangeNameEntry,
 552                 owned,
 553                 capacity.names_offset,
 554                 capacity.name_slots,
 555             ),
 556         };
 557     }
 558 
 559     pub fn activate(self: *InputChangeStorage) void {
 560         std.debug.assert(self.phase == .initialization);
 561         self.assertStorage();
 562         self.phase = .steady;
 563     }
 564 
 565     /// The call matches `current_inputs` with the recorded inputs by name, in
 566     /// order, and marks each one unchanged, changed, added or removed. A relink
 567     /// (a later link that compares its inputs with recorded ones) calls this
 568     /// function first to learn which inputs changed since the manifest (the
 569     /// record a prepared link keeps beside its output) was written. An input
 570     /// counts as unchanged when its size matches and either its file identity
 571     /// matches or its content hash does. A file identity matches when the
 572     /// manifest recorded one, the current input carries one, the inode and
 573     /// modification time are equal, and that modification time is earlier than
 574     /// the time the recorded inputs were read. The returned view stays valid
 575     /// until the next successful classification or teardown. When either input
 576     /// count exceeds what the storage was sized for, the call returns
 577     /// `error.InputCountExceedsCapacity` and leaves the previous view and the
 578     /// workspace as they were.
 579     pub fn classify(
 580         self: *InputChangeStorage,
 581         recorded: RecordedInputs,
 582         current_inputs: []const model.Input,
 583     ) Exhaustion!InputChanges {
 584         std.debug.assert(self.phase == .steady);
 585         if (recorded.inputs.len > self.capacity.recorded_inputs or
 586             current_inputs.len > self.capacity.current_inputs)
 587         {
 588             return error.InputCountExceedsCapacity;
 589         }
 590         self.assertStorage();
 591         if (recorded.inputs.len <= linear_input_classification_limit or
 592             current_inputs.len <= linear_input_classification_limit)
 593         {
 594             return self.classifyLinear(recorded, current_inputs);
 595         }
 596         return self.classifyIndexed(recorded, current_inputs);
 597     }
 598 
 599     pub fn deinit(self: *InputChangeStorage) Storage {
 600         std.debug.assert(self.phase != .teardown);
 601         self.assertStorage();
 602         const storage = self.storage;
 603         self.phase = .teardown;
 604         self.storage = &.{};
 605         self.changes = &.{};
 606         self.matched_current = &.{};
 607         self.current_links = &.{};
 608         self.current_by_name = &.{};
 609         return storage;
 610     }
 611 
 612     fn classifyLinear(
 613         self: *InputChangeStorage,
 614         recorded_inputs: RecordedInputs,
 615         current_inputs: []const model.Input,
 616     ) InputChanges {
 617         const matched_current = self.matched_current[0..current_inputs.len];
 618         @memset(matched_current, false);
 619         var change_count: usize = 0;
 620         var summary: InputChangeSummary = .{};
 621         for (recorded_inputs.inputs, 0..) |recorded, recorded_index| {
 622             const current_index = findUnmatchedInput(
 623                 current_inputs,
 624                 matched_current,
 625                 recorded_inputs.string(recorded.name_id),
 626             ) orelse {
 627                 self.append(&change_count, &summary, .{
 628                     .kind = .removed,
 629                     .recorded_index = recorded_index,
 630                 });
 631                 continue;
 632             };
 633             matched_current[current_index] = true;
 634             const current = current_inputs[current_index];
 635             self.append(&change_count, &summary, .{
 636                 .kind = if (inputContentUnchanged(
 637                     recorded,
 638                     current,
 639                     recorded_inputs.inputs_read_at_ns,
 640                 )) .unchanged else .changed,
 641                 .recorded_index = recorded_index,
 642                 .current_index = current_index,
 643             });
 644         }
 645         for (matched_current, 0..) |matched, current_index| {
 646             if (matched) continue;
 647             self.append(&change_count, &summary, .{
 648                 .kind = .added,
 649                 .current_index = current_index,
 650             });
 651         }
 652         return .{ .changes = self.changes[0..change_count], .summary = summary };
 653     }
 654 
 655     fn classifyIndexed(
 656         self: *InputChangeStorage,
 657         recorded_inputs: RecordedInputs,
 658         current_inputs: []const model.Input,
 659     ) InputChanges {
 660         const matched_current = self.matched_current[0..current_inputs.len];
 661         @memset(matched_current, false);
 662         const current_links = self.current_links[0..current_inputs.len];
 663         @memset(current_links, no_input_index);
 664         @memset(self.current_by_name, .{});
 665         var current_index = current_inputs.len;
 666         while (current_index != 0) {
 667             current_index -= 1;
 668             self.pushCurrent(current_inputs, current_links, current_index);
 669         }
 670 
 671         var change_count: usize = 0;
 672         var summary: InputChangeSummary = .{};
 673         for (recorded_inputs.inputs, 0..) |recorded, recorded_index| {
 674             const matched_index = self.popCurrent(
 675                 current_inputs,
 676                 current_links,
 677                 recorded_inputs.string(recorded.name_id),
 678             ) orelse {
 679                 self.append(&change_count, &summary, .{
 680                     .kind = .removed,
 681                     .recorded_index = recorded_index,
 682                 });
 683                 continue;
 684             };
 685             matched_current[matched_index] = true;
 686             const current = current_inputs[matched_index];
 687             self.append(&change_count, &summary, .{
 688                 .kind = if (inputContentUnchanged(
 689                     recorded,
 690                     current,
 691                     recorded_inputs.inputs_read_at_ns,
 692                 )) .unchanged else .changed,
 693                 .recorded_index = recorded_index,
 694                 .current_index = matched_index,
 695             });
 696         }
 697         for (matched_current, 0..) |matched, unmatched_index| {
 698             if (matched) continue;
 699             self.append(&change_count, &summary, .{
 700                 .kind = .added,
 701                 .current_index = unmatched_index,
 702             });
 703         }
 704         return .{ .changes = self.changes[0..change_count], .summary = summary };
 705     }
 706 
 707     fn append(
 708         self: *InputChangeStorage,
 709         count: *usize,
 710         summary: *InputChangeSummary,
 711         change: InputChange,
 712     ) void {
 713         std.debug.assert(count.* < self.changes.len);
 714         self.changes[count.*] = change;
 715         count.* += 1;
 716         switch (change.kind) {
 717             .unchanged => summary.unchanged += 1,
 718             .changed => summary.changed += 1,
 719             .added => summary.added += 1,
 720             .removed => summary.removed += 1,
 721         }
 722     }
 723 
 724     fn popCurrent(
 725         self: *InputChangeStorage,
 726         current_inputs: []const model.Input,
 727         current_links: []const u32,
 728         name: []const u8,
 729     ) ?usize {
 730         const entry = self.findCurrent(current_inputs, name) orelse return null;
 731         const input_index = entry.head_index;
 732         if (input_index == no_input_index) return null;
 733         const current_index: usize = @intCast(input_index);
 734         const next_index = current_links[current_index];
 735         entry.head_index = next_index;
 736         return current_index;
 737     }
 738 
 739     fn pushCurrent(
 740         self: *InputChangeStorage,
 741         current_inputs: []const model.Input,
 742         current_links: []u32,
 743         input_index: usize,
 744     ) void {
 745         const entry = self.findOrCreateCurrent(current_inputs, input_index);
 746         if (entry.head_index != no_input_index) {
 747             current_links[input_index] = entry.head_index;
 748         }
 749         entry.head_index = @intCast(input_index);
 750     }
 751 
 752     fn findOrCreateCurrent(
 753         self: *InputChangeStorage,
 754         current_inputs: []const model.Input,
 755         input_index: usize,
 756     ) *InputChangeNameEntry {
 757         std.debug.assert(input_index < current_inputs.len);
 758         const name = current_inputs[input_index].name;
 759         const slots = self.current_by_name;
 760         std.debug.assert(slots.len != 0);
 761         const mask = slots.len - 1;
 762         const hash: usize = @truncate(std.hash.Wyhash.hash(0, name));
 763         var slot_index = hash & mask;
 764         var probes: usize = 0;
 765         while (probes < slots.len) : (probes += 1) {
 766             const entry = &slots[slot_index];
 767             if (entry.key_index == no_input_index) {
 768                 entry.* = .{ .key_index = @intCast(input_index) };
 769                 return entry;
 770             }
 771             const key_index: usize = @intCast(entry.key_index);
 772             if (std.mem.eql(u8, current_inputs[key_index].name, name)) {
 773                 return entry;
 774             }
 775             slot_index = (slot_index + 1) & mask;
 776         }
 777         unreachable;
 778     }
 779 
 780     fn findCurrent(
 781         self: *InputChangeStorage,
 782         current_inputs: []const model.Input,
 783         name: []const u8,
 784     ) ?*InputChangeNameEntry {
 785         const slots = self.current_by_name;
 786         if (slots.len == 0) return null;
 787         const mask = slots.len - 1;
 788         const hash: usize = @truncate(std.hash.Wyhash.hash(0, name));
 789         var slot_index = hash & mask;
 790         var probes: usize = 0;
 791         while (probes < slots.len) : (probes += 1) {
 792             const entry = &slots[slot_index];
 793             if (entry.key_index == no_input_index) return null;
 794             const key_index: usize = @intCast(entry.key_index);
 795             if (std.mem.eql(u8, current_inputs[key_index].name, name)) {
 796                 return entry;
 797             }
 798             slot_index = (slot_index + 1) & mask;
 799         }
 800         return null;
 801     }
 802 
 803     fn assertStorage(self: *const InputChangeStorage) void {
 804         const expected = Capacity.derive(self.limits) catch unreachable;
 805         std.debug.assert(std.meta.eql(expected, self.capacity));
 806         std.debug.assert(self.storage.len == self.capacity.storage_bytes);
 807         std.debug.assert(self.changes.len == self.capacity.change_records);
 808         std.debug.assert(self.matched_current.len == self.capacity.matched_flags);
 809         std.debug.assert(self.current_links.len == self.capacity.current_links);
 810         std.debug.assert(self.current_by_name.len == self.capacity.name_slots);
 811     }
 812 };
 813 
 814 comptime {
 815     alloc_phase.capacity.requireProvisionedRejectingOwnerShape(InputChangeStorage);
 816 }
 817 
 818 fn inputChangeSlice(
 819     comptime T: type,
 820     storage: InputChangeStorage.Storage,
 821     offset: usize,
 822     count: usize,
 823 ) []T {
 824     const byte_count = std.math.mul(usize, count, @sizeOf(T)) catch unreachable;
 825     const bytes: []align(@alignOf(T)) u8 =
 826         @alignCast(storage[offset..][0..byte_count]);
 827     return std.mem.bytesAsSlice(T, bytes);
 828 }
 829 
 830 pub const RelinkDecision = enum {
 831     reuse_output,
 832     in_place,
 833     full_link,
 834 };
 835 
 836 pub const RelinkBlocker = enum {
 837     incremental_disabled,
 838     input_hashes_unrecorded,
 839     compatibility_mismatch,
 840     input_changed,
 841     input_added,
 842     input_removed,
 843     input_reordered,
 844     replacement_missing,
 845     replacement_not_changed,
 846     replacement_unpatchable,
 847     replacement_layout_changed,
 848     replacement_grew_past_reserve,
 849     replacement_alignment_increased,
 850 };
 851 
 852 pub const RelinkPlan = struct {
 853     decision: RelinkDecision,
 854     blocker: ?RelinkBlocker = null,
 855     blocking_change_index: ?usize = null,
 856     blocking_replacement_index: ?usize = null,
 857     input_summary: InputChangeSummary = .{},
 858     affected_contributions: InputContributionSummary = .{},
 859 };
 860 
 861 pub const manifest_binary_protocol = "tldr.incremental-manifest.bin/v10";
 862 
 863 pub const ReplacementContribution = patch.ReplacementContribution;
 864 pub const freeReplacementContributions = patch.freeReplacementContributions;
 865 pub const DirectRelinkEvidence = patch.DirectRelinkEvidence;
 866 pub const MemberHashUpdate = patch.MemberHashUpdate;
 867 pub const PatchDecision = patch.PatchDecision;
 868 pub const PatchBlocker = patch.PatchBlocker;
 869 pub const PatchPlan = patch.PatchPlan;
 870 pub const PatchApplication = patch.PatchApplication;
 871 pub const PatchApplyError = patch.PatchApplyError;
 872 pub const IndexError = patch.IndexError;
 873 pub const ContributionIndex = patch.ContributionIndex;
 874 
 875 pub const RelinkApplyError = InputChangeStorage.Exhaustion || PatchApplyError;
 876 pub const ReplacementExtractError = Allocator.Error || error{
 877     PatchRangeOutOfBounds,
 878 };
 879 pub const CandidateRelinkApplyError =
 880     InputChangeStorage.Exhaustion || ReplacementExtractError || PatchApplyError;
 881 pub const RelinkManifestUpdateError = Allocator.Error || error{
 882     RelinkUpdateRequiresInPlacePlan,
 883     ReplacementMissing,
 884     MemberMissing,
 885     SectionLayoutChanged,
 886 };
 887 pub const RelinkManifestClassifyError =
 888     InputChangeStorage.Exhaustion || RelinkManifestUpdateError;
 889 
 890 pub const RelinkApplication = struct {
 891     plan: RelinkPlan,
 892     contributions_written: usize = 0,
 893     bytes_written: usize = 0,
 894     zero_fill_bytes: usize = 0,
 895 };
 896 
 897 const replacement_accounting_index_limit = 512;
 898 const sparse_replacement_extraction_change_limit = 32;
 899 
 900 pub const RecordOwnership = packed struct {
 901     inputs: bool = false,
 902     sections: bool = false,
 903     contributions: bool = false,
 904     discarded_contributions: bool = false,
 905     external_targets: bool = false,
 906     archive_members: bool = false,
 907     got_entries: bool = false,
 908     merge_pieces: bool = false,
 909 };
 910 
 911 pub const Manifest = struct {
 912     target: model.Target,
 913     output_kind: model.OutputKind,
 914     entry_symbol_id: u32 = 0,
 915     image_base: u64,
 916     page_size: u64,
 917     gc_sections: bool,
 918     icf: model.IcfMode,
 919     strip_debug: bool,
 920     build_id: model.BuildIdMode,
 921     input_hashes_recorded: bool,
 922     inputs_read_at_ns: i64 = 0,
 923     strings: Strings = .{},
 924     inputs: []InputRecord = &.{},
 925     sections: []SectionRecord = &.{},
 926     contributions: []ContributionRecord = &.{},
 927     discarded_contributions: []DiscardedContributionRecord = &.{},
 928     external_targets: []ExternalTargetRecord = &.{},
 929     archive_members: []ArchiveMemberRecord = &.{},
 930     got_entries: []GotEntryRecord = &.{},
 931     merge_pieces: []MergePieceRecord = &.{},
 932     owned: RecordOwnership = .{},
 933 
 934     pub fn empty() Manifest {
 935         return .{
 936             .target = .{},
 937             .output_kind = .executable,
 938             .image_base = 0,
 939             .page_size = 0,
 940             .gc_sections = false,
 941             .icf = .off,
 942             .strip_debug = false,
 943             .build_id = .none,
 944             .input_hashes_recorded = false,
 945         };
 946     }
 947 
 948     pub fn fromBinary(allocator: Allocator, bytes: []u8) !Manifest {
 949         return try format.manifestFromBinary(allocator, bytes);
 950     }
 951 
 952     pub fn string(self: *const Manifest, id: u32) []const u8 {
 953         return self.strings.get(id);
 954     }
 955 
 956     pub fn entrySymbol(self: *const Manifest) []const u8 {
 957         if (self.strings.count() == 0) return "";
 958         return self.strings.get(self.entry_symbol_id);
 959     }
 960 
 961     pub fn deinit(self: *Manifest, allocator: Allocator) void {
 962         if (self.owned.inputs and self.inputs.len != 0) allocator.free(self.inputs);
 963         if (self.owned.sections and self.sections.len != 0) allocator.free(self.sections);
 964         if (self.owned.contributions and self.contributions.len != 0) allocator.free(self.contributions);
 965         if (self.owned.discarded_contributions and self.discarded_contributions.len != 0) allocator.free(self.discarded_contributions);
 966         if (self.owned.external_targets and self.external_targets.len != 0) allocator.free(self.external_targets);
 967         if (self.owned.archive_members and self.archive_members.len != 0) allocator.free(self.archive_members);
 968         if (self.owned.got_entries and self.got_entries.len != 0) allocator.free(self.got_entries);
 969         if (self.owned.merge_pieces and self.merge_pieces.len != 0) allocator.free(self.merge_pieces);
 970         self.strings.deinit(allocator);
 971         self.* = empty();
 972     }
 973 
 974     pub fn take(self: *Manifest) Manifest {
 975         const manifest = self.*;
 976         self.* = empty();
 977         return manifest;
 978     }
 979 
 980     pub fn canReuseFor(self: Manifest, options: model.LinkOptions, inputs: []const model.Input) bool {
 981         if (!self.input_hashes_recorded) return false;
 982         if (!self.canReuseOptions(options)) return false;
 983         if (self.inputs.len != inputs.len) return false;
 984 
 985         for (inputs, 0..) |input, index| {
 986             const record = self.inputs[index];
 987             if (!std.mem.eql(u8, self.string(record.name_id), input.name)) return false;
 988             if (!inputContentUnchanged(record, input, self.inputs_read_at_ns)) return false;
 989         }
 990         return true;
 991     }
 992 
 993     pub fn canReuseOptions(self: Manifest, options: model.LinkOptions) bool {
 994         if (options.incremental_mode == .off) return false;
 995         if (self.target.object_format != options.target.object_format) return false;
 996         if (self.target.architecture != options.target.architecture) return false;
 997         if (self.target.endianness != options.target.endianness) return false;
 998         if (self.target.pointer_width_bits != options.target.pointer_width_bits) return false;
 999         if (self.output_kind != options.output_kind) return false;
1000         if (self.image_base != options.image_base) return false;
1001         if (self.page_size != options.page_size) return false;
1002         if (self.gc_sections != options.gc_sections) return false;
1003         if (self.icf != options.icf) return false;
1004         if (self.strip_debug != options.strip_debug) return false;
1005         if (self.build_id != options.build_id) return false;
1006         if (!std.mem.eql(u8, self.entrySymbol(), options.entry_symbol)) return false;
1007         return true;
1008     }
1009 
1010     pub fn planContributionReplacement(
1011         self: Manifest,
1012         replacements: []const ReplacementContribution,
1013     ) PatchPlan {
1014         return patch.planContributionReplacement(self, replacements);
1015     }
1016 
1017     pub fn applyContributionReplacement(
1018         self: Manifest,
1019         image: []u8,
1020         replacements: []const ReplacementContribution,
1021     ) PatchApplyError!PatchApplication {
1022         return try patch.applyContributionReplacement(self, image, replacements);
1023     }
1024 
1025     pub fn formatTextAlloc(self: Manifest, allocator: Allocator) ![]u8 {
1026         return try format.textAlloc(self, allocator);
1027     }
1028 
1029     pub fn scalarPatchesAlloc(
1030         self: Manifest,
1031         allocator: Allocator,
1032         encoded: []const u8,
1033         input_indexes: []const usize,
1034         contribution_indexes: []const usize,
1035         archive_member_indexes: []const usize,
1036     ) ![]format.ManifestFieldPatch {
1037         return format.manifestScalarPatchesAlloc(allocator, encoded, self, input_indexes, contribution_indexes, archive_member_indexes);
1038     }
1039 
1040     pub fn formatBinaryAlloc(self: Manifest, allocator: Allocator) ![]u8 {
1041         return try format.binaryAlloc(self, allocator);
1042     }
1043 
1044     pub fn writeBinary(self: Manifest, writer: *std.Io.Writer) !void {
1045         try format.writeBinary(self, writer);
1046     }
1047 
1048     pub fn writeText(self: Manifest, writer: *std.Io.Writer) std.Io.Writer.Error!void {
1049         try format.writeText(self, writer);
1050     }
1051 };
1052 
1053 pub const PreparedState = struct {
1054     manifest: Manifest,
1055     contribution_index: ?ContributionIndex = null,
1056     input_contributions: []InputContributionSummary = &.{},
1057 
1058     pub const RecordUpdates = struct {
1059         input_indexes: std.ArrayListUnmanaged(usize) = .empty,
1060         contribution_indexes: std.ArrayListUnmanaged(usize) = .empty,
1061         archive_member_indexes: std.ArrayListUnmanaged(usize) = .empty,
1062 
1063         pub fn deinit(self: *RecordUpdates, allocator: Allocator) void {
1064             self.input_indexes.deinit(allocator);
1065             self.contribution_indexes.deinit(allocator);
1066             self.archive_member_indexes.deinit(allocator);
1067         }
1068     };
1069 
1070     pub fn fromOwnedManifest(allocator: Allocator, manifest: Manifest) Allocator.Error!PreparedState {
1071         var owned_manifest = manifest;
1072         errdefer owned_manifest.deinit(allocator);
1073 
1074         const input_contributions = try buildInputContributionSummaries(allocator, owned_manifest);
1075         errdefer if (input_contributions.len != 0) allocator.free(input_contributions);
1076 
1077         return .{
1078             .manifest = owned_manifest,
1079             .input_contributions = input_contributions,
1080         };
1081     }
1082 
1083     pub fn ensureReplacementIndex(
1084         self: *PreparedState,
1085         allocator: Allocator,
1086         replacements: []const ReplacementContribution,
1087     ) IndexError!void {
1088         if (replacements.len == 0) return;
1089         if (self.contribution_index) |*index| {
1090             index.deinit(allocator);
1091             self.contribution_index = null;
1092         }
1093         self.contribution_index = try ContributionIndex.initForReplacements(
1094             allocator,
1095             self.manifest,
1096             replacements,
1097         );
1098     }
1099 
1100     pub fn deinit(self: *PreparedState, allocator: Allocator) void {
1101         if (self.contribution_index) |*index| index.deinit(allocator);
1102         if (self.input_contributions.len != 0) allocator.free(self.input_contributions);
1103         self.manifest.deinit(allocator);
1104         self.* = undefined;
1105     }
1106 
1107     pub fn canReuseFor(self: *const PreparedState, options: model.LinkOptions, inputs: []const model.Input) bool {
1108         return self.manifest.canReuseFor(options, inputs);
1109     }
1110 
1111     pub fn classifyInputs(
1112         self: *const PreparedState,
1113         storage: *InputChangeStorage,
1114         inputs: []const model.Input,
1115     ) InputChangeStorage.Exhaustion!InputChanges {
1116         return try storage.classify(RecordedInputs.fromManifest(&self.manifest), inputs);
1117     }
1118 
1119     pub fn contributionSummaryForInput(self: *const PreparedState, recorded_index: usize) InputContributionSummary {
1120         if (recorded_index >= self.input_contributions.len) return .{};
1121         return self.input_contributions[recorded_index];
1122     }
1123 
1124     pub fn contributionSummaryForChange(self: *const PreparedState, change: InputChange) InputContributionSummary {
1125         const recorded_index = change.recorded_index orelse return .{};
1126         return self.contributionSummaryForInput(recorded_index);
1127     }
1128 
1129     fn relinkPreconditionPlan(self: *const PreparedState, options: model.LinkOptions) ?RelinkPlan {
1130         if (options.incremental_mode == .off) {
1131             return .{
1132                 .decision = .full_link,
1133                 .blocker = .incremental_disabled,
1134             };
1135         }
1136         if (!self.manifest.input_hashes_recorded) {
1137             return .{
1138                 .decision = .full_link,
1139                 .blocker = .input_hashes_unrecorded,
1140             };
1141         }
1142         if (!self.manifest.canReuseOptions(options)) {
1143             return .{
1144                 .decision = .full_link,
1145                 .blocker = .compatibility_mismatch,
1146             };
1147         }
1148         return null;
1149     }
1150 
1151     pub fn planInputRelink(
1152         self: *const PreparedState,
1153         storage: *InputChangeStorage,
1154         options: model.LinkOptions,
1155         inputs: []const model.Input,
1156     ) InputChangeStorage.Exhaustion!RelinkPlan {
1157         if (self.relinkPreconditionPlan(options)) |plan| return plan;
1158 
1159         const input_changes = try self.classifyInputs(storage, inputs);
1160         return planRelinkFromInputChangesWithContributions(input_changes, self.input_contributions);
1161     }
1162 
1163     pub fn planChangedInputRelink(
1164         self: *const PreparedState,
1165         storage: *InputChangeStorage,
1166         options: model.LinkOptions,
1167         inputs: []const model.Input,
1168         replacements: []const ReplacementContribution,
1169     ) InputChangeStorage.Exhaustion!RelinkPlan {
1170         if (self.relinkPreconditionPlan(options)) |plan| return plan;
1171 
1172         const input_changes = try self.classifyInputs(storage, inputs);
1173         return self.planChangedInputRelinkFromInputChanges(options, input_changes, replacements);
1174     }
1175 
1176     pub fn planChangedInputRelinkFromInputChanges(
1177         self: *const PreparedState,
1178         options: model.LinkOptions,
1179         input_changes: InputChanges,
1180         replacements: []const ReplacementContribution,
1181     ) RelinkPlan {
1182         if (self.relinkPreconditionPlan(options)) |plan| return plan;
1183         return self.planChangedInputRelinkFromChanges(input_changes, replacements);
1184     }
1185 
1186     fn planChangedInputRelinkFromChanges(
1187         self: *const PreparedState,
1188         input_changes: InputChanges,
1189         replacements: []const ReplacementContribution,
1190     ) RelinkPlan {
1191         if (input_changes.summary.added != 0 or input_changes.summary.removed != 0) {
1192             for (input_changes.changes, 0..) |change, change_index| switch (change.kind) {
1193                 .unchanged, .changed => {},
1194                 .added => return .{
1195                     .decision = .full_link,
1196                     .blocker = .input_added,
1197                     .blocking_change_index = change_index,
1198                     .input_summary = input_changes.summary,
1199                 },
1200                 .removed => return .{
1201                     .decision = .full_link,
1202                     .blocker = .input_removed,
1203                     .blocking_change_index = change_index,
1204                     .input_summary = input_changes.summary,
1205                     .affected_contributions = self.contributionSummaryForChange(change),
1206                 },
1207             };
1208         }
1209 
1210         if (inputOrderDriftChangeIndex(input_changes)) |change_index| {
1211             return .{
1212                 .decision = .full_link,
1213                 .blocker = .input_reordered,
1214                 .blocking_change_index = change_index,
1215                 .input_summary = input_changes.summary,
1216                 .affected_contributions = self.contributionSummaryForChange(input_changes.changes[change_index]),
1217             };
1218         }
1219 
1220         if (input_changes.allUnchanged()) {
1221             if (replacements.len == 0) {
1222                 return .{
1223                     .decision = .reuse_output,
1224                     .input_summary = input_changes.summary,
1225                 };
1226             }
1227             return self.replacementNotChangedPlan(input_changes, replacements, 0);
1228         }
1229 
1230         if (input_changes.changes.len <= replacement_accounting_index_limit) {
1231             return self.planChangedInputRelinkFromIndexedChanges(input_changes, replacements);
1232         }
1233         return self.planChangedInputRelinkFromLinearChanges(input_changes, replacements);
1234     }
1235 
1236     fn planChangedInputRelinkFromLinearChanges(
1237         self: *const PreparedState,
1238         input_changes: InputChanges,
1239         replacements: []const ReplacementContribution,
1240     ) RelinkPlan {
1241         var affected: InputContributionSummary = .{};
1242         for (input_changes.changes, 0..) |change, change_index| {
1243             switch (change.kind) {
1244                 .unchanged => {},
1245                 .added => return .{
1246                     .decision = .full_link,
1247                     .blocker = .input_added,
1248                     .blocking_change_index = change_index,
1249                     .input_summary = input_changes.summary,
1250                 },
1251                 .removed => return .{
1252                     .decision = .full_link,
1253                     .blocker = .input_removed,
1254                     .blocking_change_index = change_index,
1255                     .input_summary = input_changes.summary,
1256                     .affected_contributions = self.contributionSummaryForChange(change),
1257                 },
1258                 .changed => {
1259                     const contribution_summary = self.contributionSummaryForChange(change);
1260                     addInputContributionSummary(&affected, contribution_summary);
1261                     const recorded_index = change.recorded_index orelse {
1262                         return .{
1263                             .decision = .full_link,
1264                             .blocker = .replacement_missing,
1265                             .blocking_change_index = change_index,
1266                             .input_summary = input_changes.summary,
1267                             .affected_contributions = contribution_summary,
1268                         };
1269                     };
1270                     if (countRetainedReplacementsForInput(replacements, recorded_index) != contribution_summary.retained) {
1271                         return .{
1272                             .decision = .full_link,
1273                             .blocker = .replacement_missing,
1274                             .blocking_change_index = change_index,
1275                             .input_summary = input_changes.summary,
1276                             .affected_contributions = contribution_summary,
1277                         };
1278                     }
1279                 },
1280             }
1281         }
1282 
1283         if (replacementIndexOutsideChangedInputs(input_changes, replacements)) |replacement_index| {
1284             return self.replacementNotChangedPlan(input_changes, replacements, replacement_index);
1285         }
1286 
1287         return self.planReplacementRelinkFromChanges(input_changes, replacements, affected);
1288     }
1289 
1290     fn planChangedInputRelinkFromIndexedChanges(
1291         self: *const PreparedState,
1292         input_changes: InputChanges,
1293         replacements: []const ReplacementContribution,
1294     ) RelinkPlan {
1295         var recorded_change_indexes_storage = @as([replacement_accounting_index_limit]?usize, @splat(null));
1296         var replacement_counts_storage = @as([replacement_accounting_index_limit]usize, @splat(0));
1297         const recorded_change_indexes = recorded_change_indexes_storage[0..input_changes.changes.len];
1298         const replacement_counts = replacement_counts_storage[0..input_changes.changes.len];
1299         @memset(recorded_change_indexes, null);
1300         @memset(replacement_counts, 0);
1301 
1302         var affected: InputContributionSummary = .{};
1303         for (input_changes.changes, 0..) |change, change_index| {
1304             switch (change.kind) {
1305                 .unchanged => {},
1306                 .added => return .{
1307                     .decision = .full_link,
1308                     .blocker = .input_added,
1309                     .blocking_change_index = change_index,
1310                     .input_summary = input_changes.summary,
1311                 },
1312                 .removed => return .{
1313                     .decision = .full_link,
1314                     .blocker = .input_removed,
1315                     .blocking_change_index = change_index,
1316                     .input_summary = input_changes.summary,
1317                     .affected_contributions = self.contributionSummaryForChange(change),
1318                 },
1319                 .changed => {
1320                     const contribution_summary = self.contributionSummaryForChange(change);
1321                     addInputContributionSummary(&affected, contribution_summary);
1322                     const recorded_index = change.recorded_index orelse {
1323                         return .{
1324                             .decision = .full_link,
1325                             .blocker = .replacement_missing,
1326                             .blocking_change_index = change_index,
1327                             .input_summary = input_changes.summary,
1328                             .affected_contributions = contribution_summary,
1329                         };
1330                     };
1331                     if (recorded_index >= recorded_change_indexes.len) {
1332                         return .{
1333                             .decision = .full_link,
1334                             .blocker = .replacement_missing,
1335                             .blocking_change_index = change_index,
1336                             .input_summary = input_changes.summary,
1337                             .affected_contributions = contribution_summary,
1338                         };
1339                     }
1340                     recorded_change_indexes[recorded_index] = change_index;
1341                 },
1342             }
1343         }
1344 
1345         var first_outside_replacement_index: ?usize = null;
1346         for (replacements, 0..) |replacement, replacement_index| {
1347             if (replacement.input_index >= recorded_change_indexes.len) {
1348                 if (first_outside_replacement_index == null) first_outside_replacement_index = replacement_index;
1349                 continue;
1350             }
1351             const change_index = recorded_change_indexes[replacement.input_index] orelse {
1352                 if (first_outside_replacement_index == null) first_outside_replacement_index = replacement_index;
1353                 continue;
1354             };
1355             if (input_changes.changes[change_index].kind != .changed) {
1356                 if (first_outside_replacement_index == null) first_outside_replacement_index = replacement_index;
1357                 continue;
1358             }
1359             replacement_counts[replacement.input_index] += 1;
1360         }
1361 
1362         for (input_changes.changes, 0..) |change, change_index| {
1363             if (change.kind != .changed) continue;
1364             const recorded_index = change.recorded_index orelse continue;
1365             const contribution_summary = self.contributionSummaryForChange(change);
1366             if (recorded_index >= replacement_counts.len or replacement_counts[recorded_index] != contribution_summary.retained) {
1367                 return .{
1368                     .decision = .full_link,
1369                     .blocker = .replacement_missing,
1370                     .blocking_change_index = change_index,
1371                     .input_summary = input_changes.summary,
1372                     .affected_contributions = contribution_summary,
1373                 };
1374             }
1375         }
1376 
1377         if (first_outside_replacement_index) |replacement_index| {
1378             return self.replacementNotChangedPlan(input_changes, replacements, replacement_index);
1379         }
1380 
1381         return self.planReplacementRelinkFromChanges(input_changes, replacements, affected);
1382     }
1383 
1384     fn replacementNotChangedPlan(
1385         self: *const PreparedState,
1386         input_changes: InputChanges,
1387         replacements: []const ReplacementContribution,
1388         replacement_index: usize,
1389     ) RelinkPlan {
1390         const blocking_change_index = if (replacement_index < replacements.len)
1391             changeIndexForRecordedInput(input_changes, replacements[replacement_index].input_index)
1392         else
1393             null;
1394         return .{
1395             .decision = .full_link,
1396             .blocker = .replacement_not_changed,
1397             .blocking_change_index = blocking_change_index,
1398             .blocking_replacement_index = replacement_index,
1399             .input_summary = input_changes.summary,
1400             .affected_contributions = if (blocking_change_index) |change_index|
1401                 self.contributionSummaryForChange(input_changes.changes[change_index])
1402             else
1403                 .{},
1404         };
1405     }
1406 
1407     fn planReplacementRelinkFromChanges(
1408         self: *const PreparedState,
1409         input_changes: InputChanges,
1410         replacements: []const ReplacementContribution,
1411         affected: InputContributionSummary,
1412     ) RelinkPlan {
1413         const patch_plan = self.planContributionReplacement(replacements);
1414         if (patch_plan.decision == .in_place) {
1415             return .{
1416                 .decision = .in_place,
1417                 .input_summary = input_changes.summary,
1418                 .affected_contributions = affected,
1419             };
1420         }
1421 
1422         const blocking_replacement_index = patch_plan.blocking_index;
1423         const blocking_change_index = if (blocking_replacement_index) |replacement_index|
1424             if (replacement_index < replacements.len)
1425                 changeIndexForRecordedInput(input_changes, replacements[replacement_index].input_index)
1426             else
1427                 null
1428         else
1429             null;
1430 
1431         return .{
1432             .decision = .full_link,
1433             .blocker = relinkBlockerForPatchBlocker(patch_plan.blocker),
1434             .blocking_change_index = blocking_change_index,
1435             .blocking_replacement_index = blocking_replacement_index,
1436             .input_summary = input_changes.summary,
1437             .affected_contributions = if (blocking_change_index) |change_index|
1438                 self.contributionSummaryForChange(input_changes.changes[change_index])
1439             else
1440                 affected,
1441         };
1442     }
1443 
1444     pub fn planContributionReplacement(
1445         self: *const PreparedState,
1446         replacements: []const ReplacementContribution,
1447     ) PatchPlan {
1448         if (self.contribution_index) |index| {
1449             return index.planContributionReplacement(self.manifest, replacements);
1450         }
1451         return patch.planContributionReplacement(self.manifest, replacements);
1452     }
1453 
1454     fn contributionIndexForReplacement(
1455         self: *const PreparedState,
1456         cursor: *patch.ContributionCursor,
1457         replacement: ReplacementContribution,
1458     ) ?usize {
1459         if (self.contribution_index) |index| return index.contributionIndexForReplacement(replacement);
1460         const match = cursor.find(self.manifest, replacement) orelse return null;
1461         return match.index;
1462     }
1463 
1464     pub fn applyChangedInputRelink(
1465         self: *const PreparedState,
1466         storage: *InputChangeStorage,
1467         image: []u8,
1468         options: model.LinkOptions,
1469         inputs: []const model.Input,
1470         replacements: []const ReplacementContribution,
1471     ) RelinkApplyError!RelinkApplication {
1472         if (self.relinkPreconditionPlan(options)) |plan| return .{ .plan = plan };
1473 
1474         const input_changes = try self.classifyInputs(storage, inputs);
1475         return try self.applyChangedInputRelinkFromInputChanges(options, input_changes, image, replacements);
1476     }
1477 
1478     pub fn applyChangedInputRelinkFromCandidate(
1479         self: *const PreparedState,
1480         allocator: Allocator,
1481         storage: *InputChangeStorage,
1482         image: []u8,
1483         options: model.LinkOptions,
1484         inputs: []const model.Input,
1485         candidate_image: []const u8,
1486         candidate_manifest: Manifest,
1487     ) CandidateRelinkApplyError!RelinkApplication {
1488         if (self.relinkPreconditionPlan(options)) |plan| return .{ .plan = plan };
1489 
1490         const input_changes = try self.classifyInputs(storage, inputs);
1491 
1492         const replacements = try replacementContributionsFromImage(
1493             allocator,
1494             candidate_image,
1495             candidate_manifest,
1496             input_changes,
1497         );
1498         defer freeReplacementContributions(allocator, replacements);
1499 
1500         return try self.applyChangedInputRelinkFromChanges(input_changes, image, replacements);
1501     }
1502 
1503     pub fn applyChangedInputRelinkFromInputChanges(
1504         self: *const PreparedState,
1505         options: model.LinkOptions,
1506         input_changes: InputChanges,
1507         image: []u8,
1508         replacements: []const ReplacementContribution,
1509     ) PatchApplyError!RelinkApplication {
1510         if (self.relinkPreconditionPlan(options)) |plan| return .{ .plan = plan };
1511         return try self.applyChangedInputRelinkFromChanges(input_changes, image, replacements);
1512     }
1513 
1514     fn applyChangedInputRelinkFromChanges(
1515         self: *const PreparedState,
1516         input_changes: InputChanges,
1517         image: []u8,
1518         replacements: []const ReplacementContribution,
1519     ) PatchApplyError!RelinkApplication {
1520         const plan = self.planChangedInputRelinkFromChanges(input_changes, replacements);
1521         return try self.applyAcceptedChangedInputRelink(image, replacements, plan);
1522     }
1523 
1524     pub fn acceptedRelinkRecordUpdates(
1525         self: *const PreparedState,
1526         allocator: Allocator,
1527         inputs: []const model.Input,
1528         input_changes: InputChanges,
1529         replacements: []const ReplacementContribution,
1530         member_updates: []const MemberHashUpdate,
1531     ) !RecordUpdates {
1532         var updates = RecordUpdates{};
1533         errdefer updates.deinit(allocator);
1534         for (input_changes.changes) |change| {
1535             const recorded_index = change.recorded_index orelse continue;
1536             const current_index = change.current_index orelse continue;
1537             if (recorded_index >= self.manifest.inputs.len or current_index >= inputs.len) continue;
1538             try updates.input_indexes.append(allocator, recorded_index);
1539         }
1540         var cursor = patch.ContributionCursor{};
1541         for (replacements) |replacement| {
1542             const contribution_index = self.contributionIndexForReplacement(&cursor, replacement) orelse
1543                 return error.ReplacementMissing;
1544             if (contribution_index >= self.manifest.contributions.len) return error.ReplacementMissing;
1545             try updates.contribution_indexes.append(allocator, contribution_index);
1546         }
1547         for (member_updates) |update| {
1548             if (update.member_index >= self.manifest.archive_members.len) return error.MemberMissing;
1549             try updates.archive_member_indexes.append(allocator, update.member_index);
1550         }
1551         return updates;
1552     }
1553 
1554     pub fn replacementFileRange(
1555         self: *const PreparedState,
1556         replacement: ReplacementContribution,
1557     ) ?patch.FileRange {
1558         var cursor = patch.ContributionCursor{};
1559         const contribution_index = self.contributionIndexForReplacement(&cursor, replacement) orelse return null;
1560         if (contribution_index >= self.manifest.contributions.len) return null;
1561         return patch.replacementFileRange(self.manifest.contributions[contribution_index], replacement);
1562     }
1563 
1564     pub fn applyAcceptedChangedInputRelink(
1565         self: *const PreparedState,
1566         image: []u8,
1567         replacements: []const ReplacementContribution,
1568         accepted_plan: RelinkPlan,
1569     ) PatchApplyError!RelinkApplication {
1570         var application = RelinkApplication{
1571             .plan = accepted_plan,
1572         };
1573         if (accepted_plan.decision != .in_place) return application;
1574         const patch_application = try self.applyContributionReplacementInPlace(image, replacements);
1575         if (patch_application.plan.decision == .full_link) {
1576             application.plan = .{
1577                 .decision = .full_link,
1578                 .blocker = relinkBlockerForPatchBlocker(patch_application.plan.blocker),
1579                 .blocking_replacement_index = patch_application.plan.blocking_index,
1580                 .input_summary = accepted_plan.input_summary,
1581                 .affected_contributions = accepted_plan.affected_contributions,
1582             };
1583             return application;
1584         }
1585         application.contributions_written = patch_application.contributions_written;
1586         application.bytes_written = patch_application.bytes_written;
1587         application.zero_fill_bytes = patch_application.zero_fill_bytes;
1588         return application;
1589     }
1590 
1591     pub fn applyContributionReplacement(
1592         self: *const PreparedState,
1593         image: []u8,
1594         replacements: []const ReplacementContribution,
1595     ) PatchApplyError!PatchApplication {
1596         if (self.contribution_index) |index| {
1597             return try index.applyContributionReplacement(image, self.manifest, replacements);
1598         }
1599         return try patch.applyContributionReplacement(self.manifest, image, replacements);
1600     }
1601 
1602     fn applyContributionReplacementInPlace(
1603         self: *const PreparedState,
1604         image: []u8,
1605         replacements: []const ReplacementContribution,
1606     ) PatchApplyError!PatchApplication {
1607         if (self.contribution_index) |index| {
1608             return try index.applyContributionReplacementInPlace(image, self.manifest, replacements);
1609         }
1610         return try patch.applyContributionReplacementInPlace(self.manifest, image, replacements);
1611     }
1612 
1613     pub fn updateManifestForChangedInputRelinkFromInputChanges(
1614         self: *PreparedState,
1615         inputs: []const model.Input,
1616         input_changes: InputChanges,
1617         replacements: []const ReplacementContribution,
1618         member_updates: []const MemberHashUpdate,
1619         inputs_read_at_ns: i64,
1620     ) RelinkManifestUpdateError!void {
1621         if (!self.manifest.input_hashes_recorded) return error.RelinkUpdateRequiresInPlacePlan;
1622 
1623         const plan = self.planChangedInputRelinkFromChanges(input_changes, replacements);
1624         try self.updateManifestForAcceptedChangedInputRelinkFromInputChanges(
1625             inputs,
1626             input_changes,
1627             replacements,
1628             member_updates,
1629             inputs_read_at_ns,
1630             plan,
1631         );
1632     }
1633 
1634     pub fn updateManifestForAcceptedChangedInputRelinkFromInputChanges(
1635         self: *PreparedState,
1636         inputs: []const model.Input,
1637         input_changes: InputChanges,
1638         replacements: []const ReplacementContribution,
1639         member_updates: []const MemberHashUpdate,
1640         inputs_read_at_ns: i64,
1641         accepted_plan: RelinkPlan,
1642     ) RelinkManifestUpdateError!void {
1643         if (!self.manifest.input_hashes_recorded) return error.RelinkUpdateRequiresInPlacePlan;
1644         if (accepted_plan.decision != .in_place) return error.RelinkUpdateRequiresInPlacePlan;
1645 
1646         for (input_changes.changes) |change| {
1647             const recorded_index = change.recorded_index orelse continue;
1648             const current_index = change.current_index orelse continue;
1649             if (recorded_index >= self.manifest.inputs.len or current_index >= inputs.len) continue;
1650             const input = inputs[current_index];
1651             const identity = input.identity orelse model.InputIdentity{ .mtime_ns = 0, .inode = 0 };
1652             self.manifest.inputs[recorded_index].size = input.bytes.len;
1653             self.manifest.inputs[recorded_index].hash = hashBytes(input.bytes);
1654             self.manifest.inputs[recorded_index].mtime_ns = identity.mtime_ns;
1655             self.manifest.inputs[recorded_index].inode = identity.inode;
1656             self.manifest.inputs[recorded_index].identity_recorded = input.identity != null;
1657         }
1658         self.manifest.inputs_read_at_ns = inputs_read_at_ns;
1659 
1660         var cursor = patch.ContributionCursor{};
1661         for (replacements) |replacement| {
1662             const contribution_index = self.contributionIndexForReplacement(&cursor, replacement) orelse
1663                 return error.ReplacementMissing;
1664             if (contribution_index >= self.manifest.contributions.len) return error.ReplacementMissing;
1665             const previous_file_size = self.manifest.contributions[contribution_index].file_size;
1666             self.manifest.contributions[contribution_index].size = replacement.size;
1667             self.manifest.contributions[contribution_index].file_size = if (previous_file_size == 0 and replacement.payload.len == 0)
1668                 0
1669             else
1670                 replacement.size;
1671         }
1672 
1673         for (member_updates) |update| {
1674             if (update.member_index >= self.manifest.archive_members.len) return error.MemberMissing;
1675             self.manifest.archive_members[update.member_index].hash = update.hash;
1676         }
1677     }
1678 
1679     pub fn updateManifestForCandidateRelink(
1680         self: *PreparedState,
1681         allocator: Allocator,
1682         storage: *InputChangeStorage,
1683         inputs: []const model.Input,
1684         replacements: []const ReplacementContribution,
1685         candidate_manifest: Manifest,
1686     ) RelinkManifestClassifyError!void {
1687         const input_changes = try self.classifyInputs(storage, inputs);
1688         try self.updateManifestForCandidateRelinkFromInputChanges(allocator, inputs, input_changes, replacements, candidate_manifest);
1689     }
1690 
1691     pub fn updateManifestForCandidateRelinkFromInputChanges(
1692         self: *PreparedState,
1693         allocator: Allocator,
1694         inputs: []const model.Input,
1695         input_changes: InputChanges,
1696         replacements: []const ReplacementContribution,
1697         candidate_manifest: Manifest,
1698     ) RelinkManifestUpdateError!void {
1699         const plan = self.planChangedInputRelinkFromChanges(input_changes, replacements);
1700         try self.updateManifestForAcceptedCandidateRelinkFromInputChanges(
1701             allocator,
1702             inputs,
1703             input_changes,
1704             replacements,
1705             candidate_manifest,
1706             plan,
1707         );
1708     }
1709 
1710     pub fn updateManifestForAcceptedCandidateRelinkFromInputChanges(
1711         self: *PreparedState,
1712         allocator: Allocator,
1713         inputs: []const model.Input,
1714         input_changes: InputChanges,
1715         replacements: []const ReplacementContribution,
1716         candidate_manifest: Manifest,
1717         accepted_plan: RelinkPlan,
1718     ) RelinkManifestUpdateError!void {
1719         try self.validateCandidateSectionLayout(candidate_manifest);
1720         try self.updateManifestForAcceptedChangedInputRelinkFromInputChanges(
1721             inputs,
1722             input_changes,
1723             replacements,
1724             &.{},
1725             candidate_manifest.inputs_read_at_ns,
1726             accepted_plan,
1727         );
1728         for (self.manifest.sections, 0..) |*section, section_index| {
1729             section.size = candidate_manifest.sections[section_index].size;
1730         }
1731         try self.updateInputLinkHashesFromCandidate(input_changes, candidate_manifest);
1732         try self.replaceDiscardedContributionsFromCandidate(allocator, input_changes, candidate_manifest);
1733         try self.replaceExternalTargetsFromCandidate(allocator, candidate_manifest);
1734         try self.replaceArchiveMembersFromCandidate(allocator, input_changes, candidate_manifest);
1735         try self.replaceGotEntriesFromCandidate(allocator, input_changes, candidate_manifest);
1736         try self.replaceMergePiecesFromCandidate(allocator, input_changes, candidate_manifest);
1737         try self.rebuildInputContributionSummaries(allocator);
1738     }
1739 
1740     fn updateInputLinkHashesFromCandidate(
1741         self: *PreparedState,
1742         input_changes: InputChanges,
1743         candidate_manifest: Manifest,
1744     ) RelinkManifestUpdateError!void {
1745         for (input_changes.changes) |change| {
1746             const recorded_index = change.recorded_index orelse continue;
1747             const current_index = change.current_index orelse continue;
1748             if (recorded_index >= self.manifest.inputs.len or current_index >= candidate_manifest.inputs.len) return error.SectionLayoutChanged;
1749             self.manifest.inputs[recorded_index].link_hash = candidate_manifest.inputs[current_index].link_hash;
1750             self.manifest.inputs[recorded_index].selection_hash = candidate_manifest.inputs[current_index].selection_hash;
1751         }
1752     }
1753 
1754     fn validateCandidateSectionLayout(
1755         self: *const PreparedState,
1756         candidate_manifest: Manifest,
1757     ) error{SectionLayoutChanged}!void {
1758         if (self.manifest.sections.len != candidate_manifest.sections.len) return error.SectionLayoutChanged;
1759         for (self.manifest.sections, candidate_manifest.sections) |recorded, candidate| {
1760             if (!std.mem.eql(u8, self.manifest.string(recorded.name_id), candidate_manifest.string(candidate.name_id))) return error.SectionLayoutChanged;
1761             if (recorded.address != candidate.address) return error.SectionLayoutChanged;
1762             if (recorded.file_offset != candidate.file_offset) return error.SectionLayoutChanged;
1763             if (recorded.reserved_size != candidate.reserved_size) return error.SectionLayoutChanged;
1764             if (recorded.alignment != candidate.alignment) return error.SectionLayoutChanged;
1765         }
1766     }
1767 
1768     fn replaceDiscardedContributionsFromCandidate(
1769         self: *PreparedState,
1770         allocator: Allocator,
1771         input_changes: InputChanges,
1772         candidate_manifest: Manifest,
1773     ) RelinkManifestUpdateError!void {
1774         const discarded_contributions = try cloneCandidateDiscardedContributions(
1775             allocator,
1776             &self.manifest.strings,
1777             input_changes,
1778             candidate_manifest,
1779         );
1780         errdefer if (discarded_contributions.len != 0) allocator.free(discarded_contributions);
1781 
1782         if (self.manifest.owned.discarded_contributions and self.manifest.discarded_contributions.len != 0) {
1783             allocator.free(self.manifest.discarded_contributions);
1784         }
1785         self.manifest.discarded_contributions = discarded_contributions;
1786         self.manifest.owned.discarded_contributions = true;
1787     }
1788 
1789     fn replaceArchiveMembersFromCandidate(
1790         self: *PreparedState,
1791         allocator: Allocator,
1792         input_changes: InputChanges,
1793         candidate_manifest: Manifest,
1794     ) RelinkManifestUpdateError!void {
1795         const archive_members = try cloneArchiveMemberRecords(allocator, &self.manifest.strings, input_changes, candidate_manifest);
1796         errdefer if (archive_members.len != 0) allocator.free(archive_members);
1797 
1798         if (self.manifest.owned.archive_members and self.manifest.archive_members.len != 0) {
1799             allocator.free(self.manifest.archive_members);
1800         }
1801         self.manifest.archive_members = archive_members;
1802         self.manifest.owned.archive_members = true;
1803     }
1804 
1805     fn replaceGotEntriesFromCandidate(
1806         self: *PreparedState,
1807         allocator: Allocator,
1808         input_changes: InputChanges,
1809         candidate_manifest: Manifest,
1810     ) RelinkManifestUpdateError!void {
1811         const got_entries = try cloneGotEntryRecords(allocator, &self.manifest.strings, input_changes, candidate_manifest);
1812         errdefer if (got_entries.len != 0) allocator.free(got_entries);
1813 
1814         if (self.manifest.owned.got_entries and self.manifest.got_entries.len != 0) {
1815             allocator.free(self.manifest.got_entries);
1816         }
1817         self.manifest.got_entries = got_entries;
1818         self.manifest.owned.got_entries = true;
1819     }
1820 
1821     fn replaceMergePiecesFromCandidate(
1822         self: *PreparedState,
1823         allocator: Allocator,
1824         input_changes: InputChanges,
1825         candidate_manifest: Manifest,
1826     ) RelinkManifestUpdateError!void {
1827         const merge_pieces = try cloneMergePieceRecords(allocator, &self.manifest.strings, input_changes, candidate_manifest);
1828         errdefer if (merge_pieces.len != 0) allocator.free(merge_pieces);
1829 
1830         if (self.manifest.owned.merge_pieces and self.manifest.merge_pieces.len != 0) {
1831             allocator.free(self.manifest.merge_pieces);
1832         }
1833         self.manifest.merge_pieces = merge_pieces;
1834         self.manifest.owned.merge_pieces = true;
1835     }
1836 
1837     fn replaceExternalTargetsFromCandidate(
1838         self: *PreparedState,
1839         allocator: Allocator,
1840         candidate_manifest: Manifest,
1841     ) Allocator.Error!void {
1842         const external_targets = try cloneExternalTargetRecords(allocator, &self.manifest.strings, candidate_manifest);
1843         errdefer if (external_targets.len != 0) allocator.free(external_targets);
1844 
1845         if (self.manifest.owned.external_targets and self.manifest.external_targets.len != 0) {
1846             allocator.free(self.manifest.external_targets);
1847         }
1848         self.manifest.external_targets = external_targets;
1849         self.manifest.owned.external_targets = true;
1850     }
1851 
1852     fn rebuildInputContributionSummaries(
1853         self: *PreparedState,
1854         allocator: Allocator,
1855     ) Allocator.Error!void {
1856         const input_contributions = try buildInputContributionSummaries(allocator, self.manifest);
1857         if (self.input_contributions.len != 0) allocator.free(self.input_contributions);
1858         self.input_contributions = input_contributions;
1859     }
1860 };
1861 
1862 pub fn inputContentUnchanged(record: InputRecord, input: model.Input, inputs_read_at_ns: i64) bool {
1863     if (record.size != input.bytes.len) return false;
1864     if (inputIdentityUnchanged(record, input, inputs_read_at_ns)) return true;
1865     return record.hash == hashBytes(input.bytes);
1866 }
1867 
1868 fn inputIdentityUnchanged(record: InputRecord, input: model.Input, inputs_read_at_ns: i64) bool {
1869     if (!record.identity_recorded) return false;
1870     const identity = input.identity orelse return false;
1871     return record.inode == identity.inode and
1872         record.mtime_ns == identity.mtime_ns and
1873         record.mtime_ns < inputs_read_at_ns;
1874 }
1875 
1876 const linear_input_classification_limit = 16;
1877 
1878 const no_input_index = std.math.maxInt(u32);
1879 
1880 pub fn planRelinkFromInputChanges(input_changes: InputChanges) RelinkPlan {
1881     return planRelinkFromInputChangesWithContributions(input_changes, &.{});
1882 }
1883 
1884 pub fn replacementContributionsFromImage(
1885     allocator: Allocator,
1886     image: []const u8,
1887     manifest: Manifest,
1888     input_changes: InputChanges,
1889 ) ReplacementExtractError![]ReplacementContribution {
1890     if (input_changes.summary.changed == 0 or manifest.contributions.len == 0) return &.{};
1891     if (input_changes.summary.changed <= sparse_replacement_extraction_change_limit) {
1892         return try replacementContributionsFromImageSparse(allocator, image, manifest, input_changes);
1893     }
1894 
1895     const current_change_indexes = try currentChangeIndexesAlloc(allocator, input_changes);
1896     defer if (current_change_indexes.len != 0) allocator.free(current_change_indexes);
1897 
1898     const replacement_count = countChangedInputContributions(manifest, input_changes, current_change_indexes);
1899     if (replacement_count == 0) return &.{};
1900 
1901     const replacements = try allocator.alloc(ReplacementContribution, replacement_count);
1902     errdefer allocator.free(replacements);
1903 
1904     var replacement_index: usize = 0;
1905     for (manifest.contributions) |contribution| {
1906         const current_index = std.math.cast(usize, contribution.input_index) orelse continue;
1907         const change = changeForCurrentInput(input_changes, current_change_indexes, current_index) orelse continue;
1908         if (change.kind != .changed) continue;
1909         const recorded_index = change.recorded_index orelse continue;
1910         replacements[replacement_index] = .{
1911             .input_name = manifest.string(contribution.input_name_id),
1912             .input_index = recorded_index,
1913             .kind = contribution.kind,
1914             .name = manifest.string(contribution.name_id),
1915             .ordinal = contribution.ordinal,
1916             .size = contribution.size,
1917             .alignment = contribution.alignment,
1918             .output_section_name = manifest.string(contribution.output_section_name_id),
1919             .address = contribution.address,
1920             .file_offset = contribution.file_offset,
1921             .reserved_size = contribution.reserved_size,
1922             .payload = try contributionPayload(image, contribution),
1923         };
1924         replacement_index += 1;
1925     }
1926     return replacements;
1927 }
1928 
1929 const ChangedCurrentInput = struct {
1930     current_index: usize,
1931     recorded_index: usize,
1932 };
1933 
1934 fn replacementContributionsFromImageSparse(
1935     allocator: Allocator,
1936     image: []const u8,
1937     manifest: Manifest,
1938     input_changes: InputChanges,
1939 ) ReplacementExtractError![]ReplacementContribution {
1940     var changed_current_inputs_storage: [sparse_replacement_extraction_change_limit]ChangedCurrentInput = undefined;
1941     var changed_current_input_count: usize = 0;
1942     for (input_changes.changes) |change| {
1943         if (change.kind != .changed) continue;
1944         const current_index = change.current_index orelse continue;
1945         const recorded_index = change.recorded_index orelse continue;
1946         changed_current_inputs_storage[changed_current_input_count] = .{
1947             .current_index = current_index,
1948             .recorded_index = recorded_index,
1949         };
1950         changed_current_input_count += 1;
1951     }
1952     if (changed_current_input_count == 0) return &.{};
1953 
1954     const changed_current_inputs = changed_current_inputs_storage[0..changed_current_input_count];
1955     var replacements: std.ArrayListUnmanaged(ReplacementContribution) = .empty;
1956     errdefer replacements.deinit(allocator);
1957     try replacements.ensureTotalCapacity(allocator, @min(manifest.contributions.len, changed_current_inputs.len));
1958 
1959     for (manifest.contributions) |contribution| {
1960         const current_index = std.math.cast(usize, contribution.input_index) orelse continue;
1961         const changed_input = changedCurrentInputForContribution(changed_current_inputs, current_index) orelse continue;
1962         try replacements.append(allocator, .{
1963             .input_name = manifest.string(contribution.input_name_id),
1964             .input_index = changed_input.recorded_index,
1965             .kind = contribution.kind,
1966             .name = manifest.string(contribution.name_id),
1967             .ordinal = contribution.ordinal,
1968             .size = contribution.size,
1969             .alignment = contribution.alignment,
1970             .output_section_name = manifest.string(contribution.output_section_name_id),
1971             .address = contribution.address,
1972             .file_offset = contribution.file_offset,
1973             .reserved_size = contribution.reserved_size,
1974             .payload = try contributionPayload(image, contribution),
1975         });
1976     }
1977 
1978     if (replacements.items.len == 0) {
1979         replacements.deinit(allocator);
1980         return &.{};
1981     }
1982     return try replacements.toOwnedSlice(allocator);
1983 }
1984 
1985 fn changedCurrentInputForContribution(
1986     changed_current_inputs: []const ChangedCurrentInput,
1987     current_index: usize,
1988 ) ?ChangedCurrentInput {
1989     for (changed_current_inputs) |changed_input| {
1990         if (changed_input.current_index == current_index) return changed_input;
1991     }
1992     return null;
1993 }
1994 
1995 fn currentChangeIndexesAlloc(
1996     allocator: Allocator,
1997     input_changes: InputChanges,
1998 ) Allocator.Error![]?usize {
1999     var max_current_index: ?usize = null;
2000     for (input_changes.changes) |change| {
2001         const current_index = change.current_index orelse continue;
2002         if (max_current_index == null or current_index > max_current_index.?) max_current_index = current_index;
2003     }
2004 
2005     const index_count = if (max_current_index) |current_index| current_index + 1 else return &.{};
2006     const current_change_indexes = try allocator.alloc(?usize, index_count);
2007     @memset(current_change_indexes, null);
2008     for (input_changes.changes, 0..) |change, change_index| {
2009         const current_index = change.current_index orelse continue;
2010         current_change_indexes[current_index] = change_index;
2011     }
2012     return current_change_indexes;
2013 }
2014 
2015 fn planRelinkFromInputChangesWithContributions(
2016     input_changes: InputChanges,
2017     input_contributions: []const InputContributionSummary,
2018 ) RelinkPlan {
2019     if (inputOrderDriftChangeIndex(input_changes)) |change_index| {
2020         return .{
2021             .decision = .full_link,
2022             .blocker = .input_reordered,
2023             .blocking_change_index = change_index,
2024             .input_summary = input_changes.summary,
2025             .affected_contributions = contributionSummaryForRecordedInput(input_contributions, input_changes.changes[change_index].recorded_index),
2026         };
2027     }
2028 
2029     if (input_changes.allUnchanged()) {
2030         return .{
2031             .decision = .reuse_output,
2032             .input_summary = input_changes.summary,
2033         };
2034     }
2035 
2036     for (input_changes.changes, 0..) |change, change_index| {
2037         const blocker: RelinkBlocker = switch (change.kind) {
2038             .unchanged => continue,
2039             .changed => .input_changed,
2040             .added => .input_added,
2041             .removed => .input_removed,
2042         };
2043         const affected_contributions = contributionSummaryForRecordedInput(input_contributions, change.recorded_index);
2044         return .{
2045             .decision = .full_link,
2046             .blocker = blocker,
2047             .blocking_change_index = change_index,
2048             .input_summary = input_changes.summary,
2049             .affected_contributions = affected_contributions,
2050         };
2051     }
2052     return .{
2053         .decision = .reuse_output,
2054         .input_summary = input_changes.summary,
2055     };
2056 }
2057 
2058 fn contributionSummaryForRecordedInput(
2059     input_contributions: []const InputContributionSummary,
2060     recorded_index: ?usize,
2061 ) InputContributionSummary {
2062     const index = recorded_index orelse return .{};
2063     if (index >= input_contributions.len) return .{};
2064     return input_contributions[index];
2065 }
2066 
2067 fn countChangedInputContributions(
2068     manifest: Manifest,
2069     input_changes: InputChanges,
2070     current_change_indexes: []const ?usize,
2071 ) usize {
2072     var count: usize = 0;
2073     for (manifest.contributions) |contribution| {
2074         const current_index = std.math.cast(usize, contribution.input_index) orelse continue;
2075         const change = changeForCurrentInput(input_changes, current_change_indexes, current_index) orelse continue;
2076         if (change.kind == .changed and change.recorded_index != null) count += 1;
2077     }
2078     return count;
2079 }
2080 
2081 fn contributionPayload(
2082     image: []const u8,
2083     contribution: ContributionRecord,
2084 ) error{PatchRangeOutOfBounds}![]const u8 {
2085     const size = std.math.cast(usize, contribution.file_size) orelse return error.PatchRangeOutOfBounds;
2086     if (size == 0) return image[0..0];
2087     const start = std.math.cast(usize, contribution.file_offset) orelse return error.PatchRangeOutOfBounds;
2088     if (start > image.len or size > image.len - start) return error.PatchRangeOutOfBounds;
2089     return image[start..][0..size];
2090 }
2091 
2092 fn cloneCandidateDiscardedContributions(
2093     allocator: Allocator,
2094     strings: *Strings,
2095     input_changes: InputChanges,
2096     candidate_manifest: Manifest,
2097 ) RelinkManifestUpdateError![]DiscardedContributionRecord {
2098     const candidate_records = candidate_manifest.discarded_contributions;
2099     if (candidate_records.len == 0) return &.{};
2100 
2101     const discarded_contributions = try allocator.alloc(DiscardedContributionRecord, candidate_records.len);
2102     errdefer allocator.free(discarded_contributions);
2103 
2104     for (candidate_records, 0..) |candidate, index| {
2105         const current_index = std.math.cast(usize, candidate.input_index) orelse return error.SectionLayoutChanged;
2106         const input_index = recordedIndexForCurrentInput(input_changes, current_index) orelse return error.SectionLayoutChanged;
2107         discarded_contributions[index] = candidate;
2108         discarded_contributions[index].input_index = input_index;
2109         discarded_contributions[index].input_name_id = try strings.intern(allocator, candidate_manifest.string(candidate.input_name_id));
2110         discarded_contributions[index].name_id = try strings.intern(allocator, candidate_manifest.string(candidate.name_id));
2111     }
2112 
2113     return discarded_contributions;
2114 }
2115 
2116 fn cloneArchiveMemberRecords(
2117     allocator: Allocator,
2118     strings: *Strings,
2119     input_changes: InputChanges,
2120     candidate_manifest: Manifest,
2121 ) RelinkManifestUpdateError![]ArchiveMemberRecord {
2122     const candidate_members = candidate_manifest.archive_members;
2123     if (candidate_members.len == 0) return &.{};
2124 
2125     const archive_members = try allocator.alloc(ArchiveMemberRecord, candidate_members.len);
2126     errdefer allocator.free(archive_members);
2127 
2128     for (candidate_members, 0..) |candidate, index| {
2129         const current_index = std.math.cast(usize, candidate.input_index) orelse return error.SectionLayoutChanged;
2130         const input_index = recordedIndexForCurrentInput(input_changes, current_index) orelse return error.SectionLayoutChanged;
2131         archive_members[index] = candidate;
2132         archive_members[index].input_index = input_index;
2133         archive_members[index].name_id = try strings.intern(allocator, candidate_manifest.string(candidate.name_id));
2134     }
2135 
2136     return archive_members;
2137 }
2138 
2139 fn cloneGotEntryRecords(
2140     allocator: Allocator,
2141     strings: *Strings,
2142     input_changes: InputChanges,
2143     candidate_manifest: Manifest,
2144 ) RelinkManifestUpdateError![]GotEntryRecord {
2145     const candidate_entries = candidate_manifest.got_entries;
2146     if (candidate_entries.len == 0) return &.{};
2147 
2148     const got_entries = try allocator.alloc(GotEntryRecord, candidate_entries.len);
2149     errdefer allocator.free(got_entries);
2150 
2151     for (candidate_entries, 0..) |candidate, index| {
2152         const current_index = std.math.cast(usize, candidate.input_index) orelse return error.SectionLayoutChanged;
2153         const input_index = recordedIndexForCurrentInput(input_changes, current_index) orelse return error.SectionLayoutChanged;
2154         got_entries[index] = candidate;
2155         got_entries[index].input_index = input_index;
2156         got_entries[index].input_name_id = try strings.intern(allocator, candidate_manifest.string(candidate.input_name_id));
2157         got_entries[index].name_id = try strings.intern(allocator, candidate_manifest.string(candidate.name_id));
2158     }
2159 
2160     return got_entries;
2161 }
2162 
2163 fn cloneMergePieceRecords(
2164     allocator: Allocator,
2165     strings: *Strings,
2166     input_changes: InputChanges,
2167     candidate_manifest: Manifest,
2168 ) RelinkManifestUpdateError![]MergePieceRecord {
2169     const candidate_pieces = candidate_manifest.merge_pieces;
2170     if (candidate_pieces.len == 0) return &.{};
2171 
2172     const merge_pieces = try allocator.alloc(MergePieceRecord, candidate_pieces.len);
2173     errdefer allocator.free(merge_pieces);
2174 
2175     for (candidate_pieces, 0..) |candidate, index| {
2176         const current_index = std.math.cast(usize, candidate.input_index) orelse return error.SectionLayoutChanged;
2177         const input_index = recordedIndexForCurrentInput(input_changes, current_index) orelse return error.SectionLayoutChanged;
2178         merge_pieces[index] = candidate;
2179         merge_pieces[index].input_index = input_index;
2180         merge_pieces[index].input_name_id = try strings.intern(allocator, candidate_manifest.string(candidate.input_name_id));
2181     }
2182 
2183     return merge_pieces;
2184 }
2185 
2186 fn cloneExternalTargetRecords(
2187     allocator: Allocator,
2188     strings: *Strings,
2189     candidate_manifest: Manifest,
2190 ) Allocator.Error![]ExternalTargetRecord {
2191     const candidate_targets = candidate_manifest.external_targets;
2192     if (candidate_targets.len == 0) return &.{};
2193 
2194     const external_targets = try allocator.alloc(ExternalTargetRecord, candidate_targets.len);
2195     errdefer allocator.free(external_targets);
2196 
2197     for (candidate_targets, 0..) |candidate, index| {
2198         external_targets[index] = candidate;
2199         external_targets[index].name_id = try strings.intern(allocator, candidate_manifest.string(candidate.name_id));
2200     }
2201 
2202     return external_targets;
2203 }
2204 
2205 fn addInputContributionSummary(total: *InputContributionSummary, next: InputContributionSummary) void {
2206     total.retained += next.retained;
2207     total.discarded += next.discarded;
2208     total.retained_size += next.retained_size;
2209     total.discarded_size += next.discarded_size;
2210 }
2211 
2212 fn countRetainedReplacementsForInput(
2213     replacements: []const ReplacementContribution,
2214     recorded_index: usize,
2215 ) usize {
2216     var count: usize = 0;
2217     for (replacements) |replacement| {
2218         if (replacement.input_index == recorded_index) count += 1;
2219     }
2220     return count;
2221 }
2222 
2223 fn replacementIndexOutsideChangedInputs(
2224     input_changes: InputChanges,
2225     replacements: []const ReplacementContribution,
2226 ) ?usize {
2227     var cached_input_index: ?usize = null;
2228     var cached_change_index: ?usize = null;
2229     for (replacements, 0..) |replacement, replacement_index| {
2230         if (cached_input_index != replacement.input_index) {
2231             cached_input_index = replacement.input_index;
2232             cached_change_index = changeIndexForRecordedInput(input_changes, replacement.input_index);
2233         }
2234         const change_index = cached_change_index orelse return replacement_index;
2235         if (input_changes.changes[change_index].kind != .changed) return replacement_index;
2236     }
2237     return null;
2238 }
2239 
2240 fn changeForCurrentInput(
2241     input_changes: InputChanges,
2242     current_change_indexes: []const ?usize,
2243     current_index: usize,
2244 ) ?InputChange {
2245     if (current_index >= current_change_indexes.len) return null;
2246     const change_index = current_change_indexes[current_index] orelse return null;
2247     if (change_index >= input_changes.changes.len) return null;
2248     return input_changes.changes[change_index];
2249 }
2250 
2251 fn changeIndexForRecordedInput(input_changes: InputChanges, recorded_index: usize) ?usize {
2252     for (input_changes.changes, 0..) |change, change_index| {
2253         if (change.recorded_index == recorded_index) return change_index;
2254     }
2255     return null;
2256 }
2257 
2258 fn inputOrderDriftChangeIndex(input_changes: InputChanges) ?usize {
2259     if (input_changes.summary.added != 0 or input_changes.summary.removed != 0) return null;
2260     for (input_changes.changes, 0..) |change, change_index| {
2261         const recorded_index = change.recorded_index orelse continue;
2262         const current_index = change.current_index orelse continue;
2263         if (recorded_index != current_index) return change_index;
2264     }
2265     return null;
2266 }
2267 
2268 fn recordedIndexForCurrentInput(input_changes: InputChanges, current_index: usize) ?usize {
2269     for (input_changes.changes) |change| {
2270         if (change.current_index != current_index) continue;
2271         return change.recorded_index;
2272     }
2273     return null;
2274 }
2275 
2276 fn relinkBlockerForPatchBlocker(blocker: ?PatchBlocker) ?RelinkBlocker {
2277     const patch_blocker = blocker orelse return null;
2278     return switch (patch_blocker) {
2279         .missing_contribution => .replacement_missing,
2280         .unpatchable_contribution => .replacement_unpatchable,
2281         .layout_changed => .replacement_layout_changed,
2282         .grew_past_reserve => .replacement_grew_past_reserve,
2283         .alignment_increased => .replacement_alignment_increased,
2284     };
2285 }
2286 
2287 pub const Builder = struct {
2288     allocator: Allocator,
2289     target: model.Target,
2290     output_kind: model.OutputKind,
2291     entry_symbol_id: u32,
2292     image_base: u64,
2293     page_size: u64,
2294     gc_sections: bool,
2295     icf: model.IcfMode,
2296     strip_debug: bool,
2297     build_id: model.BuildIdMode,
2298     input_hashes_recorded: bool,
2299     contribution_records_enabled: bool,
2300     inputs_read_at_ns: i64,
2301     strings: Strings = .{},
2302     inputs: std.ArrayListUnmanaged(InputRecord) = .empty,
2303     sections: std.ArrayListUnmanaged(SectionRecord) = .empty,
2304     contributions: std.ArrayListUnmanaged(ContributionRecord) = .empty,
2305     discarded_contributions: std.ArrayListUnmanaged(DiscardedContributionRecord) = .empty,
2306     external_targets: std.ArrayListUnmanaged(ExternalTargetRecord) = .empty,
2307     archive_members: std.ArrayListUnmanaged(ArchiveMemberRecord) = .empty,
2308     got_entries: std.ArrayListUnmanaged(GotEntryRecord) = .empty,
2309     merge_pieces: std.ArrayListUnmanaged(MergePieceRecord) = .empty,
2310 
2311     pub fn init(allocator: Allocator, options: model.LinkOptions) Allocator.Error!Builder {
2312         const incremental_records_enabled = options.incremental_mode != .off;
2313         var builder = Builder{
2314             .allocator = allocator,
2315             .target = options.target,
2316             .output_kind = options.output_kind,
2317             .entry_symbol_id = 0,
2318             .image_base = options.image_base,
2319             .page_size = options.page_size,
2320             .gc_sections = options.gc_sections,
2321             .icf = options.icf,
2322             .strip_debug = options.strip_debug,
2323             .build_id = options.build_id,
2324             .input_hashes_recorded = incremental_records_enabled,
2325             .contribution_records_enabled = incremental_records_enabled,
2326             .inputs_read_at_ns = options.inputs_read_at_ns,
2327         };
2328         errdefer builder.deinit();
2329         builder.entry_symbol_id = try builder.strings.intern(allocator, options.entry_symbol);
2330         return builder;
2331     }
2332 
2333     pub fn recordsContributions(self: Builder) bool {
2334         return self.contribution_records_enabled;
2335     }
2336 
2337     pub fn deinit(self: *Builder) void {
2338         self.strings.deinit(self.allocator);
2339         self.inputs.deinit(self.allocator);
2340         self.sections.deinit(self.allocator);
2341         self.contributions.deinit(self.allocator);
2342         self.discarded_contributions.deinit(self.allocator);
2343         self.external_targets.deinit(self.allocator);
2344         self.archive_members.deinit(self.allocator);
2345         self.got_entries.deinit(self.allocator);
2346         self.merge_pieces.deinit(self.allocator);
2347         self.* = undefined;
2348     }
2349 
2350     pub fn addInput(self: *Builder, input: model.Input) Allocator.Error!void {
2351         const hash = if (self.input_hashes_recorded) hashBytes(input.bytes) else 0;
2352         const identity = input.identity orelse model.InputIdentity{ .mtime_ns = 0, .inode = 0 };
2353         try self.inputs.append(self.allocator, .{
2354             .name_id = try self.strings.intern(self.allocator, input.name),
2355             .size = input.bytes.len,
2356             .hash = hash,
2357             .mtime_ns = identity.mtime_ns,
2358             .inode = identity.inode,
2359             .identity_recorded = input.identity != null,
2360             .link_hash = hash,
2361         });
2362     }
2363 
2364     pub fn setInputLinkHash(self: *Builder, input_index: usize, link_hash: u64) void {
2365         if (!self.input_hashes_recorded) return;
2366         if (input_index >= self.inputs.items.len) return;
2367         self.inputs.items[input_index].link_hash = link_hash;
2368     }
2369 
2370     pub fn setInputSelectionHash(self: *Builder, input_index: usize, selection_hash: u64) void {
2371         if (!self.input_hashes_recorded) return;
2372         if (input_index >= self.inputs.items.len) return;
2373         self.inputs.items[input_index].selection_hash = selection_hash;
2374     }
2375 
2376     pub fn addArchiveMember(
2377         self: *Builder,
2378         input_index: usize,
2379         name: []const u8,
2380         hash: u64,
2381         link_hash: u64,
2382         selected: bool,
2383     ) Allocator.Error!void {
2384         if (!self.contribution_records_enabled) return;
2385 
2386         try self.archive_members.append(self.allocator, .{
2387             .input_index = input_index,
2388             .name_id = try self.strings.intern(self.allocator, name),
2389             .hash = hash,
2390             .link_hash = link_hash,
2391             .selected = selected,
2392         });
2393     }
2394 
2395     pub fn addSection(
2396         self: *Builder,
2397         name: []const u8,
2398         address: u64,
2399         file_offset: u64,
2400         size: u64,
2401         reserved_size: u64,
2402         alignment: u64,
2403     ) Allocator.Error!void {
2404         try self.sections.append(self.allocator, .{
2405             .name_id = try self.strings.intern(self.allocator, name),
2406             .address = address,
2407             .file_offset = file_offset,
2408             .size = size,
2409             .reserved_size = reserved_size,
2410             .alignment = alignment,
2411         });
2412     }
2413 
2414     pub fn addContribution(
2415         self: *Builder,
2416         input_name: []const u8,
2417         input_index: usize,
2418         kind: ContributionKind,
2419         name: []const u8,
2420         ordinal: u32,
2421         output_section_name: []const u8,
2422         address: u64,
2423         file_offset: u64,
2424         size: u64,
2425         reserved_size: u64,
2426         alignment: u64,
2427     ) Allocator.Error!void {
2428         return try self.addContributionWithFileSize(
2429             input_name,
2430             input_index,
2431             kind,
2432             name,
2433             ordinal,
2434             output_section_name,
2435             address,
2436             file_offset,
2437             size,
2438             size,
2439             reserved_size,
2440             alignment,
2441         );
2442     }
2443 
2444     pub fn addContributionWithFileSize(
2445         self: *Builder,
2446         input_name: []const u8,
2447         input_index: usize,
2448         kind: ContributionKind,
2449         name: []const u8,
2450         ordinal: u32,
2451         output_section_name: []const u8,
2452         address: u64,
2453         file_offset: u64,
2454         size: u64,
2455         file_size: u64,
2456         reserved_size: u64,
2457         alignment: u64,
2458     ) Allocator.Error!void {
2459         if (!self.contribution_records_enabled) return;
2460 
2461         try self.contributions.append(self.allocator, .{
2462             .input_name_id = try self.strings.intern(self.allocator, input_name),
2463             .input_index = input_index,
2464             .kind = kind,
2465             .name_id = try self.strings.intern(self.allocator, name),
2466             .ordinal = ordinal,
2467             .output_section_name_id = try self.strings.intern(self.allocator, output_section_name),
2468             .address = address,
2469             .file_offset = file_offset,
2470             .size = size,
2471             .file_size = file_size,
2472             .reserved_size = reserved_size,
2473             .alignment = alignment,
2474         });
2475     }
2476 
2477     pub fn addDiscardedContribution(
2478         self: *Builder,
2479         input_name: []const u8,
2480         input_index: usize,
2481         name: []const u8,
2482         ordinal: u32,
2483         reason: DiscardReason,
2484         size: u64,
2485         alignment: u64,
2486     ) Allocator.Error!void {
2487         if (!self.contribution_records_enabled) return;
2488 
2489         try self.discarded_contributions.append(self.allocator, .{
2490             .input_name_id = try self.strings.intern(self.allocator, input_name),
2491             .input_index = input_index,
2492             .name_id = try self.strings.intern(self.allocator, name),
2493             .ordinal = ordinal,
2494             .reason = reason,
2495             .size = size,
2496             .alignment = alignment,
2497         });
2498     }
2499 
2500     pub fn addExternalTarget(
2501         self: *Builder,
2502         name: []const u8,
2503         resolved_address: i128,
2504         size: u64,
2505     ) Allocator.Error!void {
2506         if (!self.contribution_records_enabled) return;
2507 
2508         const name_id = try self.strings.intern(self.allocator, name);
2509         const record = ExternalTargetRecord.fromResolved(name_id, resolved_address, size) orelse return;
2510         try self.external_targets.append(self.allocator, record);
2511     }
2512 
2513     pub fn addGotEntry(
2514         self: *Builder,
2515         input_index: usize,
2516         input_name: []const u8,
2517         ordinal: u32,
2518         name: []const u8,
2519         address: u64,
2520     ) Allocator.Error!void {
2521         if (!self.contribution_records_enabled) return;
2522 
2523         try self.got_entries.append(self.allocator, .{
2524             .input_index = input_index,
2525             .input_name_id = try self.strings.intern(self.allocator, input_name),
2526             .ordinal = ordinal,
2527             .name_id = try self.strings.intern(self.allocator, name),
2528             .address = address,
2529         });
2530     }
2531 
2532     pub fn addMergePiece(
2533         self: *Builder,
2534         input_index: usize,
2535         input_name: []const u8,
2536         ordinal: u32,
2537         input_offset: u64,
2538         size: u64,
2539         address: u64,
2540     ) Allocator.Error!void {
2541         if (!self.contribution_records_enabled) return;
2542 
2543         try self.merge_pieces.append(self.allocator, .{
2544             .input_index = input_index,
2545             .input_name_id = try self.strings.intern(self.allocator, input_name),
2546             .ordinal = ordinal,
2547             .input_offset = input_offset,
2548             .size = size,
2549             .address = address,
2550         });
2551     }
2552 
2553     pub fn finish(self: *Builder) Allocator.Error!Manifest {
2554         var strings = self.strings;
2555         self.strings = .{};
2556         errdefer strings.deinit(self.allocator);
2557         strings.ids.deinit(self.allocator);
2558         strings.ids = .empty;
2559         return .{
2560             .target = self.target,
2561             .output_kind = self.output_kind,
2562             .entry_symbol_id = self.entry_symbol_id,
2563             .image_base = self.image_base,
2564             .page_size = self.page_size,
2565             .gc_sections = self.gc_sections,
2566             .icf = self.icf,
2567             .strip_debug = self.strip_debug,
2568             .build_id = self.build_id,
2569             .input_hashes_recorded = self.input_hashes_recorded,
2570             .inputs_read_at_ns = self.inputs_read_at_ns,
2571             .strings = strings,
2572             .inputs = try self.inputs.toOwnedSlice(self.allocator),
2573             .sections = try self.sections.toOwnedSlice(self.allocator),
2574             .contributions = try self.contributions.toOwnedSlice(self.allocator),
2575             .discarded_contributions = try self.discarded_contributions.toOwnedSlice(self.allocator),
2576             .external_targets = try self.external_targets.toOwnedSlice(self.allocator),
2577             .archive_members = try self.archive_members.toOwnedSlice(self.allocator),
2578             .got_entries = try self.got_entries.toOwnedSlice(self.allocator),
2579             .merge_pieces = try self.merge_pieces.toOwnedSlice(self.allocator),
2580             .owned = .{
2581                 .inputs = true,
2582                 .sections = true,
2583                 .contributions = true,
2584                 .discarded_contributions = true,
2585                 .external_targets = true,
2586                 .archive_members = true,
2587                 .got_entries = true,
2588                 .merge_pieces = true,
2589             },
2590         };
2591     }
2592 };
2593 
2594 pub fn hashBytes(bytes: []const u8) u64 {
2595     return std.hash.Wyhash.hash(0x544c44, bytes);
2596 }
2597 
2598 fn findUnmatchedInput(
2599     inputs: []const model.Input,
2600     matched: []const bool,
2601     name: []const u8,
2602 ) ?usize {
2603     for (inputs, matched, 0..) |input, already_matched, index| {
2604         if (already_matched) continue;
2605         if (std.mem.eql(u8, input.name, name)) return index;
2606     }
2607     return null;
2608 }
2609 
2610 fn buildInputContributionSummaries(
2611     allocator: Allocator,
2612     manifest: Manifest,
2613 ) Allocator.Error![]InputContributionSummary {
2614     var input_count = manifest.inputs.len;
2615     for (manifest.contributions) |contribution| {
2616         input_count = @max(input_count, contribution.input_index + 1);
2617     }
2618     for (manifest.discarded_contributions) |contribution| {
2619         input_count = @max(input_count, contribution.input_index + 1);
2620     }
2621     if (input_count == 0) return &.{};
2622 
2623     const summaries = try allocator.alloc(InputContributionSummary, input_count);
2624     @memset(summaries, .{});
2625 
2626     for (manifest.contributions) |contribution| {
2627         summaries[contribution.input_index].retained += 1;
2628         summaries[contribution.input_index].retained_size += contribution.size;
2629     }
2630     for (manifest.discarded_contributions) |contribution| {
2631         summaries[contribution.input_index].discarded += 1;
2632         summaries[contribution.input_index].discarded_size += contribution.size;
2633     }
2634     return summaries;
2635 }
2636 
2637 const TestInputClassification = struct {
2638     owner: TestInputChangeOwner,
2639     changes: InputChanges,
2640 
2641     fn deinit(self: *TestInputClassification, allocator: Allocator) void {
2642         self.owner.deinit(allocator);
2643     }
2644 };
2645 
2646 const TestInputChangeOwner = struct {
2647     bytes: InputChangeStorage.Storage,
2648     storage: InputChangeStorage,
2649 
2650     fn init(allocator: Allocator, limits: InputChangeStorage.Limits) !TestInputChangeOwner {
2651         const capacity = try InputChangeStorage.Capacity.derive(limits);
2652         const bytes = try allocator.alignedAlloc(
2653             u8,
2654             .fromByteUnits(InputChangeStorage.storage_alignment),
2655             capacity.storage_bytes,
2656         );
2657         errdefer allocator.free(bytes);
2658         return .{
2659             .bytes = bytes,
2660             .storage = try InputChangeStorage.init(bytes, limits),
2661         };
2662     }
2663 
2664     fn deinit(self: *TestInputChangeOwner, allocator: Allocator) void {
2665         const bytes = self.storage.deinit();
2666         std.debug.assert(bytes.ptr == self.bytes.ptr);
2667         std.debug.assert(bytes.len == self.bytes.len);
2668         allocator.free(bytes);
2669     }
2670 };
2671 
2672 fn classifyTestInputs(
2673     allocator: Allocator,
2674     manifest: Manifest,
2675     inputs: []const model.Input,
2676 ) !TestInputClassification {
2677     var owner = try TestInputChangeOwner.init(
2678         allocator,
2679         InputChangeStorage.Limits.inspect(RecordedInputs.fromManifest(&manifest), inputs),
2680     );
2681     errdefer owner.deinit(allocator);
2682     owner.storage.activate();
2683     const changes = try owner.storage.classify(RecordedInputs.fromManifest(&manifest), inputs);
2684     return .{
2685         .changes = changes,
2686         .owner = owner,
2687     };
2688 }
2689 
2690 fn initTestInputChangeStorage(
2691     allocator: Allocator,
2692     manifest: Manifest,
2693     inputs: []const model.Input,
2694 ) !TestInputChangeOwner {
2695     var owner = try TestInputChangeOwner.init(
2696         allocator,
2697         InputChangeStorage.Limits.inspect(RecordedInputs.fromManifest(&manifest), inputs),
2698     );
2699     owner.storage.activate();
2700     return owner;
2701 }
2702 
2703 fn planInputRelinkForTest(
2704     state: *const PreparedState,
2705     allocator: Allocator,
2706     options: model.LinkOptions,
2707     inputs: []const model.Input,
2708 ) !RelinkPlan {
2709     var storage = try initTestInputChangeStorage(
2710         allocator,
2711         state.manifest,
2712         inputs,
2713     );
2714     defer storage.deinit(allocator);
2715     return try state.planInputRelink(&storage.storage, options, inputs);
2716 }
2717 
2718 fn planChangedInputRelinkForTest(
2719     state: *const PreparedState,
2720     allocator: Allocator,
2721     options: model.LinkOptions,
2722     inputs: []const model.Input,
2723     replacements: []const ReplacementContribution,
2724 ) !RelinkPlan {
2725     var storage = try initTestInputChangeStorage(
2726         allocator,
2727         state.manifest,
2728         inputs,
2729     );
2730     defer storage.deinit(allocator);
2731     return try state.planChangedInputRelink(
2732         &storage.storage,
2733         options,
2734         inputs,
2735         replacements,
2736     );
2737 }
2738 
2739 fn applyChangedInputRelinkForTest(
2740     state: *const PreparedState,
2741     allocator: Allocator,
2742     image: []u8,
2743     options: model.LinkOptions,
2744     inputs: []const model.Input,
2745     replacements: []const ReplacementContribution,
2746 ) !RelinkApplication {
2747     var storage = try initTestInputChangeStorage(
2748         allocator,
2749         state.manifest,
2750         inputs,
2751     );
2752     defer storage.deinit(allocator);
2753     return try state.applyChangedInputRelink(
2754         &storage.storage,
2755         image,
2756         options,
2757         inputs,
2758         replacements,
2759     );
2760 }
2761 
2762 fn applyChangedInputRelinkFromCandidateForTest(
2763     state: *const PreparedState,
2764     allocator: Allocator,
2765     image: []u8,
2766     options: model.LinkOptions,
2767     inputs: []const model.Input,
2768     candidate_image: []const u8,
2769     candidate_manifest: Manifest,
2770 ) !RelinkApplication {
2771     var storage = try initTestInputChangeStorage(
2772         allocator,
2773         state.manifest,
2774         inputs,
2775     );
2776     defer storage.deinit(allocator);
2777     return try state.applyChangedInputRelinkFromCandidate(
2778         allocator,
2779         &storage.storage,
2780         image,
2781         options,
2782         inputs,
2783         candidate_image,
2784         candidate_manifest,
2785     );
2786 }
2787 
2788 fn updateManifestForCandidateRelinkForTest(
2789     state: *PreparedState,
2790     allocator: Allocator,
2791     inputs: []const model.Input,
2792     replacements: []const ReplacementContribution,
2793     candidate_manifest: Manifest,
2794 ) !void {
2795     var storage = try initTestInputChangeStorage(
2796         allocator,
2797         state.manifest,
2798         inputs,
2799     );
2800     defer storage.deinit(allocator);
2801     try state.updateManifestForCandidateRelink(
2802         allocator,
2803         &storage.storage,
2804         inputs,
2805         replacements,
2806         candidate_manifest,
2807     );
2808 }
2809 
2810 fn repeatedInputManifest(
2811     allocator: Allocator,
2812     count: usize,
2813     name: []const u8,
2814     bytes: []const u8,
2815 ) !Manifest {
2816     var builder = try Builder.init(allocator, .{});
2817     defer builder.deinit();
2818     for (0..count) |_| try builder.addInput(.{ .name = name, .bytes = bytes });
2819     return try builder.finish();
2820 }
2821 
2822 const InputChangeCapacityCase = struct {
2823     limits: InputChangeStorage.Limits,
2824     changes: usize,
2825     current: usize,
2826 };
2827 
2828 const InputChangeInitFailure = struct {
2829     fn run(allocator: Allocator) !void {
2830         var owner = try TestInputChangeOwner.init(allocator, .{
2831             .recorded_inputs = 31,
2832             .current_inputs = 37,
2833         });
2834         owner.storage.activate();
2835         owner.deinit(allocator);
2836     }
2837 };
2838 
2839 fn modelInputChangeCapacity(
2840     limits: InputChangeStorage.Limits,
2841 ) InputChangeStorage.Capacity.DeriveError!InputChangeStorage.Capacity {
2842     const recorded: u128 = limits.recorded_inputs;
2843     const current: u128 = limits.current_inputs;
2844     if (current > std.math.maxInt(u32)) return error.CapacityOverflow;
2845     const changes = recorded + current;
2846     var name_slots: u128 = if (current == 0) 0 else 1;
2847     const minimum_name_slots = current * 2;
2848     var shifts: usize = 0;
2849     while (name_slots < minimum_name_slots) : (shifts += 1) {
2850         std.debug.assert(shifts <= @bitSizeOf(usize));
2851         name_slots *= 2;
2852     }
2853     const changes_offset = modelInputChangeOffset(0, @alignOf(InputChange));
2854     const changes_end = changes_offset + changes * @sizeOf(InputChange);
2855     const matched_offset = modelInputChangeOffset(changes_end, @alignOf(bool));
2856     const matched_end = matched_offset + current * @sizeOf(bool);
2857     const links_offset = modelInputChangeOffset(matched_end, @alignOf(u32));
2858     const links_end = links_offset + current * @sizeOf(u32);
2859     const names_offset = modelInputChangeOffset(links_end, @alignOf(InputChangeNameEntry));
2860     const storage_bytes = names_offset + name_slots * @sizeOf(InputChangeNameEntry);
2861     if (changes > std.math.maxInt(usize) or
2862         name_slots > std.math.maxInt(usize) or
2863         changes_offset > std.math.maxInt(usize) or
2864         matched_offset > std.math.maxInt(usize) or
2865         links_offset > std.math.maxInt(usize) or
2866         names_offset > std.math.maxInt(usize) or
2867         storage_bytes > std.math.maxInt(usize))
2868     {
2869         return error.CapacityOverflow;
2870     }
2871     return .{
2872         .recorded_inputs = limits.recorded_inputs,
2873         .current_inputs = limits.current_inputs,
2874         .change_records = @intCast(changes),
2875         .matched_flags = limits.current_inputs,
2876         .current_links = limits.current_inputs,
2877         .name_slots = @intCast(name_slots),
2878         .changes_offset = @intCast(changes_offset),
2879         .matched_offset = @intCast(matched_offset),
2880         .links_offset = @intCast(links_offset),
2881         .names_offset = @intCast(names_offset),
2882         .storage_bytes = @intCast(storage_bytes),
2883     };
2884 }
2885 
2886 fn modelInputChangeOffset(offset: u128, alignment: usize) u128 {
2887     std.debug.assert(alignment != 0);
2888     std.debug.assert(std.math.isPowerOfTwo(alignment));
2889     const requested_mask: u128 = alignment - 1;
2890     return (offset + requested_mask) & ~requested_mask;
2891 }
2892 
2893 test "input change storage derives checked capacity from both input counts" {
2894     comptime {
2895         @stardustClaim(
2896             @import("alloc_phase").capacity.witness(InputChangeStorage, "tldr_input_change_capacity_capacity_model"),
2897             null,
2898             null,
2899             null,
2900             null,
2901             null,
2902             null,
2903         );
2904     }
2905     comptime {
2906         @stardustClaim(
2907             @import("alloc_phase").capacity.witness(InputChangeStorage, "tldr_input_change_capacity_overload"),
2908             null,
2909             null,
2910             null,
2911             null,
2912             null,
2913             null,
2914         );
2915     }
2916 
2917     const cases = [_]InputChangeCapacityCase{
2918         .{ .limits = .{ .recorded_inputs = 0, .current_inputs = 0 }, .changes = 0, .current = 0 },
2919         .{ .limits = .{ .recorded_inputs = 3, .current_inputs = 5 }, .changes = 8, .current = 5 },
2920         .{
2921             .limits = .{ .recorded_inputs = 21, .current_inputs = 13 },
2922             .changes = 34,
2923             .current = 13,
2924         },
2925     };
2926     for (cases) |case| {
2927         const actual = try InputChangeStorage.Capacity.derive(case.limits);
2928         const expected = try modelInputChangeCapacity(case.limits);
2929         try std.testing.expectEqual(expected, actual);
2930         try std.testing.expectEqual(case.limits.recorded_inputs, actual.recorded_inputs);
2931         try std.testing.expectEqual(case.limits.current_inputs, actual.current_inputs);
2932         try std.testing.expectEqual(case.changes, actual.change_records);
2933         try std.testing.expectEqual(case.current, actual.matched_flags);
2934         try std.testing.expectEqual(case.current, actual.current_links);
2935     }
2936 
2937     try std.testing.expectError(
2938         error.CapacityOverflow,
2939         InputChangeStorage.Capacity.derive(.{
2940             .recorded_inputs = std.math.maxInt(usize),
2941             .current_inputs = 1,
2942         }),
2943     );
2944     try std.testing.expectError(
2945         error.CapacityOverflow,
2946         InputChangeStorage.Capacity.derive(.{
2947             .recorded_inputs = 0,
2948             .current_inputs = std.math.maxInt(usize) / 2 + 1,
2949         }),
2950     );
2951 }
2952 
2953 test "input change storage acquisition OOM is retryable" {
2954     comptime {
2955         @stardustClaim(
2956             @import("alloc_phase").capacity.witness(InputChangeStorage, "tldr_input_change_oom_retry"),
2957             null,
2958             null,
2959             null,
2960             null,
2961             null,
2962             null,
2963         );
2964     }
2965 
2966     try std.testing.checkAllAllocationFailures(
2967         std.testing.allocator,
2968         InputChangeInitFailure.run,
2969         .{},
2970     );
2971 
2972     var failing = std.testing.FailingAllocator.init(
2973         std.testing.allocator,
2974         .{ .fail_index = 0 },
2975     );
2976     try std.testing.expectError(
2977         error.OutOfMemory,
2978         TestInputChangeOwner.init(failing.allocator(), .{
2979             .recorded_inputs = 31,
2980             .current_inputs = 37,
2981         }),
2982     );
2983     failing.fail_index = std.math.maxInt(usize);
2984     var owner = try TestInputChangeOwner.init(failing.allocator(), .{
2985         .recorded_inputs = 31,
2986         .current_inputs = 37,
2987     });
2988     owner.storage.activate();
2989     owner.deinit(failing.allocator());
2990 
2991     var counting = std.testing.FailingAllocator.init(std.testing.allocator, .{});
2992     const limits = InputChangeStorage.Limits{
2993         .recorded_inputs = 31,
2994         .current_inputs = 37,
2995     };
2996     const capacity = try InputChangeStorage.Capacity.derive(limits);
2997     const bytes = try counting.allocator().alignedAlloc(
2998         u8,
2999         .fromByteUnits(InputChangeStorage.storage_alignment),
3000         capacity.storage_bytes,
3001     );
3002     defer counting.allocator().free(bytes);
3003     try std.testing.expectEqual(@as(usize, 1), counting.allocations);
3004     try std.testing.expectEqual(capacity.storage_bytes, counting.allocated_bytes);
3005     const allocation_count = counting.allocations;
3006     var measured = try InputChangeStorage.init(bytes, limits);
3007     measured.activate();
3008     const returned = measured.deinit();
3009     try std.testing.expectEqual(bytes.ptr, returned.ptr);
3010     try std.testing.expectEqual(bytes.len, returned.len);
3011     try std.testing.expectEqual(allocation_count, counting.allocations);
3012 }
3013 
3014 test "input change storage accepts exact region and rejects one byte short" {
3015     comptime {
3016         @stardustClaim(
3017             @import("alloc_phase").capacity.witness(InputChangeStorage, "tldr_input_change_region"),
3018             null,
3019             null,
3020             null,
3021             null,
3022             null,
3023             null,
3024         );
3025     }
3026 
3027     const allocator = std.testing.allocator;
3028     const limits = InputChangeStorage.Limits{
3029         .recorded_inputs = 2,
3030         .current_inputs = 3,
3031     };
3032     const capacity = try InputChangeStorage.Capacity.derive(limits);
3033     const bytes = try allocator.alignedAlloc(
3034         u8,
3035         .fromByteUnits(InputChangeStorage.storage_alignment),
3036         capacity.storage_bytes,
3037     );
3038     defer allocator.free(bytes);
3039     const sentinel: u8 = 0xa5;
3040     @memset(bytes, sentinel);
3041     try std.testing.expectError(
3042         error.StorageTooShort,
3043         InputChangeStorage.init(bytes[0 .. bytes.len - 1], limits),
3044     );
3045     for (bytes) |byte| try std.testing.expectEqual(sentinel, byte);
3046 
3047     var storage = try InputChangeStorage.init(bytes, limits);
3048     storage.activate();
3049     const returned = storage.deinit();
3050     try std.testing.expectEqual(bytes.ptr, returned.ptr);
3051     try std.testing.expectEqual(bytes.len, returned.len);
3052 }
3053 
3054 test "input change storage accepts an empty finite job" {
3055     const allocator = std.testing.allocator;
3056     var builder = try Builder.init(allocator, .{});
3057     defer builder.deinit();
3058     var manifest = try builder.finish();
3059     defer manifest.deinit(allocator);
3060 
3061     var bytes: [0]u8 align(InputChangeStorage.storage_alignment) = .{};
3062     var storage = try InputChangeStorage.init(&bytes, .{
3063         .recorded_inputs = 0,
3064         .current_inputs = 0,
3065     });
3066     defer _ = storage.deinit();
3067     storage.activate();
3068     const changes = try storage.classify(RecordedInputs.fromManifest(&manifest), &.{});
3069     try std.testing.expectEqual(@as(usize, 0), changes.changes.len);
3070     try std.testing.expect(changes.allUnchanged());
3071 }
3072 
3073 test "input change storage classifies cold at capacity after sealing" {
3074     comptime {
3075         @stardustClaim(
3076             @import("alloc_phase").capacity.witness(InputChangeStorage, "tldr_input_change_sealed_transitive_risk"),
3077             null,
3078             null,
3079             null,
3080             null,
3081             null,
3082             null,
3083         );
3084     }
3085     comptime {
3086         @stardustClaim(
3087             @import("alloc_phase").capacity.witness(InputChangeStorage, "tldr_input_change_sealed_foreign_risk"),
3088             null,
3089             null,
3090             null,
3091             null,
3092             null,
3093             null,
3094         );
3095     }
3096 
3097     const count = 20;
3098     var fixture_arena = std.heap.ArenaAllocator.init(std.testing.allocator);
3099     defer fixture_arena.deinit();
3100     const fixture_allocator = fixture_arena.allocator();
3101     var builder = try Builder.init(fixture_allocator, .{});
3102     defer builder.deinit();
3103     var inputs: [count]model.Input = undefined;
3104     for (&inputs, 0..) |*input, index| {
3105         input.* = .{
3106             .name = try std.fmt.allocPrint(fixture_allocator, "input-{d}.o", .{index}),
3107             .bytes = "same",
3108         };
3109         try builder.addInput(input.*);
3110     }
3111     var manifest = try builder.finish();
3112     defer manifest.deinit(fixture_allocator);
3113 
3114     var phase_allocator = try alloc_phase.SealedPhaseAllocator.init(std.testing.allocator);
3115     const initialization_allocator = phase_allocator.initializationAllocator();
3116     const limits = InputChangeStorage.Limits.inspect(
3117         RecordedInputs.fromManifest(&manifest),
3118         &inputs,
3119     );
3120     const capacity = try InputChangeStorage.Capacity.derive(limits);
3121     const bytes = try initialization_allocator.alignedAlloc(
3122         u8,
3123         .fromByteUnits(InputChangeStorage.storage_alignment),
3124         capacity.storage_bytes,
3125     );
3126     var storage = try InputChangeStorage.init(bytes, limits);
3127     storage.activate();
3128     const changes_pointer = storage.changes.ptr;
3129     const matched_pointer = storage.matched_current.ptr;
3130     const links_pointer = storage.current_links.ptr;
3131     const name_pointer = storage.current_by_name.ptr;
3132     const name_capacity = storage.current_by_name.len;
3133 
3134     phase_allocator.seal();
3135     const recorded = RecordedInputs.fromManifest(&manifest);
3136     const first = try storage.classify(recorded, &inputs);
3137     try std.testing.expect(first.allUnchanged());
3138     try std.testing.expectEqual(count, first.changes.len);
3139     const second = try storage.classify(recorded, &inputs);
3140     try std.testing.expect(second.allUnchanged());
3141     try std.testing.expectEqual(changes_pointer, storage.changes.ptr);
3142     try std.testing.expectEqual(matched_pointer, storage.matched_current.ptr);
3143     try std.testing.expectEqual(links_pointer, storage.current_links.ptr);
3144     try std.testing.expectEqual(name_pointer, storage.current_by_name.ptr);
3145     try std.testing.expectEqual(name_capacity, storage.current_by_name.len);
3146     try std.testing.expectEqual(@as(u64, 0), phase_allocator.violations().total());
3147 
3148     phase_allocator.beginTeardown();
3149     const returned = storage.deinit();
3150     try std.testing.expectEqual(alloc_phase.capacity.Phase.teardown, storage.phase);
3151     phase_allocator.teardownAllocator().free(returned);
3152     try std.testing.expectEqual(@as(u64, 0), phase_allocator.violations().total());
3153     phase_allocator.deinit();
3154 }
3155 
3156 test "input change storage rejects max plus one before mutation" {
3157     comptime {
3158         @stardustClaim(
3159             @import("alloc_phase").capacity.witness(InputChangeStorage, "tldr_input_change_max_plus_one"),
3160             null,
3161             null,
3162             null,
3163             null,
3164             null,
3165             null,
3166         );
3167     }
3168 
3169     const allocator = std.testing.allocator;
3170     const count = 17;
3171     var manifest = try repeatedInputManifest(allocator, count, "dup.o", "same");
3172     defer manifest.deinit(allocator);
3173     var oversized_manifest = try repeatedInputManifest(
3174         allocator,
3175         count + 1,
3176         "dup.o",
3177         "same",
3178     );
3179     defer oversized_manifest.deinit(allocator);
3180 
3181     var inputs: [count + 1]model.Input = undefined;
3182     for (inputs[0 .. count - 1]) |*input| {
3183         input.* = .{ .name = "dup.o", .bytes = "same" };
3184     }
3185     inputs[count - 1] = .{ .name = "extra.o", .bytes = "same" };
3186     inputs[count] = .{ .name = "overflow.o", .bytes = "same" };
3187 
3188     var owner = try TestInputChangeOwner.init(allocator, .{
3189         .recorded_inputs = count,
3190         .current_inputs = count,
3191     });
3192     defer owner.deinit(allocator);
3193     owner.storage.activate();
3194     const storage = &owner.storage;
3195     const recorded = RecordedInputs.fromManifest(&manifest);
3196     const previous = try storage.classify(recorded, inputs[0..count]);
3197     var change_snapshot: [count + 1]InputChange = undefined;
3198     @memcpy(change_snapshot[0..previous.changes.len], previous.changes);
3199     const matched_snapshot = storage.matched_current[0..count].*;
3200     const links_snapshot = storage.current_links[0..count].*;
3201     const capacity_snapshot = storage.capacity;
3202     const changes_pointer = storage.changes.ptr;
3203     const matched_pointer = storage.matched_current.ptr;
3204     const links_pointer = storage.current_links.ptr;
3205     const name_pointer = storage.current_by_name.ptr;
3206     const name_capacity = storage.current_by_name.len;
3207     const names_snapshot = try allocator.dupe(
3208         InputChangeNameEntry,
3209         storage.current_by_name,
3210     );
3211     defer allocator.free(names_snapshot);
3212 
3213     try std.testing.expectError(
3214         error.InputCountExceedsCapacity,
3215         storage.classify(recorded, &inputs),
3216     );
3217     try std.testing.expectError(
3218         error.InputCountExceedsCapacity,
3219         storage.classify(RecordedInputs.fromManifest(&oversized_manifest), inputs[0..count]),
3220     );
3221     try std.testing.expect(std.meta.eql(capacity_snapshot, storage.capacity));
3222     try std.testing.expectEqual(changes_pointer, storage.changes.ptr);
3223     try std.testing.expectEqual(matched_pointer, storage.matched_current.ptr);
3224     try std.testing.expectEqual(links_pointer, storage.current_links.ptr);
3225     try std.testing.expectEqual(name_pointer, storage.current_by_name.ptr);
3226     try std.testing.expectEqual(name_capacity, storage.current_by_name.len);
3227     try std.testing.expectEqualSlices(
3228         InputChangeNameEntry,
3229         names_snapshot,
3230         storage.current_by_name,
3231     );
3232     try std.testing.expectEqualSlices(
3233         InputChange,
3234         change_snapshot[0..previous.changes.len],
3235         previous.changes,
3236     );
3237     try std.testing.expectEqualSlices(bool, &matched_snapshot, storage.matched_current[0..count]);
3238     try std.testing.expectEqualSlices(u32, &links_snapshot, storage.current_links[0..count]);
3239 }
3240 
3241 test "input change storage borrows one view until next classification" {
3242     const allocator = std.testing.allocator;
3243     var manifest = try repeatedInputManifest(allocator, 1, "one.o", "old");
3244     defer manifest.deinit(allocator);
3245     var owner = try TestInputChangeOwner.init(allocator, .{
3246         .recorded_inputs = 1,
3247         .current_inputs = 1,
3248     });
3249     defer owner.deinit(allocator);
3250     owner.storage.activate();
3251     const storage = &owner.storage;
3252 
3253     const recorded = RecordedInputs.fromManifest(&manifest);
3254     const first = try storage.classify(recorded, &.{.{
3255         .name = "one.o",
3256         .bytes = "old",
3257     }});
3258     try std.testing.expectEqual(InputChangeKind.unchanged, first.changes[0].kind);
3259     const view_pointer = first.changes.ptr;
3260     const second = try storage.classify(recorded, &.{.{
3261         .name = "one.o",
3262         .bytes = "new",
3263     }});
3264     try std.testing.expectEqual(view_pointer, second.changes.ptr);
3265     try std.testing.expectEqual(InputChangeKind.changed, second.changes[0].kind);
3266     try std.testing.expectEqual(InputChangeKind.changed, first.changes[0].kind);
3267 }
3268 
3269 test "input change storage linear and indexed paths agree" {
3270     comptime {
3271         @stardustClaim(
3272             @import("alloc_phase").capacity.witness(InputChangeStorage, "tldr_input_change_differential"),
3273             null,
3274             null,
3275             null,
3276             null,
3277             null,
3278             null,
3279         );
3280     }
3281 
3282     const allocator = std.testing.allocator;
3283     const count = 24;
3284     const names = [_][]const u8{ "a.o", "b.o", "c.o", "a.o", "d.o" };
3285     var recorded_payloads: [count][1]u8 = undefined;
3286     var builder = try Builder.init(allocator, .{});
3287     defer builder.deinit();
3288     for (&recorded_payloads, 0..) |*payload, index| {
3289         payload[0] = @intCast(index);
3290         try builder.addInput(.{
3291             .name = names[index % names.len],
3292             .bytes = payload[0..],
3293         });
3294     }
3295     var manifest = try builder.finish();
3296     defer manifest.deinit(allocator);
3297 
3298     var inputs: [count + 1]model.Input = undefined;
3299     for (inputs[0..count], 0..) |*input, index| {
3300         const source_index = count - index - 1;
3301         input.* = .{
3302             .name = names[source_index % names.len],
3303             .bytes = recorded_payloads[source_index][0..],
3304         };
3305     }
3306     inputs[count] = .{ .name = "new.o", .bytes = "new" };
3307 
3308     var owner = try TestInputChangeOwner.init(allocator, .{
3309         .recorded_inputs = count,
3310         .current_inputs = count + 1,
3311     });
3312     defer owner.deinit(allocator);
3313     owner.storage.activate();
3314     const storage = &owner.storage;
3315     const recorded = RecordedInputs.fromManifest(&manifest);
3316     const linear = storage.classifyLinear(recorded, &inputs);
3317     const linear_summary = linear.summary;
3318     var linear_changes: [count + 1]InputChange = undefined;
3319     @memcpy(linear_changes[0..linear.changes.len], linear.changes);
3320     const indexed = storage.classifyIndexed(recorded, &inputs);
3321 
3322     try std.testing.expect(std.meta.eql(linear_summary, indexed.summary));
3323     try std.testing.expectEqualSlices(
3324         InputChange,
3325         linear_changes[0..linear.changes.len],
3326         indexed.changes,
3327     );
3328 }
3329 
3330 test "incremental manifest rejects changed inputs" {
3331     const allocator = std.testing.allocator;
3332     const options = model.LinkOptions{};
3333     var builder = try Builder.init(allocator, options);
3334     defer builder.deinit();
3335     try builder.addInput(.{ .name = "a.o", .bytes = "abc" });
3336     try builder.addSection(".text", 0x401000, 0x1000, 3, 4, 16);
3337 
3338     var manifest = try builder.finish();
3339     defer manifest.deinit(allocator);
3340 
3341     try std.testing.expect(manifest.canReuseFor(options, &.{.{ .name = "a.o", .bytes = "abc" }}));
3342     try std.testing.expect(!manifest.canReuseFor(options, &.{.{ .name = "a.o", .bytes = "abd" }}));
3343 
3344     var gc_options = options;
3345     gc_options.gc_sections = true;
3346     try std.testing.expect(!manifest.canReuseFor(gc_options, &.{.{ .name = "a.o", .bytes = "abc" }}));
3347 
3348     var icf_options = options;
3349     icf_options.icf = .all;
3350     try std.testing.expect(!manifest.canReuseFor(icf_options, &.{.{ .name = "a.o", .bytes = "abc" }}));
3351 
3352     var strip_options = options;
3353     strip_options.strip_debug = true;
3354     try std.testing.expect(!manifest.canReuseFor(strip_options, &.{.{ .name = "a.o", .bytes = "abc" }}));
3355 
3356     var build_id_options = options;
3357     build_id_options.build_id = .sha1;
3358     try std.testing.expect(!manifest.canReuseFor(build_id_options, &.{.{ .name = "a.o", .bytes = "abc" }}));
3359 }
3360 
3361 test "non-incremental manifest does not hash inputs for reuse" {
3362     const allocator = std.testing.allocator;
3363     const options = model.LinkOptions{ .incremental_mode = .off };
3364     var builder = try Builder.init(allocator, options);
3365     defer builder.deinit();
3366     try builder.addInput(.{ .name = "a.o", .bytes = "abc" });
3367 
3368     var manifest = try builder.finish();
3369     defer manifest.deinit(allocator);
3370 
3371     try std.testing.expect(!manifest.input_hashes_recorded);
3372     try std.testing.expectEqual(@as(u64, 0), manifest.inputs[0].hash);
3373     try std.testing.expectEqual(@as(usize, 0), manifest.contributions.len);
3374     try std.testing.expectEqual(@as(usize, 0), manifest.discarded_contributions.len);
3375     try std.testing.expect(!manifest.canReuseFor(options, &.{.{ .name = "a.o", .bytes = "abc" }}));
3376 
3377     const text = try manifest.formatTextAlloc(allocator);
3378     defer allocator.free(text);
3379     try std.testing.expect(std.mem.indexOf(u8, text, "a.o size=3 hash=unrecorded") != null);
3380 }
3381 
3382 test "incremental manifest records contributions" {
3383     const allocator = std.testing.allocator;
3384     var builder = try Builder.init(allocator, .{});
3385     defer builder.deinit();
3386     try builder.addInput(.{ .name = "a.o", .bytes = "abc" });
3387     try builder.addSection(".text", 0x401000, 0x1000, 3, 16, 16);
3388     try builder.addContribution("a.o", 0, .section, ".text", 1, ".text", 0x401000, 0x1000, 3, 16, 16);
3389 
3390     var manifest = try builder.finish();
3391     defer manifest.deinit(allocator);
3392 
3393     try std.testing.expectEqual(@as(usize, 1), manifest.contributions.len);
3394     try std.testing.expectEqualStrings("a.o", manifest.string(manifest.contributions[0].input_name_id));
3395     try std.testing.expectEqual(@as(u64, 0), manifest.contributions[0].input_index);
3396     try std.testing.expectEqual(ContributionKind.section, manifest.contributions[0].kind);
3397     try std.testing.expectEqualStrings(".text", manifest.string(manifest.contributions[0].name_id));
3398     try std.testing.expectEqual(@as(u32, 1), manifest.contributions[0].ordinal);
3399     try std.testing.expectEqualStrings(".text", manifest.string(manifest.contributions[0].output_section_name_id));
3400     try std.testing.expectEqual(@as(u64, 16), manifest.contributions[0].reserved_size);
3401 }
3402 
3403 test "incremental manifest renders a text link map" {
3404     const allocator = std.testing.allocator;
3405     var builder = try Builder.init(allocator, .{
3406         .entry_symbol = "_start",
3407         .gc_sections = true,
3408     });
3409     defer builder.deinit();
3410     try builder.addInput(.{ .name = "tiny.o", .bytes = "abc" });
3411     try builder.addSection(".text", 0x401000, 0x1000, 3, 16, 16);
3412     try builder.addContribution("tiny.o", 0, .section, ".text", 1, ".text", 0x401000, 0x1000, 3, 16, 16);
3413     try builder.addDiscardedContribution("tiny.o", 0, ".text.dead", 2, .discarded, 7, 16);
3414     try builder.addExternalTarget("tiny_symbol", 0x401001, 3);
3415     try builder.addArchiveMember(0, "member.o", 0x1234, 0x4321, true);
3416 
3417     var manifest = try builder.finish();
3418     defer manifest.deinit(allocator);
3419 
3420     const text = try manifest.formatTextAlloc(allocator);
3421     defer allocator.free(text);
3422 
3423     try std.testing.expect(std.mem.indexOf(u8, text, "tldr link map\n") != null);
3424     try std.testing.expect(std.mem.indexOf(u8, text, "options: gc_sections=true icf=off strip_debug=false build_id=none\n") != null);
3425     try std.testing.expect(std.mem.indexOf(u8, text, "summary: inputs=1 sections=1 retained=1 retained_size=3 retained_reserve=16 discarded=1 discarded_size=7 external_targets=1 archive_members=1 got_entries=0 merge_pieces=0\n") != null);
3426     try std.testing.expect(std.mem.indexOf(u8, text, "retained by output:\n  .text count=1 size=3 reserve=16\n") != null);
3427     try std.testing.expect(std.mem.indexOf(u8, text, "discarded by reason:\n  discarded count=1 size=7\n") != null);
3428     try std.testing.expect(std.mem.indexOf(u8, text, "inputs (1):\n  tiny.o size=3") != null);
3429     try std.testing.expect(std.mem.indexOf(u8, text, ".text <- tiny.o:.text#1 kind=section") != null);
3430     try std.testing.expect(std.mem.indexOf(u8, text, "discarded (1):\n") != null);
3431     try std.testing.expect(std.mem.indexOf(u8, text, "tiny.o:.text.dead#2 reason=discarded size=7 align=16") != null);
3432 }
3433 
3434 test "incremental manifest parses emitted private binary" {
3435     const allocator = std.testing.allocator;
3436     var builder = try Builder.init(allocator, .{
3437         .entry_symbol = "_start",
3438         .gc_sections = true,
3439         .inputs_read_at_ns = 4321,
3440     });
3441     defer builder.deinit();
3442     try builder.addInput(.{ .name = "tiny.o", .bytes = "abc", .identity = .{ .mtime_ns = 1234, .inode = 42 } });
3443     try builder.addSection(".text", 0x401000, 0x1000, 3, 16, 16);
3444     try builder.addContribution("tiny.o", 0, .section, ".text", 1, ".text", 0x401000, 0x1000, 3, 16, 16);
3445     try builder.addDiscardedContribution("tiny.o", 0, ".text.dead", 2, .discarded, 7, 16);
3446     try builder.addExternalTarget("tiny_symbol", 0x401001, 3);
3447     try builder.addExternalTarget("tiny_absolute", -16, 0);
3448     builder.setInputSelectionHash(0, 0x77);
3449     try builder.addArchiveMember(0, "member.o", 0x1234, 0x4321, true);
3450     try builder.addArchiveMember(0, "skipped.o", 0x5678, 0, false);
3451 
3452     var manifest = try builder.finish();
3453     defer manifest.deinit(allocator);
3454 
3455     const binary = try manifest.formatBinaryAlloc(allocator);
3456     defer allocator.free(binary);
3457     try std.testing.expect(std.mem.indexOf(u8, binary, manifest_binary_protocol) != null);
3458 
3459     var parsed = try Manifest.fromBinary(allocator, binary);
3460     defer parsed.deinit(allocator);
3461 
3462     try std.testing.expect(parsed.canReuseFor(.{ .entry_symbol = "_start", .gc_sections = true }, &.{.{ .name = "tiny.o", .bytes = "abc" }}));
3463     try std.testing.expectEqualStrings("_start", parsed.entrySymbol());
3464     try std.testing.expectEqual(@as(usize, 1), parsed.inputs.len);
3465     try std.testing.expectEqualStrings("tiny.o", parsed.string(parsed.inputs[0].name_id));
3466     try std.testing.expectEqual(@as(i64, 4321), parsed.inputs_read_at_ns);
3467     try std.testing.expectEqual(@as(i64, 1234), parsed.inputs[0].mtime_ns);
3468     try std.testing.expectEqual(@as(u64, 42), parsed.inputs[0].inode);
3469     try std.testing.expect(parsed.inputs[0].identity_recorded);
3470     try std.testing.expectEqual(@as(usize, 1), parsed.sections.len);
3471     try std.testing.expectEqualStrings(".text", parsed.string(parsed.sections[0].name_id));
3472     try std.testing.expectEqual(@as(usize, 1), parsed.contributions.len);
3473     try std.testing.expectEqualStrings(".text", parsed.string(parsed.contributions[0].name_id));
3474     try std.testing.expectEqual(@as(u64, 16), parsed.contributions[0].reserved_size);
3475     try std.testing.expectEqual(@as(usize, 1), parsed.discarded_contributions.len);
3476     try std.testing.expectEqualStrings(".text.dead", parsed.string(parsed.discarded_contributions[0].name_id));
3477     try std.testing.expectEqual(@as(usize, 2), parsed.external_targets.len);
3478     try std.testing.expectEqualStrings("tiny_symbol", parsed.string(parsed.external_targets[0].name_id));
3479     try std.testing.expectEqual(@as(i128, 0x401001), parsed.external_targets[0].address());
3480     try std.testing.expectEqual(@as(u64, 3), parsed.external_targets[0].size);
3481     try std.testing.expectEqualStrings("tiny_absolute", parsed.string(parsed.external_targets[1].name_id));
3482     try std.testing.expectEqual(@as(i128, -16), parsed.external_targets[1].address());
3483     try std.testing.expectEqual(@as(u64, 0x77), parsed.inputs[0].selection_hash);
3484     try std.testing.expectEqual(@as(usize, 2), parsed.archive_members.len);
3485     try std.testing.expectEqualStrings("member.o", parsed.string(parsed.archive_members[0].name_id));
3486     try std.testing.expectEqual(@as(u64, 0x1234), parsed.archive_members[0].hash);
3487     try std.testing.expectEqual(@as(u64, 0x4321), parsed.archive_members[0].link_hash);
3488     try std.testing.expect(parsed.archive_members[0].selected);
3489     try std.testing.expectEqualStrings("skipped.o", parsed.string(parsed.archive_members[1].name_id));
3490     try std.testing.expect(!parsed.archive_members[1].selected);
3491 
3492     var out = std.Io.Writer.Allocating.init(allocator);
3493     defer out.deinit();
3494     try manifest.writeBinary(&out.writer);
3495     const streamed = try out.toOwnedSlice();
3496     defer allocator.free(streamed);
3497 
3498     var streamed_parsed = try Manifest.fromBinary(allocator, streamed);
3499     defer streamed_parsed.deinit(allocator);
3500     try std.testing.expectEqualStrings("_start", streamed_parsed.entrySymbol());
3501     try std.testing.expectEqualStrings("tiny.o", streamed_parsed.string(streamed_parsed.inputs[0].name_id));
3502 }
3503 
3504 test "incremental private manifest interns repeated strings" {
3505     const allocator = std.testing.allocator;
3506     var builder = try Builder.init(allocator, .{
3507         .entry_symbol = "_start",
3508     });
3509     defer builder.deinit();
3510     try builder.addInput(.{ .name = "tiny.o", .bytes = "abc" });
3511     try builder.addSection(".text", 0x401000, 0x1000, 3, 64, 16);
3512     try builder.addContribution("tiny.o", 0, .section, ".text.one", 1, ".text", 0x401000, 0x1000, 3, 16, 16);
3513     try builder.addContribution("tiny.o", 0, .section, ".text.two", 2, ".text", 0x401010, 0x1010, 4, 16, 16);
3514     try builder.addDiscardedContribution("tiny.o", 0, ".text.dead", 3, .discarded, 8, 16);
3515 
3516     var manifest = try builder.finish();
3517     defer manifest.deinit(allocator);
3518 
3519     const binary = try manifest.formatBinaryAlloc(allocator);
3520     defer allocator.free(binary);
3521 
3522     try std.testing.expectEqual(@as(usize, 1), std.mem.count(u8, binary, "tiny.o"));
3523     try std.testing.expectEqual(@as(usize, 1), std.mem.count(u8, binary, "_start"));
3524 
3525     var parsed = try Manifest.fromBinary(allocator, binary);
3526     defer parsed.deinit(allocator);
3527 
3528     try std.testing.expectEqualStrings("tiny.o", parsed.string(parsed.inputs[0].name_id));
3529     try std.testing.expectEqualStrings("tiny.o", parsed.string(parsed.contributions[0].input_name_id));
3530     try std.testing.expectEqualStrings("tiny.o", parsed.string(parsed.contributions[1].input_name_id));
3531     try std.testing.expectEqualStrings("tiny.o", parsed.string(parsed.discarded_contributions[0].input_name_id));
3532     try std.testing.expectEqualStrings(".text", parsed.string(parsed.sections[0].name_id));
3533     try std.testing.expectEqualStrings(".text", parsed.string(parsed.contributions[0].output_section_name_id));
3534     try std.testing.expectEqualStrings(".text", parsed.string(parsed.contributions[1].output_section_name_id));
3535 }
3536 
3537 test "incremental planner accepts replacements within recorded reserve" {
3538     const allocator = std.testing.allocator;
3539     var builder = try Builder.init(allocator, .{});
3540     defer builder.deinit();
3541     try builder.addContribution("a.o", 0, .section, ".text", 1, ".text", 0x401000, 0x1000, 3, 16, 16);
3542     try builder.addContribution("a.o", 0, .common_symbol, "scratch", 2, ".bss", 0x402000, 0x2000, 8, 16, 8);
3543 
3544     var manifest = try builder.finish();
3545     defer manifest.deinit(allocator);
3546 
3547     const plan = manifest.planContributionReplacement(&.{
3548         .{ .input_name = "a.o", .input_index = 0, .kind = .section, .name = ".text", .ordinal = 1, .size = 12, .alignment = 16 },
3549         .{ .input_name = "a.o", .input_index = 0, .kind = .common_symbol, .name = "scratch", .ordinal = 2, .size = 4, .alignment = 1 },
3550     });
3551     try std.testing.expectEqual(PatchDecision.in_place, plan.decision);
3552     try std.testing.expectEqual(@as(?PatchBlocker, null), plan.blocker);
3553     try std.testing.expectEqual(@as(?usize, null), plan.blocking_index);
3554 }
3555 
3556 test "incremental planner accepts out-of-order replacements" {
3557     const allocator = std.testing.allocator;
3558     var builder = try Builder.init(allocator, .{});
3559     defer builder.deinit();
3560     try builder.addContribution("a.o", 0, .section, ".text.one", 1, ".text", 0x401000, 0x1000, 3, 16, 16);
3561     try builder.addContribution("b.o", 1, .section, ".text.two", 2, ".text", 0x401040, 0x1040, 8, 16, 16);
3562     try builder.addContribution("c.o", 2, .section, ".text.three", 3, ".text", 0x401080, 0x1080, 12, 16, 16);
3563 
3564     var manifest = try builder.finish();
3565     defer manifest.deinit(allocator);
3566 
3567     const plan = manifest.planContributionReplacement(&.{
3568         .{ .input_name = "c.o", .input_index = 2, .kind = .section, .name = ".text.three", .ordinal = 3, .size = 12, .alignment = 16 },
3569         .{ .input_name = "a.o", .input_index = 0, .kind = .section, .name = ".text.one", .ordinal = 1, .size = 3, .alignment = 16 },
3570     });
3571     try std.testing.expectEqual(PatchDecision.in_place, plan.decision);
3572 }
3573 
3574 test "incremental planner uses ordinals to distinguish duplicate names" {
3575     const allocator = std.testing.allocator;
3576     var builder = try Builder.init(allocator, .{});
3577     defer builder.deinit();
3578     try builder.addContribution("a.o", 0, .section, ".text", 1, ".text", 0x401000, 0x1000, 3, 16, 16);
3579     try builder.addContribution("a.o", 0, .section, ".text", 2, ".text", 0x401040, 0x1040, 32, 64, 16);
3580 
3581     var manifest = try builder.finish();
3582     defer manifest.deinit(allocator);
3583 
3584     const plan = manifest.planContributionReplacement(&.{
3585         .{ .input_name = "a.o", .input_index = 0, .kind = .section, .name = ".text", .ordinal = 2, .size = 48, .alignment = 16 },
3586     });
3587     try std.testing.expectEqual(PatchDecision.in_place, plan.decision);
3588 
3589     const oversized_first_duplicate = manifest.planContributionReplacement(&.{
3590         .{ .input_name = "a.o", .input_index = 0, .kind = .section, .name = ".text", .ordinal = 1, .size = 48, .alignment = 16 },
3591     });
3592     try std.testing.expectEqual(PatchDecision.full_link, oversized_first_duplicate.decision);
3593     try std.testing.expectEqual(PatchBlocker.grew_past_reserve, oversized_first_duplicate.blocker.?);
3594 }
3595 
3596 test "incremental planner uses input indexes to distinguish repeated inputs" {
3597     const allocator = std.testing.allocator;
3598     var builder = try Builder.init(allocator, .{});
3599     defer builder.deinit();
3600     try builder.addContribution("dup.o", 0, .section, ".text", 1, ".text", 0x401000, 0x1000, 3, 8, 16);
3601     try builder.addContribution("dup.o", 1, .section, ".text", 1, ".text", 0x401040, 0x1040, 32, 64, 16);
3602 
3603     var manifest = try builder.finish();
3604     defer manifest.deinit(allocator);
3605 
3606     var index = try ContributionIndex.init(allocator, manifest);
3607     defer index.deinit(allocator);
3608 
3609     const second_plan = index.planContributionReplacement(manifest, &.{
3610         .{ .input_name = "dup.o", .input_index = 1, .kind = .section, .name = ".text", .ordinal = 1, .size = 48, .alignment = 16 },
3611     });
3612     try std.testing.expectEqual(PatchDecision.in_place, second_plan.decision);
3613 
3614     const first_plan = index.planContributionReplacement(manifest, &.{
3615         .{ .input_name = "dup.o", .input_index = 0, .kind = .section, .name = ".text", .ordinal = 1, .size = 48, .alignment = 16 },
3616     });
3617     try std.testing.expectEqual(PatchDecision.full_link, first_plan.decision);
3618     try std.testing.expectEqual(PatchBlocker.grew_past_reserve, first_plan.blocker.?);
3619 }
3620 
3621 test "incremental contribution index matches linear planner decisions" {
3622     const allocator = std.testing.allocator;
3623     var builder = try Builder.init(allocator, .{});
3624     defer builder.deinit();
3625     try builder.addContribution("a.o", 0, .section, ".text", 1, ".text", 0x401000, 0x1000, 3, 16, 16);
3626     try builder.addContribution("a.o", 0, .section, ".text", 2, ".text", 0x401040, 0x1040, 32, 64, 16);
3627     try builder.addContribution("a.o", 0, .common_symbol, "scratch", 3, ".bss", 0x402000, 0x2000, 8, 16, 8);
3628 
3629     var manifest = try builder.finish();
3630     defer manifest.deinit(allocator);
3631 
3632     var index = try ContributionIndex.init(allocator, manifest);
3633     defer index.deinit(allocator);
3634 
3635     const replacements = [_]ReplacementContribution{
3636         .{ .input_name = "a.o", .input_index = 0, .kind = .section, .name = ".text", .ordinal = 2, .size = 48, .alignment = 16 },
3637         .{ .input_name = "a.o", .input_index = 0, .kind = .common_symbol, .name = "scratch", .ordinal = 3, .size = 16, .alignment = 8 },
3638     };
3639     const linear = manifest.planContributionReplacement(&replacements);
3640     const indexed = index.planContributionReplacement(manifest, &replacements);
3641     try std.testing.expectEqual(linear.decision, indexed.decision);
3642     try std.testing.expectEqual(linear.blocker, indexed.blocker);
3643     try std.testing.expectEqual(linear.blocking_index, indexed.blocking_index);
3644 
3645     const missing = [_]ReplacementContribution{
3646         .{ .input_name = "a.o", .input_index = 0, .kind = .section, .name = ".text", .ordinal = 4, .size = 1, .alignment = 1 },
3647     };
3648     try std.testing.expectEqual(
3649         PatchDecision.full_link,
3650         index.planContributionReplacement(manifest, &missing).decision,
3651     );
3652 }
3653 
3654 test "incremental patch application writes payloads into recorded reserves" {
3655     const allocator = std.testing.allocator;
3656     var builder = try Builder.init(allocator, .{});
3657     defer builder.deinit();
3658     try builder.addContribution("a.o", 0, .section, ".text", 1, ".text", 0x401000, 4, 3, 8, 16);
3659     try builder.addContribution("b.o", 1, .section, ".text.two", 2, ".text", 0x401040, 16, 4, 4, 16);
3660 
3661     var manifest = try builder.finish();
3662     defer manifest.deinit(allocator);
3663 
3664     var index = try ContributionIndex.init(allocator, manifest);
3665     defer index.deinit(allocator);
3666 
3667     const replacements = [_]ReplacementContribution{
3668         .{ .input_name = "a.o", .input_index = 0, .kind = .section, .name = ".text", .ordinal = 1, .size = 5, .alignment = 16, .payload = "hello" },
3669         .{ .input_name = "b.o", .input_index = 1, .kind = .section, .name = ".text.two", .ordinal = 2, .size = 4, .alignment = 16, .payload = "link" },
3670     };
3671 
3672     var linear_image = @as([32]u8, @splat(0xaa));
3673     var indexed_image = linear_image;
3674     const linear = try manifest.applyContributionReplacement(linear_image[0..], &replacements);
3675     const indexed = try index.applyContributionReplacement(indexed_image[0..], manifest, &replacements);
3676 
3677     try std.testing.expectEqual(PatchDecision.in_place, linear.plan.decision);
3678     try std.testing.expectEqual(linear.plan.decision, indexed.plan.decision);
3679     try std.testing.expectEqual(@as(usize, 2), linear.contributions_written);
3680     try std.testing.expectEqual(linear.contributions_written, indexed.contributions_written);
3681     try std.testing.expectEqual(@as(usize, 9), linear.bytes_written);
3682     try std.testing.expectEqual(@as(usize, 3), linear.zero_fill_bytes);
3683     try std.testing.expectEqualSlices(u8, "hello", linear_image[4..9]);
3684     try std.testing.expectEqualSlices(u8, &.{ 0, 0, 0 }, linear_image[9..12]);
3685     try std.testing.expectEqualSlices(u8, "link", linear_image[16..20]);
3686     try std.testing.expectEqualSlices(u8, &linear_image, &indexed_image);
3687 }
3688 
3689 test "incremental contribution index applies planned in-place replacements" {
3690     const allocator = std.testing.allocator;
3691     var builder = try Builder.init(allocator, .{});
3692     defer builder.deinit();
3693     try builder.addContribution("a.o", 0, .section, ".text", 1, ".text", 0x401000, 4, 3, 8, 16);
3694     try builder.addContribution("b.o", 1, .section, ".text.two", 2, ".text", 0x401040, 16, 4, 4, 16);
3695 
3696     var manifest = try builder.finish();
3697     defer manifest.deinit(allocator);
3698 
3699     var index = try ContributionIndex.init(allocator, manifest);
3700     defer index.deinit(allocator);
3701 
3702     const replacements = [_]ReplacementContribution{
3703         .{ .input_name = "a.o", .input_index = 0, .kind = .section, .name = ".text", .ordinal = 1, .size = 5, .alignment = 16, .payload = "hello" },
3704         .{ .input_name = "b.o", .input_index = 1, .kind = .section, .name = ".text.two", .ordinal = 2, .size = 4, .alignment = 16, .payload = "link" },
3705     };
3706 
3707     const plan = index.planContributionReplacement(manifest, &replacements);
3708     try std.testing.expectEqual(PatchDecision.in_place, plan.decision);
3709 
3710     var image = @as([32]u8, @splat(0xaa));
3711     const application = try index.applyContributionReplacementInPlace(image[0..], manifest, &replacements);
3712     try std.testing.expectEqual(PatchDecision.in_place, application.plan.decision);
3713     try std.testing.expectEqual(@as(usize, 2), application.contributions_written);
3714     try std.testing.expectEqual(@as(usize, 9), application.bytes_written);
3715     try std.testing.expectEqual(@as(usize, 3), application.zero_fill_bytes);
3716     try std.testing.expectEqualSlices(u8, "hello", image[4..9]);
3717     try std.testing.expectEqualSlices(u8, "link", image[16..20]);
3718 }
3719 
3720 test "incremental patch application returns full-link blockers without writing" {
3721     const allocator = std.testing.allocator;
3722     var builder = try Builder.init(allocator, .{});
3723     defer builder.deinit();
3724     try builder.addContribution("a.o", 0, .section, ".text", 1, ".text", 0x401000, 4, 3, 8, 16);
3725 
3726     var manifest = try builder.finish();
3727     defer manifest.deinit(allocator);
3728 
3729     var image = @as([16]u8, @splat(0xaa));
3730     const application = try manifest.applyContributionReplacement(image[0..], &.{
3731         .{ .input_name = "a.o", .input_index = 0, .kind = .section, .name = ".text", .ordinal = 1, .size = 9, .alignment = 16, .payload = "oversized" },
3732     });
3733     try std.testing.expectEqual(PatchDecision.full_link, application.plan.decision);
3734     try std.testing.expectEqual(PatchBlocker.grew_past_reserve, application.plan.blocker.?);
3735     try std.testing.expectEqual(@as(usize, 0), application.contributions_written);
3736     try std.testing.expectEqual(@as(usize, 0), application.bytes_written);
3737     for (image) |byte| try std.testing.expectEqual(@as(u8, 0xaa), byte);
3738 }
3739 
3740 test "incremental patch application rejects payload size mismatch" {
3741     const allocator = std.testing.allocator;
3742     var builder = try Builder.init(allocator, .{});
3743     defer builder.deinit();
3744     try builder.addContribution("a.o", 0, .section, ".text", 1, ".text", 0x401000, 4, 3, 8, 16);
3745 
3746     var manifest = try builder.finish();
3747     defer manifest.deinit(allocator);
3748 
3749     var image = @as([16]u8, @splat(0xaa));
3750     try std.testing.expectError(
3751         error.PatchPayloadMismatch,
3752         manifest.applyContributionReplacement(image[0..], &.{
3753             .{ .input_name = "a.o", .input_index = 0, .kind = .section, .name = ".text", .ordinal = 1, .size = 4, .alignment = 16, .payload = "bad" },
3754         }),
3755     );
3756 }
3757 
3758 test "incremental contribution index rejects duplicate keys" {
3759     const allocator = std.testing.allocator;
3760     var builder = try Builder.init(allocator, .{});
3761     defer builder.deinit();
3762     try builder.addContribution("a.o", 0, .section, ".text", 1, ".text", 0x401000, 0x1000, 3, 16, 16);
3763     try builder.addContribution("a.o", 0, .section, ".text", 1, ".text", 0x401040, 0x1040, 3, 16, 16);
3764 
3765     var manifest = try builder.finish();
3766     defer manifest.deinit(allocator);
3767 
3768     try std.testing.expectError(error.DuplicateContribution, ContributionIndex.init(allocator, manifest));
3769 }
3770 
3771 test "prepared incremental state owns indexed patch planning" {
3772     const allocator = std.testing.allocator;
3773     const options = model.LinkOptions{};
3774     var builder = try Builder.init(allocator, options);
3775     defer builder.deinit();
3776     try builder.addInput(.{ .name = "a.o", .bytes = "abc" });
3777     try builder.addContribution("a.o", 0, .section, ".text.one", 1, ".text", 0x401000, 4, 3, 8, 16);
3778     try builder.addContribution("b.o", 1, .section, ".text.two", 2, ".text", 0x401040, 16, 4, 4, 16);
3779 
3780     const manifest = try builder.finish();
3781     var state = try PreparedState.fromOwnedManifest(allocator, manifest);
3782     defer state.deinit(allocator);
3783 
3784     try std.testing.expect(state.canReuseFor(options, &.{.{ .name = "a.o", .bytes = "abc" }}));
3785 
3786     const replacements = [_]ReplacementContribution{
3787         .{ .input_name = "b.o", .input_index = 1, .kind = .section, .name = ".text.two", .ordinal = 2, .size = 4, .alignment = 16, .payload = "link" },
3788         .{ .input_name = "a.o", .input_index = 0, .kind = .section, .name = ".text.one", .ordinal = 1, .size = 5, .alignment = 16, .payload = "patch" },
3789     };
3790 
3791     const plan = state.planContributionReplacement(&replacements);
3792     try std.testing.expectEqual(PatchDecision.in_place, plan.decision);
3793 
3794     var image = @as([32]u8, @splat(0xaa));
3795     const application = try state.applyContributionReplacement(image[0..], &replacements);
3796     try std.testing.expectEqual(PatchDecision.in_place, application.plan.decision);
3797     try std.testing.expectEqual(@as(usize, 2), application.contributions_written);
3798     try std.testing.expectEqualSlices(u8, "patch", image[4..9]);
3799     try std.testing.expectEqualSlices(u8, &.{ 0, 0, 0 }, image[9..12]);
3800     try std.testing.expectEqualSlices(u8, "link", image[16..20]);
3801 }
3802 
3803 test "prepared incremental state rejects duplicate contribution keys at index build" {
3804     const allocator = std.testing.allocator;
3805     var builder = try Builder.init(allocator, .{});
3806     defer builder.deinit();
3807     try builder.addContribution("a.o", 0, .section, ".text", 1, ".text", 0x401000, 0x1000, 3, 16, 16);
3808     try builder.addContribution("a.o", 0, .section, ".text", 1, ".text", 0x401040, 0x1040, 3, 16, 16);
3809     try builder.addContribution("b.o", 1, .section, ".text.other", 2, ".text", 0x401080, 0x1080, 3, 16, 16);
3810 
3811     const manifest = try builder.finish();
3812     var state = try PreparedState.fromOwnedManifest(allocator, manifest);
3813     defer state.deinit(allocator);
3814 
3815     const duplicated = [_]ReplacementContribution{
3816         .{ .input_name = "a.o", .input_index = 0, .kind = .section, .name = ".text", .ordinal = 1, .size = 3, .alignment = 16, .payload = "one" },
3817     };
3818     try std.testing.expectError(error.DuplicateContribution, state.ensureReplacementIndex(allocator, &duplicated));
3819     try std.testing.expect(state.contribution_index == null);
3820 
3821     const outside = [_]ReplacementContribution{
3822         .{ .input_name = "b.o", .input_index = 1, .kind = .section, .name = ".text.other", .ordinal = 2, .size = 3, .alignment = 16, .payload = "two" },
3823     };
3824     try state.ensureReplacementIndex(allocator, &outside);
3825     try std.testing.expect(state.contribution_index != null);
3826     try std.testing.expectEqual(
3827         @as(?usize, 2),
3828         state.contribution_index.?.contributionIndexForReplacement(outside[0]),
3829     );
3830     try std.testing.expectEqual(
3831         @as(?usize, null),
3832         state.contribution_index.?.contributionIndexForReplacement(duplicated[0]),
3833     );
3834 }
3835 
3836 test "prepared incremental state classifies input changes" {
3837     const allocator = std.testing.allocator;
3838     var builder = try Builder.init(allocator, .{});
3839     defer builder.deinit();
3840     try builder.addInput(.{ .name = "same.o", .bytes = "abc" });
3841     try builder.addInput(.{ .name = "changed.o", .bytes = "old" });
3842     try builder.addInput(.{ .name = "removed.o", .bytes = "gone" });
3843     try builder.addContribution("changed.o", 1, .section, ".text.changed", 1, ".text", 0x401000, 0x1000, 7, 16, 16);
3844 
3845     const manifest = try builder.finish();
3846     var state = try PreparedState.fromOwnedManifest(allocator, manifest);
3847     defer state.deinit(allocator);
3848 
3849     var classified = try classifyTestInputs(allocator, state.manifest, &.{
3850         .{ .name = "same.o", .bytes = "abc" },
3851         .{ .name = "changed.o", .bytes = "new" },
3852         .{ .name = "added.o", .bytes = "fresh" },
3853     });
3854     defer classified.deinit(allocator);
3855     const changes = classified.changes;
3856 
3857     try std.testing.expect(!changes.allUnchanged());
3858     try std.testing.expectEqual(@as(usize, 1), changes.summary.unchanged);
3859     try std.testing.expectEqual(@as(usize, 1), changes.summary.changed);
3860     try std.testing.expectEqual(@as(usize, 1), changes.summary.removed);
3861     try std.testing.expectEqual(@as(usize, 1), changes.summary.added);
3862     try std.testing.expectEqual(InputChangeKind.unchanged, changes.changes[0].kind);
3863     try std.testing.expectEqual(@as(?usize, 0), changes.changes[0].recorded_index);
3864     try std.testing.expectEqual(@as(?usize, 0), changes.changes[0].current_index);
3865     try std.testing.expectEqual(InputChangeKind.changed, changes.changes[1].kind);
3866     try std.testing.expectEqual(InputChangeKind.removed, changes.changes[2].kind);
3867     try std.testing.expectEqual(@as(?usize, 2), changes.changes[2].recorded_index);
3868     try std.testing.expectEqual(@as(?usize, null), changes.changes[2].current_index);
3869     try std.testing.expectEqual(InputChangeKind.added, changes.changes[3].kind);
3870     try std.testing.expectEqual(@as(?usize, null), changes.changes[3].recorded_index);
3871     try std.testing.expectEqual(@as(?usize, 2), changes.changes[3].current_index);
3872 }
3873 
3874 test "input identity short-circuits change detection before byte hashes" {
3875     const allocator = std.testing.allocator;
3876     var builder = try Builder.init(allocator, .{ .inputs_read_at_ns = 200 });
3877     defer builder.deinit();
3878     try builder.addInput(.{ .name = "steady.o", .bytes = "old-bytes", .identity = .{ .mtime_ns = 100, .inode = 7 } });
3879     try builder.addInput(.{ .name = "touched.o", .bytes = "same-bytes", .identity = .{ .mtime_ns = 100, .inode = 8 } });
3880     try builder.addInput(.{ .name = "racing.o", .bytes = "old-bytes", .identity = .{ .mtime_ns = 250, .inode = 9 } });
3881 
3882     const manifest = try builder.finish();
3883     var state = try PreparedState.fromOwnedManifest(allocator, manifest);
3884     defer state.deinit(allocator);
3885     try std.testing.expectEqual(@as(i64, 200), state.manifest.inputs_read_at_ns);
3886 
3887     var classified = try classifyTestInputs(allocator, state.manifest, &.{
3888         .{ .name = "steady.o", .bytes = "NEW-bytes", .identity = .{ .mtime_ns = 100, .inode = 7 } },
3889         .{ .name = "touched.o", .bytes = "same-bytes", .identity = .{ .mtime_ns = 150, .inode = 8 } },
3890         .{ .name = "racing.o", .bytes = "new-bytes", .identity = .{ .mtime_ns = 250, .inode = 9 } },
3891     });
3892     defer classified.deinit(allocator);
3893     const changes = classified.changes;
3894 
3895     try std.testing.expectEqual(InputChangeKind.unchanged, changes.changes[0].kind);
3896     try std.testing.expectEqual(InputChangeKind.unchanged, changes.changes[1].kind);
3897     try std.testing.expectEqual(InputChangeKind.changed, changes.changes[2].kind);
3898 
3899     try std.testing.expect(state.canReuseFor(.{ .incremental_mode = .relink, .entry_symbol = "_start" }, &.{
3900         .{ .name = "steady.o", .bytes = "NEW-bytes", .identity = .{ .mtime_ns = 100, .inode = 7 } },
3901         .{ .name = "touched.o", .bytes = "same-bytes", .identity = .{ .mtime_ns = 150, .inode = 8 } },
3902         .{ .name = "racing.o", .bytes = "old-bytes", .identity = .{ .mtime_ns = 250, .inode = 9 } },
3903     }));
3904     try std.testing.expect(!state.canReuseFor(.{ .incremental_mode = .relink, .entry_symbol = "_start" }, &.{
3905         .{ .name = "steady.o", .bytes = "old-bytes", .identity = .{ .mtime_ns = 100, .inode = 7 } },
3906         .{ .name = "touched.o", .bytes = "same-bytes", .identity = .{ .mtime_ns = 150, .inode = 8 } },
3907         .{ .name = "racing.o", .bytes = "new-bytes", .identity = .{ .mtime_ns = 250, .inode = 9 } },
3908     }));
3909 }
3910 
3911 test "input change classification preserves repeated input order" {
3912     const allocator = std.testing.allocator;
3913     var builder = try Builder.init(allocator, .{});
3914     defer builder.deinit();
3915     try builder.addInput(.{ .name = "dup.o", .bytes = "first" });
3916     try builder.addInput(.{ .name = "dup.o", .bytes = "second" });
3917 
3918     const manifest = try builder.finish();
3919     var state = try PreparedState.fromOwnedManifest(allocator, manifest);
3920     defer state.deinit(allocator);
3921 
3922     var classified = try classifyTestInputs(allocator, state.manifest, &.{
3923         .{ .name = "dup.o", .bytes = "first" },
3924         .{ .name = "dup.o", .bytes = "changed-second" },
3925     });
3926     defer classified.deinit(allocator);
3927     const changes = classified.changes;
3928 
3929     try std.testing.expectEqual(@as(usize, 1), changes.summary.unchanged);
3930     try std.testing.expectEqual(@as(usize, 1), changes.summary.changed);
3931     try std.testing.expectEqual(InputChangeKind.unchanged, changes.changes[0].kind);
3932     try std.testing.expectEqual(@as(?usize, 0), changes.changes[0].current_index);
3933     try std.testing.expectEqual(InputChangeKind.changed, changes.changes[1].kind);
3934     try std.testing.expectEqual(@as(?usize, 1), changes.changes[1].current_index);
3935 }
3936 
3937 test "input change classification matches repeated names by first current occurrence" {
3938     const allocator = std.testing.allocator;
3939     var builder = try Builder.init(allocator, .{});
3940     defer builder.deinit();
3941     var recorded_payloads: [20][1]u8 = undefined;
3942     for (&recorded_payloads, 0..) |*payload, index| {
3943         payload[0] = @intCast(index);
3944         try builder.addInput(.{ .name = "dup.o", .bytes = payload[0..] });
3945     }
3946 
3947     const manifest = try builder.finish();
3948     var state = try PreparedState.fromOwnedManifest(allocator, manifest);
3949     defer state.deinit(allocator);
3950 
3951     var current_payloads: [21][1]u8 = undefined;
3952     var current_inputs: [21]model.Input = undefined;
3953     for (current_inputs[0..20], 0..) |*input, index| {
3954         current_payloads[index][0] = @intCast(40 - index);
3955         input.* = .{ .name = "dup.o", .bytes = current_payloads[index][0..] };
3956     }
3957     current_payloads[20][0] = 99;
3958     current_inputs[20] = .{ .name = "dup.o", .bytes = current_payloads[20][0..] };
3959 
3960     var classified = try classifyTestInputs(
3961         allocator,
3962         state.manifest,
3963         &current_inputs,
3964     );
3965     defer classified.deinit(allocator);
3966     const changes = classified.changes;
3967 
3968     try std.testing.expectEqual(@as(usize, 0), changes.summary.unchanged);
3969     try std.testing.expectEqual(@as(usize, 20), changes.summary.changed);
3970     try std.testing.expectEqual(@as(usize, 1), changes.summary.added);
3971     for (changes.changes[0..20], 0..) |change, index| {
3972         try std.testing.expectEqual(InputChangeKind.changed, change.kind);
3973         try std.testing.expectEqual(@as(?usize, index), change.recorded_index);
3974         try std.testing.expectEqual(@as(?usize, index), change.current_index);
3975     }
3976     try std.testing.expectEqual(InputChangeKind.added, changes.changes[20].kind);
3977     try std.testing.expectEqual(@as(?usize, 20), changes.changes[20].current_index);
3978 }
3979 
3980 test "prepared incremental state summarizes contributions by input index" {
3981     const allocator = std.testing.allocator;
3982     var builder = try Builder.init(allocator, .{});
3983     defer builder.deinit();
3984     try builder.addInput(.{ .name = "dup.o", .bytes = "first" });
3985     try builder.addInput(.{ .name = "dup.o", .bytes = "second" });
3986     try builder.addContribution("dup.o", 0, .section, ".text", 1, ".text", 0x401000, 0x1000, 3, 8, 16);
3987     try builder.addContribution("dup.o", 1, .section, ".text", 1, ".text", 0x401040, 0x1040, 32, 64, 16);
3988     try builder.addDiscardedContribution("dup.o", 1, ".text.dead", 2, .discarded, 5, 16);
3989 
3990     const manifest = try builder.finish();
3991     var state = try PreparedState.fromOwnedManifest(allocator, manifest);
3992     defer state.deinit(allocator);
3993 
3994     const first = state.contributionSummaryForInput(0);
3995     try std.testing.expectEqual(@as(usize, 1), first.retained);
3996     try std.testing.expectEqual(@as(usize, 0), first.discarded);
3997     try std.testing.expectEqual(@as(u64, 3), first.retained_size);
3998 
3999     const second = state.contributionSummaryForInput(1);
4000     try std.testing.expectEqual(@as(usize, 1), second.retained);
4001     try std.testing.expectEqual(@as(usize, 1), second.discarded);
4002     try std.testing.expectEqual(@as(u64, 32), second.retained_size);
4003     try std.testing.expectEqual(@as(u64, 5), second.discarded_size);
4004 
4005     try std.testing.expect(state.contributionSummaryForInput(2).isEmpty());
4006     try std.testing.expect(state.contributionSummaryForChange(.{ .kind = .added, .current_index = 2 }).isEmpty());
4007     try std.testing.expectEqual(@as(usize, 1), state.contributionSummaryForChange(.{
4008         .kind = .changed,
4009         .recorded_index = 1,
4010         .current_index = 1,
4011     }).discarded);
4012 }
4013 
4014 test "prepared incremental state plans reusable relinks for unchanged inputs" {
4015     const allocator = std.testing.allocator;
4016     const options = model.LinkOptions{};
4017     var builder = try Builder.init(allocator, options);
4018     defer builder.deinit();
4019     try builder.addInput(.{ .name = "a.o", .bytes = "abc" });
4020     try builder.addInput(.{ .name = "b.o", .bytes = "def" });
4021 
4022     const manifest = try builder.finish();
4023     var state = try PreparedState.fromOwnedManifest(allocator, manifest);
4024     defer state.deinit(allocator);
4025 
4026     const plan = try planInputRelinkForTest(&state, allocator, options, &.{
4027         .{ .name = "a.o", .bytes = "abc" },
4028         .{ .name = "b.o", .bytes = "def" },
4029     });
4030     try std.testing.expectEqual(RelinkDecision.reuse_output, plan.decision);
4031     try std.testing.expectEqual(@as(?RelinkBlocker, null), plan.blocker);
4032     try std.testing.expectEqual(@as(usize, 2), plan.input_summary.unchanged);
4033     try std.testing.expectEqual(@as(usize, 0), plan.input_summary.changed);
4034 }
4035 
4036 test "prepared incremental state rejects reordered unchanged inputs" {
4037     const allocator = std.testing.allocator;
4038     const options = model.LinkOptions{};
4039     var builder = try Builder.init(allocator, options);
4040     defer builder.deinit();
4041     try builder.addInput(.{ .name = "a.o", .bytes = "abc" });
4042     try builder.addInput(.{ .name = "b.o", .bytes = "def" });
4043     try builder.addContribution("a.o", 0, .section, ".text.a", 1, ".text", 0x401000, 0x1000, 3, 16, 16);
4044     try builder.addContribution("b.o", 1, .section, ".text.b", 1, ".text", 0x401020, 0x1020, 3, 16, 16);
4045 
4046     const manifest = try builder.finish();
4047     var state = try PreparedState.fromOwnedManifest(allocator, manifest);
4048     defer state.deinit(allocator);
4049 
4050     const inputs = [_]model.Input{
4051         .{ .name = "b.o", .bytes = "def" },
4052         .{ .name = "a.o", .bytes = "abc" },
4053     };
4054 
4055     const plan = try planInputRelinkForTest(&state, allocator, options, &inputs);
4056     try std.testing.expectEqual(RelinkDecision.full_link, plan.decision);
4057     try std.testing.expectEqual(RelinkBlocker.input_reordered, plan.blocker.?);
4058     try std.testing.expectEqual(@as(?usize, 0), plan.blocking_change_index);
4059     try std.testing.expectEqual(@as(usize, 2), plan.input_summary.unchanged);
4060     try std.testing.expectEqual(@as(usize, 1), plan.affected_contributions.retained);
4061 
4062     const changed_plan = try planChangedInputRelinkForTest(
4063         &state,
4064         allocator,
4065         options,
4066         &inputs,
4067         &.{},
4068     );
4069     try std.testing.expectEqual(RelinkDecision.full_link, changed_plan.decision);
4070     try std.testing.expectEqual(RelinkBlocker.input_reordered, changed_plan.blocker.?);
4071     try std.testing.expectEqual(@as(?usize, 0), changed_plan.blocking_change_index);
4072 }
4073 
4074 test "prepared incremental state plans full relinks for input deltas" {
4075     const allocator = std.testing.allocator;
4076     const options = model.LinkOptions{};
4077     var builder = try Builder.init(allocator, options);
4078     defer builder.deinit();
4079     try builder.addInput(.{ .name = "same.o", .bytes = "abc" });
4080     try builder.addInput(.{ .name = "changed.o", .bytes = "old" });
4081     try builder.addInput(.{ .name = "removed.o", .bytes = "gone" });
4082     try builder.addContribution("changed.o", 1, .section, ".text.changed", 1, ".text", 0x401000, 0x1000, 7, 16, 16);
4083 
4084     const manifest = try builder.finish();
4085     var state = try PreparedState.fromOwnedManifest(allocator, manifest);
4086     defer state.deinit(allocator);
4087 
4088     const plan = try planInputRelinkForTest(&state, allocator, options, &.{
4089         .{ .name = "same.o", .bytes = "abc" },
4090         .{ .name = "changed.o", .bytes = "new" },
4091         .{ .name = "added.o", .bytes = "fresh" },
4092     });
4093     try std.testing.expectEqual(RelinkDecision.full_link, plan.decision);
4094     try std.testing.expectEqual(RelinkBlocker.input_changed, plan.blocker.?);
4095     try std.testing.expectEqual(@as(?usize, 1), plan.blocking_change_index);
4096     try std.testing.expectEqual(@as(usize, 1), plan.input_summary.unchanged);
4097     try std.testing.expectEqual(@as(usize, 1), plan.input_summary.changed);
4098     try std.testing.expectEqual(@as(usize, 1), plan.input_summary.removed);
4099     try std.testing.expectEqual(@as(usize, 1), plan.input_summary.added);
4100     try std.testing.expectEqual(@as(usize, 1), plan.affected_contributions.retained);
4101     try std.testing.expectEqual(@as(u64, 7), plan.affected_contributions.retained_size);
4102 }
4103 
4104 test "prepared incremental state reports input additions before replacement extraction" {
4105     const allocator = std.testing.allocator;
4106     const options = model.LinkOptions{};
4107     var builder = try Builder.init(allocator, options);
4108     defer builder.deinit();
4109     try builder.addInput(.{ .name = "changed.o", .bytes = "old" });
4110     try builder.addInput(.{ .name = "same.o", .bytes = "abc" });
4111     try builder.addContribution("changed.o", 0, .section, ".text.changed", 1, ".text", 0x401000, 4, 3, 8, 16);
4112 
4113     const manifest = try builder.finish();
4114     var state = try PreparedState.fromOwnedManifest(allocator, manifest);
4115     defer state.deinit(allocator);
4116 
4117     const plan = try planChangedInputRelinkForTest(
4118         &state,
4119         allocator,
4120         options,
4121         &.{
4122             .{ .name = "changed.o", .bytes = "new" },
4123             .{ .name = "same.o", .bytes = "abc" },
4124             .{ .name = "added.o", .bytes = "fresh" },
4125         },
4126         &.{},
4127     );
4128     try std.testing.expectEqual(RelinkDecision.full_link, plan.decision);
4129     try std.testing.expectEqual(RelinkBlocker.input_added, plan.blocker.?);
4130     try std.testing.expectEqual(@as(?usize, 2), plan.blocking_change_index);
4131     try std.testing.expectEqual(@as(usize, 1), plan.input_summary.changed);
4132     try std.testing.expectEqual(@as(usize, 1), plan.input_summary.added);
4133 }
4134 
4135 test "prepared incremental state plans in-place relinks for changed input replacements" {
4136     const allocator = std.testing.allocator;
4137     const options = model.LinkOptions{};
4138     var builder = try Builder.init(allocator, options);
4139     defer builder.deinit();
4140     try builder.addInput(.{ .name = "same.o", .bytes = "abc" });
4141     try builder.addInput(.{ .name = "changed.o", .bytes = "old" });
4142     try builder.addContribution("changed.o", 1, .section, ".text.changed", 1, ".text", 0x401000, 4, 7, 16, 16);
4143 
4144     const manifest = try builder.finish();
4145     var state = try PreparedState.fromOwnedManifest(allocator, manifest);
4146     defer state.deinit(allocator);
4147 
4148     const plan = try planChangedInputRelinkForTest(
4149         &state,
4150         allocator,
4151         options,
4152         &.{
4153             .{ .name = "same.o", .bytes = "abc" },
4154             .{ .name = "changed.o", .bytes = "new" },
4155         },
4156         &.{
4157             .{ .input_name = "changed.o", .input_index = 1, .kind = .section, .name = ".text.changed", .ordinal = 1, .size = 9, .alignment = 16, .payload = "replacement" },
4158         },
4159     );
4160     try std.testing.expectEqual(RelinkDecision.in_place, plan.decision);
4161     try std.testing.expectEqual(@as(?RelinkBlocker, null), plan.blocker);
4162     try std.testing.expectEqual(@as(?usize, null), plan.blocking_change_index);
4163     try std.testing.expectEqual(@as(?usize, null), plan.blocking_replacement_index);
4164     try std.testing.expectEqual(@as(usize, 1), plan.input_summary.changed);
4165     try std.testing.expectEqual(@as(usize, 1), plan.affected_contributions.retained);
4166     try std.testing.expectEqual(@as(u64, 7), plan.affected_contributions.retained_size);
4167 }
4168 
4169 test "prepared incremental state applies in-place changed input relinks" {
4170     const allocator = std.testing.allocator;
4171     const options = model.LinkOptions{};
4172     var builder = try Builder.init(allocator, options);
4173     defer builder.deinit();
4174     try builder.addInput(.{ .name = "changed.o", .bytes = "old" });
4175     try builder.addContribution("changed.o", 0, .section, ".text", 1, ".text", 0x401000, 4, 3, 8, 16);
4176 
4177     const manifest = try builder.finish();
4178     var state = try PreparedState.fromOwnedManifest(allocator, manifest);
4179     defer state.deinit(allocator);
4180 
4181     var image = @as([16]u8, @splat(0xaa));
4182     const application = try applyChangedInputRelinkForTest(
4183         &state,
4184         allocator,
4185         image[0..],
4186         options,
4187         &.{.{ .name = "changed.o", .bytes = "new" }},
4188         &.{
4189             .{ .input_name = "changed.o", .input_index = 0, .kind = .section, .name = ".text", .ordinal = 1, .size = 5, .alignment = 16, .payload = "hello" },
4190         },
4191     );
4192 
4193     try std.testing.expectEqual(RelinkDecision.in_place, application.plan.decision);
4194     try std.testing.expectEqual(@as(usize, 1), application.contributions_written);
4195     try std.testing.expectEqual(@as(usize, 5), application.bytes_written);
4196     try std.testing.expectEqual(@as(usize, 3), application.zero_fill_bytes);
4197     try std.testing.expectEqualSlices(u8, "hello", image[4..9]);
4198     try std.testing.expectEqualSlices(u8, &.{ 0, 0, 0 }, image[9..12]);
4199     try std.testing.expectEqual(@as(u8, 0xaa), image[12]);
4200 }
4201 
4202 test "prepared incremental state applies accepted in-place changed input relinks" {
4203     const allocator = std.testing.allocator;
4204     const options = model.LinkOptions{};
4205     var builder = try Builder.init(allocator, options);
4206     defer builder.deinit();
4207     try builder.addInput(.{ .name = "changed.o", .bytes = "old" });
4208     try builder.addContribution("changed.o", 0, .section, ".text", 1, ".text", 0x401000, 4, 3, 8, 16);
4209 
4210     const manifest = try builder.finish();
4211     var state = try PreparedState.fromOwnedManifest(allocator, manifest);
4212     defer state.deinit(allocator);
4213 
4214     const inputs: []const model.Input = &.{.{ .name = "changed.o", .bytes = "new" }};
4215     const replacements: []const ReplacementContribution = &.{
4216         .{ .input_name = "changed.o", .input_index = 0, .kind = .section, .name = ".text", .ordinal = 1, .size = 5, .alignment = 16, .payload = "hello" },
4217     };
4218     var classified = try classifyTestInputs(allocator, state.manifest, inputs);
4219     defer classified.deinit(allocator);
4220     const changes = classified.changes;
4221 
4222     const accepted_plan = state.planChangedInputRelinkFromInputChanges(options, changes, replacements);
4223     try std.testing.expectEqual(RelinkDecision.in_place, accepted_plan.decision);
4224 
4225     var image = @as([16]u8, @splat(0xaa));
4226     const application = try state.applyAcceptedChangedInputRelink(
4227         image[0..],
4228         replacements,
4229         accepted_plan,
4230     );
4231 
4232     try std.testing.expectEqual(RelinkDecision.in_place, application.plan.decision);
4233     try std.testing.expectEqual(@as(usize, 1), application.contributions_written);
4234     try std.testing.expectEqual(@as(usize, 5), application.bytes_written);
4235     try std.testing.expectEqual(@as(usize, 3), application.zero_fill_bytes);
4236     try std.testing.expectEqualSlices(u8, "hello", image[4..9]);
4237     try std.testing.expectEqualSlices(u8, &.{ 0, 0, 0 }, image[9..12]);
4238 }
4239 
4240 test "prepared incremental state reports stale accepted relink replacements" {
4241     const allocator = std.testing.allocator;
4242     const options = model.LinkOptions{};
4243     var builder = try Builder.init(allocator, options);
4244     defer builder.deinit();
4245     try builder.addInput(.{ .name = "changed.o", .bytes = "old" });
4246     try builder.addContribution("changed.o", 0, .section, ".text", 1, ".text", 0x401000, 4, 3, 8, 16);
4247 
4248     const manifest = try builder.finish();
4249     var state = try PreparedState.fromOwnedManifest(allocator, manifest);
4250     defer state.deinit(allocator);
4251 
4252     var image = @as([16]u8, @splat(0xaa));
4253     const application = try state.applyAcceptedChangedInputRelink(
4254         image[0..],
4255         &.{
4256             .{ .input_name = "missing.o", .input_index = 9, .kind = .section, .name = ".text.missing", .ordinal = 1, .size = 4, .alignment = 16, .payload = "miss" },
4257         },
4258         .{
4259             .decision = .in_place,
4260             .input_summary = .{ .changed = 1 },
4261             .affected_contributions = .{ .retained = 1, .retained_size = 3 },
4262         },
4263     );
4264 
4265     try std.testing.expectEqual(RelinkDecision.full_link, application.plan.decision);
4266     try std.testing.expectEqual(RelinkBlocker.replacement_missing, application.plan.blocker.?);
4267     try std.testing.expectEqual(@as(?usize, 0), application.plan.blocking_replacement_index);
4268     try std.testing.expectEqual(@as(usize, 1), application.plan.input_summary.changed);
4269     try std.testing.expectEqual(@as(usize, 1), application.plan.affected_contributions.retained);
4270     try std.testing.expectEqual(@as(usize, 0), application.contributions_written);
4271     try std.testing.expectEqual(@as(u8, 0xaa), image[4]);
4272 }
4273 
4274 test "prepared incremental state updates manifest after in-place changed input relinks" {
4275     const allocator = std.testing.allocator;
4276     const options = model.LinkOptions{};
4277     var builder = try Builder.init(allocator, options);
4278     defer builder.deinit();
4279     try builder.addInput(.{ .name = "changed.o", .bytes = "old" });
4280     try builder.addContribution("changed.o", 0, .section, ".text", 1, ".text", 0x401000, 4, 3, 8, 16);
4281 
4282     const manifest = try builder.finish();
4283     var state = try PreparedState.fromOwnedManifest(allocator, manifest);
4284     defer state.deinit(allocator);
4285 
4286     const inputs: []const model.Input = &.{.{ .name = "changed.o", .bytes = "newer" }};
4287     const replacements: []const ReplacementContribution = &.{
4288         .{ .input_name = "changed.o", .input_index = 0, .kind = .section, .name = ".text", .ordinal = 1, .size = 5, .alignment = 4, .payload = "hello" },
4289     };
4290     var classified = try classifyTestInputs(allocator, state.manifest, inputs);
4291     defer classified.deinit(allocator);
4292     const changes = classified.changes;
4293 
4294     var image = @as([16]u8, @splat(0xaa));
4295     const application = try state.applyChangedInputRelinkFromInputChanges(
4296         options,
4297         changes,
4298         image[0..],
4299         replacements,
4300     );
4301     try std.testing.expectEqual(RelinkDecision.in_place, application.plan.decision);
4302 
4303     try state.updateManifestForChangedInputRelinkFromInputChanges(inputs, changes, replacements, &.{}, 0);
4304 
4305     try std.testing.expect(state.canReuseFor(options, inputs));
4306     try std.testing.expectEqual(@as(u64, 5), state.manifest.inputs[0].size);
4307     try std.testing.expectEqual(hashBytes("newer"), state.manifest.inputs[0].hash);
4308     try std.testing.expectEqual(@as(u64, 5), state.manifest.contributions[0].size);
4309     try std.testing.expectEqual(@as(u64, 8), state.manifest.contributions[0].reserved_size);
4310     try std.testing.expectEqual(@as(u64, 16), state.manifest.contributions[0].alignment);
4311 }
4312 
4313 test "prepared incremental state preserves fileless contribution metadata after relink" {
4314     const allocator = std.testing.allocator;
4315     const options = model.LinkOptions{};
4316     var builder = try Builder.init(allocator, options);
4317     defer builder.deinit();
4318     try builder.addInput(.{ .name = "changed.o", .bytes = "old" });
4319     try builder.addContributionWithFileSize("changed.o", 0, .section, ".tbss", 1, ".tbss", 0x402000, 8, 8, 0, 16, 4);
4320 
4321     const manifest = try builder.finish();
4322     var state = try PreparedState.fromOwnedManifest(allocator, manifest);
4323     defer state.deinit(allocator);
4324 
4325     const inputs: []const model.Input = &.{.{ .name = "changed.o", .bytes = "newer" }};
4326     const replacements: []const ReplacementContribution = &.{
4327         .{ .input_name = "changed.o", .input_index = 0, .kind = .section, .name = ".tbss", .ordinal = 1, .size = 8, .alignment = 4 },
4328     };
4329     var classified = try classifyTestInputs(allocator, state.manifest, inputs);
4330     defer classified.deinit(allocator);
4331     const changes = classified.changes;
4332 
4333     var image = @as([16]u8, @splat(0xaa));
4334     const application = try state.applyChangedInputRelinkFromInputChanges(
4335         options,
4336         changes,
4337         image[0..],
4338         replacements,
4339     );
4340     try std.testing.expectEqual(RelinkDecision.in_place, application.plan.decision);
4341     try std.testing.expectEqual(@as(usize, 1), application.contributions_written);
4342     try std.testing.expectEqual(@as(usize, 0), application.bytes_written);
4343 
4344     try state.updateManifestForChangedInputRelinkFromInputChanges(inputs, changes, replacements, &.{}, 0);
4345 
4346     try std.testing.expect(state.canReuseFor(options, inputs));
4347     try std.testing.expectEqual(@as(u64, 8), state.manifest.contributions[0].size);
4348     try std.testing.expectEqual(@as(u64, 0), state.manifest.contributions[0].file_size);
4349     try std.testing.expectEqual(@as(u8, 0xaa), image[8]);
4350 }
4351 
4352 test "prepared incremental state updates manifest from accepted changed input plan" {
4353     const allocator = std.testing.allocator;
4354     const options = model.LinkOptions{};
4355     var builder = try Builder.init(allocator, options);
4356     defer builder.deinit();
4357     try builder.addInput(.{ .name = "changed.o", .bytes = "old" });
4358     try builder.addContribution("changed.o", 0, .section, ".text", 1, ".text", 0x401000, 4, 3, 8, 16);
4359 
4360     const manifest = try builder.finish();
4361     var state = try PreparedState.fromOwnedManifest(allocator, manifest);
4362     defer state.deinit(allocator);
4363 
4364     const inputs: []const model.Input = &.{.{ .name = "changed.o", .bytes = "newer" }};
4365     const replacements: []const ReplacementContribution = &.{
4366         .{ .input_name = "changed.o", .input_index = 0, .kind = .section, .name = ".text", .ordinal = 1, .size = 5, .alignment = 4, .payload = "hello" },
4367     };
4368     var classified = try classifyTestInputs(allocator, state.manifest, inputs);
4369     defer classified.deinit(allocator);
4370     const changes = classified.changes;
4371 
4372     const accepted_plan = state.planChangedInputRelinkFromInputChanges(options, changes, replacements);
4373     try std.testing.expectEqual(RelinkDecision.in_place, accepted_plan.decision);
4374 
4375     try state.updateManifestForAcceptedChangedInputRelinkFromInputChanges(
4376         inputs,
4377         changes,
4378         replacements,
4379         &.{},
4380         0,
4381         accepted_plan,
4382     );
4383 
4384     try std.testing.expect(state.canReuseFor(options, inputs));
4385     try std.testing.expectEqual(@as(u64, 5), state.manifest.inputs[0].size);
4386     try std.testing.expectEqual(hashBytes("newer"), state.manifest.inputs[0].hash);
4387     try std.testing.expectEqual(@as(u64, 5), state.manifest.contributions[0].size);
4388 }
4389 
4390 test "prepared incremental state updates section sizes from candidate relinks" {
4391     const allocator = std.testing.allocator;
4392     const options = model.LinkOptions{};
4393     var builder = try Builder.init(allocator, options);
4394     defer builder.deinit();
4395     try builder.addInput(.{ .name = "changed.o", .bytes = "old" });
4396     try builder.addSection(".text", 0x401000, 4, 3, 8, 16);
4397     try builder.addContribution("changed.o", 0, .section, ".text", 1, ".text", 0x401000, 4, 3, 8, 16);
4398 
4399     const manifest = try builder.finish();
4400     var state = try PreparedState.fromOwnedManifest(allocator, manifest);
4401     defer state.deinit(allocator);
4402 
4403     var candidate_builder = try Builder.init(allocator, options);
4404     defer candidate_builder.deinit();
4405     try candidate_builder.addInput(.{ .name = "changed.o", .bytes = "new" });
4406     try candidate_builder.addSection(".text", 0x401000, 4, 5, 8, 16);
4407     try candidate_builder.addContribution("changed.o", 0, .section, ".text", 1, ".text", 0x401000, 4, 5, 8, 16);
4408     var candidate_manifest = try candidate_builder.finish();
4409     defer candidate_manifest.deinit(allocator);
4410 
4411     const inputs: []const model.Input = &.{.{ .name = "changed.o", .bytes = "new" }};
4412     const replacements: []const ReplacementContribution = &.{
4413         .{ .input_name = "changed.o", .input_index = 0, .kind = .section, .name = ".text", .ordinal = 1, .size = 5, .alignment = 16, .output_section_name = ".text", .address = 0x401000, .file_offset = 4, .reserved_size = 8, .payload = "hello" },
4414     };
4415     var classified = try classifyTestInputs(allocator, state.manifest, inputs);
4416     defer classified.deinit(allocator);
4417     const changes = classified.changes;
4418     const accepted_plan = state.planChangedInputRelinkFromInputChanges(options, changes, replacements);
4419     try std.testing.expectEqual(RelinkDecision.in_place, accepted_plan.decision);
4420 
4421     try state.updateManifestForAcceptedCandidateRelinkFromInputChanges(
4422         allocator,
4423         inputs,
4424         changes,
4425         replacements,
4426         candidate_manifest,
4427         accepted_plan,
4428     );
4429 
4430     try std.testing.expect(state.canReuseFor(options, inputs));
4431     try std.testing.expectEqual(@as(u64, 5), state.manifest.sections[0].size);
4432     try std.testing.expectEqual(@as(u64, 5), state.manifest.contributions[0].size);
4433 }
4434 
4435 test "prepared incremental state updates discarded contributions from candidate relinks" {
4436     const allocator = std.testing.allocator;
4437     const options = model.LinkOptions{};
4438     var builder = try Builder.init(allocator, options);
4439     defer builder.deinit();
4440     try builder.addInput(.{ .name = "changed.o", .bytes = "old" });
4441     try builder.addDiscardedContribution("changed.o", 0, ".text.dead", 1, .discarded, 3, 16);
4442 
4443     const manifest = try builder.finish();
4444     var state = try PreparedState.fromOwnedManifest(allocator, manifest);
4445     defer state.deinit(allocator);
4446 
4447     var candidate_builder = try Builder.init(allocator, options);
4448     defer candidate_builder.deinit();
4449     try candidate_builder.addInput(.{ .name = "changed.o", .bytes = "new" });
4450     try candidate_builder.addDiscardedContribution("changed.o", 0, ".text.dead.new", 2, .identical_code_folded, 7, 32);
4451     var candidate_manifest = try candidate_builder.finish();
4452     defer candidate_manifest.deinit(allocator);
4453 
4454     const inputs: []const model.Input = &.{.{ .name = "changed.o", .bytes = "new" }};
4455     var classified = try classifyTestInputs(allocator, state.manifest, inputs);
4456     defer classified.deinit(allocator);
4457     const changes = classified.changes;
4458     const accepted_plan = state.planChangedInputRelinkFromInputChanges(options, changes, &.{});
4459     try std.testing.expectEqual(RelinkDecision.in_place, accepted_plan.decision);
4460 
4461     try state.updateManifestForAcceptedCandidateRelinkFromInputChanges(
4462         allocator,
4463         inputs,
4464         changes,
4465         &.{},
4466         candidate_manifest,
4467         accepted_plan,
4468     );
4469     candidate_manifest.deinit(allocator);
4470     candidate_manifest = Manifest.empty();
4471 
4472     try std.testing.expect(state.canReuseFor(options, inputs));
4473     try std.testing.expectEqual(@as(usize, 1), state.manifest.discarded_contributions.len);
4474     try std.testing.expectEqualStrings(".text.dead.new", state.manifest.string(state.manifest.discarded_contributions[0].name_id));
4475     try std.testing.expectEqual(DiscardReason.identical_code_folded, state.manifest.discarded_contributions[0].reason);
4476     try std.testing.expectEqual(@as(u64, 7), state.manifest.discarded_contributions[0].size);
4477     try std.testing.expectEqual(@as(u64, 32), state.manifest.discarded_contributions[0].alignment);
4478     try std.testing.expectEqual(@as(usize, 1), state.input_contributions[0].discarded);
4479     try std.testing.expectEqual(@as(u64, 7), state.input_contributions[0].discarded_size);
4480 }
4481 
4482 test "prepared incremental state updates discarded contributions on parsed manifests" {
4483     const allocator = std.testing.allocator;
4484     const options = model.LinkOptions{};
4485     var builder = try Builder.init(allocator, options);
4486     defer builder.deinit();
4487     try builder.addInput(.{ .name = "changed.o", .bytes = "old" });
4488     try builder.addDiscardedContribution("changed.o", 0, ".text.dead", 1, .discarded, 3, 16);
4489 
4490     var built = try builder.finish();
4491     const binary = try built.formatBinaryAlloc(allocator);
4492     defer allocator.free(binary);
4493     built.deinit(allocator);
4494 
4495     var state = try PreparedState.fromOwnedManifest(
4496         allocator,
4497         try Manifest.fromBinary(allocator, binary),
4498     );
4499     defer state.deinit(allocator);
4500 
4501     var candidate_builder = try Builder.init(allocator, options);
4502     defer candidate_builder.deinit();
4503     try candidate_builder.addInput(.{ .name = "changed.o", .bytes = "new" });
4504     try candidate_builder.addDiscardedContribution("changed.o", 0, ".text.dead.new", 2, .identical_code_folded, 7, 32);
4505     var candidate_manifest = try candidate_builder.finish();
4506     defer candidate_manifest.deinit(allocator);
4507 
4508     const inputs: []const model.Input = &.{.{ .name = "changed.o", .bytes = "new" }};
4509     var classified = try classifyTestInputs(allocator, state.manifest, inputs);
4510     defer classified.deinit(allocator);
4511     const changes = classified.changes;
4512     const accepted_plan = state.planChangedInputRelinkFromInputChanges(options, changes, &.{});
4513     try std.testing.expectEqual(RelinkDecision.in_place, accepted_plan.decision);
4514 
4515     try state.updateManifestForAcceptedCandidateRelinkFromInputChanges(
4516         allocator,
4517         inputs,
4518         changes,
4519         &.{},
4520         candidate_manifest,
4521         accepted_plan,
4522     );
4523     candidate_manifest.deinit(allocator);
4524     candidate_manifest = Manifest.empty();
4525 
4526     try std.testing.expectEqual(@as(usize, 1), state.manifest.discarded_contributions.len);
4527     try std.testing.expectEqualStrings(".text.dead.new", state.manifest.string(state.manifest.discarded_contributions[0].name_id));
4528 }
4529 
4530 test "prepared incremental state refreshes external targets from candidate relinks" {
4531     const allocator = std.testing.allocator;
4532     const options = model.LinkOptions{};
4533     var builder = try Builder.init(allocator, options);
4534     defer builder.deinit();
4535     try builder.addInput(.{ .name = "changed.o", .bytes = "old" });
4536     try builder.addExternalTarget("moved_symbol", 0x401000, 4);
4537     try builder.addExternalTarget("stale_symbol", 0x401010, 8);
4538 
4539     var built = try builder.finish();
4540     const binary = try built.formatBinaryAlloc(allocator);
4541     defer allocator.free(binary);
4542     built.deinit(allocator);
4543 
4544     var state = try PreparedState.fromOwnedManifest(
4545         allocator,
4546         try Manifest.fromBinary(allocator, binary),
4547     );
4548     defer state.deinit(allocator);
4549 
4550     var candidate_builder = try Builder.init(allocator, options);
4551     defer candidate_builder.deinit();
4552     try candidate_builder.addInput(.{ .name = "changed.o", .bytes = "new" });
4553     try candidate_builder.addExternalTarget("moved_symbol", 0x401004, 4);
4554     var candidate_manifest = try candidate_builder.finish();
4555     defer candidate_manifest.deinit(allocator);
4556 
4557     const inputs: []const model.Input = &.{.{ .name = "changed.o", .bytes = "new" }};
4558     var classified = try classifyTestInputs(allocator, state.manifest, inputs);
4559     defer classified.deinit(allocator);
4560     const changes = classified.changes;
4561     const accepted_plan = state.planChangedInputRelinkFromInputChanges(options, changes, &.{});
4562     try std.testing.expectEqual(RelinkDecision.in_place, accepted_plan.decision);
4563 
4564     try state.updateManifestForAcceptedCandidateRelinkFromInputChanges(
4565         allocator,
4566         inputs,
4567         changes,
4568         &.{},
4569         candidate_manifest,
4570         accepted_plan,
4571     );
4572     candidate_manifest.deinit(allocator);
4573     candidate_manifest = Manifest.empty();
4574 
4575     try std.testing.expectEqual(@as(usize, 1), state.manifest.external_targets.len);
4576     try std.testing.expectEqualStrings("moved_symbol", state.manifest.string(state.manifest.external_targets[0].name_id));
4577     try std.testing.expectEqual(@as(i128, 0x401004), state.manifest.external_targets[0].address());
4578 
4579     const refreshed_binary = try state.manifest.formatBinaryAlloc(allocator);
4580     defer allocator.free(refreshed_binary);
4581     var refreshed = try Manifest.fromBinary(allocator, refreshed_binary);
4582     defer refreshed.deinit(allocator);
4583     try std.testing.expectEqual(@as(usize, 1), refreshed.external_targets.len);
4584     try std.testing.expectEqualStrings("moved_symbol", refreshed.string(refreshed.external_targets[0].name_id));
4585 }
4586 
4587 test "prepared incremental state rejects candidate section layout drift" {
4588     const allocator = std.testing.allocator;
4589     const options = model.LinkOptions{};
4590     var builder = try Builder.init(allocator, options);
4591     defer builder.deinit();
4592     try builder.addInput(.{ .name = "changed.o", .bytes = "old" });
4593     try builder.addSection(".text", 0x401000, 4, 3, 8, 16);
4594     try builder.addContribution("changed.o", 0, .section, ".text", 1, ".text", 0x401000, 4, 3, 8, 16);
4595 
4596     const manifest = try builder.finish();
4597     var state = try PreparedState.fromOwnedManifest(allocator, manifest);
4598     defer state.deinit(allocator);
4599 
4600     var candidate_builder = try Builder.init(allocator, options);
4601     defer candidate_builder.deinit();
4602     try candidate_builder.addInput(.{ .name = "changed.o", .bytes = "new" });
4603     try candidate_builder.addSection(".text", 0x401010, 4, 5, 8, 16);
4604     try candidate_builder.addContribution("changed.o", 0, .section, ".text", 1, ".text", 0x401010, 4, 5, 8, 16);
4605     var candidate_manifest = try candidate_builder.finish();
4606     defer candidate_manifest.deinit(allocator);
4607 
4608     try std.testing.expectError(
4609         error.SectionLayoutChanged,
4610         updateManifestForCandidateRelinkForTest(
4611             &state,
4612             allocator,
4613             &.{.{ .name = "changed.o", .bytes = "new" }},
4614             &.{
4615                 .{ .input_name = "changed.o", .input_index = 0, .kind = .section, .name = ".text", .ordinal = 1, .size = 5, .alignment = 16, .output_section_name = ".text", .address = 0x401010, .file_offset = 4, .reserved_size = 8, .payload = "hello" },
4616             },
4617             candidate_manifest,
4618         ),
4619     );
4620     try std.testing.expectEqual(@as(u64, 3), state.manifest.sections[0].size);
4621     try std.testing.expectEqual(@as(u64, 3), state.manifest.contributions[0].size);
4622 }
4623 
4624 test "replacement extraction maps current inputs to recorded inputs" {
4625     const allocator = std.testing.allocator;
4626     const options = model.LinkOptions{};
4627     var builder = try Builder.init(allocator, options);
4628     defer builder.deinit();
4629     try builder.addInput(.{ .name = "a.o", .bytes = "same" });
4630     try builder.addInput(.{ .name = "b.o", .bytes = "old" });
4631     try builder.addContribution("b.o", 1, .section, ".text.b", 1, ".text", 0x401000, 4, 3, 8, 16);
4632 
4633     const manifest = try builder.finish();
4634     var state = try PreparedState.fromOwnedManifest(allocator, manifest);
4635     defer state.deinit(allocator);
4636 
4637     var classified = try classifyTestInputs(allocator, state.manifest, &.{
4638         .{ .name = "b.o", .bytes = "new" },
4639         .{ .name = "a.o", .bytes = "same" },
4640     });
4641     defer classified.deinit(allocator);
4642     const changes = classified.changes;
4643 
4644     var candidate_builder = try Builder.init(allocator, options);
4645     defer candidate_builder.deinit();
4646     try candidate_builder.addInput(.{ .name = "b.o", .bytes = "new" });
4647     try candidate_builder.addInput(.{ .name = "a.o", .bytes = "same" });
4648     try candidate_builder.addContribution("b.o", 0, .section, ".text.b", 1, ".text", 0x401000, 4, 5, 8, 16);
4649     try candidate_builder.addContribution("a.o", 1, .section, ".text.a", 1, ".text", 0x401040, 16, 4, 4, 16);
4650     var candidate_manifest = try candidate_builder.finish();
4651     defer candidate_manifest.deinit(allocator);
4652 
4653     var candidate_image = @as([32]u8, @splat(0xaa));
4654     @memcpy(candidate_image[4..9], "hello");
4655     @memcpy(candidate_image[16..20], "same");
4656 
4657     const replacements = try replacementContributionsFromImage(allocator, &candidate_image, candidate_manifest, changes);
4658     defer allocator.free(replacements);
4659 
4660     try std.testing.expectEqual(@as(usize, 1), replacements.len);
4661     try std.testing.expectEqualStrings("b.o", replacements[0].input_name);
4662     try std.testing.expectEqual(@as(usize, 1), replacements[0].input_index);
4663     try std.testing.expectEqualStrings(".text.b", replacements[0].name);
4664     try std.testing.expectEqualStrings(".text", replacements[0].output_section_name.?);
4665     try std.testing.expectEqual(@as(?u64, 0x401000), replacements[0].address);
4666     try std.testing.expectEqual(@as(?u64, 4), replacements[0].file_offset);
4667     try std.testing.expectEqual(@as(?u64, 8), replacements[0].reserved_size);
4668     try std.testing.expectEqualSlices(u8, "hello", replacements[0].payload);
4669 
4670     var old_image = @as([16]u8, @splat(0xaa));
4671     const before = old_image;
4672     const application = try applyChangedInputRelinkForTest(
4673         &state,
4674         allocator,
4675         old_image[0..],
4676         options,
4677         &.{
4678             .{ .name = "b.o", .bytes = "new" },
4679             .{ .name = "a.o", .bytes = "same" },
4680         },
4681         replacements,
4682     );
4683 
4684     try std.testing.expectEqual(RelinkDecision.full_link, application.plan.decision);
4685     try std.testing.expectEqual(RelinkBlocker.input_reordered, application.plan.blocker.?);
4686     try std.testing.expectEqual(@as(usize, 0), application.contributions_written);
4687     try std.testing.expectEqualSlices(u8, &before, &old_image);
4688 }
4689 
4690 test "replacement extraction handles sparse changed current inputs" {
4691     var arena_state = std.heap.ArenaAllocator.init(std.testing.allocator);
4692     defer arena_state.deinit();
4693     const allocator = arena_state.allocator();
4694     const options = model.LinkOptions{};
4695     const input_count = 48;
4696 
4697     const old_inputs = try allocator.alloc(model.Input, input_count);
4698     const new_inputs = try allocator.alloc(model.Input, input_count);
4699 
4700     var builder = try Builder.init(allocator, options);
4701     defer builder.deinit();
4702     for (old_inputs, new_inputs, 0..) |*old_input, *new_input, input_index| {
4703         const name = try std.fmt.allocPrint(allocator, "obj_{d}.o", .{input_index});
4704         old_input.* = .{
4705             .name = name,
4706             .bytes = if (input_index + 1 == input_count) "old" else "same",
4707         };
4708         new_input.* = .{
4709             .name = name,
4710             .bytes = if (input_index + 1 == input_count) "new" else "same",
4711         };
4712         try builder.addInput(old_input.*);
4713     }
4714     try builder.addContribution(old_inputs[input_count - 1].name, input_count - 1, .section, ".text.changed", 1, ".text", 0x401000, 4, 3, 8, 16);
4715 
4716     const manifest = try builder.finish();
4717     var state = try PreparedState.fromOwnedManifest(allocator, manifest);
4718     defer state.deinit(allocator);
4719 
4720     var classified = try classifyTestInputs(
4721         allocator,
4722         state.manifest,
4723         new_inputs,
4724     );
4725     defer classified.deinit(allocator);
4726     const changes = classified.changes;
4727     try std.testing.expectEqual(@as(usize, 1), changes.summary.changed);
4728 
4729     var candidate_builder = try Builder.init(allocator, options);
4730     defer candidate_builder.deinit();
4731     for (new_inputs) |input| try candidate_builder.addInput(input);
4732     try candidate_builder.addContribution(new_inputs[input_count - 1].name, input_count - 1, .section, ".text.changed", 1, ".text", 0x401000, 4, 5, 8, 16);
4733     try candidate_builder.addContribution(new_inputs[0].name, 0, .section, ".text.same", 1, ".text", 0x401040, 16, 4, 4, 16);
4734     var candidate_manifest = try candidate_builder.finish();
4735     defer candidate_manifest.deinit(allocator);
4736 
4737     var candidate_image = @as([32]u8, @splat(0xaa));
4738     @memcpy(candidate_image[4..9], "hello");
4739     @memcpy(candidate_image[16..20], "same");
4740 
4741     const replacements = try replacementContributionsFromImage(allocator, &candidate_image, candidate_manifest, changes);
4742     defer if (replacements.len != 0) allocator.free(replacements);
4743 
4744     try std.testing.expectEqual(@as(usize, 1), replacements.len);
4745     try std.testing.expectEqualStrings(old_inputs[input_count - 1].name, replacements[0].input_name);
4746     try std.testing.expectEqual(@as(usize, input_count - 1), replacements[0].input_index);
4747     try std.testing.expectEqualStrings(".text.changed", replacements[0].name);
4748     try std.testing.expectEqualSlices(u8, "hello", replacements[0].payload);
4749 }
4750 
4751 test "replacement extraction rejects out-of-range candidate payloads" {
4752     const allocator = std.testing.allocator;
4753     const options = model.LinkOptions{};
4754     var builder = try Builder.init(allocator, options);
4755     defer builder.deinit();
4756     try builder.addInput(.{ .name = "a.o", .bytes = "old" });
4757 
4758     const manifest = try builder.finish();
4759     var state = try PreparedState.fromOwnedManifest(allocator, manifest);
4760     defer state.deinit(allocator);
4761 
4762     var classified = try classifyTestInputs(
4763         allocator,
4764         state.manifest,
4765         &.{.{ .name = "a.o", .bytes = "new" }},
4766     );
4767     defer classified.deinit(allocator);
4768     const changes = classified.changes;
4769 
4770     var candidate_builder = try Builder.init(allocator, options);
4771     defer candidate_builder.deinit();
4772     try candidate_builder.addInput(.{ .name = "a.o", .bytes = "new" });
4773     try candidate_builder.addContribution("a.o", 0, .section, ".text", 1, ".text", 0x401000, 4, 8, 8, 16);
4774     var candidate_manifest = try candidate_builder.finish();
4775     defer candidate_manifest.deinit(allocator);
4776 
4777     var candidate_image = @as([8]u8, @splat(0xaa));
4778     try std.testing.expectError(
4779         error.PatchRangeOutOfBounds,
4780         replacementContributionsFromImage(allocator, &candidate_image, candidate_manifest, changes),
4781     );
4782 }
4783 
4784 test "candidate relink full-links changed input layout drift" {
4785     const allocator = std.testing.allocator;
4786     const options = model.LinkOptions{};
4787     var builder = try Builder.init(allocator, options);
4788     defer builder.deinit();
4789     try builder.addInput(.{ .name = "changed.o", .bytes = "old" });
4790     try builder.addContribution("changed.o", 0, .section, ".text", 1, ".text", 0x401000, 4, 3, 8, 16);
4791 
4792     const manifest = try builder.finish();
4793     var state = try PreparedState.fromOwnedManifest(allocator, manifest);
4794     defer state.deinit(allocator);
4795 
4796     var candidate_builder = try Builder.init(allocator, options);
4797     defer candidate_builder.deinit();
4798     try candidate_builder.addInput(.{ .name = "changed.o", .bytes = "new" });
4799     try candidate_builder.addContribution("changed.o", 0, .section, ".text", 1, ".text", 0x401010, 12, 3, 8, 16);
4800     var candidate_manifest = try candidate_builder.finish();
4801     defer candidate_manifest.deinit(allocator);
4802 
4803     var old_image = @as([24]u8, @splat(0xaa));
4804     const before = old_image;
4805     var candidate_image = @as([24]u8, @splat(0xbb));
4806     @memcpy(candidate_image[12..15], "new");
4807 
4808     const application = try applyChangedInputRelinkFromCandidateForTest(
4809         &state,
4810         allocator,
4811         old_image[0..],
4812         options,
4813         &.{.{ .name = "changed.o", .bytes = "new" }},
4814         &candidate_image,
4815         candidate_manifest,
4816     );
4817 
4818     try std.testing.expectEqual(RelinkDecision.full_link, application.plan.decision);
4819     try std.testing.expectEqual(RelinkBlocker.replacement_layout_changed, application.plan.blocker.?);
4820     try std.testing.expectEqual(@as(?usize, 0), application.plan.blocking_replacement_index);
4821     try std.testing.expectEqual(@as(usize, 0), application.contributions_written);
4822     try std.testing.expectEqualSlices(u8, &before, &old_image);
4823 }
4824 
4825 test "candidate relink accepts fileless changed input contributions" {
4826     const allocator = std.testing.allocator;
4827     const options = model.LinkOptions{};
4828     var builder = try Builder.init(allocator, options);
4829     defer builder.deinit();
4830     try builder.addInput(.{ .name = "tls.o", .bytes = "old" });
4831     try builder.addContributionWithFileSize("tls.o", 0, .section, ".tbss", 1, ".tbss", 0x402000, 8, 8, 0, 16, 4);
4832 
4833     const manifest = try builder.finish();
4834     var state = try PreparedState.fromOwnedManifest(allocator, manifest);
4835     defer state.deinit(allocator);
4836 
4837     var candidate_builder = try Builder.init(allocator, options);
4838     defer candidate_builder.deinit();
4839     try candidate_builder.addInput(.{ .name = "tls.o", .bytes = "new" });
4840     try candidate_builder.addContributionWithFileSize("tls.o", 0, .section, ".tbss", 1, ".tbss", 0x402000, 8, 8, 0, 16, 4);
4841     var candidate_manifest = try candidate_builder.finish();
4842     defer candidate_manifest.deinit(allocator);
4843 
4844     var old_image = @as([32]u8, @splat(0xaa));
4845     const before = old_image;
4846     const candidate_image = @as([32]u8, @splat(0xbb));
4847 
4848     const application = try applyChangedInputRelinkFromCandidateForTest(
4849         &state,
4850         allocator,
4851         old_image[0..],
4852         options,
4853         &.{.{ .name = "tls.o", .bytes = "new" }},
4854         &candidate_image,
4855         candidate_manifest,
4856     );
4857 
4858     try std.testing.expectEqual(RelinkDecision.in_place, application.plan.decision);
4859     try std.testing.expectEqual(@as(usize, 1), application.contributions_written);
4860     try std.testing.expectEqual(@as(usize, 0), application.bytes_written);
4861     try std.testing.expectEqual(@as(usize, 0), application.zero_fill_bytes);
4862     try std.testing.expectEqualSlices(u8, &before, &old_image);
4863 }
4864 
4865 test "prepared incremental state applies changed input relinks from candidate image" {
4866     const allocator = std.testing.allocator;
4867     const options = model.LinkOptions{};
4868     var builder = try Builder.init(allocator, options);
4869     defer builder.deinit();
4870     try builder.addInput(.{ .name = "a.o", .bytes = "same" });
4871     try builder.addInput(.{ .name = "b.o", .bytes = "old" });
4872     try builder.addContribution("b.o", 1, .section, ".text.b", 1, ".text", 0x401000, 4, 3, 8, 16);
4873 
4874     const manifest = try builder.finish();
4875     var state = try PreparedState.fromOwnedManifest(allocator, manifest);
4876     defer state.deinit(allocator);
4877 
4878     var candidate_builder = try Builder.init(allocator, options);
4879     defer candidate_builder.deinit();
4880     try candidate_builder.addInput(.{ .name = "a.o", .bytes = "same" });
4881     try candidate_builder.addInput(.{ .name = "b.o", .bytes = "new" });
4882     try candidate_builder.addContribution("a.o", 0, .section, ".text.a", 1, ".text", 0x401040, 16, 4, 4, 16);
4883     try candidate_builder.addContribution("b.o", 1, .section, ".text.b", 1, ".text", 0x401000, 4, 5, 8, 16);
4884     var candidate_manifest = try candidate_builder.finish();
4885     defer candidate_manifest.deinit(allocator);
4886 
4887     var candidate_image = @as([32]u8, @splat(0xaa));
4888     @memcpy(candidate_image[4..9], "hello");
4889     @memcpy(candidate_image[16..20], "same");
4890 
4891     var old_image = @as([16]u8, @splat(0xaa));
4892     const application = try applyChangedInputRelinkFromCandidateForTest(
4893         &state,
4894         allocator,
4895         old_image[0..],
4896         options,
4897         &.{
4898             .{ .name = "a.o", .bytes = "same" },
4899             .{ .name = "b.o", .bytes = "new" },
4900         },
4901         &candidate_image,
4902         candidate_manifest,
4903     );
4904 
4905     try std.testing.expectEqual(RelinkDecision.in_place, application.plan.decision);
4906     try std.testing.expectEqual(@as(usize, 1), application.contributions_written);
4907     try std.testing.expectEqual(@as(usize, 5), application.bytes_written);
4908     try std.testing.expectEqual(@as(usize, 3), application.zero_fill_bytes);
4909     try std.testing.expectEqualSlices(u8, "hello", old_image[4..9]);
4910     try std.testing.expectEqualSlices(u8, &.{ 0, 0, 0 }, old_image[9..12]);
4911 }
4912 
4913 test "prepared incremental state rejects replacements for unchanged inputs" {
4914     const allocator = std.testing.allocator;
4915     const options = model.LinkOptions{};
4916     var builder = try Builder.init(allocator, options);
4917     defer builder.deinit();
4918     try builder.addInput(.{ .name = "unchanged.o", .bytes = "same" });
4919     try builder.addContribution("unchanged.o", 0, .section, ".text", 1, ".text", 0x401000, 4, 3, 8, 16);
4920 
4921     const manifest = try builder.finish();
4922     var state = try PreparedState.fromOwnedManifest(allocator, manifest);
4923     defer state.deinit(allocator);
4924 
4925     const plan = try planChangedInputRelinkForTest(
4926         &state,
4927         allocator,
4928         options,
4929         &.{.{ .name = "unchanged.o", .bytes = "same" }},
4930         &.{
4931             .{ .input_name = "unchanged.o", .input_index = 0, .kind = .section, .name = ".text", .ordinal = 1, .size = 5, .alignment = 16, .payload = "hello" },
4932         },
4933     );
4934 
4935     try std.testing.expectEqual(RelinkDecision.full_link, plan.decision);
4936     try std.testing.expectEqual(RelinkBlocker.replacement_not_changed, plan.blocker.?);
4937     try std.testing.expectEqual(@as(?usize, 0), plan.blocking_change_index);
4938     try std.testing.expectEqual(@as(?usize, 0), plan.blocking_replacement_index);
4939     try std.testing.expectEqual(@as(usize, 1), plan.affected_contributions.retained);
4940 }
4941 
4942 test "prepared incremental state rejects extra replacements outside changed inputs" {
4943     const allocator = std.testing.allocator;
4944     const options = model.LinkOptions{};
4945     var builder = try Builder.init(allocator, options);
4946     defer builder.deinit();
4947     try builder.addInput(.{ .name = "changed.o", .bytes = "old" });
4948     try builder.addInput(.{ .name = "unchanged.o", .bytes = "same" });
4949     try builder.addContribution("changed.o", 0, .section, ".text.changed", 1, ".text", 0x401000, 4, 3, 8, 16);
4950     try builder.addContribution("unchanged.o", 1, .section, ".text.unchanged", 1, ".text", 0x401040, 16, 3, 8, 16);
4951 
4952     const manifest = try builder.finish();
4953     var state = try PreparedState.fromOwnedManifest(allocator, manifest);
4954     defer state.deinit(allocator);
4955 
4956     var image = @as([32]u8, @splat(0xaa));
4957     const application = try applyChangedInputRelinkForTest(
4958         &state,
4959         allocator,
4960         image[0..],
4961         options,
4962         &.{
4963             .{ .name = "changed.o", .bytes = "new" },
4964             .{ .name = "unchanged.o", .bytes = "same" },
4965         },
4966         &.{
4967             .{ .input_name = "changed.o", .input_index = 0, .kind = .section, .name = ".text.changed", .ordinal = 1, .size = 5, .alignment = 16, .payload = "hello" },
4968             .{ .input_name = "unchanged.o", .input_index = 1, .kind = .section, .name = ".text.unchanged", .ordinal = 1, .size = 5, .alignment = 16, .payload = "world" },
4969         },
4970     );
4971 
4972     try std.testing.expectEqual(RelinkDecision.full_link, application.plan.decision);
4973     try std.testing.expectEqual(RelinkBlocker.replacement_not_changed, application.plan.blocker.?);
4974     try std.testing.expectEqual(@as(?usize, 1), application.plan.blocking_change_index);
4975     try std.testing.expectEqual(@as(?usize, 1), application.plan.blocking_replacement_index);
4976     try std.testing.expectEqual(@as(usize, 0), application.contributions_written);
4977     for (image) |byte| try std.testing.expectEqual(@as(u8, 0xaa), byte);
4978 }
4979 
4980 test "prepared incremental state reports missing replacements before extra replacements" {
4981     const allocator = std.testing.allocator;
4982     const options = model.LinkOptions{};
4983     const changed_names = [_][]const u8{
4984         "changed0.o",
4985         "changed1.o",
4986         "changed2.o",
4987         "changed3.o",
4988         "changed4.o",
4989         "changed5.o",
4990         "changed6.o",
4991         "changed7.o",
4992         "changed8.o",
4993         "changed9.o",
4994         "changed10.o",
4995         "changed11.o",
4996         "changed12.o",
4997         "changed13.o",
4998         "changed14.o",
4999         "changed15.o",
5000         "changed16.o",
5001         "changed17.o",
5002         "changed18.o",
5003         "changed19.o",
5004     };
5005     var builder = try Builder.init(allocator, options);
5006     defer builder.deinit();
5007     for (changed_names, 0..) |name, index| {
5008         try builder.addInput(.{ .name = name, .bytes = "old" });
5009         try builder.addContribution(name, index, .section, ".text", @intCast(index), ".text", 0x401000 + index * 16, 4 + index * 16, 3, 8, 16);
5010     }
5011     try builder.addInput(.{ .name = "same.o", .bytes = "same" });
5012     try builder.addContribution("same.o", changed_names.len, .section, ".text.same", 1, ".text", 0x402000, 512, 3, 8, 16);
5013 
5014     const manifest = try builder.finish();
5015     var state = try PreparedState.fromOwnedManifest(allocator, manifest);
5016     defer state.deinit(allocator);
5017 
5018     var inputs: [changed_names.len + 1]model.Input = undefined;
5019     for (changed_names, 0..) |name, index| {
5020         inputs[index] = .{ .name = name, .bytes = "new" };
5021     }
5022     inputs[changed_names.len] = .{ .name = "same.o", .bytes = "same" };
5023 
5024     var replacements_storage: [changed_names.len]ReplacementContribution = undefined;
5025     var replacement_count: usize = 0;
5026     for (changed_names, 0..) |name, index| {
5027         if (index == 7) continue;
5028         replacements_storage[replacement_count] = .{ .input_name = name, .input_index = index, .kind = .section, .name = ".text", .ordinal = @intCast(index), .size = 3, .alignment = 16, .payload = "new" };
5029         replacement_count += 1;
5030     }
5031     replacements_storage[replacement_count] = .{ .input_name = "same.o", .input_index = changed_names.len, .kind = .section, .name = ".text.same", .ordinal = 1, .size = 3, .alignment = 16, .payload = "new" };
5032     replacement_count += 1;
5033 
5034     const plan = try planChangedInputRelinkForTest(
5035         &state,
5036         allocator,
5037         options,
5038         &inputs,
5039         replacements_storage[0..replacement_count],
5040     );
5041 
5042     try std.testing.expectEqual(RelinkDecision.full_link, plan.decision);
5043     try std.testing.expectEqual(RelinkBlocker.replacement_missing, plan.blocker.?);
5044     try std.testing.expectEqual(@as(?usize, 7), plan.blocking_change_index);
5045     try std.testing.expectEqual(@as(?usize, null), plan.blocking_replacement_index);
5046 }
5047 
5048 test "prepared incremental state uses input index for repeated input relinks" {
5049     const allocator = std.testing.allocator;
5050     const options = model.LinkOptions{};
5051     var builder = try Builder.init(allocator, options);
5052     defer builder.deinit();
5053     try builder.addInput(.{ .name = "dup.o", .bytes = "first" });
5054     try builder.addInput(.{ .name = "dup.o", .bytes = "second" });
5055     try builder.addContribution("dup.o", 0, .section, ".text", 1, ".text", 0x401000, 4, 3, 8, 16);
5056     try builder.addContribution("dup.o", 1, .section, ".text", 1, ".text", 0x401040, 16, 12, 32, 16);
5057 
5058     const manifest = try builder.finish();
5059     var state = try PreparedState.fromOwnedManifest(allocator, manifest);
5060     defer state.deinit(allocator);
5061 
5062     const second_plan = try planChangedInputRelinkForTest(
5063         &state,
5064         allocator,
5065         options,
5066         &.{
5067             .{ .name = "dup.o", .bytes = "first" },
5068             .{ .name = "dup.o", .bytes = "changed-second" },
5069         },
5070         &.{
5071             .{ .input_name = "dup.o", .input_index = 1, .kind = .section, .name = ".text", .ordinal = 1, .size = 16, .alignment = 16, .payload = "changed-second!!" },
5072         },
5073     );
5074     try std.testing.expectEqual(RelinkDecision.in_place, second_plan.decision);
5075     try std.testing.expectEqual(@as(usize, 1), second_plan.affected_contributions.retained);
5076     try std.testing.expectEqual(@as(u64, 12), second_plan.affected_contributions.retained_size);
5077 
5078     const wrong_input_plan = try planChangedInputRelinkForTest(
5079         &state,
5080         allocator,
5081         options,
5082         &.{
5083             .{ .name = "dup.o", .bytes = "first" },
5084             .{ .name = "dup.o", .bytes = "changed-second" },
5085         },
5086         &.{
5087             .{ .input_name = "dup.o", .input_index = 0, .kind = .section, .name = ".text", .ordinal = 1, .size = 3, .alignment = 16, .payload = "bad" },
5088         },
5089     );
5090     try std.testing.expectEqual(RelinkDecision.full_link, wrong_input_plan.decision);
5091     try std.testing.expectEqual(RelinkBlocker.replacement_missing, wrong_input_plan.blocker.?);
5092     try std.testing.expectEqual(@as(?usize, 1), wrong_input_plan.blocking_change_index);
5093 }
5094 
5095 test "prepared incremental state reports replacement blockers for changed input relinks" {
5096     const allocator = std.testing.allocator;
5097     const options = model.LinkOptions{};
5098     var builder = try Builder.init(allocator, options);
5099     defer builder.deinit();
5100     try builder.addInput(.{ .name = "changed.o", .bytes = "old" });
5101     try builder.addContribution("changed.o", 0, .section, ".text", 1, ".text", 0x401000, 4, 7, 8, 16);
5102 
5103     const manifest = try builder.finish();
5104     var state = try PreparedState.fromOwnedManifest(allocator, manifest);
5105     defer state.deinit(allocator);
5106 
5107     const missing = try planChangedInputRelinkForTest(
5108         &state,
5109         allocator,
5110         options,
5111         &.{.{ .name = "changed.o", .bytes = "new" }},
5112         &.{},
5113     );
5114     try std.testing.expectEqual(RelinkDecision.full_link, missing.decision);
5115     try std.testing.expectEqual(RelinkBlocker.replacement_missing, missing.blocker.?);
5116     try std.testing.expectEqual(@as(?usize, 0), missing.blocking_change_index);
5117 
5118     const oversized = try planChangedInputRelinkForTest(
5119         &state,
5120         allocator,
5121         options,
5122         &.{.{ .name = "changed.o", .bytes = "new" }},
5123         &.{
5124             .{ .input_name = "changed.o", .input_index = 0, .kind = .section, .name = ".text", .ordinal = 1, .size = 9, .alignment = 16, .payload = "oversized" },
5125         },
5126     );
5127     try std.testing.expectEqual(RelinkDecision.full_link, oversized.decision);
5128     try std.testing.expectEqual(RelinkBlocker.replacement_grew_past_reserve, oversized.blocker.?);
5129     try std.testing.expectEqual(@as(?usize, 0), oversized.blocking_change_index);
5130     try std.testing.expectEqual(@as(?usize, 0), oversized.blocking_replacement_index);
5131     try std.testing.expectEqual(@as(usize, 1), oversized.affected_contributions.retained);
5132 }
5133 
5134 test "prepared incremental state does not write full-link changed input relinks" {
5135     const allocator = std.testing.allocator;
5136     const options = model.LinkOptions{};
5137     var builder = try Builder.init(allocator, options);
5138     defer builder.deinit();
5139     try builder.addInput(.{ .name = "changed.o", .bytes = "old" });
5140     try builder.addContribution("changed.o", 0, .section, ".text", 1, ".text", 0x401000, 4, 3, 8, 16);
5141 
5142     const manifest = try builder.finish();
5143     var state = try PreparedState.fromOwnedManifest(allocator, manifest);
5144     defer state.deinit(allocator);
5145 
5146     var image = @as([16]u8, @splat(0xaa));
5147     const application = try applyChangedInputRelinkForTest(
5148         &state,
5149         allocator,
5150         image[0..],
5151         options,
5152         &.{.{ .name = "changed.o", .bytes = "new" }},
5153         &.{
5154             .{ .input_name = "changed.o", .input_index = 0, .kind = .section, .name = ".text", .ordinal = 1, .size = 9, .alignment = 16, .payload = "oversized" },
5155         },
5156     );
5157 
5158     try std.testing.expectEqual(RelinkDecision.full_link, application.plan.decision);
5159     try std.testing.expectEqual(RelinkBlocker.replacement_grew_past_reserve, application.plan.blocker.?);
5160     try std.testing.expectEqual(@as(usize, 0), application.contributions_written);
5161     try std.testing.expectEqual(@as(usize, 0), application.bytes_written);
5162     try std.testing.expectEqual(@as(usize, 0), application.zero_fill_bytes);
5163     for (image) |byte| try std.testing.expectEqual(@as(u8, 0xaa), byte);
5164 }
5165 
5166 test "prepared incremental state reports option and hash blockers before input deltas" {
5167     const allocator = std.testing.allocator;
5168     var builder = try Builder.init(allocator, .{});
5169     defer builder.deinit();
5170     try builder.addInput(.{ .name = "a.o", .bytes = "abc" });
5171 
5172     const manifest = try builder.finish();
5173     var state = try PreparedState.fromOwnedManifest(allocator, manifest);
5174     defer state.deinit(allocator);
5175 
5176     var off_options = model.LinkOptions{};
5177     off_options.incremental_mode = .off;
5178     const incremental_disabled = try planInputRelinkForTest(
5179         &state,
5180         allocator,
5181         off_options,
5182         &.{.{ .name = "a.o", .bytes = "abd" }},
5183     );
5184     try std.testing.expectEqual(RelinkDecision.full_link, incremental_disabled.decision);
5185     try std.testing.expectEqual(RelinkBlocker.incremental_disabled, incremental_disabled.blocker.?);
5186 
5187     var gc_options = model.LinkOptions{};
5188     gc_options.gc_sections = true;
5189     const compatibility = try planInputRelinkForTest(
5190         &state,
5191         allocator,
5192         gc_options,
5193         &.{.{ .name = "a.o", .bytes = "abd" }},
5194     );
5195     try std.testing.expectEqual(RelinkDecision.full_link, compatibility.decision);
5196     try std.testing.expectEqual(RelinkBlocker.compatibility_mismatch, compatibility.blocker.?);
5197 
5198     var build_id_builder = try Builder.init(allocator, .{ .build_id = .fast });
5199     defer build_id_builder.deinit();
5200     try build_id_builder.addInput(.{ .name = "a.o", .bytes = "abc" });
5201     const build_id_manifest = try build_id_builder.finish();
5202     var build_id_state = try PreparedState.fromOwnedManifest(allocator, build_id_manifest);
5203     defer build_id_state.deinit(allocator);
5204 
5205     const build_id_plan = try planInputRelinkForTest(
5206         &build_id_state,
5207         allocator,
5208         .{ .build_id = .fast },
5209         &.{.{ .name = "a.o", .bytes = "abd" }},
5210     );
5211     try std.testing.expectEqual(RelinkDecision.full_link, build_id_plan.decision);
5212     try std.testing.expectEqual(RelinkBlocker.input_changed, build_id_plan.blocker.?);
5213 
5214     var non_incremental_builder = try Builder.init(allocator, .{ .incremental_mode = .off });
5215     defer non_incremental_builder.deinit();
5216     try non_incremental_builder.addInput(.{ .name = "a.o", .bytes = "abc" });
5217     const compact_manifest = try non_incremental_builder.finish();
5218     var compact_state = try PreparedState.fromOwnedManifest(allocator, compact_manifest);
5219     defer compact_state.deinit(allocator);
5220 
5221     const missing_hashes = try planInputRelinkForTest(
5222         &compact_state,
5223         allocator,
5224         .{},
5225         &.{.{ .name = "a.o", .bytes = "abc" }},
5226     );
5227     try std.testing.expectEqual(RelinkDecision.full_link, missing_hashes.decision);
5228     try std.testing.expectEqual(RelinkBlocker.input_hashes_unrecorded, missing_hashes.blocker.?);
5229 }
5230 
5231 test "incremental planner rejects oversized replacements" {
5232     const allocator = std.testing.allocator;
5233     var builder = try Builder.init(allocator, .{});
5234     defer builder.deinit();
5235     try builder.addContribution("a.o", 0, .section, ".text", 1, ".text", 0x401000, 0x1000, 3, 16, 16);
5236 
5237     var manifest = try builder.finish();
5238     defer manifest.deinit(allocator);
5239 
5240     const plan = manifest.planContributionReplacement(&.{
5241         .{ .input_name = "a.o", .input_index = 0, .kind = .section, .name = ".text", .ordinal = 1, .size = 17, .alignment = 16 },
5242     });
5243     try std.testing.expectEqual(PatchDecision.full_link, plan.decision);
5244     try std.testing.expectEqual(PatchBlocker.grew_past_reserve, plan.blocker.?);
5245     try std.testing.expectEqual(@as(usize, 0), plan.blocking_index.?);
5246 }
5247 
5248 test "incremental planner rejects missing and stricter-alignment replacements" {
5249     const allocator = std.testing.allocator;
5250     var builder = try Builder.init(allocator, .{});
5251     defer builder.deinit();
5252     try builder.addContribution("a.o", 0, .section, ".text", 1, ".text", 0x401000, 0x1000, 3, 16, 16);
5253 
5254     var manifest = try builder.finish();
5255     defer manifest.deinit(allocator);
5256 
5257     const missing = manifest.planContributionReplacement(&.{
5258         .{ .input_name = "b.o", .input_index = 1, .kind = .section, .name = ".text", .ordinal = 1, .size = 3, .alignment = 16 },
5259     });
5260     try std.testing.expectEqual(PatchDecision.full_link, missing.decision);
5261     try std.testing.expectEqual(PatchBlocker.missing_contribution, missing.blocker.?);
5262     try std.testing.expectEqual(@as(usize, 0), missing.blocking_index.?);
5263 
5264     const stricter_alignment = manifest.planContributionReplacement(&.{
5265         .{ .input_name = "a.o", .input_index = 0, .kind = .section, .name = ".text", .ordinal = 1, .size = 3, .alignment = 32 },
5266     });
5267     try std.testing.expectEqual(PatchDecision.full_link, stricter_alignment.decision);
5268     try std.testing.expectEqual(PatchBlocker.alignment_increased, stricter_alignment.blocker.?);
5269     try std.testing.expectEqual(@as(usize, 0), stricter_alignment.blocking_index.?);
5270 }