1 // Copyright 2010 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
13 // -----------------------------------------------------------------------------
16 // Position describes an arbitrary source position
17 // including the file, line, and column location.
18 // A Position is valid if the line number is > 0.
20 type Position
struct {
21 Filename
string // filename, if any
22 Offset
int // offset, starting at 0
23 Line
int // line number, starting at 1
24 Column
int // column number, starting at 1 (byte count)
27 // IsValid reports whether the position is valid.
28 func (pos
*Position
) IsValid() bool { return pos
.Line
> 0 }
30 // String returns a string in one of several forms:
32 // file:line:column valid position with file name
33 // file:line valid position with file name but no column (column == 0)
34 // line:column valid position without file name
35 // line valid position without file name and no column (column == 0)
36 // file invalid position with file name
37 // - invalid position without file name
39 func (pos Position
) String() string {
45 s
+= fmt
.Sprintf("%d", pos
.Line
)
47 s
+= fmt
.Sprintf(":%d", pos
.Column
)
56 // Pos is a compact encoding of a source position within a file set.
57 // It can be converted into a Position for a more convenient, but much
58 // larger, representation.
60 // The Pos value for a given file is a number in the range [base, base+size],
61 // where base and size are specified when adding the file to the file set via
64 // To create the Pos value for a specific source offset (measured in bytes),
65 // first add the respective file to the current file set using FileSet.AddFile
66 // and then call File.Pos(offset) for that file. Given a Pos value p
67 // for a specific file set fset, the corresponding Position value is
68 // obtained by calling fset.Position(p).
70 // Pos values can be compared directly with the usual comparison operators:
71 // If two Pos values p and q are in the same file, comparing p and q is
72 // equivalent to comparing the respective source file offsets. If p and q
73 // are in different files, p < q is true if the file implied by p was added
74 // to the respective file set before the file implied by q.
78 // The zero value for Pos is NoPos; there is no file and line information
79 // associated with it, and NoPos.IsValid() is false. NoPos is always
80 // smaller than any other Pos value. The corresponding Position value
81 // for NoPos is the zero value for Position.
85 // IsValid reports whether the position is valid.
86 func (p Pos
) IsValid() bool {
90 // -----------------------------------------------------------------------------
93 // A File is a handle for a file belonging to a FileSet.
94 // A File has a name, size, and line offset table.
98 name
string // file name as provided to AddFile
99 base
int // Pos value range for this file is [base...base+size]
100 size
int // file size as provided to AddFile
102 // lines and infos are protected by mutex
104 lines
[]int // lines contains the offset of the first character for each line (the first entry is always 0)
108 // Name returns the file name of file f as registered with AddFile.
109 func (f
*File
) Name() string {
113 // Base returns the base offset of file f as registered with AddFile.
114 func (f
*File
) Base() int {
118 // Size returns the size of file f as registered with AddFile.
119 func (f
*File
) Size() int {
123 // LineCount returns the number of lines in file f.
124 func (f
*File
) LineCount() int {
131 // AddLine adds the line offset for a new line.
132 // The line offset must be larger than the offset for the previous line
133 // and smaller than the file size; otherwise the line offset is ignored.
135 func (f
*File
) AddLine(offset
int) {
137 if i
:= len(f
.lines
); (i
== 0 || f
.lines
[i
-1] < offset
) && offset
< f
.size
{
138 f
.lines
= append(f
.lines
, offset
)
143 // MergeLine merges a line with the following line. It is akin to replacing
144 // the newline character at the end of the line with a space (to not change the
145 // remaining offsets). To obtain the line number, consult e.g. Position.Line.
146 // MergeLine will panic if given an invalid line number.
148 func (f
*File
) MergeLine(line
int) {
150 panic("illegal line number (line numbering starts at 1)")
153 defer f
.mutex
.Unlock()
154 if line
>= len(f
.lines
) {
155 panic("illegal line number")
157 // To merge the line numbered <line> with the line numbered <line+1>,
158 // we need to remove the entry in lines corresponding to the line
159 // numbered <line+1>. The entry in lines corresponding to the line
160 // numbered <line+1> is located at index <line>, since indices in lines
161 // are 0-based and line numbers are 1-based.
162 copy(f
.lines
[line
:], f
.lines
[line
+1:])
163 f
.lines
= f
.lines
[:len(f
.lines
)-1]
166 // SetLines sets the line offsets for a file and reports whether it succeeded.
167 // The line offsets are the offsets of the first character of each line;
168 // for instance for the content "ab\nc\n" the line offsets are {0, 3}.
169 // An empty file has an empty line offset table.
170 // Each line offset must be larger than the offset for the previous line
171 // and smaller than the file size; otherwise SetLines fails and returns
173 // Callers must not mutate the provided slice after SetLines returns.
175 func (f
*File
) SetLines(lines
[]int) bool {
176 // verify validity of lines table
178 for i
, offset
:= range lines
{
179 if i
> 0 && offset
<= lines
[i
-1] || size
<= offset
{
191 // SetLinesForContent sets the line offsets for the given file content.
192 // It ignores position-altering //line comments.
193 func (f
*File
) SetLinesForContent(content
[]byte) {
196 for offset
, b
:= range content
{
198 lines
= append(lines
, line
)
212 // A lineInfo object describes alternative file, line, and column
213 // number information (such as provided via a //line directive)
214 // for a given file offset.
215 type lineInfo
struct {
216 // fields are exported to make them accessible to gob
222 // AddLineInfo is like AddLineColumnInfo with a column = 1 argument.
223 // It is here for backward-compatibility for code prior to Go 1.11.
225 func (f
*File
) AddLineInfo(offset
int, filename
string, line
int) {
226 f
.AddLineColumnInfo(offset
, filename
, line
, 1)
229 // AddLineColumnInfo adds alternative file, line, and column number
230 // information for a given file offset. The offset must be larger
231 // than the offset for the previously added alternative line info
232 // and smaller than the file size; otherwise the information is
235 // AddLineColumnInfo is typically used to register alternative position
236 // information for line directives such as //line filename:line:column.
238 func (f
*File
) AddLineColumnInfo(offset
int, filename
string, line
, column
int) {
240 if i
:= len(f
.infos
); i
== 0 || f
.infos
[i
-1].Offset
< offset
&& offset
< f
.size
{
241 f
.infos
= append(f
.infos
, lineInfo
{offset
, filename
, line
, column
})
246 // Pos returns the Pos value for the given file offset;
247 // the offset must be <= f.Size().
248 // f.Pos(f.Offset(p)) == p.
250 func (f
*File
) Pos(offset
int) Pos
{
252 panic("illegal file offset")
254 return Pos(f
.base
+ offset
)
257 // Offset returns the offset for the given file position p;
258 // p must be a valid Pos value in that file.
259 // f.Offset(f.Pos(offset)) == offset.
261 func (f
*File
) Offset(p Pos
) int {
262 if int(p
) < f
.base ||
int(p
) > f
.base
+f
.size
{
263 panic("illegal Pos value")
265 return int(p
) - f
.base
268 // Line returns the line number for the given file position p;
269 // p must be a Pos value in that file or NoPos.
271 func (f
*File
) Line(p Pos
) int {
272 return f
.Position(p
).Line
275 func searchLineInfos(a
[]lineInfo
, x
int) int {
276 return sort
.Search(len(a
), func(i
int) bool { return a
[i
].Offset
> x
}) - 1
279 // unpack returns the filename and line and column number for a file offset.
280 // If adjusted is set, unpack will return the filename and line information
281 // possibly adjusted by //line comments; otherwise those comments are ignored.
283 func (f
*File
) unpack(offset
int, adjusted
bool) (filename
string, line
, column
int) {
285 defer f
.mutex
.Unlock()
287 if i
:= searchInts(f
.lines
, offset
); i
>= 0 {
288 line
, column
= i
+1, offset
-f
.lines
[i
]+1
290 if adjusted
&& len(f
.infos
) > 0 {
291 // few files have extra line infos
292 if i
:= searchLineInfos(f
.infos
, offset
); i
>= 0 {
294 filename
= alt
.Filename
295 if i
:= searchInts(f
.lines
, alt
.Offset
); i
>= 0 {
296 // i+1 is the line at which the alternative position was recorded
297 d
:= line
- (i
+ 1) // line distance from alternative position base
300 // alternative column is unknown => relative column is unknown
301 // (the current specification for line directives requires
302 // this to apply until the next PosBase/line directive,
303 // not just until the new newline)
306 // the alternative position base is on the current line
307 // => column is relative to alternative column
308 column
= alt
.Column
+ (offset
- alt
.Offset
)
316 func (f
*File
) position(p Pos
, adjusted
bool) (pos Position
) {
317 offset
:= int(p
) - f
.base
319 pos
.Filename
, pos
.Line
, pos
.Column
= f
.unpack(offset
, adjusted
)
323 // PositionFor returns the Position value for the given file position p.
324 // If adjusted is set, the position may be adjusted by position-altering
325 // //line comments; otherwise those comments are ignored.
326 // p must be a Pos value in f or NoPos.
328 func (f
*File
) PositionFor(p Pos
, adjusted
bool) (pos Position
) {
330 if int(p
) < f
.base ||
int(p
) > f
.base
+f
.size
{
331 panic("illegal Pos value")
333 pos
= f
.position(p
, adjusted
)
338 // Position returns the Position value for the given file position p.
339 // Calling f.Position(p) is equivalent to calling f.PositionFor(p, true).
341 func (f
*File
) Position(p Pos
) (pos Position
) {
342 return f
.PositionFor(p
, true)
345 // -----------------------------------------------------------------------------
348 // A FileSet represents a set of source files.
349 // Methods of file sets are synchronized; multiple goroutines
350 // may invoke them concurrently.
352 type FileSet
struct {
353 mutex sync
.RWMutex
// protects the file set
354 base
int // base offset for the next file
355 files
[]*File
// list of files in the order added to the set
356 last
*File
// cache of last file looked up
359 // NewFileSet creates a new file set.
360 func NewFileSet() *FileSet
{
362 base
: 1, // 0 == NoPos
366 // Base returns the minimum base offset that must be provided to
367 // AddFile when adding the next file.
369 func (s
*FileSet
) Base() int {
377 // AddFile adds a new file with a given filename, base offset, and file size
378 // to the file set s and returns the file. Multiple files may have the same
379 // name. The base offset must not be smaller than the FileSet's Base(), and
380 // size must not be negative. As a special case, if a negative base is provided,
381 // the current value of the FileSet's Base() is used instead.
383 // Adding the file will set the file set's Base() value to base + size + 1
384 // as the minimum base value for the next file. The following relationship
385 // exists between a Pos value p for a given file offset offs:
387 // int(p) = base + offs
389 // with offs in the range [0, size] and thus p in the range [base, base+size].
390 // For convenience, File.Pos may be used to create file-specific position
391 // values from a file offset.
393 func (s
*FileSet
) AddFile(filename
string, base
, size
int) *File
{
395 defer s
.mutex
.Unlock()
399 if base
< s
.base || size
< 0 {
400 panic("illegal base or size")
402 // base >= s.base && size >= 0
403 f
:= &File
{set
: s
, name
: filename
, base
: base
, size
: size
, lines
: []int{0}}
404 base
+= size
+ 1 // +1 because EOF also has a position
406 panic("token.Pos offset overflow (> 2G of source code in file set)")
408 // add the file to the file set
410 s
.files
= append(s
.files
, f
)
415 // Iterate calls f for the files in the file set in the order they were added
416 // until f returns false.
418 func (s
*FileSet
) Iterate(f
func(*File
) bool) {
422 if i
< len(s
.files
) {
426 if file
== nil ||
!f(file
) {
432 func searchFiles(a
[]*File
, x
int) int {
433 return sort
.Search(len(a
), func(i
int) bool { return a
[i
].base
> x
}) - 1
436 func (s
*FileSet
) file(p Pos
) *File
{
438 // common case: p is in last file
439 if f
:= s
.last
; f
!= nil && f
.base
<= int(p
) && int(p
) <= f
.base
+f
.size
{
443 // p is not in last file - search all files
444 if i
:= searchFiles(s
.files
, int(p
)); i
>= 0 {
446 // f.base <= int(p) by definition of searchFiles
447 if int(p
) <= f
.base
+f
.size
{
450 s
.last
= f
// race is ok - s.last is only a cache
459 // File returns the file that contains the position p.
460 // If no such file is found (for instance for p == NoPos),
461 // the result is nil.
463 func (s
*FileSet
) File(p Pos
) (f
*File
) {
470 // PositionFor converts a Pos p in the fileset into a Position value.
471 // If adjusted is set, the position may be adjusted by position-altering
472 // //line comments; otherwise those comments are ignored.
473 // p must be a Pos value in s or NoPos.
475 func (s
*FileSet
) PositionFor(p Pos
, adjusted
bool) (pos Position
) {
477 if f
:= s
.file(p
); f
!= nil {
478 return f
.position(p
, adjusted
)
484 // Position converts a Pos p in the fileset into a Position value.
485 // Calling s.Position(p) is equivalent to calling s.PositionFor(p, true).
487 func (s
*FileSet
) Position(p Pos
) (pos Position
) {
488 return s
.PositionFor(p
, true)
491 // -----------------------------------------------------------------------------
494 func searchInts(a
[]int, x
int) int {
495 // This function body is a manually inlined version of:
497 // return sort.Search(len(a), func(i int) bool { return a[i] > x }) - 1
499 // With better compiler optimizations, this may not be needed in the
500 // future, but at the moment this change improves the go/printer
501 // benchmark performance by ~30%. This has a direct impact on the
502 // speed of gofmt and thus seems worthwhile (2011-04-29).
503 // TODO(gri): Remove this when compilers have caught up.
506 h
:= i
+ (j
-i
)/2 // avoid overflow when computing h