1// Copyright 2025 The Go Authors. All rights reserved.
 2// Use of this source code is governed by a BSD-style
 3// license that can be found in the LICENSE file.
 4
 5package udiff
 6
 7import (
 8	"slices"
 9)
10
11// Merge merges two valid, ordered lists of edits.
12// It returns zero if there was a conflict.
13//
14// If corresponding edits in x and y are identical,
15// they are coalesced in the result.
16//
17// If x and y both provide different insertions at the same point,
18// the insertions from x will be first in the result.
19//
20// TODO(adonovan): this algorithm could be improved, for example by
21// working harder to coalesce non-identical edits that share a common
22// deletion or common prefix of insertion (see the tests).
23// Survey the academic literature for insights.
24func Merge(x, y []Edit) ([]Edit, bool) {
25	// Make a defensive (premature) copy of the arrays.
26	x = slices.Clone(x)
27	y = slices.Clone(y)
28
29	var merged []Edit
30	add := func(edit Edit) {
31		merged = append(merged, edit)
32	}
33	var xi, yi int
34	for xi < len(x) && yi < len(y) {
35		px := &x[xi]
36		py := &y[yi]
37
38		if *px == *py {
39			// x and y are identical: coalesce.
40			add(*px)
41			xi++
42			yi++
43
44		} else if px.End <= py.Start {
45			// x is entirely before y,
46			// or an insertion at start of y.
47			add(*px)
48			xi++
49
50		} else if py.End <= px.Start {
51			// y is entirely before x,
52			// or an insertion at start of x.
53			add(*py)
54			yi++
55
56		} else if px.Start < py.Start {
57			// x is partly before y:
58			// split it into a deletion and an edit.
59			add(Edit{px.Start, py.Start, ""})
60			px.Start = py.Start
61
62		} else if py.Start < px.Start {
63			// y is partly before x:
64			// split it into a deletion and an edit.
65			add(Edit{py.Start, px.Start, ""})
66			py.Start = px.Start
67
68		} else {
69			// x and y are unequal non-insertions
70			// at the same point: conflict.
71			return nil, false
72		}
73	}
74	for ; xi < len(x); xi++ {
75		add(x[xi])
76	}
77	for ; yi < len(y); yi++ {
78		add(y[yi])
79	}
80	return merged, true
81}