merge.go

     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  
     5  package diff
     6  
     7  import (
     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.
    24  func 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  }
    82
View as plain text