coverage — ~bigbes/sr-ht-spec — 3cb1c03d — gitx/merge.go

Coverage
79.4% 131/165 statements
Δ
—
Blob
3ac5456
Uncovered L121-L122L129-L130L133-L135L146-L147L163-L164L171-L172L179-L180L183-L184L187-L188L201-L202L205-L206L210-L211L216-L218L228-L229L232-L233L262-L263L276-L277L284-L285L313-L314L320-L321L339-L340L343-L345L350-L351L354-L355L401-L402L410-L411L414-L415L417-L418L425L429-L430L441-L442
1 package gitx
2
3 import (
4 "context"
5 "errors"
6 "fmt"
7 "sort"
8 "strings"
9
10 "github.com/go-git/go-git/v5/plumbing"
11 "github.com/go-git/go-git/v5/plumbing/filemode"
12 "github.com/go-git/go-git/v5/plumbing/object"
13 "github.com/go-git/go-git/v5/storage"
14 "github.com/go-git/go-git/v5/utils/merkletrie"
15
16 "sourcecraft.dev/bigbes/sr-ht-spec/core"
17 )
18
19 // MergeRequest asks for a proposal branch to be spliced onto the approved head.
20 type MergeRequest struct {
21 // Branch is the proposal branch, "proposals/42".
22 Branch string
23
24 // Base is the proposal's base revision B: the approved-head sha the agent
25 // held when it opened the proposal. It does not move as the proposal
26 // accumulates edits, and it is what staleness is measured against.
27 //
28 // It is required rather than derived from a merge base. The caller has it
29 // (it is the recorded base_rev, the same value the agent keeps sending as
30 // If-Match), and inferring it would let a rewritten approved branch quietly
31 // change which revision the merge believes it was proposed against.
32 Base string
33
34 // Meta is the merge commit's message, trailers and identities.
35 Meta CommitMeta
36 }
37
38 // MergedDoc records what the merge did with one document.
39 type MergedDoc struct {
40 // DocID is the document's frontmatter id — the key the whole merge turns
41 // on, since paths move and ids do not.
42 DocID string
43
44 // Path is where the blob landed in the new approved tree.
45 Path string
46
47 // ProposalPath is where the proposal held it. It differs from Path exactly
48 // when the approved branch moved the document between the base and the
49 // head, which is the case that must not become a conflict.
50 ProposalPath string
51
52 // Blob is the document's blob sha, taken unchanged from the proposal.
53 Blob plumbing.Hash
54
55 // New is set when the document did not exist on the approved head.
56 New bool
57 }
58
59 // Renamed reports whether the approved branch had moved this document under the
60 // proposal, so the proposal's blob followed the document to its new path.
61 2 func (d MergedDoc) Renamed() bool { return !d.New && d.Path != d.ProposalPath }
62
63 // MergeResult describes a completed merge.
64 type MergeResult struct {
65 // Commit is the merge commit and the new approved head.
66 Commit plumbing.Hash
67 Tree plumbing.Hash
68
69 // ApprovedHead is the head this merged onto — the first parent.
70 ApprovedHead plumbing.Hash
71 // ProposalHead is the proposal branch tip — the second parent.
72 ProposalHead plumbing.Hash
73
74 // Docs is every document the merge carried over, sorted by path.
75 Docs []MergedDoc
76 }
77
78 // Merge splices a proposal onto the approved head and moves the approved branch
79 // to the resulting two-parent merge commit.
80 //
81 // The model, exactly as designed:
82 //
83 // for d in F: # F is document ids, not paths
84 // if blob(path(d)@H) != blob(path(d)@B): # changed under us since B
85 // return 409 stale
86 // newTree = tree(H) with each d's blob replaced (at its path in H)
87 // commit newTree with parents [H, P.head]
88 //
89 // Two things about it are load-bearing and easy to get wrong:
90 //
91 // - Each changed document is resolved to its path *on the approved head*
92 // through its frontmatter id before its blob is compared. A rename between
93 // B and H therefore neither raises a conflict nor resurrects the document
94 // at the path it was moved away from: the proposal's blob is written at the
95 // head's path, and the old path is never touched.
96 // - There is no text merge. go-git v5 supports only FastForwardMerge, and the
97 // whole-document write grain makes three-way merging unnecessary anyway.
98 // A conflict is always "your base moved, re-propose" (*StaleError), which
99 // is trivial for an agent and comprehensible for a human.
100 //
101 // The build runs under the space write lock and ends in a compare-and-swap on
102 // the approved ref. Losing that swap means a human push landed underneath, so
103 // the merge is rebuilt against the new head rather than failing — up to a
104 // bounded number of attempts, after which it is ErrRefRace and nothing moved.
105 22 func (r *Repo) Merge(ctx context.Context, req MergeRequest) (MergeResult, error) {
106 22 ctx, cancel := r.withTimeout(ctx)
107 22 defer cancel()
108 22
109 22 if !IsProposalBranch(req.Branch) {
110 1 return MergeResult{}, fmt.Errorf("%w: %q is not a %s* branch", ErrBadRev, req.Branch, ProposalPrefix)
111 1 }
112 21 if req.Base == "" {
113 1 return MergeResult{}, fmt.Errorf("gitx: merge of %q needs the proposal's base revision", req.Branch)
114 1 }
115 20 if err := req.Meta.validate(); err != nil {
116 1 return MergeResult{}, err
117 1 }
118
119 19 unlock, err := r.lock(ctx)
120 19 if err != nil {
121 0 return MergeResult{}, err
122 0 }
123 19 defer unlock()
124 19
125 19 approvedRef := plumbing.NewBranchReferenceName(r.approved)
126 19 var lastErr error
127 21 for attempt := 0; attempt < r.casBudget(); attempt++ {
128 21 if err := ctx.Err(); err != nil {
129 0 return MergeResult{}, err
130 0 }
131 21 old, err := r.repo.Reference(approvedRef, false)
132 21 if err != nil {
133 0 return MergeResult{}, fmt.Errorf("%w: approved branch %q in %s: %v",
134 0 ErrNotFound, r.approved, r.ref, err)
135 0 }
136 21 res, err := r.buildMerge(ctx, req, old.Hash())
137 21 if err != nil {
138 13 return MergeResult{}, err
139 13 }
140 8 r.raceHook()
141 8 err = r.repo.Storer.CheckAndSetReference(plumbing.NewHashReference(approvedRef, res.Commit), old)
142 8 if err == nil {
143 5 return res, nil
144 5 }
145 3 if !errors.Is(err, storage.ErrReferenceHasChanged) {
146 0 return MergeResult{}, fmt.Errorf("gitx: update %s in %s: %w", approvedRef, r.ref, err)
147 0 }
148 3 lastErr = err
149 }
150 1 return MergeResult{}, fmt.Errorf("%w: %s in %s after %d attempts: %v",
151 1 ErrRefRace, approvedRef, r.ref, r.casBudget(), lastErr)
152 }
153
154 // buildMerge does everything except moving the ref: it is called afresh on each
155 // compare-and-swap attempt, against the head it was handed.
156 21 func (r *Repo) buildMerge(ctx context.Context, req MergeRequest, head plumbing.Hash) (MergeResult, error) {
157 21 proposalHead, err := r.BranchHead(ctx, req.Branch)
158 21 if err != nil {
159 1 return MergeResult{}, err
160 1 }
161 20 base, err := r.ResolveRev(ctx, req.Base)
162 20 if err != nil {
163 0 return MergeResult{}, err
164 0 }
165
166 // The base must still be on the approved branch. If it is not, the approved
167 // branch was rewritten under the proposal and every comparison below would
168 // be against a revision that is no longer part of the history.
169 20 onBranch, err := r.IsAncestor(ctx, base, head)
170 20 if err != nil {
171 0 return MergeResult{}, err
172 0 }
173 20 if !onBranch {
174 1 return MergeResult{}, &StaleError{Reason: StaleBaseDetached, Base: base, Head: head}
175 1 }
176
177 19 baseTree, err := r.treeOf(base)
178 19 if err != nil {
179 0 return MergeResult{}, err
180 0 }
181 19 headTree, err := r.treeOf(head)
182 19 if err != nil {
183 0 return MergeResult{}, err
184 0 }
185 19 proposalTree, err := r.treeOf(proposalHead)
186 19 if err != nil {
187 0 return MergeResult{}, err
188 0 }
189
190 19 changed, err := r.changedDocs(ctx, req.Branch, baseTree, proposalTree)
191 19 if err != nil {
192 5 return MergeResult{}, err
193 5 }
194 14 if len(changed) == 0 {
195 1 return MergeResult{}, fmt.Errorf("%w: %q changes no document against its base %s",
196 1 ErrUnsupportedChange, req.Branch, base)
197 1 }
198
199 13 baseIdx, err := r.buildDocIndex(ctx, baseTree)
200 13 if err != nil {
201 0 return MergeResult{}, fmt.Errorf("gitx: index documents at base %s: %w", base, err)
202 0 }
203 13 headIdx, err := r.buildDocIndex(ctx, headTree)
204 13 if err != nil {
205 0 return MergeResult{}, fmt.Errorf("gitx: index documents at approved head %s: %w", head, err)
206 0 }
207
208 13 node, err := r.loadTree(headTree, 0)
209 13 if err != nil {
210 0 return MergeResult{}, err
211 0 }
212
213 13 docs := make([]MergedDoc, 0, len(changed))
214 13 for _, c := range changed {
215 13 if baseIdx.duplicated[c.docID] || headIdx.duplicated[c.docID] {
216 0 return MergeResult{}, fmt.Errorf("%w: %s appears more than once on the approved branch",
217 0 ErrDuplicateDocID, c.docID)
218 0 }
219 13 basePath, inBase := baseIdx.byID[c.docID]
220 13 headPath, inHead := headIdx.byID[c.docID]
221 13
222 13 switch {
223 4 case inBase && inHead:
224 4 // The design's comparison, resolved through the id rather than the
225 4 // path: a rename between B and H is not a change to the document.
226 4 baseBlob, err := blobAt(baseTree, basePath)
227 4 if err != nil {
228 0 return MergeResult{}, err
229 0 }
230 4 headBlob, err := blobAt(headTree, headPath)
231 4 if err != nil {
232 0 return MergeResult{}, err
233 0 }
234 4 if baseBlob != headBlob {
235 1 return MergeResult{}, &StaleError{
236 1 Reason: StaleDocChanged, DocID: c.docID, Path: headPath, Base: base, Head: head,
237 1 }
238 1 }
239 1 case inBase && !inHead:
240 1 return MergeResult{}, &StaleError{
241 1 Reason: StaleDocRemoved, DocID: c.docID, Path: basePath, Base: base, Head: head,
242 1 }
243 1 case !inBase && inHead:
244 1 return MergeResult{}, &StaleError{
245 1 Reason: StaleDocAppeared, DocID: c.docID, Path: headPath, Base: base, Head: head,
246 1 }
247 7 default:
248 7 // A genuinely new document. Its path on the head must be free, or
249 7 // the splice would overwrite a document the proposal never read.
250 7 if _, taken := headIdx.byPath[c.path]; taken {
251 2 return MergeResult{}, &StaleError{
252 2 Reason: StalePathTaken, DocID: c.docID, Path: c.path, Base: base, Head: head,
253 2 }
254 2 }
255 }
256
257 8 target := c.path
258 8 if inHead {
259 3 target = headPath
260 3 }
261 8 if err := node.set(target, c.blob); err != nil {
262 0 return MergeResult{}, err
263 0 }
264 8 docs = append(docs, MergedDoc{
265 8 DocID: c.docID,
266 8 Path: target,
267 8 ProposalPath: c.path,
268 8 Blob: c.blob,
269 8 New: !inHead,
270 8 })
271 }
272 8 sort.Slice(docs, func(i, j int) bool { return docs[i].Path < docs[j].Path })
273
274 8 treeHash, err := node.write(r.repo.Storer)
275 8 if err != nil {
276 0 return MergeResult{}, err
277 0 }
278 // Two parents, approved head first. This is the whole of the "merge": a
279 // real merge commit, so the proposal stays visible in git log, built with
280 // explicit ParentHashes rather than any merge strategy.
281 8 parents := []plumbing.Hash{head, proposalHead}
282 8 commit, err := r.writeCommit(req.Meta, treeHash, parents)
283 8 if err != nil {
284 0 return MergeResult{}, err
285 0 }
286 8 return MergeResult{
287 8 Commit: commit,
288 8 Tree: treeHash,
289 8 ApprovedHead: head,
290 8 ProposalHead: proposalHead,
291 8 Docs: docs,
292 8 }, nil
293 }
294
295 // changedDoc is one document the proposal touched, as it exists on the proposal
296 // branch.
297 type changedDoc struct {
298 path string
299 blob plumbing.Hash
300 docID string
301 }
302
303 // changedDocs is F: the documents a proposal changed against its base.
304 //
305 // Only additions and modifications of markdown documents are expressible. A
306 // deletion, a rename, or an edit to a non-document path (an attachment, or
307 // .spec.yml) is refused rather than guessed at — the write plane is a
308 // whole-document PUT and gives an agent no way to say "delete this" or "move
309 // this", and those operations are human-push-only by design.
310 19 func (r *Repo) changedDocs(ctx context.Context, branch string, baseTree, proposalTree *object.Tree) ([]changedDoc, error) {
311 19 changes, err := object.DiffTreeWithOptions(ctx, baseTree, proposalTree, object.DefaultDiffTreeOptions)
312 19 if err != nil {
313 0 return nil, fmt.Errorf("gitx: diff %q against its base in %s: %w", branch, r.ref, err)
314 0 }
315 19 out := make([]changedDoc, 0, len(changes))
316 19 seenID := make(map[string]string, len(changes))
317 19 for _, c := range changes {
318 19 action, err := c.Action()
319 19 if err != nil {
320 0 return nil, fmt.Errorf("gitx: classify change in %q: %w", branch, err)
321 0 }
322 19 switch action {
323 1 case merkletrie.Delete:
324 1 return nil, fmt.Errorf("%w: %q deletes %q; deletion is human-push-only",
325 1 ErrUnsupportedChange, branch, c.From.Name)
326 7 case merkletrie.Modify:
327 7 if c.From.Name != c.To.Name {
328 1 return nil, fmt.Errorf("%w: %q renames %q to %q; rename is human-push-only",
329 1 ErrUnsupportedChange, branch, c.From.Name, c.To.Name)
330 1 }
331 }
332
333 17 path := c.To.Name
334 17 if !strings.HasSuffix(path, core.DocExt) {
335 1 return nil, fmt.Errorf("%w: %q changes %q, which is not a document; the merge is keyed by document id",
336 1 ErrUnsupportedChange, branch, path)
337 1 }
338 16 if err := core.ValidateDocPath(path); err != nil {
339 0 return nil, err
340 0 }
341 16 switch c.To.TreeEntry.Mode {
342 case filemode.Regular, filemode.Executable:
343 0 default:
344 0 return nil, fmt.Errorf("%w: %q at %q in %q is not a document blob",
345 0 ErrUnsupportedEntry, c.To.TreeEntry.Mode, path, branch)
346 }
347
348 16 data, err := r.readBlob(c.To.TreeEntry.Hash, path)
349 16 if err != nil {
350 0 return nil, err
351 0 }
352 16 fm, _, err := core.ParseDocument(data)
353 16 if err != nil {
354 0 return nil, fmt.Errorf("gitx: %q in %q: %w", path, branch, err)
355 0 }
356 16 if err := core.ValidateDocID(fm.ID); err != nil {
357 1 return nil, fmt.Errorf("gitx: %q in %q: %w", path, branch, err)
358 1 }
359 15 if prev, dup := seenID[fm.ID]; dup {
360 1 return nil, fmt.Errorf("%w: %q changes %s at both %q and %q",
361 1 ErrDuplicateDocID, branch, fm.ID, prev, path)
362 1 }
363 14 seenID[fm.ID] = path
364 14 out = append(out, changedDoc{path: path, blob: c.To.TreeEntry.Hash, docID: fm.ID})
365 }
366 14 sort.Slice(out, func(i, j int) bool { return out[i].path < out[j].path })
367 14 return out, nil
368 }
369
370 // docIndex maps a tree's documents both ways.
371 type docIndex struct {
372 // byID maps a document id to its path. Documents whose frontmatter is
373 // missing, unparseable or carries no valid id are absent from it.
374 byID map[string]string
375
376 // byPath maps every document path to its id, "" when it has none. It is
377 // what stops a new document from being spliced over a path that is already
378 // occupied by something this merge cannot see.
379 byPath map[string]string
380
381 // duplicated names ids that appear more than once in the tree.
382 duplicated map[string]bool
383 }
384
385 // buildDocIndex walks a tree and resolves every document's id.
386 //
387 // A document whose frontmatter will not parse, or that carries no valid id, is
388 // recorded by path and left out of the id map rather than failing the walk. The
389 // registry and the update hook are what keep those out of the approved branch;
390 // making one malformed document — which --push-option=skip-validation can
391 // always produce — block every future merge in the space would turn a typo into
392 // an outage. It is still not silently overwritten: byPath keeps its path
393 // occupied, so a proposal targeting it is refused as stale.
394 //
395 // The same reasoning applies to duplicated ids: they are recorded, and only
396 // refused when the merge actually needs to resolve one of them.
397 26 func (r *Repo) buildDocIndex(ctx context.Context, t *object.Tree) (*docIndex, error) {
398 26 budget := r.newBudget()
399 26 var entries []docEntry
400 26 if err := r.collectDocs(ctx, t, "", 0, budget, &entries); err != nil {
401 0 return nil, err
402 0 }
403 26 idx := &docIndex{
404 26 byID: make(map[string]string, len(entries)),
405 26 byPath: make(map[string]string, len(entries)),
406 26 duplicated: map[string]bool{},
407 26 }
408 31 for _, e := range entries {
409 31 if err := ctx.Err(); err != nil {
410 0 return nil, err
411 0 }
412 31 data, err := r.readBlob(e.hash, e.path)
413 31 if err != nil {
414 0 return nil, err
415 0 }
416 31 if err := budget.read(e.path, int64(len(data))); err != nil {
417 0 return nil, err
418 0 }
419 31 idx.byPath[e.path] = ""
420 31 fm, _, err := core.ParseDocument(data)
421 31 if err != nil {
422 4 continue
423 }
424 27 if err := core.ValidateDocID(fm.ID); err != nil {
425 0 continue
426 }
427 27 idx.byPath[e.path] = fm.ID
428 27 if _, dup := idx.byID[fm.ID]; dup {
429 0 idx.duplicated[fm.ID] = true
430 0 continue
431 }
432 27 idx.byID[fm.ID] = e.path
433 }
434 26 return idx, nil
435 }
436
437 // blobAt returns the blob sha of a document already known to be in the tree.
438 8 func blobAt(t *object.Tree, path string) (plumbing.Hash, error) {
439 8 entry, err := t.FindEntry(path)
440 8 if err != nil {
441 0 return plumbing.ZeroHash, fmt.Errorf("gitx: %q vanished from tree %s: %w", path, t.Hash, err)
442 0 }
443 8 return entry.Hash, nil
444 }