summaryrefslogtreecommitdiff
path: root/src/pkg/patch/patch.go
blob: e8ed627f7e9af7ec5b2c558e53c71cc0429a89cb (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
// Copyright 2009 The Go Authors.  All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Package patch implements parsing and execution of the textual and
// binary patch descriptions used by version control tools such as
// CVS, GIT, Mercurial, and Subversion.
package patch

import (
	"bytes";
	"os";
	"path";
	"strings";
)

// A Set represents a set of patches to be applied as a single atomic unit.
// Patch sets are often preceded by a descriptive header.
type Set struct {
	Header	string;	// free-form text
	File	[]*File;
}

// A File represents a collection of changes to be made to a single file.
type File struct {
	Verb			Verb;
	Src			string;	// source for Verb == Copy, Verb == Rename
	Dst			string;
	OldMode, NewMode	int;	// 0 indicates not used
	Diff;				// changes to data; == NoDiff if operation does not edit file
}

// A Verb is an action performed on a file.
type Verb string

const (
	Add	Verb	= "add";
	Copy	Verb	= "copy";
	Delete	Verb	= "delete";
	Edit	Verb	= "edit";
	Rename	Verb	= "rename";
)

// A Diff is any object that describes changes to transform
// an old byte stream to a new one.
type Diff interface {
	// Apply applies the changes listed in the diff
	// to the string s, returning the new version of the string.
	// Note that the string s need not be a text string.
	Apply(old []byte) (new []byte, err os.Error);
}

// NoDiff is a no-op Diff implementation: it passes the
// old data through unchanged.
var NoDiff Diff = noDiffType(0)

type noDiffType int

func (noDiffType) Apply(old []byte) ([]byte, os.Error) {
	return old, nil;
}

// A SyntaxError represents a syntax error encountered while parsing a patch.
type SyntaxError string

func (e SyntaxError) String() string	{ return string(e) }

var newline = []byte{'\n'}

// Parse patches the patch text to create a patch Set.
// The patch text typically comprises a textual header and a sequence
// of file patches, as would be generated by CVS, Subversion,
// Mercurial, or GIT.
func Parse(text []byte) (*Set, os.Error) {
	// Split text into files.
	// CVS and Subversion begin new files with
	//	Index: file name.
	//	==================
	//	diff -u blah blah
	//
	// Mercurial and GIT use
	//	diff [--git] a/file/path b/file/path.
	//
	// First look for Index: lines.  If none, fall back on diff lines.
	text, files := sections(text, "Index: ");
	if len(files) == 0 {
		text, files = sections(text, "diff ");
	}

	set := &Set{string(text), make([]*File, len(files))};

	// Parse file header and then
	// parse files into patch chunks.
	// Each chunk begins with @@.
	for i, raw := range files {
		p := new(File);
		set.File[i] = p;

		// First line of hdr is the Index: that
		// begins the section.  After that is the file name.
		s, raw, _ := getLine(raw, 1);
		if hasPrefix(s, "Index: ") {
			p.Dst = string(bytes.TrimSpace(s[7:len(s)]));
			goto HaveName;
		} else if hasPrefix(s, "diff ") {
			str := string(bytes.TrimSpace(s));
			i := strings.LastIndex(str, " b/");
			if i >= 0 {
				p.Dst = str[i+3 : len(str)];
				goto HaveName;
			}
		}
		return nil, SyntaxError("unexpected patch header line: " + string(s));
	HaveName:
		p.Dst = path.Clean(p.Dst);
		if strings.HasPrefix(p.Dst, "../") || strings.HasPrefix(p.Dst, "/") {
			return nil, SyntaxError("invalid path: " + p.Dst);
		}

		// Parse header lines giving file information:
		//	new file mode %o	- file created
		//	deleted file mode %o	- file deleted
		//	old file mode %o	- file mode changed
		//	new file mode %o	- file mode changed
		//	rename from %s	- file renamed from other file
		//	rename to %s
		//	copy from %s		- file copied from other file
		//	copy to %s
		p.Verb = Edit;
		for len(raw) > 0 {
			oldraw := raw;
			var l []byte;
			l, raw, _ = getLine(raw, 1);
			l = bytes.TrimSpace(l);
			if m, s, ok := atoi(l, "new file mode ", 8); ok && len(s) == 0 {
				p.NewMode = m;
				p.Verb = Add;
				continue;
			}
			if m, s, ok := atoi(l, "deleted file mode ", 8); ok && len(s) == 0 {
				p.OldMode = m;
				p.Verb = Delete;
				p.Src = p.Dst;
				p.Dst = "";
				continue;
			}
			if m, s, ok := atoi(l, "old file mode ", 8); ok && len(s) == 0 {
				// usually implies p.Verb = "rename" or "copy"
				// but we'll get that from the rename or copy line.
				p.OldMode = m;
				continue;
			}
			if m, s, ok := atoi(l, "old mode ", 8); ok && len(s) == 0 {
				p.OldMode = m;
				continue;
			}
			if m, s, ok := atoi(l, "new mode ", 8); ok && len(s) == 0 {
				p.NewMode = m;
				continue;
			}
			if s, ok := skip(l, "rename from "); ok && len(s) > 0 {
				p.Src = string(s);
				p.Verb = Rename;
				continue;
			}
			if s, ok := skip(l, "rename to "); ok && len(s) > 0 {
				p.Verb = Rename;
				continue;
			}
			if s, ok := skip(l, "copy from "); ok && len(s) > 0 {
				p.Src = string(s);
				p.Verb = Copy;
				continue;
			}
			if s, ok := skip(l, "copy to "); ok && len(s) > 0 {
				p.Verb = Copy;
				continue;
			}
			if s, ok := skip(l, "Binary file "); ok && len(s) > 0 {
				// Hg prints
				//	Binary file foo has changed
				// when deleting a binary file.
				continue;
			}
			if s, ok := skip(l, "RCS file: "); ok && len(s) > 0 {
				// CVS prints
				//	RCS file: /cvs/plan9/bin/yesterday,v
				//	retrieving revision 1.1
				// for each file.
				continue;
			}
			if s, ok := skip(l, "retrieving revision "); ok && len(s) > 0 {
				// CVS prints
				//	RCS file: /cvs/plan9/bin/yesterday,v
				//	retrieving revision 1.1
				// for each file.
				continue;
			}
			if hasPrefix(l, "===") || hasPrefix(l, "---") || hasPrefix(l, "+++") || hasPrefix(l, "diff ") {
				continue;
			}
			if hasPrefix(l, "@@ -") {
				diff, err := ParseTextDiff(oldraw);
				if err != nil {
					return nil, err;
				}
				p.Diff = diff;
				break;
			}
			if hasPrefix(l, "index ") || hasPrefix(l, "GIT binary patch") {
				diff, err := ParseGITBinary(oldraw);
				if err != nil {
					return nil, err;
				}
				p.Diff = diff;
				break;
			}
			return nil, SyntaxError("unexpected patch header line: " + string(l));
		}
		if p.Diff == nil {
			p.Diff = NoDiff;
		}
		if p.Verb == Edit {
			p.Src = p.Dst;
		}
	}

	return set, nil;
}

// getLine returns the first n lines of data and the remainder.
// If data has no newline, getLine returns data, nil, false
func getLine(data []byte, n int) (first []byte, rest []byte, ok bool) {
	rest = data;
	ok = true;
	for ; n > 0; n-- {
		nl := bytes.Index(rest, newline);
		if nl < 0 {
			rest = nil;
			ok = false;
			break;
		}
		rest = rest[nl+1 : len(rest)];
	}
	first = data[0 : len(data)-len(rest)];
	return;
}

// sections returns a collection of file sections,
// each of which begins with a line satisfying prefix.
// text before the first instance of such a line is
// returned separately.
func sections(text []byte, prefix string) ([]byte, [][]byte) {
	n := 0;
	for b := text; ; {
		if hasPrefix(b, prefix) {
			n++;
		}
		nl := bytes.Index(b, newline);
		if nl < 0 {
			break;
		}
		b = b[nl+1 : len(b)];
	}

	sect := make([][]byte, n+1);
	n = 0;
	for b := text; ; {
		if hasPrefix(b, prefix) {
			sect[n] = text[0 : len(text)-len(b)];
			n++;
			text = b;
		}
		nl := bytes.Index(b, newline);
		if nl < 0 {
			sect[n] = text;
			break;
		}
		b = b[nl+1 : len(b)];
	}
	return sect[0], sect[1:len(sect)];
}

// if s begins with the prefix t, skip returns
// s with that prefix removed and ok == true.
func skip(s []byte, t string) (ss []byte, ok bool) {
	if len(s) < len(t) || string(s[0:len(t)]) != t {
		return nil, false;
	}
	return s[len(t):len(s)], true;
}

// if s begins with the prefix t and then is a sequence
// of digits in the given base, atoi returns the number
// represented by the digits and s with the
// prefix and the digits removed.
func atoi(s []byte, t string, base int) (n int, ss []byte, ok bool) {
	if s, ok = skip(s, t); !ok {
		return;
	}
	var i int;
	for i = 0; i < len(s) && '0' <= s[i] && s[i] <= byte('0'+base-1); i++ {
		n = n*base + int(s[i]-'0');
	}
	if i == 0 {
		return;
	}
	return n, s[i:len(s)], true;
}

// hasPrefix returns true if s begins with t.
func hasPrefix(s []byte, t string) bool {
	_, ok := skip(s, t);
	return ok;
}

// splitLines returns the result of splitting s into lines.
// The \n on each line is preserved.
func splitLines(s []byte) [][]byte	{ return bytes.SplitAfter(s, newline, 0) }