this repo has no description
1package gitdiff
2
3import (
4 "errors"
5 "fmt"
6 "io"
7)
8
9// Conflict indicates an apply failed due to a conflict between the patch and
10// the source content.
11//
12// Users can test if an error was caused by a conflict by using errors.Is with
13// an empty Conflict:
14//
15// if errors.Is(err, &Conflict{}) {
16// // handle conflict
17// }
18//
19type Conflict struct {
20 msg string
21}
22
23func (c *Conflict) Error() string {
24 return "conflict: " + c.msg
25}
26
27// Is implements error matching for Conflict. Passing an empty instance of
28// Conflict always returns true.
29func (c *Conflict) Is(other error) bool {
30 if other, ok := other.(*Conflict); ok {
31 return other.msg == "" || other.msg == c.msg
32 }
33 return false
34}
35
36// ApplyError wraps an error that occurs during patch application with
37// additional location information, if it is available.
38type ApplyError struct {
39 // Line is the one-indexed line number in the source data
40 Line int64
41 // Fragment is the one-indexed fragment number in the file
42 Fragment int
43 // FragmentLine is the one-indexed line number in the fragment
44 FragmentLine int
45
46 err error
47}
48
49// Unwrap returns the wrapped error.
50func (e *ApplyError) Unwrap() error {
51 return e.err
52}
53
54func (e *ApplyError) Error() string {
55 return fmt.Sprintf("%v", e.err)
56}
57
58type lineNum int
59type fragNum int
60type fragLineNum int
61
62// applyError creates a new *ApplyError wrapping err or augments the information
63// in err with args if it is already an *ApplyError. Returns nil if err is nil.
64func applyError(err error, args ...interface{}) error {
65 if err == nil {
66 return nil
67 }
68
69 e, ok := err.(*ApplyError)
70 if !ok {
71 e = &ApplyError{err: wrapEOF(err)}
72 }
73 for _, arg := range args {
74 switch v := arg.(type) {
75 case lineNum:
76 e.Line = int64(v) + 1
77 case fragNum:
78 e.Fragment = int(v) + 1
79 case fragLineNum:
80 e.FragmentLine = int(v) + 1
81 }
82 }
83 return e
84}
85
86var (
87 errApplyInProgress = errors.New("gitdiff: incompatible apply in progress")
88)
89
90const (
91 applyInitial = iota
92 applyText
93 applyBinary
94)
95
96// Applier applies changes described in fragments to source data. If changes
97// are described in multiple fragments, those fragments must be applied in
98// order, usually by calling ApplyFile.
99//
100// By default, Applier operates in "strict" mode, where fragment content and
101// positions must exactly match those of the source.
102//
103// If an error occurs while applying, methods on Applier return instances of
104// *ApplyError that annotate the wrapped error with additional information
105// when available. If the error is because of a conflict between a fragment and
106// the source, the wrapped error will be a *Conflict.
107//
108// While an Applier can apply both text and binary fragments, only one fragment
109// type can be used without resetting the Applier. The first fragment applied
110// sets the type for the Applier. Mixing fragment types or mixing
111// fragment-level and file-level applies results in an error.
112type Applier struct {
113 src io.ReaderAt
114 lineSrc LineReaderAt
115 nextLine int64
116 applyType int
117}
118
119// NewApplier creates an Applier that reads data from src. If src is a
120// LineReaderAt, it is used directly to apply text fragments.
121func NewApplier(src io.ReaderAt) *Applier {
122 a := new(Applier)
123 a.Reset(src)
124 return a
125}
126
127// Reset resets the input and internal state of the Applier. If src is nil, the
128// existing source is reused.
129func (a *Applier) Reset(src io.ReaderAt) {
130 if src != nil {
131 a.src = src
132 if lineSrc, ok := src.(LineReaderAt); ok {
133 a.lineSrc = lineSrc
134 } else {
135 a.lineSrc = &lineReaderAt{r: src}
136 }
137 }
138 a.nextLine = 0
139 a.applyType = applyInitial
140}
141
142// ApplyFile applies the changes in all of the fragments of f and writes the
143// result to dst.
144func (a *Applier) ApplyFile(dst io.Writer, f *File) error {
145 if a.applyType != applyInitial {
146 return applyError(errApplyInProgress)
147 }
148
149 if f.IsBinary && f.BinaryFragment != nil {
150 return a.ApplyBinaryFragment(dst, f.BinaryFragment)
151 }
152
153 // TODO(bkeyes): sort fragments by start position
154 // TODO(bkeyes): merge overlapping fragments
155
156 for i, frag := range f.TextFragments {
157 if err := a.ApplyTextFragment(dst, frag); err != nil {
158 return applyError(err, fragNum(i))
159 }
160 }
161
162 return applyError(a.Flush(dst))
163}
164
165// ApplyTextFragment applies the changes in the fragment f and writes unwritten
166// data before the start of the fragment and the result to dst. If multiple
167// text fragments apply to the same source, ApplyTextFragment must be called in
168// order of increasing start position. As a result, each fragment can be
169// applied at most once before a call to Reset.
170func (a *Applier) ApplyTextFragment(dst io.Writer, f *TextFragment) error {
171 switch a.applyType {
172 case applyInitial, applyText:
173 default:
174 return applyError(errApplyInProgress)
175 }
176 a.applyType = applyText
177
178 // application code assumes fragment fields are consistent
179 if err := f.Validate(); err != nil {
180 return applyError(err)
181 }
182
183 // lines are 0-indexed, positions are 1-indexed (but new files have position = 0)
184 fragStart := f.OldPosition - 1
185 if fragStart < 0 {
186 fragStart = 0
187 }
188 fragEnd := fragStart + f.OldLines
189
190 start := a.nextLine
191 if fragStart < start {
192 return applyError(&Conflict{"fragment overlaps with an applied fragment"})
193 }
194
195 if f.OldPosition == 0 {
196 ok, err := isLen(a.src, 0)
197 if err != nil {
198 return applyError(err)
199 }
200 if !ok {
201 return applyError(&Conflict{"cannot create new file from non-empty src"})
202 }
203 }
204
205 preimage := make([][]byte, fragEnd-start)
206 n, err := a.lineSrc.ReadLinesAt(preimage, start)
207 switch {
208 case err == nil:
209 case err == io.EOF && n == len(preimage): // last line of frag has no newline character
210 default:
211 return applyError(err, lineNum(start+int64(n)))
212 }
213
214 // copy leading data before the fragment starts
215 for i, line := range preimage[:fragStart-start] {
216 if _, err := dst.Write(line); err != nil {
217 a.nextLine = start + int64(i)
218 return applyError(err, lineNum(a.nextLine))
219 }
220 }
221 preimage = preimage[fragStart-start:]
222
223 // apply the changes in the fragment
224 used := int64(0)
225 for i, line := range f.Lines {
226 if err := applyTextLine(dst, line, preimage, used); err != nil {
227 a.nextLine = fragStart + used
228 return applyError(err, lineNum(a.nextLine), fragLineNum(i))
229 }
230 if line.Old() {
231 used++
232 }
233 }
234 a.nextLine = fragStart + used
235 return nil
236}
237
238func applyTextLine(dst io.Writer, line Line, preimage [][]byte, i int64) (err error) {
239 if line.Old() && string(preimage[i]) != line.Line {
240 return &Conflict{"fragment line does not match src line"}
241 }
242 if line.New() {
243 _, err = io.WriteString(dst, line.Line)
244 }
245 return err
246}
247
248// Flush writes any data following the last applied fragment to dst.
249func (a *Applier) Flush(dst io.Writer) (err error) {
250 switch a.applyType {
251 case applyInitial:
252 _, err = copyFrom(dst, a.src, 0)
253 case applyText:
254 _, err = copyLinesFrom(dst, a.lineSrc, a.nextLine)
255 case applyBinary:
256 // nothing to flush, binary apply "consumes" full source
257 }
258 return err
259}
260
261// ApplyBinaryFragment applies the changes in the fragment f and writes the
262// result to dst. At most one binary fragment can be applied before a call to
263// Reset.
264func (a *Applier) ApplyBinaryFragment(dst io.Writer, f *BinaryFragment) error {
265 if a.applyType != applyInitial {
266 return applyError(errApplyInProgress)
267 }
268 a.applyType = applyText
269
270 if f == nil {
271 return applyError(errors.New("nil fragment"))
272 }
273
274 switch f.Method {
275 case BinaryPatchLiteral:
276 if _, err := dst.Write(f.Data); err != nil {
277 return applyError(err)
278 }
279 case BinaryPatchDelta:
280 if err := applyBinaryDeltaFragment(dst, a.src, f.Data); err != nil {
281 return applyError(err)
282 }
283 default:
284 return applyError(fmt.Errorf("unsupported binary patch method: %v", f.Method))
285 }
286 return nil
287}
288
289func applyBinaryDeltaFragment(dst io.Writer, src io.ReaderAt, frag []byte) error {
290 srcSize, delta := readBinaryDeltaSize(frag)
291 if err := checkBinarySrcSize(src, srcSize); err != nil {
292 return err
293 }
294
295 dstSize, delta := readBinaryDeltaSize(delta)
296
297 for len(delta) > 0 {
298 op := delta[0]
299 if op == 0 {
300 return errors.New("invalid delta opcode 0")
301 }
302
303 var n int64
304 var err error
305 switch op & 0x80 {
306 case 0x80:
307 n, delta, err = applyBinaryDeltaCopy(dst, op, delta[1:], src)
308 case 0x00:
309 n, delta, err = applyBinaryDeltaAdd(dst, op, delta[1:])
310 }
311 if err != nil {
312 return err
313 }
314 dstSize -= n
315 }
316
317 if dstSize != 0 {
318 return errors.New("corrupt binary delta: insufficient or extra data")
319 }
320 return nil
321}
322
323// readBinaryDeltaSize reads a variable length size from a delta-encoded binary
324// fragment, returing the size and the unused data. Data is encoded as:
325//
326// [[1xxxxxxx]...] [0xxxxxxx]
327//
328// in little-endian order, with 7 bits of the value per byte.
329func readBinaryDeltaSize(d []byte) (size int64, rest []byte) {
330 shift := uint(0)
331 for i, b := range d {
332 size |= int64(b&0x7F) << shift
333 shift += 7
334 if b <= 0x7F {
335 return size, d[i+1:]
336 }
337 }
338 return size, nil
339}
340
341// applyBinaryDeltaAdd applies an add opcode in a delta-encoded binary
342// fragment, returning the amount of data written and the usused part of the
343// fragment. An add operation takes the form:
344//
345// [0xxxxxx][[data1]...]
346//
347// where the lower seven bits of the opcode is the number of data bytes
348// following the opcode. See also pack-format.txt in the Git source.
349func applyBinaryDeltaAdd(w io.Writer, op byte, delta []byte) (n int64, rest []byte, err error) {
350 size := int(op)
351 if len(delta) < size {
352 return 0, delta, errors.New("corrupt binary delta: incomplete add")
353 }
354 _, err = w.Write(delta[:size])
355 return int64(size), delta[size:], err
356}
357
358// applyBinaryDeltaCopy applies a copy opcode in a delta-encoded binary
359// fragment, returing the amount of data written and the unused part of the
360// fragment. A copy operation takes the form:
361//
362// [1xxxxxxx][offset1][offset2][offset3][offset4][size1][size2][size3]
363//
364// where the lower seven bits of the opcode determine which non-zero offset and
365// size bytes are present in little-endian order: if bit 0 is set, offset1 is
366// present, etc. If no offset or size bytes are present, offset is 0 and size
367// is 0x10000. See also pack-format.txt in the Git source.
368func applyBinaryDeltaCopy(w io.Writer, op byte, delta []byte, src io.ReaderAt) (n int64, rest []byte, err error) {
369 const defaultSize = 0x10000
370
371 unpack := func(start, bits uint) (v int64) {
372 for i := uint(0); i < bits; i++ {
373 mask := byte(1 << (i + start))
374 if op&mask > 0 {
375 if len(delta) == 0 {
376 err = errors.New("corrupt binary delta: incomplete copy")
377 return
378 }
379 v |= int64(delta[0]) << (8 * i)
380 delta = delta[1:]
381 }
382 }
383 return
384 }
385
386 offset := unpack(0, 4)
387 size := unpack(4, 3)
388 if err != nil {
389 return 0, delta, err
390 }
391 if size == 0 {
392 size = defaultSize
393 }
394
395 // TODO(bkeyes): consider pooling these buffers
396 b := make([]byte, size)
397 if _, err := src.ReadAt(b, offset); err != nil {
398 return 0, delta, wrapEOF(err)
399 }
400
401 _, err = w.Write(b)
402 return size, delta, err
403}
404
405func checkBinarySrcSize(r io.ReaderAt, size int64) error {
406 ok, err := isLen(r, size)
407 if err != nil {
408 return err
409 }
410 if !ok {
411 return &Conflict{"fragment src size does not match actual src size"}
412 }
413 return nil
414}
415
416func wrapEOF(err error) error {
417 if err == io.EOF {
418 err = io.ErrUnexpectedEOF
419 }
420 return err
421}