1// Copyright 2017 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 edit implements buffered position-based editing of byte slices.
6package edit
7
8import (
9	"fmt"
10	"sort"
11)
12
13// A Buffer is a queue of edits to apply to a given byte slice.
14type Buffer struct {
15	old []byte
16	q   edits
17}
18
19// An edit records a single text modification: change the bytes in [start,end) to new.
20type edit struct {
21	start int
22	end   int
23	new   string
24}
25
26// An edits is a list of edits that is sortable by start offset, breaking ties by end offset.
27type edits []edit
28
29func (x edits) Len() int      { return len(x) }
30func (x edits) Swap(i, j int) { x[i], x[j] = x[j], x[i] }
31func (x edits) Less(i, j int) bool {
32	if x[i].start != x[j].start {
33		return x[i].start < x[j].start
34	}
35	return x[i].end < x[j].end
36}
37
38// NewBuffer returns a new buffer to accumulate changes to an initial data slice.
39// The returned buffer maintains a reference to the data, so the caller must ensure
40// the data is not modified until after the Buffer is done being used.
41func NewBuffer(data []byte) *Buffer {
42	return &Buffer{old: data}
43}
44
45func (b *Buffer) Insert(pos int, new string) {
46	if pos < 0 || pos > len(b.old) {
47		panic("invalid edit position")
48	}
49	b.q = append(b.q, edit{pos, pos, new})
50}
51
52func (b *Buffer) Delete(start, end int) {
53	if end < start || start < 0 || end > len(b.old) {
54		panic("invalid edit position")
55	}
56	b.q = append(b.q, edit{start, end, ""})
57}
58
59func (b *Buffer) Replace(start, end int, new string) {
60	if end < start || start < 0 || end > len(b.old) {
61		panic("invalid edit position")
62	}
63	b.q = append(b.q, edit{start, end, new})
64}
65
66// Bytes returns a new byte slice containing the original data
67// with the queued edits applied.
68func (b *Buffer) Bytes() []byte {
69	// Sort edits by starting position and then by ending position.
70	// Breaking ties by ending position allows insertions at point x
71	// to be applied before a replacement of the text at [x, y).
72	sort.Stable(b.q)
73
74	var new []byte
75	offset := 0
76	for i, e := range b.q {
77		if e.start < offset {
78			e0 := b.q[i-1]
79			panic(fmt.Sprintf("overlapping edits: [%d,%d)->%q, [%d,%d)->%q", e0.start, e0.end, e0.new, e.start, e.end, e.new))
80		}
81		new = append(new, b.old[offset:e.start]...)
82		offset = e.end
83		new = append(new, e.new...)
84	}
85	new = append(new, b.old[offset:]...)
86	return new
87}
88
89// String returns a string containing the original data
90// with the queued edits applied.
91func (b *Buffer) String() string {
92	return string(b.Bytes())
93}
94