code wiki / _hdl_build / nx_merge_queue.nx
`nx_merge_queue.nx` source

1// nx_merge_queue.nx -- the SPECULATIVE FIFO merge queue (the research-proven integration layer that
2// GitHub merge queue / GitLab merge trains / Zuul all use; /deep-research wfb7jkc6h). Upgrades
3// nx_workstream_git: each change is tested against the COMBINED state of base + all changes ahead in FIFO
4// order; disjoint changes all land (parallel throughput), an overlapping change is DROPPED (must rebase +
5// re-enter), and a drop does NOT cascade -- downstream changes are re-tested against the merged tip WITHOUT
6// the dropped change (no false failures). This catches the canonical race (both pass alone, break together)
7// that a shared branch misses. license_tier: ORIGINAL  Pairs with nx_workstream_git isolation.
8
9import "nx_syscalls.nx"
10
11const MQ_MERGED:  i64 = 1
12const MQ_DROPPED: i64 = 2   // conflicts with an already-merged change -> rejected from this train, rebase + retry
13
14// two changes can co-merge cleanly iff their file-sets are disjoint (no overlap in the combined state).
15func mq_clean(mask_a: i64, mask_b: i64) -> i64 { if (mask_a & mask_b) == 0 { return 1 } return 0 }
16
17// process the queue in FIFO order. a change merges iff its combined state (its mask vs everything already
18// merged) is clean; else it's dropped. returns the count merged; writes per-change status into out_status.
19// KEY: a dropped change does not poison downstream -- they're tested against `merged_mask` (the tip), not the drop.
20func mq_process(masks: *i64, n: i64, out_status: *i64) -> i64 {
21    var merged_mask: i64 = 0
22    var merged: i64 = 0
23    var i: i64 = 0
24    while i < n {
25        if (masks[i] & merged_mask) == 0 {        // combined state clean -> merge
26            out_status[i] = MQ_MERGED
27            merged_mask = merged_mask | masks[i]
28            merged = merged + 1
29        } else {
30            out_status[i] = MQ_DROPPED            // overlaps the merged tip -> serialize (drop + rebase)
31        }
32        i = i + 1
33    }
34    return merged
35}
36
37// the speculative-parallel property: how many of the queue could merge IN ONE TRAIN (all mutually disjoint
38// with the merged set as built FIFO) -- the throughput a shared branch can't get.
39func mq_parallel_merged(masks: *i64, n: i64) -> i64 {
40    let st: *i64 = sys_mmap(8 * n) as *i64
41    return mq_process(masks, n, st)
42}
43
44func mq_status_label(s: i64) -> *u8 { if s == MQ_MERGED { return "MERGED" as *u8 } return "DROPPED(rebase+retry)" as *u8 }
nx_merge_queue.nx source

`nx_merge_queue.nx` source
