forked from cue-lang/cue
-
Notifications
You must be signed in to change notification settings - Fork 0
/
position.go
459 lines (396 loc) · 12.6 KB
/
position.go
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
// Copyright 2018 The CUE Authors
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
// http://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
package token
import (
"fmt"
"sort"
"sync"
)
// -----------------------------------------------------------------------------
// Positions
// Position describes an arbitrary source position
// including the file, line, and column location.
// A Position is valid if the line number is > 0.
type Position struct {
Filename string // filename, if any
Offset int // offset, starting at 0
Line int // line number, starting at 1
Column int // column number, starting at 1 (byte count)
// RelPos Pos // relative position information
}
// IsValid reports whether the position is valid.
func (pos *Position) IsValid() bool { return pos.Line > 0 }
// String returns a string in one of several forms:
//
// file:line:column valid position with file name
// line:column valid position without file name
// file invalid position with file name
// - invalid position without file name
func (pos Position) String() string {
s := pos.Filename
if pos.IsValid() {
if s != "" {
s += ":"
}
s += fmt.Sprintf("%d:%d", pos.Line, pos.Column)
}
if s == "" {
s = "-"
}
return s
}
// Pos is a compact encoding of a source position within a file, as well as
// relative positioning information. It can be converted into a Position for a
// more convenient, but much larger, representation.
type Pos struct {
file *File
offset int
}
// File returns the file that contains the position p or nil if there is no
// such file (for instance for p == NoPos).
func (p Pos) File() *File {
if p.index() == 0 {
return nil
}
return p.file
}
func (p Pos) Line() int {
if p.file == nil {
return 0
}
return p.Position().Line
}
func (p Pos) Column() int {
if p.file == nil {
return 0
}
return p.Position().Column
}
func (p Pos) Filename() string {
if p.file == nil {
return ""
}
return p.Position().Filename
}
func (p Pos) Position() Position {
if p.file == nil {
return Position{}
}
return p.file.Position(p)
}
func (p Pos) String() string {
return p.Position().String()
}
// NoPos is the zero value for Pos; there is no file and line information
// associated with it, and NoPos().IsValid() is false. NoPos is always
// smaller than any other Pos value. The corresponding Position value
// for NoPos is the zero value for Position.
var NoPos = Pos{}
// RelPos indicates the relative position of token to the previous token.
type RelPos int
const (
// NoRelPos indicates no relative position is specified.
NoRelPos RelPos = iota
// Elided indicates that the token for which this position is defined is
// not rendered at all.
Elided
// NoSpace indicates there is no whitespace after this token.
NoSpace
// Blank means there is horizontal space after this token.
Blank
// Newline means there is a single newline after this token.
Newline
// NewSection means there are two or more newlines after this token.
NewSection
relMask = 0xf
relShift = 4
)
var relNames = []string{
"invalid", "elided", "nospace", "blank", "newline", "section",
}
func (p RelPos) String() string { return relNames[p] }
func (p RelPos) Pos() Pos {
return Pos{nil, int(p)}
}
// HasRelPos repors whether p has a relative position.
func (p Pos) HasRelPos() bool {
return p.offset&relMask != 0
}
func (p Pos) Before(q Pos) bool {
return p.file == q.file && p.Offset() < q.Offset()
}
// Offset reports the byte offset relative to the file.
func (p Pos) Offset() int {
return p.Position().Offset
}
// Add creates a new position relative to the p offset by n.
func (p Pos) Add(n int) Pos {
return Pos{p.file, p.offset + toPos(index(n))}
}
// IsValid reports whether the position is valid.
func (p Pos) IsValid() bool {
return p != NoPos
}
// IsNewline reports whether the relative information suggests this node should
// be printed on a new lien.
func (p Pos) IsNewline() bool {
return p.RelPos() >= Newline
}
func (p Pos) WithRel(rel RelPos) Pos {
return Pos{p.file, p.offset&^relMask | int(rel)}
}
func (p Pos) RelPos() RelPos {
return RelPos(p.offset & relMask)
}
func (p Pos) index() index {
return index(p.offset) >> relShift
}
func toPos(x index) int {
return (int(x) << relShift)
}
// -----------------------------------------------------------------------------
// File
type index int
// A File has a name, size, and line offset table.
type File struct {
mutex sync.RWMutex
name string // file name as provided to AddFile
base index // Pos index range for this file is [base...base+size]
size index // file size as provided to AddFile
// lines and infos are protected by set.mutex
lines []index // lines contains the offset of the first character for each line (the first entry is always 0)
infos []lineInfo
}
// NewFile returns a new file.
func NewFile(filename string, base, size int) *File {
if base < 0 {
base = 1
}
return &File{sync.RWMutex{}, filename, index(base), index(size), []index{0}, nil}
}
// Name returns the file name of file f as registered with AddFile.
func (f *File) Name() string {
return f.name
}
// Base returns the base offset of file f as registered with AddFile.
func (f *File) Base() int {
return int(f.base)
}
// Size returns the size of file f as registered with AddFile.
func (f *File) Size() int {
return int(f.size)
}
// LineCount returns the number of lines in file f.
func (f *File) LineCount() int {
f.mutex.RLock()
n := len(f.lines)
f.mutex.RUnlock()
return n
}
// AddLine adds the line offset for a new line.
// The line offset must be larger than the offset for the previous line
// and smaller than the file size; otherwise the line offset is ignored.
func (f *File) AddLine(offset int) {
x := index(offset)
f.mutex.Lock()
if i := len(f.lines); (i == 0 || f.lines[i-1] < x) && x < f.size {
f.lines = append(f.lines, x)
}
f.mutex.Unlock()
}
// MergeLine merges a line with the following line. It is akin to replacing
// the newline character at the end of the line with a space (to not change the
// remaining offsets). To obtain the line number, consult e.g. Position.Line.
// MergeLine will panic if given an invalid line number.
func (f *File) MergeLine(line int) {
if line <= 0 {
panic("illegal line number (line numbering starts at 1)")
}
f.mutex.Lock()
defer f.mutex.Unlock()
if line >= len(f.lines) {
panic("illegal line number")
}
// To merge the line numbered <line> with the line numbered <line+1>,
// we need to remove the entry in lines corresponding to the line
// numbered <line+1>. The entry in lines corresponding to the line
// numbered <line+1> is located at index <line>, since indices in lines
// are 0-based and line numbers are 1-based.
copy(f.lines[line:], f.lines[line+1:])
f.lines = f.lines[:len(f.lines)-1]
}
// SetLines sets the line offsets for a file and reports whether it succeeded.
// The line offsets are the offsets of the first character of each line;
// for instance for the content "ab\nc\n" the line offsets are {0, 3}.
// An empty file has an empty line offset table.
// Each line offset must be larger than the offset for the previous line
// and smaller than the file size; otherwise SetLines fails and returns
// false.
// Callers must not mutate the provided slice after SetLines returns.
func (f *File) SetLines(lines []int) bool {
// verify validity of lines table
size := f.size
for i, offset := range lines {
if i > 0 && offset <= lines[i-1] || size <= index(offset) {
return false
}
}
// set lines table
f.mutex.Lock()
f.lines = f.lines[:0]
for _, l := range lines {
f.lines = append(f.lines, index(l))
}
f.mutex.Unlock()
return true
}
// SetLinesForContent sets the line offsets for the given file content.
// It ignores position-altering //line comments.
func (f *File) SetLinesForContent(content []byte) {
var lines []index
line := index(0)
for offset, b := range content {
if line >= 0 {
lines = append(lines, line)
}
line = -1
if b == '\n' {
line = index(offset) + 1
}
}
// set lines table
f.mutex.Lock()
f.lines = lines
f.mutex.Unlock()
}
// A lineInfo object describes alternative file and line number
// information (such as provided via a //line comment in a .go
// file) for a given file offset.
type lineInfo struct {
// fields are exported to make them accessible to gob
Offset int
Filename string
Line int
}
// AddLineInfo adds alternative file and line number information for
// a given file offset. The offset must be larger than the offset for
// the previously added alternative line info and smaller than the
// file size; otherwise the information is ignored.
//
// AddLineInfo is typically used to register alternative position
// information for //line filename:line comments in source files.
func (f *File) AddLineInfo(offset int, filename string, line int) {
x := index(offset)
f.mutex.Lock()
if i := len(f.infos); i == 0 || index(f.infos[i-1].Offset) < x && x < f.size {
f.infos = append(f.infos, lineInfo{offset, filename, line})
}
f.mutex.Unlock()
}
// Pos returns the Pos value for the given file offset;
// the offset must be <= f.Size().
// f.Pos(f.Offset(p)) == p.
func (f *File) Pos(offset int, rel RelPos) Pos {
if index(offset) > f.size {
panic("illegal file offset")
}
return Pos{f, toPos(f.base+index(offset)) + int(rel)}
}
// Offset returns the offset for the given file position p;
// p must be a valid Pos value in that file.
// f.Offset(f.Pos(offset)) == offset.
func (f *File) Offset(p Pos) int {
x := p.index()
if x < f.base || x > f.base+index(f.size) {
panic("illegal Pos value")
}
return int(x - f.base)
}
// Line returns the line number for the given file position p;
// p must be a Pos value in that file or NoPos.
func (f *File) Line(p Pos) int {
return f.Position(p).Line
}
func searchLineInfos(a []lineInfo, x int) int {
return sort.Search(len(a), func(i int) bool { return a[i].Offset > x }) - 1
}
// unpack returns the filename and line and column number for a file offset.
// If adjusted is set, unpack will return the filename and line information
// possibly adjusted by //line comments; otherwise those comments are ignored.
func (f *File) unpack(offset index, adjusted bool) (filename string, line, column int) {
filename = f.name
if i := searchInts(f.lines, offset); i >= 0 {
line, column = int(i+1), int(offset-f.lines[i]+1)
}
if adjusted && len(f.infos) > 0 {
// almost no files have extra line infos
if i := searchLineInfos(f.infos, int(offset)); i >= 0 {
alt := &f.infos[i]
filename = alt.Filename
if i := searchInts(f.lines, index(alt.Offset)); i >= 0 {
line += alt.Line - i - 1
}
}
}
return
}
func (f *File) position(p Pos, adjusted bool) (pos Position) {
offset := p.index() - f.base
pos.Offset = int(offset)
pos.Filename, pos.Line, pos.Column = f.unpack(offset, adjusted)
return
}
// PositionFor returns the Position value for the given file position p.
// If adjusted is set, the position may be adjusted by position-altering
// //line comments; otherwise those comments are ignored.
// p must be a Pos value in f or NoPos.
func (f *File) PositionFor(p Pos, adjusted bool) (pos Position) {
x := p.index()
if p != NoPos {
if x < f.base || x > f.base+f.size {
panic("illegal Pos value")
}
pos = f.position(p, adjusted)
}
return
}
// Position returns the Position value for the given file position p.
// Calling f.Position(p) is equivalent to calling f.PositionFor(p, true).
func (f *File) Position(p Pos) (pos Position) {
return f.PositionFor(p, true)
}
// -----------------------------------------------------------------------------
// Helper functions
func searchInts(a []index, x index) int {
// This function body is a manually inlined version of:
//
// return sort.Search(len(a), func(i int) bool { return a[i] > x }) - 1
//
// With better compiler optimizations, this may not be needed in the
// future, but at the moment this change improves the go/printer
// benchmark performance by ~30%. This has a direct impact on the
// speed of gofmt and thus seems worthwhile (2011-04-29).
// TODO(gri): Remove this when compilers have caught up.
i, j := 0, len(a)
for i < j {
h := i + (j-i)/2 // avoid overflow when computing h
// i ≤ h < j
if a[h] <= x {
i = h + 1
} else {
j = h
}
}
return i - 1
}