Repository navigation
Expand file tree
/
Copy pathparse.go
More file actions
509 lines (472 loc) · 13.5 KB
/
Copy pathparse.go
File metadata and controls
509 lines (472 loc) · 13.5 KB
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
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
package gitconfig
import (
"bytes"
"strings"
)
// A file is kept as its bytes plus a list of items covering them exactly,
// in order: parsing never drops a byte, and edits splice the bytes, then
// parse them again.
type itemKind uint8
const (
itemBOM itemKind = iota // the UTF-8 byte order mark, first in the file
itemSpace // spaces, tabs and lone CRs
itemNewline // "\n" or "\r\n"
itemComment // from '#' or ';' to the end of the line, newline excluded
itemHeader // from '[' to ']'
itemEntry // from the key to the end of the value, continuation lines included
)
// item is one piece of the file. It holds no pointer, so that a large file
// costs the garbage collector nothing to scan: the decoded data of headers
// and entries is in the tables of parsed. Offsets are 32-bit, as a file is
// at most maxLoadBytes: an item is 24 bytes.
type item struct {
kind itemKind
implicit bool // entries only: no '='
open openEnd // entries only
sec int32 // the section a header opens or an entry is in: index in parsed.secs, 0 before any header
text int32 // entries only: index in parsed.texts
start int32 // bytes of the item: data[start:end]
end int32
line int32 // line of start, 1-based
}
// entryText is the key name and the value of an entry.
type entryText struct {
name string // lowered
value string // decoded
}
// parsed is a parsed file: its items, and the data they refer to.
type parsed struct {
items []item
// secs[0] is the zero sectionKey, for entries before any header. No
// header has it: a header always has a section name or a subsection.
secs []sectionKey
texts []entryText
}
func (p *parsed) secOf(it item) sectionKey { return p.secs[it.sec] }
func (p *parsed) nameOf(it item) string { return p.texts[it.text].name }
func (p *parsed) valueOf(it item) string { return p.texts[it.text].value }
// entries appends the entries of the file, those before any header left
// out, to out.
func (p *parsed) entries(scope Scope, file string, out []Entry) []Entry {
for _, it := range p.items {
if it.kind != itemEntry || it.sec == 0 {
continue
}
sec := p.secs[it.sec]
t := p.texts[it.text]
out = append(out, Entry{
Key: Key{Section: sec.section, Subsection: sec.subsection, HasSubsection: sec.hasSub, Name: t.name},
Value: t.value,
Implicit: it.implicit,
Origin: Origin{Scope: scope, File: file, Line: int(it.line)},
})
}
return out
}
// openEnd tells how an entry at the end of the file ends, for an edit that
// adds a line after it.
type openEnd uint8
const (
closed openEnd = iota // the next line is not part of the value
continued // a backslash-newline ends the file: the next line would continue the value
backslashEOF // a backslash ends the file: a newline would continue the value
)
var bom = []byte("\xef\xbb\xbf")
type parser struct {
parsed
name string
data []byte
pos int
line int
// budget is what remains of the entries and distinct header spellings
// allowed, shared by the files of a load.
budget *int
// emit, if set, receives the entries of the file, those before any
// header left out, and no item is kept: the parse of a load. An error
// it returns stops the parse and is returned as is.
emit func(Entry) error
scope Scope // of the entries given to emit
sec int32 // current section
secIndex map[sectionKey]int32
headers map[string]int32 // the section of each header, by its bytes
names map[string]string // key names, interned
buf []byte // scratch for values and subsections
}
func newParser(name string, data []byte, budget *int) *parser {
return &parser{
name: name, data: data, line: 1, budget: budget,
parsed: parsed{secs: []sectionKey{{}}},
secIndex: make(map[sectionKey]int32),
headers: make(map[string]int32),
names: make(map[string]string),
}
}
// parseFile splits data into items, or returns the *SyntaxError git would
// report. Beyond the limits of one file, it returns ErrLoadLimit.
func parseFile(name string, data []byte) (parsed, error) {
if len(data) > maxLoadBytes {
return parsed{}, ErrLoadLimit
}
p := newParser(name, data, new(maxLoadEntries))
p.items = make([]item, 0, min(2*bytes.Count(data, []byte{'\n'})+4, maxFileItems))
if err := p.run(); err != nil {
return parsed{}, err
}
return p.parsed, nil
}
// parseEntries gives the entries of data to emit, in order, with scope and
// name as their origin, without keeping the items of the file. It returns
// the *SyntaxError git would report, ErrLoadLimit once budget is spent, or
// the error of emit.
//
// Like git, it stops at the first error: entries before it have been given
// to emit, and an include they hold has been followed.
func parseEntries(name string, data []byte, scope Scope, budget *int, emit func(Entry) error) error {
p := newParser(name, data, budget)
p.emit, p.scope = emit, scope
return p.run()
}
func (p *parser) errorAt(line int, msg string) error {
return &SyntaxError{File: p.name, Line: line, Msg: msg}
}
// spend takes one from the budget.
func (p *parser) spend() error {
if *p.budget <= 0 {
return ErrLoadLimit
}
*p.budget--
return nil
}
// add adds an item, unless the parse keeps no item.
func (p *parser) add(kind itemKind, start, end int) {
if p.emit == nil {
p.items = append(p.items, item{kind: kind, start: int32(start), end: int32(end), line: int32(p.line), sec: p.sec})
}
}
// addEntry adds an entry item, or gives the entry to emit.
func (p *parser) addEntry(start, end int, name []byte, value string, implicit bool, open openEnd) error {
if err := p.spend(); err != nil {
return err
}
n, ok := p.names[string(name)]
if !ok {
n = lowerASCII(string(name))
p.names[string(name)] = n
}
if p.emit != nil {
if p.sec == 0 {
return nil
}
sec := p.secs[p.sec]
return p.emit(Entry{
Key: Key{Section: sec.section, Subsection: sec.subsection, HasSubsection: sec.hasSub, Name: n},
Value: value,
Implicit: implicit,
Origin: Origin{Scope: p.scope, File: p.name, Line: p.line},
})
}
p.items = append(p.items, item{
kind: itemEntry, implicit: implicit, open: open, sec: p.sec, text: int32(len(p.texts)),
start: int32(start), end: int32(end), line: int32(p.line),
})
p.texts = append(p.texts, entryText{n, value})
return nil
}
// section returns the index of sec in p.secs, adding it if absent.
func (p *parser) section(sec sectionKey) int32 {
i, ok := p.secIndex[sec]
if !ok {
i = int32(len(p.secs))
p.secs = append(p.secs, sec)
p.secIndex[sec] = i
}
return i
}
// isSpace reports whether data[i] is whitespace between tokens: a space, a
// tab, or a CR that does not start a CRLF.
func isSpace(data []byte, i int) bool {
switch data[i] {
case ' ', '\t':
return true
case '\r':
return !isNewline(data, i)
}
return false
}
// isNewline reports whether a newline, "\n" or "\r\n", starts at data[i].
func isNewline(data []byte, i int) bool {
return data[i] == '\n' || data[i] == '\r' && i+1 < len(data) && data[i+1] == '\n'
}
// newlineLen returns the length of the newline at data[i].
func newlineLen(data []byte, i int) int {
if data[i] == '\r' {
return 2
}
return 1
}
func (p *parser) run() error {
d := p.data
if bytes.HasPrefix(d, bom) {
p.add(itemBOM, 0, len(bom))
p.pos = len(bom)
}
for p.pos < len(d) {
// Each turn adds at most one item.
if len(p.items) >= maxFileItems {
return ErrLoadLimit
}
start := p.pos
c := d[start]
switch {
case isSpace(d, start):
for p.pos < len(d) && isSpace(d, p.pos) {
p.pos++
}
p.add(itemSpace, start, p.pos)
case isNewline(d, start):
p.pos += newlineLen(d, start)
p.add(itemNewline, start, p.pos)
p.line++
case c == '#' || c == ';':
end := len(d)
if i := bytes.IndexByte(d[start:], '\n'); i >= 0 {
end = start + i
if d[end-1] == '\r' {
end--
}
}
p.pos = end
p.add(itemComment, start, end)
case c == '[':
if err := p.header(); err != nil {
return err
}
case isAlpha(c):
if err := p.entry(); err != nil {
return err
}
default:
return p.errorAt(p.line, "invalid line")
}
}
return nil
}
func (p *parser) header() error {
d := p.data
start := p.pos
i := start + 1
for i < len(d) && (isKeyChar(d[i]) || d[i] == '.') {
i++
}
nameEnd := i
if i == len(d) {
// git counts the end of the line it stopped at, and so reports the
// next line for an unterminated header or value.
return p.errorAt(p.line+1, "unterminated section header")
}
// sub reuses the parser's scratch buffer, and gives it back grown.
sub := p.buf[:0]
defer func() { p.buf = sub[:0] }()
hasSub := false
switch {
case d[i] == ']':
if nameEnd == start+1 {
return p.errorAt(p.line, "empty section name")
}
i++
case isSpace(d, i):
for i < len(d) && isSpace(d, i) {
i++
}
if i == len(d) || d[i] != '"' {
return p.errorAt(p.line, "invalid section header")
}
i++
for {
if i == len(d) || d[i] == '\n' {
return p.errorAt(p.line, "unterminated subsection")
}
c := d[i]
if c == '"' {
break
}
if c == '\\' {
i++
if i == len(d) || d[i] == '\n' {
return p.errorAt(p.line, "unterminated subsection")
}
c = d[i]
}
if c == 0 {
// git cuts the subsection at the NUL, reading a key the
// file does not spell.
return p.errorAt(p.line, "NUL byte in subsection")
}
sub = append(sub, c)
i++
}
i++
if i == len(d) || isNewline(d, i) {
return p.errorAt(p.line+1, "unterminated section header")
}
if d[i] != ']' {
return p.errorAt(p.line, "invalid section header")
}
i++
hasSub = true
default:
return p.errorAt(p.line, "invalid section header")
}
// The section is decoded once for each spelling of a header: files
// repeat their headers.
sec, ok := p.headers[string(d[start:i])]
if !ok {
if err := p.spend(); err != nil {
return err
}
sec = p.section(headerKey(lowerASCII(string(d[start+1:nameEnd])), sub, hasSub))
p.headers[string(d[start:i])] = sec
}
p.sec = sec
p.pos = i
p.add(itemHeader, start, i)
return nil
}
// headerKey returns the section of a header with the lowered name, and the
// subsection sub if hasSub.
func headerKey(name string, sub []byte, hasSub bool) sectionKey {
dot := strings.IndexByte(name, '.')
switch {
case !hasSub && dot < 0:
return sectionKey{section: name}
case !hasSub:
// Legacy header [a.B]: subsection "b".
return sectionKey{name[:dot], name[dot+1:], true}
case dot < 0:
return sectionKey{name, string(sub), true}
}
// [a.b "x"]: git reads the keys as a.b.x.<name>.
return sectionKey{name[:dot], name[dot+1:] + "." + string(sub), true}
}
func (p *parser) entry() error {
d := p.data
start := p.pos
i := start
for i < len(d) && isKeyChar(d[i]) {
i++
}
name := d[start:i]
j := i
for j < len(d) && (d[j] == ' ' || d[j] == '\t') {
j++
}
if j == len(d) || isNewline(d, j) {
// No '=': an implicit value. The entry ends with its name; the
// whitespace after it is an item of its own.
p.pos = i
return p.addEntry(start, i, name, "", true, closed)
}
if d[j] != '=' {
return p.errorAt(p.line, "invalid key")
}
value, end, lines, open, err := p.value(j + 1)
if err != nil {
return err
}
p.pos = end
if err := p.addEntry(start, end, name, value, false, open); err != nil {
return err
}
p.line += lines
return nil
}
// value decodes the value starting at data[i], up to a comment, the end of
// the line or the end of the file. It returns the value, where it ends and
// how many continuation lines it spans, and how it ends if it ends the file.
//
// Whitespace outside quotes is skipped before the value, and held back
// inside it: an escape, a quote or any other character writes it out first,
// and the end of the value drops it.
func (p *parser) value(i int) (string, int, int, openEnd, error) {
d := p.data
buf := p.buf[:0]
defer func() { p.buf = buf[:0] }()
pending := -1 // start of held-back whitespace, -1 if none
inQuote := false
lines := 0
open := closed
flush := func(at int) {
if pending >= 0 {
buf = append(buf, d[pending:at]...)
pending = -1
}
}
loop:
for i < len(d) && !isNewline(d, i) {
c := d[i]
switch {
case c == '\\':
if i+1 == len(d) {
// A backslash ends the file. Outside quotes it is dropped.
if inQuote {
return "", 0, 0, 0, p.errorAt(p.line+lines+1, "unterminated quote")
}
flush(i)
i++
open = backslashEOF
continue
}
flush(i)
if isNewline(d, i+1) {
i += 1 + newlineLen(d, i+1)
lines++
if i == len(d) {
open = continued
}
continue
}
switch d[i+1] {
case 't':
buf = append(buf, '\t')
case 'n':
buf = append(buf, '\n')
case 'b':
buf = append(buf, '\b')
case '"', '\\':
buf = append(buf, d[i+1])
default:
return "", 0, 0, 0, p.errorAt(p.line+lines, "invalid escape")
}
i += 2
case c == '"':
flush(i)
inQuote = !inQuote
i++
case inQuote:
buf = append(buf, c)
i++
case c == ' ' || c == '\t' || c == '\r':
// A CR here is a lone one: the loop stops at a CRLF.
if len(buf) > 0 && pending < 0 {
pending = i
}
i++
case c == '#' || c == ';':
break loop
default:
flush(i)
buf = append(buf, c)
i++
}
}
// A comment ends the value only outside quotes: the quote is open only
// at a newline or the end of the file.
if inQuote {
return "", 0, 0, 0, p.errorAt(p.line+lines, "unterminated quote")
}
if n := bytes.IndexByte(buf, 0); n >= 0 {
// git stops reading the value at a NUL byte.
buf = buf[:n]
}
return string(buf), i, lines, open, nil
}