Log in
benchmarksPublic

Commit 46ad54da

· Browse files at this commit

46ad54da0178

Merged on mrmrs-15c4c5
mrmrs · 1 month ago · 18 files +18 added
A suites/merge/README.md
1+# Merge correctness & quality suite (P3)
2+
3+A differential merge suite. Every scenario is built as a real Git history.
4+`git merge-ort` (via `git merge-tree --write-tree`) supplies the reference
5+tree and conflict set. The same inputs then go through **Oak's merge engine**,
6+and the two results are compared. Each directional case gets exactly one
7+class, and merge laws are checked on the side.
8+
9+This suite produces diagnostic correctness evidence
10+(`evidence_class: diagnostic_merge_correctness`). It is not timing data.
11+Do not ingest its rows into performance reports, devloop baselines, or
12+public comparison tables.
13+
14+## Run
15+
16+```sh
17+# from the repo root, in an isolated worker (writes only under --workdir)
18+python3 suites/merge/run_merge_suite.py --workdir runs/merge --jobs 6 \
19+ --summary runs/merge-summary.json > runs/merge.jsonl
20+python3 suites/merge/run_merge_suite.py --workdir runs/merge --list # scenario ids
21+python3 suites/merge/run_merge_suite.py --workdir runs/m1 --only 'incident/*' # one group or case
22+python3 -m unittest tests.test_merge_suite # instrument tests
23+```
24+
25+| Option | Meaning |
26+|---|---|
27+| `--groups` | Comma list from `gix-tree,gix-cartesian,gix-text,t64xx,native,generated`. The default is all of them. |
28+| `--oak-bin` | The Oak binary under test (default `oak`). |
29+| `--git-bin` | The oracle Git. By default the macOS xcrun shim is resolved to the real Git through `oakbench.subjects`. |
30+| `--keep-equal` | Keep case directories for equal-to-git cases. By default they are deleted, and every other case directory is kept as evidence. |
31+
32+The exit code is 1 when any case is `oak-wrong` or `harness-error`, and 0
33+otherwise. Output is JSONL on stdout (one row per directional case), with a
34+summary table on stderr. Everything runs locally: a private `oak serve` on
35+loopback and an isolated `HOME`. Nothing contacts oak.space.
36+
37+Requirements are Python 3.9+ stdlib (ADR-0001), a real `git`, `bash`, and
38+the `oak` binary. The Oak and Git SHA-256 and version are recorded on every
39+row.
40+
41+## Which Oak path each result exercises (phase 1)
42+
43+`path_exercised: oak-pull-parent-sync` is the Oak **client** merge engine.
44+It is run as a user would run it:
45+
46+1. `oak clone <scenario.git>` imports main's lineage (Oak's git import) and
47+ `oak push` bootstraps `main` on a local `oak serve`.
48+2. A second `oak clone` imports the fork point. `oak commit` then checks in
49+ the scripted branch tree states, and `oak push` publishes the branch.
50+3. `oak fetch` runs, then `oak merge --dry-run --json`, which records the
51+ local merge prediction (`laws.prediction_agrees`).
52+4. `oak pull --json` runs the parent sync. This is the measured merge: merge
53+ base resolution over the local and hydrated graph, then
54+ `three_way_merge_manifests`, then diffy text merge and conflict markers.
55+ It is the same engine `oak merge` uses for non-main parents.
56+5. On a clean merge, a second `oak pull` is the idempotence check. On a
57+ conflict, `oak conflict show --json` supplies the conflict set. Each
58+ conflicted path is then overwritten with a sentinel and `oak pull
59+ --continue` commits, so the **committed** merge result is compared. The
60+ conflicted worktree is only a working view: Oak leaves paths the merge
61+ deletes in place until `--continue` (`conflict_worktree_stale_paths`).
62+
63+Two pieces of test plumbing are involved. Neither contains merge logic.
64+
65+- **Raw shim.** `oak serve` 0.105 lacks `GET /api/:o/:r/raw/:commit/:path`,
66+ which the client uses to hydrate parent blobs. `RawShim` fronts the real
67+ server and answers that one route from the publishing clone via
68+ `oak file inspect --at <commit> --output`. Oak hash-verifies those bytes.
69+ Every other request is forwarded unchanged.
70+- **Main staging.** For multi-step scenarios, the shim can report an earlier
71+ main commit as `main`'s head. This is how `main` "moves" between client
72+ pulls (for example, sync with M1, then main reverts in M2) without a
73+ hosted merge endpoint.
74+
75+Some shapes are outside Oak's public surface. Ours-side histories are always
76+fork + checkpoints + CLI syncs, because Oak cannot import an arbitrary
77+ours-side DAG. Git DAGs with several merge bases, or with unrelated
78+histories, are therefore `oak-unsupported` under the fork+squash
79+construction. The criss-cross cases that matter are instead built from
80+Oak-native steps under `incident/criss-cross-*` and
81+`git-t6416-criss-cross-modify-delete`.
82+
83+**Phase 2 (not built):** the hosted squash-merge onto `main` (oakspace
84+`POST /branches/:b/merge`). `oak_adapter.HostedMergeAdapter` is the plug
85+point, and it returns the same result shape. `sources.PHASE2_SPECS` lists
86+specs that need it: concurrent merges (M0a), push during merge (M0b), the
87+server `/sync` that loses lineage, client-vs-server criss-cross tie-break
88+agreement, server clock-skew, and dirty tree across a moved branch (fb-530).
89+The summary names them under `phase2_specs_not_executed`. They are never
90+counted as passes.
91+
92+## Classes
93+
94+| Class | Meaning |
95+|---|---|
96+| `equal-to-git` | Same clean/conflicted status and the same conflicted path set. Every non-conflicted path has identical content and mode. |
97+| `differs-but-valid` | Differs from Git, but no side's change is lost or fabricated at any non-conflicted path. `reasons` say how, for example `oak_conflicts_where_git_clean` (a false conflict, typically because Oak has no rename detection), `oak_clean_where_git_conflicts` (Oak's path-level merge kept both sides where merge-ort reports a rename conflict), `tree_differs(...)` (Git relocated a file through directory-rename detection while Oak left it in place), or `text_merge_algorithm_differs`. |
98+| `oak-wrong` | A non-conflicted path lost a side's change or holds content no input and no valid text merge explains (`lost_change`, `fabricated_content`). Also: a scenario's stated expectation was violated (`expectation_violated`), or Oak errored on a valid input (`oak_error`). |
99+| `oak-unsupported` | Decided before Oak runs. The input cannot be expressed through Oak's surface: gitlinks (the git import drops them), several git merge bases, or unrelated histories. |
100+| `harness-error` | The instrument failed: fixture build, oracle, or shim. It is never an Oak verdict. |
101+
102+Nothing passes silently. Unmeasured law values are `null` (ADR-0002). An
103+example is the no-lost-change law where no unique merge base exists.
104+
105+### Merge laws (per row under `laws`)
106+
107+- **no_lost_change**: path-level. A change made by one side only must be
108+ present. An identical change on both sides must be present. A divergent
109+ change on both sides must be text-merged, with every block either side
110+ inserted still present and no markers left. Conflicted paths are exempt.
111+ The text check is a heuristic: deletions are not verified, because lines
112+ repeat.
113+- **symmetric**: merge(A,B) ≅ merge(B,A). The clean flag, the conflicted
114+ path set, and non-conflicted content must all match. Conflicted file bytes
115+ are excluded, because side labels differ.
116+- **idempotent**: after a clean merge, `oak pull` again is a no-op. Head and
117+ tree are unchanged.
118+- **false_conflict / missed_conflict**: Oak conflicts where Git is clean, or
119+ the reverse. The summary reports rates over measured rows.
120+- **prediction_agrees**: the `oak merge --dry-run --json` prediction matches
121+ the executed merge (clean flag and conflict set).
122+
123+## Scenario sources and licenses
124+
125+| Origin (`origin`) | What | License / port mode |
126+|---|---|---|
127+| `gitoxide-tree-baseline` | Named tree scenarios from `vendor/gitoxide/tree-baseline.sh`, merge-style only. The diff3 duplicates differ only in marker text, and Oak has one marker style. Both directions are run. | **MIT OR Apache-2.0.** Vendored verbatim. |
128+| `gitoxide-cartesian` | The 14×14 atomic-operation product (`matrix`) plus its gitlink twin (`matrix-submodule`, which is `oak-unsupported`). | Same. |
129+| `gitoxide-text-baseline` | Blob triples from `text-baseline.sh` (default style), each as a one-file tree merge. | Same. |
130+| `git-t64xx-reimplemented` | Git t6423 directory-rename cases 1a 1b 1c 1f 2a 3a 4a 5a 6a 6c 6d 7a 8c 9a 9b 12d 12i, and t6422 break-detection-1/2/3 and rename/rename(1to2) binary. The IDs are in `scenario`. | Git is **GPL-2.0-only**. Only the O/A/B shapes from the testcase comment prose were re-expressed, in `sources.T64XX`. Paths and contents are our own. No Git test text was copied (a unit test enforces this). Read at Git v2.50.1. |
131+| `native-incident` | This week's incident shapes, each with its correct expected outcome in `expect`. Seeds: `merge_base_fixtures.rs` (5d2ee0fb) and the repro-server-mergebase worker. | Suite-authored. |
132+| `generated-law` | 40 seeded random histories (edits in disjoint or overlapping regions, delete, add, chmod, rename, identical changes) for the laws. | Suite-authored. |
133+
134+`vendor/gitoxide/` holds `tree-baseline.sh`, `tree-cartesian-baseline.sh`
135+and `text-baseline.sh`, byte-identical to upstream commit
136+`acf906f8fcdb8e8d143570737786543dc5a204a0`. Their SHA-256 digests are pinned
137+in `UPSTREAM.json`, and a unit test checks them. The directory also carries
138+`LICENSE-MIT`, `LICENSE-APACHE` and a `NOTICE` with the attribution. The
139+upstream scripts have no per-file headers, so none were added and the files
140+stay byte-identical. The suite only runs these scripts. Spork cases
141+(optional stretch) were not added.
142+
143+This vendoring is a deliberate, recorded exception to `docs/prior-art.md`'s
144+"no vendored external benchmark code" rule. PROGRAM.md P3 chose it, and the
145+license is permissive. GPL sources stay clean-room.
146+
147+### Incident scenarios
148+
149+| id | Shape | Correct outcome |
150+|---|---|---|
151+| `incident/stale-base-squash-revert` | `R-C-X-M1..M9-H`, M5 reverts X, `H.merge_parent=Z1` (forked from C), branch `a1` on X. The ours clone holds only R-C-X locally (a partial graph), and the rest is hydrated by pull. | The base is X, so X stays reverted. |
152+| `incident/merge-base-via-merge-parent` | The fork is Z1, reachable only through H's merge parent. | The base is Z1, so edits to `z.txt` merge cleanly. |
153+| `incident/revert-after-client-sync` | The branch syncs main M1 (adds X) with `oak pull`, then main M2 reverts X. | The revert survives, because the sync records `merge_parent`. |
154+| `incident/revert-after-lineage-less-sync` | The branch copies X by hand, which is the server `/sync` shape. | Git and Oak both resurrect X. `intent_note` explains that lineage loss is unrecoverable. The hosted `/sync` itself is phase 2. |
155+| `incident/criss-cross-tie-break-{side-newer,side-older}` | Two best common ancestors {F, Mk}, then main reverts K. | K stays reverted, whatever the tie-break or timestamps. |
156+| `incident/clock-skew-merge-base-{skewed,monotone-control}` | The best common ancestor Y is 24 h older than X. | The base is Y, and Y stays reverted. |
157+| `git-t6416-criss-cross-modify-delete` | Two histories resolve the same modify/delete differently: the branch deletes, main keeps. | A conflict, not a silent pick. |
158+
159+## Row schema (`merge_suite_schema_version: 1`)
160+
161+Each row carries `scenario`, `scenario_version`, `direction`, `origin`,
162+`upstream{id,license,commit}`, `oak{bin,sha256,version,path_exercised}`,
163+`git{bin,sha256,version,role}`, `git_result{clean,conflicts{path:[types]},tree_digest,conflict_messages}`,
164+`oak_result{clean,conflicts,tree_digest,pull_receipt,prediction,idempotence,result_source,...}`,
165+`class`, `reasons`, `laws{...}`, `evidence`, `repro`, `case_dir`, `elapsed_ms`.
166+Rows that are not equal-to-git also carry `oak_steps` (argv, return code, ms,
167+stderr tail). Scenario ids are immutable identity (ADR-0005). Changed
168+semantics need a new id or a `scenario_version` bump. Raw rows are results,
169+and results are never committed (ADR-0003).
170+
171+## First run
172+
173+See `RESULTS-2026-09-28.md` for the first run against oak 0.105.0: counts
174+per class, law rates, and every oak-wrong case with a minimal repro.