blob: 937108382b974e3f8cef6b6243900e8bc2e199af [file] [log] [blame]
Marcel van Lohuizen8a7fc452018-12-10 15:19:41 +01001// Copyright 2018 The CUE Authors
2//
3// Licensed under the Apache License, Version 2.0 (the "License");
4// you may not use this file except in compliance with the License.
5// You may obtain a copy of the License at
6//
7// http://www.apache.org/licenses/LICENSE-2.0
8//
9// Unless required by applicable law or agreed to in writing, software
10// distributed under the License is distributed on an "AS IS" BASIS,
11// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12// See the License for the specific language governing permissions and
13// limitations under the License.
14
15package token
16
17import (
18 "fmt"
19 "sort"
20 "sync"
21)
22
23// -----------------------------------------------------------------------------
24// Positions
25
26// Position describes an arbitrary source position
27// including the file, line, and column location.
28// A Position is valid if the line number is > 0.
29type Position struct {
30 Filename string // filename, if any
31 Offset int // offset, starting at 0
32 Line int // line number, starting at 1
33 Column int // column number, starting at 1 (byte count)
34 // RelPos Pos // relative position information
35}
36
37// IsValid reports whether the position is valid.
38func (pos *Position) IsValid() bool { return pos.Line > 0 }
39
40// String returns a string in one of several forms:
41//
42// file:line:column valid position with file name
43// line:column valid position without file name
44// file invalid position with file name
45// - invalid position without file name
46//
47func (pos Position) String() string {
48 s := pos.Filename
49 if pos.IsValid() {
50 if s != "" {
51 s += ":"
52 }
53 s += fmt.Sprintf("%d:%d", pos.Line, pos.Column)
54 }
55 if s == "" {
56 s = "-"
57 }
58 return s
59}
60
Marcel van Lohuizena6b9de32019-05-21 07:18:23 -040061// Pos is a compact encoding of a source position within a file, as well as
Marcel van Lohuizen8a7fc452018-12-10 15:19:41 +010062// relative positioning information. It can be converted into a Position for a
63// more convenient, but much larger, representation.
64//
Marcel van Lohuizend094cbe2019-05-20 17:46:48 -040065type Pos struct {
66 file *File
67 offset int
68}
Marcel van Lohuizen8a7fc452018-12-10 15:19:41 +010069
Marcel van Lohuizena6b9de32019-05-21 07:18:23 -040070// File returns the file that contains the position p or nil if there is no
71// such file (for instance for p == NoPos).
72//
73func (p Pos) File() *File {
74 if p.index() == 0 {
75 return nil
76 }
77 return p.file
78}
79
80func (p Pos) Line() int {
81 if p.file == nil {
82 return 0
83 }
84 return p.Position().Line
85}
86
Marcel van Lohuizen0dcad0e2019-06-08 20:58:56 +020087func (p Pos) Column() int {
88 if p.file == nil {
89 return 0
90 }
91 return p.Position().Column
92}
93
94func (p Pos) Filename() string {
95 if p.file == nil {
96 return ""
97 }
98 return p.Position().Filename
99}
100
Marcel van Lohuizena6b9de32019-05-21 07:18:23 -0400101func (p Pos) Position() Position {
102 if p.file == nil {
103 return Position{}
104 }
105 return p.file.Position(p)
106}
107
108func (p Pos) String() string {
109 return p.Position().String()
110}
111
Marcel van Lohuizen8a7fc452018-12-10 15:19:41 +0100112// NoPos is the zero value for Pos; there is no file and line information
113// associated with it, and NoPos().IsValid() is false. NoPos is always
114// smaller than any other Pos value. The corresponding Position value
115// for NoPos is the zero value for Position.
Marcel van Lohuizend094cbe2019-05-20 17:46:48 -0400116var NoPos = Pos{}
Marcel van Lohuizen8a7fc452018-12-10 15:19:41 +0100117
118// RelPos indicates the relative position of token to the previous token.
119type RelPos int
120
121const (
122 // NoRelPos indicates no relative position is specified.
123 NoRelPos RelPos = iota
124
125 // Elided indicates that the token for which this position is defined is
126 // not rendered at all.
127 Elided
128
129 // NoSpace indicates there is no whitespace after this token.
130 NoSpace
131
132 // Blank means there is horizontal space after this token.
133 Blank
134
135 // Newline means there is a single newline after this token.
136 Newline
137
138 // NewSection means there are two or more newlines after this token.
139 NewSection
140
Marcel van Lohuizend094cbe2019-05-20 17:46:48 -0400141 relMask = 0xf
142 relShift = 4
Marcel van Lohuizen8a7fc452018-12-10 15:19:41 +0100143)
144
145var relNames = []string{
146 "invalid", "elided", "nospace", "blank", "newline", "section",
147}
148
149func (p RelPos) String() string { return relNames[p] }
150
Marcel van Lohuizend094cbe2019-05-20 17:46:48 -0400151func (p RelPos) Pos() Pos {
152 return Pos{nil, int(p)}
153}
154
Marcel van Lohuizen8a7fc452018-12-10 15:19:41 +0100155// HasRelPos repors whether p has a relative position.
156func (p Pos) HasRelPos() bool {
Marcel van Lohuizend094cbe2019-05-20 17:46:48 -0400157 return p.offset&relMask != 0
Marcel van Lohuizen8a7fc452018-12-10 15:19:41 +0100158
159}
160
Marcel van Lohuizend094cbe2019-05-20 17:46:48 -0400161func (p Pos) Before(q Pos) bool {
162 return p.file == q.file && p.Offset() < q.Offset()
163}
164
165// Offset reports the byte offset relative to the file.
166func (p Pos) Offset() int {
Marcel van Lohuizen0dcad0e2019-06-08 20:58:56 +0200167 return p.Position().Offset
Marcel van Lohuizend094cbe2019-05-20 17:46:48 -0400168}
169
170// Add creates a new position relative to the p offset by n.
Marcel van Lohuizen8a7fc452018-12-10 15:19:41 +0100171func (p Pos) Add(n int) Pos {
Marcel van Lohuizend094cbe2019-05-20 17:46:48 -0400172 return Pos{p.file, p.offset + toPos(index(n))}
Marcel van Lohuizen8a7fc452018-12-10 15:19:41 +0100173}
174
175// IsValid reports whether the position is valid.
176func (p Pos) IsValid() bool {
177 return p != NoPos
178}
179
180// IsNewline reports whether the relative information suggests this node should
181// be printed on a new lien.
182func (p Pos) IsNewline() bool {
183 return p.RelPos() >= Newline
184}
185
186func (p Pos) WithRel(rel RelPos) Pos {
Marcel van Lohuizend094cbe2019-05-20 17:46:48 -0400187 return Pos{p.file, p.offset&^relMask | int(rel)}
Marcel van Lohuizen8a7fc452018-12-10 15:19:41 +0100188}
189
190func (p Pos) RelPos() RelPos {
Marcel van Lohuizend094cbe2019-05-20 17:46:48 -0400191 return RelPos(p.offset & relMask)
Marcel van Lohuizen8a7fc452018-12-10 15:19:41 +0100192}
193
194func (p Pos) index() index {
Marcel van Lohuizend094cbe2019-05-20 17:46:48 -0400195 return index(p.offset) >> relShift
Marcel van Lohuizen8a7fc452018-12-10 15:19:41 +0100196}
197
Marcel van Lohuizend094cbe2019-05-20 17:46:48 -0400198func toPos(x index) int {
199 return (int(x) << relShift)
Marcel van Lohuizen8a7fc452018-12-10 15:19:41 +0100200}
201
202// -----------------------------------------------------------------------------
203// File
204
205type index int
206
Marcel van Lohuizen8a7fc452018-12-10 15:19:41 +0100207// A File has a name, size, and line offset table.
208type File struct {
Marcel van Lohuizena6b9de32019-05-21 07:18:23 -0400209 mutex sync.RWMutex
210 name string // file name as provided to AddFile
211 base index // Pos index range for this file is [base...base+size]
212 size index // file size as provided to AddFile
Marcel van Lohuizen8a7fc452018-12-10 15:19:41 +0100213
214 // lines and infos are protected by set.mutex
215 lines []index // lines contains the offset of the first character for each line (the first entry is always 0)
216 infos []lineInfo
217}
218
Marcel van Lohuizena6b9de32019-05-21 07:18:23 -0400219// NewFile returns a new file.
220func NewFile(filename string, base, size int) *File {
221 if base < 0 {
222 base = 1
223 }
224 return &File{sync.RWMutex{}, filename, index(base), index(size), []index{0}, nil}
225}
226
Marcel van Lohuizen8a7fc452018-12-10 15:19:41 +0100227// Name returns the file name of file f as registered with AddFile.
228func (f *File) Name() string {
229 return f.name
230}
231
232// Base returns the base offset of file f as registered with AddFile.
233func (f *File) Base() int {
234 return int(f.base)
235}
236
237// Size returns the size of file f as registered with AddFile.
238func (f *File) Size() int {
239 return int(f.size)
240}
241
242// LineCount returns the number of lines in file f.
243func (f *File) LineCount() int {
Marcel van Lohuizena6b9de32019-05-21 07:18:23 -0400244 f.mutex.RLock()
Marcel van Lohuizen8a7fc452018-12-10 15:19:41 +0100245 n := len(f.lines)
Marcel van Lohuizena6b9de32019-05-21 07:18:23 -0400246 f.mutex.RUnlock()
Marcel van Lohuizen8a7fc452018-12-10 15:19:41 +0100247 return n
248}
249
250// AddLine adds the line offset for a new line.
251// The line offset must be larger than the offset for the previous line
252// and smaller than the file size; otherwise the line offset is ignored.
253//
254func (f *File) AddLine(offset int) {
255 x := index(offset)
Marcel van Lohuizena6b9de32019-05-21 07:18:23 -0400256 f.mutex.Lock()
Marcel van Lohuizen8a7fc452018-12-10 15:19:41 +0100257 if i := len(f.lines); (i == 0 || f.lines[i-1] < x) && x < f.size {
258 f.lines = append(f.lines, x)
259 }
Marcel van Lohuizena6b9de32019-05-21 07:18:23 -0400260 f.mutex.Unlock()
Marcel van Lohuizen8a7fc452018-12-10 15:19:41 +0100261}
262
263// MergeLine merges a line with the following line. It is akin to replacing
264// the newline character at the end of the line with a space (to not change the
265// remaining offsets). To obtain the line number, consult e.g. Position.Line.
266// MergeLine will panic if given an invalid line number.
267//
268func (f *File) MergeLine(line int) {
269 if line <= 0 {
270 panic("illegal line number (line numbering starts at 1)")
271 }
Marcel van Lohuizena6b9de32019-05-21 07:18:23 -0400272 f.mutex.Lock()
273 defer f.mutex.Unlock()
Marcel van Lohuizen8a7fc452018-12-10 15:19:41 +0100274 if line >= len(f.lines) {
275 panic("illegal line number")
276 }
277 // To merge the line numbered <line> with the line numbered <line+1>,
278 // we need to remove the entry in lines corresponding to the line
279 // numbered <line+1>. The entry in lines corresponding to the line
280 // numbered <line+1> is located at index <line>, since indices in lines
281 // are 0-based and line numbers are 1-based.
282 copy(f.lines[line:], f.lines[line+1:])
283 f.lines = f.lines[:len(f.lines)-1]
284}
285
286// SetLines sets the line offsets for a file and reports whether it succeeded.
287// The line offsets are the offsets of the first character of each line;
288// for instance for the content "ab\nc\n" the line offsets are {0, 3}.
289// An empty file has an empty line offset table.
290// Each line offset must be larger than the offset for the previous line
291// and smaller than the file size; otherwise SetLines fails and returns
292// false.
293// Callers must not mutate the provided slice after SetLines returns.
294//
295func (f *File) SetLines(lines []int) bool {
296 // verify validity of lines table
297 size := f.size
298 for i, offset := range lines {
299 if i > 0 && offset <= lines[i-1] || size <= index(offset) {
300 return false
301 }
302 }
303
304 // set lines table
Marcel van Lohuizena6b9de32019-05-21 07:18:23 -0400305 f.mutex.Lock()
Marcel van Lohuizen8a7fc452018-12-10 15:19:41 +0100306 f.lines = f.lines[:0]
307 for _, l := range lines {
308 f.lines = append(f.lines, index(l))
309 }
Marcel van Lohuizena6b9de32019-05-21 07:18:23 -0400310 f.mutex.Unlock()
Marcel van Lohuizen8a7fc452018-12-10 15:19:41 +0100311 return true
312}
313
314// SetLinesForContent sets the line offsets for the given file content.
315// It ignores position-altering //line comments.
316func (f *File) SetLinesForContent(content []byte) {
317 var lines []index
318 line := index(0)
319 for offset, b := range content {
320 if line >= 0 {
321 lines = append(lines, line)
322 }
323 line = -1
324 if b == '\n' {
325 line = index(offset) + 1
326 }
327 }
328
329 // set lines table
Marcel van Lohuizena6b9de32019-05-21 07:18:23 -0400330 f.mutex.Lock()
Marcel van Lohuizen8a7fc452018-12-10 15:19:41 +0100331 f.lines = lines
Marcel van Lohuizena6b9de32019-05-21 07:18:23 -0400332 f.mutex.Unlock()
Marcel van Lohuizen8a7fc452018-12-10 15:19:41 +0100333}
334
335// A lineInfo object describes alternative file and line number
336// information (such as provided via a //line comment in a .go
337// file) for a given file offset.
338type lineInfo struct {
339 // fields are exported to make them accessible to gob
340 Offset int
341 Filename string
342 Line int
343}
344
345// AddLineInfo adds alternative file and line number information for
346// a given file offset. The offset must be larger than the offset for
347// the previously added alternative line info and smaller than the
348// file size; otherwise the information is ignored.
349//
350// AddLineInfo is typically used to register alternative position
351// information for //line filename:line comments in source files.
352//
353func (f *File) AddLineInfo(offset int, filename string, line int) {
354 x := index(offset)
Marcel van Lohuizena6b9de32019-05-21 07:18:23 -0400355 f.mutex.Lock()
Marcel van Lohuizen8a7fc452018-12-10 15:19:41 +0100356 if i := len(f.infos); i == 0 || index(f.infos[i-1].Offset) < x && x < f.size {
357 f.infos = append(f.infos, lineInfo{offset, filename, line})
358 }
Marcel van Lohuizena6b9de32019-05-21 07:18:23 -0400359 f.mutex.Unlock()
Marcel van Lohuizen8a7fc452018-12-10 15:19:41 +0100360}
361
362// Pos returns the Pos value for the given file offset;
363// the offset must be <= f.Size().
364// f.Pos(f.Offset(p)) == p.
365//
366func (f *File) Pos(offset int, rel RelPos) Pos {
367 if index(offset) > f.size {
368 panic("illegal file offset")
369 }
Marcel van Lohuizend094cbe2019-05-20 17:46:48 -0400370 return Pos{f, toPos(f.base+index(offset)) + int(rel)}
Marcel van Lohuizen8a7fc452018-12-10 15:19:41 +0100371}
372
373// Offset returns the offset for the given file position p;
374// p must be a valid Pos value in that file.
375// f.Offset(f.Pos(offset)) == offset.
376//
377func (f *File) Offset(p Pos) int {
378 x := p.index()
379 if x < f.base || x > f.base+index(f.size) {
380 panic("illegal Pos value")
381 }
382 return int(x - f.base)
383}
384
385// Line returns the line number for the given file position p;
386// p must be a Pos value in that file or NoPos.
387//
388func (f *File) Line(p Pos) int {
389 return f.Position(p).Line
390}
391
392func searchLineInfos(a []lineInfo, x int) int {
393 return sort.Search(len(a), func(i int) bool { return a[i].Offset > x }) - 1
394}
395
396// unpack returns the filename and line and column number for a file offset.
397// If adjusted is set, unpack will return the filename and line information
398// possibly adjusted by //line comments; otherwise those comments are ignored.
399//
400func (f *File) unpack(offset index, adjusted bool) (filename string, line, column int) {
401 filename = f.name
402 if i := searchInts(f.lines, offset); i >= 0 {
403 line, column = int(i+1), int(offset-f.lines[i]+1)
404 }
405 if adjusted && len(f.infos) > 0 {
406 // almost no files have extra line infos
407 if i := searchLineInfos(f.infos, int(offset)); i >= 0 {
408 alt := &f.infos[i]
409 filename = alt.Filename
410 if i := searchInts(f.lines, index(alt.Offset)); i >= 0 {
411 line += alt.Line - i - 1
412 }
413 }
414 }
415 return
416}
417
418func (f *File) position(p Pos, adjusted bool) (pos Position) {
419 offset := p.index() - f.base
420 pos.Offset = int(offset)
421 pos.Filename, pos.Line, pos.Column = f.unpack(offset, adjusted)
422 return
423}
424
425// PositionFor returns the Position value for the given file position p.
426// If adjusted is set, the position may be adjusted by position-altering
427// //line comments; otherwise those comments are ignored.
428// p must be a Pos value in f or NoPos.
429//
430func (f *File) PositionFor(p Pos, adjusted bool) (pos Position) {
431 x := p.index()
432 if p != NoPos {
433 if x < f.base || x > f.base+f.size {
434 panic("illegal Pos value")
435 }
436 pos = f.position(p, adjusted)
437 }
438 return
439}
440
441// Position returns the Position value for the given file position p.
442// Calling f.Position(p) is equivalent to calling f.PositionFor(p, true).
443//
444func (f *File) Position(p Pos) (pos Position) {
445 return f.PositionFor(p, true)
446}
447
Marcel van Lohuizen8a7fc452018-12-10 15:19:41 +0100448// -----------------------------------------------------------------------------
449// Helper functions
450
451func searchInts(a []index, x index) int {
452 // This function body is a manually inlined version of:
453 //
454 // return sort.Search(len(a), func(i int) bool { return a[i] > x }) - 1
455 //
456 // With better compiler optimizations, this may not be needed in the
457 // future, but at the moment this change improves the go/printer
458 // benchmark performance by ~30%. This has a direct impact on the
459 // speed of gofmt and thus seems worthwhile (2011-04-29).
460 // TODO(gri): Remove this when compilers have caught up.
461 i, j := 0, len(a)
462 for i < j {
463 h := i + (j-i)/2 // avoid overflow when computing h
464 // i ≤ h < j
465 if a[h] <= x {
466 i = h + 1
467 } else {
468 j = h
469 }
470 }
471 return i - 1
472}