Home | History | Annotate | Download | only in edit 
      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.
      6 package edit
      7 
      8 import (
      9 	"fmt"
     10 	"sort"
     11 )
     12 
     13 // A Buffer is a queue of edits to apply to a given byte slice.
     14 type 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.
     20 type 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.
     27 type edits []edit
     28 
     29 func (x edits) Len() int      { return len(x) }
     30 func (x edits) Swap(i, j int) { x[i], x[j] = x[j], x[i] }
     31 func (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.
     41 func NewBuffer(data []byte) *Buffer {
     42 	return &Buffer{old: data}
     43 }
     44 
     45 func (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 
     52 func (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 
     59 func (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.
     68 func (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.
     91 func (b *Buffer) String() string {
     92 	return string(b.Bytes())
     93 }
     94